2017年华北理工大学y10数据结构(同等学力加试)考研复试核心题库
● 摘要
一、应用题
1． （1）对于有向无环图，叙述求拓扑有序序列的步骤；
（2）对于图1，写出它的四个不同的拓扑有序序列。
图1
【答案】（1）对有向图，求拓扑序列步骤为：
1）在有向图中选一个没有前驱（即入度为0）的顶点并输出。 2）在图中删除该顶点及所有以它为尾的弧。
3）重复1）和2）, 直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。
（2）拓扑有序序列如图2:
图2 拓扑有序序列
2． 在
树和
树中查找关键字时，有什么不同？
树的非终端结点是索引部分，其查找从根开始，从根往下查到关键
【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。
字后，要继续查到最下层结点，得到查找成功与否的结论。另外，键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。
3． 已知图的邻接矩阵为：
. 树还可以在最下层从最小关
当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出： （1）以顶点V1为出发点的唯一的深度优先遍历序列； （2）以顶点V1为出发点的唯一的广度优先遍历序列； （3）该图唯一的拓扑有序序列。
1）V1，V4，V9, V10，V7, V6, V8，V3，V2, V5 【答案】（（2） V1, V4, V3, V2, V9, V7, V6, Y5, V10, V8 （3） V1, V2, V5, V3, V4, V6, V8, V7, V9, VIO
4． 若森林共有n 个结点和b 条边（b 【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。 5． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？ 【答案】设归并路数为k ，归并趟数为s ，则 最少5-路归并完成排序。 6． 一个ISAM 文件除了主索引外，还包括哪两级索引？ 【答案】ISAM 文件有三级索引：磁盘组、柱面和磁盘，柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，可建立柱面索引的索引一主索引。故还包括的两级索引是盘组和磁道。 因 且k 为整数，故k=5，即 7． 设哈希（Hash ）表的地址范围为0～17，哈希函数为：造出哈希表，试回答下列问题： （1）画出哈希表示意图； （2）若查找关键字63，需要依次与哪些关键字比较？ （3）若查找关键字60，需要依次与哪些关键字比较？ （4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 【答案】（1）哈希表示意图如表所示： 表 哈希示意图 为关键字，用 线性探测再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49） （2）查找关键字63时，由于63比较。 （3）查找关键字60时，由于（4） 8． 设LS 是一个线性表， 若采用顺序存储结构，则在等概率的前提下，插 与 之间 的概率 为 哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17， 入一个元素需要平均移动的元素个数是多少? 若元素插 在 【答案】需要分两种情况讨论： ，插入位置0..n ，则平均移动个数为（1）等概率（后插） （2）若不等概率，则平均移动的元素个数为 则插入一个元素需要平均移动的元素个数又是多少？ 二、算法设计题 9． 试将下列递归过程改写为非递归过程。 【答案】算法如下：