2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研强化模拟题
● 摘要
一、填空题
1． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
2． 中缀式对应的前缀式为_____，若则后缀式运算结果为_____。
【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
3． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。
【答案】
【解析】哈夫曼树只有度为0和2的节点。
4． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
5． 起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
6． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
第 2 页，共 47 页
的
7． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
8． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
9． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
10．顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。 11．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
12．下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。
第 3 页，共 47 页
【答案】
【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
二、判断题
13．对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）
【答案】√
【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。
14．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第的最多结点数为
【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为
层全满时，
此时从根结点到第
层具有最大的结点数为
15．即使有向无环图的拓扑序列唯一，也不能唯一确定该图。（ ）
【答案】×
【解析】如果有向无环图的拓扑序列唯一，则能够确定每个结点的唯一前驱和后继，因此能够确定该图。
16．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
17．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过
【答案】×
【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段
第 4 页，共 47 页
层具有
余下的个结点在第k 层的任一位置上。（ ）
（ ）