数据结构单元自测题

《数据结构单元自测题》由会员分享，可在线阅读，更多相关《数据结构单元自测题（28页珍藏版）》请在装配图网上搜索。

1、第一章 线性表一 单选题1 线性表是具有n个_的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项*2 线性表的静态链表存储结构与顺序存储结构相比优点是_。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为_。 A) O(n ) B ) O(l) C) O(n) D) O(n2)*4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关;(2) 静态链表中能容纳元素个数的最大数在定义是

2、就确定了,以后不能增加;(3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动.PS图1.10插入结点示意 以上错误的是_. A) (1),(2) B) (1) C) (1),(2),(3) D) (2)5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为_.A) snext=p+1; pnext=s; B) (*p).next=s; (*s).next=(*p).next; C) snext=pnext; pnext=snext; D) snext=pnext; pnext=s;6 在双向链表存储结构中,删除p所指的结点时须修改指针_A) pnextprior=ppr

3、ior; ppriornext=pnext;B) pnext=pnextnext; pnextprior=p;.C) ppriornext=p; pprior=ppriorprior;D) pprior=pnextnext; pnext=ppriorprior;7在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,其修改指针的操作是_.A) pnext=q; qprior=p; pnextprior=q; qnext=q;B) pnext=q; pnextprior=q; qprior=p; qnext=pnext; C) qprior=p; qnext=pnext; pnex

4、tprior=q; pnext=q; D) qnext=pnext; qprior=p; pnext=q; pnext=q;8 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_. A) n B) 2n-1 C)2n D) n-19 在一个长度为n的顺序表中,在第i个元素(lin+1)之前插入一个新元素时须向后移动_个元素. A) n 1 B ).n-i+1 C)n-i-1 D) .i10 线性表L=(a1 ,a2,an),下列说法正确的是_.A) 每个元素都有一个直接前驱和一个直接后继 B) 线性表中至少有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一

5、个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继11 对单链表表示法,以下说法错误的是_.A) 数据域用于存储线性表的一个数据元素 B) 指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C) 所有数据通过指针的链接而组织成单链表 D) NULL称为空指针,它不指向任何结点只起标志作用12 若给定有n个元素的向量,则建立一个有序单向链表的时间复杂度的量级是_.A) O(l) B) O(n) C) O(n2) D) O(nlog2n) 13 以下说法正确的是_.A) 顺序存储方式的优点是存储密度大且插入,删除运算效率高B) 链表的每个结点中都恰好包含

6、一个指针C) 线性表的顺序存储结构优于链式存储结构D) 顺序存储结构属于静态结构而链式结构属于动态结构14 以下说法错误的是_.A) 对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表 B) 对单链表来说,只有从头结点开始才能扫描表中全部结点C) 双链表的特点是找结点的前驱和后继都很容易D) 对双链表来说,结点*p的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前驱指针中15以下说法错误的是_.A) 求表长,定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B) 顺序存储的线性表可以随机存取C) 由于顺序存储要求连续的存储区域,所

7、以在存储管理上不够灵活D) 线性表的链式存储结构优于顺序存储结构*二 多选题1 表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动的元素平均个数为_,删除一个元素所需移动的平均个数为_. A) (n-1)/2 B) n C) n+1 D) n-1 E) n/2 F) (n+1)/2 G) (n-2)/22 便于插入和删除操作的是_. A) 静态链表B) 单链表 C) 顺序表 D) 双链表 E)循环链表3 从表中任一结点出发都能扫描整个表的是_. A) 静态链表B) 单链表 C) 顺序表 D) 双链表 E)循环链表三 填空题1 在单链表中设置头结点的作

8、用是_.2 设单链表的结点结构为(data,next),next为指针域.已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:_;_.3 对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有_个,单链表为_个。4 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻.因此,这种表便于_访问,是一种_结构.5 对一个线性表分别进行遍历和逆置运算,其最好的时间复杂性量级分别为_和_.6 在一个循环单链表中,表尾结点的指针域与表头指针_.7 求顺序表和单链表长度的时间复杂性的量级分别为_和_.8 在一个不带头结点

