数据结构商大习题

1、一.单选题 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（ B）。A) a，b，c，e，d B) b，c，a，e，d C) a，e，c，b，d D) d，c，e，b，a1. 数据的逻辑结构可以分为_C_。A) 静态结构和动态结构 B) 物理结构和存储结构C) 线性结构和非线性结构 D) 虚拟结构和抽象结构2. 顺序存储方式的优点是_A_。A) 存储密度大 B) 插入、删除运算方便C) 可进行动态存储分配 D) 可方便地用于各种逻辑结构的存储表示3. 下面关于线性表的叙述中，错误的是 _B_。A) 线性表采用顺序存储，必须占用一片连续的存储单元B)

2、线性表采用顺序存储，便于进行插入和删除操作C) 线性表采用链接存储，不必占用一片连续的存储单元D) 线性表采用链接存储，可以动态分配存储空间4. 用数组存储线性表的优点是_B_。A) 便于插入和删除操作 B) 便于随机存取C) 可以方便地改变表的长度 D) 不需要占用一片连续的存储空间5. 线性表中各元素之间呈_C_关系。A) 层次 B) 网状 C) 有序 D) 集合6. 一维数组和线性表的区别是_A_。A) 前者长度固定，后者长度可变 B) 后者长度固定，前者长度可变C) 两者长度均固定 D) 两者长度均可变7.单链表L中，P所指结点为尾结点的条件为 _B_ 。A) PL B) P->

3、next=NULLC) P.next:L D) Pnil8.与数据元素本身的形式、内容、相对位置及个数无关的是数据的 _C_ 。A) 存储结构 B) 存储实现 C) 逻辑结构 D) 运算实现9.单链表中，增加头结点的目的是 _C_ 。A) 使单链表至少有一个结点B) 表示单链表中首结点的位置C) 方便运算的实现D) 说明单链表是线性表的链式存储结构一.单选题10. 数据结构是一门研究非数值计算的程序设计问题中计算机的_A_以及它们之间的关系和运算等的学科。 A）操作对象 B）计算方法 C）逻辑存储 D）数据映像11.算法分析的目的是_B_。 A）找出数据结构的合理 B）分析算法的效率以求改进C

4、）研究算法中的输入和输出的关系 D）分析算法的易懂性和文档性12.在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为_A_。A）n-i+1 B）n - i C) i D）i-113. 不带头结点的单链表 head为空的判断条件为_A_。 A）head =Null B） head ->next = Null C） head ->next = head D） head ! = Null 14. 数据结构被形式地定义为(D，S)，其中D是数据元素的有限集合，S是D上_B_的有限结合。A）操作 B）关系 C）存储 D）映像15.线性结构的顺序存储结构是一种 A 的

5、存储结构。A）随机存取 B）顺序存取 C）索引存取 D）散列存取16.组成数据的基本单位是_C_。 A）数据项 B）数据类型 C）数据元素 D）数据变量17. 双循环链表的*p结点之后插入*s结点的操作是 ( D )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->

6、next=s，p->next->prior=s；D）s->prior=p，s->next=p->next，p->next->prior=s，p->next=s；18.一维数组和线性表的共同点是 A 。A两者都是相同类型数据的集合 B两者都允许不同类型数据共存C两者长度均固定 D两者长度均可变19. 线性链表中各链接结点之间的地址_A_。A）连续与否都可以 B）必须连续C）一定不连续 D）部分地址必须连续 20. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 C 。A）单链表 B）用头指针表示的单循环链表 C）用带尾指针表示的单循

