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

一、算法设计题

1． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

2． 设整数序列ai ，a2，a3，…，an ，给出求解最大值的递归程序。

【答案】算法如下:

//设整数序列存于数组a 中，共有n 个，本算法求解其最大值

3． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

第 2 页，共 34 页

和B 的

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

T 数组初始化

若结点i 的左子女是则结点L 的

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是

i

判断U 是否是V 的后代

4． 给定nxm 矩阵

并设

设计一算法判定x 的值是否在A 中，要求时间复杂度

为O(m＋n) 。

【答案】算法如下:

//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中

//flag是成功査到x 的标志

//假定x 为整型

(“矩阵A 中无

算法search 结束。

5． 已知P 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(

) 改造为(

【答案】算法如下:

//本算法将线性表

//q指向a 1结点

//r记住a l 结点的指

针

//先将a 1结点放到正确位置

第 3 页，共 34 页

元素\n"，x) ；

) 。

改造为

//从a 2结点开始

//暂存后继

//对称放置

//恢复待处理结点

二、应用题

6． 设a ，b ，c ，d ，e 五个字符的编码分别为1，2，3，4，5，并设标识符依以下次序出现:ac ，Bd ，aa ，be ，ab ，ad ，cd ，be ，ae ，ce 。要求用哈希(Hash)方法将它们存入具有10个位置的表中。

(1)将上述关键字(标识符) 构造一个哈希函数，使得发生冲突尽可能地少； (2)线性探测再散列法解决冲突。写出上述各关键字在表中位置。

【答案】(1)构造的哈希函数为:哈希函数H(key)=(关键字各字符编码之和)MOD7。 (2)关键字在表中的位置如表所示:

表 关键字在表中的位置

7． 对一个有

t 个非零元素的矩阵，用的数组来表示，

其中第0行的三个元素分别为m ，n ，t ，从第一行开始到最后一行，每行表示一个非零元素；第一列为矩阵元素的行号，第二列为其列号，第三列为其值。对这样的表示法，如果需要经常进行该操作-确定任意一个元素A[i][j]在B 中的位置并修改其值，应如何设计算法可以使时间得到改善？

【答案】题中矩阵非零元素用三元组表存储，查找某非零元素时，按常规要从第一个元素开始查找，属于顺序查找，时间复杂度为0(n)。若使查找时间得到改善，可以建立索引，将各行行号及各行第一个非零元素在数组B 中的位置(下标) 放入一向量C 中。若查找非零元素，可先在数组C 中用折半查找到该非零元素的行号，并取出该行第一个非零元素在B 中的位置，再到B 中顺序(或折半) 查找该元素，这时时间复杂度为0(logn)。

第 4 页，共 34 页