9、的单链表中,在表头插入或删除与在其他位置插入或删除其操作过程_.9 在线性表的顺序存储中,元素之间的逻辑关系是通过_决定的;在线性表的链式存储中,元素之间的逻辑关系是通过_决定的.10 单链表表示法的基本思想是用_表示结点间的逻辑关系.四 判断题1 线性表采用链表存储时,结点和结点内部的存储空间可以是不连接的. ( )2 在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点. ()3 顺序存储的线性表可以随机存取. ( )4、在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。 ( )5、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该

10、元素的位置有关。 ( )6. 顺序存储结构属于静态结构，链式结构属于动态结构。 ( )五 算法设计题*2、在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，但不是B中的元素时,e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表根据元素之值按递增排列。函数append()用于在链表中添加结点。#includeStruct nodeInt element;Struct node *link; Typedef

11、 struct node NODE;NODE *A,*B,*C;NODE *append(last,e);NODE *last;Int e;Lastlink=(NODE*)malloc(sizeof(NODE); lastlinkelement=e; return(lastlink); NODE *difference(A,B)NODE *A,*B;NODE *C,*last; C=last=(NODE*)malloc(sizeof(NODE); While( ( 1 ) ) If(Aelementai+1an. 五 算法设计题 1 可用一个数组S(设大小为MAX)作为两个堆栈的共享空间.请说

12、明共享方法,栈满/栈空的判断条件,用C语言设计公用的入栈操作push(I,x),其中I为0或1,用于表示栈号,x为入栈值. 2 试各举一个例子,用示意图和简要说明阐述栈和队列在程序设计中所起的作用. 3 已知Q是一个非空队列,S是一个空栈。使用C语言编写一个算法，仅用队列和栈的ADT函数和少量工作变量，将队列Q中的所有元素逆置.栈的ADT函数有: makeEmpty(s:stack); 置空栈 push(s:stack;value:datatype); 新元素value进栈pop(s:stack):datatype; 出栈,返回栈顶值isEmpty(s:stack):Boolean; 判栈空否

13、队列的ADT函数有:enqueue(q:queue;value:datatype); 元素value进队deQueur(q:queue):datatype; 出队列,返回队头值isEmpty(q:queue):Boolean; 判队列空否4 有递归算法如下: int sum(int n) if(n=0) sum=0; else cinx; sum=sum(n-1)+x; 设初值n=4,读入x=4,9,6,2. 问:(1)若x为局部变量时,该函数递归结束时返回调用程序的sum=?并画出在递归过程中栈状态的变化过程. (2)若x为全程变量,递归结束时返回调用程序的sum=?5 已知Fibonacc

14、i数列的递归定义如下: 试写出求解fib(n)的递归和非递归算法. fib(n)= 第三章 串 一 单选题 1 若串S=software,其子串的数目是_. A)8 B)37 C)36 D)9 2 设串长为n,模式串长为m, 则KMP算法所需的附加空间为_. A)O(m) B)O(n) C)O(n*log2m) D)O(m*n) E)其他 3 设S为一个长度为n的字符串,其中的字符各不相同,则S中互异的非平凡子串(非空且不同于S本身)的个数为_. A)2n-1 B)n2 C)(n2/2)+(n/2) D)(n2/2)+(n/2)-1 E) (n2/2)-(n/2)-1 4 字符串ababaab

15、ab的nextval为_. A)(0,1,0,1,0,4,1,0,1) B)(0,1,0,1,0,2,1,0,1) C)(0,1,0,1,0,0,0,1,1) D)(0,1,0,1,0,1,0,1,1) 5 在字符串匹配中,当模式串位j与主串位i的比较失败时,新一趟匹配开始,主串的位移公式是_. A)i =i+1 B) i=j+1 C)i=i-j+1 D)i=i-j+2 6 已知串S=aaab,其next数组值为_. A)0123 B)1123 C)1231 D)1211 二 多选题1 串又称字符串_. A)串中元素只能是字符 B)串中元素只能是字母 C)串是一种特殊的线性表 D)串中可以含有

