《c语言数据结构》第8章查找自测卷

《《c语言数据结构》第8章查找自测卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、找长度为巡。解：显然，平均查找长度=0(log2n)<5次(2‘)。但具体是多少次，则不应当按照公式=—log2(n+l)来计算(即(21xl0g221)/20=4.6次并不正确！)。因为这是在假设nn=2ra-l的情况下推导出来的公式。应当用穷举法罗列：全部元素的查找次数为=(1+2x2+4x3+8x4+5x5)=74;ASL=74/20=3.7!!!4.【计研题2000］折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素28,6,12,20比较大小。5•在各种查找方

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

4、n+1)—1(A)2.【计研题2001］折半査找有序表(4,6,1(),12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中比较大小，査找结果是失败。A.20,70,30,50B.30,88,70,50C・20,50D・30,88,50(C)3.【计研题2001】对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。A.3B・4C・5D・6（A）4.链表适用于查找A・顺序B・二分法C.顺序，也能二分法D.随机（C）5.折半搜索与二叉搜索树的时间性能A.相同B.完全不同C.有时不相同D.数量

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

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

7、：A：①顺序存储线性表②非顺序存储非线性表③顺序存储非线性表④非顺序存储线性表B：①不需要移动结点，不需改变结点指针②不需要移动结点，只需改变结点指针③只需移动结点，不需改变结点指针④既需移动结点，又需改变结点指针C：①顺序查找②循环查找③条件查找④二分法查找D：①顺序查找②随机查找③二分法查找④分块查找E：①效率较低的线性查找②效率较低的非线性查找③效率较高的非线性查找④效率较高的线性查找答案：A=@B=②C=@D=©E=38.【97程P18】从供选择的答案中，选出应填入下面叙述二内的最确切的解答，把相应编号写在答卷的对应栏内。在

8、二叉排序树中,每个结点的关键码值A，_B_一棵二叉排序，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称作最佳二叉排序，最佳二叉排序树在结构上的特点是_C。供选择的答案A：①比左子树所有