数据结构课后答案

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

第一章 绪论 一、选择题

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

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

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

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（ B ） 。

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

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

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

（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 11．在下面的程序段中，对 x 的赋值语句的频度为（ C ） For（i=1;i<=n;i++） For（j=1;j<=n;j++） x=x+1;

A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段For（i= n; i<=1;i--） For（j=1;j<=i;j++） IF A[j]>A[j+1]

THEN A[j]与A[j+1]对换；

其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D ） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 14．以下数据结构中， （ A ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 16．连续存储设计时，存储单元的地址（ A ） 。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

二、判断题

1. 数据元素是数据的最小单位。( × ) 2. 记录是数据处理的最小单位。 ( × )

3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；(× ) 4．算法的优劣与算法描述语言无关，但与所用计算机有关。( × ) 5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 (√ )

1

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

6．算法可以用不同的语言描述，如果用 C 语言或 C++语言等高级语言来描述，则算法实际上就是程序了。(× ) 7．程序一定是算法。(× )

8．数据的物理结构是指数据在计算机内的实际存储形式。(√ ) 9. 数据结构的抽象操作的定义与具体实现有关。( × )

10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(× ) 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(× )

12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(√ ) 13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( × ) 三、填空

1．数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。

2. 对于给定的 n 个元素,可以构造出的逻辑结构有 线性结构（1） ，树形结构（2），图形结构（3），（4）集合四种。

3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 。

4．一个数据结构在计算机中 表示（又称映像） 称为存储结构。

5．抽象数据类型的定义仅取决于它的一组逻辑特性（1），而与在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性（3）不变，都不影响其外部使用。

6．数据结构中评价算法的两个重要指标是 时间复杂度 和 空间复杂度 。

7. 数据结构是研讨数据的逻辑结构（1）和物理结构（2），以及它们之间的相互关系，并对与这种结构定义相应的操作（3），设计出相应的算法（4）。

8． 一个算法具有 5 个特性: 有穷性（1） 、 确定性（2） 、 可行性（3） ，有零个或多个输入、有一个或多个输出。 11.下面程序段中带下划线的语句的执行次数的数量级是：log2n i=1； WHILE i

12. 下面程序段中带下划线的语句的执行次数的数量级是( nlog2n )。 i=1； while (i

for(i=1;i<=n;i++)

x=x+1； i=i*2；

15. 下面程序段的时间复杂度为____ O(n) ____。(n>1) sum=1；

for (i=0；sum

8．对于一个数据结构，一般包括哪三个方面的讨论？ 逻辑结构、存储结构、操作（运算）

第二章 线性表 一 选择题

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

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有 n 个（ C ）的有限序列（n>0） 。

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

2

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ D ）存储方式最节省运算时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 9. 链表不具有的特点是（ B ）

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

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

13. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

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

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

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 位置元素的时间复杂性为（ C ）

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

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

A．P->NEXT=H B．P->NEXT= H->NEXT C．P=H D．P=H->NEXT 18．在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A） A. p->next=h B. p->next=NIL C. p->next.＾next=h D. p->data=-1 19．完成在双循环链表结点 p 之后插入 s 的操作是（ D ） ；

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;

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

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;

24．在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是： （ B ） 。 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 的带头结点的单链表，判定该表为空表的条件是（ B ） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 二、判断

1. 链表中的头结点仅起到标识的作用。( × )

2. 顺序存储结构的主要缺点是不利于插入或删除操作。(√)

3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√ ) 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × )

3

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

5. 对任何数据结构链式存储结构一定优于顺序存储结构。(×) 6．顺序存储方式只能用于存储线性结构。( ×) 7．集合与线性表的区别在于是否按关键字排序。( × ) 8. 所谓静态链表就是一直不发生变化的链表。( × ) 9. 线性表的特点是每个元素都有一个前驱和一个后继。(× ) 10. 取线性表的第 i 个元素的时间同 i 的大小有关. ( × ) 11. 循环链表不是线性表. ( × )

12. 线性表只能用顺序存储结构实现。( ×) 13. 线性表就是顺序存储的表。( × )

14．为了很方便的插入和删除数据，可以使用双向链表存放数据。( √ ) 15. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × )

16. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( √ ) 三、填空

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

5．在单链表中设置头结点的作用是___主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。

10．链接存储的特点是利用__指针______来表示数据元素之间的逻辑关系。

11.顺序存储结构是通过___物理上相邻_____表示元素之间的关系的;链式存储结构是通过____指针____表示元素之间的关系的。 12. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 __4____个，单链表为____2___个。 15. 带头结点的双循环链表 L 中只有一个元素结点的条件是：__L->next->next==L______ 16. 在单链表 L 中，指针 p 所指结点有后继结点的条件是：_p->next!=null_ 17.带头结点的双循环链表 L 为空表的条件是：__L->next==L && L->prior==L______。 18. 在单链表 p 结点之后插入 s 结点的操作是：__s->next=p->next;p->next=s;_____。 四 应用题

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

（1）如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？

（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O（1）。 （2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。

2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

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

采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

第三章 栈和队列 一 选择题

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

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

①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底

4

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

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

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

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

3. 一个栈的输入序列为 123?n，若输出序列的第一个元素是 n，输出第 i（1<=i<=n）个元素是（ B ） 。 A. 不确定 B. n-i+1 C. i D. n-i

4. 若一个栈的输入序列为 1,2,3,?,n，输出序列的第一个元素是 i，则第 j 个输出元素是（ D ） 。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

5. 若已知一个栈的入栈序列是 1,2,3,?,n，其输出序列为 p1,p2,p3，?，pN,若pN 是 n，则 pi 是( D )。 A. i B. n-i C. n-i+1 D. 不确定

11. 设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ D ） 。 A．fedcba B. bcafed C. dcefba D. cabdef 13. 输入序列为 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

14. 若一个栈以向量 V[1..n]存储，初始栈顶指针 top 为 n+1，则下面 x 进栈的正确操作是( C )。 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]，则栈满的条件是（ B ） 。

A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 栈在（ D ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 19. 表达式a*(b+c)-d 的后缀表达式是( B )。

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

