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

一、算法设计题

1． 写出一个递归算法来实现字符串逆序存储。

【答案】算法如下:

//字符串逆序存储的递归算法

r

//需要使用静态变量

//

规定

是字符串输入结束标志

//字符串逆序存储

//字符串结尾标记

//结束算法InvertStore

2． 设要求按

是一个记录构成的数组，

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

的内容调整A 中记录的次序，比如当B[l]＝ll 时，则要求将A[l]的内容调整到A[ll]

中去。规定可使用的附加空间为O(1)。

【答案】算法如下:

//A是100个记录的数组，B 是整型数组，本算法利用数组B 对A 进行计数排序

//若B[i]＝i 则A[i]正好在自己的位置上，则不需要调整

//B[j]和B[k]交换

//r0是数组A 的元素类型，A[j]和A[k]

交换

//完成了一个小循环，第i 个已经安排好

//算法结束

3． 写出一趟快速排序算法。

【答案】算法如下:

一趟快速排序算法，枢轴记录到位，并返回其所在位置

4． 设线性表存于A[l..size]的前mun 各分量中，且递增有序。请设计一个算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。

【答案】算法如下:

//A是Size 个元素空间但目前仅有num(num＜size}个元素的线性表 //本算法将元素x 插入到线性表中，并保持线性表的有序性

//题目要求下标从1开始

//对分査找元素x 的插入位置

//元素后移

//将元素x 插人

算法结束

设计思想:算法中当查找失败(即线性表中无元素X) 时，变量low 在变量high 的右面(low＝high ＋l) 。移动元素从位置low 开始，直到num 为止。

时间复杂度:查找的复杂度为O (logn)，插入的时间复杂度为O (n)，若用顺序查找，则查找的时间复杂度亦为O(n)。

5． 设记录的关键字为。，树结点

的败者树，要求除

指向败者记录，

和1

为全胜以外，只

记录下标。写一算法产生对应上述用O(1)辅助空间。

【答案】算法如下:

选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树

是

指示新的胜者

到:_

小数

设置T 中" 败者" 的初值

依次从

出发调整败者

为完全二叉树T 的叶结点，本算法建立败者树

是与题中要求的关键字类型相同的机器最

的双亲结点

二、应用题

6． 假定有下列，nxn 矩阵(n为奇数

)

如果用一维数组B 按行主次序存储A 的非零元素，问: (1)A中非零元素的行下标与列下标的关系； (2)给出A 中非零元素在B 中的位置公式。

(1)主对角线上元素的坐标是i ＝j ，【答案】副对角线上元素的坐标i 和j 有i ＋j ＝n ＋l 的关系，所以A 中非零元素的行下标和列下标的关系是i ＝j

或

的下标(i，j) 与B 中的下标R 的关系；

，给出利用

的下标(i，j) 定位

(3)假定矩阵中每个元素占一个存储单元且B 的起始地址为