数据结构课堂练习WORD版.doc

综合练习一设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ ）。A) a，b，c，e，d B) b，c，a，e，d C) a，e，c，b，d D) d，c，e，b，a一.单选题1. 数据的逻辑结构可以分为_。A) 静态结构和动态结构 B) 物理结构和存储结构C) 线性结构和非线性结构 D) 虚拟结构和抽象结构一.单选题2. 顺序存储方式的优点是_。A) 存储密度大B) 插入、删除运算方便C) 可进行动态存储分配D) 可方便地用于各种逻辑结构的存储表示一.单选题3. 下面关于线性表的叙述中，错误的是 _。A) 线性表采用顺序存储，必须占用一片连续的存储单元B) 线性表采用顺序存储，便于进行插入和删除操作C) 线性表采用链接存储，不必占用一片连续的存储单元D) 线性表采用链接存储，可以动态分配存储空间一.单选题4. 用数组存储线性表的优点是_。A) 便于插入和删除操作 B) 便于随机存取C) 可以方便地改变表的长度D) 不需要占用一片连续的存储空间一.单选题5. 线性表中各元素之间呈_关系。A) 层次B) 网状 C) 有序 D) 集合一.单选题6. 一维数组和线性表的区别是_。A) 前者长度固定，后者长度可变 B) 后者长度固定，前者长度可变C) 两者长度均固定 D) 两者长度均可变一.单选题7.单链表L中，P所指结点为尾结点的条件为 _ 。A) PL B) P-next=NULLC) P.next:L D) Pnil一.单选题8.与数据元素本身的形式、内容、相对位置及个数无关的是数据的 _ 。A) 存储结构B) 存储实现 C) 逻辑结构D) 运算实现一.单选题9.单链表中，增加头结点的目的是 _ 。A) 使单链表至少有一个结点B) 表示单链表中首结点的位置C) 方便运算的实现 D) 说明单链表是线性表的链式存储结构一.单选题10. 数据结构是一门研究非数值计算的程序设计问题中计算机的_以及它们之间的关系和运算等的学科。 A）操作对象 B）计算方法 C）逻辑存储 D）数据映像一.单选题11.算法分析的目的是_。 A）找出数据结构的合理性 B）分析算法的效率以求改进 C）研究算法中的输入和输出的关系 D）分析算法的易懂性和文档性一.单选题12.在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为_。A）n-i+1 B）n - i C）i D）i-1一.单选题13. 不带头结点的单链表 head为空的判断条件为_。 A）head =Null B） head -next = Null C） head -next = head D） head ! = Null 一.单选题14. 数据结构被形式地定义为(D，S)，其中D是数据元素的有限集合，S是D上_的有限结合。A）操作 B）关系 C）存储D）映像一.单选题15.线性结构的顺序存储结构是一种 的存储结构。A）随机存取B）顺序存取C）索引存取D）散列存取一.单选题16.组成数据的基本单位是_。 A）数据项B）数据类型C）数据元素D）数据变量一.单选题17. 双循环链表的*p结点之后插入*s结点的操作是 A）p-next=s，s-prior=p，p-next-prior=s，s-next=p-next；B）p-next=s，p-next-prior=s，s-prior=p，s-next=p-next；C）s-prior=p，s-next=p-next，p-next=s，p-next-prior=s；D）s-prior=p，s-next=p-next，p-next-prior=s，p-next=s；一.单选题18.一维数组和线性表的共同点是 。两者都是相同类型数据的集合两者都允许不同类型数据共存两者长度均固定两者长度均可变一.单选题19. 线性链表中各链接结点之间的地址_。A）连续与否都可以 B）必须连续C）一定不连续D）部分地址必须连续一.单选题20. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 。A）单链表B）用头指针表示的单循环链表 C）用带尾指针表示的单循环链表D）顺序表二.多选题1. 下列关于链式存储结构的叙述中，正确的是_。 A) 结点除自身信息外还包括指针域，因此存储密度小于 顺序存储结构 B) 可以通过计算直接确定第i个结点的存储地址 C) 逻辑上相邻的结点物理上不必相邻 D) 插入、删除操作方便，不必移动结点ACD二.多选题2. 下面的叙述正确的是_。(06)A）线性表在链式存储时，查找第i个元素的时间同i的值成正比B）线性表在链式存储时，查找第i个元素的时间同i的值无关C）线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D）线性表在顺序存储时，查找第i个元素的时间同i的值无关AD二.多选题3. 链表具有的特点是_。A）插入、删除不需要移动元素B）不必事先估计存储空间C）可随机访问任一元素D）所需空间与链表长度成正比ABD二.多选题4. 下列关于链式存储结构的叙述中，正确的是_。A) 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B) 可以通过计算可以直接确定第i个结点的存储地址C) 逻辑上相邻的结点物理上必须相邻D) 插入、删除操作方便，不必移动结点AD二.多选题5. 数据元素之间的关系在计算机中的表示方法有_。 A）顺序映像 B）线性结构 C）非线性结构D) 非顺序映像AD三、判断题1. 数据结构中与所使用的计算机无关的是数据的逻辑结构。2. 线性表是一个有序序列，其中可包含相同的元素，也允许各个元素可以是不同的数据类型。3. 链表的每个结点都含有两个指针。4.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个后继。5.线性表中各元素类型必须是相同的。 6.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上。 7.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。正确 1 5 6 7四、填空题1. 数据结构包括的三个方面的内容是 、 和 。2. 通常衡量算法效率的一般标准为 和 。3. 算法是对特定问题求解步骤的一种描述，它具有有穷性、确定性、可行性、_及一个或多个输出等重要特征。4. 数据结构是相互之间存在一种或多种关系的_集合。5. 线性结构中元素的关系是_的关系。 答案：1 逻辑结构、存储结构、运算 2 时间复杂度、空间复杂度 3 具有零个或多个输入 4 数据元素 5 一对一四、填空题6. 用一维数组表示线性表L=(a1,a2,an)，假定删除表中任一元素的概率相同（都为1/n），则删除一个元素平均需移动的元素个数为_ 。(n-1)/2 7.当线性表采用顺序存储结构进行存储时，其主要特点是 _ 。逻辑结构相邻的结点存储结构也相邻8.链式存储结构最显著的优点是 _。 方便插入、删除操作四、填空题9.单循环链表的最显著的优点是 _ 。答：从任意结点出发都可以访问链表中的每个元素10.一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是_ 。答：110五、简答题1解释数据结构、逻辑结构、存储结构的概念，并讨论他们之间的关系；参考答案：数据结构：相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构：逻辑结构描述数据之间的逻辑关系。包括集合、线性、树形和网状结构。存储结构：数据结构在计算机中的表示称存储结构。包括顺序、索引、链式和散列。三者关系：在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构。五、简答题2线性表的顺序存储具有如下缺点：(1).在进行插入或删除操作时，需要移动大量元素；(2).由于难以估计其大小，必须预先分配较大的存储空间，往往使存储空间得不到充分利用；(3).表的容量难以扩充。试问线性表的链式存储结构是否一定能克服上述缺点？试做简要讨论。参考答案：链式存储结构一般克服的顺序结构的三个弱点： 首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为O(1)；其二，不需要预先分配存储空间，可根据需要动态申请；其三，表容量只受内存空间的限制；缺点：因指针增加了内存空间开销，当空间不允许时，就不能克服顺序存储的优点。六、编程题1已知两个带头结点的单链表La和Lb中的元素按非递减顺序排列，试用C语言编写一个函数将这两个有序表合并成一个有序单链表保存在La中，而不改变其排序性。设带头结点的单链表的结点结构说明及函数名如下：typedef struct node /*定义结点结构*/ datatype data; struct node next; lklist;typedef struct node *pointer;函数首部为：pointer mergelklist(lklist ha,lklist hb)1题参考答案pointer mergelklist(lklist ha,lklist hb) pointer *h, *pa, *pb ; pa=ha-next, pb=hb-next； h= r = ha； while(pa & pb) If(pa-data data) /*移动ha, hb头指针, 修改r指向 r-next =pa; r=pa; pa= pa-next ； else r-next =pb; r=pb; pb= pb-next ； if(pa=NULL) r-next=pb; if(pb=NULL) r-next=pa; return h； 六、编程题2 设计算法求两个递增有序的顺序表L1和L2中的公共元素，并将其置入顺序表L3中，用C语言实现。设顺序表存储结构说明如下：typedef struct ElemType *elem; Int length ;sqlist;sqlist L1,L2,L3;函数首部为： status complist(sqlist L1, sqlist L2, sqlist L3)2题参考答案status complist(sqlist L1, sqlist L2, sqlist L3) i1=0,i2=0,i3=0; L3.length=0; while(i1=L1.length-1)& (i2=L2.length-1) if(L1.elemi1 L2.elemi2) i2=i2+1; if(L1.elemi1 = L2.elemi2) L3.elemi3= L1.elemi1; i3=i3+1; i1=i1+1; i2=i2+1; L3.length=i3; 综合练习二一.单选题1. 字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成_个不同的字符串。A) 5 B) 4C) 6D) 1一.单选题2. 栈和队列都是 。A) 顺序存储的线性结构 B) 链式存储的非线性结构C) 限制存取点的线性结构 D) 限制存取点的非线性结构一.单选题3. 设有x，y，z三个元素顺序进栈，在进栈过程可以出栈，不可能出现的出栈序列为 。A) xyz B) yzx C) zxy D) zyx一.单选题4. 设一环形队列用一维数组Am表示，队头和队尾的指针分别为front和tail，则入队时判定队列满的条件是_。A) front=tailB) front=tail+1C) front=(tail+1) % mD) front=tail % m一.单选题5. 单链表L中，P所指结点为尾结点的条件为 _ 。A) PL B) P-next=NULLC) P.next:L D) Pnil一.单选题6.借助栈输入A、B、C三个元素，则不可能的输出序列是 _。A) ABCB) CAB C) CBA D) BAC一.单选题7. 设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的条件是_。 A）S-top!=0 B）S-top=0 C）S-top!=m-1 D）S-top=m-1一.单选题8. 在一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除的结点，则执行的操作是_。P47图3.3 A）x= HS, HS = HS -next ; B）x= HS -data ; C）x= HS -data , HS = HS -next ; D）HS = HS -next , x= HS -data ; 一.单选题9.设用一维数组An存储一个栈，令A0为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一个元素时，变量T的变化为_。A) T=T+1 B) T=T-1C) T不变D) T=n一.单选题10.设用一维数组An存储一个栈，令An-1为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一个元素时，变量T的变化为_。A) T=T+1 B) T=T-1C) T不变D) T=n一.单选题11.和顺序栈相比，链栈有一个明显的优势是_。A）通常不会出现栈空的现象B）通常不会出现栈满的现象C）插入操作更容易实现D）删除操作更容易实现一.单选题12.循环队列用数组Am存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是_。P64A）(rear-front+m)%mB）rear-front+1C）rear-front-1D）rear-front一.单选题13.在一个链队中，若front和rear分别为队头、队尾指针，则所插入s所指结点操作为_。A）front-next=s，front=s；B）rear-next=s，rear=s；C）s-next=rear，rear=s；D）s-next=front，front=s；一.单选题14.栈和队列的共同点是_。A）都是先进后出B）都是先进先出C）只允许在端点处插入和删除元素D）没有共同点一.单选题15.设数组0.m作为循环链队列lq的存储空间，若front和rear分别为队头、队尾指针，则入队时修改指针的语句是_。A）lq.front=(lq.front+1)%mB）lq.front=(lq.front+1)%(m+1)C）lq.rear=(lq.rear+1)%mD）lq.rear=(lq.rear+1)%(m+1)二.多选题1. 栈的基本运算包括_。 A) 删除栈底元素 B) 将栈置为空栈 C) 判断栈是否为空 D) 删除栈顶元素BCD二.多选题2. 队列的基本运算包括_。 A) 从队尾插入一个新元素 B) 判断一个队列是否为空 C) 从队列中删除第i个元素 D) 读取队头元素的值ABD二.多选题3. 从逻辑上讲，下列属于线性结构的是_。A) 队列 B) 栈 C) 线索二叉树 D) 线性表 ABD二.多选题4. 下列术语与为数据结构的是_。A) 栈 B) 队列C) 散列表 D) 串ABD二.多选题5.以下说法错误的是 。A）因链栈本身没有容量限制，故在用户内存空间范围内不会出现栈满情况B）因顺序栈本身没有容量限制，故在用户内存空间范围内不会出现栈满情况C）对链栈而言，在栈满情况下，如果再入栈操作，则会发生“上溢”D）对顺序栈而言，在栈满情况下，如果再入栈操作，则会发生“下溢”BCD三、判断题1. 栈和队列既可采用顺序存储方式，也可采用链接存储方式。2. 队列是允许在队头一端进行插入，在队尾一端进行删除操作的线性表。3. 链栈的每个结点都含有两个指针。4.顺序队列和循环队列的队空和队满判断条件是不一样的。 5.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。正确 1 4 5 四、填空题1. 队列和栈都是线性表。在栈中， 称为栈顶，栈操作的原则是 ；队列操作的原则是_。2.假设以S和X分别表示进栈和出栈操作，若对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_。 3.设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少应为_。 答：1. 表尾(允许操作的一端)、后进先出、先进先出 2. bceda 3. 3四、填空题4. 设栈S的初始状态为空，队列Q的初始状态为 a1 a2 a3 a4 队头 队尾对栈S和队列Q进行如下两步操作：(1) Q中的元素依次出队，并压入栈S中，直至Q为空；(2) 依次弹出S中的元素并进入Q，直至S为空。在上述两步操作后，队列Q的状态是 。答：a4a3a2a1四、填空题5. 具有n个单元的循环队列中，队满时共有 _个元素。6.通常程序在调用另一个程序时，都需要使用一个_来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。7. 定义一维数组，int Am+1；作为循环队列的存储空间，front为队头指针，rear为队尾指针，则元素x执行入队操作的语句是_。8.设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的条件是_ 。答： 5. n-1 6. 栈 7. rear=(rear+1)%(m+1) , Arear=x 8. S-top = m-1 四、填空题9.假设以S和X分别表示进栈和出栈操作，若对输入序列1,2,3,4,5进行一系列栈操作SSSXXSXSXX之后，得到的输出序列为 。 答： 3245110. 设有一个顺序栈S，元素a，b，c，d，e，f依次进栈，如果6个元素的出栈顺序为b，c，d，f，e，a，则顺序栈的容量至少应为。答： 3五、简答题1如图所示，在栈的输入端有6个元素，输入顺序为A、B、C、D、E、F。能否在栈的输出端得到序列ACEDFB及EDFCAB？若能，写出对栈的操作过程（用push表示进栈，pop表示退栈）；若不能，简述其理由。PUSH(S,A)A元素进栈POP(S) 栈顶元素出栈五、简答题1参考答案：可以产生ACEDFB， ACEDFB进栈过程：PUSH(S,A) ，POP(S)，PUSH(S,B) ，PUSH(S,C) ，POP(S)，PUSH(S,D)，PUSH(S,E)，POP(S)，POP(S)，PUSH(S,F) ，POP(S)，POP(S)不能产生EDFCAB，原因：不能产生EDFCAB原因：栈是一种特殊的线性表，其操作原则“先进后出”或“后进先出”。在进栈系列ABCDEF中，B比A后进栈，在出栈时应比A先出栈，故不可以得到EDFCAB系列。 六、编程题写一个算法，借助栈将一个单链表(带有头结点)置逆；给定函数如下，Iin_stack(S)，初始化栈；Pop_stack(S,p),入栈； Push_stack(S,P)，出栈； Enmpty_stack(S)，栈空。单链表的结点结构说明及函数名如下：typedef struct node /*定义结点结构*/ datatype data; struct node *next; LinkNode， *lklist;函数首部为：Lklist Re_Linklist (lklist L)1题参考答案 Lklist Re_Linklist (lklist L) Linknode *p, *q, *r ; p=L-next, r = L, L-next=NULL； Iin_stack(S) while(p) Push_stack(S,P)； P=P-next； while(！Enmpty_stack(S) Pop_stack(S,q)； r-next =q；r=q； r-next =NULL； return L； 综合练习三一.单选题1. 设用一维数组An存储一个栈，令An-1为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当从栈中弹出一个元素时，变量T的变化为_。A) T=T+1 B) T=T-1 C) T不变D) T=n-1答案：A 一.单选题2. 下列关于串的叙述中，不正确的是_。A) 串是字符的有限序列B) 空串是由空格构成的串C) 模式匹配是串的一种重要运算D) 串既可以采用顺序存储，也可以采用链式存储答案：B一.单选题3. 设有数组A810，每个元素Aij的长度为3个字节，行下标i从0到7，列下标j从0到9，该数组从首地址1000开始连续存储，需要占用的存储空间为_【1】_个存储单元。如果数组按行存放，元素A74的起始地址为_【2】_；如果数组按列存放，元素A47的起始地址为_【3】_【1】A) 80 B) 100 C) 240 D) 270【2】A) 1141 B) 1144 C) 1222 D) 1225【3】A) 1222 B) 1117 C) 1180 D) 1225答案： 【1】C 【2】C 【3】C 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 1920 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3940 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 5960 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79一.单选题4. 以下关于广义表的叙述中，正确的是_。A) 广义表是0个或多个单元素或子表组成的有限序列B) 广义表至少有一个元素是子表C) 广义表不可以是自身的子表D) 广义表不能为空表答案：A一.单选题5.广义表(a, b), c, d )的表头是 _ ，表尾是_ 。A) a B) d C) (a, b) D) (c ,d)答案：C、 D6. .广义表(a, b, c, d )的表头是 _ ，表尾是_ 。A) a B) (a, b,c,d) C) (a, b,c,d) D) ( ) 答案：C、D一.单选题7. 稀疏矩阵一般是指 _。 A) 非零元素和零元素都非常少B) 非零元素较多 C) 零元素较多D) 非零元素和零元素都较多答案：C一.单选题8.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为（）。 A）SA+141 B）SA+180 C）SA+222 D）SA+225答案：B一.单选题9.已知广义表LS( (a,b,c),d,e,f ),运用head和tail函数取出LS中原子e的运算是_。A）head(tail(LS) B）tail(head(LS)C）head(tail(tail(LS) D) head(tail(tail(head(LS)答案：C一.单选题10. 有一个10090的稀疏矩阵，非0元素有10个，数据元素为整型数据，设每个整型数据占2个字节，则用三元组表示该矩阵时，所需字节数是_。A）60B）66C）18000D）16答案： B 二.多选题1. 下面说法中，错误的是_。P108 A）广义表的表头总是一个广义表 B）广义表的表尾总是一个广义表 C）广义表可以用顺序存储结构 D）广义表可以是一个多层次的结构 答案：AC二.多选题2. 串常用机内表示方法有_。P73 A）串的定长顺序存储表示 B）串的块链存储表示 C）串的堆分配存储表示 D）串的十字链表表示答案：ABC二.多选题3. 在串的块链存储表示法中，影响串处理效率的因素是_。 A）串的结点的大小 B）存储空间的大小 C）存储密度 的大小 D）串的字符集 答案：ABCD二.多选题4. 稀疏矩阵的压缩存储方法包括_。P98 A）三元组表示法 B）十字链表法 C）孩子兄弟表示法 D）堆分配存储表示法答案：AB二.多选题5.下面关于串存储表示方法正确的是_。A）定长顺序存储表示B）块链存储表示 C）十字链表表示D）矩阵存储表示答案：AB三、判断题1. 数组和广义表可以看成线性表的扩展，即表中的元素本身也是一个数据结构。参考答案 ： 正确 2. 若采用三元组压缩存储技术存储稀疏矩阵,只要把每个元素的行下标和列标互换, 就完成了该矩阵的转置。P98参考答案 ： 错误四、填空题1.空字符串是 _ ，其长度为_ 。参考答案 ： 零个字符的串 ， 02. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、列号和 _。参考答案：元素值3.经常对数组进行的两种操作是_ 。参考答案：存取和修改四、填空题4. 设有两个串P和Q，求Q在P中的首次出现的位置的操作称为_。答案：模式匹配5. 有如下定义：char s130=“Stocktom,CA”， char s230=“March,5,2000”，则调用函数strCmp(s1,s2)的返回值是_；调用函数strlen(strcat(s1,s2)的返回值是_。答案：正数 (6)， 23综合练习四一.单选题1. 设二叉树的第1层为根结点，则第i层最多有 【1】 个结点，深度为k的二叉树最多有 【2】 个结点。对任一棵二叉树T，如果其叶结点数为n0，度数为1的结点数为n1，度数为2的结点数为n2，则n0=_【3】_。【1】A) 2i B) 2i-1 C) 2i-1 D) 2i+1【2】A) 2k-1 B) 2k-1 C) 2k+1 D) 2k【3】A) n2+1 B) n1+1 C) n+1 D) n1+n2参考答案： 【1】 C 2】 B 【3】 A 一.单选题2. 在一棵二叉树中，若一个结点是叶结点，则它没有_。 A) 左子结点 B) 右子结点 C) 左子结点和右子结点 D) 左子结点、右子结点和兄弟结点答案：C一.单选题3. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶结点的先后顺序_。 A) 都不相同 B) 完全相同 C) 先序和中序相同，而与后序不同 D) 中序和后序相同，而与先序不同答案 B一.单选题4. 由3个结点可以构造出_种不同的二叉树。 A) 2 B) 3 C) 4 D) 5D5. 带权路径长度最短的二叉树称为_。 A) 赫夫曼树 B) 诺伊曼树 C) 线索二叉树 D) B+树A一.单选题6.树结构最适合用来表示 _ 。 A) 元素间具有分支、层次关系的数据 B) 有序数据 C) 元素间没有关联的数据 D) 无序数据A一.单选题7. 深度为k的二叉树所含叶子的个数最多为 _。 A) 2k -1 B) 2k-1 C) k D) 2k参考答案：B8.设有一棵n个叶结点的哈夫曼树，其树中总结点数是_ 。 A) 2n-1 B) n(n+1) C) n D) n-1参考答案： A 9.具有10个叶结点的二叉树中有_个度为2的结点。P124 A）8 B）9 C）10 D）ll参考答案： B一.单选题10.一个具有1025个结点的二叉树的高h为_。P124 A）11 B）10 C）11至1025之间 D）10至1024之间参考答案： C11. 在线索二叉树中，t 所指结点没有左子树的必要条件是 _。P132 A) t-left =NULL B) t-ltag =1 且 t-left =NULL C) t-ltag =1 D) 以上都不对参考答案： C一.单选题12. 由权值3，8，6，5，2 的叶子结点生成一棵赫夫曼树，它的带权路径长度为_。 A) 48 B) 72 C) 53 D) 24一.单选题13. 已知某二叉树 的后序遍历是dabec，中序序列是debac，则它的先序序列是_。 A) acbed B) deabc C) decab D) cedba一.单选题14. 线索二叉树 是一种_结构。 A) 逻辑 B) 存储 C) 线性存储 D) 逻辑存储B15. 深度为5的二叉树 最多有_结点。 A) 32 B) 31 C) 16 D) 10B二.多选题1. 下列关于哈夫曼树的叙述中，正确的是_。 A) 哈夫曼树是一棵二叉树，因此，它的结点的度可以是0、1或2 B) 具有n个权值的哈夫曼树共有2n-1个结点 C) 哈夫曼树根结点的权值等于所有叶结点的权值之和 D) 具有n个权值的哈夫曼树含有n-1个非叶结点参考答案：B C D二.多选题2.下面的说法中，正确的是_。 A）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变 B）按二叉树定义，具有三个结点的二叉树共有6种 C）用二叉树的前序遍历和中序遍历可以导出该树的后序遍历 D）完全二叉树一定存在度为1的结点参考答案：A C二.多选题3.在下述结论中，正确的是_。 A）只有一个结点的二叉树的度为0 B）二叉树的度为2 C）深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 D）二叉树的左右子树可任意交换;参考答案：A C二.多选题4. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是错误的是_。A）500B）254C）505D）以上答案都不对参考答案：ABC(最大层有490=1001-511个结点，次最大层有11=511-1001/2)个结点) 二.多选题5.关于二叉树，下面说法正确的是_。p124A）完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B）在三叉链表上，二叉树的求双亲操作很容易实现C）在二叉链表上，求根以及左、右孩子等操作很容易实现D）在二叉链表上，求双亲的时间性能很好参考答案：ABC三、判断题1. 用二叉链表存储有n个结点的二叉树，结点的2n个指针中，只利用了n-1个指针，其余n+1个是空指针。P1262. 树是一种线性数据结构。3. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点。正确 ：四、填空题1. 假设二叉树的第1层为根结点，则具有n个结点的二叉树的最大高度是 _。答案：n 2. 带权结点A、B、C、D的权值分别为8、6、1、5，则B结点的哈夫曼编码（二进制）为 。 (权值小的叶结点为左子树) 答案：1 0 四、填空题3. 设森林F由n棵树组成，它的第一棵树，第二棵树，第n棵树分别有t1，t2，tn个结点，则与森林F对应的二叉树中，根结点的左子树有 个结点。答案：t1-1(t1为根节点的二叉树节点数减一个根节点) 四、填空题4. 在树中，一个结点的直接子结点的个数称为该结点的 。答案：度5. 已知完全二叉树的第七层有10个结点，则整个二叉树有 _ 个结点。答案：73 （26-1 + 10）6. 若叶结点A只有三个兄弟(不包括A本身),并且B是A的双亲结点,则B的度是 _。答案： 四、填空题7. 将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组b51中，并从b1开始存放，这棵二叉树最下面一层上最左边一个结点存储在数组元素 中。答案：b328. 假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。P124 答案: 5 18 四、填空题9. 对于具有30个结点的完全二叉树，若一个结点的编号为5，则它的左孩子的编号为_，右孩子的结点为_ ，双亲结点结点的编号为 _ 。124参考答案：10 11 2 四、填空题10.设森林中有4棵树，结点个数分别为n1、n2、n3、n4，当把森林转换成一棵二叉树后，根结点的右子树上有_结点。参考答案： n2+n3+n4 五、简答题1简要回答树和二叉树之间有什么区别和联系。 参考答案：区别：.对子树要求不同，二叉树任一结点都有两棵子树，且两棵子树之间有次序关系。.二叉树即使一结点只有一棵非空子树，仍需区别是左子树还是右子树。.二叉树上任一结点的度定义为该结点的孩子数，树的度定义为结点拥有子树的数目。二叉树与树有相似之处，但并非树的特例，属两种不同的数据结构。联系：逻辑结构相同，都是树形结构。五、简答题2.已知一棵二叉树如下，请分别写出按先序、中