2017年北京市培养单位光电研究院864程序设计之数据结构考研题库
● 摘要
一、填空题
1． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
【答案】（1）（2）（3）（4）（5）
2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
3． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，
元素个数为 一个元素时，此时堆的元素个数最少，元素个数为
5． 已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
6． 设数组数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（1）存放该数组至少需要的单元数是_____；
（2）存放数组的第8列的所有元素至少需要的单元数_____； （3）数组按列存储时，元素【答案】270; 27; 2204 【解析】数组的元素个数为需要
第8列有9个元素，共占
因为每个元素占内存48个二进制位，即6个字节。故总
个单元数。
个字节，因此至少需要
个单元数。由题知，每个元素占3
个字节，因为主内存字长为16位，即2个字节，所以至少需要
的起始地址是_____。
个单元。按列存储时，的起始地址为
7． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表ht[]中插入值为的元素，如该元素已在哈希表中，报告出错。
9． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
10．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
二、判断题
11．对于有n 个结点的二叉树，其高度为
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
12．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
且ri 在rj 之前，而在排序后的
序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
13．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）
【答案】
函数，函
【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个数本身包含了模式串的局部匹配信息。
14．在链队列中，即使不设置尾指针也能进行入队操作。（ ）
【答案】
（ ）