《数据结构与算法》（清华）典型例题 - 图文

6.3 典型例题

一、单项选择题

[例6-1] 数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是 ( ① )的有穷集合，R是D上( ② )的有限集合。

①A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构 ②A. 操作 B. 映像 C. 存储 D．关系

解析：由数据结构的集合形式化定义可知，本题答案为：①B； ②D。 [例6-2] 数据的常用存储结构中不包括( )。

A．顺序存储结构 B．线性结构 C．索引存储结构 D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。

[例6-3] 算法指的是( ① )，它必须具备( ② )这三个特性。

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

解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。

[例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i

for(j=0；j

x=x+l：

A．O(2n) B．O(n) C．O(n2) D．O(1bn)

解析：语句的执行频度即语句重复执行的次数，属于算法的时间复杂度类题目。本题 中对x的赋值语句为一个二重循环的循环体，外层循环循环n次，内层循环也循环n次， 显然此语句的执行次数为n×n＝n2次。由此可知，本题答案为：C。 二、填空题

[例6-5] 是数据的基本单位，通常由若干个 组成， 是数据的最小单位。

解析：本题是基本概念题，知识点为数据结构的相关概念。本题答案为：数据元素；数 据项；数据项。 三、应用题

[例6-6] 简述数据结构的定义。

解析：数据结构是指数据元素之间的相互关系，即数据的组织形式。数据结构通常包 括三个方面的内容，分别是数据的逻辑结构、数据的存储结构(物理结构)和在这些数据上 定义的运算。用集合的观点可以把数据结构表示为一个二元组DS＝(D，R)。其中，D是数 据元素的有穷集合，R是D上关系的有限集合。 [例6-7] 分析以下程序段的时间复杂度。

for(i=0；i

x=x+1； //语句②

for(j=0；j<2*n；j++) //语句③ y++； //语句④ }

1

解析：语句的执行频度指的是语句重复执行的次数。一个算法中所有语句的执行频度之和构成了该算法的运行时间。在本例算法中，语句①的执行频度是n+l，语句②的执行频度是n，语句③的执行频度是n(2n+2)＝2n2-2n，语句④的执行频度是n(2n+1)＝2n2+n。该程序段的时间复杂度T(n)＝(n+1)+n+(2n2+2n)+(2n2+n)＝4n2+5n+1＝O(n2)。 实际上，可以用算法中基本操作重复执行的频度作为度量标准，而被视为基本操作的一般是最深层循环内的语句。在上例中，语句④为基本操作，其执行频度为2n2+n，因此， 该算法的时间复杂度T(n)＝2n2+n＝O(n2)。 [例6-8] 分析以下程序段的时间复杂度。 i=1；

while(i<=m) i=i*2；

解析：上述算法的基本操作语句是i＝i*2，设其执行频度为T(n)，则有：2T(n)≤n，即 T(n)≤lbn＝O(lbn)。因此，该程序段的时间复杂度为O(lbn)。

2

7.3 典 型 例 题

一、单项选择题

[例7-1] 在数据结构中，与所使用计算机无关的数据叫( ① )结构；链表是一种采用( ② )存储结构存储的线性表；链表适用于( ③ )查找；在链表中进行( ④ )操作的效率比在线性表中进行该操作的效率高。

①A．存储 B．物理 C．逻辑 D．物理和逻辑 ②A．顺序 B．网状 C．星式 D．链式 ③A．顺序 B．二分法 C．顺序及二分法 D．随机 ④A．二分法查找 B．快速查找 C．顺序查找 D．插入 解析：本题考查的是基本概念。本题答案为：①C；②D；③A；④D。 [例7-2] 链表不具备的特点是( )。

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

C．不必预分配空间 D．所需空间与其长度成正比

解析：线性表可随机访问任一结点，而链表必须从第一个数据结点出发逐一查找每个 结点。本题答案为：B。

[例7-3] 不带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head_>next＝＝NULL C．head_>next＝＝head D．head!＝NULL

解析：在不带头结点的单链表head中，head指向第一个数据结点。空表即该表没有结 点，head＝＝NULL表示该单链表为空。本题答案为：A。 [例7-4] 带头结点的单链表head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL

解析：在带头结点的单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝NULL表示该单链表为空。本题答案为：B。

[例7-5] 带头结点的循环单链表head中，head为空的判定条件是( )。 A．head＝＝NULL B．head—>next＝＝NULL C．head—> next＝＝head D．head!＝NULL

解析：在带头结点的循环单链表head中，head指向头结点。空表即该表只有头结点，head—>next＝＝head表示该单链表为空。本题答案为：C。 [例7-6] 线性表采用链式存储时其存储地址( )。

A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以

解析：链式存储采用动态存储，地址一般不连续。本题答案为：D。 [例7-7] 在双向链表的* p结点前插入新结点*s的操作为( )。

A．p—>prior=s；s—>next=p；p—>prior—>next=s；s—>prior=p—>prior； B．p—>prior=s；p—>prior—>next=s；s—>next=p；s—>prior=p—>prior； C．s—>next=p；s—>prior=p—>prior；p—prior=s；p—>prior—>next=s； D．s—>next=p；s—>prior=p—>prior；p—prior—>next=s；p—>prior=s；

解析：在双向链表的 * p结点前插入新结点 * s的操作如图7.12所示，图中虚线为所 作的操作，序号为操作顺序。本题答案为：D。

3

图7.12 双向链表插入结点的过程示意图

(例7-8) 若某表最常用的操作是在最后一个结点后插入一个结点和删除第一个结点，则采用( )存储方式最节省运算时间。

A．单链表 B．双向链表

C．给出表头指针的循环单链表 D．给出尾指针的循环单链表

解析：在链表中插入或删除一个结点，需修改相邻结点的指针域。上述四个选项中， 只有选项D才能从尾指针经过最少的结点来进行题目要求的插入或删除操作。本题答案 为：D。

[例7-9] 若线性表中有2n个元素，算法( )在单链表上实现要比在顺序表上实现效率更高。

A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C．顺序输出前k个元素 D．交换其中某两个元素的值

解析：对于选项A，在单链表上和顺序表上实现的时间复杂度都为O(n)，但后者要移动大量的元素，因此在单链表上实现效率更高。本题答案为：A。

(例7-10) 在长度为n的( )上，删除第一个元素，其算法复杂度为O(n)。 A．只有表头指针的不带头结点的循环单链表 B．只有尾指针的不带表头结点的循环单链表 C．只有表尾指针的带头结点的循环单链表 D．只有尾指针的带表头结点的循环单链表 解析：本题答案为：A。具体算法如下： linklist * delfirst(linklist * h) {

Linklist * p＝h；

while(p—> next!＝h) //找到表尾结点 p＝p—>next；

p—>next=h—> next； free(h)；

returnp一>next； //返回头指针

}

二、填空题

[例7-11] 在单链表中结点 * p后插入结点 * s的指令序列为 ； 。 解析：在单链表中结点 * p后插入结点 * s，即将 * p 的后继结点变为 * s 的后继结点， * s 则成为 * p的后继结点。操作指令序列为：s—>next＝p—>next；p—>next＝s。

[例7-12] 在线性表的链式存储结构中，根据每个结点所含指针的个数，链表可分为 和 ；而根据指针的链接方式，链表又可分为 和 。 解析：本题答案为：单链表；多重链表；循环链表；普通链表(非循环链表)。 [例7-13] 在单链表中，要删除某一个指定的结点，必须找到该结点的 结点。

4

解析：由单链表的特点可知，删除某一个结点的操作是将其前驱结点的next指针域指 向该结点的后继结点。本题答案为：前驱。

[例7-14] 在一个长度为n的顺序表中删除第i(0≤i≤n一1)个元素，需向前移动 个元素。

解析：需将第i个元素后的元素依次前移一个位置，总共移动(n-1)-(i+1)+1个元素。本题答案为：n-i-1。

[例7-15] 在一个具有n个结点的单链表，在 * p结点后插入一个新结点的时间复杂度是 ；在给定值为x的结点后插入一个新结点的时间复杂度是 。

解析：在 * p结点后插入一个新结点 * s的操作是：s—> next＝p—> next；p—>next＝ s；其时间复杂度为0(1)。

在给定值为x的结点后插入一个结点，首先要找到该结点，然后再进行插入。找到该 结点的时间复杂度为O(n)，插入的时间复杂度为O(1)。本题答案为：O(1)；O(n)。 三、应用题

(例7-16) 设A是一个线性表(a0，a1，?，ai，?，an-1)，采用顺序存储结构，则在等概率情况下平均每插入一个元素需要移动的元素个数是多少?若元素插在ai和ai+1之间 (0≤i≤n-1)的概率为

n?1，则平均每插入一个元素所需要移动的元素个数是多少? n(n?1)/2 解析：在等概率情况下，平均每插入一个元素需要移动的元素个数为：

(0?1?2???n)n?

n?12若元素插在ai和ai+l之间(0≤i≤n-1)的概率为要移动的元素个数为：

n?i，则平均每插入一个元素所需

n(n?1)/2?i?0n?1(n?i)222n?1 222???n?(n?1)???1??n(n?1)/2n(n?1)?3 (例7-17) 简述线性表采用顺序存储方式和链式存储方式的优缺点。

解析：顺序表的优点是可以随机访问数据元素，而且不需要额外的空间存储元素间的逻辑关系；缺点是表的大小固定，增减结点需要移动大量元素。链表的优点是增减元素非常方便，只需要修改指针内容；缺点是只能进行顺序访问，另外在每个结点上增加指针域会造成存储空间增大。

[例7-18] 若频繁地对一个线性表进行插入和删除操作，则应采用何种存储结构来存储该线性表?为什么?

解析：应采用链式结构来存储该线性表。采用链式存储结构来存储线性表，在进行插 入和删除操作时的复杂度体现在查找插入或删除结点的前驱结点的操作上，查找过程中平 均移动指针域的次数为表长的一半；而采用顺序存储结构存储线性表，在进行插入和删除 操作时的复杂度则体现在元素的移动上，平均需移动表中的一半元素。因为指针域的移动 操作次数比元素的移动操作次数少得多，所以应采用链式结构来存储该线性表。 (例7—19) (1)写出在双向链表中的结点 * p前插入一个结点 *s的语句序列。 (2)写出判断带头结点的双向循环链表L为空表的条件。 解析：(1)s—>prior＝p—>prior；p—>prior — >next＝s；

s—>next＝p；p—>prior＝s；

(2)(L＝＝L—>next)&&(L＝＝L—>prior)

[例7-20] 链表所表示的元素是否是有序的?如果有序，则有序性体现在何处?链表所表

5

示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?

解析：链表所表示的元素是有序的，其有序性体现在逻辑有序，即指针有指向。链表所表示的元素在物理上不一定相邻。有序表的有序性不仅在逻辑结构上有序，而且在物理结构上也有序。

四、算法设计题

(例7-21) 编写一个算法，将一个带头结点的单链表逆转。要求在原链表空间上进行逆转，即不允许构造新的链表结点；

解析：从单链表的一种构造方法——头插法中可以得知，该方法构造的线性表中结点 的顺序与插人次序相反。因此我们可以将表结点从前往后逐个拆下并用头插法插人新表， 所构造的单链表即为原表的逆转。 具体算法如下：

linklist * reverse(1inklist * h) {

linklist * p，*q，*r； p＝h—>next；

h—>next=NULL； //构造空表 while(p!＝NULL) {

q=p； //拆下结点 p=p—> next；

q—>next=h—>next； //用头插法插入 h—>next=q； }

return h； }

(例7-22) 已知一个顺序表La的元素按值非递减有序，编写一个算法将元素x插人后保持该表仍然按值非递减有序。

解析：要让插入新元素后的顺序表仍然按值非递减有序，必须把x插入到表中第一个 大于等于x的元素之前。应先在表中找到该位置，然后后移该元素，空出一个位置，再将x 插入。

具体算法如下：

insert(sqlist *La，datatype x) //La为指向顺序表的指针 {

int i=0，j；

while(i<= La—>last) //查找插入位置i {

if(x<=La—>data[i])

break； i++； }

for(j=La—>last+1；j>i；j--) //后移所有大于等于x的元素 La—>data[j]=La—>data[j-1]；

La—>data[i]＝x； //将x插入 La—>last++； //表长度加1

6

}

(例7-23) 用顺序表A、B表示集合，编写算法求集合A和集合B的交集C(假设A、B表内无重复元素)。 ’

解析：求C＝A∩B，C中元素是A、B中的公共元素。对于表A中的每个元素，在表B中扫描，若有与它相同的元素，则为交集元素，将其放到C中。 具体算法如下：

intersection(sqlist A，sqlist B，sqlist * C) {

int i，j，k＝0；

for(i＝0；i<＝A．1ast；i++) { j=0；

while(j<＝B.1ast&& A.dara[i]!＝B.data[j] j++；

if(j<＝B.1ast) //表示A.data[i]在B中 C—>data[k++]＝A.data[i]

}

C—>last=k—l； //修改表长度 }

[例7-24] 编写一个算法，计算在头指针为head的单链表中数据域值为x的结点个数。 解析：先设一计数器n，初值为0。然后遍历链表中的每个结点，每遇到一个结点都需 要判断其数据域值是否为x，如果是，计数器n加1。遍历完成后计数器n的值就是所求的 结点数。

具体算法如下：

int count(linklist * head, datatype x) {

int n=0； linklist * p； p = head；

while(p ! = NULL) {

if(p—> data = = x) n++; p=p—>next； }

return n； }

(例7-25) 用单链表La、Lb表示集合A、B，编写算法求集合A和集合B的差集C， 并用链表Lc表示(假设A、B内无重复元素)。

解析：根据集合运算规则可知，集合A—B中包含所有属于集合A而不属于集合B的 元素。具体做法是：从头到尾扫描单链表La，并判断当前元素是否在单链表Lb中；若不 在，则将其插入单链表Lc中。

具体算法如下：

linklist * difference(linklist * La, linklist * Lb)

7

{

linklist *Lc, * pa, *pb, * s, * r； pa= La—>next

Lc = (linklist * ) malloc (sizeof (linklist)) ; r=Lc;

while(pa! = NULL) {

pb=Lb—> next;

while (phb! = NULL & & pb—> data ! = pa—> data) pb= pb—>next； if(pb = = NULL) {

s= (linklist * )malloe(sizeof(linklist)); s—> data= pa—>data； r—>next=s； r—s； }

pa= pa—>next； }

r—>next = NULL； return Lc； }

(例7-26) 已知两个头指针分别为La和Lb的单链表，它们的元素按值递增有序。编写一算法将两个单链表合并，要求合并后链表仍然递增有序，不允许开辟另外的链表空间。 解析：由于题目要求不开辟另外的链表空间，所以首先以两个链表中的一个头结点为新链表的头结点构造一个空的单链表。从头到尾逐个比较La和Lb表中的元素，将值较小的元素结点链接到新表的末尾，若结点值相同则将其中一个链接到新表的末尾而释放另一个。当La或Lb为空后，把另一个链表余下的结点链接到新表的末尾。 具体算法如下：

linklist * union(linklist * La, linklist * Lb) {

linklist * pa, * pb, * r； pa = La—> next； pb= Lb—>next；

r=La； //以*La为新表头结点，r为新表尾指针 free(Lb); //释放Lb表头结点 while(pa! =NULL && pb! =NULL) {

if ( pa—> data< pb—> data) {

r=pa;

pa= pa—>next； }

else if(pa—>datadata)

8

{

r—> next = pb； r=pb；

pb = pb—> next; r—>next= pa； }

else //pa->data = = Pb—>data的情况 {

r=pa； //将原La表结点插入，原Lb表结点删除 pa = pa—> next； s=pb；

pb = pb—>next； free(s)； }

}

if(pa==NULL) //将Lb表剩余结点链到新表 r—>next=pb；

return La； //返回新表头结点地址 }

(例7-27) 设计——个将循环双链表中结点*p与其后继结点交换位置的算法。解析：本题应充分利用双向链表可对前驱结点和后继结点进行操作的特点。

具体算法如下：

int swap(dlinklist * p) {

dlinklist * q；

if(p—>next= = p—>prior) //只有一个数据结点，不能交换 return 0； //交换失败

q=p—>next； //q指向 * p的后继 p—>next=q—>next； //删除 * q q—>next—>prior= p；

q—>prior= p—>prior； //把*q插入*p前 q—>next=p；

p—>prior—>next=q； p—>prior=q；

return 1； //交换成功 }

9

8.3 典型例题

一、单项选择题

[例8-1] 在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top为栈顶指针，则向栈中压入一个元素时top的变化是( )。

A．top不变 B．top=n C．top=top-1 D．top=top+1 解析：本题答案为：C。

(例8-2) 一个栈的进栈序列是a，b，c，d，e，则不可能的出栈序列是( )。 A．edcba B．decba C。dceab D．abcde

解析：栈的特点是先进后出。在选项C中，a、b、c、d进栈，d出栈，c出栈，e进栈，e出栈，此时栈中从栈顶到栈底应该是b、a，不可能a先出栈。本题答案为：C。

[例8-3] 若已知一个栈的进栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若pl＝3，则p2为( )。

A．可能是2 B．不一定是2 C．可能是1 D．一定是1

解析：当p1＝3时，表示3最先出栈，前面l、2应该在栈中。此时若出栈，则p2为2； 此时若进栈，则p2可能为3，4，5，?，n的任何一个。本题答案为：A。

[例 8-4] 若一个栈的输入序列为1，2，3，4，?，n，输出序列的第一个元素是n，则第i个输出元素是( )。

A．n—i B．n—i—1 C．i D．n—i+1 解析：本题答案为：D。

(例8-5) 栈和队列的共同点是( )。

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

解析：栈和队列都是操作受限的线性表，只允许在表端点处进行插入和删除操作。本 题答案为：C。

(例8-6) 向一个栈顶指针为top的链栈中插入一个s所指的结点时，操作语句序列为( )。

A．top—>next=top； B．s—>next=top—>next；top—>next=s； C．s—>next＝top；top＝s； D．s—>next=top；top＝top—>next；

解析：向链栈中插入一个结点，就是在不带头结点的单链表的表头插入一个结点。本 题答案为：C。

[例8-7] 在解决计算机主机与打印机之间速度不匹配的问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据进行打印。该缓冲区应该是一个( )结构。

A．栈 B．队列 C．数组 D．线性表 解析：本题答案为：B。

(例8-8) 一个队列的入队序列是1，2，3，4，则队列的输出序列是( )。

A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．4，1，3，2 解析：本题答案为B。

[例8-9] 判断一个循环队列Q为满队列的条件是( )。 A．Q一>front= =Q—>rear B．Q一>front!＝Q—>rear

C．Q一>front= =(Q一>rear+1)％MaxSize D．Q—>front!＝(Q—>rear+1)％MaxSize

解析：由循环队列的结构可知，本题答案为：C。

10

[例8-10] 循环队列用数组A[0，MaxSize-1]存放其元素，已知其头尾指针分别是front和rear，则当前队列元素个数为( )。

A．(rear—front + MaxSize)％MaxSize B．rear—front+1 C．rear—front—l D．rear—front 解析：本题答案为：A。

(例8-11) 在一个链队列中，假设f和r分别是队头指针和队尾指针，则插入s所指 结点的运算是( )。

A．f —>next＝s；f＝s； B．r—> next＝s；r＝s； C．s—> next＝r；r＝s； D．s—> next＝f；f＝s；

解析：向链队列插入一个结点即在单链表表尾插入一个结点。本题答案为：B。 二、判断题

[例8-12] 栈是一种先进先出的线性结构。

解析：错误。栈是一种先进后出的线性结构。 [例8-13] 栈和队列都是线性表。

解析：正确。栈和队列都是操作受限的线性表。

[例8-14] 即使对不含相同元素的同一输入序列进行两组不同的但合法的人栈和出栈组合操作，所得的输出序列也一定相同。

解析：错误。根据栈的特性，不同的人栈和出栈组合操作所得的输出序列是不相同的。 [例8-15] 循环队列也存在空间溢出问题。

解析：正确。循环队列的引入只是解决了一般顺序队列的假溢问题，并没有解决溢出 问题。

[例8-16] 循环队列通常用指针来实现队列的头尾相接。

解析：错误。循环队列的首尾相接是假想的，事实上并没有实质上的相接，只是在指针时实现了从最大下标向最小下标的过渡。 三、填空题

[例8-17] 栈的特点是 ，队列的特点是 ，栈和队列都是 。 解析：本题答案为：先进后出／FILO(或后进先出／LIFO)；先进先出／FIFO；操作受限的线性表。

[例8-18] 一个栈的输入序列是：l，2，3，则不可能的栈输出序列是 。 解析：在栈的操作中，如果输入序列按递增排序号，则在输出序列中，某一个元素后 所有比它序号小的元素序号肯定是逆序的。本题答案为：3，1，2。 [例8-19] 队列是限制了插入操作只能在表的一端，而删除操作只能在表的另一端进行的线性表，其特点是 。

解析：本题答案为：先进先出。

(例8-20) 若用不带头结点的单链表来表示链栈s，则创建一个空栈所要执行的操作是 。

解析：由链栈的运算过程可知，本题答案为：s＝NULL。

(例8-21) 在链队列Q中，判定其只有一个结点的条件是 。 解析：只有一个结点时，队头指针和队尾指针都指向链表头结点。 本题答案为：Q—>front＝＝Q—>rear。 四、应用题

[例8-22] 为什么说栈是一种先进后出表?

解析：栈是一种线性表，如果把所有元素都放人栈中再出栈，则最后插入栈中的那个元素总是最先从栈中移出，因此说栈是一种先进后出表。

11

(例8-23) 对于一个栈，按顺序输入A，B，C。如果不限制出栈时机(即栈中元素不必等所有输入元素都进栈再输出)，试给出全部可能的输出序列。 解析：本题利用栈的后进先出的特点，有如下几种情况：

(1)A进，A出，B进，B出，C进，C出，产生输出序列ABC。 (2)A进，A出，B进，C进，B出，C出，产生输出序列ACB。 (3)A进，B进，B出，A出，C进，C出，产生输出序列BAC。 (4)A进，B进，C进，C出，B出，A出，产生输出序列CBA。 (5)A进，B进，B出，C进，C出，A出，产生输出序列BCA。 不可能产生的序列为：CAB。

(例8-24) 有一字符串次序为-3 * y - a/y^2，试利用栈将该字符串次序改为3y-ay^2/ * -，写出操作步骤。(可用X代表扫描该字符串并顺序取一字符进栈的操作，用S代表从栈中取出一字符加到新字符串尾的出栈操作)

解析：实现上述转换的进、出栈操作如下：

-进 3进 3出 *进 y进 y出 -进 -出 a进

a出 ／进 y进 y出 ^进 ^出 2进 2出 /出 *出 -出

所以操作步骤为：XXSXXSXSXSXXSXSXSSSS。

(例8-25) 什么是顺序队列的上溢现象?什么是假溢现象?解决假溢现象的方法有哪些? 解析：在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队的容量为 MaxSize。当有元素加入队列时，若rear＝＝MaxSize-1(初始时rear＝＝-1)，则发生队列的上溢现象，该元素不能加入队列。

队列的假溢现象是指队列中尚有空余空间，但此时rear＝＝MaxSize-1，元素不能入队。解决队列假溢的方法如下：

(1)建立一个足够大的存储空间，但这样做会造成空间浪费。 (2)采用循环队列方式。原理参照8.2.5中的介绍。

(3)采用平移元素的方法，即每当队列中删除一个元素肘，依次移动队中元素，始终使front＝＝—1。

(例8-26) 假设Q[0．．11]是一个循环队列，初始状态为front＝＝rear＝0，画出做完下列操作后队列的头、尾指针的状态变化情况。若不能人队，请指出其元素，并说明理由。 d，e，b，g，h入队 d，e出队

i，j，k，l，m人队 b出队

n，o，p，q人队

解析：本题入队和出队的变化如图8.7所示。队列没有产生上溢。

12

五、算法设计题

[例8-27] 设有两个栈S1和S2，都采用顺序结构表示，并且共享一个存储区V[o.. n-1]。为尽量利用空间，减少溢出的可能，现采用栈顶相对、迎面增长的方式存储。试设计公用栈的操作算法。

解析：让两个栈迎面增长，只有相遇时才会溢出。另外，用一个变量i(i＝1表示栈l操作，i＝2表示栈2操作)来区别S1和S2的操作。 进栈操作算法如下：

int push(datatype V[ ]，int top1，int，top2，datatype x，int i) {

if(i!＝1& & i!=2)

return 0； //参数错误 if(topl+1 !=top2) {

if(i= =1) //S1进栈操作 V[++topl]＝x；

else //S2进栈操作 V[++top2]＝x； } else

return 0； //溢出 return l； //成功 }

13

[例8-28] 设单链表中存放着n个字符，试设计判断字符是否中心对称的算法。例如，abcba和xyzzyx是中心对称。 解析：

方法一：将字符串中前一半字符进栈，然后将栈中字符逐个与链表中的后一半字符进 行比较。要注意区分字符个数为奇数和偶数的两种情况。字符串不对称时，返回值为0；反 之，返回值为1。

int mateh(1inklist * h，int n) {

linklist * p; int i＝1； datatype x； sqstack s；

initstack(&s)； //栈初始化

p=h一>next； //p指向链表第一个数据结点 while(i!=n/2+1) //扫描链表前一半 {

push(s，p—>data)； //元素进栈

p=p一>next； i++； }

if(n％2！＝0) //n为奇数 p=p—>next； while(p!=NULL) {

x=pop(s)； //元素出栈

if(x!=p—>data) //若不相等，则不对称 return 0；

p=p—>next； }

return 1； //中心对称 }

方法二：将字符串中的全部字符进栈，然后将栈中字符逐个出栈，并与链表中字符从前，往后逐个比较。字符串不对称时，返回值为0；反之，返回值为1。 int match(1inklist * h) {

linklist * p； datatype x； sqstack s；

initstack(&s)； //初始化

p=h—>next； //p指向链表第一个数据结点 while(p!=NULL) {

push(s，p—>data)； //元素进栈

p=p—>next；

14

}

p=h—>next； //P重新指向链表第一个数据结点 while(p!=NULL) {

x=pop(s)； //元素出栈

if(x!=p—>data) //若不相等，则不对称 return 0； p=p—>next； }

return 1； //中心对称 }

[例8-29] 编写一个算法，利用队列的基本运算返回队列中的最后一个元素。

解析：假设队列为循环顺序队列。建立一个临时队列，将指定队列中所有元素出队并入队到临时队列中，这样指定队列为空，再将临时队列中所有元素出队并入队到指定队列(因为不能破坏原队列结构，所以需要恢复元素)，最后一个元素即为所求。具体算法如下：

datatype lastelem (queue * Q) {

datatype x； queue tmp Q； initqueue(& tmp Q)

while(! emty (Q)) //将Q中元素放入tmpQ {

x=dequeue(Q)

enqueue(&tmpQ，x)； }

while (! empty (& tmpQ)) //将tmpQ中元素恢复回Q {

x=dequeue ( & tmpQ)； enqueue(Q，x)； } return x； }

(例8-30) 假定用一个循环单链表表示队列(循环链队，带头结点)，该队列只设一个队尾指针rear，不设队头指针，试编写算法实现下列要求： (1)向循环链队中插入一个元素x。 (2)从循环链队中删除一个结点。 解析：定义本题队列类型如下： typedef struct {

linklist * rear; } Queue2

(1)队列中人队操作是在队尾进行，即在链尾插入一个新结点。 void enqueue (Queue2 * Q，datatype x) {

15

linklist * s；

s＝(linklist * )malloe (sizeof (linklist))； //建立新结点 s—>datda=x；

s—>next=Q—>rear—>next； //将新结点插入队尾 q—>rear—>next = s； q—>rear = s； }

(2)队列中出队操作是在队头进行，即删除链表第一个数据结点。 datatype dequeue (Queue2 * Q) {

datatype x； linklist * p；

if (Q—>rear—>next= =Q—>rear) //队列为空 return NULL；

p＝Q一>rear一>next一>next； //p指向队头结点 x=p一>data；

Q一>rear一>next一>next＝p一>next //删除 * p结点 free (p)

return x； //返回原队头元素 }

注意：队列和栈都是线性表，它们是操作受限的线性表。在考虑它们的性质、算法的时候可以结合上一章中有关线性表的内容。

16

9.3 典 型 例 题

一、单项选择题

[例9-1] 下列操作中，( )是数组的基本运算。 A．插入 B．删除 C．修改 D．排序

解析：数组的基本运算只有两种，一种是给定一组下标，存取相应的元素；另一种是 给定一组下标，修改相应数据元素中某个数据项的值。本题答案为：C。 (例9-2) 一维数组和线性表的区别是( )。

A．前者长度固定，后者长度可变 B．后者长度固定，前者长度可变 C．两者长度均固定 D．两者长度均可变

解析：由数组和线性表的定义可知，数组的长度是固定的，而线性表的长度是可变的。 本题答案是：A。

[例9-3] 二维数组A的每个元素是由6个字符组成的字符串，其行下标i＝0，1，?，8，列下标j＝1，2，?，10。当A按行存储时，元素A[8，5]的起始地址与当A按列存储时的元素( )的起始地址相同(设每个字符占一个字节)。

A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9]

解析：当A按行存储时，元素A[8，5]前共有(8—0)×(10—1+1)+(5—1)＝84个元素。对侯选答案进行类似计算可知，本题答案为：B。

(例9-4) 有一个100×90的稀疏矩阵，有非零元素(整型)10个。设每个整型数占2个字节，则用三元组表表示该矩阵时，所需的字节数为( )。 A．60 B．66 C．18 000 D．33

解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用手存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。本题答案为：B。

[例9-5] 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上的所有元素)依次存放于一维数组B[0..(n(n+1))／2—1)中，则在B中确定ai，j(i

A．

i(i?1)j(j?1)i(i?1)j(j?1)?j B．?i C．?j D．?i 2222解析：参考9.2.3节有关对称矩阵的内容可知，本题答案为：D。

二、填空题

(例9-6) 三维数组A[c1..d1，c2..d2，c3..d3]共含有 个元素。 解析：第一维大小为d1-cl+1，第二维大小为d2-c2+1，第3维大小为d3-c3+1，共有(dl-c1+1)×(d2-c1+1)×(d3-c3+1)个元素。

本题答案为：(d1-c2+1)×(d2-c1+1) ×(d3-c3+1)。

[例9-7] 设二维数组A[-20..30，-30..19]，每个元素占用4个存储单元，存储起始地址为200。如按行优先顺序存储，则元素A[25][18]的存储地址为 ；如按列优先顺序存储，则元素A[一18][一25]的存储地址为 。

解析：当按行优先顺序存储时，元素A[25][18]的存储地址为： LOC(A[25][18])＝LOC(A[-20][-30])+((25-(-20))×(19-(-30)+1) +(18-(-30)))×4 ＝200+9192＝9392

当按列优先顺序存储时，元素A[-18][-25]的存储地址为：

LOC(A[-18][-25])＝LOC(A[-20][-30])+((-25-(-30))×(30-(-20)+1)

+(-18-(-20))) × 4

17

=2004+1028=1228 本题答案为：9392；1228。

[例9-8] 将一个10阶对称矩阵A用压缩存储方式(以行为主序存储下三角，且a00＝1)进行存储，设每个元素占一个地址空间，则a85的地址为 。

解析：矩阵下标从0开始，以行为主序存储下三角，a85前有8行，第0行1个元素，第1行2个元素，??，第7行8个元素，共计(1+8)×8／2＝36个元素，第8行中a85前有5个元素。所以，a85前共有36+5＝41个元素，其地址为41+l＝42。本题答案为：42。 [例9-9] 一稀疏矩阵有8个非零元素，矩阵元素为整型。现用三元组表方式对其进行压缩存储，假设整型元素占2个存储单元，则该三元组表至少占 个存储单元。

解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用于存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。表头部分占3×2＝6个存储单元，主表部分占8×3×2＝48 个存储单元，总共占6+48＝54个存储单元。本题答案为：54。 三、应用题

[例9-10] 已知An×n为稀疏矩阵，试从空间和时间的角度比较采用两种不同的存储 结构二维数组和三元组表完成求?aii运算的优缺点。

i?0n?1 解析：由题目可知，所进行的运算是计算主对角线元素之和。对于采用二维数组方法存储的矩阵，需要n2个存储单元，但由于可以进行随机存取，即可以随机地访问主对角线上的元素，因此时间效率比较高。采用三元组表方法存储矩阵时是压缩存储，节省了存储空间，但在算法实现上需要从头到尾扫描整个三元组表，因此时间效率相对低一些。 (例9-11) 设给定n维数组A[c1..d1][c2..d2)?[cn..dn)，如果A[c1][c2]?[cn]的存储地址为a，每个元素占用1个存储单元，求A[i1][i2]?[in]的存储地址。

解析：若整个数组采用按行优先顺序存储，则A[i1][i2]?[in]的存储地址为： LOC(A[i1][i2]?[in])=a+((i1-c1)×(d2-c2+1)×?×(dn-cn+1) +(i2-c2)×(d3-c3+1)×?×(dn-cn+1) ?

+(in-cn))×l

若整个数组采用按列优先顺序存储，则A[i1][i2]?[in]的存储地址为： LOC(A[i1][i2]?[in])=a+((in-cn)×(dn-1-cn-1+1)×?×(d1-c1+1)

+(in-1-cn-1)×(dn-2-cn-2+1)×?×(d1-c1+1)

?

+(i1-c1))×l

(例 9-12) 设上三角矩阵An×n，将其上三角元素逐行存于数组B[m]中，使得B[k]＝aij，且k=f1（i）+f2（j）+c。试推导出函数f1（i）、f2（j）和常数C。 解析：由前面内容的分析可得k和i、j之间的关系为：

?1)?i(2n?i+j-i 当i≤j时 ??2 k??

n(n?1)? 当i>j时，存放常数c ??2

当i≤j时，有

f1(1)=?n?1?i?1i2

???2?2 18

f2(j)=j

C=0

当i>j时，有

f1(i)=f2(j)=0

C?n(n?1) 2四、算法设计题

(例9—13) 已知一个n×n矩阵B按行优先顺序存储在一个一维数组A[0..n×n一1) 中，试给出一个算法将原矩阵转置后仍存于数组A中。

解析：矩阵转置是将矩阵中第i行第j列的元素与第j行第i列的元素位置互换。因此， 先确定矩阵与一维数组的映射关系：bi，j在一维数组A中的下标为i×n+j，bi，j在一维数组A中的下标为j×n+i。具体算法如下： void trans ( datatype A[]，int n) {

int i，j；

datatype temp； for(i=0；i

temp=A[i * n+1]；

A[i * n+j]=A[j * n+i]； A[j * n+i]=temp； } }

(例9-14) 假设稀疏矩阵A采用三元组表表示，试编写一个算法求其转置矩阵B，要求B也用三元组表表示。

解析：三元组表表示要求按行的顺序存放，所有转置过程不能直接将行下标和列下标 转换，还必须使得转置后矩阵按顺序存放。因此，首先在A中找出第一列中的所有元素 (即B中第一行)，并把它们依次存放在转置矩阵B的三元组表中；然后依次找出第二列中的所有元素，把它们依次存放在三元组表B中；最后按此方法逐列进行，直到第n列的操作完成。值得注意的是，除了各元素的行号列号需要互换外，表头部分的行数列数也应该互换。具体算法如下：

void transmatrix (smatrix * A，smatrix * B) {

int p，k，col；

B—>m=A—>n； //B的行数为A的列数 B—>n=A—>m； //B的列数为A的行数

B—>t=A—>t； //转置前后非零元素个数不变 if(B—>t!＝0) //非0矩阵 {

k=0； //B表元素计数器，作当前放置元素指针 for(col=0；coln；col++)

19

for(p＝0；pt；p++) if(A—>data[p].j＝＝co1) {

B—>data[k]．i=A—>data[p].j； B—>data[k].j=A—>data[p].i B—>data[k].v＝A—>data[p].v； K++

}

} }

20

10.3 典型例题

一、单项选择题

[例10-1] 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则 T中的叶子数为( )。

A．5 B．6 C．7 D．8 解析：假设度为0的结点数为n。，度为1的结点数为n1，??，度为4的结点数为n4， 则结点数n＝n0+n1+n2+n3+n4。又因为树的结点数为分支数加1，而分支数为n0×0+n1×1+n2×2+n3×3+n4×4，所以可得n0+n1+n2+n3+n4＝n1×1+n2×2+n3×3+n4×4+1，将已知条件代人得n0＝8。本题答案为：D。

[例10-2] 树最适合用来表示( )。

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

C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 解析：由树的特点可知，本题答案为：C。

[例10-3] 如图10.13所示的二叉树中，( )不是完全二叉树。

解析：在一棵二叉树中，除最后一层外其余各层都是满的，最后一层或者是满的，或者是结点都集中在左边，这样的二叉树称为完全二叉树。由此可见，A不是完全二叉树，B、C是完全二叉树，D为空树，也是完全二叉树。本题答案为：A。 (例10-4] 如图10．14所示的二叉树的中序遍历序列是( )。

A．abdefgc B．dbgfeac C．dbfgeac D．dgfebac 解析：由二叉树中序遍历(LDR)可知，本题答案为：C。

(例10-5) 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 ( )。

A．空树或只有一个结点的二叉树 B．高度等于其结点数的二叉树 C．完全二叉树 D．二叉排序树

21

解析：对于高度等于其结点数的二叉树，每层只有一个结点，假设从上向下分别为a1，a2，?，an，则先序遍历序列为a1，a2，?an，后序遍历序列为an，an-1,?，a1。本题答案为：D。

[例10-6] 按照二叉树的定义，具有3个结点的二叉树有( )种不同的树形。 A．3 B．4 C．5 D．6

3C2nnC6?5。本题答案为：C。 解析：n个结点的二叉树总数为＝

n?14(例10-7) 在一非空二叉树的中序遍历中，根结点的右边( )。

A．只有右子树上的结点 B．只有右子树上的部分结点 C．只有左子树上的结点 D．只有左子树上的部分结点 解析：在中序遍历序列中，根结点将左、右子树上的结点分开，左边为左子树上的结点，右边为右子树上的结点。本题答案为：A。 [例10-8] 用于编码的是( )。

A．完全二叉树 B．二叉排序树 C．最优二叉树 D．空树

解析：用于编码的二叉树是哈夫曼树，又称最优二叉树。本题答案为：C。 (例10-9) 根据使用频率，为5个字符设计的哈夫曼树编码不可能是( )。 A．000，001，010，011，1 B．0000，0001，001，01，1 C．000，001，01，10，11 D．00，100，101，110，111

解析：哈夫曼树中只有度为0或2的结点，D不满足这种条件。本题答案为：D。 [例10-10] 一个具有1024个结点的二叉树的高h为( )。 A．11 B．10

C．11~1024之间 D．10至1024之间

解析：根据二叉树的性质2，可知高度为k的二叉树至多有2k-1个结点，即高度为10的二叉树至多有1023个结点；而当二叉树每层只有一个结点时，树高和结点数是一样 的。本题答案为：C。 二、判断题

[例10-11] 二叉树是一种特殊的树，度为2的树就是二叉树。

解析：错误。二叉树是一种特殊的树，但是度为2的树不一定是二叉树。原因是二叉树为有序树，并且二叉树中不一定存在度为2的结点。

[例10-12] 二叉树的先序遍历序列中，任意一个结点均处于其孩子结点前面。 解析：正确。先序遍历时，应先访问根结点，再访问其孩子。 [例10-13] 将一棵树转换成二叉树后，根结点没有左子树。 解析：错误。从树和二叉树的相互转换可知，由一棵树转换成的二叉树，根结点必无 右子树，没有左子树的情况只有两种：空树和只有一个结点的树。

(例10-14) 用树的先序遍历序列和中序遍历序列可以导出树的后序遍历序列。

解析：正确。用树的先序遍历序列或后序遍历序列加上中序遍历序列可以恢复二叉树，从而可以得出另一个遍历序列。

(例10-15) 中序遍历一棵二叉排序树的结点就可得到值递增的结点序列。

解析：正确。二叉排序树的特点是左子树上所有结点的值小于根结点的值，根结点的值小于右子树上所有结点的值。中序遍历的顺序是先遍历左子树，再访问根结点，最后遍历右子树。因此，中序遍历一棵二叉排序树的结点所得到的序列是递增的，命题正确。

(例10-16) 在由同样的叶子结点构成的树中，哈夫曼树是带权路径长度最小的树，路

22

径上权值较大的结点离根较近。

解析：正确。由哈夫曼树的定义可知本命题正确。 三、填空题

(例10—17) 有一棵树如图10.15所示，试回答下列问题： (1)这棵树的根结点是 。 (2)这棵树的叶子结点有 。 (3)结点b的双亲是 。 (4)结点b的子孙有 。 (5)结点b的兄弟是 。 (6)树的度为 。

(7)树的深度为 。

解析：由树的相关定义可知，本题答案为：(1)a；(2)c，d，e，h5(3)a；(4)d，e，f，g，h； (5) c；(6) 3；(7) 5。

[例10-18] 结点数最少的二叉树为 。 解析：本题答案为：空树。

[例l0-19] 在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。 解析：由二叉树的性质4可知，具有n个结点的完全二叉树的深度为[1bn]+1或[1b(n+1)]。又因为用顺序存储的二叉树的结点编号和完全二叉树中相同位置上结点的编号是一致的，所以如果编号为i和j的两个结点处在同一层，则有[1bi]＝[1bj]。本题答案为：[1bi]＝[1bi]。 [例10-20] 深度为h的完全二叉树至少有 个结点；至多有 个结点；h和结点总数n之间的关系是 。

解析：由二叉树的性质2可知，高度为k的二叉树至多有2k一1个结点。由性质4可

—

知，具有n个结点的完全二叉树的深度为[1bn]+1或[1b(n+1)]。所以本题答案为：2h 1;2 h

-1;h=[1bn]+1或h＝[1b(n+1)]。

[例10-21] 在二叉树中，指针p所指结点为叶子结点的条件是 。

解析：叶子结点的特点是没有子树。本题答案为：p一>lchild = =NULL && p一>rchild= =NULL。

[例10-22] 高度为8的完全二叉树至少有 个叶子结点。

解析：在完全二叉树中，度为1的结点要么没有，要么只有一个；又由二叉树的性质3 可知，任何一棵二叉树的叶子结点数no为度为2的结点数n2加1。由此可知，完全二叉树的叶子结点数基本是随着总结点数的增多而增多的，即在同样高度的完全二叉树中，结点最少的完全二叉树的叶子结点也最少。高度为8的完全二叉树的结点最少有27个，叶子结点为26个。本题答案为：64。

23

[例10-23] 一棵二叉树的先序遍历、中序遍历和后序遍历序列分别如下，其中有一部分未显示出来。试填补空格处的内容。 先序遍历序列： B F ICEH G 中序遍历序列： D KFIA EJC 后序遍历序列： K FBHJ G A 解析：由三种遍历序列的特点可知，先序遍历为每棵子树的根结点总在该子树中其他结点前被遍历；中序遍历为左子树结点在前，根结点次之，右子树结点最后；后序遍历为每棵子树的根结点总在该子树中其他结点后被遍历。由此可推断出：先序遍历序列空格中依次填入A、D、K、J，中序遍历序列中依次填入B、H、G，后序遍历序列中依次填人D、I、E、C。

[例10-24] 若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度为 。

解析：本题答案为：69。 四、应用题

(例10-25) 从概念上讲，树、森林和二叉树是三种不同的数据结构，将树、森林转换成二叉树的基本目的是什么?并指出树和二叉树的主要区别。 解析：树和森林转换成二叉树是为了采用二叉树的存储结构并利用二叉树的已有算法解决树和森林的有关问题。

树和二叉树的主要区别是：树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树中结点的子树无左、右之分，而二叉树中结点的子树有严格的左、右之分。

（例l0-26) 请说明一棵二叉树进行先序、中序和后序遍历后，其叶子结点的相对次序是否会发生改变?为什么?

