算法与数据结构C语言版课后习题答案第9.10章

第9章 集合

一、基础知识题

9.1 若对长度均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？

（1）查找不成功，即表中没有和关键字K相等的记录； （2）查找成功，且表中只有一个和关键字K相等的记录；

（3）查找成功，且表中有多个和关键字K相等的记录，要求计算有多少个和关键字K相等的记录。 【解答】

（1）平均查找长度不相同。前者在n+1个位置均可能失败，后者失败时的查找长度都是n+1。 （2）平均查找长度相同。在n个位置上均可能成功。 （3）平均查找长度不相同。前者在某个位置上(1<=i<=n)查找成功时，和关键字K相等的记录是连续的，而后者要查找完顺序表的全部记录。

9.2 在查找和排序算法中，监视哨的作用是什么？

【解答】监视哨的作用是免去查找过程中每次都要检测整个表是否查找完毕，提高了查找效率。

9.3 用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？若每块长度为25 ，平均查找长度是多少？

【解答】分成45块，每块的理想长度为45(最后一块长20)。若每块长25，则平均查找长度为ASL=(80+1)/2+(25+1)/2=53.5(顺序查找确定块)，或ASL=19(折半查找确定块)。

9.4 用不同的输入顺序输入n个关键字，可能构造出的二叉排序树具有多少种不同形态? 【解答】 1n n?12n9.5 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，中序前驱结点没有右孩子。

【证明】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左孩子；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结点，没有右孩子。命题得证。

9.6 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树， 其最大高度是多少? 最小高度是多少?

【解答】设以Nh表示深度为h的AVL树中含有的最少结点数。显然，N0=0，N1 =1，N2 =2，且Nh = Nh-1 + Nh-2 +1(h≥2)。这个关系与斐波那契序列类似，用归纳法可以证明：当h≥0时，Nh = Fh+2 -1，而Fh约等于

CФ/5。其中Ф=(1+5)/2，则Nh约等于Ф

hh+2

/(5-1) (即深度为h的AVL树具有的最少结点数)。

(

有n个结点的平衡二叉树的最大高度是logФ5(n+1))-2，最小高度是?log2n?。

9.7 试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 【解答】根据9.6的结论可知，深度为n的AVL树中的最少结点数为Nn?Fn?2?1

所以12=Fn?2?1，有Fn?2=13，求得n+2=7(Fibonacci数列第一项的值假设为1，对应于二叉树表

示有一个结点的二叉树的深度为1)，所以n=5。

可表示为如下图所示的AVL树：

9.8 假定有n个关键字，它们具有相同的哈希函数值，用线性探测方法把这n个关键字存入到哈希表中要做多少次探测？

【解答】n个关键字都是同义词，因此用线性探测法第一个关键字存入时不会发生冲突，所以探测的次数应为1?2???n?n(n?1)2次。

9.9 建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。 【解答】 7 查找成功时的平均查找长度为：

3 1

2 5 4 8 6 9 10 12 ASLsucc?(1?1?2?2?3?4?4?6)/13?41/13

查找不成功时的平均查找长度为：

ASLun?(2?3?12?4)/14?54/14?27/7

11 13 9.10 二叉排序树中关键字互不相同，则其中关键字最小值结点无左孩子，关键字最大值结点无右孩子，此命题是否正确？最小值结点和最大值结点一定是叶子吗？一个新结点总是插在二叉排序树的某叶子上吗？ 【解答】

（1）此命题正确。

（2）最小值结点和最大值结点不一定是叶子结点。

（3）一个新结点不一定总是插在二叉排序树的某叶子上。 9.11 回答问题并填空：

（1）散列表存储的基本思想是什么？

（2）散列表存储中解决碰撞的基本方法有哪些？其基本思想是什么？ （3）用线性探查法解决碰撞时，如何处理被删除的结点？为什么？ 【解答】

（1）散列表存储的基本思想是用关键字的值决定数据元素的存储地址 （2）散列表存储中解决碰撞的基本方法：

① 开放定址法 形成地址序列的公式是：Hi=(H(key)+di)% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．di =12，-12，22，-22，? ，?k2(k≤m/2) 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3(j为整数)的素数时才有可能。 c．di =伪随机数序列，称为随机探测再散列。

② 再散列法 Hi=RHi(key) i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。

③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i(0≤i≤m-1)的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。

④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区O[0..m-1]。 （3）要在被删除结点的散列地址处作标记，不能物理的删除。否则，中断了查找通路。

9.12 如何衡量哈希函数的优劣？简要叙述哈希表技术中的冲突概念，并指出三种解决冲突的方法。 【解答】评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法见上面9.11题。

9.13 设有一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key % 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) % 10(di=12，22，32，?，)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 【解答】

散列地址 关键字 比较次数 0 14 1 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 3 4 平均查找长度：ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8

以关键字27为例：H(27)=27%7=6(冲突) H1=(6+1)=7(冲突) H2=(6+22)=0(冲突) H3=(6+33)=5 所以比较了4次。

9.14 对下面的关键字集合{30，15，21，40，25，26，36，37}，若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突。要求：

（1）设计哈希函数； （2）画出哈希表；

（3）计算查找成功和查找失败的平均查找长度。

【解答】由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。

（1）用除留余数法，哈希函数为H(key)=key % 7 （2）

散列地址 关键字 比较次数 0 21 1 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 （3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i(0≤i≤m-1)时的查找次数。本例中m=10。故查找失败和查找成功时的平均查找长度分别为：

ASLunsucc=(9+8+7+6+5+4+3+2+1+1)/10=4.6 ASLsucc =16/8=2

9.15 设哈希函数H（k）=3k % 11，散列地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12）按下述两种解决冲突的方法构造哈希表：

