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

一、填空题

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

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

2． 设广义表

则

是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

3． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

4． 设有两个算法在同一机器上运行，其执行时闻分别为_____。

【答案】15 【解析】当

时，

而

，

时，

要使前者快于后者，n 至少为

5． 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_____和_____; 而又根据指针的连接方式，链表又可分成_____和_____。

【答案】单链表；双链表；（动态）链表；静态链表

【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。

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

【答案】顺序存储结构

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

7． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：_____;

【答案】

8． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

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

【答案】快速

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

10．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

【答案】（1）（2）（3）（4）（5）

置空链表，然后将原链表结点逐个插入到有序表中

当链表尚未到尾，p 为工作指针

查P 结点在链表中的插入位置，这时q 是工作指针

将P 结点链入链表中

是q 的前驱，u 是下个待插入结点的指针

二、算法设计题

11．已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。

例如：

第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：

1，4，7……第一个数组

9，12，28，29，45……第二个数组 【答案】算法如下：

12．线性表中元素存放在向量和最小元素。

【答案】算法如下：

13．给定

矩阵

并设

设计一算法判定x 的值是否在A 中，

要求时间复杂度为

【答案】算法如下：

14．设求按

是一个记录构成的数组，

中，元素是整型数。试写出递归算法求出A 中的最大

是一个整数数组，其值介于1～100之间，现要

时，则要求将

的内容调整到

中

的内容调整A 中记录的次序，比如当

【答案】算法如下：

去。规定可使用的附加空间为