数据结构单元测验6(包含答案与讲解)

《数据结构单元测验6(包含答案与讲解)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》小测验六（2008-2009学年第一学期）一．判断题(用×表示错，用√表示对)（每题1分，共23分）1.（×）2.（√）3.（√）4.（√）5.（√）6.（√）7.（√）8.（×）9.（×）10.（√）11.（×）12.（×）13.（√）14.（×）15.（√）16.(√)17.(√)18.(√)19.(×)20.(√)21.(×)22.(√)23.(√)二．选择题（每项选择0.5分，共24分）123456-A6-B6-C6-D6-EBACAC④⑤③③④7-A7-B7-C7-D7-E8-A8-B8-C9-A9-B9-C9-D④②④①③①②②④①③④10-A10-B10-C10

2、-D10-E⑦④⑥②⑥11121314151617181920212223242526CCDBDCDCDBCBCBBC27-A26-B26-C26-D26-E③①④②⑦三、填空题（每空1分，共33分）第4页(共3页)1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成

3、功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为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比较大小。5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法

4、是散列查找。6.散列法存储的基本思想是由关键字的值决定数据的存储地址。7.有一个表长为m的散列表，初始状态为空，现将n（n

5、则选用选择。11.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。12.对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2)。若对其进行快速排序，在最坏的情况下所需要的时间是O(n2)。13.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间是O(n)。14．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。第4页(共3页)15.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是HCQ

6、PAMSRDFXY；初始步长为4的希尔（shell）排序一趟的结果是PACSQHFXRDMY；二路归并排序一趟扫描的结果是HQCYAPMSDRFX；快速排序一趟扫描的结果是FHCDPAMQRSYX；堆排序初始建堆的结果是ADCRFQMSYPHX。16.在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法；若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法；若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。四．算法应用题（共10分）1.(1)先画出判定

7、树如下（注：mid=ë(1+12)/2û=6）：30563374287424547295(2)求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；但最后一层未满，不能用8×4，只能用5×4=20次，所以ASL＝1/12（17＋20）＝37/12≈3.082.解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,首先要与