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

一、算法设计题

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

它们已用

域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由

域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【答案】算法如下：

2． 给定一个整数数组求出b 中最长平台的长度。

【答案】算法如下：

第 2 页，共 51 页

中连续的相等元素构成的子序列称为平台。试设计算法，

3． 请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用

【答案】算法如下：

法存储。

4． 写出按后序序列遍历中序线索树的算法。

【答案】算法如下：

//求结点

//求结点

//若t 是father 的右孩子，返回1, 否则返回0

第 3 页，共 51 页

t 最左子孙的左线索

//沿左分支向下

t 最右子孙的右线索

//沿右分支向下

//后序遍历中序线索二叉树bt

//沿左分支向下

//左孩子为线索，右孩子为链，相当从左返回

//P为叶子，相当从右返回

//访问结点

//修改P 指向双亲

//P是左子女，用最右子孙的右线索找双亲

//转向当前结点右分支

} }//结束PostOrderInThr

5． 假定用两个一维数组L 【N 】和R 【N 】作为有N 个结点1，2, ...，N 的二叉树的存储结构L[i]和R[i] 分別指示结点i 的左儿子和右儿子L[i]=0 （R[i]=0）表示i 的左（右）儿子为空。试写一个算法，由L 和R 建立一个维数组T[n]，使T[i]存放结点i 的父亲：然后再写一个判别结点u 是否为结点V 的后代的算法。

【答案】算法如下：

int Generation （int U, V , N , L[], R[], T[]}

//L[ ]和R[ ]是含N 个元素且指示二叉树结点i 左儿子和右儿子的一维数组 //本算法据此建立结点i 的双亲数组T , 并判断结点U 是否是结点V 的后代 {for（i=l; i<=N; i++） T[i]=0; //T数组初始化

for （i=l; i<=N; i++） if （L[i]!=0） T[L[i]]=i; //若结点i 的左子女是L , 则结点的双亲是结点i for （i=l; i<=N; i++） if （R[i]!=0> T[R[i]]=i; //若结点i 的右子女是R , 则R 的双亲是i int parent=U; //判断U 是否是V 的后代 while （

parent!=V

parent!=0） parent=T[parent];

if （parent==V）{printf（“结点U 是结点V 的后代”）; return （l ）:} else{printf（“结点U 不是结点V 的后代”）; return （0）; } }结束 Generation

第 4 页，共 51 页