数据结构复习题

1、数据结构第一二章一 填空1. 衡量算法效率的两个重要指标称为算法的 时间复杂度_和 空间复杂度。2. 一个算法应具有 有穷性，确定性，可行性，输入和 输出这五个特性。3. 线性表的长度是指_表中元素的个数_。4. 在线性表的顺序存储中，元素之间的逻辑关系是通过 元素存储的相对位置 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 相关元素的存储位置 决定的。5 在双向链表中，每个结点包含两个指针域，一个指向其直接前趋结点，另一个指向 其直接后继 结点。二、 判断题 1线性表的逻辑顺序与存储顺序总是一致的。(FALSE) 2顺序存储的线性表可以按序号随机存取。(TRUE) 3在线性表的顺序

2、存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（FALSE） 4在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（TRUE） 5在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（TRUE） 6线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（TRUE） 三、 单选题 (请从下列A，B，C，D选项中选择一项) 1线性表是(A) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2对顺序存储的线性表，设其长度为n，在任何位置上插入或删

3、除操作都是等概率的。插入一个元素时平均要移动表中的（A ）个元素。 (A) n/2 (B)（n+1）/2 (C) (n 1)/2 (D) n 3线性表采用链式存储时，其地址( D ) 。 (A) 必须是连续的； (B) 部分地址必须是连续的； (C) 一定是不连续的； (D) 连续与否均可以。 4用链表表示线性表的优点是 （ C）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 5. 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( D )存储方式最节省运算时间。 (A)单链表 (B)双链表

