《数据结构第六章习题课》由会员分享,可在线阅读,更多相关《数据结构第六章习题课(10页珍藏版)》请在金锄头文库上搜索。
1、1、下图所示的4棵二叉树中,不是完全二叉树的是( )ABCD2、二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法( )。 A、正确B、错误C、不一定3、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是( )。 A、acbedB、decabC、deabcD、cedba 4、如果T2是由有序树T转换而来的二叉树,那么T中结点的后序就是T2中结点的( )。 A、前序B、中序C、后序D、层次序5、深度为5的二叉树至多有( )个结点。 A、16B、32C、31D、106、在一个非空二叉树的中序遍历序列中,根结点的右边( )。 A、只有右子树上的所有
2、结点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+m=2n C
3、、m=h-1 D、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/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DEAB+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))
4、D. A*B+C/D*E+F-G14. 在下述结论中,正确的是( )只有一个结点的二叉树的度为0; 二叉树的度为2; 二叉树的左右子树可任意交换; 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A B C D15. 设森林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 500
5、 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-120. 利用二叉链表存储树,则根结点的右指针是( )。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 Cnl Dn 27下面几个符号串编码集合中,不是前缀编码的是( )。A0,10,110,1111 B11,10,001,101,0001C00,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