2017年南昌航空大学信息工程学院817数据结构考研题库
● 摘要
一、填空题
1． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
2． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
3． 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为
4． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
5．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。
6． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
7． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
8． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1） 9． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
10．克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边 对应的前缀式为_____，若
则后缀式
的
（3）算法结束时，相邻矩阵中的元素指出最小生成树的
二、选择题
11．某计算机系统中有8台打印机，由K 个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K 最小值是（ ）。
A.2 B.3 C.4 D.5
【答案】C
【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行（这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析）。所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁。
12．假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
13．就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是复杂度也是
所需要的辅助存储为
仅仅表示的是一个量级，
比如
最好，是在综合考虑的情况下。
14．归并排序中，归并的趟数是（ ）。
【答案】B
【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，这组的元素个数为n
。因此每次归并元素的个数增加一倍。所以
15．在’体系结构中，直接为ICMP 提供服务的协议是（ ）。
A.PPP B.IP C.UDP D.TCP
【答案】B 。
所以归并的趟数为
所需要的辅助存储为和
的量级都为
虽然堆排序的时间
之所以说快排
看似堆排序比快速排序的性能好，
但是需要注意
【解析】首先明确ICMP 是网络层的协议，由于服务必须是下一层向上一层提供服务的，因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层，在网络层上面，所以显然错误，而PPP 协议是广域网数据链路层协议，直接为网络层，也就是IP 层提供服务，ICMP 协议是封装在网络层，因此PPP 不能直接为ICMP 提供服务，ICMP 报文直接封装在IP 分组中，故答案是B 。
16．已知程序如下：
{
}