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

一、算法设计题

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

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

【答案】算法如下:

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

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

//循环完各行列表头

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

数

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

//指针后移

//存该行非零元个数

//移到下一行列表头

//输出各行非零元个数

第

}算法结束

行非零元个数为

}

//稀疏矩阵非零元个数

2． 已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA(P，q) , 该算法寻找结点P 的父亲结点q 。设线索二叉树的结点结构、表头结点结构和空树结构分别为(LTAG，LLINK ，INFO , RL1NK ，RTAG) ，且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。

【答案】算法如下:

在中序线索树t 上，求结点p 的双亲结点q

暂存

找P 的中序最右下的结点

顺右线索找到q 的后继(P的袓先结点

)

若后继是头结点，则转到根结点

根结点无双亲

找最右结点的过程中回找到

P

结束FFA

3． 结点类型和存储结构如下:

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

【答案】算法如下:

对存储在数组R 中的记录进行排序

初始化

设R[0]作监视哨，Max 是该类型最大元

素

初始假定第一个元素有序

前驱

第一个元素

査找第i 个元素的序号

将笫i 个元素链入静态链表

准备到左子树中找

P

4． 设A 和B 均为下三角矩阵，每一个都有n 行n 列。因此在下三角区域中各有n(n＋l)/2个无素。另设有一个二维数组C ，它有n 行n ＋1列。试设计一个方案，将两个矩阵A 和B 中的下三角区域元素存放于同一个C 中。要求将A 的下三角区域中的元素存放于C 的下三角区域中，B 的下三角区域中的元素转置后存放于C 的上三角区域中。并给出计算A 的矩阵元素矩阵元素

在C 中的存放位置下标的公式。

//本算法将n 阶方阵的下三角矩阵A 和B 置于C 中，矩阵B 要逆置

//算法结束

5． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。

【答案】算法如下::

打印从根结点bt 到结点p 之间路径上的所有结点

.

是元素为二叉树结点指针的栈，容量足够大

是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同

步

根结点就是所找结点

左子女入栈，并置标记

找到结点P , 栈中元素均为结点P 的祖先

从根结点到P 结点的路径为

沿左分支向下

本题不要求输出遍历序列，

这里只出栈

沿右分支向下

结束算法

为叶结点

从根结点到P 结点的路径为

输出从根到叶子q 的路径上的所有袓先

【答案】算法如下:

和B 的