搜索
第九章查找一、单项选择题1、顺序查找法适合于存储结构为（B）的线性表。A．散列存储B.顺序存储或链接存储C.压缩存储D.索引存储2、采用折半查找方法查找长度为n的线性表时，每个元素的平均查找长度为（D）。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)3、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C）。A.nB.n/2C.(n+1)/2D.(n-1)/24、10个元素的有序表，等概率条件下折半查找成功的平均查找长度是（A）。A．2.9B.3C.4.5D.5.05、设哈希表长m=14,哈希函数H(key)=key%k11,表中已有4个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空如果采用二次探测再散列处理冲突，关键字为49的结点的地址是（D）。A.8B.3C.5D.9二、设有序顺序表中的元素依次为017，094，154，170，275，503，509，512，553，612，677，765，897，908。试画出对其进行折半查找时做性能分析用的判定树，并计算等概率条件下查找成功时的平均查找长度和查找不成功时的平均查找长度。解：1234567891011121314017094154170275503509512553612677765897908判定树:7315246119138101214ASL成功=(1*1+2*2+3*4+4*7)/14=45/14ASL不成功=(1*1+4*14)/15=57/15三、已知待散列存储的线性表为（25，48，32，50，68），散列用的一维地址空间为[0..6],假定选用散列函数为h(k)=k%7,若发生冲突则菜用线性探测再散列的开放定地法解决，试计算出每一元素（即关键字）的存储地址，并计算出等概率条件下的平均查找长度。三、解：h(25)=25%7=4h(48)=48%7=6h(32)=32%7=4h1=(4+1)%7=5h(50)=50%7=1h(68)=68%7=5h1=(5+1)%7=6h2=(5+2)%7=06850253248ASL=(1*3+2*1+3*1)/5=1.6