数据结构(C语言描述)-第八章

数据结构(C语言描述)-第八章习题8.1选择题1、顺序查找法适合于存储结构为(B)的线性表。A、散列存储B、顺序存储或链接存储C、压缩存储D、索引存储2、对线性表进行折半查找时，要求线性表必须(C)。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排序D、以链接方式存储，且结点按关键字有序排序3、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为(C)。A、nB、n/2C、(n+1)/2D、(n-1)/24、采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为(D)。A、o(n2)B、o(nlog2n)C、o(n)D、o(log2n)5、有一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，100），当折半查找给定值为82的元素时，（C）次比较后查找成功。A、1B、2C、4D、86、设散列表长m=14，散列函数H（key）=key%11。表中已有4个结点：addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7，其余地址为空，如用二次探测再散列解决冲突，关键字为49的结点的散列地址是（D）。A、8B、3C、5D、97、如图所示的4棵二叉树，（B）是平衡二叉树。ABCDSHAPE8、具有五层结点的二叉平衡树至少有()个结点。A、10B、12C、15D、179、从二叉排序树中查找一个元素时，其时间复杂度大致为(B)。A、o(n2)B、o(log2n)C、o(n)D、o(1)10、在散列函数H(key)=key%p中，p应取(A)。A、素数B、整数C、任意数D、小数8.2填空题数据结构(C语言描述)-第八章全文共4页，当前为第1页。1、假定在有序表R[0…9]上进行二分查找，则比较一次查找成功的结点数为（1），比较两次查找成功的结点数为（2），比较三次查找成功的结点数为（4），平均查找长度为（log2n）。数据结构(C语言描述)-第八章全文共4页，当前为第1页。2、在分块查找中，首先查找（索引表），然后再查找相应的（主表），整个分块查找的平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的（和）。3、在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就（越大），当装填因子的值越小，存取元素时发生冲突的可能性就（越小）。4、用二分查找方法进行查找时，要求数据文件应为（顺序），且限于（有序），要进行顺序查找，则线性表的存储方式为（顺序或链式存储）。5、假定查找共有12个元素的有序表的概率相等，则进行顺序查找的平均查找长度为（13/2），进行二分查找时的平均查找长度为（37/12）。8.3应用题1、假定查找有序表A[25]中每个元素的概率相等，试分别求出顺序、折半和分块（假定被分为5块，每块5个元素）查找每个元素时的平均查找长度。解：顺序查找ASL=（n+1）/2=13折半查找ASL=（1*1+2*2+4*3+8*4+9*5+1*6）/25=100/25=4分块查找ASL=（（2+3+4+5+6）+（3+4+5+6+7）+（4+5+6+7+8）+（5+6+7+8+9+）+（6+7+8+9+10））/25=150/25=62、设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用散列函数H(key)=key%13，采用开放定址法的二次探测再散列方法解决冲突，试在0到18的形式列地址空间中对该关键字序列构造散列表。解：计算散列地址：H(19)=19%13=6H(01)=01%13=1H(23)=23%13=10H(14)=14%13=1(冲突)H1=(1+12)%19=2H(55)=55%13=3H(20)=20%13=7H(84)=84%13=6(冲突)H1=(6+12)%19=7（冲突）H2=(6-12)%19=5H(27)=27%13=1（冲突）H1=(1+12)%19=2（冲突）H2=(1-12)%19=0H(68)=68%13=3（冲突）H1=(3+12)%19=4H(11)=11%13=11H(10)=10%13=10（冲突）H1=(10+12)%19=11（冲突）H2=(10-12)%19=9H(77)=77%13=12数据结构(C语言描述)-第八章全文共4页，当前为第2页。数据结构(C语言描述)-第八章全文共4页，当前为第2页。012345678910-1112131415161718270114556884192010231177ASL=（7*1+2*2+3*3）/12=20/12=5/33、假定一个待散列存储的线性表为（32，75，29，63，48，94，25，36，18，70），散列地址空间为HT[13],若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每个元素的散列地址，画出最后得到的散列表，并求出平均查找长度。解：散列地址为：H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3（冲突）H1=(3+1)%13=4H(25)=25%13=12H(36)=36%13=10（冲突）H1=(10+1)%13=11（冲突）H2=(10+2)%13=12（冲突）H3=(10+3)%13=0H(18)=18%13=5H(70)=70%13=5（冲突）H1=(5+1)%13=6（冲突）H2=(5+2)%13=7散列表为：012345678910111236299418327048756325ASL=（7*1+1*2+1*3+1*4）/10=16/10=1.64、假定一个待散列存储的线性表为（32，75，29，63，48，94，25，36，18，70），散列地址空间为HT[11],若采用除留余数法构造散列函数和链地址法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。解：散列地址为：H(32)=32%13=6H(75)=75%13=10H(29)=29%13=3H(63)=63%13=11H(48)=48%13=9H(94)=94%13=3H(25)=25%13=12H(36)=36%13=10H(18)=18%13=5H(70)=70%13=5散列表为：图没有画ASL=（1*7+2*3）/10=1.38.4算法题编写折半查找的非递归算法。（作为上机实践题目）intBinSearch(ListSqL,intlow,inthigh,keytypeK){while(low<=high){intmid=(low+high)/2;//求出待查区间中间点元素下标if(K==L.e[mid].key)returnmid;//查找成功返回元素下标elseif(K<L.e[mid].key)high=mid-1;//在左子表上继续查找else数据结构(C语言描述)-第八章全文共4页，当前为第3页。数据结构(C语言描述)-第八章全文共4页，当前为第3页。}return-1;//查找失败返回-1}假设查找表以单链表的形式存储，试写出对此单链表进行顺序查找时的实现算法。（作为上机实践题目）structElemtype//数据元素的数据类型定义{keytypekey;//关键字项┆}；structLnode{Elemtypedata;structLnode*next;};intseqsearch(Lnode*L,keytypes){Lnode*p=L->