数据结构第九、十章作业答案.doc

《数据结构第九、十章作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找一、填空题1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8,其下标从小到大依次是1,3,6,8,11,13,16,

2、19______，平均查找长度为3.7。解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小

3、。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。6.散列法存储的基本思想是由关键字的值决定数据的存储地址。7.有一个表长为m的散列表，初始状态为空，现将n（n

4、、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以顺序方式存储，且结点按关键字有序排列。11在分块查找方法中，首先查找索引，然后再查找相应的块。12．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ n __次；当使用监视哨时，若查找失败，则比较关键字的次数为__n+1  。13．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_____6,9,11,12 _____。14.在有序表A[

5、1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 _15.已知二叉排序树的左右子树均不为空，则____左子树______上所有结点的值均小于它的根结点值，____右子树______上所有结点的值均大于它的根结点的值。16、中序遍历二叉排序树得到的序列是有序序列（填有序或无序）。17、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为1和3·二、单项选择题（B）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为Ａ.ＡＳＬ

6、＝ｎ;Ｂ.ＡＳＬ＝（ｎ＋１）／２;Ｃ.ＡＳＬ＝＋１;Ｄ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（A）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50（C）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A．3B．4C．5D．6（A）4.链表适用于查找A．顺序B．二分法C．顺序，也能二分法D．随机（C）5.折

7、半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量级都是O（log2n）6．散列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（D）。A．8B.9C.10D.117.当采用分快查找时，数据的组织方式为(B)A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若

8、干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同8.散列函数有一个共同的性质，即函数值应当以(D)取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？(D)A．k-1次B.k次C.k+1次D.k（k+1）/2次10、哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