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

一、综合题

1． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0

中的数据由

. 要求:

(1)给出算法的基本设计思想.

(2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由得到最终得到结果

(2)用C 语言算法描述如下:

第 2 页，共 27 页

变换为

原地逆置，

然后

，

再将数组R 中的前，ti-P 个数和后P 个数分别原地逆置，

(3)说明算法的复杂性:上述算法中3个Reverse 函数的的时间复杂度分别为O(p/2)、O((p-2)/2)为0(n/2)，故算法的时间复杂度为O(n)，算法的空间复杂度为0(1).

2． 两个字符串s1和s2的长度分别为m 和n 。求这两个字符串最大共同子串算法的时间复杂度为T(m，n) 。估算最优的T(m，n) ，并简要说明理由。

【答案】最优的T(m，n) 是D(n)。串S2是串S1的子串，且在S1中的位置是1。开始求出最 大公共子串的长度恰是串S2的长度。一般情况下，

3． 下列广义表，可以唯一对应一棵二叉树的有（ ）。并归纳出唯一对应的条件。

(1)(A(B(D，E) ，C(F))) (2)(A(B(D，E) ，C)) (3)(A)

(4)(A(B(C，D(E)))) (5)（ ）

【答案】唯一对应一棵二叉树的有(2)、(3)和(5)。唯一对应的条件:空表、只有一个元素的表、每个子表个数是零或是2的表。 4． 已知有6个顶点(顶点编号为0--5) 的有向带权图G , 其邻接矩阵A 为上三角矩阵, 按行为主序(行优先) 保存在如下的一维数组中。

要求:

(1)写出图G 的邻接矩阵A 。 (2)画出有向带权图G 。

(3)求图G 的关键路径, 并计算该关键路径的长度。

【答案】(1)由题可以画出待定上三角矩阵的结构图如下(图中？为待定元素) :

可以看出, 第一行至第五行主对角线上方的元素分别为5, 4, 3, 2, 1个, 由此可以画出压缩存储数组中的元素所属行的情况, 如下图所示:

第 3 页，共 27 页

将各元素填入各行即得邻接矩阵:

(2)根据第一步所得矩阵A 容易做出有向带权图G , 如下:

(3)下图中粗线箭头所标识的4个活动组成图G 的关键路径。

由上图容易求得图的关键路径长度为:

5．

一个长度为的中位数。例如, 若

(1)给出算法的基本设计思想。

的升序序列S ,

处在第

。

个位置的数为S 的中位数。例如,

若序列

则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列

, 则S1和S2的中位数是11。现有两个等长升序序列A

和B , 试设计一个时间和空间两方面都尽可能高效的算法, 找出两个序列A 和B 的中位数。要求:

(2)根据设计思想, 采用C 或C++或JA V A 语言描述算法, 关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。

【答案】(1)算法的基本设计思想:分别求两个升序序列A 和B 的中位数, 设为a 和b 。 ①若a=b, 则a 或b 即为所求的中位数。

②否则, 若ab, 中位数只能出现(b, a) 范围内, 舍弃b 所在序列B 的较小一半, 同时舍弃a 所在序列A 的较大一半。

③在保留的两个升序序列中求出新的中位数a 和b , 重复上述过程, 直到两个序列中只含一个元素时为止, 则较小者即为所求的中位数。

(2)用C 语言算法描述如下:

第 4 页，共 27 页