20. 表达式3* 2^(4+2*2-6*3)-5 求值过程中当扫描到 6 时，对象栈和算符栈为（ D ） ，其中^为乘幂 。 A. 3,2,4,1,1；(*^(+*- B. 3,2,8；(*^- C. 3,2,4,2,2；(*^(- D. 3,2,8；(*^(-

21. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 22. 用链接方式存储的队列，在进行删除运算时（D ） 。

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

23. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。 A．仅修改队头指针 B. 仅修改队尾指针

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

30. 若以 1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( C )。

A. 1234 B. 4132 C. 4231 D. 4213

31. 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ B ） 。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 32. 栈和队列的共同点是（ C ） 。

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

33. 栈的特点是（ ① B ）,队列的特点是（ ② A ）,栈和队列都是（ ③ C ） 。若进栈序列为 1,2,3,4 则（ C ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈） ；若进队列的序列为 1,2,3,4 则（ ⑤ F ）是一个出队列序列。

①, ②: 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

5

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

34. 栈和队都是（ C ）

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

35. 设栈S和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和e6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 2

36. 用单链表表示的链式队列的队头在链表的（ A ）位置。 A．链头 B．链尾 C．链中 1. 消除递归不一定需要使用栈，此说法（ √ ） 2. 栈是实现过程和函数等子程序所必需的结构。 （√ ）

3. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。 （ √ ）

4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （ √ ）

5. 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。 （ × ） 6. 有 n 个数顺序（依次）进栈，出栈序列有 Cn 种，Cn=[1/（n+1）]*（2n）!/[(n!)*(n!)]。 （ √ ） 8. 若输入序列为 1,2,3,4,5,6,则通过一个栈可以输出序列 3,2,5,6,4,1. （ √ ） 9. 栈和队列都是限制存取点的线性结构。 （ √ ）

12. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。 （× ）

13. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ × ） 14. 通常使用队列来处理函数或过程的调用。 （ × ）

15. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。 （√ ） 16. 循环队列通常用指针来实现队列的头尾相接。（ × ） 17. 循环队列也存在空间溢出问题。 （ √ ）

18. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。 （× ） 19. 栈和队列都是线性表， 只是在插入和删除时受到了一些限制。 （ √ ） 20. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 （ √ ）

三 填空题

1．栈是___操作受限____的线性表，其运算遵循__后进先出_____的原则。 2．___栈____是限定仅在表尾进行插入或删除操作的线性表。

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

4. 设有一个空栈，栈顶指针为 1000H(十六进制)，现有输入序列为 1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是__23_____，而栈顶指针值是__100C_____H。设栈为顺序栈，每个元素占 4 个字节。

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

6．两个栈共享空间时栈满的条件__两栈顶指针值相减的绝对值为1（或两栈顶指针相邻）_____。 8. 多个栈共存时，最好用__链式存储结构_____作为存储结构。

9．用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S和X 的操作串为___S×SS×S××____。

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

11．表达式23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是__23.12.3*2-4/34.5*7/++108.9/+（注：表达式中的点(.)表示将数隔开，如23.12.3是三个数）

12. 循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_____。 14．___队列_____又称作先进先出表。 15. 队列的特点是__先进先出_____。

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

17. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是___s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；____。

18．区分循环队列的满与空，只有两种方法，它们是__牺牲一个存储单元 ____和____设标记__。

6

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

21．表达式求值是__栈 _____应用的一个典型例子。

22．循环队列用数组 A[0..m-1]存放其元素值，已知其头尾指针分别是 front 和 rear ，则当前队列的元素个数是__（rear-front+m）% m_____。

23．设 Q[0..N-1]为循环队列，其头、尾指针分别为 P 和 R，则队 Q 中当前所含元素个数为____（R-P+N）% N___。 第四章 串 一、选择题

1．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘8’ ),length(S2))) 其结果为（ E ）

A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234

3．设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ C ） A．求子串 B．联接 C．匹配 D．求串长 8．若串S=’software’,其子串的数目是（ B ） 。 A．8 B．37 C．36 D．9

9．设 S 为一个长度为 n 的字符串，其中的字符各不相同，则 S 中的互异的非平凡子串（非空且不同于 S本身）的个数为（ D ） 。

A．2n-1 B．n2 C．(n2/2)+(n/2) D．(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况 10．串的长度是指（ B ）

A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数

二、判断题

1．串是一种数据对象和操作都特殊的线性表。 （ √ ） 二、填空题

1．空格串是指__(1) 由空格字符（ASCII值32）所组成的字符串__，其长度等于_空格个数__(2)__。 2．组成串的数据元素只能是___字符_____。

3．一个字符串中_____任意个连续的字符组成的子序列___称为该串的子串 。 4．INDEX（ ‘DATASTRUCTURE’ ， ‘STR’ ）=___5_____。

8．设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为__模式匹配(1)__，又称P 为__模式串(2)__。

9．串是一种特殊的线性表，其特殊性表现在_其数据元素都是字符_(1)__；串的两种最基本的存储方式是_顺序存储_(2)__、_链式存储_(3)__；两个串相等的充分必要条件是__(4) 串的长度相等且两串中对应位置的字符也相等__。

10．两个字符串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等。_____。 11．知U=‘xyxyxyxxyxy’ ；t=‘xxy’ ； ASSIGN（S，U） ；

ASSIGN（V，SUBSTR（S，INDEX（s，t） ，LEN（t）+1） ） ； ASSIGN（m， ‘ww’ ）

求REPLACE（S，V，m）= ____’xyxyxywwy’____。 第五章 数组 一、选择题

1.设有一个10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ B ） 。

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

8. 二维数组 A 的元素都是 6 个字符组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范圈从 1 到 10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。

（1）存放 A 至少需要（ E ）个字节；

（2）A 的第 8 列和第 5 行共占（ A ）个字节；

7

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

（3）若 A 按行存放，元素 A[8，5]的起始地址与 A 按列存放时的元素（ B ）的起始地址一致。 供选择的答案：

（1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

12. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 T[N（N+1）/2]中，则对任上三角元素a[i][j]对应T[k]的下标k 是（ B ） 。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1

13. 设二维数组 A[1.. m，1.. n]（即 m 行 n 列）按行存储在数组 B[1.. m*n]中，则二维数组元素 A[ij]在一维数组 B 中的下标为( A )。

A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 15. 数组A[0..4,-1..-3,5..7]中含有元素的个数（ B ） 。 A. 55 B. 45 C. 36 D. 16 17. 对稀疏矩阵进行压缩存储目的是（ C ） 。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度

二、判断题

2. 从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。（√ ） 3. 稀疏矩阵压缩存储后，必会失去随机存取功能。（√ ） 4. 数组是同类型值的集合。 （× ）

5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。 （ ×）

6. 一个稀疏矩阵 Am*n 采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把 m 和n 的值互换，则就完成了 Am*n 的转置运算。（ × ）

三、 填空题

1. 数组的存储结构采用__顺序存储结构_____存储方式。

3. 设数组 a[1..50,1..80]的基地址为2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_9174（1）_;若以列序为主序顺序存储，则元素 a[45,68]的存储地址为_8788（2）_。

4. 将整型数组 A[1..8，1..8]按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A[7，3]的地址是：___1100____。 6. 设有二维数组 A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为 100，若按列优先顺序存储，则元素 A[6,6]存储地址为__232_____。

11．设n 行n 列的下三角矩阵 A 已压缩到一维数组 B[1..n*（n+1）/2]中，若按行为主序存储，则 A[i,j]对应的 B 中存储位置为__i(i-1)/2+j (1<=i,j<=n)_____。

14. 设有一个 10 阶对称矩阵 A 采用压缩存储方式（以行为主序存储：a11=1），则 a85 的地址为____33 (k=i(i-1)/2+j) (1<=i,j<=n)___。

15. 所谓稀疏矩阵指的是__非零元很少(t<

17. 上三角矩阵压缩的下标对应关系为：_上三角矩阵中，主对角线上第r(1￡r￡n) 行有n-r+1个元素，aij所在行的元素数是j-i+1。所以，元素在一维数组的下标k和二维数组下标关系:k=((i-1)*(2n-i+2))/2+(j-i+1)=(i-1)(2n-i)/2+j (i￡j)______。

18. 假设一个 15 阶的上三角矩阵 A按行优先顺序压缩存储在一维数组 B 中， 则非零元素 A9,9在 B中的存储位置k=__93_____。 （注：矩阵元素下标从 1 开始）如果按行序为主序将下三角元素 Ai j (i,j)存储在一个一维数组 B[ 1..n(n+1)/2]中，对任一个三角矩阵元素 A ,它在数组B 中的下标为___i(i-1)/2+j ____。

第六章 树和二叉树

1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为(D ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 3. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（C ）

A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G 5. 在下述结论中，正确的是（ D）

8

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④

8．若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是（B ） A．9 B．11 C．15 D．不确定

11．具有10 个叶结点的二叉树中有（ B）个度为2 的结点。 A．8 B．9 C．10 D．ll

14. 有n 个叶子的哈夫曼树的结点总数为（ D）。 A．不确定 B．2n C．2n+1 D．2n-1 16. 有关二叉树下列说法正确的是（B ） A．二叉树的度为2 B．一棵二叉树的度可以小于2

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

19．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(B )结点 A．2h B．2h-1 C．2h+1 D．h+1

21. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 27. 利用二叉链表存储树，则根结点的右指针是（C ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空

34．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ D）。 A．acbed B．decab C．deabc D．cedba

41．对于前序遍历与中序遍历结果相同的二叉树为（BF）; 对于前序遍历和后序遍历结果相同的二叉树为（B）。

A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树

D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树 51. 线索二叉树是一种（ C）结构。

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

58．由3 个结点可以构造出多少种不同的二叉树？（D ） A．2 B．3 C．4 D．5

63．下面几个符号串编码集合中，不是前缀编码的是（ ）。

A．{0,10,110,1111} B．{11,10,001,101,0001} C．{00,010,0110,1000} D．{b,c,aa,ac,aba,abb,abc} 二、判断题

21．由一棵二叉树的前序序列和后序序列可以唯一确定它。 23. 二叉树只能用二叉链表表示。×

28. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.× 49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 三、填空题

8．深度为k 的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。

42．一个无序序列可以通过构造一棵______树而变成一个有序序列，构造树的过程即为对无序序列进行排 序的过程。

50．线索二元树的左线索指向其______，右线索指向其______。

53．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 四、应用题

44．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）

9

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

46．设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。

（2）画出这棵二叉树的后序线索树。

（3）将这棵二叉树转换成对应的树（或森林）

第七章 图

一、选择题

4．要连通具有n 个顶点的有向图，至少需要（ B）条边。 A．n-l B．n C．n+l D．2n

11．下列哪一种图的邻接矩阵是对称矩阵？（ B） A．有向图 B．无向图 C．AOV 网 D．AOE 网 15. 下列说法不正确的是（C ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程

28. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（D ）。 A．G 中有弧 B．G 中有一条从Vi 到Vj 的路径 C．G 中没有弧 D．G 中有一条从Vj 到Vi 的路径 二、判断题

6．强连通图的各顶点间均可达。（ √）

12．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（× ） 31. 最小生成树问题是构造连通网的最小代价生成树。（√ ） 34．拓扑排序算法把一个无向图中的顶点排成一个有序序列。（×） 39．任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（× ）

46. 在表示某工程的AOE 网中，加速其关键路径上的任意关键活动均可缩短整个工程的完成时间。（× ） 44.关键路径是 AOE 网中从源点到终点的最长路径。√ 三、填空题

22. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是__深度优先____遍历方法。 28. Prim（普里姆）算法适用于求__边稠密____的网的最小生成树；

29．克鲁斯卡尔算法的时间复杂度为__O(eloge）____,它对__边稀疏____图较为适合。

34. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按___递增___次序依次产生，该算法弧上的权出现____负值__情况时，不能正确产生最短路径。 四、应用题

43．对于如下的加权有向图，给出算法Dijkstra 产生的最短路径的支撑树，设顶点A 为源点，并写出生成过程。

10

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

第八章 查找

4. 下面关于二分查找的叙述正确的是 ( )

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储

14．在等概率情况下,线性表的顺序查找的平均查找长度ASL 为( （1） ),有序表的折半查找的ASL 为 ( （2） ),对静态树表,在最坏情况下,ASL 为( （3） ),而当它是一棵平衡树时,ASL 为 ( （4） ),在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需( （5） )次旋转。供选择的答案：

（1）（2）（3）（4）（5）: A. O(1) B. O( log2n ) C. O((log2n)2) D.O(nlog2n) E. O(n) 21. 下面关于m 阶B 树说法正确的是( )

①每个结点至少有两棵非空子树； ②树中每个结点至多有m 一1 个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B 树结点分裂后，树长高一层。 A． ①②③ B. ②③ C. ②③④ D. ③

27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1 的链中有（ ）个记录。 A．1 B. 2 C. 3 D. 4

28. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

31. 设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15，38，61，84 共四个，现要将关键字为49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9 二、 判断题

15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 20．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 36. B+树既能索引查找也能顺序查找。 三、填空题

12. 在哈希函数H（key）=key%p 中，p 值最好取__________。

49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;

第三章 排序

一、选择题

3．下列排序算法中，其中（ D）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序

11

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 10．下面的排序算法中，不稳定的是（CDF ）

A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 12．排序趟数与序列的原始状态有关的排序方法是(CD )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速

14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是(BD )。 A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序

15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ D）。 A． 直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序

23．下列排序算法中( C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆

30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（C ）算法，最费时间的是（B ）算法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序

31. 就平均性能而言，目前最好的内排序方法是(D )排序法。 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 二、判断题

18．在基数排序时，最高位优先分配法比最低位优先分配法简单。（×）

19． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2 n ),所以快速排序比冒泡排序算法效率更高。 （× ） 24．快速排序总比简单排序快。（ ×） 三、填空题

1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较____和记录的___移动__。 6．直接插入排序用监视哨的作用是___免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。____。

第九章 文件

一、选择题

4．下述文件中适合于磁带存储的是（ A）。

A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 6. ISAM 文件和VASM 文件属于（ B）。

A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（B ）文件系统中。 A. ISAM B. VSAM 二、判断题

1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。√ 2. 倒排文件是对次关键字建立索引。√ 三、填空题

1. 文件可按其记录的类型不同而分成两类，即__操作系统文件____和_数据库_____文件。 7. 索引顺序文件既可以顺序存取，也可以___随机___存取。 8. 建立索引文件的目的是___提高查找速度___。

9. 索引顺序文件是最常用的文件组织之一，通常用__树__结构来组织索引。 10. 倒排序文件的主要优点在于___检索记录快___。 13. VSAM 系统是由___索引集、顺序集、数据集构成的。

广义表

18. 已知广义表L=（（x,y,z），a，（u，t，w）），从L 表中取出原子项t 的运算是（D ）。 A. head（tail（tail（L））） B. tail（head（head（tail（L））））

C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 19. 已知广义表LS＝((a,b,c),(d,e,f)),运用head 和tail 函数取出LS 中原子e 的运算是( C)。 A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))

12

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

20. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d

21. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( F)。A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ C ）。 A. (c,d) B. c,d C. ((c,d)) D. d

26. 设广义表L=（（a,b,c）），则L 的长度和深度分别为（C ）。 A. 1 和1 B. 1 和3 C. 1 和2 D. 2 和3 27. 下面说法不正确的是(A )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、判断题

8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ×） 9. 若一个广义表的表头为空表，则此广义表亦为空表。（× ）

10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ×） 11. 所谓取广义表的表尾就是返回广义表中最后一个元素。（ ×）

12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（√ ） 13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（√ ） 14. 一个广义表可以为其它广义表所共享。（√） 三、 填空题

31. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于 。(b) 32. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是___ (x,y,z)____。

33. 已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是___(d,e)____。

第 1 章绪 论

1. 填空

⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构

⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（ ）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码

⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。【解答】问题规模

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题

⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。

⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。

⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 【解答】C，E 3. 判断题

13

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。

【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。 ⑵ 每种数据结构都具备三个基本操作：插入、删除和查找。

【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。 ⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。 【解答】错。是数据之间的逻辑关系的整体。

⑷ 逻辑结构与数据元素本身的内容和形式无关。 【解答】对。因此逻辑结构是数据组织的主要方面。

⑸ 基于某种逻辑结构之上的基本操作，其实现是唯一的。

【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。

【解答】⑴ 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ⑵ 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 ⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。 ⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2≤n，所以T(n)=O(n 1/2)。 ⑸ x++是基本语句，所以 5．设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何

种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。

6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。 【解答】整数的抽象数据类型定义如下： ADT integer Data 整数a：可以是正整数(1, 2, 3, ? )、负整数(-1, -2, -3, ?)和零 Operation Constructor 前置条件：整数a不存在 输入：一个整数b 功能：构造一个与输入值相同的整数

输出：无 后置条件：整数a具有输入的值 Set 前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同 输出：无 后置条件：整数a的值发生改变 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生改变 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果 后置条件：整数a的值发生改变 Multi 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相乘 输出：相乘的结果 后置条件：整数a的值发生改变 Div 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod 前置条件：存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数 输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal 前置条件：存在一个整数a 输入：一个整数b 功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变 endADT

7. 求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+?+a1x+a0 ⑵ A(x)=(?(anx+an-1)x+?+a1)x)+a0 根据算法的时间复杂度分析比较这两种算法的优劣。 【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。

8. 算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度） ⑴ 对一个整型数组A[n]设计一个排序算法。 【解

答】下面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的C++描述。

分析算法，有两层嵌套的for循环，所以

⑵ 找出整型数组A[n]中元素的最大值和次最大值。 【解答】算法的伪代码描述如下：

14

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

算法的C++描述如下： 分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。 学习自测及答案

1．顺序存储结构的特点是（ ），链接存储结构的特点是（ ）。 【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。 2. 算法在发生非法操作时可以作出处理的特性称为（ ）。 【解答】健壮性

3. 常见的算法时间复杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。 【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)

4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!

5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。

6. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。 ⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,,,,} ⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,} ⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}， R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)}