7、环链表 D）顺序表二.多选题1. 下列关于链式存储结构的叙述中，正确的是 ( ACD ) A) 结点除自身信息外还包括指针域，因此存储密度小于 顺序存储结构 B) 可以通过计算直接确定第i个结点的存储地址 C) 逻辑上相邻的结点物理上不必相邻 D) 插入、删除操作方便，不必移动结点2. 下面的叙述正确的是_AD_。(06)A）线性表在链式存储时，查找第i个元素的时间同i的值成正比B）线性表在链式存储时，查找第i个元素的时间同i的值无关C）线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D）线性表在顺序存储时，查找第i个元素的时间同i的值无关3. 链表具有的特点是_ABD_。A）插入、删

8、除不需要移动元素B）不必事先估计存储空间C）可随机访问任一元素D）所需空间与链表长度成正比4. 下列关于链式存储结构的叙述中，正确的是_AD_。A) 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B) 可以通过计算可以直接确定第i个结点的存储地址C) 逻辑上相邻的结点物理上必须相邻D) 插入、删除操作方便，不必移动结点5. 数据元素之间的关系在计算机中的表示方法有_AD_。 A）顺序映像 B）线性结构 C）非线性结构 D) 非顺序映像三、判断题1. 数据结构中与所使用的计算机无关的是数据的逻辑结构。2. 线性表是一个有序序列，其中可包含相同的元素，也允许各个元素可以是不同的数据类型

9、。3. 链表的每个结点都含有两个指针。4.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个后继。5.线性表中各元素类型必须是相同的。 6.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上。 7.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。正确 1 5 6 7四、填空题1. 数据结构包括的三个方面的内容是 、 和 。2. 通常衡量算法效率的一般标准为 和 。3. 算法是对特定问题求解步骤的一种描述，它具有有穷性、确定性、可行性、_及一个或多个输出等重要特征。4. 数据结构是相互之间存在一种或多种关系的_集合。5. 线性结构中元素的关系是_的关系。 答案：1 逻辑结构、存储结构

10、、运算 2 时间复杂度、空间复杂度 3 具有零个或多个输入 4 数据元素 5 一对一6. 用一维数组表示线性表L=(a1,a2,an)，假定删除表中任一元素的概率相同（都为1/n），则删除一个元素平均需移动的元素个数为_ 。(n-1)/2 7.当线性表采用顺序存储结构进行存储时，其主要特点是_ 。逻辑结构相邻的结点存储结构也相邻8.链式存储结构最显著的优点是 _。 方便插入、删除操作9.单循环链表的最显著的优点是 _ 。答：从任意结点出发都可以访问链表中的每个元素10.一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是_ 。答：110五、简答题1解释数据结构、逻辑

11、结构、存储结构的概念，并讨论他们之间的关系；参考答案：数据结构：相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构：逻辑结构描述数据之间的逻辑关系。包括集合、线性、树形和网状结构。存储结构：数据结构在计算机中的表示称存储结构。包括顺序、索引、链式和散列。三者关系：在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构。五、简答题2线性表的顺序存储具有如下缺点：(1).在进行插入或删除操作时，需要移动大量元素；(2).由于难以估计其大小，必须预先分配较大的存储空间，往往使

12、存储空间得不到充分利用；(3).表的容量难以扩充。试问线性表的链式存储结构是否一定能克服上述缺点？试做简要讨论。参考答案：链式存储结构一般克服的顺序结构的三个弱点： 首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为O(1)；其二，不需要预先分配存储空间，可根据需要动态申请；其三，表容量只受内存空间的限制；缺点：因指针增加了内存空间开销，当空间不允许时，就不能克服顺序存储的优点。六、编程题1已知两个带头结点的单链表La和Lb中的元素按非递减顺序排列，试用C语言编写一个函数将这两个有序表合并成一个有序单链表保存在La中，而不改变其排序性。设带头结点的单链表的结点结构说明及函数

13、名如下：Ø 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

14、&& pb) If(pa->data <= pb->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

15、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) i1=i

16、1+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_个不同的字符串。A) 5 B) 4 C) 6 D) 12. 栈和队列都是 C 。A) 顺序存储的线性结构 B) 链式存储的非线性结构C) 限制存取点的线性结构 D) 限制存取点的非线性结构3. 设有x，y，z三个元素顺序进栈，在进栈过程可以

