2018年西南石油大学理学院925数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 在基于关键字比较且时间为
【答案】归并；堆
2． 高度为h 的堆中，最多有_____元素，最少有_____个元素。
【答案】
。当最后一层只有
【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为
_ 的排序中，若要求排序是稳定的，则可选用_____
排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。
一个元素时，此时堆的元素个数最少，元素个数为。
3． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
【答案】
4． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15 【解析】当
时，100n2>2n，而，
2n
时，100n ＜2
5． 在单链表中设置头结点的作用是_____。
【答案】方便运算
6． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
7． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
8． 中缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
9． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
10．在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式
的
【解析】叶子节点的左右孩子都不存在。
二、判断题
11．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
12． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】 ×
【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
13．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
14．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】 √
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
15．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
16．用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
17．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】 ×
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。