【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构，其逻辑结构图如图1-4(b)所示；⑶ 属于树结构，其逻辑结构图如图1-4(c)所示；⑷ 属于图结构，其逻辑结构图如图1-4(d)所示。

7. 求下列算法的时间复杂度。 count=0; x=1; while (x { x*=2; count++; } return count; 【解答】Ｏ(log2n)

第 2 章线性表

1. 填空

⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（ ）个元素，具体移动元素的个数与（ ）和（ ）有关。 【解答】表长的一半，表长，该元素在表中的位置

⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（ ）。 【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108

⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（ ）。 【解答】p->next=(p->next)->next

⑷ 单链表中设置头结点的作用是（ ）。 【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（ ）。 【解答】p->next=head 【分析】如图2-8所示。 ⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（ ）；删除开始结点的操作序列为（ ）。 【解答】s->next =rear->next; rear->next =s; rear =s; q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图2-9所示： ⑺ 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（ ）；在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。 【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 ⑻ 可由一个尾指针唯一确定的链表有（ ）、（ ）、（ ）。 【解答】循环链表，循环双链表，双链表 2. 选择题

⑴ 线性表的顺序存储结构是一种（ ）的存储结构，线性表的链接存储结构是一种（ ）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见2.2.1。 ⑵ 线性表采用链接存储时，其地址（ ）。 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。

⑶单循环链表的主要优点是（A ）。A 不再需要头指针了；B 从表中任一结点出发都能扫描到整个链表；C 已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。 【解答】B ⑷ 链表不具有的特点是（ ）。A 可随机访问任一元素；B插入、删除不需要移动元素；C不必事先估计存储空间；D所需空间与线性表长度成正比

⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（ ）存储方法最节省时间。 A 顺序表 B 单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。

⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节省时间。 A 单链表 B 带

15

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

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

【解答】D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，⑺ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方法最节省运算时间。 A 单链表 B 循环双链表 C单循环链表 D 带尾指针的单循环链表 【解答】B 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。 ⑻ 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 【解答】B 【分析】首先应顺序查找新结点在单链表中的位置。

⑼ 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。 A O(1) B O(n) C O(n2) D O(nlog2n) 【解答】C 【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。 ⑽ 使用双链表存储线性表，其优点是可以（ ）。 A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间 【解答】B 【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。 ⑾ 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（ ）操作。 A s->next=p->next; p->next=s; B q->next=s; s->next=p; C p->next=s->next; s->next=p; D p->next=s; s->next=q; 【解答】B 【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。

⑿ 在循环双链表的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 【解答】D【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。 3. 判断题

⑴ 线性表的逻辑顺序和存储顺序总是一致的。 【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。

⑵ 线性表的顺序存储结构优于链接存储结构。 【解答】错。两种存储结构各有优缺点。

⑶ 设p，q是指针，若p=q，则*p=*q。 【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。

⑷ 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。 【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。

⑸ 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。 【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。

4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 ⑴ 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 ⑵ 如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 ⑶ 描述一个城市的设计和规划。

【解答】顺序表的优点：① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；② 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：① 插入和删除操作需移动大量元素；② 表的容量难以确定；③ 造成存储空间的“碎片”。 单链表的优点：① 不必事先知道线性表的长度；② 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：① 指针的结构性开销；② 存取表中任意元素不方便，只能进行顺序存取。 ⑴ 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 ⑵ 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。

⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。 5．算法设计

⑴ 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。 【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。

分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。

⑵ 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。 【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下：

分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。

⑶ 试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。 【解答】参见2.2.3。

⑷ 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。 【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下： 单链表的逆置请参见2.2.4算法2-4和算法2-6。 ⑸ 假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。 【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下： ⑹ 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。 【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下： ⑺ 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下： ⑻ 判断带头结点的双循环链表是否对称。 【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。 学习自测及答案

16

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

1. 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（ ）。 A 108 B 180 C 176 D 112 【解答】D

2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为： （ ）。 A O(0) B O(1) C O(n) D O(n2) 【解答】C

3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（ ）个元素。 【解答】n-i+1，n-i

4．在单链表中，除了头结点以外，任一结点的存储位置由（ ）指示。 【解答】其前趋结点的指针域 5．当线性表采用顺序存储结构时，其主要特点是（ ）。 【解答】逻辑结构中相邻的结点在存储结构中仍相邻

6．在双链表中，每个结点设置了两个指针域，其中一个指向（ ）结点，另一个指向（ ）结点。 【解答】前驱，后继 7．设A是一个线性表（a1, a2, ?, an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为 ，则平均每插入一个元素所要移动的元素个数又是多少？ 【解答】 ， 。

8．线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下： 9. 已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。 【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。

10．设单循环链表L1，对其遍历的结果是：x1, x2, x3,?, xn-1, xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1, x3,? ；L2中含有原L1表中序号为偶数的结点且遍历结果为：? , x4, x2。 【解答】算法如下：

第 3 章特殊线性表——栈、队列和串 课后习题讲解 1. 填空

⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5， 经过push，push，pop，push，pop，push，push后，输出序列是（ ），栈顶指针为（ ）。 【解答】23，1003H ⑵ 栈通常采用的两种存储结构是（ ）；其判定栈空的条件分别是（ ），判定栈满的条件分别是（ ）。 【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间

⑶（ ）可作为实现递归函数调用的一种数据结构。 【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。 ⑷ 表达式a*(b+c)-d的后缀表达式是（ ）。 【解答】abc+*d- 【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。

⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（ ），队列的操作特性是（ ），栈和队列的主要区别在于（ ）。 【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（ ）。 【解答】假溢出 ⑺ 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（ ）。 【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。

⑻ 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（ ）和（ ）。 【解答】Ｏ(1)，Ｏ(n) 【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。

⑼ 串是一种特殊的线性表，其特殊性体现在（ ）。 【解答】数据元素的类型是一个字符 ⑽ 两个串相等的充分必要条件是（ ）。 【解答】长度相同且对应位置的字符相等 【分析】例如\≠\，\≠\。 2. 选择题

⑴ 若一个栈的输入序列是1，2，3，?，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。 A 不确定 B n-i C n-i-1 D n-i+1 【解答】D 【分析】此时，输出序列一定是输入序列的逆序。

⑵ 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。 A 6 B 4 C 3 D 2 【解答】C 【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。 ⑶ 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。 A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。

⑷ 设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳 A 顺序表 B 栈 C 队列 D 链表 【解答】B 【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。

⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ ）结构。 A 栈 B队列 C 数组 D线性表 【解答】B 【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。 ⑹ 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ ）。 A 4321 B 1234 C 1432 D 3241 解答B 【分析】队列的入队顺序和出队顺序总是一致的。

⑺ 栈和队列的主要区别在于（ ）。 A 它们的逻辑结构不一样 B 它们的存储结构不一样 C 所包含的运算不一样 D 插入、删除运算的限定不一样。解答D

【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。

⑻ 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（ ）。 A S1的栈底位置为0，S2的栈底位置为n-1 B S1的栈底位置为0，S2的栈底位置为n/2 C S1的栈底位置为0，S2的栈底位置为n D S1的栈底位置为0，S2的栈底位置为1 【解答】A 【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。 ⑼ 设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）。 A 连接 B 模式匹配 C 求子串 D 求串长 【解答】B 3. 判断题

17

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑴ 有n个元素依次进栈，则出栈序列有(n-1)/2种。 【解答】错。应该有 种。

⑵ 栈可以作为实现过程调用的一种数据结构。 【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。 ⑶ 在栈满的情况下不能做进栈操作，否则将产生“上溢”。 【解答】对。

⑷ 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。 【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。

⑸ 空串与空格串是相同的。 【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。

4. 设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。 ⑴ C，E，A，B，D ⑵ C，B，A，D，E 【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。

5. 举例说明顺序队列的“假溢出”现象。 【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生“上溢”，此时的“上溢”又称为“假溢出”，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。

6. 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。） 【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。

7． 在操作序列EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。 【解答】队头元素为5，队尾元素为9。其执行过程如图3-8所示。

8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？ 【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。

9. 算法设计 ⑴ 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。 【解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。 入队算法如下： 出队算法如下：

⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，?，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，?，a2，a2n-1，a2n-3，?，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。 【解答】操作步骤为： ① 将所有元素出栈并入队； ② 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈； ③ 将奇数结点出栈并入队；

④ 将偶数结点出队并入栈； ⑤ 将所有元素出栈并入队； ⑥ 将所有元素出队并入栈即为所求。

⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。 【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下：

⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。 【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下： ⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。 【解答】参见3.2.5 学习自测及答案

1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（ ）。 A 不变 B top=0; C top=top-1; D top=top+1; 【解答】C

2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（ ）。 A edcba B cdeba C debca D abcde 【解答】C 3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）。 A x=top; top=top->next; B x=top->data; C top=top->next; x=top->data; D x=top->data; top=top->next; 【解答】D

4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。 【解答】PA321, P3A21, P32A1, P321A, AP321 5.设S=\，其长度为（ ）。 【解答】15

6．对于栈和队列，无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（ ）。 【解答】Ｏ(1)

7．如果进栈序列为A、B、C、D，则可能的出栈序列是什么？ 答：共14种，分别是：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA

8．简述队列和栈这两种数据结构的相同点和不同点。 【解答】相同点：它们都是插入和删除操作的位置受限制的线性表。 不同点：栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。

9. 利用两个栈S1和S2模拟一个队列，如何利用栈的运算实现队列的插入和删除操作，请简述算法思想。 【解答】利用两个栈S1和S2模拟一个队列，当需要向队列中插入一个元素时，用S1来存放已输入的元素，即通过向栈S1执行入栈操作来实现；当需要从队列中删除元素时，则将S1中元素全部送入到S2中，再从S2中删除栈顶元素，最后再将S2中元素全部送入到S1中；判断队空的条件是：栈S1和S2同时为空。

10. 设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出。 【解答】算法基于原理：N=(N div d)×d + N mod d （div为整除运算，mod为求余运算）。

11．假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用。编写算法判断给定表达式中所含括号是否配对出现。 【解答】假设表达式已存入字符数组A[n]中，具体算法如下：

第 4 章广义线性表——多维数组和广义表

1. 填空

⑴ 数组通常只有两种运算：（ ）和（ ），这决定了数组通常采用（ ）结构来实现存储。 【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

18

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（ ）。 【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（ ）。 【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+?+8)+5=41个元素。 ⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（ ）和（ ）。 【解答】三元组顺序表，十字链表 ⑸ 广义表((a), (((b),c)),(d))的长度是（ ），深度是（ ），表头是（ ），表尾是（ ）。 【解答】3，4，(a)，((((b),c)),(d)) ⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（ ）。 【解答】Head(Head(Tail(LS))) 2. 选择题

⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（ ）个字节，A的第8列和第5行共占（ ）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（ ）元素的起始地址一致。 A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。 ⑵ 将数组称为随机存取结构是因为（ ） A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定 【解答】B

⑶ 下面的说法中，不正确的是（ ） A 数组是一种线性结构 B 数组是一种定长的线性结构 C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操 【解答】C 【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（ ） A 表达变得简单 B 对矩阵元素的存取变得简单 C 去掉矩阵中的多余元素 D 减少不必要的存储空间 【解答】D 【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。

⑸ 下面（ ）不属于特殊矩阵。 A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵 【解答】C ⑹ 若广义表A满足Head(A)=Tail(A)，则A为（ ） A ( ) B (( )) C (( ),( )) D(( ),( ),( )) 【解答】B

⑺ 下面的说法中，不正确的是（ ） A 广义表是一种多层次的结构 B 广义表是一种非线性结构 C 广义表是一种共享结构 D 广义表是一种递归 【解答】B 【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。

⑻ 下面的说法中，不正确的是（ ） A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。 B 对角矩阵只须存放非零元素即可。 C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。 D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 【解答】D 【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。 3. 判断题

⑴ 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。 【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。

⑵ 使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。 【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。

⑶ 稀疏矩阵压缩存储后，必会失去随机存取功能。 【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。

