数据结构第六章知识题课

1、* *1 、下图所示的 4 棵二叉树中，不是完全二叉树的是（）ABCD2 、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。A 、正确B、错误C、不一定3 、已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是（）。A 、acbedB、decabC、deabcD 、cedba4 、如果 T2 是由有序树 T 转换而来的二叉树，那么T 中结点的后序就是T2 中结点的（）。A 、前序B、中序C、后序D 、层次序5 、深度为 5 的二叉树至多有（）个结点。A、16B、32C、31D、106 、在一个非空二叉树的中序遍历序列中，根结点的右边

2、（）。* *A 、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D 、只有左子树上的所有结点7 、树最适合用来表示（）。A 、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D 、元素之间无联系的数据。8 、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。A 、不发生改变B、发生改变C、不能确定D 、以上都不对9 、实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（ ）存储结构。A 、二叉链表B、广义表存储结构C、三叉链表D 、顺序存储结构10 、对一个满二叉树， m 个树叶， n 个结点，深度为h ，则（）。

3、A 、n=m+hB 、h+m=2nC、m=h-1D 、n=2 h -111 、设 n ，m为二叉树上的两个结点，在中序遍历时，n 在 m前的条件是（）。A 、n 在 m 右方B、n 是 m 祖先C、n 在 m 左方D 、 n 是 m 子孙12 已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为 ABC*+DE/-，* *其前缀形式为 ()A -A+B*C/DEB. -A+B*CD/EC -+*ABC/DED. -+A*BC/DE/13. 设有一表示算术表达式的二叉树（见右图） ，+*C *-它所表示的算术表达式是（）A BDE F GA. A*B+C/(D*E)+(F-G)B. (A*

4、B+C)/(D*E)+(F-G)C. (A*B+C)/(D*E+ （F-G ）)D. A*B+C/D*E+F-G14.在下述结论中，正确的是（）只有一个结点的二叉树的度为0;二叉树的度为2 ；二叉树的左右子树可任意交换 ;深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。A BCD 15. 设森林 F 对应的二叉树为 B，它有 m 个结点， B 的根为 p,p 的右子树结点个数为 n, 森林 F 中第一棵树的结点个数是（）A m-nB m-n-1Cn+1D 条件不足，无法确定16 若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（）A9B

5、11C15D不确定* *17 一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（）A 250B 500C 254D 505E以上答案都不对18. 一个具有 1025 个结点的二叉树的高 h 为（）A 11B 10C11 至 1025之间D 10 至 1024之间19 深度为 h 的满 m 叉树的第 k 层有（）个结点。 (1=<k=<h)A m k-1Bm k-1Cm h-1D m h -120.利用二叉链表存储树，则根结点的右指针是（）。A 指向最左孩子B指向最右孩子C空D 非空21 对二叉树的结点从1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点

6、的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 () 次序的遍历实现编号。A 先序B. 中序C. 后序D. 从根开始按层次遍历22 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用 () 遍历方法最合适。A 前序B中序C后序D 按层次23 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树* *一定满足（）A 所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D 是任意一棵二叉树24 . 若 X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则 x 的前驱为 ()A.X 的双亲B.X 的右子树中最左的结点C.X 的左子树中最右结点D

7、.X 的左子树中最右叶结点25.线索二叉树是一种（）结构。A 逻辑B 逻辑和存储C 物理D线性26 n 个结点的线索二叉树上含有的线索数为（）A 2nB n lCn lD n27 下面几个符号串编码集合中，不是前缀编码的是（）。A 0,10,110,1111B 11,10,001,101,0001C 00,010,0110,1000D b,c,aa,ac,aba,abb,abc28. 当一棵有 n 个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组Al.n 中时，数组中第 i 个结点的左孩子为（）A A2i(2i=<n)B. A2i+1(2i+1=< n)CAi/2D

8、 无* *法确定29 、高度为 h 的完全二叉树至少有多少个结点?至多有多少个结点 ?解：高度为 h 的完全二叉树至少有2 h-1 个结点，至多有2 h-1 个结点 (也就是满二叉树 )。30 、在什么样的情况下，等长编码是最优的前缀码?答：在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。31 .假设在树中，结点x 是结点 y 的双亲时 ,用(x,y) 来表示树边。已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用图表

9、示出此树，并回答下列问题：(1) 哪个是根结点 ? (2) 哪些是叶结点 ? (3) 哪个是 g 的双亲 ? (4) 哪些是 g 的祖先 ?(5) 哪些是 g 的孩子 ? (6) 哪些是 e 的子孙 ? (7) 哪些是 e 的兄弟 ?哪些是 f 的兄弟 ?(8) 结点 b 和 n 的层次各是多少 ? (9) 树的深度是多少 ? (10) 以结点 c 为根的子树的深度是多少 ? (11) 树的度数是多少 ?答：这是测试我们对树的基本概念的掌握情况。a 是根结点； mndfjkl是叶结点； c 是 g 的双亲； c,a 是 g 的祖先；j,k 是 g 的孩子； imn 是 e 的子孙； d 是 e

