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

一、填空题

1． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

2． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

3． 已知二维数组

为1000的连续存储区域时，

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为：

4． 设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为_____。

【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

5． 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为

6． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

7． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。

【答案】序查找效率一样为

第 2 页，共 36 页

中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。

【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺

8． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ） 而快速排序算法需要比较的次数达到最大，时间复杂度为

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

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

10．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

二、算法设计题

11．叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179，208，93，306，55，859，984，9，271，33）

【答案】算法如下：

第 3 页，共 36 页

12．从键盘上输入一串正整数，最后输入-1作为结束标志。如：

请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为那么

序遍历次序的前驱结点的地址。

那么

【答案】算法如下：

第 4 页，共 36 页

其中：域为结点的数据场。

域中存在的是该结点的左儿子结点的地址。ltag=1，那么left 域中存放的是该结点的按中

那么right 域中存放的是该结点的右儿子结点的地址。

域中存放的是该结点的按中序遍历次序的后继结点地址。