4.【NOIP2014】
01 #include
<iostream>
02 #include
<string>
03 using
namespace std;
04 const
int SIZE=100;
05 int
main() {
06 string dict[SIZE];
07 int rank[SIZE];
08 int ind[SIZE];
09 int i,
j, n, tmp;
10 cin >> n;
11 for (i = 1; i <= n; i++) {
12 rank[i] = i;
13 ind[i] = i;
14 cin >> dict[i];
15 }
16 for (i = 1; i < n; i++)
17 for (j = 1; j <= n - i; j++)
18 if (dict[ind[j]] >
dict[ind[j + 1]]) {
19 tmp = ind[j];
20 ind[j] = ind[j + 1];
21 ind[j + 1] = tmp;
22 }
23 for (i = 1; i <= n; i++)
24 rank[ind[i]] = i;
25 for (i = 1; i <= n; i++)
26 cout << rank[i] <<
" ";
27 cout << endl;
28 return 0;
29 }
判断题
（1）该程序的本质是按字典序对字符串排序。 （ ）
（2）如果输入0，没有任何输出。 （ ）
（3）如果使用c++98编译，不会出现编译错误。 （ ）
（4）如果去掉第12行，不影响程序。 （ ）
选择题
（5）输入
7
aaa
aba
bbb
aaa
aaa
ccc
aa
输出为（ ）
A. 2
5 6 3 4 7 1 B. 1 2 34 5 6 7
C. 1 7 4 3 6 5 2 D. 7 6 5 4 3 2 1
（6）这个程序使用的是什么排序（ ）
A. 插入排序 B. 希尔排序 C. 选择排序 D. 冒泡排序
2、递归
【NOIP2014】
01 #include
<iostream>
02 using
namespace std;
03 int
fun( int n, int minNum, int maxNum ) {
04 int
tot, i;
05 if
(n == 0) return 1;
06 tot
= 0;
07 for
(i=minNum; i<=maxNum; i++)
08 tot
+= fun(n-1, i+1, maxNum);
09 return
tot;
10 }
11 int
main() {
12 int
n;
13 cin
>> n;
14 cout
<< fun(n, 1, 6)
15 return
0;
16 }
判断题
（1）将第5行删除，程序编译错误。 （ ）
（2）当输入的n的绝对值在1000以内，程序不一定能正常运行。 （ ）
（3）将第4行的内容接在第2行后，程序输出与原样不同。 （ ）
（4）将第4行的内容去掉，程序将会运行错误。 （ ）
选择题
（5）fun(2, 1, 6)的值为（ ）
A. 15 B. 10 C. 6 D. 3
（6）fun(3, 1, 6)的值为（ ）
A. 20 B. 10 C. 4 D. 1
3、二分
切割绳子
有 n 条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出 m 条长度相同的绳段，求绳段的最大长度是多少。
输入：第一行是一个不超过 100 的正整数 n，第二行是 n 个不超过106的正整数，表示每条绳子的长度，第三行是一个不超过108的正整数 m。
输出：绳段的最大长度，若无法切割，输出 Failed。
#include<iostream>
using namespace
std;
int n, m, i,
lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main() {
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
____①____;
}
cin >> m;
if (____②____) {
cout << "Failed"
<< endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while (_____③___) {
mid = _____④___;
count = 0;
for (i = 0; i < n; i++)
_____⑤___;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
选择题
（1）①处应填（ ）
A. 空 B. count += len[i]
C. count++ D.
count = count *10 + len[i]
（2）②处应填（ ）
A. count == m
B.
count < m
C. count > m D.
count != m
（3）③处应填（ ）
A. count = m
B.
lbound = ubound
C. lbound < ubound D.
lbound > ubound
（4）④处应填（ ）
A. (lbound +
ubound +1) / 2 B. (lbound + ubound -1) / 2
C. (lbound - ubound +1) / 2 D.
(lbound + ubound +1)
（5）⑤处应填（ ）
A. count +=
len[i]/mid B.
count = (count + len[i])/mid
C. count += len[i]/lbound
D. count =
(count + len[i])/ubound
4、字符
【NOIP2016】读入正数
请完善下面的程序，使得程序能够读入两个 int 范围内的整数， 并将这两个整数分别输出，每行一个。（第一、五空 2.5 分，其余 3 分）
输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。
例如：
输入：
123
-789
输出：
123
-789
#include <iostream>
using namespace std;
int readint(){
int
num = 0; // 存储读取到的整数
int
negative = 0; // 负数标识
char
c; // 存储当前读取到的字符
c
= cin.get();
while
((c < '0' || c > '9') && c != '-')
c
= _____①___;
if
(c == '-')
negative
= 1;
else
_____②___;
c
= cin.get();
while
(_____③___){
_____④___;
c
= cin.get();
}
if
(negative == 1)
_____⑤___;
return
num;
}
int main()
{
int
a, b;
a
= readint();
b
= readint();
cout
<< a << endl
<< b << endl;
return
0;
}
选择题
（1）①处应填（ ）
A. c
– ‘0’ B. ‘0’ C. c+’0’ D. cin.get()
（2）②处应填（ ）
A. num=0 B. num=c-‘0’
C. num=c-‘a’ D. num=c
（3）③处应填（ ）
A. c>=’0’
&& c<=’9’ B. c>=’a’ && c<=’z’
C. c<’0’ || c>’9’ D. c != ’-’
（4）④处应填（ ）
A.
num=num+c-‘0’ B.
num=num*10+c-‘0’
C. num=num+c D.
num=num*10+c
（5）⑤处应填（ ）
A. num=-num B. num=num+num
C. num-- D. num++
【NOIP2016】
01 #include
<iostream>
02 using
namespace std;
03 int
main() {
04 int
a[6] = {1, 2, 3, 4, 5, 6};
05 int
pi = 0;
06 int
pj = 5;
07 int
t, i;
08 while
(pi < pj) {
09 t
= a[pi];
10 a[pi]
= a[pj];
11 a[pj]
= t;
12 pi++;
13 pj--;
14 }
15 for
(i = 0; i < 6; i++)
16 cout
<< a[i] << ",";
17 cout
<< endl;
18 return
0;
19 }
判断题
（1）将第8行改成pi<=pj，不影响程序结果。 （ ）
（2）程序输出六个数，逗号只出现在相邻两个数之间。 （ ）
（3）如果a={1,2,3,4,5,6}，那么输出6,5,4,3,2,1。 （ ）
选择题
（4）这个程序在（ ）
A. 将已知序列翻转 B. 求序列的逆
C. 求序列的排序 D. 将原始数列随机打乱
（5）程序的时间复杂度为（ ）
A. O(n2) B. O(n) C.
O(nlogn) D. O(n√n)
（6）如果a={6,5,4,3,2,1}，那么输出（ ）
A. 6,5,4,3,2,1 B. 6 5 4 3 2 1 C. 1 2 3 4 5 6 D. 1,2,3,4,5,6