（二）作业 - 图文

说明：

上机作业3道，10分 平时作业13道，10分

上机时间：第4、6、7周 周六6:00-9:00 综合楼机房412 交上机作业时间：第5、7、8周周五截止。

上机作业格式：主题输入 学号+姓名+第X次上机作业 上机作业邮箱：wangliang19900227@163.com

平时作业：必须提交手写板 10月7日 提交1-10题 10月31日提交11-13题

所有作业请按时交纳，不收补交作业。

1. 设计一个非递归算法，从一棵二叉树中查找出所有结点的最大值并返回。 2. 设树采用定长结点的多重链表表示，设计算法实现树的按层次遍历。 3. 阅读下列算法，若有错，改正之。

BiTree InSucc(BiTree q)

{ // 已知q是指向中序线索二叉树上某个结点的指针， // 本函数返回指向*q的后继的指针。 r = q->rchild;

if (r -> rtag==0 )

while (!r -> rtag ) r = r->rchild return r; }

4. 写出二叉树的先序遍历和后序遍历的非递归算法。 5. 设计一个非递归算法，计算树的叶子结点数。（要求说明树的存储方式） 6. 已知带权无向图如图所示：

(1). 根据普里姆（Prim）算法，设计算法,求它的从顶点a出发的最小生成树；

(2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树,给出添加边次序。 a

7．已知带权有向图如图所示：

(1). 画出该图的邻接矩阵存储结构；

(2). 求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。

30 b c 5 2 1 8 6 ad 2 e h 9 f 3 7 24 g 21 6 b 5 5 1 c 4 d 7 e 3 2

8．列出图中全部可能的拓扑有序序列，并指出应用7.5.1节中算法Topological Sort算法求得的是哪一个序列？

1234 9．对下图所示AOE网络，计算各活动弧的e(ai)和l（ai）函数值，各事件（顶点）的ve(vi)和vl(vi)函数值，列出各条关键路径。

56

10．试利用Floyd算法求图中所示有向图中各顶点之间的最短路径。（求解过程）

10A3 78B5

D6 C11．在平衡二叉树的每个结点中增设一个lsize域，其值为它的左子树的结点数加1.试写一O（logn）的算法，确定树中第k小的结点的位置。

12．已知(k1,k2,?,kp)是堆，则可以写一个时间复杂度为O(logn)的算法将

(k1,k2,?,kp,kp+1调整为堆。试编写“从p=1起，逐个插入建堆”的算法，并讨论时间复杂度。

13．已知待排序序列为{17，18，60，40，7，32，73，65，85}，请写出按下列排序方法进行升序排序时的第一趟排序结果： ①二路归并排序；

②以第一个元素为枢轴的快速排序； ③基数排序第一趟分配和收集后的序列； ⑤取d1=4时的希尔排序。

上机作业：

1．设树采用孩子兄弟表示法存放。用类C语言设计算法计算树的高度。 2．设计算法实现图的拓扑排序

3．试写一个判别给定二叉树是否为二叉排序树的算法，设二叉树以二叉链表为存储结构，且结点关键字均不相同。

本文来源：https://www.bwwdw.com/article/chff.html