数据结构练习2-08答案_副本.docVIP

数据结构练习（二）答案 一、填空题： 1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为 （1）4 ，树的深度为 （2）4 ，树中叶子结点的个数为（3）8。 2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间关系的表达式 （4）n=2h-1,m=n+1-2h-1 n=2m-1 。 3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。一棵深度为k的完全二叉树中最少有 2k-1（6） 个结点，最多有（7）2k-1 个结点。 4．具有n个结点的二叉树，当它是一棵 (8)完全 二叉树时具有最小高度 （9）(log2n」+1 ，当它为一棵单支树时具有高度 (10) n 。 5．对具有n个结点的完全二叉树按照层次从上到下， 行编号，i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____， 6．若具有n个结点的二叉树采用二叉链表存储结构，，，ABDCEFG，DBCAFEG， 9．已知某完全二叉树采用顺序存储结构，A,B,C,D,E,F,G,H,I,J， 10．若具有n个结点的非空二叉树有n0个叶结点，1的结点。 11．任何非空树中有且仅有一个结点没有前驱结点，k的树中第i层最多有___ki-1_______个结点(i=1)，深度为h的k叉树最多有___k0+k1+....+kh-1____个结点。 12．非空二叉树一共有__4__种基本形态，第i层最多有__ 2i-1___个结点。 13．在一棵完全二叉树中，编号i和编号j的两个结点处于同一层的条件是_log2i=log2j__ 14．有n个顶点的强连通图至少有 （7）n 弧，有n个顶点的连通图至少有 （8）n-1 边。 15．设无向图G的顶点数为n，图G最少有 (12) 0 边，最多有 (13) n(n-1)/2 条边；若边数为e，用邻接矩阵表示图，求每一顶点度的时间复杂性为 (14) O(n2) ；若用邻接表表示图，访问一个顶点的所有邻接顶点的时间复杂性为 (15) O(n) 。一个有n个顶点的有向图中，最少有 (16)0 弧，最多有 (17) n(n-1) 弧。 二、选择题 1.树型结构最适合用来描述_______ A．有序的数据元素 B．无序的数据元素 C．D． 2.对于一棵具有n个结点、度为4的树而言，。 A．n-4 B．n-3 C．第i层上最多有4×(i-1)个结点 D．最少在某一层上正好有4个结点 3.”二叉树为空”意味着二叉树______ A． B． C．不存在 D．没有结点 4.按照二叉树的定义，具有3个结点的二叉树有___种形态(不考虑数据信息的组合情况)。 A.2 B.3 C.4 D.5 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为 。 A．9 B．11 C．15 D．不确定 6.一个具有1025个结点的二叉树的高h为 。 A．11 B．10 C．11—1025 D．12—1024 7．若二叉树的前序序列与后序序列的次序正好相反,则该二叉树一定是___树。 A． B． C．D．1 8．任何一棵非空二叉树中的叶结点在前序遍历、中序遍历与后序遍历中的相对位置__ A． B． C． D． 9．如图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有_____个叶子结点。 A．4 B．5 C．6 D．7 10．设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_____。 A．n在m右方 B．n是m祖先 C．n在m左方 D．n是m子孙 11．一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是_____。 A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEGB 12．引入线索二叉树的目的是_____。 A．加快查找结点的前驱或后继结点的速度 C．为了能方便找到双亲 B．为了能在二叉树中方便插入和删除 D．使二叉树的遍历结果唯一 13．线索二叉树是一种_____结构。 A．逻辑 B．逻辑和存储 C．物理 D．线性 14．判断线索二叉树中*p结点有右孩子结点的条件是_____。 A．p！=NULL B．P—rchild!=NULL C．p—rtag=0 D．p—rtag=1 15．n个结点的线索二叉树上含有的线索数为_____。 A．2n B．n-1 C．n+1 D．n 16．根据使用频率