2018年辽宁省培养单位沈阳自动化研究所864程序设计之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
2． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
3． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n
【解析】当时，100n2>2n，而，时，100n ＜2
4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
一个元素时，此时堆的元素个数最少，元素个数为。
5． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若
是边，则
的值等于_____，若
不是边，则A(i, j) 的值是一个比任何
置
边的权_____，矩阵的对角线元素全为0。
(2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素成_____，若
【答案】(1)
已包括进生成树，就把矩阵元素
置成_____。
(3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。
边上的权值；都大的数；(2)1; 负值；(3)为负；边
6． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
7． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
8． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
9． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
10．设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
11．在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
12．一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
二、单项选择题
13．某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2字节，逻辑地址结构为:
逻辑地址空间大小为（ ）.
A.64 B.128 C.256 D.512
【答案】B
字节，页表项大小为
页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是