习题八 根及其应用 - 烟台大学计算机与控制工程学院

1、习题八: 根树及其应用1从简单有向图的邻接矩阵怎样去决定它是否为根树。如果是根树，怎样定出它的树根和树叶。2求出对应于图7-8.9所给出的树的二叉树。1413983124567101112图7-8.93证明在完全二叉树中，边的总数等于，式中是树叶数。4在一棵叉树中，其外部通路长度与内部通路长度之间有什么关系。5给定权1，4，9，16，25，36，49，64，81，100a）构造一棵最优二叉树。b）构造一棵最优三叉树。c）说明如何构造一棵最优叉树。6构造一个与英文字母对应的前缀码，并画出该前缀码对应的二叉树，再用此六个字母构成一个英文短语，写出此短语的编码信息。7设是二进制序列的集合。我们将划分

2、为两个子集和，这里是中第一个数字是0的序列的集合，是中第一个数字是1的序列的集合，然后我们根据序列中的第二个数字将划分成两个子集，对也用同样方法加以划分。运用不断的将序列的集合划分成子集的方法来证明：如果是前缀码，则存在一棵二叉树，其中从每个分枝点射出的两条边分别标号0和1，使得赋于树叶的0和1的序列是中的序列。8给出公式（的根树表示。9（1）求带权为1，1，2，3，3，4，5，6，7的最优三元树。 （2）求带权为1，1，2，3，3，4，5，6，7，8的最优三元树。10在通信中要传输八进制数字0，1，2，7。这些数字出现的频率为0：30%；1：20%；2：15%；3：10%；4：10%；5：6

3、%；6：5%；7：4%。 编一个最佳前缀码，使通信中出现的二进制数字尽可能地少。具体要求如下：（1） 画出相应的二元树。（2） 写出每个数字对应的前缀码。（3） 传输按上述比例出现的数字10000个时，至少要用多少个二进制数字？11如何由有向图G的邻接矩阵判定G是否为根树，若为根树，如何定出它的树根和树叶。12非平凡的无向连通图G是树当且仅当G的每条边都是割边。13根数中最长路径的端点都是树叶吗？为什么？14证明：若T是有n个结点的完全二元树，则T有片树叶。15设T为高为h的r元正则树，证明T的树叶数t满足： 。16（1）求带权为2，3，5，7，8的最优二元树T。 （2）求T对应的二元前缀码。

4、17将图7-9所示的有序树表示成二叉树并求出相应的前缀码。 52678910413图7-918根据图7-10中所示的两棵二元树，产生两个前缀码。图7-10（1）（2）19. 在下面给出的3个符号串集合中，哪些是前缀码？哪些不是前缀码？若是前缀码，构造二叉树，其树叶代表二进制编码。若不是前缀码，则说明理由。（1）B1=0，10，110，1111；（2）B2=1，01，001，000；（3）B3=1，11，101，001，0011。20连通图G的树图是一个图，它的结点为G的生成树，与相邻的充要条件是它们恰好有v-2条公共边（其中v为G的结点数）。证明：连通图的树图是连通图。21在图7-11中，（1

5、），（2）所示的连通图G1，G2中各有几棵非同构的生成树？（1）（2）图7-1122画出具有7个结点的所有非同构的树。23结点已标定的，和各有多少棵生成树？24（1）证明完全二元树的树叶数比内部结点数大1。 （2）找出完全n元树的树叶数的表达式，该表达式用树的内部结点数的项表示。25证明一棵完全二元树必有奇数个结点。26在图7-12（1）、（2）所示的两图中各求一棵最小生成树，将生成树用粗边给出并计算它们的权。7-12 4ae54143d63c2babc9d125e8516798f56（1）（2）7-12 4ae54143d63c2babc9d125e8516798f567-12 4ae54143d63c2babc9d125e8516798f5627在图7-13所示的带权图G中共有多少棵生成树，它们的权各为多少？其中哪些是图中的最小生成树？adbcv3v6v8v9v7v5v4v1v0v2图7-13图7-144122328分别用先根、中根、和后根的次序通过如图7-14所示的二叉树。29设G是一无向加权图且各边的权不相等，V，E分