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

一、填空题

1． 实现字符串拷贝的函数strcpy 为：

【答案】

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

【答案】

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

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

【答案】15

【解析】当时，而，时，

4． 外排序的基本操作过程是_____和_____。

；归并 【答案】生成有序归并段（顺串）

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

【答案】

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

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

【答案】稳定

7． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

第 2 页，共 34 页

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

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

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

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

设编号为

和

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

和

。

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

【答案】

，

则结点

和

在同一层上的条件是

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

二、算法设计题

11．有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。

【答案】算法如下：

12．编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：

它们已用

域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由

域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【答案】算法如下：

第 3 页，共 34 页

13．设记录

的关键字为

树结点

的败者树，要求除

指向败者记录，

和

为全胜记以外，只用

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

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

14．请编写完整的程序。如果矩阵A 中存在这样的一个元素矩阵A 的所有马鞍点。

【答案】算法如下：

满足条件：

是第i 行中值

的

最小的元素，且又是第j 列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出

第 4 页，共 34 页