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

一、填空题

1． 设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

2． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。

【答案】m/2

【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。

3． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储 4． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

5． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

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

【答案】

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

7． 当两个栈共享一存储区时，栈利用一维数组当栈1空时

，

【答案】

为_____，栈2空时

，

表示，两栈顶指针为则

为_____，栈满时为_____。

【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。 8． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

Prior （node , x ） { if（node !=null）

If （ （1） ） *x=node->right；else * x-node->left;

}

next （bt , node, x ）/*bt是二叉树的树根*/ { （2） ;

if （node->rflag）（3）; else {do t=*x；;

while （*x==node ）; *x=t; } }

【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）

9． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

10．阅读下列程序，指出其功能，并写出空格处应填上的语句。

的元素，如该元素已在哈希表中，报告出错。

【答案】

【解析】本题是在哈希表ht[]中插入值为

二、判断题

11．完全二叉树肯定是平衡二叉树。（ ）

【答案】×

【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。

12．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）

【答案】×

【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。

13．倒排文件的目的是为了多关键字查找。（ ）

【答案】√

【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。

14．在链队列中，即使不设置尾指针也能进行入队操作。（ ）

【答案】

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。