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

一、算法设计题

1． 以三元组表存储的稀疏矩阵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

2． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下:

//求具有N 个元素的整型数组b 中最长平台的长度。

//局部最长平台

//新平台起点

(“最长平台长度

3． 对于任意的无符号的十进制整数m ，写出将其转换为十六进制整数的算法(转换仅要求能够输出正确的十六进制的整数即可) 。

【答案】算法如下:

//本算法将无符号十进制整数m 转换为十六进制整数

b 中连续的相等元素构成的子序列称为平台。试设计算法，

在b 数组中起始下标为”，1，

k)

本算法的递归描述如下:

//本算法将无符号十进制整数m 转换为十六进制整数

4． 已知两个线性表A , B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A 与B 的交集C ，要求C 另开辟存储空间。，并同样以元素值的递增有序的单链表形式存储。

【答案】算法如下:

//线性表A 和B 以带头结点的单链表作为存储结构。本算法求A 和B 的交集C , C 另辟空间

//pa、pb 是两链表的工作指针

//监视哨

//pa指针后移

//pb指针后移

//处理交集元素

//删除重复元素

//交集元素并入结果表

//置结果链表尾

5． 叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。(179，208，93，306，55，859，984，9，271，33)

【答案】算法如下: