违法和不良信息举报 联系客服
免费注册 登录

线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不

题目
填空题
线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索（）次。设有100个结点，用二分法查找时，最大比较次数是（）。
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

设有一个已按各元素的值排好序的顺序表(长度大于2)，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是s和b，在查找不成功情况下s和b的关系是

A．s=b

B．s＞b

C．s＜b

D．s＞=b


正确答案：B
解析：顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较，若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。二分查找是一种效率较高的查找方法，要求线性表是有序表。基本思想是：首先将待查的K值和有序表R [0]到R[n-1]的中间位置mid上的结点的关键字进行比较，若相等，则查找完成；否则，若R[mid]．key＞K，则说明待查找的结点只可能在左子表R[0]到R[mid-1]中，我们只要在左子表中继续进行折半查找，若R[mid]．keyK，则说明待查找的结点只可能在右子表R[mid+1]到R[n-1]中，我们只要在右子表中继续进行折半查找。这样，经过一次关键字比较就缩小一半的查找空间。对顺序查找而言，如果查找失败，比较次数为n次；二分查找而言，如果查找失败，比较次数为log 2(n+1)次。

第2题：

设一线性表中有a1，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较______次。


正确答案：9
9 解析：因为29=512，故最多需要比较9次。

第3题：

设有一个已按各元素的值排好序的顺序表(长度大于2) ，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是，和b，在查找不成功的情况下s和b的关系是

A．s=b

B．s＞b

C．s＜b

D．s＞=b


正确答案：B
解析：顺序查找的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的节点关键宇和给定值k相比较，若当前扫描到的节点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的节点，则查找失败。二分查找是一种效率较高的查找方法，要求线性表是有序表。基本思想是：首先将待查的K值和有序表R[0]到R[n-1]的中间位置mid上的节点的关键字进行比较，若相等，则查找完成；否则，若R[mid].key＞K，则说明待查找的节点只可能在左子表R[0]到R[mid-1) 中，我们只要在左子表中继续进行折半查找，若R[mid].keyK，则说明待查找的节点只可能在右子表R[mid+1) 到R[n-1) 中，我们只要在右子表中继续进行折半查找。这样，经过一次关键字比较就缩小一半的查找空间。对顺序查找而言，如果查找失败，比较次数为n次；对二分查找而言，如果查找失败，比较次数为log2(n+1) 次。

第4题：

线性表L=(a1,a2,a3,…ai,…an),下列说法正确的是( )。A.每个元素都有一个直接前件和直接后件SXB

线性表L＝(a1，a2，a3，…ai，…an)，下列说法正确的是（ ）。

A.每个元素都有一个直接前件和直接后件

B.线性表中至少要有一个元素

C.表中诸元素的排列顺序必须是由小到大或由大到小

D.除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前继和直接后继


正确答案：D
线性表可以为空表；第一个元素没有直接前驱，最后一个元素没有直接后继；线性表的定义中，元素的排列并没有规定大小顺序。

第5题：

设一线性表中有al，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较【 】次。


正确答案：9
9 解析：因为29=512，故最多需要比较9次。

第6题：

有一排好序的线性表，长度大于2，对给定的K值，分别用顺序查找和二分查找一个与K值相等的元素，比较的次数分别是X和Y。在查找不成功的情况下，正确的X和Y的关系是

A．X，Y

B．X＜Y

C．X=Y

D．与K大小有关


正确答案：D
解析：顺序查找没有要求线性表按关键字值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，k值大小都决定了性表的位置。

第7题：

（数据结构）设线性表（a1,a2,a3,...,a500)中所有元素的值由小到大排列，对一个给定的值K，用二分法查找表中与K相等的元素，在查找不成功的情况下，至多需要比较 次。

A、8

B、9

C、10

D、11


正确答案：D
          

第8题：

若在线性表中采用折半查找法查找元素，该线性表应该()

A.元素按值有序

B.构采用顺序存储结

C.元素按值有序且采用顺序存储结构

D.元素按值有序且采用链式存储结构


正确答案：C

第9题：

设有一个已按各元素的值排好序的线性表，长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和b，在查找不成功的情况下，正确的s和b的数量关系是

A．总有s＞b

B．总有s＜b

C．总有s=b

D．与k值大小有关


正确答案：D
解析：第一步，理解题意，抓住一个关键词“排好序的线性表”，对解决此题帮助甚大。第二步，着手分析，因为顺序查找并没有要求逻辑次序，即没有要求将线性按关键码排好序。而本题中恰恰是排好序的线性表，所以当顺序查找失败时，不必遍历全表，而仅是其大于或小于某个值时确定查找是否结束，这也是解题的关键。再分析一下二分查找，进行的前提即为排好序，每经过一次比较将查找范围缩小一半。第三步分析s和b的关系，待查值k的大小决定了其在表中的前后位置，而位置的这种变化直接使得顺序查找次数的大小变化，二分查找亦如此。故s和b大小关系是不确定的。

第10题：

下列数据结构中,能用二分法进行查找的是( )。A.顺序存储的有序线性表B.线性链表

下列数据结构中，能用二分法进行查找的是( )。

A.顺序存储的有序线性表

B.线性链表

C.二叉链表

D.有序线性链表


正确答案：A
二分查找只适用于顺序存储的有序表。此处所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)的。选项A)正确。

更多相关问题
相关内容