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

一、填空题

1． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

2． 在基于关键字比较且时间为

【答案】归并；堆

3． 建立索引文件的目的是_____。

【答案】提高查找速度

4．

线性表

【答案】(n﹣1)/2

【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。

5． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

【解析】当

6． 模式串

【答案】01122312

时，100n2>2n，而，2n 时，100n ＜2 _ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。 用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。 的next 函数值序列为_____。

7． 已知t) ，LEN(t)＋1))

:

【答案】

8． 在哈希函数； ；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。 中，p 值最好取_____。

【答案】小于等于表长的最大素数或不包含小于20的质因子的合数

【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。

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

【答案】

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

10．顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

11．在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。

【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)

【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。

12．按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。

【答案】稳定

13．组成串的数据元素只能是_____。

【答案】字符

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

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

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

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

二、判断题

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

【答案】×

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

17．快速排序和归并排序在最坏情况下的比较次数都是（ ）

【答案】×

【解析】快速排序最坏的情况下比较次数是

18．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）

【答案】 ×

【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。

19．十字链表是无向图的一种存储结构。（ ）

【答案】×

【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