数据结构习题集第6和二叉树

1、第六章树和二叉树一、单项选择题1.树的先序遍历是。A. 先树的根结点，再从左到右依次先序遍历根结点的各子树B. 先序遍历根结点的各子树，最后根结点C. 先从左到右依次先序遍历根结点的各子树D. 先树的根结点，再从右到左依次先序遍历根结点的各子树2.除根结点外，树上每个结点。要有任意多个孩子，任意多个双亲可有任意多个孩子、一个双亲可有一个孩子、任意多个双亲只有一个孩子、一个双亲用孩子兄弟链表表示一棵树，若要找到结点*p 的第 5 个孩子，则只要先找到*p个孩子，然后。从孩子域指针连续扫描 5 个结点即可从孩子域指针连续扫描 4 个结点即可从兄弟域指针连续扫描 5 个结点即可从兄弟域指针连续扫描

2、4 个结点即可的第 14. 现有一棵结点总数 20 的二叉树，它含有 4 个度为 2 的结点，由此可知其叶子结点数为。A. 20B.16C.11D.55. 若由一棵一般树转化得到的二叉树是非空二叉树，则该二叉树的形状是。A. 根结点C. 根结点可能有树的二叉树树和右子树B. 根结点无树的二叉树D. 各结点只有一个孩子的二叉树6.若由森林转化得到的二叉树是非空二叉树，则该二叉树的形状是。根结点根结点无根结点可能树的二叉树树的二叉树有树和右子树D.7.A.各结点只有一个孩子的二叉树树是叶子结点的外部路径长度的二叉树。最短B. 最长C. 可变D. 固定8.从 1 开始对二叉树进行连续，要求每个结点的

3、大于其左、右孩子的。在同一个结点的左、右孩子中，其左孩子的号。小于其右孩子的，则可采用遍历实现编A. 先序9.二叉树B. 中序C. 后序D. 从根开始的层层遍历索化后，下列问题中相对较难解决的是。先序线索二叉树中求先序后继中序线索二叉树中求中序后继中序线索二叉树中求中序前趋后序线索二叉树中求后序后继10.一棵A. 0树为空的二叉树在先序线索化后，其空指针域数为。B. 1C. 2D. 不确定11.如下图所示二叉树中的中序遍历序列是。A. abcdgefB.dfebagcC. dbaefcgD. defbagc，则其指针域部分用来指向结点的左、12. 对具有 100 个结点的二叉树，若用二叉链表右

4、孩子，其余个指针域为空。A. 50B. 99C. 100D. 101树，则该D. 2513.设有 13 个值，用它们组成一棵树有个结点。A. 13二、填空题B. 12C. 26*1.设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别为 M1、M2 和 M3，与森林 F 对应的三叉树根结点的右子树上的结点个数是。M2+M3*2.有如下图所示的二叉树，其前序遍历序列是，中序遍历序列是，后序遍历序列是。abcidehfgjicdbaefghjidcbgfjhea*3.对于一个具有 n 个结点的二叉树，当它为一棵二叉树时具有最小高度，即为，当它为一棵单支树具有高度，即为。完全log2(n+1)

5、最大n对于一棵具有 n 个结点的树，该树中所有结点的度这和为。n+1.假定一棵树的广义表表示为 A(B(E),C(F(H,I,J),G),D),则该树的度为，树的深度为，终端结点的个数，单分支结点的个数为，双分支结点的个数，三分支结点的个数为，C 结点的双亲结点为，其孩子结点为和结点。346112AFG3.以如下图所示的二叉树，其前序遍历序列是，中序遍历序列是，后序遍历序列是。abdceghf,dbagehcfdbghefca4.在二叉树的遍历中，任何结点的先于树都该结点的右子树遍历，二叉树的先序遍历顺序是 ABDGEHICE，则该二叉树的根结点是。 A二叉树的后序遍历顺序是 GFCDBFIB

6、A，则该二叉树的根结点是。 A树与二叉树之间的救困扶危方法中，树的根结点变成二叉树的。根结点树与二叉树之间的转换方法中，树的 B 结点的右边相邻的兄弟结点是 C,在变成二叉树后， C 结点是 B 结点的结点。右孩子三、多项选择题设 F 是由 T1、T2 和 T3 三棵树组成的森林，与 F 对应的二叉树为 B，已知 T1、T2 和 T3的结点个数分别为 n1、n2 和 n3，则二叉树 B 的根结点的为 和。树和右子树中结点的个数分别A. n1+n2+n3B.n1-1C. n1+n2D. n2+n32.设有一棵满二叉树，用顺序方法，将它的 n 个结点按从上到下的，从左到右的顺序编号作为下标，于一维

7、数组d1.n中，那么，对于其左孩子序号为，右孩子的序号为。不 i 的结点，若它有左、右孩子，A.2iB. 2i+1C. 2i-1D. i+13.对于一棵高度为 k数至多为。的二叉树，共第 i 层（ik）上的结点个数至多为个，总结点个A. 2iB.2i-1C.2i-1D. 2kE. 2k-1F. 2k-14.深度为 k 的完全二叉树，至少有个结点，至多有个结点。A. 2k-1-1B.2k-1C.2k-1D.2kE.2k+1四、算法设计题10. 二叉树的中序遍历算法的通用形式为：void Inorder (Bif (T) Node *T, void(*visit)(Daype x)Inorder(

8、T-lchild, visit); Visit(T-data);Inorder(T-rchild, Visit);其中 visit 是一个函数指针，它指向形如 void f(daype x)的函数。因此可以将结点的操作写在函数 f 中，通过调用语句 Inorder(root,f)将f 的地址传递给 visit 来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成中序遍历的函数调用。解：设计f 函数如下：void f(ElemType x)xout xlchild=NULL & t-rchild=NULL) return 1;elsereturn (countleaf(t-lchi

9、ld)+countleaf(t-rchild);结点总数的算法如下：nodes(BNode *t)if (t=NULL)retrun 0; elsereturn (nodes(t-lchild)+nodes(t-rchild)+1);12.以二叉链表为结构，写出求二叉树高度的算法。解：算法如下：heigh (BNode *t)h1, h2;if (t=NULL)return 0; else h1=height(t-lchild); h2=height(t-rchild); if (h1h2)return h1; elsereturnh2;13.以二叉树表为void copytree(B结构，写

10、一个一棵二叉树的算法。Node* root,BNoce*newroot)其中，新树的结点是动态申请的。解：本题的递归算法如下：void copytree(BNode* root,BNoce*newroot)BNode*p:if (root!=NULL)newroot=( B newroot-daNode *) malloc( sizeof(B-data;Node);copytree(root-lchild, newroot-lchild);copytree(toot-rchild, newroot-rchild);elsenewroot=NULL;五、简答题1.对二叉树中的结点进行按层次顺序（每一层自左至右）的操作称为二叉树的遍历，得到的结点序列称为二叉树层次序列。