7. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）
A．?logn?+1 B．logn+1 C．?logn? D．logn-1 8．深度为h的满m叉树的第k层有（ A）个结点。(1= A．mk-1 B．mk-1 C．mh-1 D．mh-1 9．在一棵高度为k的满二叉树中，结点总数为（ C） A．2k-1 B．2k C．2k-1 D．?log2k?+1 10．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 11．树的后根遍历序列等同于该树对应的二叉树的( B ). A. 先序序列 B. 中序序列 C. 后序序列 12．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D ）。 A．acbed B．decab C．deabc D．cedba 13．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： C A、 E B、 F C、 G D、 H 14．对于前序遍历与中序遍历结果相同的二叉树为（F）; 对于前序遍历和后序遍历结果相同的二叉树为（B）。 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树 15．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ C ） A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树 16. 引入二叉线索树的目的是（ A ） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 17．n个结点的线索二叉树上含有的线索数为（ C ） A．2n B．n－l C．n＋l D．n 18．（ C）的遍历仍需要栈的支持. A．前序线索树 B．中序线索树 C．后序线索树 19．二叉树在线索后，仍不能有效求解的问题是（ D ）。 A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 20．由3 个结点可以构造出多少种不同的二叉树？（ D ） A．2 B．3 C．4 D．5 21．下述编码中哪一个不是前缀码（ B ）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 22．从下列有关树的叙述中,选出5条正确的叙述(共5分) （ CDFHI ） A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B．当K≥1时高度为K的二叉树至多有2k-1个结点。 C．用树的前序周游和中序周游可以导出树的后序周游。 6 D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。 F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G．在二叉树中插入结点,该二叉树便不再是二叉树。 H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J．用一维数组存储二叉树时,总是以前序周游存储结点。 判断题 1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√ 2. 二叉树只能用二叉链表表示。× 3．在二叉树的第i层上至少有2i-1个结点(i>=1) × 4．度为二的树就是二叉树。× 5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。√ 填空题： 1．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。 2．具有256个结点的完全二叉树的深度为__9____。 3．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。 4．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ N2 _+ 1___ 5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是__99____。 6．一个有2001个结点的完全二叉树的高度为__11____。 7．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__n1-1_个结点，右子树中有_n2+n3__个结点。 作业题 1、给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41， （1）试画出用Huffman算法建造的Huffman树； （2）求平均编码长度（）考虑概率 解：（1） 7 238 95 143 42 19 23 65 34 17 10 5 2 3 5 7 17 31 37 78 41 11 24 53 29 13 （2）（7×（2＋3）＋6×5＋5×7 ＋4×（17＋66＋13）＋3×（31＋37＋41＋29＋19＋23））/ 238 2、．设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的后序线索树。 解：（1） A B D F G E H C (2) 后序遍历为：F D B G H E C A 8 A B D F G E H C 3．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr; if (bt==NULL) return((1)_ 0__); hl=depth(bt->lchild); hr=depth(bt->rchild); if((2) hl>hr ___) (3)_ hr=hl_____； return(hr+1); } 4．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。 /* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null) { thread_inorder((1) tree->lchild ____); if(tree->lchild==(2)__ NULL______) { tree->ltag=1; tree->lchild=pre; } if((3) tree->rchild____ == null){ (4) tree->rtag=1__; (5) tree->rchild=tree _______;} pre=p; thread-inorder((6)_ tree->rchild __); } } 5、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ （请给出具体的推理过程） 解： 16 6、一棵共有n个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。 n(k?1)?1n0? k7. 假设一个二叉树的两种遍历如下： 9 前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA 画出这棵二叉树以及它的中序线索树； 解： A B F G H C D E I J L K F G B A C H D E I J L K 第七章练习 选择题 1．设无向图的顶点个数为n，则该图最多有（ B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 3．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 4．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 5．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（B ）。 A． ?A[i,j]i?1n B． ?A?i,j?j?1n C． ?A[j,i]i?1n D． ?A[i,j]?A?j,i?i?1nn+ j?1 7．无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}， 对该图进行深度优先遍历，得到的顶点序列正确的是（ D ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 8．下面哪一方法可以判断出一个有向图是否有环（回路）：（ B ） 10 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库期末数据结构复习习题(含答案)(2)在线全文阅读。
相关推荐：