计算机三级
有一排好序的线性表，长度大于2，对给定的K值，分别用顺序查找和二分查找一个与K值相等的元素，比较的次数分别是X和Y。在查找不成功的情况下，正确的X和Y的关系是A．X，YB．X＜YC．X=YD．与K大小有关
题目
有一排好序的线性表，长度大于2，对给定的K值，分别用顺序查找和二分查找一个与K值相等的元素，比较的次数分别是X和Y。在查找不成功的情况下，正确的X和Y的关系是
A．X，Y
B．X＜Y
C．X=Y
D．与K大小有关
相似问题和答案
第1题：
设有一个己按各元素的值排好序的线性表，长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k相等的元素，比较的次数分别为s和b，在查找不成功的情况下，正确的s和b的数量关系是 ______。
A．总有s=b
B．总有s＞b
C．总有s＜b
D．与k值大小有关
第2题：
有一个排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是______。
A．x＞y
B．总是x＜y
C．x＝y
D．与k值大小有关
解析：顺序查找没有要求线性表按关键词值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了线性表的位置，所以应选择D。
第3题：
有一排好序的线性表，长度大于2，对给定的k值，分别用顺序查找和二分查找查找一个与k值相等的元素，比较的次数分别为x和y。在查找不成功的情况下，正确的x和y的关系是 ______。
A．x＞y
B．总是x＜y
C．x＝y
D．与k值的大小有关
解析：顺序查找没有要求线性表按关键字值排序。本题要求对排好序的线性表进行查找，不论线性表是升序或降序，则k值大小决定了性表的位置，所以应选择D。
第4题：
设有一个已按各元素的值排好序的线性表，长度大于2，对给定的值k，分别用顺序查找法和二分查找法查找一个与k值相等的元素，比较的次数分别为s和b，在查找不成功的情况下，正确的s和b的数量关系是
A．总有s＞b
B．总有s＜b
C．总有s=b
D．与k值大小有关
解析：第一步，理解题意，抓住一个关键词“排好序的线性表”，对解决此题帮助甚大。第二步，着手分析，因为顺序查找并没有要求逻辑次序，即没有要求将线性按关键码排好序。而本题中恰恰是排好序的线性表，所以当顺序查找失败时，不必遍历全表，而仅是其大于或小于某个值时确定查找是否结束，这也是解题的关键。再分析一下二分查找，进行的前提即为排好序，每经过一次比较将查找范围缩小一半。第三步分析s和b的关系，待查值k的大小决定了其在表中的前后位置，而位置的这种变化直接使得顺序查找次数的大小变化，二分查找亦如此。故s和b大小关系是不确定的。
第5题：
设一线性表中有al，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较【 】次。
9 解析：因为29=512，故最多需要比较9次。
第6题：
（数据结构）设线性表（a1,a2,a3,...,a500)中所有元素的值由小到大排列，对一个给定的值K，用二分法查找表中与K相等的元素，在查找不成功的情况下，至多需要比较 次。
A、8
B、9
C、10
D、11
第7题：
设一线性表中有a1，a2，…，a500个元素按递增顺序排列，则用二分法查找给定值K，最多需要比较______次。
9 解析：因为29=512，故最多需要比较9次。
第8题：
设有一个已按各元素的值排好序的顺序表(长度大于2)，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是s和b，在查找不成功情况下s和b的关系是
A．s=b
B．s＞b
C．s＜b
D．s＞=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)次。
第9题：
设有一个已按各元素的值排好序的顺序表(长度大于2) ，现分别用顺序查找法和二分查找法查找与给定值k相等的元素，比较的次数分别是，和b，在查找不成功的情况下s和b的关系是
A．s=b
B．s＞b
C．s＜b
D．s＞=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) 次。