2018年苏州大学计算机科学与技术学院839管理信息系统与数据结构之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏
2． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
3． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
4． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____ 【答案】
5． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
7． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
8． 模式串
【答案】01122312
9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
第 2 页，共 64 页 的next 函数值序列为_____。
10．
给定一组数据
WPL 的值为_____。
【答案】5；96 以它构造一棵哈夫曼树，则树高为_____，带权路径长度
【解析】每次找两个最小的权值构建哈夫曼树:
11．深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
12．从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
二、单项选择题
13．归并排序中，归并的趟数是（ ）。
A.O(n) B. C. D.
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数増加一倍。所以
。
14．分区分配内存管理方式的主要保护措施是（ ）.
A. 界地址保护
B. 程序代码保护
C. 数据保护
D. 栈保护
【答案】A
【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护. 通常的界地址保护方法采用软硬件结合的方法. 考生要注意本题与虚拟存储方法的区别.
第 3 页，共 64 页 。所以归并的趟数为
15．4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
16．下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。
【答案】D
【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息, 解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树, 左链域空, 无右子树, 右链域指向其后继结点b ; 结点b 无左子树, 左链域指向其前驱结点d ; 结点c 无左子树, 左链域指向其前驱结点b , 无右子树, 右链域指向其后继结点a 。所以正确选项为D 。
17．有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。
18．下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ ）。
A. 二叉排序树
第 4 页，共 64 页