⑷ 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。 【解答】对。

⑸ 若一个广义表的表头为空表，则此广义表亦为空表。 【解答】错。如广义表L=(( )，(a，b))的表头为空表，但L不是空表。

4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。 【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。

5．已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求 运算的优缺点。 【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << m×n时，采用三元组顺序表存储可获得较好的时、空性能。

6．设某单位职工工资表ST由“工资”、“扣除”和“实发金额”三项组成，其中工资项包括“基本工资”、“津贴”和“奖金”，扣除项包括“水”、“电”和“煤气” 。

⑴ 请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的“奖金”项； ⑵ 画出该工资表ST的存储结构。【 解答】⑴ ST=((基本工资，津贴，奖金)，(水，电，煤气)，实发金额) Head(Tail(Tail(Head(ST))))=奖金 ⑵ 工资表ST的头尾表示法如图4-7所示。 7．若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。 【解答】在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。 具体算法如下：

分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n次，所以，最坏情况下的时间复杂度为Ｏ(mn+n2)。

8．已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。 【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。

第 5 章树和二叉树

1. 填空题 ⑴ 树是n（n≥0）结点的有限集合，在一棵非空树中，有（ ）个根结点，其余的结点分成m（m＞0）个（ ）的集合，每个集合都是根结点的子树。 【解答】有且仅有一个，互不相交 ⑵ 树中某结点的子树的个数称为该结点的（ ），子树的根结点称为该结点的（ ），该结点称为其子树根结点的（ ）。 【解答】度，孩子，双亲

19

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑶ 一棵二叉树的第i（i≥1）层最多有（ ）个结点；一棵有n（n>0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。 【解答】2i-1，(n+1)/2，(n-1)/2 【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。

⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（ ），最小值是（ ）。 【解答】2h -1，2h-1 【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。 ⑸ 深度为k的二叉树中，所含叶子的个数最多为（ ）。 【解答】2k-1 【分析】在满二叉树中叶子结点的个数达到最多。 ⑹ 具有100个结点的完全二叉树的叶子结点数为（ ）。 【解答】50 【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。

⑺ 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（ ）个叶子结点。 【解答】12 【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。 ⑻ 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（ ）。 【解答】CDBGFEA 【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。

⑼ 在具有n个结点的二叉链表中，共有（ ）个指针域，其中（ ）个指针域用于指向其左右孩子，剩下的（ ）个指针域则是空的。 【解答】2n，n-1，n+1

（10） 在有n个叶子的哈夫曼树中，叶子结点总数为（ ），分支结点总数为（ ）。 【解答】n，n-1 【分析】n-1个分支结点是经过n-1次合并后得到的。 2. 选择题

⑴ 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（ ）。 A 1 B 2 C 3 D 4 【解答】D ⑵ 设二叉树有n个结点，则其深度为（ ）。 A n-1 B n C +1 D 不能确定 【解答】D

【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是 +1。

⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 【解答】B 【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。 ⑷ 线索二叉树中某结点R没有左孩子的充要条件是（ ）。 A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 解答C【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。