解析：在二叉树中，叶子结点必在某结点的左或右子树中。因为三种遍历方法对左、右子树的遍历都是按左子树在前、右子树在后的顺序进行的，所以在三种遍历序列中，叶子结点的相对次序是不会发生改变的。

[例10-27] 一棵完全二叉树用一维数组存放为：abcdefghijk。请写出中序遍历该二叉树的访问结点序列。 解析：由顺序存储完全二叉树的存储方式，我们很容易画出这棵完全二叉树的树形结构。对其进行中序遍历得到的序列为：hdibjekafcg。

[例10-28] 假设二叉树采用顺序存储结构，如图10.16所示。 (1)画出此二叉树树形。

(2)写出此二叉树的先序、中序和后序遍历序列。 (3)将此二叉树转换为森林。

解析：(1)此二叉树树形如图10．17所示。 (2)该二叉树的遍历序列如下： 先序遍历序列：bcdfeagh 中序遍历序列：cfdebahg 后序遍历序列：fedchgab

(3)转换成的森林如图10.18所示。

24

(例10-29) 已知哈夫曼树的叶子结点数为no，试推导出该哈夫曼树共有多少个结点。

解析：设度为1的结点数为n1，度为2的结点数为n2，结点总数为n，则有

n=n0+n1+n2

