首页 › 题库 › GESP编程能力等级认证 › 5.1 二分查找

GESP-Python五级 题库

共 7 道题 · 按题型筛选,点「查看答案」核对解析
章节 5.1 二分查找 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

下面的python代码实现了二分查找算法,在数组 arr 找到目标元素 target 的位置,则横线上能填写的最佳代码是( )。

def binary_search(arr, left, right, target):
	while left <= right:
		_________________________

		if arr[mid] == target:
			return mid
		elif arr[mid] < target:
			left = mid + 1
		else:
			right = mid - 1
	return -1
A
mid = left + (right - left) // 2
B
mid = left;
C
mid = (left + right) // 2 + 1;
D
mid = right;
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

旋转数组是一种常见的数据结构问题,通常是指一个有序数组经过旋转后,使得所有元素逆序排列。整数数组 nums 按升序排列,数组中的值互不相同。在预先未知的某个下标 k(0 <= k < nums.length)上进行了旋转,使数组变为 [nums[k], nums[k + 1],…, nums[n - 1], nums[0], nums[1],…, nums[k - 1]](下标从 0 开始计数)。

现在给定旋转后的数组 nums 和一个整数 target,如果 nums 中存在这个目标值 target,则返回它的下标,否则返回-1。

下面程序中()处应填入的程序是:例如,给定一个数组 [4,5,6,7,0,1,2],它可能经过旋转变为 [0,1,2,4,5,6,7]。二分查找算法搜索旋转排序数组的程序,下面横线中,应填入的一行或多行代码是( )

def search(nums, target):
	left, right = 0, len(nums) - 1
	
	while left <= right:
		mid = (left + right) // 2
		if nums[mid] == target:
			return True
			
		if nums[mid] > nums[right]:
			if nums[mid] > target or nums[left] <= target:
				right = mid - 1
			else:
				left = mid + 1
				
		elif nums[mid] < nums[right]:
			_______________________
		else:
			right -= 1
			
	return False
A
if nums[mid] < target or nums[right] >= target:
	lleft = mid - 1
else:
	lright = mid + 1
B
if nums[mid-1] < target and nums[right+1] >= target:
	left = mid + 1
else:
	right = mid - 1
C
if nums[mid] < target or nums[right] >= target:
	lleft = mid
else:
	lright = mid
D
if nums[mid] < target and nums[right] >= target:
	lleft = mid + 1
else:
	lright = mid - 1
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

下列程序中,使用了二分查找算法,横线处应该填写的是()。

def search(arr, x):
	low = 0
	high = len(arr) - 1
	while low <= high:
		__________________
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			high = mid - 1
		else:
			low = mid + 1
	return -1


A
mid = (low - high) // 2
B
mid = (low + high) // 2
C
mid = (low + high) / 2
D
mid = (low - high) / 2
答案与解析
正确答案:B

首先排除C和D,应该是要整除才对,mid应该要取low和high的中间位置,所以应该是(low+high)//2。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

下面Python代码用于有序 list 的二分查找,有关说法错误的是(   )。

A

代码采用二分法实现有序list的查找

B

代码采用分治算法实现有序list的查找

C

代码采用递归方式实现有序list的查找

D

代码采用动态规划算法实现有序list的查找

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
5 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

二分查找仅适用于有序数据。若输入数据无序,当仅进行一次查找时,为了使用二分而排序通常不划算。()

A
对
B
错
答案与解析
正确答案:对
排序复杂度O(nlogn),单次顺序查找仅O(n),数据量大时排序开销更大。
题目详情
6 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

二分查找依赖数据的有序性,通过循环逐步缩减一半搜索区间来进行查找,且仅适用于数组或基于数组实现的数据结构。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 5.1 二分查找

二分查找适用于对无序数组和有序数组的查找。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情