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

一、填空题

1． 索引顺序文件既可以顺序存取，也可以_____存取。

【答案】随机

2． 假定查找有序表

【答案】37/12

【解析】折半查找时每个的次数如表所示：

表

平均查找次数为

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

第 2 页，共 57 页

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____

【答案】

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

4． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

5． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树 【解析】二叉排序树

或者是一棵空树，或者是具有下列性质的二叉树：①若它

的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

6．

=_____

【答案】5

7． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

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

【答案】

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

9． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。

【答案】要加“虚结点”。

第 3 页，共 57 页

【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，

设编号为

和

的结点在顺序存储中的下标为

和

。

，

则结点

和

在同一层上的条件是

10．在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

二、判断题

11．对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）

【答案】√

，【解析】形状不同的两个二叉排序树（关键字集合相同）在中序遍历下是输出排好序的序列，所以顺序是一致的。

12．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）

【答案】×

【解析】例如起泡排序是稳定排序，将4，3，2，1按起泡排序排成升序序列，第一趟变成3，2，1，4，此时3就朝向最终位置的相反方向移动。

13．数据结构的抽象操作的定义与具体实现有关。（ ）

【答案】

【解析】数据结构的抽象操作定义取决于客观存在的一组逻辑特性，与其在计算机内具体表示和实现无关。

14．串是一种数据对象和操作都特殊的线性表。（ ）

【答案】

【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。

15．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）

【答案】×

【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转

第 4 页，共 57 页