一、单选题
1、在8位二进制补码中，10101011表示的数是十进制下的（ ）。
A 43
B -85
C -43
D -84
2、计算机存储数据的基本单位是（ ）。
A、 bit
B、
Byte
C、
GB
D、
KB
3、下列协议中与电子邮件无关的是（ ）。
A、
POP3
B、
SMTP
C、 WTO
D、
IMAP
4、分辨率为800x600、16位色的位图，存储图像信息所需的空间为（ ）。
A 937.5KB
B 4218.75KB
C 4320KB
D 2880KB
5、计算机应用的最早领域是（ ）。
A 数值计算
B 人工智能
C 机器人
D 过程控制
6、下列不属于面向对象程序设计语言的是（ ）。
A C
B C++
C Java
D C#
7、NOI的中文意思是（ ）。
A、
中国信息学联赛
B、 全国青少年信息学奥林匹克竞赛
C、
中国青少年信息学奥林匹克竞赛
D、
中国计算机协会
8、2017年10月1日是星期日，1999年10月1日是（ ）。
A 星期三
B 星期日
C 星期五
D、
星期二
9、甲、乙、丙三位同学选修课程， 从4门课程中， 甲选修2门， 乙、丙各选修3门，则不同的选修方案共有（ ）种。
A 36
B 48
C 96
D 192
10、设G是有n个结点、m条边（n≤m）的连通图，必须删去G的（ ）条边，才能使得G变成一棵树。
A m – n + 1
B m - n
C m + n + 1
D n – m + 1
11、对于给定的序列{ak}，我们把 (i, j) 称为逆序对当且仅当i<j且ai>aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为（ ）个。
A 4
B 5
C 6
D 7
12、表达式 a * (b + c) * d 的后缀形式是（ ）。
A a bcd * + *
B a bc + * d *
C a * bc + * d
D b + c * a * d
13、向一个栈顶指针为hs 的链式栈中插入一个指针 s 指向的结点时，应执行（ ）。
A hs->next = s;
B s->next = hs; hs = s;
C s->next = hs->next; hs->next = s;
D s->next = hs; hs = hs->next;
14、若串S=“copyright”，其子串的个数是（ ）。
A 72
B 45
C 46
D 36
15、十进制小数13.375对应的二进制数是（ ）。
A 1101.011
B 1011.011
C 1101.101
D 1010.01
16、对于入栈顺序为 a, b,c, d,e, f, g 的序列， 下列（ ）不可能是合法的出栈序列。
A a, b, c, d, e,f, g
B a,d, c, b, e,g, f
C a,d, b, c, g,f, e
D g,f, e,d, c, b, a
17、设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序 的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做 ( ) 次比较。
A n2
B n log n
C 2n
D 2n-1
18、从（ ）年开始，NOIP竞赛将不再支持 Pascal 语言。
A 2020
B 2021
C 2022
D 2023
19、一家四口人，至少两个人生日属于同一月份的概率是（ ） （假定每个人生日属于每个月份的概率相同且不同人之间相互独立） 。
A 1/12
B 1/144
C 41/96
D 3/4
20、以下和计算机领域密切相关的奖项是（ ）。
A 奥斯卡奖
B 图灵奖
C 诺贝尔奖
D 普利策奖
二、简答题
21、一个人站在坐标（0,0）处，面朝x轴正方向。
第一轮， 他向前走1单位距离，然后右转；第二轮，他向前走2单位距离，然后右转；第三轮，他向前走3单位距离，然后右转……他一直这么走下去。请问第2017轮后，他的坐标是：( , ) 。（请在答题纸上用逗号隔开两空答案）
参考答案：4034,0
22、如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由1变0，或由0变1）。现在要使得所有的格子中的数字都变为0，至少需要 次操作。
参考答案：至少需要6次操作。
23、
#include <iostream>
using namespace std;
int main() {
int t[256];
string s;
int i;
cin >> s;
for (i = 0; i < 256; i++)
t[i] = 0;
for (i = 0; i < s.length(); i++)
t[s[i]]++;
for (i = 0; i < s.length(); i++)
if (t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}
输入： xyzxyw
输出：
参考答案：输出：x
24、
#include <iostream>
using namespace std;
int g(int m, int n, int x) {
int ans = 0;
int i;
if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main() {
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}
输入： 7 3
输出：
参考答案：输入：7 3输出：35
25、
#include <iostream>
using namespace std;
int main() {
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for (i = 0; i < 200; i++)
b[i] = 0;
for (i = 1; i <= n; i++) {
a[i] = ch[i - 1] - '0';
b[i] = b[i - 1] + a[i];
}
res = b[n];
t = 0;
for (i = n; i > 0; i--) {
if (a[i] == 0)
t++;
if (b[i - 1] + t < res)
res = b[i - 1] + t;
}
cout << res << endl;
return 0;
}
输入： 1001101011001101101011110001
输出：
参考答案：输入为 "1001101011001101101011110001"，程序首先读取输入的字符串，并将其长度存储在变量 n 中。然后，程序初始化一个数组 b，将所有元素设置为0。接下来，程序遍历字符串中的每个字符，将其转换为整数并存储在数组 a 中，同时更新数组 b 的元素，其中 b[i] = b[i-1] + a[i]。然后，程序找到数组 b 的最后一个元素，将其存储在变量 res 中。接着，程序从 n 开始向前遍历数组 a 和 b，同时计算以当前位置为结尾的最长前缀0的个数 t。如果 b[i-1] + t 小于 res，则更新 res 的值。最后，程序输出 res 的值。对于输入 "1001101011001101101011110001"，程序会找到最长的前缀0的个数，即 "10011010110011011010" 前面有 10 个 0，因此输出结果为 10。
26、
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while (cnt != 2) {
cnt = 0;
x = x + dx;
y = y + dy;
if (x == 1 || x == n) {
++cnt;
dx = -dx;
}
if (y == 1 || y == m) {
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0;
}
输入 1：4 3
输出 1： （3 分）
输入 2：2017 1014
输出 2： （5 分）
参考答案：该题目没有给出具体的答案，因为它是一个编程题目，需要运行程序并输出结果。
三、实操题
27、（快速幂）请完善下面的程序，该程序使用分治法求xp mod m的值。（第一空 2 分，其余 3 分）
输入：三个不超过10000的正整数x，p，m。
输出：xp mod m的值。
提示：若p为偶数，xp=(x2)p/2；若p为奇数，xp=x*(x2)(p-1)/2。
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main() {
cin >> x >> p >> m;
result = (1) ;
while ( (2) ) {
if (p % 2 == 1)
result = (3) ;
p /= 2;
x = (4) ;
}
cout << (5) << endl;
return 0;
}
参考答案：1. `1`2. `p > 0`3. `x * result % m`4. `pow(x, p / 2, m)`5. `result`
28、（切割绳子）有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。（第一、二空2.5分，其余3分）
输入：第一行是一个不超过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];
(1) ;
}
cin >> m;
if ( (2) ) {
cout << "Failed" << endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while ( (3) ) {
mid = (4) ;
count = 0;
for (i = 0; i < n; i++)
(5) ;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
参考答案：1. 在(1)处，应填写`cin >> len[i];`，用于从输入中读取每条绳子的长度。2. 在(2)处，应填写`if (n == 0 || m == 0) `，用于检查输入的有效性。如果n或m为0，则无法切割绳子，输出"Failed"。3. 在(3)处，应填写`lbound <= ubound`，用于确保二分查找的循环条件正确。4. 在(4)处，应填写`(lbound + ubound) / 2`，用于计算二分查找的中间值。5. 在(5)处，应填写`if (len[i] >= mid) count++;`，用于统计长度大于等于中间值的绳子数量。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
