平时作业：（1-6十一假期后提交，7-11最后一堂课之前提交） 1. 设计一个算法，从一棵二叉树中查找出所有结点的最大值并返回。 2. 求二叉树中所有的度为1的结点数。 3. 假设称正读和反读都相同的字符序列为“回文”，例如’abba’和’abcba’是回文，’abcde’和’ababab’则不是回文。试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。 4. 阅读下列算法，若有错，改正之。 BiTree InSucc(BiTree q) { // 已知q是指向中序线索二叉树上某个结点的指针， // 本函数返回指向*q的后继的指针。 r = q->rchild; if (!r -> rtag ) while (!r -> rtag ) r = r->rchild return r; } 5. 写出二叉树的先序遍历和后续遍历的非递归算法。 6. 编写算法判别给定二叉树是否为完全二叉树 7. 试推导含12个结点的平衡二叉树的最大深度，并画出一颗这样的树。 8. 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？ 9. 在平衡二叉树的每个结点中增设一个lsize域，其值为它的左子树的结点数加1.试写一O（logn）的算法，确定树中第k小的结点的位置。 10. 已知记录序列a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组c[1..n]，对每个记录a[i]，统计序列中关键字比他小的记录个数存于c[i]中，则c[i]=0的记录必为关键字最小的记录，然后依c[i]值的小对a中记录进行重新排列，试编写算法实现之。 11. 已知(k1,k2,…,kp)是堆，则可以写一个时间复杂度为O(logn)的算法将(k1,k2,…,kp,kp+1调整为堆。试编写“从p=1起，逐个插入建堆”的算法，并讨论时间复杂度。 上机作业： 12. 编写算法，由依次输入的顶点数目、弧的数目、各顶点信息和各弧的信息建立有向图的邻接表。 13. 在上题题邻接表的存储结构上实现图的基本操作：InsertVex(G，v) ，InsertArc(G，v，w)，DeleteVex(G，v) ，DeleteArc(G，v，w)。 14. 将7题的邻接表转换为邻接矩阵存储，然后实现求任意两个顶点的最短路径的弗洛伊德算法。 作业提交：dlut.zhangsw@gmail.com 本文来源：https://www.wddqw.com/doc/4b5778305a8102d276a22f31.html