10、 的兄弟， g,h 是 f 的兄弟；b 的层次是 2 ，n 的层次是 5；树的深度是5；以 c 为根的子树深度是3 ；* *树的度数是 3 。32 、试找出分别满足下面条件的所有二叉树：(1) 前序序列和中序序列相同； (2) 中序序列和后序序列相同；(3) 前序序列和后序序列相同； (4) 前序、中序、后序序列均相同。答：(1) 前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树 )。(2) 中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树 )。(3) 前序序列和后序序列相同的二叉树是：只有根结点的二叉树。(4) 前序、中序、后序序列均相同的二叉树：只有根结点的二叉

11、树。33 、对二叉树中的结点进行按层次顺序( 每一层自左至右 ) 的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为 ABCDEFGHIJ, 中序序列为 DBGEHJACIF ，请画出此二叉树。解： A/ B C/ D EF/ /G H IJ34 、对下图所示的森林：* *(1) 求各树的前序序列和后序序列；(2) 求森林的前序序列和后序序列；(3) 将此森林转换为相应的二叉树；(4) 给出 (a) 所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构， 并指出哪些存储结构易于求指定结点的祖先， 哪些易于求指定

12、结点的后代 ?解：(1)(a) 的前序序列： ABCDEF后序序列： BDEFCA(b) 的前序序列： GHIJK后序序列： IJKHG(c) 的前序序列： LMPQRNO后序序列： QRPMNOL(2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO此森林的后序序列：BDEFCAIJKHGQRPMNOL(3) 略(4) 略* *35 完全二叉树中，结点个数为n ，则编号最大的分支结点的编号为。答： n/236 二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1),则该二叉树对应的树林包括(2)棵树。答： (1)E

13、ACBDGF（2）237 具有 n 个结点的满二叉树，其叶结点的个数是_。答： (n+1)/2设内部节点数为a，叶节点数为 b ，明显有 a+b=n (1)，非空满二叉树中所有节点的出度正好等于入度，每个内部节点出度为2 ，叶节点出度为 0 ，所有节点的出度和为 2a ；根节点入度为 0 ，其他节点的入度为 1 ，所有节点的入度和为a+b-1;因此有 2a=a+b-1 (2)。由(1)(2) 得 b=(n+1)/2，a=(n-1)/2。另外可得b=a+1，也就是说， 非空满二叉树的叶节点数正好比内部节点数多1 。38 设一棵后序线索树的高是50 ，结点 x 是树中的一个结点， 其双亲是结点 y

14、,y的右子树高度是31 ，x 是 y 的左孩子。则确定x 的后继最多需经过 _中间结点（不含后继及x 本身）答： 31 （x 的后继是经 x 的双亲 y 的右子树中最左下的叶结点）* *39 有一份电文中共使用6 个 字符 :a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，试构造一棵哈夫曼树，则其加权路径长度WPL为(1) ，字符c 的编码是 (2) 。答： (1)80 (2)001（不唯一）40 下面是求二叉树高度的类C 写的递归算法，试补充完整。 说明 二叉树的两指针域为lchild与 rchild,算法中 p 为二叉树的根， lh 和 rh分别为以 p 为根的二叉树的

15、左子树和右子树的高，hi 为以 p 为根的二叉树的高，hi最后返回。height(p)if (1)if(p->lchild=null) lh=(2) if(p->rchild=null) rh=(4); else; elselh=(3);rh=(5);if (lh>rh) hi=(6)elsehi=(8);returnhi;/；elsehi=(7);答： (1)p (2)0 (3)height(p->lchild)(4)0(5)height(p->rchild)(6)lh+1(7)rh+1(8)0* *41 已知一棵满二叉树的结点个数为20 到 40 之间的素数，

16、此二叉树的叶子结点有多少个？答：结点个数在20 到40的满二叉树且结点数是素数的数是31 ，其叶子数是16 。42 用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL 。请写出后序遍历该二叉树的访问结点序列。答： HIDJKEBLFGCA43 一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？答：左右子树均不空的二叉树先序线索化后，空指针域为 1 个（最后访问结点的右链为空）。44 设有正文 AADBAACACCDACACAAD,字符集为 A,B,C,D, 设计一套二进制编码，使得上述正文的编码最短。45 编程求以孩子兄弟表示法存储的森林的叶子结点数。要求描述结构。 题目分析

