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

一、填空题

1． 数组的存储结构采用_____存储方式。

【答案】顺序存储结构

【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。

2． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）

【答案】3个

【解析】以3, 4先出栈的序列有34521、34215、34251共3个。

3． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

4． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

5． 假定查找有序表

【答案】37/12

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

表

平均查找次数为

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

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

7． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

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

8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

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

【答案】

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

10．

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

【答案】

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

11．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

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

【答案】

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

13．从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

14．数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

15．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

.

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

二、算法设计题

16．设整数序列

【答案】算法如下：

17．设记录

的关键字为

树结点

的败者树，要求除

指向败者记录，

和

为全胜记以外，只用

给出求解最大值的递归程序。

录下标。写一算法产生对应上述

辅助空间。 【答案】算法如下：

18．对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法（转换仅要求能够输出正确的十六进制的整数即可）。

【答案】算法如下：