16、空白字符 E)串长度不为零 2 模式串T=abcaabbcabcaabdab,该模式串的next数组值为(1)_,nextval数组的值为(2)_.3 两个串相等必有_. A)串长度相等 B)串中各位置字符任意 C)串中各位置字符均对应相等 D)串长度不等 E)串长度任意三 填空题1 空格串是指_,其长度等于_. 2 模式串p=abaabcac的next函数值序列为_.3一个字符串中_称为该串的子串.4 设正文串长度为n,模式串长度为m,则串匹配的KMP算法的时间复杂度为_.5空串和空格串的区别在于:_.6 在字符串运算中的”模式匹配”是常见的,KMP匹配算法是有用的办法.(1) 其基本思想为

17、_.(2) 对模式串P(=P1P2.Pn)求next数组时,next i 是满足下列性质的k的最大值或为0:_. 7 串相等是指_. 8设有两个串P和Q,求Q在P中首次出现的位置运算称_. 9 串的两种最基本的存储方式是_. 10 串的顺序存储有两种方法:一种是每个单元只存一个字符,称为_格式;另一种是每个单元存放多个字符,称为_格式. 四 判断题 1 串是由有限个字符构成的连续序列,串长度为串中字符的个数,子串是主串中字符构成的有限序列. 2 子串定位函数的时间复杂度在最坏情况下为O(n*m),因此子串定位函数没有实际使用的价值. 3 KMP算法的最大特点是指示主串的指针不需回朔. 4 设模

18、式串的长度为m,目标串的长度为n;当nm且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价也可能更为节省. 5 设有两个串P和Q,其中Q是P的子串,把Q在P中首次出现的位置作为子串Q在P中的位置算法称为模式匹配. 五 算法设计题 1 S=”S1S2Sn”是一个长为N的字符串,存放在一个数组中,编程序将S改造之后输出: (1) 将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分:(2) 将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分. 例如:S=ABCDEFGHIJKL 则改造后的S为ACEGIKLJHFDB.2 写一个递归算法来实现

19、字符串逆序存储,要求不另设存储空间. 第四章 数组和广义表 一 单选题 1 已知广义表LS=(a,b,c),(d,e,f)，运用head和tail函数取出LS元素e的运算是_.A) head(tail(LS) B)tail(head(LS) C)head(tail(head(tail(LS) D)head(tail(tail(head(LS) 2 将一个A1100,1.100的三对角矩阵，按行优先存入一维数组B1.298中，A中元素a66,65（即该元素下标i=66,j=65）,在B数组中的位置K为_. A)198 B)195 C)197 3 若广义表A满足Head(A)=Tail(A),则A

20、为_. A)() B)() C)(),() D)(),(),() 4 广义表A=(a,b,(c,d),(e,f,g),则下面式子的值为_.Head(Tail(Head(Tail(Tail(A) A) (g) B) (d) C) c D) d5 图4.9所示的结构是一个_. A)线性表 B)数形结构 C)图结构 D)广义表 atom info link图4.9中的结点结构为：图4.9循环链表1 b 0 -1head 6 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,.,8，列下标j=1,2,10.若A按行先存储，元素A8，5的起始地址与当A按列先存储时的元素_的起始地址相同.设每

21、个字符占一个字节. A) A8,5 B) A3,10 C) A5,8 D) A0,97 数组SZ-350,010含有元素数目为_. A) 88 B) 99 C) 80 D) 90 8 稀疏矩阵一般的压缩存储方法有_两种.A)二维数组和三维数组 B)三元组和散列表 C)三元组和十字链表 D)散列表和十字链表 9 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如图4.10所示)按行序存放在一维数组B1.n(n-1)/2中,对下三角部分中任一元素aij(ij)在一维数组B的下标位置k值为_. A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i

22、(i+1)/2+jA=图4.10 矩阵A的下三角部分 10 对于以行为主序的存储结构来说,在数组Ac1.d1,c2.d2中,c1和d1分别为数组A的第一维下标的下,上界, c2和d2分别为第二维下标的下,上界,每个数据元素占k个存储单元,二维数组中任一元素ai,j的存储位置可由_确定.A) Loci,j=(d2-c2+1)(i-c1)+(j-c2) kA) Loci,j=Locc1,c2+(d2-c2+1)(i-c1)+(j-c2) kB) Loci,j=Ac1,c2+(d2-c2+1)(i-c1)+(j-c2) kC) Loci,j=Loc0,0+(d2-c2+1)(i-c1)+(j-c2)