17、 当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（ firstchild=null）,则它必是叶子， 总的叶子结点个数是孩子子树 （firstchild）上的叶子数和兄弟（ nextsibling）子树上叶结点个数之和。typedefstructnodeElemTypedata;/ 数据域* *structnode * firstchild, * nextsibling;/孩子与兄弟域*Tree;int Leaves (Tree t)/ 计算以孩子 - 兄弟表示法存储的森林的叶子数if(t)if(t->firstchild=null)/ 若结点无孩子，则该结点必是叶子return(1

18、+Leaves(t->nextsibling);/ 返回叶子结点和其兄弟子树中的叶子结点数else return (Leaves(t->firstchild)+Leaves(t->nextsibling); /孩子子树和兄弟子树中叶子数之和/ 结束 Leaves46 有 n 个结点的完全二叉树存放在一维数组A1.n 中，试据此建立一棵用二叉链表表示的二叉树，根由tree 指向。BiTree Creat(ElemType A,int i)/n个结点的完全二叉树存于一维数组A 中，本算法据此建立以二叉链表表示的完全二叉树 BiTree tree;if (i<=n) tree

19、=(BiTree)malloc(sizeof(BiNode); tree->data=Ai;if(2*i>n)tree->lchild=null；elsetree->lchild=Creat(A,2*i)；if(2*i+1>n)tree->rchild=null；elsetree->rchild=Creat(A,2*i+1)；* *return (tree)；/Creat 算法讨论 初始调用时 ,i=1 。47. 以孩子兄弟链表为存储结构，请设计算法求树 / 森林的深度。 题目分析 由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一

20、子女为空，高度为1 和兄弟子树的高度的大者；否则，高度为第一子女树高度加 1 和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。int TreeDepth(CSTree T)if (!T) return 0;else h1= TreeDepth(T->firstchild);h2= TreeDepth(T->nextsibling);return (max(h1+1,h2);/ TreeDepth48. 设计算法返回二叉树 T 的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。 题目分析 二叉树先序序列的最后一个结点，若二叉树有右子树，则是右子树中

21、最右下的叶子结点； 若无右子树， 仅有左子树， 则是左子树最右下的叶子结* *点；若二叉树无左右子树，则返回根结点。BiTree LastNode(BiTree bt)/ 返回二叉树 bt 先序序列的最后一个结点的指针BiTree p=bt;if(bt=null)return(null);else while(p)if (p->rchild)p=p->rchild;/ 若右子树不空，沿右子树向下else if (p->lchild) p=p->lchild; /右子树空，左子树不空，沿左子树向下else return(p);/ 左右子树均为空， p 即为所求/lastn

22、ode49. 设一棵二叉树的根结点指针为 T，C 为计数变量，初值为 0，试写出对此二叉树中结点计数 的算法： BTLC（T，C）。int BTLC(BiTree T,int *c)/ 对二叉树 T 的结点计数if(T)*c+;/ 调用时 *c=0BTLC(T->lchild,&c);/ 统计左子树结点BTLC(T->rchild,&c);/ 统计右子树结点/* *50 设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。void Count(BiTree bt,int *n0,*n) /统计二叉树 bt 上叶子结点数 n0 和非叶子结点数 nif(bt)i

23、f (bt->lchild=null && bt->rchild=null) *n0+；/ 叶子结点else*n+; /非叶结点Count(bt->lchild,&n0,&n);Count(bt->rchild,&n0,&n);/Count51 、编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T 中的所有的边。输出形式为（k1,k2） （ ki,kj） ，其中ki和kj为树结点中的结点标识。Void OutEdger(CSTree T) if (T) p=T->firstchild;while(p)/ 先根

24、遍历输出树中各条边 printf(T->data,p->data); OutEdger(p); p=p->nextsibling;* */52 、已知 Li 和 Ri （i=1,2 ， ， n ）分别指示二叉树中第i 个结点的左孩子和右孩子结点， 0 表示空，试写出判别结点u 是否是结点 v 的子孙的算法。status descendent(int L,int R,int u,int v) if (u&&v) if(Lv=u|Rv=u)return TRUE;else if(descendent(L,R,u,Lv) return TRUE;else retur

25、n(descendent(L,R,u,Rv);else return FALSE;/53.设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。类似本题的另外叙述有：（1 ）设 t 为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。（2 ）写一个将二叉树中每个结点的左右孩子交换的算法。void exchange(BiTree bt)/ 将二叉树 bt 所有结点的左右子树交换* *if(bt) BiTree s；s=bt->lchild; bt->lchi

26、ld=bt->rchild; bt->rchild=s; /左右子女交换exchange(bt->lchild);/ 交换左子树上所有结点的左右子树exchange(bt->rchild);/ 交换右子树上所有结点的左右子树 算法讨论 将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。下面是本题（ 1）要求的非递归算法void exchange(BiTree t)/ 交换二叉树中各结点的左右孩子的非递归算法int top=0; BiTree s,p;/s 是二叉树的结点指针的栈，容量足够大if(bt)

27、s+top=t;while(top>0)t=stop-;if(t->lchild|t->rchild)p=t->lchild;t->lchild=t->rchild;t->rchild=p;/交换左右if(t->lchild) s+top=t->lchild; /左子女入栈if(t->rchild) s+top=t->rchild; /右子女入栈/while(top>0)/if(bt)* */exchange54 要求二叉树按二叉链表形式存储，（ 1）写一个建立二叉树的算法。（ 2 ）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1 至 N 的结点