数据结构题集答案

数据结构题集

第一章 绪论

一、单选题

1. 在数据结构中，从逻辑上可以把数据结构分成【 C 】。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构

C. 线性结构和非线性结构 D. 内部结构和外部结构

2. 数据结构在计算机内存中的表示是指【 A 】。

A. 数据的存储结构 B. 数据结构

C. 数据结构的逻辑结构 D. 数据元素之间的关系

3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。

A. 数据项 B. 数据元素

C. 信息项 D. 表元素

4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。

A. 数据与数据之间存在某种关系 B. 数据元素与数据元素之间存在某种关系

C. 元素内部存在某种结构 D. 数据项与数据项之间存在某种关系

5. 算法分析的目的是【 C 】。

A. 找出数据结构的合理性 B. 研究输入和输出的关系

C. 分析算法的效率以求改进 D. 分析算法的易懂性

6. 在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。

A. 数据处理的方法 B. 数据元素的类型

C. 数据元素之间的关系 D. 数据的存储方法

7. 算法分析的主要任务是分析【 D 】。

A. 算法是否具有较好的可读性

B. 算法中是否存储语法错误和逻辑错误

C. 算法的功能是否符合设计要求

D. 算法的执行时间与问题规模之间的关系。

8. 数据的运算【 A 】。

A. 效率与采用何种存储结构有关

B. 是根据存储结构来定义的

C. 有算术运算和关系运算两大类

D. 必须用程序设计语言来描述

9. 算法的计算量的大小称为算法的【 B 】。

A. 效率 B. 时间复杂度 C. 现实性 D. 难度

10. 连续存储分配时，存储单元的地址【A 】。

A. 一定连续 B. 一定不连续

C. 不一定连续 D. 部分连续，部分不连续

二、判断题

1. 数据元素是数据结构的最小单位【. × 】。

2. 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×. 】。

3. 数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×. 】。

4. 算法的优劣与算法的描述语言无关，但与使用的计算机有关【. × 】。

5. 数据结构的抽象操作的定义与具体实现有关【. × 】。

三、填空题

1. 数据的逻辑结构指

2. 一个数据结构在计算机中的称为存储结构。

3. 数据的物理结构主要包括

4. 数据逻辑结构包括、、四种，树结构和图结构统称为 非线性结构 。

5. 顺序存储方法把逻辑上存储在物理位置链式存储方法中结点间的逻辑关系是由 指针域 表示的。

6、数据结构研究的是和并对于这种结构定义相应的 运算 ，设计出相应的 算法 。

7. 算法的执行时间是的函数。

8. 以下是4个算法所有语句频度之和的表达式，其中的复杂度相同的是

A.T A (n)=2n3+3n2+1000 B.T B (n)=n3-n 2log 2n-1000

C.T C (n)=n2log 2n+n2 D.T D (n)=n2+1000

四、解答题

1. 简述数据的逻辑结构和存储结构的关系。

答：在数据结构中，逻辑结构和存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。通常情况下，一种逻辑结构可以有多种存储结构，例如，线性结构可以采取顺序存储结构或链式存粗结构表示。

2. 数据结构和数据类型有什么区别？

答：数据结构是相互间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容：数据的逻辑结构、存储结构和多数据的运算。数据类型是一个值得集合和定义在这个值集上的一组操作的总称。数据结构重点考虑元素之间的关系，数据类型重点考虑数据的个体特征。

3. 当为解决某一问题已经选定其数据的逻辑结构后，选择数据的存储结构时，应从哪些方面考虑？

答：通常从两个方面考虑：第一是算法实现的存储空间复杂度；第二是算法执行的时间复杂度。若存储空间难以确定，宜选择链式存储结构，否则选择顺序存储结构。若插入、删除操作频繁，则选链式存储结构，否则选择顺序存储结构。

第二章 线性表

一、单选题

1. 链表不具备的特点是【 A 】。

A. 可随机访问任一结点 B. 插入删除不需要移动元素

C. 不必事先估算存储空间 D. 所需空间与其长度成正比

2. 设线性表有n 个元素，以下操作中，【 A 】在顺序表上实现比在链表上实现效率更高。

A. 输出第i （1≤i ≤n ）个元素的值

B. 顺序输出这n 个元素

C. 交换第1个与第2个元素的值

D. 输出与给定值x 相等的元素在线性表中的序号

3. 如果最常用的操作是取第i 个结点及其前驱，则采用【 D 】存储方法最节省时间。

A. 单链表 B. 双链表 C. 线性链表 D. 顺序表

4. 线性表是具有n 个【 C 】的有限序列（n ≥0）。

A. 表元素 B. 字符 C. 数据元素 D. 数据项

5. 下面关于线性表的叙述中，错误的是【 B 】。

A. 线性表采用顺序存储，则必须占用一片连续的存储单元

B. 线性表采用顺序存储，则便于插入和删除操作

C. 线性表采用链式存储，则不必占用一片连续的存储单元

D. 线性表采用链式存储，则便于插入和删除操作