23、 k 二 多选题 1 稀疏矩阵的压缩存储方式有_ . A) 顺序存储 B) 三元组表 C) 循环链表 D) 十字链表 2 对广义表来说,下述哪些是正确的_.A) 广义表是一种多层次的结构 B) 广义表是一种非线性结构 C)广义表是一种共享结构 D) 广义表是一种递归表 E) 广义表是一种单链表结构 三 填空题1 广义表(a,(a,b),d,e,(i(i,j,),k)的长度是_,深度是_.2 设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储:a11=1),则a85的地址为_.3 设数组a1.50,1.80的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素a45,6

24、8的存储地址为_;若以列序为主序存储,则元素a45,68的存储地址为_.4 设有三对角矩阵如图4.11所示,将带状区域中的元素aij(|i-j|1)放在一维数组B中,则B的大小为_.元素aij在B中的位置是_.(下标从0开始计) 5 三维数组a 4 5 6 (下标从0开始计,a有456个元素),每个元素的长度是2,则a 2 3 4 的地址是_.(设a 0 0 0 的地址是1000,数据以行为主序方式存储)6 广义表的元素可以是广义表;因此,广义表是一个_的结构.7 数组结构是由固定数量的且由一个值和一组下标组成的数据元素构成,其元素的下标关系具有_.图4.11三对角矩阵 8 一维数组的逻辑结构

25、是_,存储结构是_; 对二维或多维数组,分为按_和_两种不同的存储方式. 9 广义表(a)的表头是_,表尾是_. 10 需要压缩存储的矩阵可分为_矩阵和_矩阵两种. 四 判断题 1 稀疏矩阵压缩存储后,必会失去随机存取功能. 2 若一个广义表的表头为空表,则此广义表亦为空表. 3 广义表是线性表的推广,是一类线性数据结构. 4 任何一个非空广义表,其表头可能是单元素或广义表,其表尾必定是广义表. 5 一个稀疏矩阵Amn采用三元组形式表示.若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Amn的转置运算 6 数组是同类型值的集合. 7 数组是一种复杂的数据结构;数组元素之间

26、的关系既不是线性的,也不是树形的. 8 广义表是由零或多个原子或子表所组成的有限序列,所以广义表可能是空表. 9 线性表可以看成是广义表的特例,如果广义表的每个元素都是原子,则广义表便成为线性表. 10 广义表中原子个数即为广义表的长度. 五 综合题目 1 设有矩阵a=,执行下列语句后,矩阵c和a的结果分别是多少?(1) FOR i:=1 TO 3 DO FOR j:=1 TO 3 DO c i,j :=aa i,j ,a j,i (2) FOR i:=1 TO 3 DOFOR j:=1 TO 3 DOa i,j :=aa i,j ,a j,i 2 一个n阶对称矩阵A采用一维数组S按行序为主序