17、出栈，不可能出现的出栈序列为 C 。A) xyz B) yzx C) zxy D) zyx4. 设一环形队列用一维数组Am表示，队头和队尾的指针分别为front和tail，则入队时判定队列满的条件是_C_。A) front=tail B) front=tail+1C) front=(tail+1) % m D) front=tail % m5. 单链表L中，P所指结点为尾结点的条件为 _B_ 。A) PL B) P->next=NULLC) P.next:L D) Pnil6.借助栈输入A、B、C三个元素，则不可能的输出序列是 _B_。A) ABC B) CAB C) CBA D) BA

18、C7. 设top为栈顶指针，判定一个栈S(最多元素为m)为栈满的条件是_D_。 A）S->top!=0 B）S->top=0 C）S->top!=m-1 D）S->top=m-18. 在一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删除的结点，则执行的操作是_C_。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存储一个栈

19、，令A0为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一个元素时，变量T的变化为_A_。A) T=T+1 B) T=T-1C) T不变 D) T=n10.设用一维数组An存储一个栈，令An-1为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。当压入栈中一个元素时，变量T的变化为_B_。A) T=T+1 B) T=T-1C) T不变 D) T=n11.和顺序栈相比，链栈有一个明显的优势是_B_。A）通常不会出现栈空的现象B）通常不会出现栈满的现象C）插入操作更容易实现D）删除操作更容易实现12.循环队列用数组Am存放其元素值,已知其头尾指针分别是front和rear则当前队

20、列中的元素个数是_A_。P64A）(rear-front+m)%m B）rear-front+1C）rear-front-1 D）rear-front13.在一个链队中，若front和rear分别为队头、队尾指针，则所插入s所指结点操作为_B_。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.栈和队列的共同点是_C_。A）都是先进后出 B）都是先进先出C）只允许在端点处插入和删除元素 D）没有共同点15.设数组0.m作为循环链

21、队列lq的存储空间，若front和rear分别为队头、队尾指针，则入队时修改指针的语句是_D_。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. 栈的基本运算包括_BCD_。 A) 删除栈底元素 B) 将栈置为空栈 C) 判断栈是否为空 D) 删除栈顶元素2. 队列的基本运算包括_ABD_。 A) 从队尾插入一个新元素 B) 判断一个队列是否为空 C) 从队列中删除第i个元素 D) 读取队头元素的值3. 从逻辑上讲，下列属

22、于线性结构的是_ABD_。A) 队列 B) 栈 C) 线索二叉树 D) 线性表 4. 下列术语与为数据结构的是_ABD_。A) 栈 B) 队列 C) 散列表 D) 串5.以下说法错误的是 BCD 。A）因链栈本身没有容量限制，故在用户内存空间范围内不会出现栈满情况B）因顺序栈本身没有容量限制，故在用户内存空间范围内不会出现栈满情况C）对链栈而言，在栈满情况下，如果再入栈操作，则会发生“上溢”D）对顺序栈而言，在栈满情况下，如果再入栈操作，则会发生“下溢”三、判断题1. 栈和队列既可采用顺序存储方式，也可采用链接存储方式。2. 队列是允许在队头一端进行插入，在队尾一端进行删除操作的线性表。3.

23、链栈的每个结点都含有两个指针。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，

24、60;s4， s6， s5， s1，则顺序栈的容量至少应为_。 答：1. 表尾(允许操作的一端)、后进先出、先进先出 2. bceda 3. 34. 设栈S的初始状态为空，队列Q的初始状态为 a1 a2 a3 a4 队头 队尾对栈S和队列Q进行如下两步操作：(1) Q中的元素依次出队，并压入栈S中，直至Q为空；(2) 依次弹出S中的元素并进入Q，直至S为空。在上述两步操作后，队列Q的状态是 。答：a4a3a2a15. 具有n个单元的循环队列中，队满时共有 _个元素。6.通常程序在调用另一个程序时，都需要使用一个_来保存被调用程序内分配的局部变量、形式参数的存储空间