根据二叉树的性质3有

n=n2+1

又由哈夫曼树的构造原理可知，哈夫曼树中不存在度为l的结点，即nl＝0，所以有

n=n0+n2=n0+n0-1=2n0-1

[例10-30] 设给定字符集合{a，b，c，d，e，f} 的权值集合w={2，3，4，?，8，9}，试构造关于w的一颗哈夫曼树，并求其带权路径长度及各字符的哈夫曼编码。 解析：根据给定的权值集合构造的哈夫曼树如图10.19所示。 其加权路径长度WPL＝(9+7+8)×2+4×3十(2+3)×4＝80。 各字符的哈夫曼编码如下：

a 0000 b 0001 c 001 d 10 e 11 f 0l

注意：此题哈夫曼树形不唯一，因此哈夫曼编码也有多种方案，但WPL是一定的。 五、算法设计题

25

[例10-31] 给定一个二叉树t，试设计算法输出其嵌套括号的表示。

解析：首先输出根结点，然后再依次输出它的左子树和右子树，在输出左子树之前输出左括号，在输出右子树之前输出右括号；若左、右子树都为空，则无需输出。

具体算法如下：

void disptree(bitree * t) (

if(t! =NULL) {

printf(\—>data)；

if(t—>lchild ! =NULL | | t—>rchild ! =NULL) {

printf (\；

disptree(t—> lchild)； if(t—>rchild ! =NULL) printf(\，\； disptree(t—>rchild)； printf(\； } } }

[例10-32] 假设二叉树采用链式存储，编写一个二叉树后序遍历的非递归算法。 解析：根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点。先扫描根结点的所有左结点并入栈，然后扫描当前栈顶结点的右孩子并入栈，再扫描该右孩子的所有左结点并人栈，最后扫描当前栈顶结点的右孩子并人栈，反复进行，直到当前栈顶结点没有右孩子(此过程从根出发，查找最左下方第一个叶子结点，并将所经过的结点人栈)。若栈顶结点的左、右子树都已被访问，则访问它并出栈；否则以它的右孩子为根出发重复开始的过程。如此这般，直到栈空为止。其中的难点是如何判断一个结点的右孩子结点已访问过，为此用p保存刚访问过的结点，若t一>rchild＝＝p成立(在后序遍历中，t的右孩子结点必然在t之前被访问)，则说明t的左、右子树均已访问，现在应访问t。具体算法如下：

void lastorder (bitree * t) {

bitree * stack [MaxSize]，* p；

int flag，top= -1； //置空栈 do {

while (t! =NULL) //将t的所有左结点人栈 {

top++； stack[top]＝t t=t—>lchild； }

p=NULL； //p指向当前结点的前一个已访问结点 flag=1； //设置t的访问标志为已访问

26

while (top!＝-1&& flag) {

t=stack[top] //取当前栈顶元素

if(t—>rchild==p) //右子树不存在或已被访问，访问t {

printf(“％d”，t—>data)；

top--； //出栈 p=t； } else {

t=t一>rchild； //t指向其右子树

flag=0； //设置未被访问的标志 } }

} while(top!=-1)； //当栈非空 }

(例10-33) 设一棵完全二叉树采用顺序存储结构存储在数组bt[n+1](从下标为1到下标为n)中，请写出非递归的先序遍历算法。

解析：由二叉树的顺序存储可知，将完全二叉树的结点以层为序，同层从左到右进行编号，然后以编号为下标存储在数组bt中。根据二叉树性质5可得出结点间的存储与逻辑的对应关系。具体算法如下： void preoder ( int bt[]，int n) {

int root，top，stack [MaxSize]；

root=1； //root指向根结点 top= —1； //置空栈 while (rooto) {

while (root

print (“％ d”，bt[root])；

top++； //访问过的结点人栈 stack [top]=root；

root=2 * root； //指向左孩子 }

if(top!= -1) //指向栈顶元素的右孩子，并出栈 {

root=stack[top] * 2+1；

top--； } } }

(例10-34) 假设二叉树采用链式存储结构，设计一个算法求二叉树中指定结点的层数。

27

解析：本题采用递归算法，设h返回p所指结点的高度，初始值为-1。找到指定的结 点时返回其层次；否则返回-1。1h作为一个中间变量在计算、搜索层次时使用，初始值为 1。具体算法如下：

void level(bitree * t，bitree * p，int * h，int lh) {

if(b = =NULL)

h= -l； //空树时返回—1 else if (p==t) //找到结点p h=lh； else {

level(t—>lchild，p，h，lh+1)； //在左子树中查找 if (* h = = - 1)

level(t—>rchild，p，h，1h+1)； //在右子树中查找

} }

[例10-35] 设计一个算法，判断一棵二叉树是否为完全二叉树。

解析：若二叉树采用链式存储结构，则根据完全二叉树的定义，对完全二叉树按层次遍历时应该满足：若某结点没有左孩子，则必无右孩子；若某结点缺孩子，则其所有的后继都是叶子。若不满足以上条件，则该二叉树就不是完全二叉树。具体算法如下： int fullbitreel (bitree * t)

{

bitree * s，* Q[MaxSize]；

int rear=1，front=0，flag=1； //flag表示到目前为止所有结点均有2个孩子 if(t＝＝NULL) return 1；

Q[rear]＝t //根结点地址人队 while (front

front++； //出队 s=Q[front]；

if (!flag && (s—>1child!＝NULL | | s—>rchil！＝NULL)) return 0；

if (s—>1child＝＝NULL) {

flag=0； //无左

if (p—>rchild! = NULL) //左空右不空，非完全二叉树

return 0； } else {

Q一>[++rear]＝s—>lchild； //s结点的左孩子的地址人队 if (s一>rchild＝＝NULL)

flag=0； //有左无右

28

else

Q一>[++rear]＝s—>rchild； //s结点的右孩子的地址人队 } }

return 1； }

若二叉树采用顺序存储结构，则只需判断从第一个结点位置到最后一个结点位置之间 没有空结点即可。假设二叉树存储在数组bt[n+1]中，具体算法如下： int fu11bitree2 (char bt[]，int n) {

int i；

for(i＝1；i<＝n；i++) if(A[i]]＝＝’@’) return 0; return 1 }

(例10-36) 假设二叉树以链式结构存储，编写一算法判断此二叉树是否为二叉排序树。 解析：由于二叉排序树的中序遍历序列为一递增序列，所以利用中序遍历算法即可判 断该二叉树是否为二叉排序树。具体算法如下： int judgebst ( bitree * t，datatype pre)

//pre为当前遍历结点中序前驱，初值为最小值 {

int m1，m2； if(t==NULL)

return 1； //空树，返回1 ml＝judgebst (t一>lehild，pre)； //判断左子树 if(ml==0)

return 0； //左子树不是BST，整棵树就不是BST if(t—> data<＝pre) //非递增，不是BST return 0；

m2＝judgebst(t一>lchild，pre)；

return m2； //右子树不是BST，整棵树就不是BST }

29

11.3 典型例题

一、单项选择题

(例11-1) 若无向图的顶点个数为n，则该图最多有( )条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0

解析：任意一个顶点与其他n-1个顶点间最多有n-l条边，又因为无向图任意两个顶点间至多只能有一条边，所以边数最多为n(n-1)/2。本题答案为：B。

[例11-2] 在一个图中，所有顶点的度数之和等于所有边数的( )倍。 A．1/2 B．2 C．1 D．4

解析：因为每条边与两个顶点相关联，即给这两个顶点分别产生1个度，所以所有顶点的度数之和是所有边数的两倍。本题答案为：B。

(例11-3) 在一个有向图中，所有顶点的人度之和等于所有顶点的出度之和的 ( )倍。

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

解析：在有向图中，任意一条弧对起点来说产生一个出度，对终点来说产生一个入度， 也就是说出度和入度是一一对应的。本题答案为：C。

(例11-4) 一个有n个顶点的图，最少有( )个连通分量，最多有( )个连通分量。 A．0 B．1 C．n-1 D．n

解析：n个顶点的图，如果是连通图，则只有1个连通分量；如果图中不包含边，则每 个顶点自成连通分量，有n个连通分量。本题答案为：B；D。

(例11-5) 具有7个顶点的无向图至少应该有( )条边才能确保是一个连通图。 A．5 B．6 C．7 D．8 解析：n个顶点的连通图中至少有n-1条边。本题答案为：B。

(例11-6) 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的元素个数为( )。

A．n B．(n-1)2 C．n-1 D．n2 解析：由图的邻接矩阵表示可知，本题答案为：D。

(例11-7) 当一个有n个顶点的有向图用邻接矩阵A表示时，顶点vi的度是 ( )。 A．

?A[i][j] B．?A[i][j] C．?A[j][i] D．?A[i][j]??A[j][i]

i?0n?1n?1n?1i?0n?1i?0n?1j?0j?0解析：在有向图的邻接矩阵中，顶点对应的行上非零元素个数之和为该顶点的出度，顶点对应的列上非零元素个数之和为该顶点的入度，而顶点的度为出度与人度之和。本题答案为：D。

[例11-8] 某无向图如图11.11所示，在下面的5个序列中，符合该图深度优先搜索遍历的序列有( )。

a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．5个 B．4个 C．3个 D．2个

30

f d e b”和“a e d f □c b“中加框 解析：由图的深度优先搜索遍历可知，序列“a c □

顶点为出错的遍历顶点，其他序列都是正确序列。本题答案为：C。

(例11-9) 某无向图如图11.1l所示，在下面的5个序列中，符合该图广度优先搜索遍历的序列有( )。

a e b c d f a c f d e b a e d f b c a e b c f d a b e f c d A．5个 B．4个 C．3个 D．2个

f d e b”d f b c” 解析：由图的广度优先搜索遍历可知，序列“a c □、“a e □，和“a b e

f c d”□，中加框顶点为出错的遍历顶点，其他序列都是正确序列。本题答案为：D。

(例11-10) 已知一有向图的邻接链表存储结构如图11．12所示，以顶点0为出发点的深度优先搜索遍历序列为( )。

A．0 1 2 4 3 B．0 1 2 3 4 C．0 2 3 4 1 D．0 3 2 4 1 解析：由深度优先搜索遍历算法可知，本题答案为：C。

(例11—11) 已知一有向图的邻接链表存储结构如图11.12所示，以顶点0为出发点的广度优先搜索遍历序列为( )。

A．0 1 2 3 4 B．0 2 1 3 4 C．0 2 3 4 1 D．0 3 2 4 1 解析：由广度优先搜索遍历算法可知，本题答案为：B。 (例11-12) 任何一个无向连通图的最小生成树( )。 A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在

解析：任何一个无向连通图有一棵或多棵最小生成树。本题答案为：A。 [例11-13] 关键路径是事件顶点网络中( )。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路

解析：在AOE网中，从源点到汇点的最长路径称为关键路径。本题答案为：A。

二、判断题

31

[例ll-14] 在有n个结点的无向图中，若边数大于n-1，则该图必是连通图。 解析：错误。n个顶点的无向图至多有n(n-1)/2条边，假设一无向图顶点数为7， 图中任意6个顶点间边数至多为15条，显然15>6。若此6个顶点与另一顶点间没有边相 连，即此图不连通。

(例11-15) 有向图中顶点i的度等于其邻接矩阵中第i行中1的个数。

解析：错误。有向图的邻接矩阵中第i行中1的个数为图中顶点i的出度，第i列中1的个数为图中顶点i的入度，两者之和为顶点i的度。 [例11-16] 强连通分量是无向图的极大强连通子图。 解析：错误。强连通分量是有向图的极大强连通子图。

(例11-17) 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 解析：错误。根据图的邻接矩阵存储方式可知，无向图的邻接矩阵一定是对称矩阵，而有向图的邻接矩阵一般是非对称矩阵，但若有向图中的弧都是成对的(即有，则必有)，则其邻接矩阵也是对称矩阵。

[例ll-18] 不同的求最小生成树的方法最后得到的生成树是相同的。 解析：错误。连通图的最小生成树有可能是多棵。

(例11-19) 拓扑排序算法把一个无向图中的顶点排成一个有序序列。

解析：错误。拓扑排序是将AOV网中的所有顶点排成一个线性序列，它的排序对象是有向图。

(例11-20) 若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。

解析：正确。

[例11-21] 在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。

解析：错误。在AOE网中，关键路径上某个活动的时间缩短，整个工程的时间有可能 缩短，只有缩短了包含在所有路径上的那些关键活动时，才一定能缩短整个工程的时间。 三、填空题

[例11-22] 判断一个无向图是一棵树的条件是 。

解析：树是连通的，且树中必无回路。本题答案为：图是连通的且不存在回路。 [例11-23] 一个连通图的 是一个极小连通子图。 解析：由生成树的定义可知，本题答案为：生成树。

[例11-24] 图G是一个非连通无向图，共有28条边，则该图至少有 个顶点。 解析：图G是非连通无向图，至少有两个连通分量，其中一个连通分量最少的顶点数是由28条边组成的无向图，设其顶点数为n，边数为e，则有e≤n(n-1)/2，e＝28，可得n≥8；另一个连通分量只有一个顶点，所以该图至少有9个顶点。本题答案为：9。

(例11—25) 已知一有向图的邻接链表存储结构如图11.13所示，以顶点0为出发点的深度优先搜索遍历序列为 ；广度优先搜索遍历序列为 。

32

解析：由图的遍历算法可知，本题答案为：03241；03214。

[例11-26] 已知一个有向图用邻接矩阵表示，删除所有从第i个顶点出发的边的方法是 。

解析：邻接矩阵第i行的非零元素表示从第i个顶点出发的边。本题答案为：将邻接矩阵第i行元素全部置0。

[例11—27] 对有n个顶点的连通图来说，它的生成树一定有 条边。 解析：由生成树的定义可知，本题答案为：n—l。

[例11—28] 有向图G可拓扑排序的判别条件是 。 解析：根据拓扑排序算法可知，本题答案为：图中不存在环。 (例11—29) 一个无向网络如图11.14所示，用Prim算法

从顶点0开始求其最小生成树，按次序产生的边为 ，共 条边；用Kruskal算法产生的边次序为 ，共 条边。(注：边用( i，j形式表示。)

解析：从顶点。开始求最小生成树，按次序产生的边为：(0，3)，(3，5)，(5，2)，(3，1)，(1，4)共5条边。采用Kruskal算法产生的边次序为：(0，3)，(2，5)，(3，5)，(1，3)，(1，4)共5条边。本题答案为：(0，3)，(3，5)，(5，2)，(3，1 )，(1，4)；5；(0，3)，(2，5)，(3，5)，(1，3)，(1，4)；5。

(例11—30) 设图G有n个顶点和e条边，采用邻接矩阵存储，则拓扑排序算法的时间复杂度为 。 解析：拓扑排序算法需查找每个顶点的入度域和每个顶点出边对应的顶点，其时间复杂度为O (n+e)。本题答案为：O (n+e)。 (例11—31) AOV网中，顶点表示 ，边表示 。AOE网中，顶点表示 ，边表示 。

解析：根据AOV网和AOE网的定义可知，本题答案为：活动；活动间的先后关系；事件；活动。 四、应用题

[例11—32] (1)如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边?

(2)如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边?G2最 少有多少条边?

解析：(1)G1最多有n(n-1)／2条边，最少有n-1条边。 (2) G2最多有n(n-1)条边，最少有n-1条边。

[例11—33] 证明具有n个顶点和n-1条边的无向连通图G是树。

证明：设图G是无向连通图但不是树，则G中必有回路存在，可以从回路中去掉一条边且使得G仍然是连通的。这时，G成为含有n个顶点但只有n-2条边的连通图，这显 是不可能的，即假设错误。所以命题正确，证毕。

[例11—34] 判断一个图G中是否有回路的方法有哪些? 解析：判断一个图中是否有回路的方法一般有以下四种。

方法一：利用拓扑排序算法可以断定图G中是否有回路。在拓扑排序中，若输出顶点数小于总顶点数，则图G中必存在回路。 方法二：设图G是有n个顶点的无向连通图，若G的边数e≥n，则图G中必存在回路，反之亦然。利用这一原理，只要计算图G中的边数，即可判断图中是否有回路。

方法三：设图G是有n个顶点的无向连通图，若G的每个顶点的度大于或等于2，则

33

图中一定有回路。

方法四：利用深度优先搜索遍历算法可以判断图G中是否有回路。对于无向图来说，若在深度优先搜索遍历过程中遇到了回边，则必定存在回路；对于有向图来说，这条回边可能是指向深度优先搜索遍历中另一棵生成树上的顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在该次递归遍历结束前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，因此，有向图中必定存在包含顶点v和顶点u的环。

(例11—35) 已知带权连通图G＝(V，E)的邻接链表如图11.15所示。请画出该图，并分别以深度优先搜索和广度优先搜索遍历该图，写出从顶点。出发的遍历序列，并画出该图的一个最小生成树。图11.15中链表结点的三个域依次为顶点序号、边的权和指针。

解析：由题目给出的邻接链表中存储的信息，可以得出图G，如图11.16所示。从顶点 0出发进行深度优先搜索遍历的序列为0，1，2，3，4；进行广度优先搜索遍历的序列为0， 1，2，3，4。最小生成树如图11.17所示。

[例11—36] 设有数据逻辑结构为： G＝(V，E)，V＝{v1，v2，?，v9}

E＝{(v1，v3)，(Vl，V8)，(v2，v3)，(v2，v4)，(v2，v5)，(v3，v9)，(v5，v6)，(v8，v9)， (V9，v7)，(v4，v7)，(v4，v6)} (1)画出这个逻辑结构的图示。

(2)相对于关系E，指出所有的开始顶点和终端顶点。

(3)分别对关系E中不同的开始结点，举出一个拓扑序列的例子。 (4)分别画出该逻辑结构的邻接链表和逆邻接链表。 (5)对于(4)画出的邻接链表，请画出该图的深度优先搜索生成树和广度优先搜索生成树。

解析：(1)根据题目给出的关系E，可得这个逻辑结构如图11.18所示。

34

(2) 根据开始顶点和终端顶点的定义，可知开始顶点是入度为零的顶点，终端顶点是出度为零的顶点。所以开始顶点有：v1，v2；终端顶点有：v6，v7。

(3)根据拓扑排序算法，可得以v1为起始点的拓扑序列之一为1，8，2，3，9，4，7， 5，6；以v2为起始点的拓扑序列之一为2，1，8，3，9，4，7，5，6。

(4)该逻辑结构的邻接链表和逆邻接链表如图11.19所示。

(5)该图的深度优先搜索生成树和广度优先搜索生成树如图11.20所示。

[例11—37] 已知图G的邻接矩阵如下所示：

?? ???0 1 0 1 ?0 0 1 0 ? 1 0 0 0 ??0 0 1 0 ?(1)请由邻接矩阵画出相应的图G。

(2)图G中的所有顶点是否都在它的拓扑序列中? (3)如果要使此图成为完全图，还需增加几条边? 解析：(1)由邻接矩阵画出的图G如图11.21所示。

35

(2)由图11.21可见，图G中有环存在，因此对图G进行拓扑排序并不能输出所有顶点，即有顶点不在拓扑序列中。

(3)n个顶点的完全有向图有n(n-1)条边。图G有4个顶点、5条边，若要使其成为完全有向图，还需要4×(4—1)-5＝7条边。

(例11—38) 已知AOE网中顶点vl，v2，v3，v4，v5，v6，v7，分别表示7个事件，弧a1，a2，a3，a4，a5，a6，a7，a8，a9，a10分别表示10项活动，弧上的数值表示每项活动花费的天数，如图11.22所示。请分别计算出各事件的最早发生时间、最晚发生时间，各活动 的最早开始时间、最晚开始时间以及时间余量。用顶点序列表示出关键路径，并给出关键活动。

解析：各事件的最早发生时间及最晚发生时间如表11.1所示，各活动的最早开始时间、最晚开始时间以及时间余量如表11.2所示。

表11.1 各事件的最早发生时间及最晚发生时间

事件 最早发生时间 最晚发生时间

活动 最早开始时间 最晚开始时间 时间余量 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 0 0 0 3 3 2 2 6 7 5 0 0 1 3 4 5 3 6 7 6 0 0 1 0 1 3 1 0 0 1 v1 v2 v3 v4 v5 v6 v7 0 3 2 6 7 5 10 0 3 2 6 7 6 10 表11．2 各活动的最早开始时间、最晚开始时间及时间余量

由表11.1和表11.2可知，关键路径有两条：v1，v2，v5，v7和v1，v4，v5，v7；关键活动为：a1，a4，a2，a8，a9。

[例11—39] 试证明当深度优先搜索遍历算法应用于一个连通图时，所经历的边形成一棵树。

证明：由深度优先搜索遍历算法可知，图中每个顶点都被访问且仅被访问一次，而且从一个顶点到另一个顶点时必须经过这两个顶点所连接的边。这样，当深度优先搜索遍历将连通图中的全部顶点都访问过一次后，共通过了其中n-1条边，而这n-1条边刚好使得全部n个顶点连通，即这n-1条边和n个顶点一起构成了原图的一个连通子图。而具有n个顶点n-1条边的连通图为树，得证。 五、算法设计题

[例11-40] 编写一个算法，将一个无向图的邻接矩阵转换成邻接链表。

解析：先设置一个空邻接链表，然后在邻接矩阵上查找值非零元素。找到非零元素后创建表结点，并在邻接链表对应的单链表中插入该结点。具体算法如下： void mattolist (graph * g，vexnode ga[]，int n) //n为顶点数 {

36

inti，j；

edgenode * p；

for(i=0；i

for (i＝0；i

If (g—>arcs[i][j]＝0) {

p＝(edgenode * )malloc(sizeof (edgenode))； //创建一个结点 p—>adjvex=j

p—>next=ga[i].link； //链人链表 ga[i].1inkt = p；

p=(edgenode * )malloc ( sizeof ( edgenode))； //创建另一个结点 p—>adjvex=i；

p—>next=ga[j].link； //创建一个结点 ga[j].1ink t=p； } } }

[例11-41] 设计一个算法，求无向图的连通分量个数。

解析：由深度优先搜索遍历算法和广度优先搜索遍历算法可知，调用一次深度优先搜 索递归算法或广度优先搜索递归算法只能遍历图中1个连通分量。因此，只需要记录递归 函数被调用的次数，该次数就是图中连通分量的个数。具体算法如下： iht visited[n]； int count(graph * g) {

int i，m=0；

for( i=0；i

for( i＝0；i

dfs(g，i)；

n++； //每调用一次，计数器加1 }

return n； }

[例11—42] 假设图用邻接矩阵表示，设计一个算法，输出含指定顶点vi的所有简单回路。

解析：用数组p保存走过的路径。定义递归算法path (g，i，k)，其功能是确定路径上第k+1个顶点的序号。调用这个算法之前，先将i存入p[0]中。假设p[k]的值为t，检查邻接矩阵的第t行：如果vs是vt相邻的未被访问点，则将vs标记为已被访问，将s存入p[k+1]中，并递归调用path (g，i，k+1)函数。为了实现回溯，在执行path (g，i，k+1)调用后，要

37

重新将vs标记为未被访问。若Vp[k]到Vi存在一条边，则表示找到了一条路径，输出p数组。具体算法如下： intvisited[n]； int p[n]；

void path(graph * g，int i，int k) {

int s；

if(g—>arcs[p[k]][i]＝＝1) //找到一条路径并输出 {

for(s=o；s<＝k；s++)

printf(”％d \\n”，p[s])； } else {

s=0； while (s

if(g—>arcs[p[k]][s]＝＝1&& visited[s]＝＝0) {

visited[s]＝1； p[k+1]＝s；

path(g，i，k+1)； visited[s]＝0； }

s++； } } }

void disppath(graph * g，int i) {

int k； p[0]＝i；

for(k=0；k

(例11—43) 给定n个村庄之间的交通图，若村庄i和村庄j之间有道路，则将顶点i和顶点j用边连接，边上的权叶表示这条道路的长度。现要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路径最近?试设计一个算法解决此问题，并应用该算法解答图11.23所示实例。

38

解析：算法基本思想如下： (1)建立图的邻接矩阵。

(2)用Floyd算法计算每一对顶点间的最短路径。

(3)找出从每一个顶点出发到其余各顶点的最短路径中的最长路径。 (4)在这n条最长路径中找出最短的一条，则它的出发点即为所求。 具体算法如下：

inthospital(intn，int C[][]，int A[][]) //C为邻接矩阵，A是路径长度矩阵 {

inti，j，k，m，s； for(i＝0；i

for(k＝0；k

if(A[i][k])+A[k][i]

for(i＝1；i

s=0；

for(j＝0；js) s=A[i][j]；

if(s

m=s； k＝i； } }

return k； //返回所求村庄序号 }

实例分析：最初的邻接矩阵为

39

经过Floyd算法处理之后，求出每一对顶点之间的最短路径，原邻接矩阵变换为

由矩阵可见，每列中的最大值依次为：9，9，6，7，9，9，其中的最小值为6。因此医 应该选村庄v3，使得离医院最远的村庄到医院的路径最短。

40

12.3 典型例题

一、单项选择题

[例12-1] 内部排序方法的稳定性是指( )。 A．排序算法不允许有相同的关键字记录 B．排序算法允许有相同的关键字记录 C．平均时间为O(nlbn)的排序方法 D．以上都不对

解析：若在待排的一组序列中，h和曳的关键字相同，即ki＝kj，且在排序前ki领先于kj，那么当排序后，如果ki和kj的相对次序保持不变，即ki仍领先于垮，则称此排序方法为稳定的，否则称此方法为不稳定的。本题答案为：D。

[例12-2] 排序方法中，从未排序序列中依次取出元素与已排序列(初始时取第一个 元素)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为( )。 A．希尔排序 B．冒泡排序 C。插入排序 D．选择排序

解析：插人排序的基本思想是：每一趟将一个待排记录按其关键字的大小插入到前面 已经排好序的子序列中的适当位置上，直到全部记录插完为止。本题答案为：C。 (例12-3) 在待排元素序列基本有序的前提下，效率最高的排序方法是( )。 A．插入排序 B．选择排序 C．快速排序 D．归并排序

解析：插入排序时将待排序列的记录插入到前面已排好序的子序列中，即考虑已排好 序的子序列。在待排元素序列基本有序的前提下，插入排序需要的比较和记录移动次数都 比较少。本题答案为：A。

[例12-4] 对记录关键字为{50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为：

50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是( )。

A．选择排序 B．快速排序 C．希尔排序 D．归并排序

解析：由排序结果可知，该排序是增量序列为5、3、1的希尔排序。本题答案为：C。 [例12-5] 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为 ( )。

A．O(1) B．O(1bn) C．O(n2) D．O(n) 解析：由表12.1可知，本题答案为：D。

[例12-6] 一组记录的关键字为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为基准得到的第一次划分结果为( )。

A．38，40，46，56，79，84 B．40，38，46，79，56，84 C．40，38，46，56，79，84 D．40，38，46，84，56，79 解析：第一次划分的过程如下(r[0]．key＝46，i＝0，j＝6)： 1 2 3 4 5 6

46，79，56，38，40，84 //i=1，j=5，r[i]=r[j]，i++，i=2 40，79，56，38，40，84 //i=2，j=5，r[j]=r[i]，j - -，j=4 40，79，56，38，79，84 //i=2，j=4，r[i]=r[j]，i++，j=3 40，38，56，38，79，84 //i=3，j=4，r[j]=r[i]，j - -，j=3 40，38，56，56，79，84 //i=3，j=3，循环结束，r[i]=r[0]

41

40，38，46，56，79，84 本题答案为：C。

[例12-7] 用某种排序方法对线性表(25，84，2l，47，15，27，68，35，20)进行排序时，若元素序列的变化情况如下：

25，84，2l，47，15，27，68，35，20 20，15，21，25，47，27，68，35，84 15，20，2l，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则采用的排序方法是( )。

A．选择排序 B．希尔排序 C．归并排序 D．快速排序

解析：从序列中看到，每次将一个子序列以第一个元素为基准分为两段，显然这是快速排序方法。本题答案为：D。 ：

[例12-8] 在所有排序方法中，关键字的比较次数与记录的初始排列次序无关的是( )。

A．希尔排序 B．冒泡排序 巴插入排序 D．选择排序 解析：由于选择排序每趟从待排记录中选出关键字最小的记录，每个记录都需要进行比较，不考虑已排好序的子序列，因此，关键字比较的次数与记录的初始排列次序无关。 本题答案为：D。

[例12-9] 一组记录的关键字为{46，79，56，38，40，84}，则利用堆排序(建立大根堆)的方法建立的初始堆为( )。

A．79，46，56，38，40，84 B．84，79，56，38，40，46 C．84，79，56，46，40，38 D．84，56，79，40，46，38 解析：根据初始堆的建立调整方法可知，本题答案为：B。

(例12-10) 设有1000个无序元素序列，希望用最快的速度挑选出其中前10个最大的元素，最好用( )法。

A．冒泡排序 B．快速排序 C．堆排序 D．基数排序

解析：由于堆排序一趟排好一个记录，当只挑选出其中前10个最大的记录时，使用堆 排序最好。本题答案为：C。

(例12-11) 下述几种排序方法中，要求内存量最大的是( )。 A．插入排序 B．选择排序 C．快速排序 D．归并排序 解析：由表12.1可知，本题答案为：D。

(例12-12) 下列排序算法中，其中( )是稳定的。 A．堆排序和冒泡排序 B．快速排序和堆排序 C．直接选择排序和归并排序 D．归并排序和冒泡排序 解析：由表12．1可知，本题答案为：D。 二、判断题

(例12-13) 若采用顺序存储结构进行排序操作，在待排序的元素很大时，为了交换元素的位置而移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

解析：正确。在采用顺序存储结构进行排序操作时，时间复杂度主要反映在关键字的比较和对记录的移动上；在待排序的元素很大时，移动记录需要的时间是比较多的，从而移动元素就成了影响时间复杂度的主要因素。

(例12-14) 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 解析：错误。若在待排的一组序列中，ki和kj的关键字相同，即ki=kj，且在排序前ki 领先于kj，那么当排序后，如果ki和kj的相对次序保持不变，即ki仍领先于kj，则称此排

42

序方法为稳定的，否则称此方法为不稳定的。

(例12-15) 在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlbn)。

解析：错误。在初始数据已经有序时，快速排序算法蜕变为冒泡排序，其时间复杂度为O(n2)。

(例12-16) 在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。 解析：正确。在用堆排序算法排序时，第一次是将初始堆的第一个记录与最后一个记录交换，如果是大根堆就将最大的记录换到最后，依此类推，待排序完成后序列即可成为一个增序序列。

(例12-17) 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法，冒泡排序算法的最坏时间复杂度为O(n2)，而快速排序算法的最坏时间复杂度为O(nlbn)，所以快速排序比冒泡排序的算法效率更高。

解析：错误。由表12.1可知，在待排序列已经有序的情况下，快速排序算法的最坏时间复杂度为O(n2)，与冒泡排序是一样的。

[例12—18] 归并排序在任何情况下都比所有简单排序的速度快。

解析：错误。由表12.1可知，简单排序(如冒泡排序和直接插入排序)在最好情况下的时间复杂度为O(n)，而归并排序的时间复杂度为O(nlbn)，所以说命题说法是错误的。

[例12-19] 快速排序的速度在所有排序方法中是最快的，而且所需附加空间也最少。 解析：错误。由表12.1可知，快速排序的速度并不是在所有情况下都是最快的，它只是平均性能最好的一种排序方法。而直接插入排序、希尔排序、堆排序、直接选择排序、冒泡排序等方法所需附加空间都是一个，比快速排序所需要的辅助空间要少。 三、填空题

[例12—20] 若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 和记录的 。

解析：在内排序过程中，主要进行的两种基本操作是关键字的比较和记录的移动。本题答案为：比较；移动。

(例12—21) 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，最省时间的是 算法，最费时间的是 算法。

解析：由表12.1可知，对初态有序的表进行排序，堆排序的时间复杂度为O(nlbn)；快速排序为最坏情况，时间复杂度为O(n2)；冒泡排序为最好情况，时间复杂度为O(n)；归并排序时间复杂度为O(nlbn)。本题答案为：冒泡排序；快速排序。

(例12—22) 快速排序法在 情况下最不利于发挥其长处，在 情况下最易发挥其长处。 解析：快速排序在待排记录有序的情况下蜕变为冒泡排序是最坏情况，在待排记录基本无序而且记录数较多的情况下最易发挥其长处。本题答案为：待排记录有序；待排记录基本无序且记录数较多。

[例12—23] 每次通过直接或间接比较两个元素，若出现逆序排列时就交换它们的位置，此种方法叫做 排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做 排序。

解析：由快速排序和归并排序的定义可知，本题答案为：快速；归并。

[例12—24] 在归并排序和快速排序中，若原始记录接近正序或反序，则选用 ，若原始记录无序，则最好选用 。

解析：当原始记录接近正序或反序时，使用快速排序效率最低。本题答案为：归并排 序；快速排序。

[例12—25] 对n个记录的序列进行冒泡排序时，最少的比较次数是 。

43

解析：当初始序列正序时，第一趟比较n-1次，没有交换产生，退出算法。本题答案为：n-1。

(例12—26) 在堆排序、快速排序和归并排序中，若只从存储空间方面考虑，则应首先取 方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定性方面考虑，则应选取 方法；若要在平均情况下排序最快，则应选取 方法；若要在最坏情况下排序最快并且要节省内存，则应选取 方法。

解析：由表12.2可知，本题答案为：堆排序；快速排序；归并排序；归并排序；快速排序；堆排序。

[例12—27] 排序不需要进行关键字的比较。

解析：基数排序不需要进行关键字的比较。本题答案为：基数。 四、应用题

(例12—28) 我们知道，对于由n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：

(1)当n= 7时，在最好情况下需进行多少次比较?请说明理由。 (2)当n＝7时，给出一个最好情况的初始排序的实例。

(3)当n＝7时，在最坏情况下需进行多少次比较?请说明理由。 (4)当n＝7时，给出一个最坏情况的初始排序的实例。

解析：(1)在最好情况下，假设每次划分能得到2个长度相等的子序列，子序列的长度为n=2k-1，那么，第一遍划分得到2个长度为[n/2]的子序列，第二遍划分得到4个长度为[n/4]的子序列；依此类推，总共进行k=lb(n+1)遍划分，各子序列长度为l，排序完毕。当n＝7时，k＝3，在最好情况下，第一遍比较6次可将序列分为2个长度都为3的子序列，第二遍分别对2个子序列进行排序，各比较2次。这样就可以将原序列排序完毕。所以最好情况下总共比较10次即可。

(2)最好的初始序列就是每次排序时都可将原序列分成2个长度一样的子序列的初始序列，即可使每个基准刚好都是该待排序列中大小位置居中的记录。当n＝7时，最好的初始排序情况的例子为4，7，5，6，3，1，2。

(3)在最坏情况下，若每次用来划分的记录的关键字具有最大值(或最小值)，那么只能得到左(或右)子序列，其长度比原长度少1。因此，若原序列中的记录按关键字递减次序排列。而要求按递增次序排序时，快速排序的效率与冒泡排序相同，其时间复杂度为O(n2)。所以当n＝7时，最坏情况下的比较次数为21次。

(4)当n＝7时，最坏情况下的初始排序的例子为7，6，5，4，3，2，1。 （例l2—29) 在执行某排序算法过程中，出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法正确吗?为什么? 解析：这种说法是不正确的。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次序经过排序后发生了变化，而题中未涉及到元素的相对次序改变，只有移动元素，所以此说法不正确。

[例12—30] 设记录的关键字集合key＝{49，38，66，90，75，10，20}。 (1)写出快速排序的第一趟和第二趟之后的结果。 (2)把关键字集合key调整成小根堆。

(3)在内部排序算法中，哪个排序要求的内存容量最多?

解析：(1)快速排序第一趟排序后的结果：{20，38，10，49，75，90，66}。 快速排序第二趟排序后结果：{10，20，38，49，75，90，66}。 (2)调整后的小根堆为：{10，38，20，90，75，66，49}。 (3)归并排序要求内存容量最多。

44

[例12—31] 设有6000个无序元素，希望用最快的速度挑选出其中最大的前10个元素。在以下的排序方法中，采用哪种方法最好?为什么?

快速排序 堆排序 归并排序 基数排序 希尔排序

解析：上面所列的几种排序方法都是速度比较快的排序方法，但快速排序、归并排序、 基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，在排序过程中无法知道部分元素的有序性。而堆排序则每次输出一个最大(或最小)的元素，然后对堆排序进行调整，保证堆顶的元素总是最大(或最小)。根据题意，只要求挑选出无序元素中最大的前10个元素，故采用堆排序方法是合适的。

(例12—32) 已知序列{25，18，60，40，7，21，32，73，68}，请给出分别采用冒泡排序方法、直接选择排序方法和快速排序方法对该序列做升序排列时的每一趟结果。 解析：(1)采用冒泡排序方法排序的各趟结果如下：(加框为每次冒出元素) 初始序列：25， 18， 60， 40， 7， 21， 32， 73， 68

7， 25， 18， 60， 40， 21， 32， 68， 73 第——趟：□

8， 25， 21， 60， 40， 32， 68， 73 第二趟： 7， 1□

21， 25， 32， 60， 40， 68， 73 第三趟： 7， 18， □

5， 32， 40， 60， 68， 73 第四趟： 7， 18， 21， 2□

第五趟： 7， 18， 21， 25， 32， 40， 60， 68， 73 第五趟无元素交换，排序结束。

(2)采用直接选择排序方法排序的各趟结果如下：(加框为每次选出元素)

7， 21， 32， 73， 68 初始序列：25， 18， 60， 40， □

18， 60， 40， 25， 2l， 32， 73， 68 第——趟：[7] □

21， 32， 73， 68 第二趟： [7， 18] 60， 40， 25， □

5， 60， 32， 73， 68 第三趟： [7， 18， 21] 40， 2□

2， 73， 68 第四趟： [7， 18， 21， 25] 40， 60， 3□

0， 73， 68 第五趟： [7， 18， 21， 25， 32] 60， 4□

0， 73， 68 第六趟： [7， 18， 21， 25， 32， 40] 6□

8 第七趟： [7， 18， 21， 25， 32， 40， 60] 73， 6□

第八趟： [7， 18， 21， 25， 32， 40， 60， 68] 73 结束： 7， 18， 21， 25， 32， 40， 60， 68， 73 (3)采用快速排序方法排序的各趟结果如下：

初始序列：25， 18， 60， 40， 7， 21， 32， 73， 68

第一趟： [21 18 7] 25 [40 60 32 73 68] 第二趟： [7 18] 21 25 [32] 40 [60 73 68] 第三趟： 7 [18] 21 25 32 40 60 [73 68] 第四趟： 7 18 21 25 32 40 60 [68] 73 结束： 7 18 21 25 32 40 60 68 73

(例12—33) 在冒泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序方向 相反的方向移动，试举例说明。快速排序过程中有没有这种现象?

解析：在冒泡排序过程中，有的关键宇在某趟排序中可能朝着与最终排序方向相反的 方向移动，如下面排序过程中关键字27的位置变化。

27 13 97 初始关键字：49 38 □

7 97 第一趟结果：13 49 38 2□

27 49 38 97 第二趟结果：13 □

27 38 49 97 第三趟结果：13 □

45

但在快速排序中不会出现这种情况，因为在每趟快速排序中，比基准元素大的元素都 交换到右边，而比基准元素小的元素都交换到左边。 五、算法设计题

[例12—34] 仔细阅读下面程序，并回答有关问题。 void test (int a[0.. 499], int n)

{

int i, j, x, flag；

flag= 1； i=1；

while(i

flag = 0；

for(j=l； j< ；j++) if( ) { x= a[j]；

a[j]=a[j+l]； a[j+1] = x； ； } i++； } }

(1)在“ ”中填上正确的语句，使该过程能完成预期的排序功能。 (2)该过程使用的是什么排序方法? （3）当数组a的元素初始时已按值递增排列，在该过程执行中会进行多少次比较？多少次交换?

(4)当数组a的元素初始时已按值递减排列，在该过程执行中会进行多少次比较?多少次交换?

解析：(1) 499；a[j]>a[j+1]；flag＝1 (2)本过程采用的是冒泡排序。 (3)进行499次比较，0次交换。

(4)在此种情况下，比较次数和交换次数都是最多的。其比较次数为

n(n?1)500?(500?1)?=124 570 22因为每比较一次关键字都需要交换一次记录，所以交换次数为

n(n?1)500?(500?1)?=124 750 22 [例]2—35] 已知奇偶转换排序如下所述：第一趟对所有奇数的i，将a[i]和a[i+1]

进行比较，第二趟对所有偶数的i，将a[i]与a[i+1]进行比较，每次比较时若a[i]> a[i+1]，则将二者交换，以后重复上述两趟过程，直至整个数组有序。 (1)试问排序结束的条件是什么?

(2)编写一个实现上述排序过程的算法。 解析：(1)排序结束的条件是没有元素交换。

46

(2)实现奇偶转换排序的算法如下：

void oesort(int a[]，int n) //排[序元素a[0]~a[n-1] {

int i，flag； int temp； do {

flag=0；

for(i=0；i

if(a[i]>a[i+1] //交换 {

flag=1；

temp=a[i+1]； a[i+1]＝a[i]； a[i]＝temp；

} i++； }

for(i=1；i

if(a[i]>a[i+1]) //交换 {

flag＝1； temp=a[i+1]； a[i+1]＝a[i]； a[i]=temp； }

i++； }

}while(flag==1)； }

[例12—36] 编写一个算法，用非递归方式实现快速排序。

解析：依题意，使用一个栈stack，它是一个二维数组，其中，stack[i][0]存储子表第一个元素的下标，stack[i][1]存储子表最后一个元素的下标。

首先将(1，n)人栈，然后进行如下循环直到栈空：退栈得到t1和t2，调用数据分割函数partition( )，该函数自动调整好t1～t2子表的第一个元素(基准)位置并将原表分解成两个子表t1~i—1和i+1～t2(i为基准最终位置)，若这些子表内元素个数大于1，则入栈。实现快速排序的非递归算法如下：

void quicksort(rectype r[]，int tl，int t2) //排序元素r[0]~r[n-1] {

int stack[m][2], i，top= -1； //m为栈的最大深度 top++；

stack [top] [0]＝t1；

47

stack [top] [1]=t2；

while (top>—1) //栈非空时循环 {

tl =stack[top][0]； t2=stack[top][1]； top--；

i=partition(r，t1，t2)；

if(tl

top++；

stack[top][0]＝t1； stack[top][1]＝i—1； }

if(i+1

top++；

stack[top][0]＝i+1； stack[top][1]=t2； } } }

int partition(rectype r[]，int l，int h) {

inti＝1，j＝h；

rectype x //基准 x＝r[i] do

{//从右向左扫描，查找第一个关键字小于x.key的记录 while(x.key<＝r[j]．key && j>i) j--；

if(j>i) //找到则交换 {

r[i]＝r[j]； i++； }

//从左向右扫描，查找第一个关键字大于x．key的记录 while(x．key)＝r[i]．key && i

if(j>i) //找到则交换 {

r[j]=r[i]； j--； }

} while (i!＝j)；

48

r[i]＝x；

return i; //返回基准位置 }

49

13.3 典型例题

一、单项选择题

(例13—1) 顺序查找法适用于查找存储结构为( )的线性表。 A．散列存储 B．顺序存储或链式存储 C．索引存储 D．压缩存储

解析：顺序查找适用于线性表，不论采用顺序存储还是链式存储都可以。本题答案为：B。

[例13—2] 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n

解析：由13.2.2节内容可知顺序查找法的平均查找长度为(n+1)/2。本题答案为：C： [例13-3] 适用于折半查找的表的存储方式及元素排列要求为( )。 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

解析：折半查找要求查找表以顺序方式存储而且表内元素按关键字有序。本题答案为：D。

[例13-4] 具有12个关键字的有序表，折半查找的平均查找长度为( )。 A．35/12 B．37/12 C．39/12 D．43/12

解析：构造相应的12个结点的判定树，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则ASL＝(1×l+2×2+3×4+4×5)/12＝37/12。本题答案为：B。 [例13-5] 当采用分块查找时，数据的组织方式为( )。 A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的

数据组成索引块

C．数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块 D．数据分成若干块，每块(除最后一块外)中数据个数需相同 解析：本题答案为：B。

[例13-6] 若对有序表A[1..18]做折半查找，则查找A[3]的比较序列的下标为( )。 A．1，2，3 B．9，5，2，3 C．9，5，3 D．9，4，2，3

解析：第一次比较元素的下标为[(1+18)/2]＝9，第二次[(1+8)/2]＝4，第三次 [(1+3)/2]＝2，第四次[(3+3)/2]＝3。本题答案为：D。

[例13-7] 如图13.8所示二叉排序树的查找不成功的平均查找长度是( )。 A．21/7 B．28/7 C．15/6 D．21/6

解析：如图13.9所示，方框结点为查找不成功的外部结点。查找失败时，其比较过程是经历了一条二叉排序树根结点到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。其平均查找长度为(2×2+3×3+4×2)/7＝21/7。本题答案为：A。

50

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