2017年河南科技大学数据结构考研复试核心题库
● 摘要
一、应用题
1． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题：
（1）画出哈希表示意图；
（2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示：
表 哈希示意图
（2）查找关键字63时，由于63比较。
（3）查找关键字60时，由于（4）
哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，
为关键字，用
线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）
2． 在二叉树的Llink-Rlink 存储表示中，引入“线索”的好处是什么？
【答案】在二叉链表表示的二叉树中，引入线索的目的主要是便于査找结点的前驱和后继，因为若知道各结点的后继，二叉树的遍历就非常简单。利用二叉链表结构查结点的左右子女非常方便. 但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，利用结点的空链域，左链为空时作为前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定：当ltag=0时，lchild 指向左子树，当ltag=1时，lchild 指向前驱：当rtag=0时，rchild 指向右子树，当rtag=l时，rctiild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（利用后序线索二叉树査后扔继续要栈）。
3． 设有正文AADBAACACCDACACAAD ，字符集为A , B , C , D , 设计一套二进制编码，使得上述正文的编码最短。
A :1, B :000，C :01，D :001。 【答案】字符A , B , C , D 出现的次数为9, 1, 5, 3。其哈夫曼编码如下：
4． 外排序中为何采用k 一路么？
【答案】外排序用路归并
合并而不用2—路合并? 这种技术用于内排序有意义吗? 为什是因为k 越小，归并趟数越多，读写外存次数越多，时间效
率越低，故一般应大于最少的2-路归并。若将k-路归并的败者树思想单纯用于内排序，因其由胜者树改进而来，且辅助空间大，完全可由堆排序取代，故将其用于内排序效率并不高。
5． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。 6． 已知有6个顶点（顶点编号为0--5）的有向带权图G , 其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。 要求： （1）写出图G 的邻接矩阵A 。 （2）画出有向带权图G 。 （3）求图G 的关键路径，并计算该关键路径的长度。 【答案】（1）由题可以画出待定上三角矩阵的结构图如下（图中? 为待定元素）： 可以看出，第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示： 将各元素填入各行即得邻接矩阵： （2）根据第一步所得矩阵A 容易做出有向带权图G , 如下： （3）下图中粗线箭头所标识的4个活动组成图G 的关键路径。 由上图容易求得图的关键路径长度为：4+5+4+3 = 16。 7． 设内存中可利用空间已连成一个单链表，对用户的存储空间需求，一般有哪三种分配策略？ 【答案】（1）首次适配法 从链表头指针开始查找，找到第一个大于等于所需空间的结点即分配。首次适配法适合事先不知道请求分配和释放信息的情况，分配时需查询，释放时插在表头。 （2）最佳适配法 链表结点大小增序排列，找到第一个大于等于所需空间的结点即分配。最佳适配法适用于请求分配内存大小范围较宽的系统，释放时容易产生存储量很小难以利用的内存碎片，同时保留那些很大的内存块以备将来可能发生的大内存量的需求，分配与回收均需查询。 （3）最差适配法 链表结点大小逆序排列，总从第一个结点开始分配，将分配后结点所剩空间插入到链表适当位置。最差适配法适合请求分配内存大小范围较窄的系统，分配时不查询，回收时查询，以便插入适当位置。 8． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？ 【答案】设归并路数为k ，归并趟数为s ，则最少5-路归并完成排序。 因 且k 为整数，故k=5，即 二、算法设计题 9． 设有两个栈操作算法。 【答案】栈的定义： 都采用顺序栈方式，并且共享一个存储区为了尽量利用空 间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计81, 82有关入栈和出栈的