数据结构习题11级用

数 据 结 构 习 题

计算机学院专业基础教研室

2012年12月

1

前 言

数据结构是计算机相关专业教学计划中的一门核心课程，是有志从事计算机与技术工作的人员的一门重要的专业基础课程。计算机相关学科各领域都要用到各种数据结构，要从事这些领域的工作，尤其是计算机应用领域的开发研制工作，必须具备良好的数据结构基础。

数据结构课程的教学要求是学会分析研究计算机加工的数据对象的特征，以便在实际应用中选择适当的数据结构、存储结构和相应的算法，初步掌握算法的时间与空间性能分析技巧，得到复杂程序设计的训练。

我们在认真总结多年教学经验和体会的基础上，结合新时期大学生的学习特点和要求，编写了这本《数据结构习题》，作为数据结构课程学习的配套教材，以希望通过习题的求解，使学生更好地学习和掌握课程内容，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

由于时间仓促和编者水平所限，本书一定还存在着许多问题，敬请广大读者批评指正。

2

目 录

第一章 绪论????????????????????????????? 1 第二章 线性表???????????????????????????? 6 第三章 栈和队列???????????????????????????12 第四章 串?????????????????????????????‥19 第五章 数组和广义表????????????????????????‥22 第六章 树和二叉树????????????????????????‥‥28 第七章 图?????????????????????????????‥33 第九章 查找????????????????????????????‥38 第十章 内部排序???????????????????????????41

3

第一章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）

A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法

C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性

4．一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（ ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ ）

(1)算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算

法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（ ）？

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（ ）

1

A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（①）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 12．在以下的叙述中，正确的是（①）。

A．线性表的线性存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出

13．以下哪个数据结构不是多型数据类型（ ）

A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（ ）是非线性数据结构

A．树 B．字符串 C．队 D．栈 15. 下列数据中，（ ）是非线性数据结构。

A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（ ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 17．以下属于逻辑结构的是（ ）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表 18.一个数据对象是（ ）的集合。

A.相同类型的数据项 B.相同类型的数据元素

C.不同类型的数据项 D.不同类型的数据元素 19. ( )是数据的基本单位。

