河南广播电视大学现数中心 第八章查找课后习题容案 1,单项选择题 (1)D (2)C (3)C (4)B (5)C 2、综合圈 (1)参考算法： int segsearch(NOOE a0 int nint k) {夏监视哨设在个无素的升序期序表低下标端，期序查找关健字为k的数据无素。 看存在，则返国其在顺序表中的位置。吾则，运回0 河kyt i-n. while (r]key构 if0088key-k幻 retum0: 0 e山moy (2) 查找7： low-0 hight-8 mid-4 9p7 10w=0 hight=3 md车1 3×7 low-2 hight=3 mid-2 5c7 low-3 hight-3 mid-3 7-?找到 查找15 low=0 hight= mid49<15 low=5 hight=8 mid-6 13<15 1ow-7 hight-8mid715-15找到 (3)分块查找索引表由若干个所有记录组成，每个索明记录对应一个块。素引记录包含两 个数据项，即对应块内最大美健字值和块中第一个记录位置的地址指针。 分块查找首先要对素引表选行查找以确定给定值所在的块，由于素引表有序。则可用顺 序查找。也可用折半查找：其次在该块中查找给定的值，由于块内不一定有序，所以要用顺 序查找。 第1页共4页 版权所有河南电大现赖中心袍隔，配箱@恤田
河南广播电视大学现教中心 第1页 共4页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第八章 查找 课后习题答案 1、 单项选择题 （1） D （2） C （3） C （4） B （5） C 2、 综合题 （1）参考算法： int seqsearch( NODE a[], int n,int k) { // 监视哨设在 n 个元素的升序顺序表低下标端，顺序查找关键字为 k 的数据元素。 //若存在，则返回其在顺序表中的位置，否则，返回 0 r[0].key=k; i=n; while (r[i].key>k) i--; if (i>0 && r[i].key==k) return(i); else return(0); } （2） 查找 7： low=0 hight=8 mid=4 9>7 low=0 hight=3 mid=1 3<7 low=2 hight=3 mid=2 5<7 low=3 hight=3 mid=3 7=7 找到 查找 15： low=0 hight=8 mid=4 9<15 low=5 hight=8 mid=6 13<15 low=7 hight=8 mid=7 15=15 找到 （3）分块查找索引表由若干个所有记录组成，每个索引记录对应一个块。索引记录包含两 个数据项，即对应块内最大关键字值和块中第一个记录位置的地址指针。 分块查找首先要对索引表进行查找以确定给定值所在的块，由于索引表有序，则可用顺 序查找，也可用折半查找；其次在该块中查找给定的值，由于块内不一定有序，所以要用顺 序查找
问南广播电视大学现黄中心 (4)二叉序树如知下图： 中序：12223引4046657888 后序：1231402265887846 (5) 序列119,1,23,14.55,20,84.27,68.11.10,77 0123456789101112131415161718 1145527681920842311077 H(ky)=k%13m=19 H(19)-6 H(1)=1 H(23)=10 H(14)-1冲突，H1-(1+1)%19-2 H(55)=3 H(20)=7 H(84)=6冲突，H1=(6+1)%19=7 冲突，H2-(6+2)%19-8 H(27)=1冲突，H1-(1+1)%19-2 冲突，H2=(1+2)%19=3 冲突，H3-(1+3)%19=4 H(68)-3冲突，HI-(3+1)%19=4 冲突，H2-(3+2)%19=5 H(11)-11 H(10)=10冲突，H1■(10+1)%19=11 冲突，H2=(10+2)%19=12 H(77)=12冲突，H1-(12+1)%19-13 (6)两分查找判定树如下：AS1=(1+22+34+4“4)11=3 0 判定树推导过程： 第2项共4页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第2页 共4页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （4）二叉排序树如下图： 中序：12 22 31 40 46 65 78 88 后序：12 31 40 22 65 88 78 46 （5） 序列：19，1，23，14，55，20，84，27，68，11，10，77 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 14 55 27 68 19 20 84 23 11 10 77 H（key）=key%13 m=19 H（19）= 6 H（1）= 1 H（23）= 10 H（14）= 1 冲突，H1=（1+1）%19 = 2 H（55）= 3 H（20）= 7 H（84）= 6 冲突，H1=（6+1）%19 = 7 冲突，H2=（6+2）%19 = 8 H（27）= 1 冲突，H1=（1+1）%19 = 2 冲突，H2=（1+2）%19 = 3 冲突，H3=（1+3）%19 = 4 H（68）= 3 冲突，H1=（3+1）%19 = 4 冲突，H2=（3+2）%19 = 5 H（11）= 11 H（10）= 10 冲突，H1=（10+1）%19 = 11 冲突，H2=（10+2）%19 = 12 H（77）= 12 冲突，H1=（12+1）%19 = 13 （6）两分查找判定树如下：ASL=（1+2*2+3*4+4*4）/11=3 判定树推导过程：
河南广厂播电现大学现数中心 5=(0+10)2 2-04)2 8-(6+10)2 2 8 3-(3412 6(67)2 0-(0+1)2 949+10)2 0 3 9 10 (7)参考算法： #ndude <stdio.h≥ define n 50 typedefint keytype /pedefsruc间 keytype key. Inodeyype: typedef nodetype seqlisin seqlista: main0 intm: keytype k fcr-0时cn114+) a叩keyt 性成遍增序列1-n cr0-0j=-14) 喻曲查找的序列 prinm(d-%d".alkeyk prind(n): print(nputk:i方 输入要直我的值k scant(%d"&k): int low-0.high=n-1.mid. while (lowe=high) mid=(low+highy2. if (amid]key=-k制 print['search p0ss0nis%dnmd水所半在找成功井输出k的位置 if (almid]key<k) highmmid.1: cise low=mid-1: printf(no se功.n门所半查找失败 第3风共项 版权所有河南电大现教中心范额，好箱5@m加cm
河南广播电视大学现教中心 第3页 共4页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （7）参考算法： #include #define n 50 typedef int keytype; typedef struct{ keytype key; }nodetype; typedef nodetype seqlist[n]; seqlist a; main() { int m,i,j; keytype k; for(i=0;i<=n-1;i++) a[i].key=i; //生成递增序列 1~n for(i=0;i<=n-1;i++) //输出查找的序列 printf("%d--%d ",i,a[i].key); printf("\n"); printf("input k:\n"); //输入要查找的值 k scanf("%d",&k); int low=0,high=n-1,mid; while (low<=high) { mid=(low+high)/2; if (a[mid].key==k) printf("search position is:%d\n",mid); //折半查找成功并输出 k 的位置 if (a[mid].key<k) high=mid+1; else low=mid-1; } printf("no search.\n"); //折半查找失败
河南广播电视大学现黄中心 (8)哈希函数是记录的关键字值与该记素的存储迪址之间所构造的对应关系。 哈希表是用来存政查找表中记录序列的表，每个记录的存销位置是以该记录的美健字 为自变量，由相应哈希函数计算所阁到的函数值。 同义词是具有相同函数值的两个关键字 冲突是因为关键字不月，即ky1k2,但H(ky1)=H(k2)的现象。 第4页共4页 版权所有河南电大观教中心范隔，船箱5@up恤团
河南广播电视大学现教中心 第4页 共4页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn } （8）哈希函数是记录的关键字值与该记录的存储地址之间所构造的对应关系。 哈希表是用来存放查找表中记录序列的表，每个记录的存储位置是以该记录的关键字 为自变量，由相应哈希函数计算所得到的函数值。 同义词是具有相同函数值的两个关键字。 冲突是因为关键字不同，即 key1key2，但 H（key1）= H（key2）的现象