树图查找排序复习.doc

树 一、判断题： 1.二叉树是一棵无序树。（×） 2.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（√） 3.度为二的有序树等价于二叉树。（√） 4.树的带权路径长度最小的二叉树中必定没有度为1的结点。（√） 5.哈夫曼树一定是满二叉树。5层上的结点个数最多为____C____A.8 B.15 C.16 D.32 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。A.98 B.99 C.50 D.48 由权值分别为3, 8, 6, 2, 5的叶子结点生成一颗赫夫曼树，它的带权路径长度为__D___。A. 24 B. 48 C. 72 D. 53 把一棵树转换为二叉树后，这棵二叉树的形态是 A 。Ａ.唯一的 Ｂ.有多种Ｃ.有多种，但根结点都没有左孩子 Ｄ.有多种，但根结点都没有右孩子 具有n(n0)个结点的完全二叉树的深度为 C 。Ａ (log2(n)( Ｂ ( log2(n)( Ｃ ( log2(n) (+1 Ｄ (log2(n)+1( ù 四、应用题 1..将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。 先序：ABEFCDGJ 中序：EFBCGJDA 后序：FEJGDCBA 2.写出下图所示二叉树的先序、中序、后序序列 先序序列：ABDEFC 中序序列：DBFEAC 后序序列：DFEBCA 3.已知一棵二叉树的先根和中根序列，画出其对应的二叉树并求其后根序列。 先根序列：A, B, C, D, E, F, G, H, I, J 中根序列：C, B, A, E, F, D, I, H, J,G 后根序列：C, B, F, E, I, J, H, G, D, A 6已知一棵二叉树的先序、中序和后序遍历序列分别为: （参看课件） 先序: BE×KCJADG×HI 中序: LK×CAJ××FGIH 后序: KL×JCEF××GDB 其中有些字母已丢失,请添写完整并画出此二叉树 7.在一份电文中共使用8种字符，即a, b, c, d, e, f, g, h，它们出现的频率依次为0.07, 0.19, 0.02,0.06, 0.32, 0.03, 0.21, 0.10，试画出对应的赫夫曼树，求出每个字符的赫夫曼编码，以及带权路径长度。 哈夫曼编码:a:0010 b:10 c:00000 d:0001 e:01 f:00001 g:11 树和wpl：略。 8.写出下图所示森林的先序、中序序列。将该森林转换为相应的二叉树。 先序序列：1、2、3、4、5、6、8、7、9、10、11、12、13、15、14 中序序列：3、4、8、6、7、5、2、1、10、9、11、15、13、14、12 9. 设二叉树后根遍历为BAC，画出所有可能的二叉树。 11、已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。存储结构定义： typedef struct BiTNode { // 结点结构 Selemtype data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void inorder(BITree t) {if(t!=NULL) {inorder(t-lchild); printf(“%d”，t-data); inorder(t-rchild);}} 图 一、判断题： 1.图的深度优先有哪些信誉好的足球投注网站是一种典型的回溯有哪些信誉好的足球投注网站的例子，可以通过递归算法求解。（√） 2.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。（√） 3.如果有向图中各个顶点的度都大于2，则该图中必有回路。（×） 4.具有n个顶点的连通图的生成树具有n-1条边（√） 5．在n个结点的无向图中,若边数n-1,则该图必是连通图.(×) 6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（×） 7.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的