⑸ 深度为k的完全二叉树至少有（ ）个结点，至多有（ ）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（ ）。 A 2k-2+1 B 2k-1 C 2k -1 D 2k–1 -1 E 2k+1 F 2k+1 -1 G 2k -1+1 H 2k 【解答】B，C，A 【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。

⑹ 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（ ）成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D 【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。 ⑺ 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。 A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化 【解答】A 【分析】三种遍历次序均是先左子树后右子树。

⑻ 如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（ ）序列，T中结点的后序序列就是 T' 中结点的（ ）序列。 A 前序 B 中序 C 后序 D 层序 【解答】A，B

⑼ 设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（ ）个结点，根结点的左子树上有（ ）个结点。 A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 【解答】D，A 【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。

（10）讨论树、森林和二叉树的关系，目的是为了（ ）。 A 借助二叉树上的运算方法去实现对树的一些运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧，没有什么实际意义 【解答】B 3. 判断题

⑴ 在线索二叉树中，任一结点均有指向其前趋和后继的线索。 【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。 ⑵ 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。 【解答】对。由前序遍历的操作定义可知。 ⑶ 二叉树是度为2的树。 【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。 ⑷ 由树转换成二叉树，其根结点的右子树总是空的。 【解答】对。因为根结点无兄弟结点。 ⑸ 用一维数组存储二叉树时，总是以前序遍历存储结点。 【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。 4．证明：对任一满二叉树，其分枝数B＝2(n0-1) 。（其中，n0为终端结点数） 【解答】因为在满二叉树中没有度为1的结点，所以有： n=n0+n2 设B为树中分枝数，则 n=B+1 所以 B=n0 +n2-1 再由二叉树性质： n0=n2+1 代入上式有： B=n0+n0-1-1=2(n0-1) 5．证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。 【解答】证明采用归纳法。 设二叉树的前序遍历序列为a1a2a3? an，中序遍历序列为b1b2b3? bn。 当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树； 假设当n<=k时，前序遍历序列a1a2a3? ak和中序遍历序列b1b2b3? bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3? akak+1和中序遍历序列b1b2b3? bk bk+1可唯一确定一棵二叉树。 在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2? bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3? ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3? ai和中序遍历序列b1b2? bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2? ak+1和中序遍历序列bi+1bi+2? bk+1唯一确定了根结点的右子树。

6．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，??，nm个度为m的结点，问该树中共有多少个叶子结点？ 【解答】设该树的总结点数为n，则 n=n0+n1+n2+??+nm 又： n=分枝数+1=0×n0+1×n1+2×n2+??+m×nm+1 由上述两式可得： n0= n2+2n3+??+(m-1)nm+1 7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。 【解答】二叉树的构造过程如图5-12 所示。

8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。 【解答】构造的哈夫曼树如图5-13所示。

树的带权路径长度为： WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120

20

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。 10．算法设计

⑴ 设计算法求二叉树的结点个数。 【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的“访问”操作改为“计数操作”，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。 具体算法如下：

⑵ 设计算法按前序次序打印二叉树中的叶子结点。 【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下：

⑶ 设计算法求二叉树的深度。 【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下：

⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。 【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下：

⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。 【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下：

⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。 【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下：

⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。 【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下： ① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。 ② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。 具体算法如下：

⑻ 编写算法交换二叉树中所有结点的左右子树。 【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。 具体算法如下：

⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。 【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。 树的孩子兄弟表示法中的结点结构定义如下： template struct TNode { T data; TNode *firstchild, *rightsib; }; 具体算法如下： 学习自测及答案

1．前序遍历和中序遍历结果相同的二叉树是（ ）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树

C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树 【解答】D

2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（ ）。 A 24 B 48 C 53 D 72 【解答】C

3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（ ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D

4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（ ）。 A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律 【解答】C

5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（ ）。 A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D 6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ ）。 A h B h+1 C h或h+1 D 任意 【解答】C

7．假定一棵度为3的树中结点数为50，则其最小高度应为 。 A 3 B 4 C 5 D 6 【解答】C 8．在线索二叉树中，一个结点是叶子结点的充要条件为（ ）。 A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C 9．对于一棵具有n个结点的树，其所有结点的度之和为（ ）。 【解答】n-1

10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（ ）。 【解答】

11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？ 【解答】共有5种二叉树可以得到这一结果，如图5-15所示。

12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。 ⑵ 中序序列和后序序列相同。 ⑶ 前序序列和后序序列相同。 【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。 ⑵ 空二叉树、只有一个根结点的二叉树和左斜树。 ⑶ 空二叉树、只有一个根结点的二叉树 13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。 【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。

14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。 【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下：

15．设计算法，判断一棵二叉树是否为完全二叉树。 【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足： ⑴ 若某结点没有左孩子，则其一定没有右孩子； ⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。 若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。

第 6 章图

1. 填空题

⑴ 设无向图G中顶点数为n，则图G至少有（ ）条边，至多有（ ）条边；若G为有向图，则至少有（ ）条边，至多有（ ）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图

21

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

中，任意两个顶点之间都存在边。

⑵ 任何连通图的连通分量只有一个，即是（ ）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（ ）和（ ）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。

⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（ ）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（ ）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（ ）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）；图的广度优先遍历类似于树的（ ）遍历，它所用到的数据结构是（ ）。 【解答】前序，栈，层序，队列

⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用Kruskal算法求最小生成树的时间复杂度为（ ）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（ ），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 （10） 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（ ）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题

⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则 。

⑵ n个顶点的强连通图至少有（ ）条边，其形状是（ ）。 A n B n+1 C n-1 D n×(n-1) E 无回路 F 有回路 G 环状 H 树状 【解答】A，G

⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。 A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。

⑷ 对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。 A n B (n-1)2 C n-1 D n2 【解答】D ⑸ 图的生成树（ ），n个顶点的生成树有（ ）条边。 A 唯一 B 不唯一 C 唯一性不能确定 D n E n +1 F n-1 【解答】C，F ⑹ 设无向图G=(V, E)和G' =(V', E' )，如果G' 是G的生成树，则下面的说法中错误的是（ ）。 A G' 为 G的子图 B G' 为 G的连通分量

C G' 为G的极小连通子图且V = V' D G' 是G的一个无环子图 【解答】B 【分析】连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。 ⑺ G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A 6 B 7 C 8 D 9 【解答】D 【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。

⑻ 最小生成树指的是（ ） 。 A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 【解答】C

⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。 A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 【解答】D 【分析】当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。

⑽ 下面关于工程计划的AOE网的叙述中，不正确的是（ ）

A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 【解答】B 【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。 3. 判断题

⑴ 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 【解答】对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。 ⑵ 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。 【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。 ⑶ 图G的生成树是该图的一个极小连通子图 【解答】错。必须包含全部顶点。 ⑷ 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 【解答】错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。 ⑸ 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。 【解答】错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。 ⑹ 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 【解答】错。只能说明从顶点a到顶点b有一条路径。 ⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。 【解答】对。参见第11题的证明。 ⑻ 在AOE网中一定只有一条关键路径? 【解答】错。AOE网中可能有不止一条关键路径，他们的路径长度相同。

4．n个顶点的无向图，采用邻接表存储，回答下列问题? ⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少?

【解答】 ⑴ 边表中的结点个数之和除以2。 ⑵ 第i个边表中是否含有结点j。 ⑶ 该顶点所对应的边表中所含结点个数。

5．n个顶点的无向图，采用邻接矩阵存储，回答下列问题： ⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少？ 【解答】 ⑴ 邻接矩阵中非零元素个数的总和除以2。 ⑵ 当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。 ⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。

6．证明：生成树中最长路径的起点和终点的度均为１。 【解答】用反证法证明。 设v1, v2, ?, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, ?, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。 同理可证起点v1的度不能大于1，只能为1。 7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。

【解答】邻接矩阵表示如下： 深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下： 8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 【解答】按Prim算法求最小生成树的过程如下：

22

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

按Kruskal算法求最小生成树的过程如下：