27、存放其上三角各元素,写出S K 与A i,j 的关系公式.设A1,1存于S1中. 3 给定有m个整数的递增有序数组a 1.m 和有n个整数的递减有序数组b 1.n ,试写出算法,将数组a和b归并为递增有序数组c 1.m+n .(要求算法的时间复杂度为O(m+n) 4 给定一个整数数组b 0.N-1 ,b中连续的相等元素构成的子序列称为平台,试写算法,求出b中最长平台的长度. 5 如果一个数列中的任意一段(至少是两个元素)的各个元素均相同,我们称之为等值数列段等值数列段中元素的个数叫等值数列段长度.现有由100个元素组成的整数数列A,求A中长度最大的所有等值数列段的首末位置,如果没有等值数列段,

28、则输出特殊标志. 第五章 树和二叉树一 填空题1 8层完全二叉树至少有_个结点,拥有100个结点的完全二叉树的最大层数为_.2 线索二叉树的左线索指向其_,右线索指向其_.3 树在计算机内的表示方式有_,_,_.4 一棵有n个结点的满二叉树有_个度为1的结点,有_个分支(非终端)结点和_个叶子,该满二叉树的深度为_.5 设一棵后序线索树的高度是50,结点x是树中的一个结点,其双亲是结点y,y的右子树高度是31,x是y的左孩子,则确定x的后继最多需经过_中间结点(不含后继及本身).6 设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B.已知T1,T2,T3的结点数分别为n1,n2和n

29、3,则二叉树B的左子树中有_个结点,二叉树B的右子树中有_个结点.7 若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点,则它必是该子树的_序列中的最后一个结点.8 一棵共有n个结点的树,其中所有分支结点的度均为k,则该树中的叶子结点个数为_.9 深度为k(设根的层数为1)的完全二叉树至少有_个结点,至多有_个结点,k和结点数n之间的关系是_.10 一棵含有n个结点的k叉树,可能达到的最大深度为_,最小深度为_.11 包含结点A,B和C的二叉树有_种不同的形态,_种不同的二叉树.12 包含结点A,B和C的树有_种不同的形态,_种不同的树. 13 设只包含根结点的二叉树高度为0,则高度

30、为k的二叉树最大结点数为_,最小结点数为_.14 某二叉树结点的对称序列为A,B,C,D,E,F,G, 后序序列为B,D,C,A,F,G,E, 则该二叉树结点的前序序列为_,该二叉树对应的树林包括_棵树. 15 若二叉树有n个结点,对它分别进行前序遍历,中序遍历,后序遍历时,开辟的栈分别为_个存储单元,_个存储单元,_个存储单元16 一棵完全二叉树有999个结点,它的深度是_.A B C DG E H F I 图5.43 树17 对于一棵具有n个结点的树,该树中所有结点的度数之和为_. 18 有n个结点并且其高度为n的二叉树有_个.19 图5.42为某树的静态双亲链表表示,则结点D,E的双亲分

31、别为_. 01234 A -1 B 0 C 0 D 1 E 2图5.42双亲链表 20 一棵具有n个结点的二叉树,若它有n0个叶子结点,则该二叉树上度为1的结点n1=_. 21 若一棵二叉树的叶子数为n0,则该二叉树中左,右子树皆非空的结点个数为_. 22 设n0为哈夫曼树的叶子结点数目,则该哈夫曼树共有_个结点. 23 若以4,5,6,7,8作为叶子结点的权值构造哈夫曼树,则其带权路径长度是_. 24 如果结点A有3兄弟,而且B是A的双亲,则B的度为_. 25 高度为h的二叉树中叶子结点的数目至多为_. 26 具有n个结点的二叉树,采用二叉链表存储,共有_个空链域. 27 利用树的孩子兄弟表

32、示法存储,可以将一棵树转换成_. 28 二叉树的线索化实质是将二叉链表中的_改为_. 29 在一棵树中,_结点没有前驱结点,其余每个结点有且只有一个_,可以有任意多个_结点. 30 二叉树有不同的链式存储结构,其中最常用的是_与_. 31 对于一棵完全二叉树,设一个结点的编号为i,若它的左孩子结点存在,则其编号为_;若右孩子结点存在,则其编号为_;而双亲结点的编号为_. 32 对于一棵具有n个结点的二叉树,对应二叉链表中指针总数为_个,其中_个用于指向孩子结点,_个指针空闲者. 33 一棵左右子树均不空的二叉树在先序线索化后,其空指针域有_个. 34 用一维数组存放一棵完全二叉树:ABCDEF

33、GHIJKL,则后序遍历该二叉树的结点序列为_. 35 在图5.43的树中，结点H的祖先为_. 36 深度为k的完全二叉树,其前k-1层共有_个结点. 37 对任何二叉树,若度为2的结点数为n2,则叶子数n0=_. 38 具有n个结点的完全二叉树,若按层次从上到下,从左到右对其编号(根结点为1),则编号最大的分支结点序号是_,编号最小的分支结点序号是_. 39 结点最少的树是_,结点最少的二叉树是_. 40 若二叉树的一个叶子结点是某子树中根遍历序列中的第一个结点,则它必然是该子树后根遍历序列中的_个结点. 41二叉树通常有_存储结构和_存储结构. 42 具有n个结点互不相似的二叉树的数目为_

34、. 43 哈夫曼树是带权路径长度_的树,通常权值较大的结点离根_. 二 判断题 1 完全二叉树的某结点若无左孩子,则它必是叶结点. 2二叉树中,具有两个子女结点的中序后继结点最多只能有一个子女. 3 存在这样的二叉树,对它采用任何次序的遍历,结果相同. 4二叉树就是结点度为2的树. 5二叉树中不存在度大于2的结点,当某个结点只有一棵子树时无所谓左右之分. 6 任何一棵二叉树都可以不用栈实现前序线索树的前序遍历. 7 对任何二叉树的后序线索树进行后序遍历时都必须用栈. 8 一棵有n(n1)个结点的d叉树,若用多重链表表示,树中每个结点都有d个链域,则在树的nd个链域中,有n(d-1)+1个是空链

35、域,只有n-1个是非空链域. 9 一般来说,若深度为k的n个结点的二叉树具有最小路径长度,那麽从根结点到第k-1层具有最多的结点数为2k-1,余下的n-2k-1+1个结点在第k层的任一位置上. 10 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点. 11若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点,则它必是该子树的中序遍历序列中的最后一个结点. 12 已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个. 13 在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应作特殊

36、处理. 14 对n个结点的二叉树用递归程序进行中序遍历时,最坏情况下要附加n个辅助存储空间. 15 当k1时,高度为k的二叉树至多有2k-1个结点. 16 一棵含有n个结点的完全二叉树,它的高度是. 17 ( 101 , 88 , 46 , 70 , 34 , 39 , 45 , 58 , 66 , 10 )是堆. 18 将一棵树转换成二叉树后,根结点没有左子树. 19 用树的前序遍历和中序遍历可以导出数的后序遍历.20 即使对不含相同元素的同一输入序列进行两组不同的,合法的入栈和出栈组合操作,所得的输出序列也一定相同. 21 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近. 2

37、2 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列.23 将一棵树转换成二叉树后,根结点没有左子树. 24 用树的前序遍历和中序遍历可以导出树的后序遍历.25 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近. 26 在叶子数目和权值相同的所有二叉树中,最优二叉树一定是完全二叉树.27 后序遍历森林和中序遍历与该森林相对应的二叉树其结果不同. 28 若一个二叉树的树叶是某子树的中序遍历序列的第一个结点,则它必是该子树的后序遍历序列中的第一个结点. 29 不使用递归也能实现二叉树前序,中序和后序遍历. 30 对于后序线索二叉树要找它的任一结点的后继有时是很困难的,因此还需要使用

38、栈. 31 在二叉树中,具有一个子女的父结点,在中序遍历中,它没有后继子女结点. 32 中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点. 33前序遍历森林和前序遍历与该森林相对应的二叉树其结果不同. 34 二叉树中每个结点有两个子女,而对一般的树则无此限制,因此二叉树是树的特殊情形. 35 用一维数组存储二叉树时,总是以前序遍历顺序存储结点. 36 一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为n-1. 三 选择题 1 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足_. A) 所有的结点均无左孩子 B) 所有的结点均无右孩子 C)只有一个叶子结