25、以及返回地址。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，

26、d，f，e，a，则顺序栈的容量至少应为。答： 3五、简答题1如图所示，在栈的输入端有6个元素，输入顺序为A、B、C、D、E、F。能否在栈的输出端得到序列ACEDFB及EDFCAB？若能，写出对栈的操作过程（用push表示进栈，pop表示退栈）；若不能，简述其理由。PUSH(S,A)¡ª¡ªA元素进栈POP(S) ¡ª¡ª栈顶元素出栈参考答案：n 可以产生ACEDFB， ACEDFB进栈过程：Ø PUSH(S,A) ，POP(S)，Ø PUSH(S,B) ，PUSH(S,C) ，POP(S)，&#

27、216; PUSH(S,D)，PUSH(S,E)，Ø POP(S)，POP(S)，Ø PUSH(S,F) ，POP(S)，POP(S)n 不能产生EDFCAB，原因：不能产生EDFCAB原因：栈是一种特殊的线性表，其操作原则“先进后出”或“后进先出”。在进栈系列ABCDEF中，B比A后进栈，在出栈时应比A先出栈，故不可以得到EDFCAB系列。 六、编程题 写一个算法，借助栈将一个单链表(带有头结点)置逆；给定函数如下，Iin_stack(S)，初始化栈；Pop_stack(S,p),入栈； Push_stack(S,P)，出栈； Enmpty_stack(S)，栈空。单链表

28、的结点结构说明及函数名如下：n typedef struct node /*定义结点结构*/ datatype data; struct node *next; LinkNode， *lklist;n 函数首部为：Ø 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(！

29、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_。A) T=T+1 B) T=T-1 C) T不变 D) T=n-12. 下列关于串的叙述中，不正确的是_B_。A) 串是字符的有限序列B) 空串是由空格构成的串C) 模式匹配是串的一种重要运算D) 串既可以采用顺序存储，也可以采用链式存储3. 设有数组A810，每个元素Aij的长度为3个

30、字节，行下标i从0到7，列下标j从0到9，该数组从首地址1000开始连续存储，需要占用的存储空间为_【1】C_个存储单元。如果数组按行存放，元素A74的起始地址为_【2】C_；如果数组按列存放，元素A47的起始地址为_【3】_C【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) 12254. 以下关于广义表的叙述中，正确的是_A_。A) 广义表是0个或多个单元素或子表组成的有限序列B) 广义表至少有一个元素是子表C) 广义表不可以是自身的子表D) 广义表不能为空

31、表5.广义表(a, b), c, d )的表头是 _C_ ，表尾是_D_ 。A) a B) d C) (a, b) D) (c ,d)6 .广义表(a, b, c, d )的表头是 _C_ ，表尾是_D_ 。A) a B) (a, b,c,d) C) (a, b,c,d) D) ( )7. 稀疏矩阵一般是指 _C_。 A) 非零元素和零元素都非常少 B) 非零元素较多 C) 零元素较多 D) 非零元素和零元素都较多8.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为（ B ）。 A）SA+141 B）SA+180 C）SA

