一、单选题 2题（每题 10分，共 20分）

第 1 题

1.使用二分算法，在1~500（包含1和500）之间猜数字77，按照向下取整的原则来找中间值，依次取出的中间值是？( ）。

{{ select(1) }}

• 250, 125, 187, 218, 77
• 251, 125, 63, 94, 77
• 250, 125, 62, 93, 77
• 125, 63, 94, 77

---

第 2 题

2.观察一个升序的数字序列，左边界L，右边界R，第一次二分处理时中间值mid为5，要找的数字为8，L、R的值要如何变化（ ）。

{{ select(2) }}

• R=mid+1
• R=mid-1
• L=mid+1
• L=mid-1

---

二、代码选择 2题（每空 10分，共 80分）

1.字典找字

【问题描述】 现有一字典，查找字典15到45页中，某一页的页码，用二分法快速翻至所需要页码，需要翻多少次？ （中间值 mid = (最大值+最小值)/2） 【输入格式】 字典中某一页的页码n。（15≤n≤45） 【输出格式】 一个整数，表示查找的次数。 【输入样例】 18 【输出样例】 3

#include<iostream>
using namespace std;
int main(){
	int n,L=15,R=45,mid,s=0;//L最小 R最大 mid中间
	cin>>n;
	//中间值与数字炸弹进行比较
	while(__①___){ //多了一个可退出循环的条件,当范围不在L与R之间时循环终止
		s++;//统计查找次数 
		mid=__②__; //取中间值
		if(__③__){
			break;//找到结果退出循环
		} else if(mid>n) {  //比数字炸弹大
			__④__; //更新最大值
		} else {   //比数字炸弹小
			__⑤__; //更新最小值
		}
	}
	cout<<s;//输出查找次数 
	return 0;
} 

第 3 题 ①处应填写{{ select(3) }}

• L>=R
• L==R
• L<R
• L<=R

---

第 4 题 ②处应填写{{ select(4) }}

• (L-R)/2
• (L+R)
• (L+R)/2
• (R-L)/2

---

第 5 题 ③处应填写{{ select(5) }}

• mid==n
• mid+1==n
• mid==n-1
• mid>=n

---

第 6 题 ④处应填写{{ select(6) }}

• R=mid-1
• R=mid+1
• L=mid-1
• L=mid+1

---

第 7 题 ⑤处应填写{{ select(7) }}

• R=mid-1
• R=mid+1
• L=mid-1
• L=mid+1

---

2.贪心的小乐

【题目描述】 兔子采集队工作回来，把采集回来的胡萝卜分成 4 堆,小乐只能从每堆里拿走 1 根胡萝卜。 小乐的目标是拿走总重量最重的 4 根胡萝卜。假如我们知道每根胡萝卜的重量，爱学编程的你来帮帮小乐吧。 【输入描述】 4堆胡萝卜，共4行：每行第一个正整数n，是一堆胡萝卜的数量（≤1000）。后面n个正整数，是每堆胡萝卜中每个胡萝卜的重量（1≤单个胡萝卜重≤100）。 【输出描述】 请问拿走的4根胡萝卜总重量最大是多少？ 【样例输入】 5 4 3 2 1 6 4 3 2 1 4 6 9 3 2 4 6 3 3 11 2 1 【样例输出】 30

#include<bits/stdc++.h>
using namespace std;
int main(){
	int sum=0;
	for(int i=1;i<=4;i++){
		int n;//每堆数量 
		cin>>n;
		int maxx=0;//每堆最大值 
		for(int j=1;j<=n;j++){
			int t;//当前堆里的每一个重量 
			cin>>t; 
			if(__①___) maxx=t; //求每堆最大值 
		}
		__②__;//累加每堆最大值 
	}
	cout<<__③__; 
	return 0;
}

第 8 题 ①处应填写{{ select(8) }}

• t>=maxx
• t>maxx
• t<maxx
• t<=maxx

---

第 9 题 ②处应填写{{ select(9) }}

• maxx++
• maxx+=sum
• sum++
• sum+=maxx

---

第 10 题 ③处应填写{{ select(10) }}

• sum
• maxx
• t
• n

---