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

一、算法设计题

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

【答案】算法如下:

待排序记录的个数

关键字由d 个分量组成

静态链域

记录的其他数据域

存放n 个记录

.

用队列表示桶，共m 个

进行基数排序，返回收集用的链头指针

将

进行d 趟排序

初始化桶

按关键字的第j 个分量进行分配

k 为桶的序号

将将

链到桶头

链到桶尾

链成一个静态链表

将初始链表的终端结点指针置空，P 指向链表的第一个结点

队列的头、尾指针

对

修改桶的尾指针

扫描下一个记录

找第一个非空的桶

为收集链表的头指针，t 为尾指针

连接非空桶

本趟收集完毕，将链表的终端结点指针置空

2． —个有向图G=(V，E) 的平方图

，使得表示。

【答案】算法如下:

3． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。

【答案】算法如下:

//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐

//滤掉s1左端空格

("字符串s1为空串或空格串\n")；exit(0)；

}

//字符串S1向字符串S2中

复制

(”字符串s1没有

//P指针也后退

//往后査找一个非空格字符作为串S2的尾字

符

满足下述性质

:

当且仅当存在某个顶点

且

22

。写一个算法从给定的G 求出G , G 和G 可分别用两个邻接表

个有效字符\n"，n) ；exit(0)；

}

//若最后一个字符为空格，

则需向后找到第一个非空格字符

("s1串没有

//字符串s2最后一个非空字符

//置S2字符串结束标记

个两端对齐的字符串exit(0)；

}

//将s1串其余部分送字符串

S3

//置串S3结束标记

4． 设稀疏矩阵中有t 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M 的转置矩阵N ，要求转置算法的时间复杂度为0(n＋t) 。

【答案】算法如下:

//采用三元组表方式存储，按列序实现矩阵的转置

//行数、列数和非零元素个数

//设置N 中第一个非零元素从下标1开始存储

//按列，共

//在//转置

//三元组表上实现矩阵的快速转置的算法

//矩阵M 每一列非零元初始化为零

//求矩阵M 每一列的非

零元个数

//第1列第一个非零元在转置后的三元组中下标是

1

//求

第j 列第一个非零元在

中的序号

列

个元素中查找

//求转置矩阵N 的三元组表