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

一、算法设计题

1． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。

串被确认的最大长度

【答案】算法如下:

//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回

//在类C 中，一维数组下标从零开始

//两串相等

//算法结束

2． 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。

(1)处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。

(2)处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。

【答案】(1)算法如下:

按关键字第一个字母在字母表中的顺序输出各关键字

哈希地址

1~26

设哈希表初始值为

null

取关键字第一字母在字母表中的序号

(2)算法如下:

求链地址解决冲突的哈希表査找不成功时平均査找长度

记査找不成功的总的次数

按我们约定，査找不成功指到空指针为止

3． 以三元组表存储的稀疏矩阵A ，B 非零元个数分别为m 和n 。试用类PASCAL 语言编写时间复杂度为0(m＋n) 的算法将矩阵B 加到矩阵A 上去。A 的空间足够大，不另加辅助空间。要求描述所用结构。

【答案】算法如下:

＝大于非零元素个数的某个常量

//本算法实现以三元组表存储的各有m 和n 个非零元素两个稀疏矩阵相加，结果放到A 中

//L，p 为A ，B 三元组表指针，k 为结果三元组表榫针(下标

)

//行号不等时，行号大者的三元组为结果三元组表中一项

//A中当前项为结

果项

//B中当前项为结果

当前项

//行号相等时，比较列号

//结束行号相等时的处理

-

//结束行号比较处理

//结果三元组表的指针前移(减

1)

//结束WHILE 循环。

//处理B 的剩余部

分

//处理A 的剩余部

分

//稀疏矩阵相应元素相加时，有和为零的元素，因而元素总数＜m ＋

n

//三元组前移，使第一个三元组的下标

为

1

//修改结果三元组表中非零元素个数

//结束addmatrix

4． 写一算法找出n 个数的最大值和最小值，要求最坏条件下的元素比较次数为

。

【答案】算法如下:

用最多3n/2－2次比较在n 个元素r 中选出最大值和最小值

n 为偶数时

r 最小值

("最大值) ；

5． 在一个循环链队中只有尾指针(记为rear ，结点结构为数据域data ，指针域next) ，请给出这种队列的入队和出队操作的实现过程。

【答案】算法如下:

//rear是带头循环链队列的尾指针，本算法将元素X 插入到队尾

//申请结点空间

//将s 结点链入队尾

//rear指向新队尾