32、+222 D）SA+2259.已知广义表LS( (a,b,c),d,e,f ),运用head和tail函数取出LS中原子e的运算是_C_。A）head(tail(LS) B）tail(head(LS)C）head(tail(tail(LS) D) head(tail(tail(head(LS)10. 有一个100×90的稀疏矩阵，非0元素有10个，数据元素为整型数据，设每个整型数据占2个字节，则用三元组表示该矩阵时，所需字节数是_B_。A）60 B）66 C）18000 D）16二.多选题1. 下面说法中，错误的是_AC_。P108 A）广义表的表头总是一个广义表 B）广义表的表尾总

33、是一个广义表 C）广义表可以用顺序存储结构 D）广义表可以是一个多层次的结构 2. 串常用机内表示方法有_ABC_。P73 A）串的定长顺序存储表示 B）串的块链存储表示C）串的堆分配存储表示 D）串的十字链表表示3. 在串的块链存储表示法中，影响串处理效率的因素是_ABCD_。 A）串的结点的大小 B）存储空间的大小 C）存储密度的大小 D）串的字符集 4. 稀疏矩阵的压缩存储方法包括_AB_。P98 A）三元组表示法 B）十字链表法C）孩子兄弟表示法 D）堆分配存储表示法5.下面关于串存储表示方法正确的是_AB_。A）定长顺序存储表 B）块链存储表示 C）十字链表表示 D）矩阵存储表示三、

34、判断题1. 数组和广义表可以看成线性表的扩展，即表中的元素本身也是一个数据结构。参考答案 ： 正确 2. 若采用三元组压缩存储技术存储稀疏矩阵,只要把每个元素的行下标和列标互换, 就完成了该矩阵的转置。P98参考答案 ： 错误四、填空题1.空字符串是 _ ，其长度为_ 。 参考答案 ： 零个字符的串 ， 02. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的行号、列号和 _。 参考答案：元素值3.经常对数组进行的两种操作是_ 。 参考答案：存取和修改4. 设有两个串P和Q，求Q在P中的首次出现的位置的操作称为_。答案：模式匹配5. 有如下定义：char s130=“Stocktom,

35、CA”， char s230=“March,5,2000”，则调用函数strCmp(s1,s2)的返回值是_；调用函数strlen(strcat(s1,s2)的返回值是_。答案：正数 (6)， 23一.单选题1. 设二叉树的第1层为根结点，则第i层最多有 【1】 C 个结点，深度为k的二叉树最多有 【2】B 个结点。对任一棵二叉树T，如果其叶结点数为n0，度数为1的结点数为n1，度数为2的结点数为n2，则n0=_【3】A_。【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)

36、n+1 D) n1+n22. 在一棵二叉树中，若一个结点是叶结点，则它没有_C_。 A) 左子结点 B) 右子结点 C) 左子结点和右子结点 D) 左子结点、右子结点和兄弟结点3. 在二叉树结点的先序序列、中序序列和后序序列中，所有叶结点的先后顺序_B_。 A) 都不相同 B) 完全相同 C) 先序和中序相同，而与后序不同 D) 中序和后序相同，而与先序不同4. 由3个结点可以构造出_D_种不同的二叉树。 A) 2 B) 3 C) 4 D) 55. 带权路径长度最短的二叉树称为_A_。 A) 赫夫曼树 B) 诺伊曼树 C) 线索二叉树 D) B+树6.树结构最适合用来表示 _A_ 。 A) 元

37、素间具有分支、层次关系的数据 B) 有序数据 C) 元素间没有关联的数据 D) 无序数据7. 深度为k的二叉树所含叶子的个数最多为 _B_。 A) 2k -1 B) 2k-1 C) k D) 2k8.设有一棵n个叶结点的哈夫曼树，其树中总结点数是_A_ 。 A) 2n-1 B) n(n+1) C) n D) n-19.具有10个叶结点的二叉树中有_B_个度为2的结点。P124 A）8 B）9 C）10 D）ll10.一个具有1025个结点的二叉树的高h为_C_。P124 A）11 B）10 C）11至1025之间 D）10至1024之间11. 在线索二叉树中，t 所指结点没有左子树的必要条件是

38、 _C_。P132 A) t->left =NULL B) t->ltag =1 且 t->left =NULL C) t->ltag =1 D) 以上都不对12. 由权值3，8，6，5，2 的叶子结点生成一棵赫夫曼树，它的带权路径长度为_C_。 A) 48 B) 72 C) 53 D) 24WPL=2×3+3×3+5×2+8×2+6×2=5313. 已知某二叉树 的后序遍历是dabec，中序序列是debac，则它的先序序列是_D_。 A) acbed B) deabc C) decab D) cedba14. 线索二叉

