《数据结构复习题》doc版.doc

数据结构复习题第1章 绪 论一、单选题（共有题目7题）1.从一维数组an中顺序查找出一个最大值元素的时间复杂度为（ ）。A. O(1) B. O(n) C. O(n2) D. O(n!)2.输出一个二维数组bmn中所有元素值的时间复杂度为（ ）。A. O(m+n) B. O(mn) C. O(m2) D. O(n2)3.下面程序段的时间复杂度是（ ）。for( int i=0;im;i+)for(int j=0;jn;j+)aij=i*j;A. O(m2) B. O(n2) C. O(mn) D. O(m+n)4.分析下面程序段的时间复杂度是（ ）。int i=1;while (i=n)i=i*2; A. O(n) B. O(log2n) C. O(n2) D. O(1)5.下面程序段的时间复杂度是（ ）。int i,j;for(i=1;i=n;i+)for (j=1;j=i;j+)S;A. O(n) B. O(n2) C. O(log2n) D. O(1)6.下面算法的时间复杂度为（ ）。int f( int n) if(n=0|n=1) return 1;else return n*f(n-1); A. O(n) B. O(1) C. O(n2) D. O(n!)7.下面程序段的时间复杂度是（ ）。int i,j;for( i=0; in; i+)for(j=0; jm;j+)aij=i*j;A. O(n2) B. O(m2) C. O(mn) D. O(m+n)二、填空题（共有题目14题）1.在线性结构中，前驱结点和后继结点之间存在着_的联系。1对1(1：1)2.对算法评价一般从正确性、_、可读性、简单性、_、_六个方面进行的。 健壮性、时间复杂度、空间复杂度3.在图形结构中，前驱和后继结点之间存在着_的联系。多对多（m：n）4.数据结构研究的内容主要包括_、_和数据的_三部分。 数据的逻辑结构；数据的存储结构（数据的物理结构）；操作5.数据的物理结构又名_，它主要有_、_、_和_4种方式。 存储结构；顺序存储；链接存储；索引；散列6.在树形结构中，前驱和后继结点之间存在着_联系。1对多（1：N）7.数据的逻辑结构被分为_、_、_、_4种。集合结构；线性结构；树形结构；图形结构8._是指对特定问题求解步骤的一种描述，是一组指令的有限序列；也可以说是解决特定问题的方法步骤。 算法9.在一个算法的程序描述中，不同的语句重复执行的次数不同，某语句重复执行的次数称为该语句的_。 频度（频次）10._是数据处理领域组织数据的基本单位。 记录（数据记录）11.依据视点的不同，数据结构分为数据的_和_。_是面向问题的，_是面向计算机的。逻辑结构；物理结构；数据的逻辑结构；数据的物理结构（数据的存储结构）12.算法应具备_、确定性、_、输入和输出五个特性。有穷性、可行性13.在下面程序段中，s=s+p语句的执行次数是_，p*=j语句的执行次数是_，该程序段的时间复杂度为_。int i=0,s=0;while(+i=n) int p=1;for( int j=1;jnext; B. L- next = L- next - next;C. L = L; D. L- next = L;3.给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ ）。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)4.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ ）。A. p=q-next;p-next=q-next; B. p=q-next;q-next=p;C. p=q-next;q-next=p-next; D. q-next=q-next-next;q-next=q;5.在一个长度为n的顺序表中删除第i个元素（0in-1）时，需要从前向后依次前移（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i6.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（ ）存储方式节省时间。A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表7.不带头结点的单链表first为空的判定条件是（ ）。A. first = NULL; B. first- next = NULL;C. first- next = first; D. first != NULL;8.执行下面程序段时，执行S语句的次数为（ ）。 for(int i=1; i=n; i+)for(int j=1; jlink所指向的结点，则应执行的操作是（ ）。A. p-link=p-link-link; B. p=p-link; p-link=p-link-link;C. p-link=p; D. p=p-link-link;10.一个数组元素ai与（ ）的表示等价。A. *(a+i) B. a+i C. *a+i D. &a+i11.非空的循环单链表head的尾指针p满足（ ）。A. p-next=NULL B. p=NULL C. p-next=head D. p=head12.在二维数组A810中，每一个数组元素Aij占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（ ）。A. 80 B. 100 C. 240 D. 27013.在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为（ ）。A. n B. n/2 C. (n+1)/2 D. (n-1)/214.带头结点的单链表first为空的判定条件是（ ）。A. first=NULL; B. first- next =NULL;C. first- next =first; D. first!=NULL;15.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n)，其数量级形式的复杂度表示为（ ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)16.某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（ ）。A. O(n) B. O(n2) C. O(n3) D. O(1)17.有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（ ）。A.head=NULL B. Head-next=NULLC. head-next=head D. Head!=NULL18.在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ ）。A. s-next = p-next; p-next = s; B. p-next = s; s-next = q;C. p-next = s-next; s-next = p; D. q-next = s; s-next = p;19.在一个长度为n的顺序存储的线性表中，删除第i个元素（1in）时，需要从前向后依次前移（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i20.设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（ ）。A. s-link=p-link; p-link=s; B. q-link=s; s-link=p;C. p-link=s-link; s-link=p; D. p-link=s; s-link=q;21.在一个长度为n的有序顺序表中搜索值为x元素的时间效率最高的算法的渐进时间复杂度为（ ）。A. O(1) B. O(1) C. O(log2n) D. O(n)22.在一个单链表HL中，若要在指针q所指向结点的后面插入一个由指针p所指向的结点，则执行（ ）。 A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. q-next=p-next; q-next=p; D. p-next=q-next; q-next=p;23.已知L是一个不带表头的单链表，在表首插入结点*p的操作是（ ）。A. p = L; p- next = L; B. p- next = L; p = L;C. p- next = L; L = p; D. L = p; p- next = L;24.设单循环链表中结点的结构为(data, link)，且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ ）。A. s = rear; rear = rear-link; delete s;B. rear = rear-link; delete rear;C.rear = rear-link-link; delete rear;D.s = rear-link-link; rear-link-link = s-link; delete s;25.某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为（ ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(1)26.在一个长度为n的顺序表中向第i个元素（0in-1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i27.在一个长度为n的顺序表的任一位置插入一个新元素的时间复杂度为（ ）。A. O(n) B. O(n/2) C. O(1) D. O(n2)28.多维数组实际上是由嵌套的（ ）实现的。A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量29.设有一个nn的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中（ ）处。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/230.设有一个nn的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中（ ）处。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/231.利用双向链表作线性表的存储结构的优点是（ ）。A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间32.在数据结构的讨论中把数据结构从逻辑上分为（ ）。A.内部结构与外部结构 B.静态结构与动态结构C.线性结构与非线性结构 D.紧凑结构与非紧凑结构33.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。A. O(1) B. O(m) C. O(n) D. O(m+n)34.带表头的双向循环链表的空表满足（ ）。A. firstNULL; B. first-rLink=firstC. first-lLink=NULL D. first-rLink=NULL35.一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为（ ）。A.所有域长度之和 B.最大域所占字节长度C.任意一个域长度 D.sizeof(r)的值36.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。A. n B. n/2 C. (n-1)/2 D. (n+1)/237.在二维数组中，每个数组元素同时处于（ ）个向量中。A. 0个 B. 1个 C. 2个 D. n个38.设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ ）。A. s-link=p; p-link=s; B. p-link=s; s-link=p;C. s-link=p-link; p=s; D. s-link=p-link; p-link=s;39.非空的循环单链表first的尾结点（由p所指向）满足的条件是（ ）。A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first;40.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（ ）。A. n B. n/2 C. (n-1)/2 D. (n+1)/241.采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。A. 必须是连续的 B. 部分地址必须是连续的C. 一定是不连续的 D. 可连续可不连续 42.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)43.在一个长度为n的顺序存储的线性表中，向第i个元素（1in+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A. n-i B. n-i+1 C. n-i-1 D. i44.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。A. HL=p; p-next=HL; B. p-next=HL; HL=p;C. p-next=HL; p=HL; D. p-next=HL-next; HL-next=p;45.下面程序段的时间复杂度为（ ）。 for(int i=0; im; i+) for(int j=0; jnext=NULL; HL-next=HL;2.线性表的链接存储只能通过_顺序访问。 链接指针3.链表是一种采用_存储结构存储的线性表。 链接4.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，则其后继结点的地址为_，后继结点的值为_。p-next; p-next-data；5.若设L是指向带表头的单链表，语句 L-next=L-next-next的作用是_单链表中的第一个结点。 删除6.在单链表中除了表头结点外，任意结点的存储位置由其_结点的指针域的值所指示。 直接前驱7.在双向链表中，每个结点包含两个指针域，一个指向其_结点，另一个指向其_结点。 前驱（双亲，父，后继） 后继（孩子，前驱）8.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地_和释放。 分配9.在链表中进行插入和_操作的效率比在顺序存储结构中进行相同操作的效率高。 删除10.在线性表的单链接存储结构（结点）中，若一个元素所在结点的地址为p，p为一个数组a中的下标，则其后继结点的地址为_。&ap.next 或 (a+p)-next11.在线性表的顺序存储结构中，若一个元素的下标为i，则它的前驱元素的下标为_，后继元素的下标为_。i-1 i+112.单链表中逻辑上相邻的结点而在物理位置上_相邻。不一定13.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的_的值。 指针域14.在循环双向链表中表头结点的左指针域指向_结点，最后一个结点的右指针域指向_结点。 表尾 表头15.对于一个单链接存储的线性表，在表头插入结点的时间复杂度为_，在表尾插入元素的时间复杂度为_。 O(1) O(n)16.在循环单链表中，最后一个结点的指针域指向_结点。表头17.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_，在表尾插入元素的时间复杂度为_。 O(n) O(1)18.链表与顺序表、索引表、散列表等都是数据逻辑结构的_表示。存储19.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫_，另一个叫_域。 数值域 指针20.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对_进行特殊处理。 表头指针21.在双向链表中，每个结点除了数据域外, 还有两个指针域, 它们分别指向_。 前驱结点和后继结点22.链表只适用于_查找。 顺序23.设双向循环链表每个结点结构为(data,llink,rlink)，则结点*p的前驱结点的地址为_。 p-llink;24.线性表是具有_的数据元素的一个_。相同属性、有限序列25.逻辑顺序与物理顺序一致的数据结构是_。 顺序表三、判断题（共有题目13题）1.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。2.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。3.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。4.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。5.用字符数组存储长度为n的字符串，数组长度至少为n+1。6.数据元素是数据的最小单位。7.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。8.在线性链表中删除中间的结点时，只需将被删结点释放。9.线性表若采用链式存储表示，在删除时不需要移动元素。10.数据的逻辑结构与数据元素本身的内容和形式无关。11.如果采用如下方式定义一维字符数组： const int maxSize = 30; char amaxSize; 则这种数组在程序执行过程中不能扩充。12.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。13.顺序表和一维数组一样，都可以按下标随机（或直接）访问。第3章 稀疏矩阵和广义表一、单选题（共有题目4题）1.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为（ ）。A. O(m) B. O(n) C. O(n+t) D. O(n*t)2.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（ ）。A. 行号 B. 列号 C. 元素值 D. 地址3.广义表( )的表头是（ ）。A. ( ) B. 没有表头 C. ( ) D. 04.广义表( )的表尾是（ ）。A. 没有表尾 B. ( ) C. ( ) ) D. 0二、填空题（共有题目16题）1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_、_和_3项。 行（行号），列（列号）元素值2.( ),(e),(a,(b,c,d)的表头是_。 ( ) 或 空表;3.一个广义表中的元素分为_元素和_元素两类。单，表4.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为_域和_域。 值，指针5.一个广义表的深度等于_嵌套的最大层次数。括号6.稀疏矩阵是一种非零元素的个数_零元素的个数，且非零元素的分布没有规律的矩阵。 远远小于（小于，远小于）7.广义表( )的表头是_。 ( );空表;8.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应_对应三元组线性表的长度。 大于等于（=）9.广义表(e),(a,(b,c,d)的深度是_。 310.广义表( ( ) )的表尾是_。 ( );空表11.( ),(e),(a,(b,c,d)的表尾是_。 (e),(a,(b,c,d)12.在一个广义表的存储结构中，每个结点均包含有_个域。 313.广义表(e),(a,(b,c,d)的长度是_。 214.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有_个域，在相应的十字链接存储中，每个结点包含有_个域。4，515.在稀疏矩阵的十字链接存储中，每个结点的down指针域指向_相同的下一个结点，right指针域指向_相同的下一个结点。列号（列），行号（行）16.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_为主序、_为辅序的次序排列。行号（行），列号（列）三、判断题（共有题目1题）1.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。第4章 栈和队列一、单选题（共有题目10题）1.在一个顺序队列中，队首指针指向队首元素的（ ）位置。A. 前一个 B. 后一个 C. 当前 D. 后面2.假定利用数组aN循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未空，当进行出队并返回队首元素时所执行的操作为（ ）。A. return a+r%N; B. return a-r%N;C. return a+f%N; D. return af+%N;3.一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为（ ）。A. top-next=top; B. top=top-data;C. top=top-next; D. top-next=top-next-next;4.一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为（ ）。A. p-next =top; top=top-next; B. top=p; p-next=top; C. p-next=top-next;top-next=p; D. p-next=top;top=p;5.栈的插入和删除操作在（ ）进行。A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置6.当利用大小为N的数组顺序存储一个队列时，若没设有队列长度的变量，则该队列的最大长度为（ ）。A. N-2 B. N-1 C. N D. N17.若让元素1、2、3依次进栈，则出栈次序不可能出现（ ）情况。A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，28.从一个顺序队列删除元素时，首先需要（ ）。A. 队首指针循环加1 B. 队首指针循环减1C. 取出队首指针所指位置上的元素 D. 取出队尾指针所指位置上的元素9.假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为（ ）。A. front=rear B. front!=NULLC. rear!=NULL D. front=NULL10.如果一个递归函数过程中的所有递归语句都是可执行的最后一条语句，则称这种递归过程为（ ），它很容易被改写为非递归过程。A. 单向递归 B. 回溯递归 C. 间接递归 D. 末尾递归二、填空题（共有题目9题）1.后缀表达式“4 5 * 3 2 + -”的值为_。 152.若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_。183.栈又称为_表，队列又称为_表。 后进先出，先进先出4.队列的插入操作在_进行，删除操作在_进行。队尾，队首5.中缀表达式3*(x+2)-5所对应的后缀表达式为_。 3 x 2 + * 5 -6.在一个链队中，若队首指针与队尾指针的值相同，则表示该队为_或该队_。 空，只含有一个结点7.在一个不设队列长度变量的顺序队列Q中，判断队空的条件为_，判断队满的条件为_。Q.front=Q.rear； (Q.rear+1)%MaxSize=Q.front；8.向一个栈顶指针为HS的链栈中插入一个新结点*p时，应执行_和_操作。 p-next=HS; HS=p;9.迷宫问题是一个回溯控制的问题，最好使用_的方法来解决。递归第5章 树和二叉树一、单选题（共有题目34题）1.在一棵完全二叉树中，若编号为i 的结点存在左孩子，则左孩子结点的编号为（ ）。A. 2i B. 2i-1 C. 2i+1 D. 2i+22.在一棵树中，每个结点最多有（ ）个前驱结点。A. 0 B. 1 C. 2 D. 任意多个3.在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。A. 2 i B. 2 i+1 C. 2i-1 D. 2 n4.在一棵具有35个结点的完全二叉树中，该树的深度为（ ）。A. 6 B. 7 C. 5 D. 85.在一棵具有n个结点的完全二叉树中，树枝结点的最大编号是（ ）。A. (n+1)/2 B. (n-1)/2 C. n/2-1 D. n/26.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。 A. 2 B. 1 C. 0 D. 17.在一棵完全二叉树中，对于编号为i(i1)的结点，其双亲结点的编号为（ ）。A. (i+1)/2 B. (i-1)/2 C. i/2 -1 D. i/28.一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，则该二叉树的高度为（ ）。A. 3 B. 4 C. 5 D. 69.一棵树的广义表表示为a(b(c),d(e,f(g(h,i),j)，该树的深度为（ ）。A. 3 B. 4 C. 5 D. 610.在一棵深度为h的完全二叉树中，所含结点个数不大于（ ）。A. 2 h B. 2 h+1 C. 2h -1 D. 2 h-111.树中所有结点的度等于所有结点数加（ ）。A. 0 B. 1 C. -1 D. 212.一棵二叉树的广义表表示为a(b(c),d(e(,g(h),f)，则该二叉树所含的单分支结点数为（ ）。A. 2 B. 3 C. 4 D. 513.在一棵完全二叉树中，若编号为i的结点存在右孩子，则右孩子结点的编号为（ ）。A. 2i B. 2i-1 C. 2i+1 D. 2i+214.在一棵深度为h的完全二叉树中，所含结点个数不小于（ ）。A. 2 h B. 2 h+1 C. 2 h -1 D. 2 h-115.对于一棵具有30个结点的三叉树，则其最小深度为（ ）。A. 3 B. 4 C. 5 D. 616.对于一棵深度为4的三叉树，最多具有（ ）个结点。A. 30 B. 36 C. 40 D. 5417.在一棵二叉树中，叶子结点数等于双分支结点数加（ ）。A. 0 B. 1 C. -1 D. 2EFDGAB/+*-C*18.设有一表示算术表达式的二叉树（见下图），它所表示的算术表达式是（ ）。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-G19.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。A.9 B.11 C.15 D.不确定20.在一棵三叉树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A.4 B.5 C.6 D.7 21.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。A. 250 B. 500 C.254 D.以上答案都不对22.有关二叉树下列说法正确的是（ ）。A.二叉树的度为2 B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为223.一个具有1025个结点的二叉树的高h为（ ）。A.11 B.10 C.11至1025之间 D.10至1024之间24.一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结点。A.2h B.2h-1 C.2h+1 D.h+1 25.对于有n 个结点的二叉树，其高度为（ ）。A.nlog2n B.log2n C.log2n+1 D.不确定26.一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）。A.logn+1 B.logn+1 C.logn D.logn-127.深度为h的满m叉树的第k层有（ ）个结点。(1kh)A.mk-1 B.mk-1 C.mh-1 D.mh-128.在一棵高度为k的满二叉树中，结点总数为（ ）。A.2k-1 B.2k C.2k-1 D.log2k+129.高度为 K的二叉树最大的结点数为（ ）。A.2k B.2k-1 C.2k -1 D.2k-1-130.一棵树高为K的完全二叉树至少有（ ）个结点.A.2k 1 B. 2k-1 1 C. 2k-1 D. 2k31.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）。A.4 B.5 C.6 D.732.某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个结点 B.任一结点无左子树C.高度等于其结点数 D.任一结点无右子树33.在下列情况中，可称为二叉树的是（ ）A.每个结点至多有两棵子树的树 B. 哈夫曼树C.每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树34.由3 个结点（结点不区分大小）可以构造出多少种不同的二叉树？（ ）A.2 B.3 C.4 D.5二、填空题（共有题目18题）1.对于一棵具有n个结点的树，则树中所有结点的度数之和为_。 n-12.对于一棵含有40个结点的理想平衡树，它的高度为_。 63.在一棵二叉树中，第5层上的结点数最多有_个。 164.一棵高度为3的四叉树中，最多含有_结点。 215.在一棵二叉树中，若双分支结点数为5个，单分支结点数为6个，则叶子结点数为_个。 66.一棵三叉树的结点个数为50，则它的最小深度为_，最大深度为_。 5，507.在一棵高度为5的理想平衡树中，最少含有_个结点，最多含有_个结点。 16，318.一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则结点H的双亲结点是_，孩子结点有_。 B I、J9.一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为_，右孩子元素为_。 a2i a2i+110.已知一棵二叉树的先根和中根序列如下：先根序列：A，B，C，D，E，F，G，H，I，J中根序列：C，B，A，E，F，D，I，H，J，G则其后根序列为_。 C B F E I J H G D A11.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数有2个，则度为0的结点数有_个。 612.一棵深度为5的满二叉树中的结点数为_个。 3113.在一棵高度为3的四叉树中，最多含有_个结点，假定树根结点的高度为0。 8514.如果结点A有3个兄弟，而且B是A的双亲，则B的度是_。415.已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_，左子树中有_， 右子树中有_。a bde hfcg 16.如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_。 6917.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用.表示，现前序遍历二叉树，访问的结点的序列为ABD.G.CE.H.F.，则中序遍历二叉树时，访问的结点序列为_；后序遍历二叉树时，访问的结点序列为_。 .D.G.B.A.E.H.C.F. GD.BHE.FCA18.含4个度为2的结点和5个叶子结点的二叉树，可有_个度为1的结点。 5三、判断题（共有题目16题）1.二叉树是度为2的有序树。2.深度为K的二叉树中结点总数2k-1。3.用一维数组存储二叉树时，总是以前序遍历顺序存储结点。4.完全二叉树中，若一个结点没有左孩子，则它必是树叶。5.二叉树只能用二叉链表表示。6.完全二叉树一定存在度为1的结点。7.树形结构中元素之间存在一个对多个的关系。8.度为二的树就是二叉树。9.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。10.对于有N个结点的二叉树，其高度为log2n。11.二叉树的遍历只是为了在应用中找到一种线性次序。12.二叉树的前序遍历并不能唯一确定这棵树，