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

一、算法设计题

1． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。

【答案】算法如下:

L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符

//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表

//建立三个链表的头结点

//置三个循环链表为空表

//分解原链表

//L指向待处理结点的后继

//处理字母字符

//处理数字字符

//处理其他符号

//结束while(L!＝

null) //算法结束

2． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2，…，N

的二叉树的存储结构。

和

分别指示结点i 的左儿子和右儿子，

，使

) 表示i 的左(右) 儿子为空。试写一个

存放结点i 的父亲；然后再写一个判别结点u 是否

算法，由L 和R 建立一个一维数组为结点V 的后代的算法。

【答案】算法如下:

和

是含有N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组

本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代

T 数组初始化

若结点i 的左子女是则结点L 的

双亲是结点

i

若结点i 的右子女是R , 则R 的

双亲是

i

判断U 是否是V 的后代

3． 设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

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

递减序输出二叉排序树t 中所有左子树为空右子树非空的结点数据域的值

(2)非递归算法如下:

递减序输出二叉排序树t 中所有左子树为空、右子树非空的结点的数据域的值

S 是二叉排序树结点指针的栈，容量足够大

沿右分支向下

去左分支

算法结束

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

【答案】算法如下:

待排序记录的个数

关键字由d 个分量组成

静态链域

记录的其他数据域

存放n 个记录

.

用队列表示桶，共m 个

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

将

进行d 趟排序

初始化桶

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

k 为桶的序号

将将

链到桶头

链到桶尾

链成一个静态链表

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

队列的头、尾指针

对

修改桶的尾指针

扫描下一个记录

找第一个非空的桶

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

连接非空桶

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

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

【答案】算法如下:

（ ）

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

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