第四章习题 1.假设线性表按关键字递增顺序存放,试写出在此线性表上进行顺序查找的算法 nt searchI( Seqlist *I,intx)/按关键字升序排列的顺序存储的线性表上的顺序查找* >r[o].key=x; le(L->ri].key>x) f(L->r[i key==x) n(1) return(O) NODE *search2(NODE *head, int x) /*按关键字升序排列的链式存储的线性表上的顺序查找* (NODE"p: p=head->next while(p!=nULL&&p->data. keynext; return(p) eturn(NULL) 2.写出以链式存储结构存放的线性表上的顺序查找算法。 nodetype * search(nodetype *head, elemtype nodetype*p; p=head->next while(p!=nulL & p->datal=x) return p, 3.试写出递归的二分查找算法。 int binsearch( Elem Type r[, int low, int high, int x) int mid
第四章习题 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.keynext; if(p->data.key==x) return(p); else return(NULL); } 2． 写出以链式存储结构存放的线性表上的顺序查找算法。 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(xr[mid)) low=mid+1 return mid- return 0 4.试分别画出在线性表(ab,cd,e,f,gh)中使用二分查找方法查找关键字e、f和h过程。 (1)查找关键字e hi high=t d h low=5 mid=6 high=8 g h; low-mid=high=5 查找成功 (2)查找关键字f g h; low=5 mid=6 high=8 查找成功 (3)查找关键字h h d=6
{ mid=(low+high)/2; if(xr[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
low=7 mid=7 high=8 low=mid=high=8 查找成功 5、对关键字序列{18,25,14,56,78,33,27,32,60,42}用除留取余法构造哈希函数 将其散列到地址空间0~12中。试分别画出分别采用①线性探测再散列、②二次探测再散列、 ③链地址法处理冲突所生成的哈希表,并分别求出等概率条件下在三个哈希表上查找成功时 的平均查找长度。 p=13 h(k)=k 地址表 关键字182 14 6 33 32 地址表 5 2 7 8 线性探测处理冲突生成的哈希表 14 42 6 18 33 25 ASL=(1+1+1+1+1+1+2+1+1+1)/10=1.1 二次探测处理冲突生成的哈希表 10 78 14|2742 32 60 ASL=(1+1+1+1+1+1+2+1+1+1 链地址处理冲突生成的哈希表
{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 链地址处理冲突生成的哈希表
0 27∧ 2∧ 18∧ 6 32∧ 7 33∧ 10∧ 5∧ 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},分别写出直 接插入排序、冒泡排序、快速排序和简单选择排序的各趟排序结果。 53871261706827652135} 直接插入排序 初始状态 87126170682765 第一趟:{53871261706827652135} 第二趟:{538712617068 第三趟:{12538761706827652135} 第四趟:{12536187706827652135 第五趟:{12536170876827652135} 第六趟:{12536168708727 35}
∧ 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} 14 27 ∧ 42 ∧ 56 ∧ 18 ∧ 32 ∧ 33 ∧ ∧ 0 78 ∧ 1 2 3 4 5 6 7 8 ∧ ∧ ∧ 9 10 11 12 60 ∧ 25 ∧
第七趟 12275361687087652135} 第八趟:{1227536165687087213 第九趟:{122127 第十趟 122127 5361 冒泡排序 初始状态:{53871261706827652135} 第一趟:{12538721617068276535} 第二趟:{122153872761706865 第三趟:{12212753 3561706865} 第四趟:{122 第五趟:{122127355361876568 第六趟:{12 70} 第七趟:{122127353616568 70} 第八趟:{12212735536165 快速排序 初始状态:{538712617068 进行一次表划分的全过程为 53871261706827652135 35871261706827652135 35871261706827652187 35211261 35211261706827652187 35211261706827656187 352112617068276 3521122770682765 35211227706870656187 完成第一趟排序的结果
第七趟： { 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 完成第一趟排序的结果：
[3521122753[6870656187] 分别进行快速排序 221 61[65 70[87 12[21 最后排序结果: 122127355361656 7087 简单选择排序 初始状态:{53871261706827652135} 第一趟: 1287536170682765213 第二趟: 12215361706827658735} 第三趟 12212761706853658735} 第四趟 12212735706853658761} 第五趟:{12212735536870658761} 第六趟 12212735536170658768} 第七趟:{12212735536165708768 第八 8770} 第九 12212735536165 87} 8.对n个元素组成的线性表进行快速排序时,所需进行的比较次数依赖于元素的初始排列 顺序 (1)n=7时,在最好情况下需要进行多少次比较?说明理由。 (2)n=7时,给出一个最好情况的初始排列实例。 (1)10次比较 每次将待排序区间均匀划分为两个小区间 (2)最好情况实例 [342645]53[786189]6次比较 [26]34[45]2次比较 [61]7889]2次比较 9.写出以单链表为存储结构实现简单选择排序的算法 假定结点的数据值为整型 void selectsort(NODE* head) (NODE", q,top /*q用于记下排序范围数据域值最小的结点的指针* /*top用于记下待排序范围最前端结点的指针* int temp
[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 个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于元素的初始排列 顺序。 （1）n=7 时，在最好情况下需要进行多少次比较？说明理由。 （2）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 while(p!l=NULL temp=top->data top=top->next, 10.对于参加某次英语竞赛的所有选手的成绩进行排序,已知每位选手的信息包括姓名、系 别和笔试、口语、听力三门比赛成绩,要求对所有选手按总分由高到低进行排序;若总分相 同,则按笔试成绩由高到低排序;若总分和笔试成绩均相同,则按口语成绩由高到低排序。 最后打印出本次英语竞赛的排行榜,格式如下: 名次 姓名 系别 笔试口语听力总分 张三 中文 李四 计算机 287 参考程序见“程序示例”文件夹中的“ multikeysort.cpp
top=head->next; while(top->next!=NULL) { p=top->next; q=top; while(p!=NULL) { if(p->datadata) 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