39、点 D)是任意一棵二叉树 2 一棵完全二叉树上有1001个结点，其中叶子结点的个数是_. A) 250 B)500 C) 254 D) 505 E)以上答案都不对3 以上说法正确的是_.A) 若一个树叶是某二叉树前序遍历序列中的最后一个结点,则它必是该子树后序遍历序列中的最后一个结点B) 若一个树叶是某二叉树前序遍历序列中的最后一个结点,则它必是该子树中序遍历序列中的最后一个结点 C) 在二叉树中,具有两个子女的父结点,在中序遍历序列中,它的后继结点最多只能有一个子女结点D) 在二叉树中,具有两个子女的父结点,在中序遍历序列中,它没有后继子女结点 4 以下说法错误的是_. A) 哈夫曼树是带权

40、路径长度最短的树,路径上权值较大的结点离根较近. B) 若一个二叉树的树叶是某子树的中序遍历序列的第一个结点,则它必是该子树的后序遍历序列中的第一个结点. C) 已知二叉树的前序遍历序列和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个. D) 在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的. 5 二叉树在线索化后,仍不能有效求解的问题是_. A) 前(先)序线索二叉树中求前(先)序后继 B) 中序线索二叉树中求中序后继C) 中序线索二叉树中求中序前驱 D) 后序线索二叉树中求后序后继6 任何一棵二叉树的叶结点在前(先)序,中序和后序遍历序列中的相对

