数据结构第六章习题课

数据结构第六章习题课数据结构第六章习题课数据结构第六章习题课数据结构第六章习题课编制仅供参考审核批准生效日期地址：电话：传真:邮编:1、下图所示的4棵二叉树中，不是完全二叉树的是（）AABCD2、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法（）。A、正确 B、错误 C、不一定3、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A、acbed B、decab C、deabc D、cedba4、如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的（）。A、前序 B、中序 C、后序 D、层次序5、深度为5的二叉树至多有（）个结点。A、16 B、32 C、31 D、106、在一个非空二叉树的中序遍历序列中，根结点的右边（）。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+hB、h+m=2nC、m=h-1D、n=2h-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/DEABAB+C*EFDG+*-/13.设有一表示算术表达式的二叉树（见右图），它所表示的算术表达式是（）A.A*B+C/(D*E)+(F-G)B.(A*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．①②③B．②③④C．②④D．①④15.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定16．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C17．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对18.一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间19．深度为h的满m叉树的第k层有（）个结点。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-120.利用二叉链表存储树，则根结点的右指针是（）。A．指向最左孩子B．指向最右孩子C．空D．非空21．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历22．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最合适。A．前序B．中序C．后序D．按层次23．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树24.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()的双亲的右子树中最左的结点的左子树中最右结点的左子树中最右叶结点25.线索二叉树是一种（）结构。A．逻辑B．逻辑和存储C．物理D．线性26．n个结点的线索二叉树上含有的线索数为（）A．2nB．n－lC．n＋lD．n27．下面几个符号串编码集合中，不是前缀编码的是（）。A．{0,10,110,1111}B．{11,10,001,101,0001}C．{00,010,0110,1000}D．{b,c,aa,ac,aba,abb,abc}28.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为（）A．A[2i](2i=<n)B.A[2i+1](2i+1=<n)C．A[i/2]D．无法确定29、高度为h的完全二叉树至少有多少个结点至多有多少个结点解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-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)}用图表示出此树，并回答下列问题：(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的兄弟，g,h是f的兄弟；b的层次是2，n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3。32、试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同；(4)前序、中序、后序序列均相同。答：(1)前序序列和中序序列相同的二叉树是：没有左子树的二叉树(右单支树)。(2)中序序列和后序序列相同的二叉树是：没有右子树的二叉树(左单支树)。(3)前序序列和后序序列相同的二叉树是：只有根结点的二叉树。(4)前序、中序、后序序列均相同的二叉树：只有根结点的二叉树。33、对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。解：A

/\BC/\\

DEF/\

/GHI\

J34、对下图所示的森林：(1)求各树的前序序列和后序序列；(2)求森林的前序序列和后序序列；(3)将此森林转换为相应的二叉树；(4)给出(a)所示树的以双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代解：(1)

(a)的前序序列：ABCDEF

后序序列：BDEFCA

(b)的前序序列：GHIJK

后序序列：IJKHG

(c)的前序序列：LMPQRNO

后序序列：QRPMNOL(2)

此森林的前序序列：ABCDEFGHIJKLMPQRNO

此森林的后序序列：BDEFCAIJKHGQRPMNOL略略35．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为。答：n/236．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为(1),则该二叉树对应的树林包括(2)棵树。答：(1)EACBDGF（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,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为根的二叉树的左子树和右子树的高，hi为以p为根的二叉树的高，hi最后返回。height(p){if((1)){if(p->lchild==null)lh=(2);elselh=(3);if(p->rchild==null)rh=(4);elserh=(5);if(lh>rh)hi=(6)；elsehi=(7);}elsehi=(8);returnhi;}n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。BiTreeCreat(ElemTypeA[],inti)以孩子兄弟链表为存储结构，请设计算法求树/森林的深度。[题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。intTreeDepth(CSTreeT){if(!T)return0;else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);return(max(h1+1,h2));}}设计算法返回二叉树T的先序序列的最后一个结点的指针，要求采用非递归形式，且不许用栈。[题目分析]二叉树先序序列的最后一个结点，若二叉树有右子树，则是右子树中最右下的叶子结点；若无右子树，仅有左子树，则是左子树最右下的叶子结点；若二叉树无左右子树，则返回根结点。BiTreeLastNode(BiTreebt)设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。intBTLC(BiTreeT,int*c)设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild,data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。类似本题的另外叙述有：（1）设t为一棵二叉树的根结点地址指针，试设计一个非递归的算法完成把二叉树中每个结点的左右孩子位置交换。（2）写一个将二叉树中每个结点的左右孩子交换的算法。voidexchange(BiTreebt)//将二叉树bt所有结点的左右子树交换{if(bt){BiTrees；s=bt->lchild;bt->lchild=bt->rchild;bt->rchild=s;//左右子女交换exchange(bt->lchild);//交换左子树上所有结点的左右子树exchange(bt->rchild);//交换右子树上所有结点的左右子树}}[算法讨论]将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。下面是本题（1）要求的非递归算法voidexchange(BiTreet)//交换二叉树中各结点的左右孩子的非递归算法{inttop=0;BiTrees[],p;//s是二叉树的结点指针的栈，容量足够大if(bt){s[++top]=t;while(top>0){t=s[top--];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的结点一一对应。此题以此定义为准。[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。BiTreeCreat()//建立二叉树的二叉链表形式的存储结构{ElemTypex；BiTreebt;scanf(“%d”,&x);//本题假定结点数据域为整型if(x==0)bt=null;elseif(x>0){bt=(Bi