2017年中国刑事警察学院计算机软件综合之数据结构(C语言版)考研复试核心题库
● 摘要
一、应用题
1． 简述广义表属于线性结构的理由。
【答案】广义表中的元素，可以是原子，也可以是子表，即广义表是原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。
2． KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？
【答案】朴素的模式匹配度达到
时间复杂度是
KMP 算法有一定改进，时间复杂
主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配
时，KMP 算法的优点更为突出。
3． 设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？
【答案】设归并路数为k ，归并趟数为s ，则
因
且k 为整数，故k=5，即
最少5-路归并完成排序。
4． 以归并算法为例，比较内部排序和外部排序的不同，说明外部排序如何提高操作效率。
【答案】（1）内部排序中的归并排序是在内存中进行的归并排序，辅助空间为
外部归
并排序是将外存中的多个有序子文件合并成一个有序子文件，将每个子文件中记录读入内存后的排序方法可采用多种内排序方法。外部排序的效率主要取决于读写外存的次数，即归并的趟数。
（2）因为归并的趟数部排序的效率。
其中，m 是归并段个数，k 是归并路数。增大k 和减少m 都
可减少归并趟数。应用中通过败者树进行多（k ）路平衡归并和置换一选择排序减少m ，来提高外
5． 某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链一轮驻留集（扫描时间忽略不计）
尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程
（1）访问（2）访问（3）访问【答案】
（1）页框号为21。因为起始驻留集为空，而0页对应的页框为空闲链表中的第三个空闲页框，其对应的页框号为21。
（2）页框号为32。理由：因11>10故发生第三轮扫描，页号为1、3的页框32、15在第二轮已处于空闲页框链表中，此刻1页又被重新访问，因此应被重新放回到驻留集中。其页框号为32。
（3）页框号为41。理由：因为第2页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。
（4）适合。理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。
6． 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。
【答案】快速排序的思想如下：首先将待排序记录序列中的所有记录作为当前待排序区域，，凡其关键字不大干枢轴的记录均移动至该记录之前，以第一个记录的关键字作为枢轴（或支点）
凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序割成两部分：
和
和
且
将分
然后再递归地将
P
依次访问的<虚拟页号，访问时刻>是
：
请回答下列问题。
时，对应的页框号是什么？
时，对应的页框号是什么? 说明理由。 . 时，对应的页框号是什么? 说明理由。
（4）该策略是否适合于时间局部性好的程序? 说明理由。
进行快速排序。快速排序在记录有序时蜕变为起泡排序，可用“三者取中”法
改善其性能，避免最坏情况的出现。本题解答如下：
初始序列：[28]，07，39，10，65，14，61，17，50，21 21移动：21，07，39，10，65，14，61，17，50，[] 39移动：21，07，[]，10，65，14，61，17，50，39 17移动：21，07，17，10，65，14，61，[]，50，39 65移动：21，07，17，10，[]，14，61，65，50，39 14移动：21，07，17，10，14，[28]，61，65，50，39
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）
哈希地址12内为空，查找失败。 所以需要依次与31，46，47，32，17，
8． 试证明：同一棵二叉树的所有叶结点，在前序序列、对称序序列以及后序序列中都按相同的，例如前序后序运对称序。 相对位置出现（即先后顺序相同）
，中序遍历是“左根右”，后序遍历是“左右根”【答案】前序遍历是“根左右”。三种遍历中只是访问 " 根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位罝出现。
二、算法设计题
9． 元素集合己存入整型数组树T 的非递归算法
：
【答案】算法如下：
中，试写出依次取A 中各值
构造一棵二叉排序
相关内容
相关标签