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

一、算法设计题

1． 设计算法将一个带头结点的单链表A 分解为两个具有相同结构的链表B 、C , 其中B 表的结点为A 表中值小于零的结点，而C 表的结点为A 表中值大于零的结点(链表A 的元素类型为整型，要求B 、C 表利用A 表的结点) 。

【答案】算法如下:

//本算法将带头结点的单链表A 分解成数据域值小于零和大于零的两个单链表B 和

C

//为C 申请结点空间

//C初始化为空表

//P为工作指针

//B表初始化

//暂存P 的后继

//小于0的放入B 表

//将小于0的结点链人B 表

//P指向新的待处理结点

//算法结束

2． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i

【答案】算法如下:

对以邻接表存储的DAG 图g 重新编号, 使若有

第 2 页，共 38 页

，则编号

求各顶点的入度

记录结点的逆序序号

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

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

【答案】算法如下:

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

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

//循环完各行列表头

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

数

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

//指针后移

//存该行非零元个数

//移到下一行列表头

//输出各行非零元个数

第

}算法结束

行非零元个数为

}

//稀疏矩阵非零元个数

第 3 页，共 38 页

4． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下:

在二叉树t 中査找结点值等于x 的结

点

结束

统计以t 为根结点的子树的叶结点数

n0

. 叶结点

输出并计数

结束

:

5． 假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT 中，写出计算该算术表达式值的算法。

【答案】算法如下:

以后序遍历算法求以二叉树表示的算术表达式的

值

.

求左子树表示的子表达式的值

求右子树表示的子表达式的值

二、应用题

6． 解答问题。设有数据逻辑结构为:

第 4 页，共 38 页