第四章习题
1.假设线性表按关键字递增顺序存放，试写出在此线性表上进行顺序查找的算法。
int search1(SeqList *L,int x)/*按关键字升序排列的顺序存储的线性表上的顺序查找*/
{int i;
L->r[0].key=x;
i=n;
while(L->r[i].key>x)
i--;
if(L->r[i].key==x)
return(i);
else
return(0);
}
NODE *search2(NODE *head,int x)
/*按关键字升序排列的链式存储的线性表上的顺序查找*/
{NODE *p;
p=head->next;
while(p!=NULL&&p->data.key<x)
p=p->next;
if(p->data.key==x)
return(p);
else
return(NULL);
}
写出以链式存储结构存放的线性表上的顺序查找算法。
nodetype *searchL(nodetype *head,elemtype x)
{
nodetype *p;
p=head->next;
while(p!=NULL && p->data!=x)
p=p->next;
return p;
}
3．试写出递归的二分查找算法。
int binsearch(ElemType r[],int low,int high,int x)
{
int mid;
if(low<=high)
{
mid=(low+high)/2;
if(x<r[mid])
{
high=mid-1;
binsearch(r,low,high,x);
}
else
if(x>r[mid])
{
low=mid+1;
binsearch(r,low,high,x);
}
else
return mid;
}
else
return 0;
}
4．试分别画出在线性表（a,b,c,d,e,f,g,h）中使用二分查找方法查找关键字e、f和h过程。
(1)查找关键字e
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
{a b c d e f g h}
low=mid=high=5 查找成功
(2)查找关键字f
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
查找成功
(3)查找关键字h
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
{a b c d e f g h}
low=7 mid=7 high=8
{a b c d e f g h}
low=mid=high=8 查找成功
5、对关键字序列{18，25，14，56，78，33，27，32，60，42}用除留取余法构造哈希函数，将其散列到地址空间0~12中。试分别画出分别采用①线性探测再散列、②二次探测再散列、③链地址法处理冲突所生成的哈希表，并分别求出等概率条件下在三个哈希表上查找成功时的平均查找长度。
m=13 p=13
h(k)=key%p;
地址表关键字
18
25
14
56
78
33
27
32
60
42
地址表
5
12
1
4
0
7
1
6
8
3
线性探测处理冲突生成的哈希表
0
1
2
3
4
5
6
7
8
9
10
11
12
78
14
27
42
56
18
32
33
60
25
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
二次探测处理冲突生成的哈希表
0
1
2
3
4
5
6
7
8
9
10
11
12
78
14
27
42
56
18
32
33
60
25
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
链地址处理冲突生成的哈希表
∧
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
6、对于一组给定的关键字序列{53，87，12，61，70，68，27，65，21，35}，分别写出直接插入排序、冒泡排序、快速排序和简单选择排序的各趟排序结果。
{ 53 87 12 61 70 68 27 65 21 35}
直接插入排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{ 53 87 12 61 70 68 27 65 21 35}
第二趟,{ 53 87 12 61 70 68 27 65 21 35}
第三趟,{ 12 53 87 61 70 68 27 65 21 35}
第四趟,{ 12 53 61 87 70 68 27 65 21 35}
第五趟,{ 12 53 61 70 87 68 27 65 21 35}
第六趟,{12 53 61 68 70 87 27 65 21 35}
第七趟,{ 12 27 53 61 68 70 87 65 21 35}
第八趟,{ 12 27 53 61 65 68 70 87 21 35}
第九趟,{ 12 21 27 53 61 65 68 70 87 35}
第十趟,{12 21 27 35 53 61 65 68 70 87 }
冒泡排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{12 53 87 21 61 70 68 27 65 35}
第二趟,{12 21 53 87 27 61 70 68 65 35}
第三趟,{12 21 27 53 87 35 61 70 68 65 }
第四趟,{12 21 27 35 53 87 61 65 70 68 }
第五趟,{12 21 27 35 53 61 87 65 68 70 }
第六趟,{12 21 27 35 53 61 65 87 68 70 }
第七趟,{12 21 27 35 53 61 65 68 87 70 }
第八趟,{12 21 27 35 53 61 65 68 70 87 }
快速排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
进行一次表划分的全过程为：
53 87 12 61 70 68 27 65 21 35
( (
35 87 12 61 70 68 27 65 21 35
( (
35 87 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 61 87
( (
35 21 12 61 70 68 27 65 61 87
( (
35 21 12 27 70 68 27 65 61 87
( (
35 21 12 27 70 68 70 65 61 87
( (
35 21 12 27 70 68 70 65 61 87
((
完成第一趟排序的结果：
[35 21 12 27] 53 [68 70 65 61 87 ]
分别进行快速排序：
[27 21 12] 35 [61 65] 68 [70 87]
[12 21] 27 61 [65] 70 [87]
12 [21]
最后排序结果：
12 21 27 35 53 61 65 68 70 87
简单选择排序
初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{ 12 87 53 61 70 68 27 65 21 35}
第二趟,{ 12 21 53 61 70 68 27 65 87 35}
第三趟,{ 12 21 27 61 70 68 53 65 87 35}
第四趟,{ 12 21 27 35 70 68 53 65 87 61}
第五趟,{ 12 21 27 35 53 68 70 65 87 61}
第六趟,{ 12 21 27 35 53 61 70 65 87 68}
第七趟,{ 12 21 27 35 53 61 65 70 87 68}
第八趟,{ 12 21 27 35 53 61 65 68 87 70 }
第九趟,{ 12 21 27 35 53 61 65 68 70 87 }
8．对n个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于元素的初始排列顺序。
n=7时，在最好情况下需要进行多少次比较？说明理由。
n=7时，给出一个最好情况的初始排列实例。
（1）10次比较
每次将待排序区间均匀划分为两个小区间
（2）最好情况实例
53 26 45 34 78 61 89
[34 26 45] 53 [78 61 89] 6次比较
[26] 34 [45] 2次比较
[61] 78 [89] 2次比较
9．写出以单链表为存储结构实现简单选择排序的算法。
// 假定结点的数据值为整型
void selectsort(NODE* head)
{NODE *p,*q,*top;
/*q用于记下排序范围数据域值最小的结点的指针*/
/*top用于记下待排序范围最前端结点的指针*/
int temp;
top=head->next;
while(top->next!=NULL)
{
p=top->next;
q=top;
while(p!=NULL)
{
if(p->data<q->data)
q=p;
p=p->next;
}
temp=top->data;
top->data=q->data;
q->data=temp;
top=top->next;
}
}
10．对于参加某次英语竞赛的所有选手的成绩进行排序，已知每位选手的信息包括姓名、系别和笔试、口语、听力三门比赛成绩，要求对所有选手按总分由高到低进行排序；若总分相同，则按笔试成绩由高到低排序；若总分和笔试成绩均相同，则按口语成绩由高到低排序。最后打印出本次英语竞赛的排行榜，格式如下：
名次 姓名 系别 笔试 口语 听力 总分
1 张三 中文 96 98 95 289
2 李四 计算机 97 95 95 287
… … … … … … …
参考程序见“程序示例”文件夹中的“multikeysort.cpp”。
1.假设线性表按关键字递增顺序存放，试写出在此线性表上进行顺序查找的算法。
int search1(SeqList *L,int x)/*按关键字升序排列的顺序存储的线性表上的顺序查找*/
{int i;
L->r[0].key=x;
i=n;
while(L->r[i].key>x)
i--;
if(L->r[i].key==x)
return(i);
else
return(0);
}
NODE *search2(NODE *head,int x)
/*按关键字升序排列的链式存储的线性表上的顺序查找*/
{NODE *p;
p=head->next;
while(p!=NULL&&p->data.key<x)
p=p->next;
if(p->data.key==x)
return(p);
else
return(NULL);
}
写出以链式存储结构存放的线性表上的顺序查找算法。
nodetype *searchL(nodetype *head,elemtype x)
{
nodetype *p;
p=head->next;
while(p!=NULL && p->data!=x)
p=p->next;
return p;
}
3．试写出递归的二分查找算法。
int binsearch(ElemType r[],int low,int high,int x)
{
int mid;
if(low<=high)
{
mid=(low+high)/2;
if(x<r[mid])
{
high=mid-1;
binsearch(r,low,high,x);
}
else
if(x>r[mid])
{
low=mid+1;
binsearch(r,low,high,x);
}
else
return mid;
}
else
return 0;
}
4．试分别画出在线性表（a,b,c,d,e,f,g,h）中使用二分查找方法查找关键字e、f和h过程。
(1)查找关键字e
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
{a b c d e f g h}
low=mid=high=5 查找成功
(2)查找关键字f
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
查找成功
(3)查找关键字h
{a b c d e f g h}
low=1 mid=4 high=8
{a b c d e f g h}
low=5 mid=6 high=8
{a b c d e f g h}
low=7 mid=7 high=8
{a b c d e f g h}
low=mid=high=8 查找成功
5、对关键字序列{18，25，14，56，78，33，27，32，60，42}用除留取余法构造哈希函数，将其散列到地址空间0~12中。试分别画出分别采用①线性探测再散列、②二次探测再散列、③链地址法处理冲突所生成的哈希表，并分别求出等概率条件下在三个哈希表上查找成功时的平均查找长度。
m=13 p=13
h(k)=key%p;
地址表关键字
18
25
14
56
78
33
27
32
60
42
地址表
5
12
1
4
0
7
1
6
8
3
线性探测处理冲突生成的哈希表
0
1
2
3
4
5
6
7
8
9
10
11
12
78
14
27
42
56
18
32
33
60
25
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
二次探测处理冲突生成的哈希表
0
1
2
3
4
5
6
7
8
9
10
11
12
78
14
27
42
56
18
32
33
60
25
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
链地址处理冲突生成的哈希表
∧
ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1
6、对于一组给定的关键字序列{53，87，12，61，70，68，27，65，21，35}，分别写出直接插入排序、冒泡排序、快速排序和简单选择排序的各趟排序结果。
{ 53 87 12 61 70 68 27 65 21 35}
直接插入排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{ 53 87 12 61 70 68 27 65 21 35}
第二趟,{ 53 87 12 61 70 68 27 65 21 35}
第三趟,{ 12 53 87 61 70 68 27 65 21 35}
第四趟,{ 12 53 61 87 70 68 27 65 21 35}
第五趟,{ 12 53 61 70 87 68 27 65 21 35}
第六趟,{12 53 61 68 70 87 27 65 21 35}
第七趟,{ 12 27 53 61 68 70 87 65 21 35}
第八趟,{ 12 27 53 61 65 68 70 87 21 35}
第九趟,{ 12 21 27 53 61 65 68 70 87 35}
第十趟,{12 21 27 35 53 61 65 68 70 87 }
冒泡排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{12 53 87 21 61 70 68 27 65 35}
第二趟,{12 21 53 87 27 61 70 68 65 35}
第三趟,{12 21 27 53 87 35 61 70 68 65 }
第四趟,{12 21 27 35 53 87 61 65 70 68 }
第五趟,{12 21 27 35 53 61 87 65 68 70 }
第六趟,{12 21 27 35 53 61 65 87 68 70 }
第七趟,{12 21 27 35 53 61 65 68 87 70 }
第八趟,{12 21 27 35 53 61 65 68 70 87 }
快速排序初始状态,{ 53 87 12 61 70 68 27 65 21 35}
进行一次表划分的全过程为：
53 87 12 61 70 68 27 65 21 35
( (
35 87 12 61 70 68 27 65 21 35
( (
35 87 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 21 87
( (
35 21 12 61 70 68 27 65 61 87
( (
35 21 12 61 70 68 27 65 61 87
( (
35 21 12 27 70 68 27 65 61 87
( (
35 21 12 27 70 68 70 65 61 87
( (
35 21 12 27 70 68 70 65 61 87
((
完成第一趟排序的结果：
[35 21 12 27] 53 [68 70 65 61 87 ]
分别进行快速排序：
[27 21 12] 35 [61 65] 68 [70 87]
[12 21] 27 61 [65] 70 [87]
12 [21]
最后排序结果：
12 21 27 35 53 61 65 68 70 87
简单选择排序
初始状态,{ 53 87 12 61 70 68 27 65 21 35}
第一趟,{ 12 87 53 61 70 68 27 65 21 35}
第二趟,{ 12 21 53 61 70 68 27 65 87 35}
第三趟,{ 12 21 27 61 70 68 53 65 87 35}
第四趟,{ 12 21 27 35 70 68 53 65 87 61}
第五趟,{ 12 21 27 35 53 68 70 65 87 61}
第六趟,{ 12 21 27 35 53 61 70 65 87 68}
第七趟,{ 12 21 27 35 53 61 65 70 87 68}
第八趟,{ 12 21 27 35 53 61 65 68 87 70 }
第九趟,{ 12 21 27 35 53 61 65 68 70 87 }
8．对n个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于元素的初始排列顺序。
n=7时，在最好情况下需要进行多少次比较？说明理由。
n=7时，给出一个最好情况的初始排列实例。
（1）10次比较
每次将待排序区间均匀划分为两个小区间
（2）最好情况实例
53 26 45 34 78 61 89
[34 26 45] 53 [78 61 89] 6次比较
[26] 34 [45] 2次比较
[61] 78 [89] 2次比较
9．写出以单链表为存储结构实现简单选择排序的算法。
// 假定结点的数据值为整型
void selectsort(NODE* head)
{NODE *p,*q,*top;
/*q用于记下排序范围数据域值最小的结点的指针*/
/*top用于记下待排序范围最前端结点的指针*/
int temp;
top=head->next;
while(top->next!=NULL)
{
p=top->next;
q=top;
while(p!=NULL)
{
if(p->data<q->data)
q=p;
p=p->next;
}
temp=top->data;
top->data=q->data;
q->data=temp;
top=top->next;
}
}
10．对于参加某次英语竞赛的所有选手的成绩进行排序，已知每位选手的信息包括姓名、系别和笔试、口语、听力三门比赛成绩，要求对所有选手按总分由高到低进行排序；若总分相同，则按笔试成绩由高到低排序；若总分和笔试成绩均相同，则按口语成绩由高到低排序。最后打印出本次英语竞赛的排行榜，格式如下：
名次 姓名 系别 笔试 口语 听力 总分
1 张三 中文 96 98 95 289
2 李四 计算机 97 95 95 287
… … … … … … …
参考程序见“程序示例”文件夹中的“multikeysort.cpp”。