39、树 是一种_B_结构。 A) 逻辑 B) 存储 C) 线性存储 D) 逻辑存储15. 深度为5的二叉树 最多有_B_结点。 A) 32 B) 31 C) 16 D) 10二.多选题1. 下列关于哈夫曼树的叙述中，正确的是_BCD_。 A) 哈夫曼树是一棵二叉树，因此，它的结点的度可以是0、1或2 B) 具有n个权值的哈夫曼树共有2n-1个结点 C) 哈夫曼树根结点的权值等于所有叶结点的权值之和 D) 具有n个权值的哈夫曼树含有n-1个非叶结点2.下面的说法中，正确的是_AC_。 A）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变 B）按二叉树定义，具有三个结点的二叉树共有6种 C）用二叉树

40、的前序遍历和中序遍历可以导出该树的后序遍历 D）完全二叉树一定存在度为1的结点3.在下述结论中，正确的是_AC_。 A）只有一个结点的二叉树的度为0 B）二叉树的度为2 C）深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 D）二叉树的左右子树可任意交换;二.多选题4. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是错误的是_ABC_。A）500 B）254 C）505 D）以上答案都不对 (最大层有490=1001-511个结点，次最大层有11=511-1001/2)个结点) 5.关于二叉树，下面说法正确的是_ABC_。p124A）完全二叉树上结点之间的父子关系可由它们编

41、号之间的关系来表达B）在三叉链表上，二叉树的求双亲操作很容易实现C）在二叉链表上，求根以及左、右孩子等操作很容易实现D）在二叉链表上，求双亲的时间性能很好三、判断题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

42、 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开始存放，这棵二叉树

43、最下面一层上最左边一个结点存储在数组元素 中。答案：b328. 假定一棵二叉树的结点数为18，则它的最小深度为_，最大深度为_。P124 答案: 5 18 9. 对于具有30个结点的完全二叉树，若一个结点的编号为5，则它的左孩子的编号为_，右孩子的结点为_ ，双亲结点结点的编号为 _ 。124参考答案：10 11 2 10.设森林中有4棵树，结点个数分别为n1、n2、n3、n4，当把森林转换成一棵二叉树后，根结点的右子树上有_结点。参考答案： n2+n3+n4 五、简答题1简要回答树和二叉树之间有什么区别和联系。 参考答案：区别：.对子树要求不同，二叉树任一结点都有两棵子树，且两棵子树之间有次

44、序关系。.二叉树即使一结点只有一棵非空子树，仍需区别是左子树还是右子树。.二叉树上任一结点的度定义为该结点的孩子数，树的度定义为结点拥有子树的数目。二叉树与树有相似之处，但并非树的特例，属两种不同的数据结构。联系：逻辑结构相同，都是树形结构。五、简答题2.已知一棵二叉树如下，请分别写出按先序、中序、后序和层次遍历时得到的结点序列。 DABCFGEH参考答案：先序：A B D G C E F H中序：D G B A E C H F后序：G D B E H F C A层次：A B C D E F G H1假设用于通信的电文由字符集A，B，C，D，E，F，G中的字母构成，它们出现的频率依次为10、9、2、7、8、6、3。试画出对应的哈夫曼树，并计算它的WPL值。1答案： WPL= 2×4+3×4+6×3+7×3+8×3+9×2+10×2=1211045192611658231597ABEDFGC2试画出下图所示森林对应的二叉树。OPRQSACBDFEGHIJKLM森林中第一棵树对应的二叉树:ACBDFEGACBDEFG森林中第二棵树对应的二叉树:HIJKLMJHIKLM森林中第三棵树对应的二叉树