（1）线性探测再散列

（2）链地址法，并分别求出等概率下查找成功时和查找失败时的平均查找长度。

【解答】（1）

散列地址 关键字 比较次数 0 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 查找成功时的平均查找长度为 ASLsucc?(1?1?1?2?1?2?1?2)/8?11/8

查找不成功时的平均查找长度为 ASLun?(1?2??1?8?7?6?5?4?3?2?1)/11 4（2）

0 1 2 3 4 5 6 7 8 9 10 ∧ ∧ ∧ 32 21∧ ∧ 13 24∧ ∧ 4 ∧ ∧ 12 49 ∧ 38 ∧ 查找成功时的平均查找长度为 ASLsucc?(1*5?2*3)/8?11/8

查找不成功时的平均查找长度为 ASLun?(1?2??1?2?3?1?3?1??31?1)/11 19.16 已知长度为l2的表{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}

（1）试按表中元素的次序依次插入一棵初始为空的二叉排序树，并求在等概率情况下查找成功的平均查找长度。

（2）用表中元素构造一棵最佳二叉排序树，求在等概率的情况下查找成功的平均查找长度。 （3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 【解答】 （1） Jan

Feb Mar Apr June May

Aug July Sep

Dec Oct

Nov ASLsuss =(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12=3.5

（2）最佳二叉排序树的形状和12个结点的折半查找判定树相同，见题目9.17。 ASLsuss =(1*1+2*2+4*3+5*4)/12=37/12 （3） Mar

Jan Oct Aug June May Sep

Feb July Apr Nov

Dec

ASLsuss =(1*1+2*2+3*4+4*4+5*1)/12=38/12

9.17 假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题：(1) 画出描述折半查找过程的判定树；(2) 若查找元素54，需依次与哪些元素比较?(3) 若查找元素90，需依次与哪些元素比较?(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 【解答】

（1） 判定树：（注：结点内的数字为数据元素，旁边的数字是该元素在有序表中的位置） 6 30

3 9

63 5

1 4 7 11

7 42 87 3 24 54 95 4 72

10 12 2 5 8

（2）若查找元素54，需依次与元素30、63、42、54比较，查找成功。 （3）若查找元素90，需依次与元素30、63、87、95比较，查找失败。

（4）等概率下，查找成功时的平均查找长度：ASL=(1*1+2*2+4*3+5*4) /12=37/12

9.18 直接在二叉排序树中查找关键字K与在中序遍历输出的有序序列中查找关键字K，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？

【解答】在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O(n)。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是(n+1)/2，时间复杂度也是O(n)。

9.19 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。

（1）51，250，501，390，320，340，382，363

（2）24，877，125，342，501，623，421，363

【解答】序列(2)不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面应出现小于501的数，但序列中出现了623，故不可能。

9.20 用关键字1，2，3，4的四个结点（1）能构造出几种不同的二叉排序树？其中（2）最优查找树有几种？（3）AVL树有几种？(4)完全二叉树有几种？试画出这些二叉排序树。 【解答】（1）本题的本质是给定中序序列1、2、3、4，有几种不同的二叉排序树，即该中序序列相当多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二叉数的数目为1/(n+1)C2nn，这里n=4，故有14种。图示如下： （1）

（2）

（3）

（4）

（5） 1 2 3 1 2 4 1 3 2 4 1 4 2 3 1 4 3 2 4 （6） （7） 3 （8） （9） 2 1 3 4 2 1 3 4 3 1 2 4 3 2 4 （10） 4 1 2 3 1 （11） 4 1 3 2 （12） 4 2 （13） 4 3 （14） 4 3 2 2 1

1 3 1 （2）最优查找树有4种，图中（6）（7）（8）（9）。 （3）AVL树也有4种，图中（6）（7）（8）（9）。 （4）完全二叉树有1种，图中（9）。 9.21 简要叙述B-树与B+树的区别? 【解答】m阶的B+树和B-树主要区别有三：

（1）有n棵子树的结点中含有n(B-树中n-1)个关键字；

（2）B+树叶子结点包含了全部关键字信息，及指向含关键字记录的指针，且叶子结点本身依关键字大小自小到大顺序链接；

（3）B+树的非终端结点可以看成是索引部分，结点中只含其子树(根结点)中最大(或最小)关键字。B+树的查找既可以顺序查找，也可以随机查找，B-只能随机查找。

9.22 包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程。）

【解答】本题等价于“含有n个关键字的m阶B-树的最大高度是多少”？一次检索中最多走一条从根到叶子的路径，由于根结点至少有两棵子树，其余每个(除叶子)结点至少有?m/2?棵子树，则第三层至少有?m/2?*2个结点，第l+1层至少有2*?m/2?l-1个结点。设B-树深度为l+1，即第l+1层是叶子结点，叶子结点数是n+1(下面推导)，故有n+1≥2*?m/2?l-1，即l≤log?m/2?( )+1。

注：推导B-树中叶子结点数s与关键字数n的关系式：s=n+1

设B-树某结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树，有 ∑Ni=∑(Ci-1)=∑Ci-k(1≤i≤k) ??(1)

因为B树上的关键字数，即∑Ni=n (1≤i≤k) ??(2)

而B-树上的子树数可这样计算：每个结点(除根结点)都是一棵子树，设叶子(子树)数为s；则 ∑Ci=(k-1)+s (1≤i≤k) ??(3)

综合(1)(2)(3)式，有s=n+1。证毕。

9.23 设有一棵空的3阶B-树，依次插入关键字30，20，10，40，80，58，47，50，29，22，56，98，99，请画出该树。 【解答】

40 58 20 29 50 98 10 22 30 47 56 80 99

9.24 含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？

【解答】含9个叶子结点的3阶B-树至少有4个非叶子结点，当每个非叶子结点均含3棵子树，第三层是叶子结点时就是这种情况。当4层3阶B-树有10个叶子结点时，非叶子结点达到最大值8个：其中第一层1个，第二层2个，第三层5个。

9.25 选择题：对顺序表进行二分查找时，要求顺序表必须：

A. 以顺序方式存储 B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储 D. 以链接方式存储，且数据元素有序 【解答】B

9.26 选择题：下列二叉排序树中查找效率最高的是： A. 平衡二叉树 B. 二叉查找树

C. 没有左子树的二叉排序树 D. 没有右子树的二叉排序树 【解答】A

二、算法设计题

9.27 元素集合已存入整型数组A[1..n]中，试写出依次取A中各值A[i](1<=i<=n)构造一棵二叉排序树T的非递归算法。

【题目分析】本题以非递归形式建立二叉排序树

void CSBT(BSTree T，ElemType A[]，int n)

{ ∥以存储在数组K中的n个关键字，建立一棵初始为空的二叉排序树

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

{

p=T; f=null; ∥在调用Creat_BST时，T=null

while(p!=null)

if(p->data

{ f=p; p=p->rchild; } ∥ f是p的双亲

else if(p->data>A[i]){ f=p;p=p->lchild; } s=(BSTree)malloc(sizeof (BiNode)); ∥ 申请结点空间 s->data=A[i]; s->lchild=null; s->rchild=null; if(f==null) T=s; ∥根结点 else if(s->datadata) f->lchild=s; ∥左子女 else f->rchild=s; ∥右子树根结点的值大于等于根结点的值

}

}∥算法结束

9.28 编写删除二叉排序树中值是X的结点的算法。要求删除结点后仍然是二叉排序树，并且高度没有增长。

【题目分析】在二叉排序树上删除结点，首先要查找该结点。查找成功后，若该结点无左子树，则可直接将其右子树的根结点接到其双亲结点上；若该结点有左子树，则将其左子树中按中序遍历的最后一个结点代替该结点，从而不增加树的高度。

void Delete(BSTree bst, keytype X) ∥在二叉排序树bst上，删除其关键字为X的结点 { BSTree f,p=bst;

while(p && p->key!=X) ∥查找值为X的结点 if(p->key>X) { f=p; p=p->lchild; } else { f=p; p=p->rchild; }

if(p==null) { printf(“无关键字为X的结点\\n”); exit(0); } if (p->lchild==null) ∥被删结点无左子树

if(f->lchild==p) f->lchild=p->rchild; ∥将被删结点的右子树接到其双亲上 else f->rchild=p->rchild; else { q=p; s=p->lchild; ∥被删结点有左子树

while(s->rchild !=null) ∥查左子树中最右下的结点(中序最后结点) { q=s; s=s->rchild; }

p->key=s->key; ∥结点值用其左子树最右下的结点的值代替 if(q==p)

p->lchild=s->lchild; ∥被删结点左子树的根结点无右子女

else q->rchild=s->lchild; ∥s是被删结点左子树中序序列最后一个结点 free(s); }∥else }∥算法结束

9.29 假设二叉排序树的各个元素值均不相同，设计一个递归算法按递减次序打印各元素的值。 【题目分析】按着“右子树－根结点－左子树”遍历二叉排序树，并输出结点的值。 void InOrder(BSTree bt) ∥按递减次序输出二叉排序树结点的值

{

BiTree s[],p=bt; ∥s是元素为二叉树结点指针的栈，容量足够大 int top=0;

while(p || top>0) { while(p) { s[++top]=p; bt=p->rchild; } ∥沿右子树向下 if(top>0) { p=s[top--]; printf(p->data); p=p->lchild; } } }∥结束

以下是递归输出，算法思想是一样的。

void InvertOrder(BSTree bt)∥按递减次序输出二叉排序树结点的值 { BiTree p=bt; if(p)

{ InOrder(bt->rchild); ∥中序遍历右子树 printf(p->data); ∥访问根结点 InOrder(bt->lchild); ∥中序遍历左子树 }∥if }∥结束

9.30 设记录R1，R2，?，Rn按关键字值从小到大顺序存储在数组r[1..n]中，在r[n+1]处设立一个监视哨，其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树，求出在等概率情况下查找成功时的平均查找长度。

int Search(rectype r[]，int n，keytype k)

{ ∥在n个关键字从小到大排列的顺序表中，查找关键字为k的结点 r[n+1].key=MAXINT; ∥在高端设置监视哨 i=1; while(r[i].key

查找过程的判定树是单枝树，限于篇幅不再画出。本题中虽然表按关键字有序，但进行顺序查找，查找成功的平均查找长度亦为(n+1)/2。

9.31 在二叉排序树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其递归和非递归算法（要求给出结点的定义）。 typedef struct node

{ ElemType data；int count；struct node *llink，*rlink； }BiTNode，*BSTree；

void Search_InsertX(BSTree t，ElemType X)

{ ∥在二叉排序树t中查找值为X的结点，若查到，则其结点的count域值增1 ∥否则，将其插入到二叉排序树中 p=t;

while(p!=null && p->data!=X) ∥查找值为X的结点，f指向当前结点的双亲 { f=p;

if(p->datarlink; else p=p->llink; }

if(!p) ∥无值为x的结点，插入之

{ p=(BiTNode *)malloc(sizeof (BiTNode));

p->data=X; p->llink=null; p->rlink=null;

if(t==null) t=p; ∥若初始为空树，则插入结点为根结点 else if(f->data>X) f->llink=p; else f->rlink=p; }

else p->count++; ∥ 查询成功，值域为X的结点的count增1 }∥ Search_InsertX

9.32 假设一棵平衡二叉树的每个结点都标明了平衡因子b，试设计一个算法，求平衡二叉树的高度。 【题目分析】 因为二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左、右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-1时)子树向下查找。 int Height(AVLTree t) ∥ 求平衡二叉树t的高度 { level=0; p=t; while(p)

{ level++; ∥ 树的高度增1 if(p->bf<0)p=p->rchild; ∥bf=-1 沿右分枝向下 else p=p->lchild; ∥bf>=0 沿左分枝向下 }∥while

return (level); ∥平衡二叉树的高度 } ∥算法结束

9.33 设二叉排序树的存储结构为：

typedef struct node{ElemType key; int size:int; struct node *lchild， *rchild，*parents;}node，*BiTree; 一个结点*x的size域的值是以该结点为根的子树中结点的总数（包括*x本身）。例如，下图中x所指结点的size值为4。设树高为h，试写一时间为O(h)的算法Rank(BiTree T，node *x)返回x所指结点在二叉排序树T的中序序列里的排序序号，即：求x^结点是根为T的二叉排序树中第几个最小元素。

【题目分析】 因为T是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点*x。若T的左子树为空，则其中序序号为1，否则为T->lchild->size+1。设T的中序序号为r，其左子女p的中序序号和右子女q的中序序号分别为r-p->rchild->size-1和r+q->lchild->size+1。

int Rank(tree T，node *x) ∥ 在二叉排序树T上，求结点x的中序序号 { if(T->lchild) r=T->lchild->size+1; else r=1; ∥根结点的中序序号 while(T)

if(T->key>x->key) ∥到左子树去查找 { T=T->lchild; if(T) { if(T->rchild) r=r-T->rchild->size-1; else r=r-1; } } else if(T->keykey) ∥到右子树去查找 { T=T->rchild; if(T) { if(T->lchild)r=r+T->lchild->size+1; else r=r+1; }

} else return (r); ∥返回*x结点的中序序号 return (0); ∥T树上无x结点 }∥结束算法Rank

算法2：本题的另一种解法是设r是以*x为根的中序序号。初始时，若x的左子树为空，r=1;否则，r=x->lchild->size+1。利用结点的双亲域，上溯至根结点，即可求得*x的中序序号。

int Rank(tree T，node *x) ∥在二叉排序树T上，求结点x的中序序号 { if(x->lchild)r=x->lchild->size+1; else r=1; ∥x的这个序号是暂时的 p=x; ∥p要上溯至根结点T，求出*x的中序序号 while(p!=T)

{ if(p==p->parents->rchild) ∥p是其双亲的右子女，

{ if(p->parents->lchild==null) r++; ∥p结点的双亲排在p结点的前面 else r=r+p->parent->lchild->size+1; ∥双亲及左子树均排在p前面 } p=p->parents; }∥while return (r); }∥Rank

9.34 已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。 (1) 处理冲突的方法为线性探测再散列。编写按第一个字母的顺序输出哈希表中所有关键字的算法。 (2) 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。 【题目分析】 本题未直接给出哈希表表长，但已给出装填因子小于1，且哈希函数H(k)为关键字第一个字母在字母表中的序号，字母‘A’的序号为1，表长可设为n(n≥27)，而链地址法中，表长26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数)。

(1)void Print(rectype h[])∥按关键字第一个字母在字母表中的顺序输出各关键字 { int i,j; for(i=1;i≤26；i++) ∥哈希地址1到26 { j=1；printf(“\\n”); while(h[j]!=null) ∥设哈希表初始值为null

{ if(ord(h[j])==i) ∥ord()取关键字第一字母在字母表中的序号 printf(“%s”，h[j])； j=(j+1)% n； }∥while }∥for }∥end

(2)int ASLHash(rectype h[]) ∥链地址解决冲突的哈希表查找不成功时平均查找长度 { int i,j; count=0; ∥记查找不成功的总的次数 LinkedList p; for(i=1;i<=26；i++) { p=h[i];j=1; ∥按我们约定，查找不成功指到空指针为止 while(p!=null) { j++; p=p->next; } count+=j; } return (count/26.0);

}

9.35 有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。 （1）请设计一个哈希表

（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对算法所需时间和用一维数组(每个分量存放一个非零元素的行值、列值和元素值)作存储结构时存取元素的算法进行比较。

【题目分析】非零元素个数是100，负载因子取0.8，表长125左右，取p为127，散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127，i，j为行值和列值。

#define m 127

typedef struct {int i,j; ElemType v;}triple;

void CreatHT(triple H[m]) ∥生成稀疏矩阵的哈希表，表中元素值初始化为0 { for(k=0；k<100；k++) { scanf(&i,&j,&val); ∥设元素值为整型 h=(3*i+2*j)% m; ∥计算哈希地址

while(HT[h].v!=0)) h=(h+1) % m; ∥线性探测哈希地址 HT[h].i=i; HT[h].j=j; HT[h].v=val; ∥非零元素存入哈希表 }∥for

}∥算法CreatHT结束

ElemType Search(triple HT[m]，int i，int j)

{∥在哈希表中查找下标为i，j的非零元素，查找成功返回非零元素，否则返回零值 int h=(3*i+2*j) % m;

while((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=(h+1)% m; return (HT[h].v); }∥Search

第10章 排序

一、 基础知识题

10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树。

【解答】⑴内排序和外排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 ⑵稳定排序和不稳定排序 假设待排序记录中有关键字Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。

⑶顺串 外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。 ⑷败者树 败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。

⑸最佳归并树 在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼

树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用nk表示度为k的个数，若(m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。

10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)， 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。

(1) 直接插入排序 (2) 希尔排序(增量为5，2，1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】

(1) 直接插入排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】 第七趟直接插入排序：【6，6′，15，17，20，21，23，30】 (2) 希尔排序(增量为5，2，1)

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟希尔排序： 6′，20，6，30，23，15，21，17 第二趟希尔排序： 6′，15，6，17，21，20，23，30 第三趟希尔排序： 6′，6，15，17，20，21，23，30 (3) 起泡排序

初始关键字序列：15，21，6，30，23，6′，20，17 第一趟起泡排序：15，6，21，23，6′，20，17，30 第二趟起泡排序：6，15，21，6′，20，17，23，30 第三趟起泡排序：6，15，6′，20，17，21，23，30 第四趟起泡排序：6，6′，15，17，20，21，30，23 第五趟起泡排序：6，6′，15，17，20，21，30，23 (4) 快速排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟快速排序： 【6′，6】15【30，23，21，20，17】 第二趟快速排序： 6′，6， 15【17，23，21，20】30 第三趟快速排序： 6′，6， 15，17【23，21，20】30 第四趟快速排序： 6′，6， 15，17，【20，21】23，30 第五趟快速排序： 6，6′，15，17，20，21，30，23 (5) 直接选择排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接选择排序： 6，21，15，30，23，6′，20，17 第二趟直接选择排序： 6，6′，15，30，23，21，20，17 第三趟直接选择排序： 6，6′，15，30，23，21，20，17 第四趟直接选择排序： 6，6′，15，17，23，21，20，30 第五趟直接选择排序： 6，6′，15，17，20，21，23，30

第六趟直接选择排序： 6，6′，15，17，20，21，23，30 第七趟直接选择排序： 6，6′，15，17，20，21，23，30 (6) 锦标赛排序

初始关键字序列： 15，21，6，30，23，6′，20，17 6 6 6’ 15 6 6’ 17 15 21 6 30 23 6’ 20 17 6’ 15 6’ 15 30

6’ 17 15 21 ∞ 30 23 6’ 20 17 15 15 23 15 30 23 17 15 21 ∞ 30 23

∞ 20 17

锦标赛排序的基本思想是：首先对n个待排序记录的关键字进行两两比较，从中选出?n/2?个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。我们将一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出，具体做法为：输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。上面给出了排在前三个的记录，详细过程略。 (7) 堆排序

初始关键字序列：15，21，6，30，23，6′，20，17 初始堆： 6，17，6’，21，23，15，20，30 第一次调堆： 6’，17，15， 21，23，30，20，【6】 第二次调堆： 15，17，20，21，23，30，【6’，6】 第三次调堆： 17，21，20，30，23，【15，6’，6】 第四次调堆： 20，21，23，30，【17，15，6’，6】 第五次调堆： 21，30，23，【20，17，15，6’，6】 第六次调堆： 23，30，【21，20，17，15，6’，6】 第七次调堆： 30，【23，21，20，17，15，6’，6】 堆排序结果调堆：【30，23，21，20，17，15，6’，6】 (8) 二路归并排序

初始关键字序列： 15，21，6，30，23，6′，20，17 二路归并排序结果：15，17，20，21，23，30，6，6’ final↑ ↑first (9) 基数排序

初始关键字序列：p→15→21→6→30→23→6′→20→17 第一次分配得到:

B[0].f→30→20←B[0].e B[1].f→21←B[1].e B[3].f→23←B[3].e B[5].f→15←B[5].e B[6].f→6→6’←B[6].e B[7].f→17←B[7].e 第一次收集得到:

p→30→20→21→23→15→6→6’→17 第二次分配得到

B[0].f→6→6’←B[0].e B[1].f→15→17←B[1].e B[2].f→20→21→23←B[5].e B[3].f→30←B[3].e 第二次收集得到

p→6→6’→15→17→20→21→23→30

基数排序结果：6，6′，15，17，20，21，23，30

10.3在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。

【解答】见下表： 排序方法 直接插入排序 折半插入排序 二路插入排序 表插入排序 起泡排序 直接选择排序 希尔排序 快速排序 堆排序 2-路归并排序 基数排序 平均时间 O(n2) O(n2) O(n2) O(n2) O(n2) O(n2) O(n1.3) O(nlog2n) O(nlog2n) O(nlog2n) 最坏情况 O(n2) O(n2) O(n2) O(n2) O(n2) O(n2) O(n1.3) O(n2) O(nlog2n) O(nlog2n) 辅助空间 O(1) O(1) O(n) O(1) O(1) O(1) O(1) O(log2n) O(1) O(n) 稳定性 稳定 稳定 稳定 稳定 稳定 不稳定 不稳定 不稳定 不稳定 稳定 稳定 不稳定排序举例 2,2’,1 3,2,2’,1(d=2,d=1) 2,2’,1 2,1,1’(极大堆) O(d*(rd+n)) O(d*(rd+n)) O (rd ) 10.4在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？

【解答】这种说法不对。因为排序的不稳定性是指两个关键字值相同的元素的相对次序在排序前、后发生了变化，而题中叙述和排序中稳定性的定义无关，所以此说法不对。对4，3，2，1起泡排序就可否定本题结论。

10.5 在堆排序、快速排序和归并排序方法中：

(1)若只从存储空间考虑，则应首先选取哪种排序，其次选取哪种排序，最后选取哪种排序？ (2)若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)若只从平均情况下排序最快考虑，则应选取哪种排序方法？

(4)若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 【解答】

(1)堆排序，快速排序，归并排序 (2)归并排序 (3)快速排序 (4)堆排序

10.6 设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最多。

【解答】对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初始是上升序时关键字交换的次数为最多。

10.7 快速排序的最大递归深度是多少？最小递归深度是多少？

【解答】设待排序记录的个数为n,则快速排序的最小递归深度为?log2n?+1,最大递归深度n。

10.8我们知道，对于n个元素组成的顺序表进行快速排序时，所需进行的比较次数与这n个元素的初始排

序有关。问：

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

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

(1) 在最好情况下,每次划分能得到两个长度相等的子文件。假设文件的长度n=2k-1,那么第一遍划分得到两个长度均为?n/2?的子文件,第二遍划分得到4个长度均为?n/4?的子文件,以此类推,总共进行k=log2(n+1)遍划分,各子文件的长度均为1,排序完毕。当n=7时,k=3,在最好情况下,第一遍需比较6次,第二遍分别对两个子文件（长度均为3,k=2）进行排序,各需2次,共10次即可。 (2) 在最好情况下快速排序的原始序列实例：4,1,3,2,6,5,7。

(3) 在最坏情况下,若每次用来划分的记录的关键字具有最大(或最小)值,那么只能得到左(或右)子文件,其长度比原长度少1。因此,若原文件中的记录按关键字递减次序排列,而要求排序后按递增次序排列时,快速排序的效率与冒泡排序相同,其时间复杂度为O(n2)。所以当n=7时,最坏情况下的比较次数为21次。 (4) 在最坏情况下快速排序的初始序列实例： 7,6,5,4,3,2,1,要求按递增排序。 10.9判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整成堆。 (1) 100，90，80，60，85，75，20，25，10，70，65，50 (2) 100，70，50，20，90，75，60，25，10，85，65，80 【解答】 (1) 是堆

(2) 不是堆。 调成大堆： 100,90,80,25,85,75,60,20,10,70,65,50

10.10 在多关键字排序时，LSD和MSD两种方法的特点是什么？ 【解答】

最高位优先（MSD）法：先对最高位关键字K0进行排序,将序列分成若干子序列,每个子序列中的记录都具有相同的K0值,然后,分别就每个子序列对关键字K1进行排序,按K1值不同再分成若干更小的子序列,??,依次重复,直至最后对最低位关键字排序完成,将所有子序列依次连接在一起,成为一个有序子序列。

最低位优先（LSD）法：先对最低位关键字Kd-1进行排序,然后对高一级关键字Kd-2进行排序,依次重复,直至对最高位关键字K0排序后便成为一个有序序列。进行排序时,不必分成子序列,对每个关键字都是整个序列参加排序,但对Ki (0<=i

10.11 给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，列出一趟分配和收集的过程。 【解答】

按LSD法 →321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

321 33 34 156 57 28 331 63 46 7

收集 →321→331→33→63→34→156→46→57→7→28

10.12 奇偶交换排序如下所述：对于初始序列A[1]，A[2]，?，A[n]，第一趟对所有奇数i(1<=iA[i+1]，则将两者交换；第二趟对所有偶数i(2<=iA[i+1]，则将两者交换；第三趟对所有奇数i(1<=i

(2) 写出用这种排序方法对35，70，33，65，24，21，33进行排序时，每一趟的结果。

【解答】

(1) 排序结束条件为没有交换为止 (2)

第一趟奇数：35,70,33,65,21,24,33 第二趟偶数：35,33,70,21,65,24,33

第三趟奇数：33,35,21,70,24,65,33 第四趟偶数：33,21,35,24,70,33,65

第五趟奇数：21,33,24,35,33,70,65 第六趟偶数：21,24,33,33,35,65,70

第七趟奇数：21,24,33,33,35,65,70(无交换) 第八趟偶数：21,24,33,33,35,65,70(无交换) 结束

10.13 设某文件经内排序后得到100个初始归并段(初始顺串)，若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？

【解答】 设归并路数为k,归并趟数为s,则s=?logk100?,因?logk100?=3 ,且k为整数，故k=5,即最少5路归并可以完成排序。

10.14 证明：置换-选择排序法产生的初始归并段的长度至少为m。(m是所用缓冲区的长度)。

【证明】 由置换选择排序思想,第一个归并段中第一个元素是缓冲区中最小的元素,以后每选一个元素都不应小于前一个选出的元素,故当产生第一个归并段时（即初始归并段）,缓冲区中m个元素中除最小元素之外,其他m-1个元素均大于第一个选出的元素,即当以后读入元素均小于输出元素时,初始归并段中也至少能有原有的m个元素。证毕。

10.15 设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做4路平衡归并，要求： (1)指出总的归并趟数； (2)构造最佳归并树；

(3)根据最佳归并树计算每一趟及总的读记录数。 【解答】

因为(11-1)%(4-1)=1,所以加“虚段”,第一次由两个段合并。 25 9 16 40 48 53 25 77 128

242 64 38 88 556 98

(1)三趟归并

(2)最佳归并树如图 (3)设每次读写一个记录 第一趟50次读写 总的读写次数：2052 [(9+16)*3+(25+38+40)*2+ (48+53+64+77)*2+(88+98)]*2

10.16 对输入文件(101，51，19，61，3，71，31，17，19，100，55，20，9，30，50，6，90)，当k=6时，使用置换-选择算法，写出建立的初始败者树及生成的初始归并段。 【解答】 2 5 71 4 0 3 1 3 1 61 1

19 1 51 1 101 1 1

初始败者树

初始归并段： R1:3,19,31,51,61,71,100,101

R2:9,17,19,20,30,50,55,90 R3:6

10.17 选择题：下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。 A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆排序法 【解答】A

10.18 选择题：一个排序算法的时间复杂度与以下哪项有关。 A．排序算法的稳定性 B. 所需比较关键字的次数 C. 所采用的存诸结构 D. 所需辅助存诸空间的大小 【解答】B

二、算法设计题

10.19 请编写一个算法，在基于单链表表示的关键字序列上进行简单选择排序。 void LinkedListSelectSort(pointer head);

∥本算法一趟找出一个关键字最小的结点,其数据和当前结点进行交换;若要交换指针 ∥则须记下当前结点和最小结点的前驱指针 { p=head->next;

while(p)

{ q=p->next; r=p; ∥设r是指向关键字最小的结点的指针 while(q!=null)

{ if(q->datadata) r=q;

q=q->next; }

if (r!=p) r->data<-->p->data; p=p->next; }//while

}// LinkedListSelectSort

10.20 设单链表头结点指针为L，结点数据为整型。试写出对链表L按“直接插入方法”排序的算法。

void LinkInserSort(LinkedList L)

//本算法对单链表L按“直接插入方法”进行排序

{ p=L->next->next; //链表至少一个结点,p初始指向链表中第二结点（若存在） L->next->next=null; //初始假定第一个记录有序 while(p!=null)

{q=p->next; //q指向p的后继结点} s=L;

while(s->next!=null && s->next->datadata)

s=s->next; //向后找插入位置

p->next=s->next; s->next=p;//插入结点 p=q; //恢复p指向当前结点 }//while

}// LinkInserSort

10.21 试设计一个双向冒泡排序算法，即在排序过程中交替改变扫描方向。 void BubbleSort2(int a[],int n) ∥相邻两趟向相反方向起泡的冒泡排序算法 {change=1;low=0;high=n-1; ∥冒泡的上下界 while(low

{change=0; ∥设不发生交换

for(i=low;i

if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;} ∥有交换,修改标志change high--; ∥修改上界

for(i=high;i>low;i--) ∥气泡下沉,小元素上浮（向左） if(a[i]a[i-1];change=1;} low++; ∥修改下界 }∥while }∥BubbleSort2

10.22 写出快速排序的非递归算法。 void QuickSort(rectype r[n+1]; int n) {∥ 对r[1..n]进行快速排序的非递归算法 typedef struct{int low,high; }node node s[n+1]；∥栈,容量足够大

int quickpass(rectype r[],int,int); ∥ 函数声明 int top=1; s[top].low=1; s[top].high=n; while(top>0)

{ss=s[top].low; tt=s[top].high; top--;

if(ss

{k=quickpass(r,ss,tt);

if(k-ss>1) {s[++top].low=ss; s[top].high=k-1;}

if(tt-k>1) {s[++top].low=k+1; s[top].high=tt;}

}

} ∥ 算法结束

int quickpass(rectype r[];int s,t) { i=s; j=t; rp=r[i]; x=r[i].key; while （i

{ while(i

while(i=r[j].key) i++; if(i

return (i);

} ∥ 一次划分算法结束

[算法讨论]可对以上算法进行两点改进：一是在一次划分后,先处理较短部分,较长的子序列进栈；二是用“三者取中法”改善快速排序在最坏情况下的性能。下面是部分语句片段： int top=1; s[top].low=1; s[top].high=n;

ss=s[top].low; tt=s[top].high; top--; flag=true; while(flag || top>0)

{k=quickpass(r,ss,tt);

if(k-ss>tt-k) ∥ 一趟排序后分割成左右两部分

{if(k-ss>1) ∥ 左部子序列长度大于右部,左部进栈 {s[++top].low=ss; s[top].high=k-1; }

if(tt-k>1) ss=k+1; ∥ 右部短的直接处理 else flag=false; ∥ 右部处理完,需退栈 }

else if(tt-k>1) ∥右部子序列长度大于左部,右部进栈 {s[++top].low=k+1; s[top].high=tt; }

if(k-ss>1) tt=k-1 ∥ 左部短的直接处理 else flag=false ∥ 左部处理完,需退栈 }

if(!flag && top>0) ∥退栈 {ss=s[top].low; tt=s[top].high; top--; flag=true;} } ∥ end of while(flag || top>0) } ∥ 算法结束

int quickpass(rectype r[];int s,t)

∥ 用“三者取中法”进行快速排序的一次划分 { int i=s, j=t, mid=(s+t)/2; rectype tmp;

if(r[i].key>r[mid].key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp } if(r[mid].key>r[j].key) {tmp=r[j];r[j]=r[mid];

if(tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp } }

{tmp=r[i];r[i]=r[mid];r[mid]=tmp }

∥ 三者取中：最佳2次比较3次赋值；最差3次比较10次赋值 rp=r[i]; x=r[i].key;

while （i

{while(i

while(i=r[j].key) i++; if(i

r[i]=rp; return (i);

} ∥ 一次划分算法结束

10.23 假设由1000个关键字为小于10000的整数的记录序列，请设计一种排序方法，要求以尽可能少的比较次数和移动次数实现排序，并按你的设计编写算法。

【题目分析】设关键字小于10000的整数的记录序列存于数组中，再设容量为10000的临时整数数组，按整数的大小直接放入下标为该整数的数组单元中，然后对该数组进行整理存回原容量为1000的数组中。 void intsort(int R[],int n)

{//关键字小于10000的1000个整数存于数组R中，本算法对整数进行排序 int R1[10000]={0}; //初始化为0 for(i=0;i<1000;i++) R1[R[i]]=R[i];

for(i=0,k=0;i<10000;i++) if(R1[i]!=0)

R[k++]=R1[i]; }

10.24 荷兰国旗问题：设有一个仅有红、白、蓝 三种颜色的条块组成的条块序列。编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案

【题目分析】设用整型数组R表示荷兰国旗,元素值1、2和3分别表示红、白和篮色。再设整型变量i,j和k,排序结束后R[1..i-1]表示红色,R[i..j-1]表示白色,R[j..n]表示篮色。 void DutchFlag(int R[],int n)

∥对红、白、篮三种颜色的条块,经排序形成荷兰国旗 { int i=1,j=1,k=n; ∥指针初始化,j到k是待排序元素 while(j<=k)

if(r[j]==1) ∥红色

{r[i]<-->r[j]; i++;j++; } else if(r[j]==2) j++; ∥白色

else {r[j]<-->r[k]; k--;} ∥兰色

}

[算法讨论]象将元素值为正数、负数和零排序成前面都是负数,接着是零,最后是正数的排序,以及字母字符、数字字符和其它字符的排序等,都属于这类荷兰国旗问题。排序后,红、白和蓝色的元素个数分别为i-1,j-i,n-j+1。

10.25 已知记录序列a[1..n]中的关键字各不相同，可按如下所述实现计数排序：另设数组c[1..n]，对每个记录a[i]，统计序列中关键字比它小的记录个数存于c[i]，则c[i]=0的记录必为关键字最小的记录，然后依c[i]值的大小对a中记录进行重新排列，编写算法实现上述排序方法。 void CountSort(rectype r[],int n)

{//对r[1..n]进行计数排序

c[1..n] =0; //c数组初始化，元素值指其在r中的位置。

for(i=1;ir[j].key) c[i]++; else c[j]++; i=1;

while(i

while(c[j]+1!=i)

{k=c[j]+1;rt=r[k]; //暂时保存r[k]/ r[k]=rc; j=c[k]; //取下一 j 值 c[k]=k-1; //第k个已排好 rc=rt

}

r[i]=rc; c[i]=i-1； //完成了一个小循环，第i个已排好 }//if i=i+1 }// while

上述调整也可用如下逻辑简单但效率低下的算法： c[1..n]= c[1..n]+1 {c数组元素值指其在r中的位置。 while( i

{ while( c[i]!=i)

{j=c[i]; c[i]? ? c[j]; r[i]? ? r[j]} i=i+1; }

10.26 若待排序序列用单链表存储，试给出其快速排序算法。

[题目分析]快速排序的思想是以第一个元素作“枢轴”,通过一趟的比较,将枢轴元素放在其排序的最终位置,使它左面的元素都小于等于它,而它右面的元素都大于等于它,从而再对其左右两部分递归进行快速排序。在链表中实现快速排序也必须使用这一原则。 void LinkQuickSort(LinkedList start,end)

∥对单链表start进行快速排序,end是链表的尾指针,初始调用时为null { LinkedList start1,end1,end2,p;

int flag=0; ∥tag是是否结束排序的标志

If(start==null || start==end) return; ∥空表或只有一个结点

start1=end1=start; ∥start1和end1是右一半链表头结点的前驱和尾结点的指针 if(end1!=end) flag=1;

p=start->next; ∥p为工作指针

while(flag) ∥进行一趟快速排序

{ if(p->datadata) ∥结点插入前一半 {end1->next=p->next; ∥保留后继结点 if(p==end) flag=0; ∥一趟快速排序结束

if(start==end1)

end0=p;∥end0是遍历遇到的第一个小于枢轴的结点,将为前半的尾结点

p->next=start; start=p;∥修改左半部链表头指针 p=end1->next; ∥恢复当前待处理结点 }

else ∥处理右半部链表

{if(p==end) flag=0; ∥已到链表尾

end1->next=p; end1=p; ;∥end1和p是前驱和后继关系 p=p->next; }∥else

}∥while

LinkQuickSort(start,end0); ∥对枢轴元素最终位置前的单链表快速排序 LinkQuickSort(start1->next,end1);∥对枢轴元素最终位置后的单链表快速排序 }∥LinkQuickSort

10.27 在数组A[0..n-1]中存放有n个不同的整数，其值均在1到n之间。写出一个函数或过程，将A中的n个数从大到小排序后存入B[0..n-1]数组中，要求算法的时间复杂度为O(n)。 【题目分析】因为n个值不同且大小在1到n之间的整数,要求逆序放入另一数组,只要逐个取出放到适当位置即可。即值为i(1<=i<=n)的元素就是数组下标为n-i的元素。 void ReArrange(int A[], int B[],int n) {for(i=0;i

if(start==end1)

end0=p;∥end0是遍历遇到的第一个小于枢轴的结点,将为前半的尾结点

p->next=start; start=p;∥修改左半部链表头指针 p=end1->next; ∥恢复当前待处理结点 }

else ∥处理右半部链表

{if(p==end) flag=0; ∥已到链表尾

end1->next=p; end1=p; ;∥end1和p是前驱和后继关系 p=p->next; }∥else

}∥while

LinkQuickSort(start,end0); ∥对枢轴元素最终位置前的单链表快速排序 LinkQuickSort(start1->next,end1);∥对枢轴元素最终位置后的单链表快速排序 }∥LinkQuickSort

10.27 在数组A[0..n-1]中存放有n个不同的整数，其值均在1到n之间。写出一个函数或过程，将A中的n个数从大到小排序后存入B[0..n-1]数组中，要求算法的时间复杂度为O(n)。 【题目分析】因为n个值不同且大小在1到n之间的整数,要求逆序放入另一数组,只要逐个取出放到适当位置即可。即值为i(1<=i<=n)的元素就是数组下标为n-i的元素。 void ReArrange(int A[], int B[],int n) {for(i=0;i

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