6. 线性表的顺序存储结构是一种【 A 】。

A. 随机存取的存储结构 B. 顺序存取的存储结构

C. 索引存取的存储结构 D.Hash 存取的存储结构

7. 单链表中增加一个头结点的目的是为了【 C 】。

A. 使单链表至少有一个结点 B. 标识表首结点的位置

C. 方便运算的实现

D. 说明单链表是线性表的链式存储

8. 不带头结点的单链表（头指针为h ）为空的条件是【 A 】。

A.h==NULL B.h->next==NULL

C.h->next==h D.h!=NULL

9. 带头结点的单链表（头指针为h ）为空的条件是【 B 】。

A.h==NULL B.h->next==NULL

C.h->next==h D.h!=NULL

10. 带头结点的循环双向链表（头指针为L ）为空的条件是【 D 】。

A.L==NULL B.L->next->prior==NULL

C.L->prior==NULL D.L->next==L

11. 非空的循环单链表（头指针为head ）的尾结点（由p 指向）满足【 C 】。

A.p->next==NULL B.p==NULL

C.p->next==head D.p==head

12. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【 A 】最节省时间。

A. 带头结点的双循环链表 B. 单循环链表

C. 带尾指针的单循环链表 D. 单链表

13. 若某线性表最常用的操作存取任意指定序号的元素和在表尾进行插入和删除，则选用

【 A 】的存储方式最节省时间。

A. 顺序表 B. 双链表

C. 带头结点的双循环链表 D. 单循环链表

14. 在n 个结点的线性表的顺序实现中，算法的时间复杂度为O(1)的操作是【 A 】。

A. 访问第i 个结点和求第i 个结点的直接前驱

B. 在第i 个结点后插入一个新结点

C. 删除第i 个结点 D. 以上都不对

15. 若长度为n 的线性表采用顺序存储结构，在第i 个位置插入一个新元素的算法的时间复杂度为【 C 】。

A.O(0) B.O(1) C.O(n) D.O(n2)

16. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为【 C 】。

A.O(n)O(n) B.O(n)O(1) C.O(1)O(n) D.O(1)O(1)

17. 线性表以链式方式存储，访问第i 个结点的时间复杂度为【 C 】。

A.O(i) B.O(1) C.O(n) D.O(i-1)

18. 循环链表H 尾结点p 的特点是【 A 】。

A.p->next==H B.p->next==H->next

C.p==H D.p==H->next

二、判断题

【× 】1. 取线性表的第i 个元素的时间同i 的大小有关。

【× 】2. 线性表中每个元素都有一个直接前驱和一个直接后继。

【× 】3. 顺序存储方式只能用于存储线性结构。

【× 】4. 线性表采用链式存储时，结点和结点内部的存储空间可以不连续。

【× 】5. 在一个设有头指针和尾指针的单链表中，执行删除单链表最后一个结点的操作与链表的长度无关。

三、填空题

1. 向一个长度为n 的顺序表中的第i 个元素之前插入一个元素时，需要向后移动 个元素。

2. 在一个长度为n 的顺序表中删除第i 个元素时，需要向前移动个元素。

3. 在单链表中设置头结点的作用是

4. 在单链中要删除某一指定结点，必须找到该结点的

5. 访问单链表中的结点，必须沿着依次进行。

6. 在双链表中每个结点有两个指针域，一个指向，一个指向结点 。

7. 在O(1)。

8. 访问一个线性表中具有给定值的时间复杂度的数量级是

