2018年北京市培养单位软件研究所408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
2． 已知非空双向链表由d 指出，结点结构为(llink，data ，rlink) ，请设计算法将链表中数据域值最大(假定唯一) 的那个结点移至链表的最前面。要求:不得额外申请新的双链表结点。
【答案】算法如下:
//d是循环链表，本算法将链表中数据域值最大的结点移至链表的最前面
//设链表有头结点
//q指向待处理结点
//P记数据域值最大的结点
//将P 摘下
//插人P 结点
3． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。
【答案】算法如下:
（ ）
//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数
//整数存储到数组a ，i 记整数个数
//从左到右读入字符串
//'#'是字符串结束标记
//是数字字符
//数初始化
//拼数
//若拼数中输入了’#’，则不再输入
//输入非数字且非#时，继续输入字符
("共有
个整数，它们是:
)
//每10个数输出在一行上
//算法结束
4． 已知一具有n
个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组
和
中(设该二叉树各结点的数据值均不相同) 。请写一建立该二叉树的二叉链表结构的非递
归算法。该二叉链表的链结点结构为(lchild, data , rchild) ，其中data 为数据域，lchild 与rhild 分别为指向该结点左、右孩子的指针域(当孩子结点不存在时，相应指针域为空，用nil 表示) 。
【答案】算法如下:
由二叉树的中序序列IN[ ]和后序序列POST[ ]建立二叉树
和
为栈，容量足够大
初始化
取出栈顶数据
在中序序列中査等于
.
根结点的值
无左子树
分別是中序序列和后序序列第一和最后元素的下标，初始调用时
，
的结点
将建立左子树的数据入栈
无右子树
右子树数据入
结束
:
5． 写出一趟快速排序算法。
【答案】算法如下:
一趟快速排序算法，枢轴记录到位，并返回其所在位置
二、应用题
6． 设a ，b ，c ，d ，e 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现:ac ，Bd ，aa ，be ，ab ，ad ，cd ，be ，ae ，ce 。要求用哈希(Hash)方法将它们存入具有10个位置的表中。
(1)将上述关键字(标识符) 构造一个哈希函数，使得发生冲突尽可能地少； (2)线性探测再散列法解决冲突。写出上述各关键字在表中位置。
【答案】(1)构造的哈希函数为:哈希函数H(key)=(关键字各字符编码之和)MOD7。 (2)关键字在表中的位置如表所示:
表 关键字在表中的位置
7． 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能? 为什么？
【答案】特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元(对值相同元素只分配一个单元) ，将非零元素存储在向量中，元素的下标i 和j 和该元