9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度

v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点 终点 最短路径 最短路径长度

v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。 【解答】

任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2?vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。 假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2?vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。 12. 算法设计

⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。 【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。 邻接矩阵存储结构定义如下： const int MaxSize=10; template struct AdjMatrix { T vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum, arcNum; //图的顶点数和边数 };

邻接表存储结构定义如下：

const int MaxSize=10; struct ArcNode //定义边表结点 { int adjvex; //邻接点域 ArcNode *next; }; template struct VertexNode //定义顶点表结点 { T vertex; ArcNode *firstedge; };

struct AdjList { VertexNode adjlist[MaxSize]; int vertexNum, arcNum; //图的顶点数和边数 }; 具体算法如下：

⑵ 设计算法，将一个无向图的邻接表转换成邻接矩阵。 【解答】在邻接表上顺序地取每个边表中的结点，将邻接矩阵中对应单元的值置为1。邻接矩阵和邻接表的存储结构定义与上题相同。具体算法如下：

⑶ 设计算法，计算图中出度为零的顶点个数。 【解答】在有向图的邻接矩阵中，一行对应一个顶点，每行的非零元素的个数等于对应顶点的出度。因此，当某行非零元素的个数为零时，则对应顶点的出度为零。据此，从第一行开始，查找每行的非零元素个数是否为零，若是则计数器加1。具体算法如下：

⑷ 以邻接表作存储结构，设计按深度优先遍历图的非递归算法。 【解答】参见6.2.1。

⑸ 已知一个有向图的邻接表，编写算法建立其逆邻接表。 【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头结点firstedge域置空，然后逐行将表头结点的邻接点进行转化。 ⑹ 分别基于深度优先搜索和广度优先搜索编写算法，判断以邻接表存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。 【解答】⑴ 基于深度优先遍历： ⑵ 基于广度优先遍历： 学习自测及答案

1．某无向图的邻接矩阵A=，可以看出，该图共有（ ）个顶点。 A .3 B. 6 C. 9 D .以上答案均不正确 【解答】A 2．无向图的邻接矩阵是一个（ ），有向图的邻接矩阵是一个（ ） A 上三角矩阵 B 下三角矩阵 C 对称矩阵 D 无规律 【解答】C，D

3．下列命题正确的是（ ）。 A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一 【解答】B 4．十字链表适合存储（ ），邻接多重表适合存储（ ）。 【解答】有向图，无向图 5. 在一个具有n 个顶点的有向完全图中包含有（ ）条边： A n(n-1)/2 B n(n-1) C n(n+1)/2 D n2 【解答】B

6．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（ ）个非零元素。 【解答】2(n-1)

7．表示一个有100个顶点，1000条边的有向图的邻接矩阵有（ ）个非零矩阵元素。 【解答】1000 8．一个具有n个顶点k条边的无向图是一个森林（n>k），则该森林中必有（ ）棵树。 A k B n C n - k D 1 【解答】C

9．用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。 A 逆拓扑有序 B 拓扑有序 C 无序 D 深度优先遍历序列 【解答】A 10. 关键路径是AOE网中（ ）。 A 从源点到终点的最长路径 B 从源点到终点的最长路径 C 最长的回路 D 最短的回路 【解答】A

11. 已知无向图G的邻接表如图6-10所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。

【解答】深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为： 广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为： 12. 已知已个AOV网如图6-11所示，写出所有拓扑序列。 【解答】拓扑序列为：v0 v1 v5 v2 v3 v6 v4、 v0 v1 v5 v2 v6 v3 v4、 v0 v1 v5 v6 v2 v3 v4。

第 7 章查找技术

1. 填空题

⑴ 顺序查找技术适合于存储结构为（ ）的线性表，而折半查找技术适用于存储结构为（ ）的线性表，并且表中的元素必须是（ ）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序

⑵ 设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（ ）次，至多需比较（ ）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。

⑶ 对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（ ）。若按二叉排序树组织该数列，则查找一个数的平均比较次数为（ ）。 【解答】8，59/15 【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。

23

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

⑷ 长度为20的有序表采用折半查找，共有（ ）个元素的查找长度为3。【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。

⑸ 假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（ ）。 【解答】62 【分析】H(48)= H(62)=6

⑹ 在散列技术中，处理冲突的两种主要方法是（ ）和（ ）。 【解答】开放定址法，拉链法 ⑺ 在各种查找方法中，平均查找长度与结点个数无关的查找方法是（ ）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。

⑻ 与其他方法相比，散列查找法的特点是（ ）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较 2. 选择题

⑴ 静态查找与动态查找的根本区别在于（ ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同C 所包含的数据元素的类型不一样 D 存储实现不一样【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵ 有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（ ）；在查找不成功的情况下，s和b的关系是（ ）。A s=b B s>b C s 【解答】D，D 【分析】此题没有指明是平均性能。例如，在有序表中查找最大元素，则顺序查找比折半查找快，而平均性能折半查找要优于顺序查找，查找不成功的情况也类似。⑶ 长度为 12的有序表采用顺序存储结构，采用折半查找技术，在等概率情况下，查找成功时的平均查找长度是（ ），查找失败时的平均查找长度是（ ）。 A 37/12 B 62/13 C 3 9/12 D 49/13 【解答】A，B 【分析】画出长度为12的折半查找判定树，判定树中有12个内结点和13个外结点。

⑷ 用n个键值构造一棵二叉排序树，其最低高度为（ ）。 A n/2 B n C log2n D log2n+1 【解答】D 【分析】二叉排序树的最低高度与完全二叉树的高度相同。

⑸ 二叉排序树中，最小值结点的（ ）。 A 左指针一定为空 B 右指针一定为空C 左、右指针均为空 D 左、右指针均不为空【解答】A 【分析】在二叉排序树中，值最小的结点一定是中序遍历序列中第一个被访问的结点，即二叉树的最左下结点。 ⑹ 散列技术中的冲突指的是（ ）。 A 两个元素具有相同的序号 B 两个元素的键值不同，而其他属性相同C 数据元素过多 D 不同键值的元素对应于相同的存储地址【解答】D

⑺ 设散列表表长m=14，散列函数H(k)=k mod 11。表中已有15、38、61、84四个元素，如果用线性探侧法处理冲突，则元素49的存储地址是（ ）。

A 8 B 3 C 5 D 9 【解答】A 【分析】元素15、38、61、84分别存储在4、5、6、7单元，而元素49的散列地址为5，发生冲突，向后探测3个单元，其存储地址为8。

⑻ 在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置的键值（ ）。 A 一定都是同义词 B 一定都不是同义词 C不一定都是同义词 D 都相同【解答】C 【分析】采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。 3. 判断题

⑴ 二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。 【解答】错。 分析二叉排序树的定义，是左子树上的所有结点的值都小于根结点的值，右子树上的所有结点的值都大于根结点的值。例如图7-7所示二叉树满足任一结点的值均大于其左孩子的值，小于其右孩子的值，但不是二叉排序树。

⑵ 二叉排序树的查找和折半查找的时间性能相同。 【解答】错。二叉排序树的查找性能在最好情况和折半查找相同。

⑶ 若二叉排序树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。 【解答】错。在二叉排序树中，最小元素所在结点一定是中序遍历序列中第一个被访问的结点，即是二叉树的最左下结点，但可能有右子树。最大元素所在结点一定是中序遍历序列中最后一个被访问的结点，即是二叉树的最右下结点，但可能有左子树。如图7-8所示，5是最小元素，25是最大元素，但5和25都不是叶子结点。

⑷ 散列技术的查找效率主要取决于散列函数和处理冲突的方法。 【解答】错。更重要的取决于装填因子，散列表的平均查找长度是装填因子的函数。

⑸ 当装填因子小于1时，向散列表中存储元素时不会引起冲突。 【解答】错。装填因子越小，只能说明发生冲突的可能性越小。4．分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找关键码e和g的过程。【解答】查找关键码e的过程如图7-9所示，查找关键码g的过程如图7-10所示。

5．画出长度为10的折半查找判定树，并求等概率时查找成功和不成功的平均查找长度。 【解答】参见7.2.1。

6．将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。【解答】二叉排序树如图7-11所示，其平均查找长度=1+2×2+3×2+4×2=19/7 7．一棵二叉排序树的结构如图7-12所示，结点的值为1～8，请标出各结点的值。【解答】二叉排序树中各结点的值如图7-13所示。8．已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。【解答】H(25)=1, H(37)=1, H(52)=4, H(43)=7, H(84)=0, H(99)=3, H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10 构造的开散列表如下： 平均查找长度ASL=(8×1+4×2)/12=16/12 9. 算法设计⑴ 设计顺序查找算法，将哨兵设在下标高端。

【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下： ⑵ 编写算法求给定结点在二叉排序树中所在的层数。 【解答】根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。具体算法如下： ⑶ 编写算法，在二叉排序树上找出任意两个不同结点的最近公共祖先。 【解答】设两个结点分别为A和B，根据题目要求分下面情况讨论： ⑴ 若A为根结点，则A为公共祖先； ⑵ 若A->datadata且root->datadata，root为公共祖先； ⑶ 若A->datadata且B->datadata，则到左子树查找； ⑷ 若A->data>root->data且B->data>root->data，则到右子树查找。具体算法如下： ⑷ 设计算法判定一棵二叉树是否为二叉排序树。 【解答】对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。 学习自测及答案

1．已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，经过（ ）次比较后查找成功。 A 2 B 3 C 4 D 5 【解答】A 2．已知10个元素（54，28，16，73，62，95，60，26，43），按照依次插入的方法生成一棵二叉

24

杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航 杜晓航

排序树，查找值为62的结点所需比较次数为（ ）。 A 2 B 3 C 4 D 5 【解答】B 3．已知数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ）。 A 4 B 5 C 6 D 7 【解答】B 4．按（ ）遍历二叉排序树得到的序列是一个有序序列。 A 前序 B 中序 C 后序 D 层次【解答】B 5．将二叉排序树T按前序遍历序列依次插入初始为空的二叉排序树T '中，则T与T'是相同的，这种说法是否正确？ 【解答】正确 6. 一棵高度为h的平衡二叉树，最少含有个结点。 A 2h B 2 h -1 C 2 h +1 D 2 h -1 【解答】D 7．在散列函数H(k)= k mod m中，一般来讲，m应取（ ）。 A 奇数 B 偶数 C 素数 D 充分大的数【解答】C

8．已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)= ，其中i为关键码中第一个字母在字母表中的序号，采用线性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用线性探测法处理冲突，得到的闭散列表如下： 平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1×7+2×4+3×1)/12=18/12 第九题 9. 试推导含有12个结点的平衡二叉树的最大深度，并画出以棵这样的树。【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点树目，则： F1=1，F2=2，?，Fn= Fn-2+Fn-1+1。含有12 个结点的平衡二叉树的最大深度为5，例如：