9. 由n 个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为 O(n) ，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 O(n2。

10. 在链表中，可以用表尾指针代替表头指针。

11. 根据n 个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 O(n) ，最坏的情况是 O(n2

12. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是和 。

13. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 相同 。

14. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 不相同 。

四、简答题

1. 阐述顺序表和链表存储方式的特点。

答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随机访问线性表的数据元素，即数据访问的时间复杂度为O(1)。

链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺序访问线性表中的数据元素。

2. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？

答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因为链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。

3. 在单链表、双向循环链表和单循环链表中，若仅知道指针p 指向某结点，不知道头指针，能否将结点p 从相应的链表中删除？若可以，时间复杂度各为多少。

答：要实现删除p 结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p 的后继结点，以实现删除结点p 。单链表不行，因为不知道头指针就无法找到结点p 的前驱结点。双向循环链表和单循环链表可以可以实现删除p 结点。单循环链表删除p 结点的时间复杂度为O(n)，双循环链表删除P 结点的时间复杂度为O(1)。

4. 对链表设置头结点的作用是什么？

答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比带头结点的算法复杂些。

其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针，可以减少出错的可能性。

五、算法设计题

1. 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。 解：算法基本思想：从头结点的下一个结点开发，遍历单链表的每个结点，每遇到一个结点，结点计算器加1。

int listlenght(linklist L)

{ int length=0;

P=L->next;

while(p)

{ length++;

p=p->next;

}

return(length);

}

2. 已知一个顺序表L ，其中的元素按值递增有序排列，设计一个算法插入一个值为x

的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1）。

void insertsq(sqlist L,elemtype x)

{ n=L.length-1;

while(n>=0&&LT(x,L.elem[n])

{ L.elem[n+1]=L.elem[n];

n--;

}

L.elem[n+1]=x;

}

L.lenght++;

return;

}

3. 写一个算法，从顺序表中删除值为x 的所有元素。

void delallsq(Sqlist &L)

{ int i=0,j=0;

while(j

{ if(L.elem[j]!=x)

L.elem[i++]=L.elem[j];

j++;

}

L.longth=i;

}

第三章 栈和队列

一、单选题

1. 对于栈操作数据的原则是【 C 】。

A. 先进先出 B. 后进后出

C. 后进先出 D. 不分顺序

2. 队列的先进先出特征是指【 A 】。

A. 最后插入队列的元素总是最后被删除

B. 当同时进行插入、删除操作时，总是插入操作优先

C. 每当有删除操作时，总要先做一次插入操作

D. 每次从队中删除的元素总是最早插入的元素

3. 与顺序栈相比较，链栈有一个比较明显的优势是【 A 】。

A. 通常不会出现栈满的情况 B. 插入操作更容易实现

C. 通常不会出现栈空的情况 D. 删除操作更容易实现

4. 栈和队列的共同点是【 C 】。

A. 都是先进先出 B. 都是后进后出

C. 只允许在端点处进行插入和删除 D. 无共同点

5. 栈的特点是【① B 】，队列的特点是【② A 】；栈和队列都是【③ C 】若入栈序列是1，2，3，4 ，则【④ A 】是不可能的出栈序列；若进队列的序列是1，2，3，4，则【⑤

D 】是可能的出队序列。

①② A. 先进先出 B. 后进先出 C. 进优先于出 D. 出优先于进

③ A. 顺序存储的线性结构 B. 链式存储的线性结构

C. 限制存取点的线性结构 D. 限制存取点的非线性结构

④⑤ A.3,2,1,4 B.3,2,4,1 C.4,2,3,1 D.1,2,3,4

6. 用单链表表示的链队列的队头在链表的【 A 】。

A. 链头 B. 链尾 C. 链中 D. 都不是

7. 设入栈序列为1,2,3,4,5, 则可能得到的出栈序列为【 C 】。

A.1,2,5,3,4 B.3,1,2,5,4

C.3,2,5,4,1 D.1,4,2,3,5

8. 输入序列是ABC ，若输出序列变为CBA ，经过的栈操作为【 B 】。

A.push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop

D. push,pop,push,push,pop,pop

9. 栈在【 D 】应用。

A. 递归调用 B. 函数调用

C. 表达式求值 D.A,B,C

10. 设计一个判别表达式中左、右括号是否配对的算法，采用【 D 】数据结构最佳。

A. 线性表的顺序存储结构 B. 队列

C. 线性表的链式存储结构 D. 栈

11. 允许对队列进行的操作有【 D 】。

A. 对队列中的元素排序 B. 取出最近进队的元素

C. 在队头之前插入元素 D. 删除队头元素

12. 对于循环队列【 D 】。

A. 无法判断队列是否为空 B. 无法判断队列是否为满

C. 队列不可能满 D. 以上说法都不对

13. 队列存放在A[0..M-1]中，则入队时的操作为【 B 】。

A.rear=rear+1 B.rear=(rear+1)%M

C.rear=(rear+1)%(M+1) D.rear=(rear+1)%(M-1)

14. 队列存放在A[0..M-1]中，则出队时的操作为【 B 】。

A.front=front+1 B. front=(front+1)%M

C. front=(front+1)%(M+1) D. front=(front+1)%(M-1)

15. 循环队列的最大容量为M ，则队空的条件是【 A 】。

A.rear==front B.(rear+1)%M==front

C.rear+1==front D.(rear-1)%M==front

16. 循环队列的最大容量为M ，则队满的条件是【 B 】。

A.rear==front B.(rear+1)%M==front

C.rear+1==front D.(rear-1)%M==front

二、判断题

【× 】1. 队列在函数调用时必不可少，因此递归离不开队列。

【√ 】2. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。

【√ 】3. 设尾指针的循环链表表示队列，则入队和出队算法的时间复杂度为0(1)。

【× 】4. 队列逻辑上是一个上端和下端既能增加又能减少的线性表。

【√ 】5. 在链队列中，即使不设置尾指针也能进行入队操作。

【√ 】6. 栈和队列度是限制存取点的线性结构。

【× 】7. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作，所得的输出序列一定相同。

【√ 】8. 栈是实现函数调用所必需的数据结构。

【√ 】9. 顺序队列中的元素个数，可以根据队首指针和队尾指针的值计算出来。

三、填空题

1. 循环队列的引入，目的是为了克服。

2. 区分循环队列的空与满有3种方法，它们是计数器记录队列中元素个数 。

3. 栈和队列的区别是插入操作，在另一端进行删除操作 。

4. 一个栈的输入序列是12345，则栈的输出序列43512是

5. 设栈采取顺序存储结构，栈中已有i-1个元素，则第i 个元素进栈操作的算法时间复杂度是 O （1） 。

6. 若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是。

7. 从循环队列中删除一个元素的操作是

8. 从循环队列中插入一个元素的操作是 。

9. 判断链队列中只有一个结点的条件是

10. 如果栈的最大长度难以估计，最好使用。

四、简答题

1. 为什么说栈是一种后进先出表？

答：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，

所以说栈是一种后进先出表。

2. 对于一个栈，其输入序列是A,B,C, 试给出全部可能的输出序列。

答：可能的出栈序列是：ABC 、ACB 、BAC 、BCA 、CBA 。

3. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。

答：队列上溢指在队列的顺序存储分配中，所有单元中已有元素，再进行插入操作时称为队列上溢。

假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。

解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即：

入队操作：Q.rear=(Q.rear+1)%MSize

出队操作：Q.front=(Q.front+1)%MSize

4. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。

答：使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易找到链表的头结点，入队出队操作的算法时间复杂度均为O(1)。若只设头指针，则出队操作的算法时间复杂度为O(1)，入队操作的算法时间复杂度为O(n)。

5. 简述线性表、栈和队列的异同？

答：栈和队列都是操作位置受限的线性表，即对插入和删除操作的位置加以限制。栈是仅允许在表的一端进行插入和删除操作的线性表，因而是后进先出表。队列是允许在表的一端进行插入，在表的另一端进行删除的线性表，因而是先进先出表。线性表可以在任何位置进行插入和删除操作。

五、算法设计题

1. 设计一个算法，利用栈和队列的基本运算将指定栈中的元素顺序逆转。

解：算法基本思想：先将栈中元素出栈运算移至队列中，再将队列中元素出队列移至栈中。

void reverse(Stack &st)

{ Queue sq；

ElemType x;

InitQueue(sq)

while(!StackEmpty(st)

{ pop(st,x)

EnQueue(sq,x);

}

while(!QueueEmpty(sq)

{ DeQueue(sq,x);

Push(st,x);

}

DestroyQueue(sq);

}

2. 设计一个算法，利用栈的基本运算返回指定栈中栈底元素。

解：先将栈中元素依次移至另一个临时栈中，最后一个元素即为栈底元素，设为x. 。再将临时栈中元素移至原栈中，即恢复栈内容。

ElemType bottom(Stack &st)

{ ElemType x,y;

Stack tmpst;

InitStack(tmpst)

while(!StackEmpty(st)

{ pop(st,x)

push(tmpst,x);

}

while(!QueueStack(temst)

{ pop(tmpst,y); //此时必须用另一个变量y ，才能保留栈底元素在x 中 Push(st,y);

}

DestroyStack(tmpst);

return(x);

}

3. 设计一个算法，利用栈来实现带头结点的单链表h 的逆序。

解：算法基本思想：将单链表结点依次放入链栈中，链栈本身就是一个单链表，即实现了原单链表的逆序。假设链栈不带头结点，再加上原来的头结点，就完成了原单链表的逆序。

Void revert(SNode *h)

{ SNode *st=NULL,*p=h->next,q;

While(p)

{ q=p->next;

p->next=st;

st=p;

p=q;

}

h->next=st;

}

第四章 串

一、单选题

1. 串是任意有限个【 D 】。

A. 符号构成的集合 B. 符号构成的序列

C. 字符构成的集合 D. 字符构成的序列

2. 串是一种特殊的线性表，其特殊性体现在【 B 】。

A. 可以顺序存储 B. 数据元素是一个字符

C. 数据元素可以使多个字符 D. 可以链接存储

3. 两个串相等必有串长度相等且【 B 】。

A. 串的各位置字符任意 B. 串中各位置字符均对应相等

C. 两个串含有相同的字符 D. 两个串所含字符任意

4. 设有两个串p 和q ，求q 在p 中首次出现的位置的运算称着【 B 】。

A. 连接 B. 模式匹配

C. 求子串 D. 求串长

二、填空

1. 空串是。

2. 一个串中

3. 设s=“abcd ”，则执行语句s2=Substr(s,2,2)后，s2= 。

4. 空白串是 由一个或多个空格字符组成的串 ，其长度等于 其所包含的空格字符的个数 。

第五章 数组

一、单选题

1. 一维数组与线性表的区别是【 A 】。

A. 前者长度固定，后者长度可变

B. 后进长度固定，前者长度可变

C. 两者长度均固定 D. 两者长度均可变

2. 多维数组的数组元素之间的关系，【 A 】。

A. 是线性的 B. 是树型的

C. 既是线性的，又是树型的

D. 既不是线性的，也不是树型的

3. 设有数组A[8][10]，每个元素占3个存储单元，存放该数组的存储单元数为【 C 】。

A.80 B.100 C.240 D.270

4. 设有数组A[8][10]，每个元素占3个存储单元，首地址为SA ，则元素[7][5]的起始地址是

【 D 】。

A.SA+141 B.SA+144 C.SA+222 D.SA+225

5. 设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为【 C 】。

A.n*n B.n*n/2 C.n*(n+1)/2 D.(n+1)2/2

6. 设A 是一个n*n的对称矩阵，压缩存储到一个一维数组B[0..n(n+1)/2-1]中，则下三角部分元素ai,j 在B 中的位置是【 A 】。

A. i(i-1)/2+j-1 B. i(i-1)/2+j

C. i(i+1)/2+j-1 D. i(i+1)/2+j

7. 稀疏矩阵一般的压缩方法有两种，即【 C 】。

A. 二维数组和三维数组 B. 三元组和散列

C. 三元组和十字链表 D. 散列和十字链表

8. 设有一个10*10的对称矩阵A ，以行主次序进行压缩存储，每个元素占一个存储单元，a 1,1的地址是1，则A8,5的起始地址是【 B 】。

A.13 B.33 C.18 D.40

二、解答题

1. 设数组A[50][80]，其基地址为2000，每个元素占2个存储单元，以行序位主序顺序存储，回答下列问题：

（1）该数据组由多少元素？

（2）该数组占用多少存储单元？

（3）数组元素a[30][30]的存储地址是多少？

答：

（1）该数组有：50*80=4000个元素

（2）该数组占用4000*4=8000个存储单元

（3）loc(30,30)=2000+(30*80+30)*2=2000+4860=6860

第六章 树与二叉树

一、单选题

1. 有关二叉树下列说法正确的是【 B 】。

A. 二叉树的度为2 B. 一棵二叉树的度可以小于2

C. 一棵二叉树至少有一个结点的度为2 D. 二叉树中任何一个结点的度为2

2. 利用二叉链表存储树，则根结点的右指针是【 C 】。

A. 指向最左孩子 B. 指向最右孩子

C. 空 D. 非空

3. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为【 B 】。

A.9 B.11

C.15 D. 不确定

4. 一棵二叉树有1001个结点，其中叶结点的个数为【 D 】。

A.250 B.490

C.254 D. 不确定

5. 一棵完全二叉树有1001个结点，其中叶结点的个数为【 D 】。

A.250 B.500

C.254 D. 以上答案均不对

6. 一棵具有1025个结点的二叉树的高h 为【 C 】。

A.11 B.11

C.11至1025之间 D.10至1024之间

7. 一棵124个叶结点的完全树，最多具有【 B 】个结点。

A.247 B.248

C.249 D.251

8. 一棵具有10个叶结点的二叉树具有【 B 】度为2的结点。

A.8 B.9

C.10 D.11

9. 已知一棵完全二叉树有625个结点，叶结点的个数为【 C 】。

A.311 B.312

C.313 D. 其它

10. 一棵具有n 个结点的完全二叉树的高h 为【 AB 】。

A. ⎣log 2n ⎦+1 B. ⎡log 2n+1⎤

C.log 2n+1 D.log 2n-1

11. 由8个权值构造一棵哈夫曼树，该哈夫曼树有【 A 】个结点。

A.15 B.16

C.17 D.14

12. 由3个结点可以构造【 D 】种不同的二叉树。

A.2 B.3

C.4 D.5

13. 树最适合用来表示【 C 】。

A. 有序数据元素 B. 无序数据元素

C. 元素间具有分支层次关系的数据 D. 元素间无联系的数据

14. 下图中4棵二叉树中，【 C 】不是完全二叉树。

A. B. C. D.

15. 某二叉树的先序遍历序列和后序便利序列正好相反，则该二叉树一定是【 A 】。

A. 空或只有一个结点 B. 完全二叉树

C. 二叉排序树 D. 高度等于其结点数

16. 在一棵非空二叉树的中序遍历序列中，根结点的右边【 A 】。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点

C. 只有左子树上的部分结点 D. 只有左子树上的所有结点

17. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序【 A 】。

A. 不发生上改变 B. 发生改变

C. 不能确定 D. 以上都不对

18. 一棵满二叉树，m 个叶结点，n 个结点，深度为h ，则【 D 】。

A.n=h+m B.h+m=2n C.m=h-1 D.n=2 h -1

19. 设n ，m 是二叉树上的两个结点，在中序遍历时，n 在m 之前的条件是【 C 】。

A.n 在m 右方 B.n 是m 的祖先

C.n 在m 左方 D.n 是m 的子孙

20. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中包含的结点数最少为【 B 】。

A.2h B.2h-1 C.2h+1 D.h+1

二、判断题

【× 】1. 二叉树是一般树的特殊树型。

【√ 】2. 树与二叉树是两种不同的树形结构。

【× 】3. 对于有n 个结点的二叉树，其高度为log 2n 。

【√ 】4. 完全二叉树中，若一个没有左孩子，则它必定是叶结点。

【√ 】5. 一棵具有n 个结点的完全二叉树，从上到下、从左到右用自然数对结点进行编号，结点为i 的结点的左孩子的编号为2i(2i

【× 】6. 一棵树中的叶结点数一定等于与其对应的二叉树的叶结点数。

【√ 】7. 哈夫曼树是带权路径长度最短的树，路经上权值较大的结点离根最近。

【√ 】8. 哈夫曼树的结点个数不偶数。

三、填空题

1. 深度为k 的完全二叉树至少有K-1个结点，至多有K

2. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2, 则有。

i-1K 3. 一棵二叉树第i 层最多有个结点，一棵有n 个结点的满二叉树共有

个结点，共有 2K-1个叶结点。

4. 根据二叉树的定义，具有3个结点的二叉树共有是 。

5. 在一棵完全二叉树中，结点个数为n ，则编号最大的分支结点的编号为。

6. 在一棵完全二叉树中，编号i 和j 的两个结点处于同一层的条件i j

7. 具有n 个结点的二叉树采用二叉链表存储结构，共有 8. 具有n 个结点的二叉树中，如果有m 个叶结点，则一定有个度为2的结点，有 n-2m+1 个度为1的结点。

9. 在二叉树的链式存储结构中，指针p 所指结点为叶结点的条件是 10. 二叉树的先序序列和中序序列相等的条件是

11. 有一棵如下图所示的树，回答下列问题：

①这棵树的根结点是 a 。

②这棵树的叶子结点是 b,e,g,d 。

③结点c 的度为 2 。

④这棵树的深度是 4 。

⑤结点c 的孩子结点是 e,f 。

⑥结点c 的双亲结点是 a 。

⑦这棵树的度是 3 。

12. 树与二叉树的两个主要差别是 树中结点的最大度没有限制，二叉树结点的最大度限定为2 、 树的结点无左右之分，二叉树的的结点有左右之分 。

13. 树中任一结点允许有 0个或多个孩子 个孩子结点，除根结点之外，其余结点有 1 个双亲结点。

四、简答题

1. 设有如下图所示的二叉树，给出其前序、中序和后序遍历结果。

答： 前序序列：eadcbifghj

中序序列：abcdiefhgj

后序序列：bcidahjgfe

e

a f

d g

c j h i

b

2. 给出下图所示的树的二叉树表示。 e

a

d f

c b h g i

答：下图为其树的二叉树表示。

k

e

a

d

c f

b h j

g

i k

3. 有一份电文共有5个字符：a,b,c,d,e, 它们出现的频率依次为4，7，5，2，9，构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。

字符编码：

a ：011

b ：10

c ：00

d ：010

e ：11

4. 假设一棵二叉树采用顺序存储结构，如下图所示。

回答些列问题：

①画出二叉树表示。

②写出先序、中序和后序遍历结果

③写出结点c 的双亲结点和左、右孩子结点

④画出此二叉树还原成森林的图

②先序序列为：eadcbjfghi

中序序列为：acbdjefhgi

后序序列为：bcjdahigfe

③结点c 的双亲结点是d ，左孩子为

b ，无右孩子

④该二叉树对应的森林为

第七章 图

一、单选题

1. 在一个无向图中，所有顶点的度数之和等于所有边的【 C 】倍。

A.1/2 B.1 C.2 D.4

2. 在一个有向图中，所有顶点的入度数之和等于所有顶点的出度之和的【 B 】倍。

A.1/2 B.1 C.2 D.4

3. 一个有n 个顶点的无向图最多有【 C 】条边。

A.n B.n(n-1) C.n(n-1)/2 D.2n

4. 具有4个顶点的无向完全图有【 A 】条边。

A.6 B.12 C.16 D.20

5. 具有6个顶点的无向图至少应有【 A 】条边才能确保是一个连通图。

A.5 B.6 C.7 D.8

6. 一个有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是【 D 】。

A.n B. (n-1)2 C. (n-1) D. n2

7. 对某个无向图的邻接矩阵来说，【 A 】。

A. 第i 行上的非0元素个数等于第i 列上非0元素个数

B. 矩阵中非0元素个数等于图中的边数

C. 第i 行、第i 列上非0元素个数等于顶点vi 的度数

D. 矩阵中非全0行的行数等于图中的顶点数

8. 对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则表头向量的大小为【①

A 】；所有邻接表中结点总数为【② C 】 。

①A.n B.n+1 C.n-1 D.n2

②A.e/2 B.e C.2e D.n+e

二、判断题

【 ×】1.n 个顶点的无向图至多有n(n-1)条边。

【 √】2. 有向图中，各顶点的入度之和等于各顶点的出度之和。

【 √】3. 邻接矩阵只存储了边的信息，没有存储顶点的信息。

【 ×】4. 连通分量是无向图的极小连通子图。。

【 ×】5. 如果表示有向图的邻接矩阵是对称的，则该有向图一定是完全有向图。

【 ×】6. 如果表示图的邻接矩阵是对称的，则该图一定是无向图。

【 √】7. 如果表示图的邻接矩阵不是对称的，则该图一定是有向图。

三、填空题

1. 有n 个顶点的无向图最多有

2. 具有n 个顶点的强连通有向图至少有

3. 具有n 个顶点的有向图最多有

4. 一个图的

5. 具有10个顶点的无向图，边的总数最多为

6. 在有n 个顶点的有向图中，每个顶点的度最大可达。

7. 已知一个有向图采用邻接矩阵表示，计算第i 个顶点的入度的方法是。

8. 已知一个有向图的邻接矩阵表示，删除所有从第i 个结点出发的弧的方法是行对应的1置成0 。

9. 对于n 的顶点的无向图，采用邻接矩阵表示，求图中边的方法是

素值为1的个数 ，判断任意两个顶点是否有边相连的方法是 判断对应邻接矩阵元素的值是否为1，再除以2 ，求任意顶点的度的方法是 求邻接矩阵中对应顶点所在行值为1 的元素个数 。

10. 对于n 的顶点的有向图，采用邻接矩阵表示，求图中边的方法是元素值为1的个数 ，判断任意两个顶点是否有边相连的方法是 判断对应邻接矩阵元素的值是否为1 ，求任意顶点的度的方法是 求邻接矩阵中对应顶点所在行和列的元素值为1的个数 。

11. 无向图的连通分量指

12. 若无向图有m 条边，，则表示该无向图的邻接表中有结点。

四、简答题

1. 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表那个更好些？ 答：从占用存储空间看，稠密图采用邻接矩阵更好，稀疏图采用邻接表更好。

2. 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？为什么？。

答：用邻接矩阵表示图，矩阵元素的个数与图的顶点个数直接相关，与边的条数无关。因为假设定点个数为n ，则邻接矩阵的大小为n 2。

第九章 查找

一、单选题

1. 顺序查找法适合于存储结构为【 B 】的查找表。

A. 散列存储 B. 顺序存储或链式存储

C. 压缩存储 D. 索引存储

2. 对查找表进行折半查找时，要求查找表必须【 B 】。

A. 以顺序方式存储

B. 以顺序方式存储，且结点按关键字有序排列

C. 以链式方式存储

D. 以链式方式存储，且结点按关键字有序排列

3. 采用顺序查找法查找长度为n 的查找表时，每个元素查找的平均查找长度为【 C 】。

A.n B.n/2 C.(n+1)/2 D.(n-1)/2

4. 采用折半查找法查找长度为n 的查找表时，每个元素查找的平均查找长度为【 D 】。

A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)

5. 采用分块查找时，若查找表中有625个元素，查找每个元素的概率相同，假设对索引表和块都采用顺序查找，每块应分【 B 】个结点最佳。

A.10 B.25 C.6 D.625

6. 查找n 个元素的有序表时，最有效的查找方法是【 C 】。

A. 顺序查找 B. 分块查找 C. 折半查找 D. 二叉排序树

7. 如果要求一个查找表既能快速查找，又能适应动态变化的要求，可以采用【 A 】查找方法。

A. 分块 B. 顺序 C. 折半 D. 散列

8. 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【 B 】量级相当。

A. 顺序查找 B. 折半查找 C. 分块查找 D. 前三个都不正确

9. 查找效率最高的二叉排序树是【 C 】。

A. 所有结点的左子树都为空的二叉排序树

B. 所有结点的右子树都为空的二叉排序树

C. 平衡二叉树

D. 没有左子树的二叉排序树

10. 假定有k 个关键字互为同义词，若用线性探测再散列法把这k 个关键字的纪录插入到散列表中，至少要进行【 D 】次探测。

A.k-1 B.k C.k+1 D.k(k+1)/2

11. 以下说法错误的是【 B 】。

A. 散列法存储的基本思想是由记录关键字决定数据存储地址

B. 散列法的结点中只包含数据元素自身的信息，不包含任何指针

C. 装填因子是散列法的一个重要参数，它反映了散列表的装填程度

D. 散列表的查找效率取决于散列造表是的散列函数和冲突处理的方法

12. 散列表的平均查找长度【 A 】。

A. 与冲突处理方法有关而与表的长度无关

B. 与冲突处理方法无关而与表的长度有关

C. 与冲突处理方法有关且与表的长度有关

D. 与冲突处理方法无关且与表的长度无关

二、判断题

【 √】1. 顺序查找法适合于顺序或链式存储结构的查找表。

【 ×】2. 顺序查找法只能在顺序存储结构上进行。

【 ×】3. 二分查找可以在有序的双向链表上进行。

【 ×】4. 在二叉排序树中，每个结点的关键字比左孩子的关键字大，比右孩子的关键字小。

【 ×】5. 每个结点的关键字都比左孩子的关键字大，比右孩子的关键字小，这样的二叉树都是二叉排序树。

【 √】6. 哈希存储法只能存储数据元素的值，不能存储数据元素之间的关系。

【 ×】7. 哈希冲突是指同一个关键字对应多个不同的哈希地址。

三、填空题

1. 顺序查找含n 个元素的顺序表，若查找成功，则比较关键字的次数最多为若查找不成功，则比较关键字的次数为 n+1 次。

2. 在含有n 个元素的有序顺序表中进行二分查找，n

3. 用二分查找一个查找表，该查找表必须具有的特点是。

4. 分块查找发将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间 关键字有序 。

5. 在分块查找方法中，首先查找 ，然后再查找相应的。

6. 用二叉排序树在n 个元素中进行查找，最坏情况下查找时间复杂度为n

7. 折半查找的存储结构仅限于 顺序存储结构 ，且是 关键字有序排列 。

8. 一个无序序列可以通过构造一棵树而变成有序序列，构造树的过程即是对无序序列进行排序的过程。

9. 用二叉排序树查找，在最坏的情况下，平均查找长度为n+1

10. 在哈希函数H(key)=key/p中，p 最好取 。

11. 哈希表是通过将关键字按选定的按关键字转换为地址进行存储的存储表，哈希方法的关键是 选择好的哈希函数 和 冲突处理的方法 。一个好的哈希函数其转换地址应尽可能 均匀 ，而且函数运算应尽可能 简单 。

四、解答题

1、画出对长度为10的右序表进行折半查找的一棵判定树，并求其等概率时查找成功的平均查找长度。

平均查找长度=(1+2*2+4*3+3*4)/10=2.9

2、设有数据集合d={1，12，5，8，3，10，7，13，9}，回答下列问题：

① 依次取d 中各数据，构造一棵二叉排序树bt ；

② 如何依据此二叉排序树得到d 的一个有序序列。

②对该二叉排序树进行中序遍历，就可以得到d 的一个有序序列：

{1，3，5，7，8，9，10，12，13}

3. 若对具有n 个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列两种情况下分别讨论两者在等概率时的平均查找长度：

①查找不成功，即表中无关键字等于给定值k 的记录。

②查找成功，即表中有关键字等于给定值k 的记录。

答：①对无序表的顺序查找，需要进行n+1次比较才能确定查找失败。

对有序表的顺序查找，只要确定某个记录关键字不等于且大于给定k 值，就能确定

查找失败，即最少1次，最多n+1次，平均查找长度为（n+2）/2。

②查找成功，其平均查找长度均为（n+1）/2，有序表和无序表是一样的。

第十章 排序

一、单选题

1. 直接插入排序在最好的情况下的时间复杂度为【 A 】。

A.O(n) B.O(nlog2n) C.O(n2) D.O(log2n)

2. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为1）中的元素进行比较，将其放入已排序序列的正确位置的方法，称为【 B 】。

A. 冒泡排序 B. 插入排序 C. 选择排序 D. 归并排序

3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是【 A 】。

A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序

4. 在下列排序方法中，【 C 】排序方法可能出现：在最后一趟开始前，所有元素都不在最终的位置上。

A. 堆排序 B. 冒泡排序 C. 插入排序 D. 快速排序

5. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的后面的方法，称为【 D 】。

A. 希尔排序 B. 归并排序 C. 直接插入排序 D. 直接选择排序

6. 在对n 个元素的序列进行排序时，堆排序所需要的附加空间是【 A 】。

A.O(1) B.O(nlog2n) C.O(n) D.O(log2n)

7. 在待排序的元素序列基本有序的前提下，效率最差的排序方法是【 C 】。

A. 插入排序 B. 冒泡排序 C. 快速排序 D. 归并排序

8. 将两个各有n 个元素的有序表归并成一个有序表，其最小的比较次数为【 A 】。

A.n B.2n-1 C.2n D.n-1

9. 在下列排序方法中，要求内存量最大的方法【 D 】。

A. 直接插入排序 B. 选择排序 C. 快速排序 D. 归并排序

10. 如果对n 个元素进行直接选择排序，则进行一趟排序过程中，为寻找最小值元素所需要的时间复杂度为【 D 】。

A.O(1) B.O(log2n) C.O(n2) D.O(n)

11. 就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是【 A 】。

A. 堆排序

B. 堆排序

C. 堆排序>归并排序>快速排序

D. 堆排序>快速排序>归并排序

二、填空题

1. 每次从无序子表中取出一个元素，把它插入到有序子表中恰当位置，此种排序方法叫做 插入 排序；若每次从无序子表中挑选出最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 直接选择 排序。

2. 每次通过基准元素间接比较两个元素，不满足约定要求时就交换位置，该排序方法叫做 快速 排序；每次使两个相邻有序表合并成一个有序表的排序方法叫做 归并 排序。

叉树的结构。

4. 对n 个元素的表进行直接选择排序，所需要的关键字的比较次数为。

5. 在堆和快速排序中，若原始记录接近正序或反序，则选用若原始记录无序，则选用 快速 。

6. 在插入和选择排序中，若初始数据基本正序，则选用，若初始数据基本反序，则选用 选择 。

7. 在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取 方法，其次选择 快速排序 方法，最后选择 归并排序 方法；若只从平均情况下排序最快考虑，则应选取 快速排序 方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 堆排序 方法。