数据结构第9章自测卷.doc

《数据结构第9章自测卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章查找自测卷姓名袁忠杨班级计算机1班A题号一二三四五总分题分1027162423100得分一、填空题（每空1分，共10分）1.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。2.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索8次。设有100个结点，用二分法查找时，最大比较次数是7。3.假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找

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.在各种查找方法中，平均

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

4、）－１（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.折半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量级都是O（log2n）6．从供选择的答

5、案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。要进行线性查找，则线性表A；要进行二分查找，则线性表B；要进行散列查找，则线性表C。某顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为D，最大比较次数为E。供选择的答案：A~C：①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储④既可以以顺序方式，也可以以链表方式存储⑤必须以顺序方式存储且数据元素已按值递增或递减

6、的次序排好⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E：①25000②30000③45000④90000答案：A=④B=⑤C=③D＝③E＝④7.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。数据结构反映了数据元素之间的结构关系。链表是一种A，它对于数据元素的插入和删除B。通常查找线性表数据元素的方法有C和D两种方法，其中C是一种只适合于顺序存储结构但E的方法；而D是一种对顺序和链式存储结构均适用的方法。供选择的答案：A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线

7、性表④非顺序存储线性表B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针C：①顺序查找②循环查找③条件查找④二分法查找D：①顺序查找②随机查找③二分法查找④分块查找E：①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找答案：A＝④B＝②C＝④D＝①E＝③8.从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对应栏内。在二叉排序树中，每个结点的关键码值A，B一棵二叉排序，即可得到排序序

8、列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是C。供选择的答案A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大③比左右