2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(8)

19．已知一具有n个结点的二叉树的中序遍历序列与后序遍历序列分别存放于数组和

中（设该二叉树各结点的数据值均不相同）。请写一建立该二叉树的二叉链表结构的非

递归算法。该二叉链表的 链结点结构为（lchild，data, rchild）,其中data为数据域，lchild与rhild分别为指向该结点左、右孩子的指针域 （当孩子结点不存在时，相应指针域为空，用nil表示）。

【答案】算法如下：

//由二叉树的中序序列IN[]和后序序列POSTt[]建立二叉树

分别是中序序列和后序序列第一和最后元素的下标，初始调用时

，

为栈，容量足够大

//初始化

//取出栈顶数据

//在中序序列中查等于

//根结点的值

无左子树

将建立左子树的数据人栈

无右子树

//右子树数据入

栈

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

【答案】算法如下：

//对以邻接表存储的DAG图g重新编号,使若有<i,＞j，则编号

i< j

//求各顶点的入度

的结点

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2017年南昌大学信息工程学院838数据结构[专业硕士]考研题库(8)在线全文阅读。