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

一、算法设计题

1． 输入一个字符串，内有数字和非数字字符，如:akl23x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a 中，例如123放入a[0]，456放入a[l]，...... 。编程统计其共有多少个整数，并输出这些数。

【答案】算法如下:

（ ）

//从键盘输入字符串，连续的数字字符算作一个整数，统计其中整数的个数

//整数存储到数组a ，i 记整数个数

//从左到右读入字符串

//'#'是字符串结束标记

//是数字字符

//数初始化

//拼数

//若拼数中输入了’#’，则不再输入

//输入非数字且非#时，继续输入字符

("共有

个整数，它们是:

)

//每10个数输出在一行上

//算法结束

2． 编写算法打印出由指针Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意:行、列及总表头结点的形式为:

它们已用val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由right(down)域把它们链接成循环链表，该行(列) 的表头结点即为该行(列) 循环链表的表头。

【答案】算法如下:

//输出由Hm 指向的十字链表中每一行的非零元素个数

//数组A 记各行非零元个数，i 记行号

//循环完各行列表头

//P是稀疏矩阵行内工作指针，num 记该行非零个

数

//完成行内非零元的查找

//指针后移

//存该行非零元个数

//移到下一行列表头

//输出各行非零元个数

第

}算法结束

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

【答案】算法如下:

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

行非零元个数为

}

//稀疏矩阵非零元个数

本算法的递归描述如下:

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

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

【答案】算法如下:

待排序记录的个数

关键字由d 个分量组成

静态链域

记录的其他数据域

存放n 个记录

.

用队列表示桶，共m 个

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

将

进行d 趟排序

初始化桶

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

k 为桶的序号

队列的头、尾指针

对

链成一个静态链表

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