4、(C)单循环链表 (D)带头结点的双循环链表 6. 循环链表的主要优点是( D ) 。 (A)不再需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 7. 单链表中，增加一个头结点的目的是为了（ C ）。 (A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置 （C）方便运算的实现 (D) 说明单链表是线性表的链式存储 8. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省运算时间（B ）。 (A) 单链表 (B) 顺序表 (C)

5、 双链表 (D) 单循环链表 四、简答题1何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主

6、要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。3 为什么在单循环链表中设置尾指针比设置头指针更好?答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next-&

7、gt;next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。五、分别设计算法，实现线性表的顺序存储结构和链式存储结构的原地置逆。顺序存储结构的原地置逆typedef struct ElemType *elem; /存储空间基址 int length; /线性表的实际长度 int listsize； /当前分配的存储容量， /（以sizeof（ElemType）为单位sqList;void reverse(SqList &A) /顺序表的就地逆置   int i; int j; for(i=1,j=A.length;i<

8、;j;i+,j-)     A.elemi<->A.elemj;/reverse链式存储结构的原地置逆。算法：ypedef struct LNodeElemType data; /结点值 struct LNode *next; /指针域，存储下一个结点的地址LNode,*LinkList;void ReverseList( LinkList &L )/ 将L 所指的带头结点的单链表逆置if( L->next && L->next->next)/当链表不是空表或单结点时 p=L->next;q=p

9、->next; p -> next=NULL; /将开始结点变成终端结点 while (q) /每次循环将后一个结点变成开始结点 p=q; q=q->next ; p->next = L-> next ;L->next = p;作业2.1,2.2答案见习题册后面答案2.6答案：解答：a.（4）（1）b.（7）（11）(8)（4）（1） c.（5）（12）d.（11）（9）（1）（6） 或 (11)（9）（4）（1）2.7答案：解答：a.（11）（3）（4） b.（10）（12）（8）（10）（3）（4） c. （10）（12）（7）（3）（4）d.（12）（

10、11）（3）（14） e.（9）（11）（3）(14)2.8 已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a在P结点后插入S结点的语句序列是-。 b在P结点前插入S结点的语句序列是-。 c删除P结点的直接后继结点的语句序列是-。 d删除P结点的直接前驱结点的语句序列是-。 e删除P结点的语句序列是-。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (

11、3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=

12、p->next; (18)free(Q);解答：a.（12）（7）（3）（6） 3必须在12和7的后面，其余的顺序可变b.（13）（8）（4）（5） 同上c.（15）（1）（11）（18） 不可变d.（16）（2）（10）（18） 不可变e.（9）（14）（17）2.31答案： ypedef struct LNode ElemType data; /结点值 struct LNode *next; /指针域，存储下一个结点的地址LNode,*LinkList;Status Delete_Pre(linklist s ElemType e) /删除单循环链表中结点s的直接前驱 &#

13、160;p=s;  while(p->next->next!=s) p=p->next; /找到s的前驱的前驱p  q=p->next; p->next =s; e=q ->data; free(q);  return OK;/Delete_Pre第三章一 、单项选择题1.栈中元素的进出原则是 （B ）先进先出 后进先出 栈空则进 栈满则出 2.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为 （C）I n=i n-i+1 不确定 解释：当p1=n，即

14、n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经表明了），那么输入顺序必定是1，2，3，n，则出栈的序列是n，3，2，1。 （若不要求顺序出栈，则输出序列不确定） 3.判定一个栈ST（最多元素为m0）为空的条件是 （B ）ST->top<>0 ST->top= =0 ST->top<>m0 ST->top= =m0 4. 在作进栈运算时,应先判别栈是否( B ),在作退栈运算时应先判别栈是否( A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( B )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享

15、一片连续的内存空间时,应将两栈的 ( D )分别设在这片内存空间的两端,这样,当( C )时，才产生上溢。 : A. 空 B. 满 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 长度 B. 深度 C. 栈顶 D. 栈底:A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.5. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c,

16、 d，b, a D. d, c，a，b6. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ B ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top27. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈8. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( A )。A仅修改队头指

17、针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改9. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。A队列 B多维数组 C栈 D. 线性表10. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 二 填空题1. 线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入

18、元素， 在 队头 删除元素。2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3 1 2_。4. 循环队列的引入，目的是为了克服_队列的假溢出_。 5用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式是：M=_(M+1)%N_；6.队列的特点是_先进先出_。7表达式求值是_栈_应用的一个典型例子。3.1 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序

19、开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。【解答】(1) 可能的不同出栈序列有 种。(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426

20、可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 1354260 m-13-15 将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top1减1得到新的栈顶位置。当top0+1 = top1时或top0 = top1-1时

21、，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。【解答】bot0 top0 top1 bot1双栈的类定义如下：#include <assert.h>template <class Type> class DblStack /双栈的类定义 private: int top2, bot2;/双栈的栈顶指针和栈底指针 Type *elements; /栈数组 int m;/栈最大可容纳元素个数 public: DblStack ( int sz =10 );/初始化双栈, 总体积m的默

22、认值为10 DblStack ( ) delete elements; /析构函数 void DblPush ( const Type& x, int i );/把x插入到栈i的栈顶 int DblPop ( int i );/退掉位于栈i栈顶的元素 Type * DblGetTop ( int i );/返回栈i栈顶元素的值 int IsEmpty ( int i ) const return topi = boti; /判栈i空否, 空则返回1, 否则返回0 int IsFull ( ) const return top0+1 = top1; /判栈满否, 满则返回1, 否则返回0

23、 void MakeEmpty ( int i ); /清空栈i的内容template <class Type> DblStack<Type> : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一个最大尺寸为sz的空栈, 若分配不成功则错误处理。 elements = new Typem;/创建栈的数组空间 assert ( elements != NULL );/断言: 动态存储分配成功与否template <class Type> void DblStack

24、<Type> : DblPush ( const Type& x, int i ) /如果IsFull ( )，则报错；否则把x插入到栈i的栈顶 assert ( !IsFull ( ) );/断言: 栈满则出错处理，停止执行 if ( i = 0 ) elements +top0 = x;/栈0情形：栈顶指针先加1, 然后按此地址进栈 else elements-top1 = x;/栈1情形：栈顶指针先减1, 然后按此地址进栈template <class Type> int DblStack<Type> : DblPop ( int i ) /如

25、果IsEmpty ( i )，则不执行退栈，返回0；否则退掉位于栈i栈顶的元素，返回1 if ( IsEmpty ( i ) ) return 0;/判栈空否, 若栈空则函数返回0 if ( i = 0 ) top0-;/栈0情形：栈顶指针减1 else top1+; /栈1情形：栈顶指针加1 return 1;template <class Type> Type * DblStack<Type> : DblGetTop ( int i ) /若栈不空则函数返回该栈栈顶元素的地址。 if ( IsEmpty ( int i ) ) return NULL;/判栈i空否,

26、 若栈空则函数返回空指针 return& elements topi ;/返回栈顶元素的值template <class Type> void MakeEmpty ( int i ) if ( i = 0 ) top0 = bot0 = -1; else top1 = bot1 = m; 或S1.base S2.base S1Sm 进栈：S1.top+ S2.top- 出栈：S1.top- S2.top+ 栈满：S1.top=-S2.top或+S1.top=S2.top3.1【解答】(1) 可能的不同出栈序列有5种：123，132，213，231，321。(2) 不能得到4

27、35612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。 3.15 画出两个栈共享存储空间S 1.m示意图，并说明两个栈进栈、出栈操作时栈顶指针变化情况及栈满的条件。进栈：S1.top+ S2.top- 出栈：S1.top- S2.top+ 栈满：S1.top=-S2.top或+S1.top=S2.topS1.base s1.top s2.top s2.base s1 sm3.28 假设以带头结点的循环链表

28、表示队列，并且只设一个指针指向队尾元素（注意不设头指针）， 试编写相应的队列初始化、入队列和出队列的算法。 typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;void InitQueue(Queue &Q) /初始化循环链表表示的队列Q  Q=(QueuePtr)malloc(sizeof(QNode);  Q->next=Q;/InitQueueStatus EnQueue(QueuePtr &tail,QElemType e ） q =

29、 (QueuePtr)malloc(sizeof(QNode); /分配空间，构造入队列元素结点 q->data = e; /元素赋值 q->next = tail ->next; /入队列 tail ->next = q; tail = tail ->next; /队尾指针后移 return OK;Status DeQueue(QueuePtr & tail,QElemType &e）  if(tail = tail ->next) return ERROR; /队列已空 q = tail ->next->next;

30、/q指向带头结点链表的第一个元素 e = q->data; /返回出队列元素 tail ->next->next = q ->next; /元素出队列 free(q); /释放空间 return OK;3.30 假设将循环队列定义为：以rear和length分别指示环形队列中的队尾元素的位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的入队列和出队列元素的算法（在出队列的算法中要返回队头元素）。队空条件:Q.length=0队满条件： Q.length=MAXSIZEStatus EnCyQueue(CyQueue &Q,int x

31、) /带length域的循环队列入队算法  if(Q.length=MAXSIZE) return OVERFLOW;  Q.rear=(Q.rear+1)%MAXSIZE;  Q.baseQ.rear=x;  Q.length+;  return OK;/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x) /带length域的循环队列出队算法  if(Q.length=0) return ERROR; 

32、60;head=(Q.rear+ MAXSIZE -Q.length+1)%MAXSIZE; /详见书后注释  x=Q.basehead;  Q.length-;/DeCyQueue 第四五章 一、填充题1、一个串中任意个 连续 的字符组成的子序列称为该串的子串。 2、串的静态存储结构中的两种不同的存储方式分别是 非紧缩 格式和 紧缩 格式。3、两个串的相等，是指两个两串的 长度 相等， 对应位置的字符 相同。4、已知二维数组A有m行n列，采用行优先方式存储，每个数据元素占k个存储单元，并且第一个元素的存储地址是LOC(A1,1)，则数据元素Ai,j的地

33、址是 LOC(A1,1)+(n(i-1)+(j-1)k 。5、有一个10阶的对称矩阵，采用以行优先的压缩存储方式，已知元素A1,1的地址为1，则元素A8,5的地址是 33 ，元素A5,8的地址是 33 。6、广义表(a,(a,b),d,e,(i,j),k)的长度是 5 ，深度是 3 。二、单选题1、给出字符串A=abcd，它的子串个数是 C 。 A、10 B、9 C、11 D、142、给出两个串A=ABCDE，B=ABCdE，它们的关系是不是 A 。 A、B串大于A串 B、B串等于A串 C、B串小于A串 D、B串是A串的子串 3、设有两个串A和B，求B在A中首次出现的位置的操作称作 C 。 A

34、、连接 B、求串长 C、模式匹配 D、求子串 4、设串S1=ABCDEFG，串S2=PQRST，函数con(x,y)返回x和y串的连接串，函数subs(s,i,j) 返回串s的从序号i的字符开始的j个字符组成的子串，而函数len(s) 则返回串s 的长度。那么，表达式con(subs(S1,2,len(S2),subs(S1,len(S2),2)的结果串是 D 。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、数组通常具有的两种基本操作是 C 。 A、建立与删除 B、索引与修改 C、查找与修改 D、查找与索引 6、在数组A中，每个数据元素Ai,j的长度为3个字节

35、，数组A的行下标i从1到8，而列下标j从1到10，从首地址SA开始连续存放在存储器中，若该数组按行优先存放时，数据元素A8,5的起始地址为 D 。 A、SA+141 B、SA+144 C、SA+225 D、SA+2227.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（B ）。A. 13 B. 33 C. 18 D. 40 E.12 8. 将一个A100100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。A. 198

36、B. 195 C. 1979. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（i<j）的位置k的关系为( A )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i10. 对稀疏矩阵进行压缩存储目的是（ C ）。A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度11. 已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tai

37、l(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)12. 广义表（a,(b,c),d,e）的表头为（ A ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)4.24void HString_Concat(HString &t ,HString s1,HString s2) /将堆结构表示的串s1和s2连接为新串t  if(t.ch) free(t.ch);  if(!(t.ch=(char*)malloc(s1.length

38、+s2.length)*sizeof(char);  exit (OVERFLOW); for(i=1;i<=s1.length;i+) t.chi-1=s1.chi-1;  for(j=1;j<=s2.length;j+,i+) t.chi-1=s2.chj-1;  t.length=s1.length+s2.length;/HString_Concat 5.23typedef struct            

39、;     int j;                 int e;                DSElem; typedef struct         

40、60;DSElem dataMAXSIZE;           int cpotMAXROW; /这个向量存储每一行在二元组中的起始位置            int mu,nu,tu;  DSMatrix; /二元组矩阵类型 Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)/求二元组矩阵的

41、元素Aij的值e  for(s=A.cpoti;s<A.cpoti+1&&A.datas.j!=j;s+);/注意查找范围  if(s<A.cpoti+1&&A.datas.j=j) /找到了元素ij      e=A.datas;    return OK;    return ERROR;/DSMatrix_Locate第六章一、 填空题1. 不相交的树的聚集称之为 森

42、林 。2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。3. 深度为k的完全二叉树至少有2 k-1个结点。至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2k-2+1。4. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=n2+1。5. 一棵二叉树的第i（i1）层最多有2 i-1个结点；一棵有n（n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。6. 现

43、有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。7. 哈夫曼树 是带权路径最小的二叉树。8. 前缀编码是指任一个字符的编码都 不是 另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。9. 以给定的数据集合4，5，6，7，10，12，18为结点权值构造的Huffman树的加权路径长度是 165 。10. 树被定义为连通而不具有 回路 的（无向）图。11. 若一棵根树的每个结点最多只有 两个 孩子，且孩子又有 左、右 之分，次序不能颠倒，则称此根树为 二叉树 。12. 高度为k，且有 2k-1 个结点的二叉树称为 满 二叉树。13. 带权路径长度最小的二叉

44、树称为最优二叉树，它又被称为 Huffman 树。14. 在一棵根树中，树根是 入度 为零的结点，而 出度 为零的结点是 树叶 结点。15. Huffman树中，结点的带权路径长度是指由 节点 到 树根 之间的路径长度与结点权值的乘积。16. 满二叉树是指高度为k，且有 2k-1 个结点的二叉树。二叉树的每一层i上，最多有 2i-1 个结点。二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。(A)8(B)9(C)10(D)112 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3

45、）次序的遍历实现编号。（1）先序 （2）中序（3）后序 （4）从根开始按层遍历3. 由2、3、4、7作为结点权值构造的树的加权路径长度 B 。 A、33 B、30 C、36 D、40 4. 高度为6的满二叉树，总共有的结点数是 B 。 A、15 B、63 C、20 D、25 5. 下面描述根树转换成二叉树的特性中，正确的是 C 。 A、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子。 B、根树转换成的二叉树是不唯一的，二叉树的根结点只有左孩子。 C、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。 D、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子。6. 如图所示的4棵

46、二叉树中，不是完全二叉树的是 C 。 A、 B、 C、 D、 7.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是 D 。 A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca8. 已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK， 按后序遍历所得到的结点序列为DCEGBFHKJIA， 按先序遍历所得到的结点序列为 ABCDGEIHFJK 。9. 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 C 。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙10.

47、二叉树第i 层结点的结点个数最多是（设根的层数为1） ：A A）2i-1 B）2i-1 C）2i D） 2i-1 11. 树的后根遍历序列等同于该树对应的二叉树的： B A）先序序列 B）中序序列 C）后序序列12. 树最适合用来表示_C_。A. 有序数据元素           B. 无序数据元素 C. 元素之间具有分支层次关系的数据  D. 元素之间无联系的数据13. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_B_。  A. 正确&#

48、160;         B. 错误14. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 B   个。  A15        B16     C17     D4715. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。  A. 3     &

49、#160;  B. 4       C. 5       D. 616. 深度为5的二叉树至多有_C_个结点。  A. 16      B. 32     C. 31      D. 1017. 对一个满二叉树，m个树叶，n个结点，深度为h，则_D_ 。  A. n=h+m   

50、    B. h+m=2n       C. m=h-1        D. n=2 h-118. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。  A.不发生改变    B.发生改变      C.不能确定     D.以上都不对19. 如果某二叉树的前根次序遍历结果为stuwv，中序

51、遍历为uwtvs，那么该二叉树的后序为_C_。 A. uwvts        B. vwuts        C. wuvts      D. wutsv20. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A. 正确         B. 错误21. 在一非空二叉树的中序遍历序列中，根结点的右边_A_。  A. 只有右子