数据结构第六章习题课.docx

《数据结构第六章习题课.docx》由会员分享，可在线阅读，更多相关《数据结构第六章习题课.docx（14页珍藏版）》请在三一办公上搜索。

1、数据结构第六章习题课1、下图所示的4棵二叉树中，不是完全二叉树的是 A B C D 2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法。 A、正确 B、错误 C、不一定 3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。 A、acbed B、decab C、deabc D、cedba 4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的。 A、前序 B、中序 C、后序 D、层次序 5、深度为5的二叉树至多有个结点。 A、16 B、32 C、31 D、10 6、在一个非空二叉树的中序遍历序列中，根结点的右边。

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

3、m=2n C、m=h-1 D、n=2h-1 11、设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/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE / 13. 设有一表示算术表达式的二叉树， + + 它所表示的算术表达式是 A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) * C * - C. (A*B+C)/(D*E+) D.

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

5、500 C254 D505 E以上答案都不对 18. 一个具有1025个结点的二叉树的高h为 A11 B10 C11至1025之间 D10至1024之间 19深度为h的满m叉树的第k层有个结点。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-1 20. 利用二叉链表存储树，则根结点的右指针是。 A指向最左孩子 B指向最右孩子 C空 D非空 21对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A先序 B. 中序 C. 后序 D. 从根开始按层次遍历 22若二叉树采用

6、二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 A前序 B中序 C后序 D按层次 23一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足 A所有的结点均无左孩子 B所有的结点均无右孩子 C只有一个叶子结点 D是任意一棵二叉树 24. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 25. 线索二叉树是一种结构。 A 逻辑 B 逻辑和存储 C 物理 D线性 26n个结点的线索二叉树上含有的线索数为 A2n Bnl Cn

7、l Dn 27下面几个符号串编码集合中，不是前缀编码的是。 A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc 28. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 Al.n中时，数组中第i个结点的左孩子为 AA2i(2i=n) B. A2i+1(2i+1=lchild=null) lh=(2) ; else lh=(3); if(p-rchild=null) rh=(4); else rh=(5); if (lhrh) hi=(6)；else hi=(7); el

8、se hi=(8); return hi; / 答：(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之间的素数，此二叉树的叶子结点有多少个？ 答：结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。 42用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 答：HIDJKEBLFGCA 43一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为多少？ 答：左右子树均不空的二叉树先序线索

9、化后，空指针域为1个。 44设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 45编程求以孩子兄弟表示法存储的森林的叶子结点数。要求描述结构。 题目分析当森林以孩子兄弟表示法存储时，若结点没有孩子,则它必是叶子，总的叶子结点个数是孩子子树上的叶子数和兄弟子树上叶结点个数之和。 typedef struct node ElemType data; /数据域 struct node * firstchild, * nextsibling;/孩子与兄弟域 *Tree; int Leaves (Tree t) /计算以孩子-兄弟表示法存

10、储的森林的叶子数 if(t) if(t-firstchild =null) /若结点无孩子，则该结点必是叶子 return(1+Leaves(t-nextsibling); /返回叶子结点和其兄弟子树中的叶子结点数 else return (Leaves(t-firstchild)+Leaves(t-nextsibling); /孩子子树和兄弟子树中叶子数之和 /结束Leaves 46有n个结点的完全二叉树存放在一维数组A1.n中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 BiTree Creat(ElemType A,int i) /n个结点的完全二叉树存于一维数组A中，本算

11、法据此建立以二叉链表表示的完全二叉树 BiTree tree; if (idata=Ai; if(2*in) tree-lchild=null；else tree-lchild=Creat(A,2*i)； if(2*i+1n) tree-rchild=null；else tree-rchild=Creat(A,2*i+1)； return (tree)； /Creat 算法讨论初始调用时,i=1。 47. 以孩子兄弟链表为存储结构，请设计算法求树/森林的深度。 题目分析由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第

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

13、若二叉树无左右子树，则返回根结点。 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即为所求 /lastnode 49. 设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法

14、：BTLC。 int BTLC(BiTree T,int *c) /对二叉树T的结点计数 if(T) *c+; /调用时*c=0 BTLC(T-lchild,&c); /统计左子树结点 BTLC(T-rchild,&c); /统计右子树结点 / 50设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。 void Count(BiTree bt,int *n0,*n) /统计二叉树bt上叶子结点数n0和非叶子结点数n if(bt) if (bt-lchild=null & bt-rchild=null) *n0+；/叶子结点 else *n+; /非叶结点 Count(bt-lchild

15、,&n0,&n); Count(bt-rchild,&n0,&n); /Count 51、编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中的所有的边。输出形式为，其中ki和kj为树结点中的结点标识。 Void OutEdger(CSTree T) /先根遍历输出树中各条边 if (T) p=T-firstchild; while(p) printf(T-data,p-data); OutEdger(p); p=p-nextsibling; / 52、已知Li和Ri分别指示二叉树中第i个结点的左孩子和右孩子结点，0表示空，试写出判别结点u是否是结点v的子孙的算法。 status de

16、scendent(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 return(descendent(L,R,u,Rv); else return FALSE; / 53. 设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild, data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。 类似本题的另外叙述有： 设t为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置

17、交换。 写一个将二叉树中每个结点的左右孩子交换的算法。 void exchange(BiTree bt) /将二叉树bt所有结点的左右子树交换 if(bt) BiTree s； s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; /左右子女交换 exchange(bt-lchild); /交换左子树上所有结点的左右子树 exchange(bt-rchild); /交换右子树上所有结点的左右子树 算法讨论将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。 下面是本题要求的非递归算法 v

18、oid exchange(BiTree t) /交换二叉树中各结点的左右孩子的非递归算法 int top=0; BiTree s,p; /s是二叉树的结点指针的栈，容量足够大 if(bt) s+top=t; while(top0) 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(top0) /if(bt) /exchange 54要求二

19、叉树按二叉链表形式存储， 写一个建立二叉树的算法。写一个判别给定的二叉树是否是完全二叉树的算法。 完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 题目分析二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 BiTree Creat /建立二叉树的二叉链表形式的存储结构 ElemType x；BiTree bt; scanf(“%d”,&x); /本题假定结点数据域为整型 if(x=0) bt=null; else

20、if(x0) bt=(BiNode *)malloc(sizeof(BiNode); bt-data=x; bt-lchild=creat; bt-rchild=creat; else error(“输入错误”)； return(bt); / Creat int JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否则，返回0 int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大 if(p=null) return (1); QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针

21、入队 while (!QueueEmpty(Q) p=QueueOut(Q); /出队 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1; /while return 1; /JudgeComplete 算法讨论完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。