第 8 章排序技术

1. 填空题

⑴ 排序的主要目的是为了以后对已排序的数据元素进行（ ）。 【解答】查找 【分析】对已排序的记录序列进行查找通常能提高查找效率。

⑵ 对n个元素进行起泡排序，在（ ）情况下比较的次数最少，其比较次数为（ ）。在（ ）情况下比较次数最多，其比较次数为（ ）。 【解答】正序，n-1，反序，n(n-1)/2

⑶ 对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较（ ）次。 【解答】3 【分析】当把第7个记录60插入到有序表时，该有序表中有2个记录大于60。

⑷ 对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 83）进行快速排序，在递归调用中使用的栈所能达到的最大深度为（ ）。 【解答】3 ⑸ 对n个待排序记录序列进行快速排序，所需要的最好时间是（ ），最坏时间是（ ）。 【解答】O(nlog2n)，O(n2) ⑹ 利用简单选择排序对n个记录进行排序，最坏情况下，记录交换的次数为（ ）。 【解答】n-1 ⑺ 如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（ ）交换。 【解答】50 ⑻ 对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（ ）的结点开始。 【解答】60 【分析】60是该键值序列对应的完全二叉树中最后一个分支结点。 2. 选择题

⑴ 下述排序方法中，比较次数与待排序记录的初始状态无关的是（ ）。 A插入排序和快速排序 B归并排序和快速排序 C选择排序和归并排序 D插入排序和归并排序 【解答】C 【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。 ⑵ 下列序列中，（ ）是执行第一趟快速排序的结果。 A [da，ax，eb，de，bb] ff [ha，gc] B [cd，eb，ax，da] ff [ha，gc，bb]

C [gc，ax，eb，cd，bb] ff [da，ha] D [ax，bb，cd，da] ff [eb，gc，ha] 【解答】A 【分析】此题需要按字典序比较，前半区间中的所有元素都应小于ff，后半区间中的所有元素都应大于ff。 ⑶ 对初始状态为递增有序的序列进行排序，最省时间的是（ ），最费时间的是（ ）。已知待排序序列中每个元素距其最终位置不远，则采用（ ）方法最节省时间。 A 堆排序 B插入排序 C快速排序 D 直接选择排序 【解答】B，C，B 【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。 ⑷ 堆的形状是一棵（ ）。 A二叉排序树 B满二叉树 C完全二叉树 D 判定树 【解答】C 【分析】从逻辑结构的角度来看，堆实际上是一种完全二叉树的结构。

⑸ 当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（ ），就平均时间而言，（ ）最佳。 A 直接插入排序 B 起泡排序 C简单选择排序 D快速排序 【解答】A，D

⑹ 设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。 A快速排序 B堆排序 C希尔排序 D 归并排序 【解答】B 【分析】堆排序不必将整个序列排序即可确定前若干个最大（或最小）元素。

⑺ 设要将序列（Q，H，C，Y，P，A，M，S，R，D，F，X）中的关键码按升序排列，则（ ）是起泡排序一趟扫描的结果，（ ）是增量为4的希尔排序一趟扫描的结果，（ ）二路归并排序一趟扫描的结果，（ ）是以第一个元素为轴值的快速排序一趟扫描的结果，（ ）是堆排序初始建堆的结果。 A （F，H，C，D，P，A，M，Q，R，S，Y，X） B （P，A，C，S，Q，D，F，X，R，H，M，Y） C （A，D，C，R，F，Q，M，S，Y，P，H，X） D （H，C，Q，P，A，M，S，R，D，F，X，Y） E （H，Q，C，Y，A，P，M，S，D，R，F，X） 【解答】D，B，E，A，C 【分析】此题需要按字典序比较，并且需要掌握各种排序方法的执行过程。 ⑻ 排序的方法有很多种，（ ）法从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（ ）法从未排序序列中挑选元素，并将其依次放入已排序序列的一端。交换排序是对序列中元素进行一系列比较，当被比较的两元素为逆序时，进行交换；（ ）和（ ）是基于这类方法的两种排序方法，而（ ）是比（ ）效率更高的方法；（ ）法是基于选择排序的一种方法，是完全二叉树结构的一个重要应用。 A 选择排序 B 快速排序 C 插入排序 D 起泡排序 E 归并排序 F 堆排序 【解答】C，A，D，B，B，D，F

⑼ 快速排序在（ ）情况下最不利于发挥其长处。 A 待排序的数据量太大 B 待排序的数据中含有多个相同值 C 待排序的数据已基本有序 D 待排序的数据数量为奇数

【解答】C 【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否含有多个相同值，待排序的数据数量为奇数或偶数都没有影响。

⑽ （ ）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。 A 归并排序 B 插入排序 C 快速排序 D 选择排序 【解答】D 3. 判断题

⑴ 如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。 【解答】错。一种排序算法适合于某种特定的数据环境，有时对排序的稳定性没有要求。

⑵ 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。 【解答】对。此时着重考虑元素的移动次数。

25

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