A.数据项 B.关键字 C.数据元素 D.数据类型 20.数据结构在计算机中的表示称为数据( )。 A.对象 B.的存储结构 C.类型 D.元素 21.下列程序段的时间复杂度为( )。 { for(i=0；i<5；i++) for(j=0；j

A.O(5) B.O(5+n) C.O(n5 ) D.O(n)

22．数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间

2

的（②）和运算等的学科。

①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象 ②A．结构 B．关系 C．运算 D．算法

23．数据结构被形式地定义为（K，R），其中K是（①）的有限集合，R是K上的（②）

的有限集合。

①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 24．在数据结构中，从逻辑上可以把数据结构分成（①）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

25．线性表的顺序存储结构是一种（①）的存储结构，线性表的链式存储结构是一种 （②）的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取 26．算法分析的目的是（①），算法分析的两个主要方面是（②）。 ①A．找出数据结构的合理性

B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性

D．数据复杂性和程序复杂性

27．计算机算法指的是（①），它必具备输入、输出和（②）等五个特性。

①A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法 ②A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性

28．线性表的逻辑顺序与存储顺序总是一致的，这种说法（①）。 A．正确 B．不正确

二、填空题

1．数据的物理结构包括 的表示和 的表示。

3

2. 对于给定的n个元素,可以构造出的逻辑结构有 （1） ， （2） ， （3） ，

__（4）四种。

3．数据的逻辑结构是指 。

4．一个数据结构在计算机中 称为存储结构。

5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内

部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。 6．数据结构中评价算法的两个重要指标是

7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这

种结构定义相应的_（3）_，设计出相应的（4）_。

8． 一个算法具有5个特性: （1） 、 （2） 、 （3） ，有零个或多个输入、有一

个或多个输出。

9． 下面程序段的时间复杂度为________。(n>1) sum=1；

for (i=0;sum

10．计算机执行下面的语句时，语句s的执行次数为 _______ 。 FOR(i=l；i=i;j--) s;

11.下面程序段中带下划线的语句的执行次数的数量级是：

i：=1； WHILE i

三、基础知识题

1．数据结构是一门研究什么内容的学科？

2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

3．数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类

型的主要特点是什么？使用抽象数据类型的主要好处是什么？ 4．回答问题（每题2分）

（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存

在着怎样的关系？

（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？

举例说明之。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同

的数据结构。这样说法对吗？举例说明之。 （4）评价各种不同数据结构的标准是什么？

4

5．评价一个好的算法，您是从哪几方面来考虑的？ 6．解释和比较以下各组概念 抽象数据类型及数据类型 数据结构、逻辑结构、存储结构 抽象数据类型

算法的时间复杂性（5） 算法（6）频度

7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？ 8．对于一个数据结构，一般包括哪三个方面的讨论？

9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？

10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？ 11．数据结构与数据类型有什么区别？

12．数据的存储结构由哪四种基本的存储方法实现？

13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最

方便，写出这些结构？

14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存

储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。

15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?

16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运

算效率不同。

17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的

时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。 18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月

日、储蓄类型、存入累加数、利息、帐面总数。

5

n

第二章 线性表

一 、 选择题

1．下述哪一条是顺序存储结构的优点？（ ）

A． 存储密度大 B．插入运算方便

B． C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运

算，则利用（ ）存储方式最节省时间。 A．顺序表

B．双链表

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

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省

时间。 A. 单链表

B.单循环链表

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

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A．单链表 B．双链表

C．单循环链表 D．带头结点的双循环链表 8. 静态链表中指针表示的是（ ）.

A． 内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

6

9. 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 10. 下面的叙述不正确的是（ ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

11． 双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链

表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）

A．p^.llink^.rlink:=p^.llink; p^.llink^.rlink:=p^.rlink; dispose(p); B．dispose(p); p^.llink^.rlink:=p^.llink; p^.llink^,rlink:=p^.rlink; C．p^.llink^.rlink:=p^.llink; dispose(p); p^.llink^.rlink:=p^.rlink; D．以上A，B，C都不对。

12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第

i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（ ）

A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）

13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法

的时间复杂度为（ ）(1<=i<=n+1)。

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

14. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 15．线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）

A．O（i） B．O（1） C．O（n） D．O（i-1） 16．非空的循环单链表head的尾结点p↑满足（ ）。

A．p↑.link=head B．p↑.link=NIL C．p=NIL D．p= head 17．循环链表H的尾结点P的特点是（ ）。

A．P^.NEXT:=H B．P^.NEXT:= H^.NEXT C．P:=H D．P:=H^.NEXT

7

18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（）

A. p＾.next=h B. p＾.next=NIL C. p＾.next.＾next=h D. p＾.data=-1 19．完成在双循环链表结点p之后插入s的操作是（ ）；

A． p^.next:=s ; s^.priou:=p; p^.next^.priou:=s ; s^.next:=p^.next; B． p^.next^.priou:=s; p^.next:=s; s^.priou:=p; s^.next:=p^.next; C． s^.priou:=p; s^.next:=p^.next; p^.next:=s; p^.next^.priou:=s ; D． s^.priou:=p; s^.next:=p^.next; p^.next^.priou:=s ; p^.next:=s; 20．在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。

注:双向链表的结点结构为(llink,data,rlink)。 供选择的答案：

A． p↑.llink：=q； q↑.rlink：=p； p↑.llink↑.rlink：=q；q↑.llink：=q； B． p↑.llink：=q； p↑.llink↑.rlink：=q ； q↑.rlink：= p； q↑.llink:=p↑.llink；

C． q↑.rlink：=p； q↑.llink：=p↑.llink； p↑.llink↑.rlink：=q; p↑.llink：=q;

D． q↑.llink:=p↑.llink；q↑.rlink:=p； p↑.llink：=q；p↑.llink：=q； 21．在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为: rlink(p) ← q; llink(p) ← llink(q); llink(q) ← p; （ ）

A．rlink(q) ← p B．rlink(llink(q)) ← p C．rlink(llink(p)) ← p D．rlink(rlink(p)) ← p

22． 双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ ） A. p＾.llink:=q; q＾.rlink:=p; p＾.llink＾.rlink:=q; q^.llink:=p^.llink;

B. q＾.llink:=p^.llink; p＾.llink^.rlink:=q; q＾.rlink:=p; p^.llink:=q^.rlink;

C. q^.rlink:=p; p^.rlink:=q; p^.llink^.rlink:=q; q^.rlink:=p; D. p^.llink^.rlink:=q; q^.rlink:=p; q^.llink:=p^.llink; p^.llink:=q; 23．在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 A. p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q； B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink; C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q; D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;

8

24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;

25．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 26. 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。 A． (p^.llink)^.rlink:=p^.rlink (p^.rlink)^.llink:=p^.llink; B． p^.llink:=(p^.llink)^.llink (p^.llink)^.rlink:=p; C． (p^.rlink)^.llink:=p p^.rlink:=(p^.rlink)^.rlink D． p^.rlink:=(p^.llink)^.llink p^.llink:=(p^.rlink)^.rlink;

二、填空题

1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。

2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。

3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;

4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。

5．在单链表中设置头结点的作用是________。

6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。 7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。

8．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、

_______、_______、________。

9．在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：

s^ .next:=p； s^ .prior:= ________；p^ .prior:=s；________:=s； 10.链接存储的特点是利用________来表示数据元素之间的逻辑关系。

11.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过

9

________表示元素之间的关系的。

12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链

表为_______个。

13. 循环单链表的最大优点是：________。

14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________ 15. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 16. 在单链表L中，指针p所指结点有后继结点的条件是：__ 17.带头结点的双循环链表L为空表的条件是：________。 18. 在单链表p结点之后插入s结点的操作是：_______。

三、解答题

1．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性

表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取

线性表中的元素，那么应采用哪种存储结构？为什么？

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大

量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

3．若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？

为什么？

4．线性结构包括______、______、_______和_______。线性表的存储结构分成______

和______。请用类PASCＡL语言描述这两种结构。

5．线性表（a1，a2，?，an）用顺序映射表示时，ai和ai+1（1<=i

6. 说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首

元结点的关系。

7. 试述头结点,首元结点,头指针这三个概念的区别.

8．有线性表(a1,a2,?,an),采用单链表存储，头指针为H，每个结点中存放线性表中一个元素，现查找某个元素值等于X的结点。分别写出下面三种情况的查找语句。要求时间尽量少。

（1）线性表中元素无序。（2）线性表中元素按递增有序。 （3）线性表中元素按递减有序。

10

9. 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?

10. 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链

表？

11. 设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C

语言语句。

12. 设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，

请写出在p结点之前插入s结点的操作（PASCAL语句）。

四、算法设计题

1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法

将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

2. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点

个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 3．在带头结点的单链表上，给出求表长Length(L)的算法，并加入简要的注释或说

明。

4．设单链表具有头结点，且表中元素各不相同，试给出在单链表中查找值为\的结

点的算法，并加入简要的注释或说明。

5．设单链表具有头结点，且表中元素各不相同，试给出在单链表中删除值为\的结点的算法。

11

第三章 栈和队列

一、 选择题

1. 对于栈操作数据的原则是（ ）。

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

2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

③ , ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.

3. 一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定 B. n-i+1 C. i D. n-i

4. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。

A. i-j-1 B. i-j C. j-i+1 D. 不确定的

5. 若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定

6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）

A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4，

12

8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ ）。

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列

的是（ ）。

A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b

11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的

序列为（ ）。

A．fedcba B. bcafed C. dcefba D. cabdef

12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排

列是( )。

A．XYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

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 14. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确

操作是( )。

A．top:=top+1; V [top]:=x B. V [top]:=x; top:=top+1 C. top:=top-1; V [top]:=x D. V [top]:=x; top:=top-1 15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i

=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 17. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 18. 执行完下列语句段后，i值为：（ ） int f(int x)

{ return ((x>0) ? x* f(x-1):2);}

13

int i ; i =f(f(1));

A．2 B. 4 C. 8 D. 无限递归 19. 表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

20. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），

其中^为乘幂 。

A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(-

21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构

最佳。

A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈

22. 用链接方式存储的队列，在进行删除运算时（ ）。

A. 仅修改头指针

B. 仅修改尾指针 D. 头、尾指针可能都要修改

C. 头、尾指针都要修改

23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向

队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

24. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结

构。

A．队列 B．多维数组 C．栈 D. 线性表

25. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前

队列中的元素个数为（ ）。 A．(rear-front+m)%m C．(front-rear+m)%m

B．rear-front+1 D．(rear-front)%m

26. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则

当前队列中的元素数是( )。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front

27. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。

A. rear=rear+1 B. rear=(rear+1) mod (m-1)

14

C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

28. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0

和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

29. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 30. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也

不能由输出受限的双端队列得到的输出序列是( )。 A. 1234 B. 4132 C. 4231 D. 4213

31. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是

（ ）。

C．rear+1=front D. (rear-l) MOD n=front

32. 栈和队列的共同点是（ ）。

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

33. 栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。若

进栈序列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出

C. 进优于出 D. 出优于进

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

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

④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 34. 栈和队都是（ ）

A．顺序存储的线性结构 B. 链式存储的非线性结构 C. 限制存取点的线性结构 D. 限制存取点的非线性结构

35. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，

一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。

15

A. (rear+1) MOD n=front B. rear=front

A． 6 B. 4 C. 3 D. 2 36. 用单链表表示的链式队列的队头在链表的（ ）位置。

A．链头 B．链尾 C．链中

37. 依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求

下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？

A．{d ，e，c，f，b，g，a} B. {f，e，g，d，a，c，b} C. {e，f，d，g，b，c，a} D. {c，d，b，e，f，a，g}

二、填空题

1．栈是_______的线性表，其运算遵循_______的原则。 2．_______是限定仅在表尾进行插入或删除操作的线性表。

3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。

4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，

经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。

6．两个栈共享空间时栈满的条件_______。

7．在作进栈运算时应先判别栈是否_(1)_;在作退栈运算时应先判别栈是否_(2)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)_。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_(4)_分别设在内存空间的两端，这样只有当_(5)_时才产生溢出。 8. 多个栈共存时，最好用_______作为存储结构。

9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342

出栈顺序，相应的S和X的操作串为_______。

10. 顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是

_______。

11．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。

12. 循环队列的引入，目的是为了克服_______。 13．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效

下标范围内循环， M= _______。 14．________又称作先进先出表。

16

15. 队列的特点是_______。

16．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是

_______。

17. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 18．区分循环队列的满与空，只有两种方法，它们是______和______。

19．设循环队列用数组A[1..M]表示，队首、队尾指针分别是FRONT和TAIL，判定队

满的条件为_______。

20. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的

出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。

三、基础知识题 1．名词解释：栈。 2．名词解释：队列 3．什么是循环队列？

4．假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。

（1）试指出判别给定序列是否合法的一般规则。

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得

到，请举列说明。

5. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 6.如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。

7. 若元素的进栈序列为：A、B、C、D、E，运用栈操作，能否得到出栈序列B、C、A、E、D 和D、B、A、C、E？为什么？

8. 设输入序列为a,b,c,d,试写出借助一个栈可得到的两个输出序列和两个不能得到的输出序列。

9. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？

10. 试证明：若借助栈由输入序列1,2,?,n得到输出序列为P1,P2,?,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i

11. 设一数列的输入顺序为123456，若采用堆栈结构，并以A和D分别表示入栈

17

第六章 树和二叉树

一、选择题

1．树最适合用来表示（ ）。

A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 2．深度为5的二叉树至多有（ ）个结点。

A． 16 B． 32 C． 31 D． 10

3．有32个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5

4．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（ ）个叶结

点。

A．25 B．15 C．16 D．41

5．在有n个结点的二叉链表中值为非空的链域的个数为（ ）。

A． n-1 B 2n-1 C n+1 D 2n+1

6．有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A．8 B．7 C．6 D．5

7．对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列

均相同。

A． 3 B． 1 C． 2 D． 不存在

8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）二叉树。 A． 空或只有一个结点 B． 高度等于其结点数 C． 任一结点无左孩子 D． 任一结点无右孩子

9．前序遍历与中序遍历结果相同的二叉树为（ ）；前序遍历和后序遍历结果相同的二叉树为（ ）。

A．一般二叉树 B．只有根结点的二叉树

C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子树的二叉树 F．所有结点只有右子树的二叉树

10．设n, m为一棵二叉树上的两个结点，在中序遍历时n在m前的条件是（ ）。

A． n在m右方 B． n在m左方 C． n是m祖先 D． n是m子孙

11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（ ）。

A． 不发生改变 B． 发生改变

28

C． 不能确定 D． 以上都不对 12．线索二叉树是一种（ ）结构。

A． 逻辑 B． 逻辑和存储 C． 物理 D． 线性

13. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先

序遍历、中序遍历和后序遍历。如把由树转化得到的二叉树叫做这棵树对应的二叉树，则结论（ ）是正确的。

A． 树的先根遍历序列与对应的二叉树的先序遍历序列相同 B． 树的后根遍历序列与对应的二叉树的后序遍历序列相同 C． 树的先根遍历序列与对应的二叉树的中序遍历序列相同 D． 以上都不对

14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数

至少为（ ）。

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

15. 设bt是某树的二叉树表示的根结点指针，则bt满足（ ）。

A． bt->lchild==bt->rchild B． bt->rchild==NULL C． bt->lchild==NULL D． bt==NULL

16．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（ ）。

A．2n+2 B． 2n+1 C． 2n D． 2n-1

17．设哈夫曼树的叶子结点数为n，则它的结点总数为（ ）。

A． 2n-1 B． 2n C． 2n+1 D． 不确定

18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（ ）。

A． 50 B． 60 C. 52 D. 65

19．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根

的右子树的根是（ ）。

A． E B． F C. G D. H 20．下列有关二叉树的叙述中正确的是（ ）。

A． 二叉树的度为2

B． 任何一棵二叉树中至少有一个结点的度为2 C. 度为0的树是一棵二叉树 D. 二叉树中任何一个结点的度为2 21．二叉树上叶结点数等于（ ）。

A． 分支结点数加１ B． 单分支结点数加１ C. 双分支结点数加１ D. 双分支结点数减１ 22．判断线索二叉树中p所指结点由左孩子的条件是（ ）。

29

A． p!=UNLL B． p->lchild!=NULL C. p->ltag==0 D. p->ltag==1

二、填空题

1. 具有n个结点的完全二叉树的深度为 。 2. 二叉树第i层上最多有 个结点。 3. 深度为k的二叉树最多有 个结点。

4．具有n个结点的二叉树的最小深度为 ，最大深度为 ；具有具有n个结点的度为2的树的最小深度为 ，最大深度为 。 5．具有m个叶结点的huffman树共有 个结点。

6．完全二叉树T按顺序存放，编号依次为1,2,...,n,则编号为i的结点左孩子如果存在的话，其编号为 。

7．在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。 8．三个结点a,b,C．组成二叉树，共有 种不同的结构。

9. 一颗树T中，包括1个度为1的结点，2个度为2的结点，3个度为3的结点，则T的叶子结点数为 。

10．已知某完全二叉树采用顺序存储结构，结点的存放顺序为（A,B,C,D,E,F,G,H,I,J），该完全二叉树的后根遍历序列为 。 11．前序遍历序列是abc且后序遍历序列为cba的二叉树共有 棵。

12. F是由T1, T2, T3三棵树组成的森林，T1, T2, T3 的结点数分别为n1,n2,n3,则F对应的二叉树B(F)的根的左子树中结点数为 ，根的右子树中的结点数为 。

三、基础知识题

1．已知一棵树遍的集合为{,,,,, , ,

,,,,,}, 请画出这棵树，并回答下列问题： (1) 哪个是根结点？ (2) 哪些是叶子结点？ (3) 哪个是结点g的双亲？ (4) 哪些是结点g的祖先？ (5) 哪些是结点g的孩子？ (6) 哪些是结点e的子孙？

(7) 哪些是结点e的兄弟？哪些是结点f的兄弟？ (8) 结点b和n的层次号分别是什么？

30

(9) 树的深度是多少？

(10) 以结点c为根的子树的深度是多少？ (11) 树的度数是多少？

2．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，?，nk个度为k

的结点，问该树中有多少个叶子结点？

4．对题2所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 5．现有按先序遍历二叉树的结点序列为abc，试写出能得到这一遍历结果的各种二

叉树。

6．一棵非空的二叉树其先序序列和后序序列正好相反，说明这棵二叉树的形状。 7．分别画出和下列树对应的二叉树。

A B

8．画出和下列二叉树相应的森林。

A B

9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权

路径长度。

10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出

31

该树并给出其后序序列。

12. 已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,

试画出该二叉树形状（要求写出中间过程）， 并写出它的先序遍历序列。 13. 设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设

计huffman编码并画出对应huffman树。

14. 对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带

权路径长度。

15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15, 18,23，

构造一棵huffman树，并给出每个字符的huffman编码。

16. 设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求：

(1) 画出该二叉树(要求写出中间步骤); (2)将这棵二叉树转换成对应的树(或森林)。

17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21,

10, 要求： (1) 为每个字母设计huffman编码, (2) 给出八个字母二进制表示的等长编码并比较两方案的优缺点。

18．证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。

19. 证明一棵二叉树无论进行先序、中序或后序遍历，其叶结点的相对次序不发生改

变。

四、算法设计题

1．试给出二叉树先序遍历的非递归形式的算法。 2．试写出按层次遍历二叉树的算法。

3．以二叉链表作存储结构，试编写求二叉树深度的算法。

4．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上叶子结点个数。 5．设一棵二叉树以二叉链表存储，试设计算法求此二叉树上度为2的结点个数。 6．试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子结点个数。 7．设计一个算法，统计二叉树中 等于给定值x的结点个数。 8．设计一个算法，从一棵二叉树中查找出所有结点的最大值。 9．编写递归算法，将二叉树中所有结点的左、右子树相互交换。

10．编写求任意二叉树中一条最长的路径的算法，要求输出此路径上各结点的值及路径的长度。

11．设一棵树以孩子-兄弟表示法存储，试编写计算树的深度的算法。

32

本文来源：https://www.bwwdw.com/article/wow7.html