41、次序_. A) 不发生变化 B) 发生变化 C)不能确定7 设A,B为一棵二叉树上的两个结点.在中序遍历时,A在B前面的条件是_.A) A在B的后方 B) A在B的左方 C) A是B的祖先 D) A是B的子孙 8 在一棵具有个结点的完全二叉树中，树枝结点的最大编号为_. A) B) C) D) 9 在N个结点的线索二叉树中，线索的数目为_. A)N-1 B)N C)N+1 D)2N 10 设深度为K的二叉树上只有度为0和度为2的结点,则这类二叉树上所含有的结点总数为_. A) K+1 B)2K C)2K-1 D)2K+1 11 设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有_个结点.

42、A)13 B)12 C) 26 D) 2512下面4 棵二叉树,都有4个叶子结点a,b,c,d,分别带权7,5,2,4,其中是哈夫曼树的是_. D5274dacbC25abcd74B7542dabcbcda7524A 13 下面几个符号串编码集合中,不是前缀编码的是_.A) 0 , 10 , 110 , 1111 B) 11 , 10 , 001 , 101 , 0001 C) 00 , 010 , 0110 , 1110 D) B , C , AA , AC , ABA , ABB , ABC 14 以下说法错误的是_.A) 存在这样的二叉树,对它采用任何次序遍历其结点访问序列均相同 B)

43、二叉树是树的特殊情形 C) 由树转换成二叉树,其根结点的右子树总是空的 D) 在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 15 如果T2是由有序树T转换而来的二叉树,那麽T中结点的后序就是T2中结点的_. A) 先序 B) 中序 C) 后序 D) 层次序 16 树的基本遍历策略可分为先根遍历和后根遍历; 二叉树的基本遍历策略可分为前序,中序和后序三种遍历.我们把由树转化得到的二叉树称该树对应二叉树,则下面是_正确的. A) 树的先根遍历序列与其对应的二叉树先序遍历序列相同 B) 树的后根遍历序列与其对应的二叉树后序遍历序列相同 C) 树的先根遍历序列与其对应的二叉树中序遍

44、历序列相同 D) 以上都不对 17 设F是一森林,B是由F变换得到的二叉树.若F中有N个非终端结点,则B中右指针域为空的结点有_个. A) N-1 B) N C) N+1 D) N+2 18 一棵有N个结点的二叉树,按层次从上到下,同一层从左到右的顺序存储在一维数组A1.N中, 则二叉树中第I个结点(I从1开始用上述方法编号)的右孩子在数组A中的位置是_. A) A 2I (2IN) B)A 2I+1 (2I+1N) C) A I/2 D) 条件不充分,无法确定 19 将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度是_. A) 4 B) 5 C) 6 D) 720 设树

45、T的高度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1,T中的叶子数为_. A) 5 B) 6 C) 7 D) 8 21 下列有关二叉树的说法正确的是_. A)二叉树的度为2 B)一棵二叉树度可以小于2 C)二叉树中至少有一个结点的度为2 D)二叉树中任一个结点的度都为2 22 某二叉树中序列为a b c d e f g ,后序序列为b d c a f g e ,则前序序列是_. A) e g f a c b d B) e a c b d g f C) e a g c f b d D)上面的都不对 20309510561350图5.44 二叉树23 设森林F对应的二叉树为B,它有M个结点,B的根为P,P的右子树结点个数为N,森林F中第一棵树的结点个数是_. A) M-N B)M-N-1 C)N+1 D)条件