第四章习题 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. key<x) p=p->next; 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.key<x) p=p->next; 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(x<r[mid) binsearch(r, low, high, x); else f(x>r[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(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
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 完成第一趟排序的结果：