当前位置：问答库＞考研试题

一、填空题

1．

每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。

【答案】

【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。

2． 下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

【答案】

【解析】快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

.

，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的

3． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

【答案】

【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

4． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。

【答案】树。故结点个数为

5．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉

6． 在二叉树中，指针p 所指结点为叶结点的条件是_____。

【答案】

【解析】叶子节点的左右孩子都不存在。

7． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

8． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

9． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

10．已知一循环队列的存储空间为环队列判满的条件是（ ）

【答案】

其中队头和队尾指针分别为front 和rear , 则此循

二、判断题

11．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）

【答案】×

【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。

12．若一个广义表的表头为空表，则此广义表亦为空表。（ ）

【答案】×

【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。

13．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）

【答案】×

【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

且ri 在rj 之前，而在排序后的

序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

14．—个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）

【答案】×

【解析】图的邻接表表示法类似于树的孩子链表示法。对于图G 中的每个顶点V i ，该方法把所以邻接于顶点V i 的V j 链接成一个带头。在有向图中，为图中每个顶点V i 建立一个入边表的方法称为逆邻接表示法。

15．—个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（ ）

【答案】√

【解析】树的前序遍历和后序遍历叶子节点的相对次序是不变的，都遵循左右的次序。