单项选择
（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
第 1 题 在内存储器中每个存储单元都被赋予一个唯一的序号，称为（ ）。
A. 地址
B. 序号
C. 下标
D. 编号
【解析】基础概念。
【答案】A。
第 2 题 编译器的主要功能是（ ）。
A. 将源程序翻译成机器指令代码
B. 将源程序重新组合
C. 将低级语言翻译成高级语言
D. 将一种高级语言翻译成另一种高级语言
【解析】计算机只能识别二进制机器码，其他编译类语言都要经过编译器转化为机器码再交给计算机来执行。
【答案】A。
第 3 题 设 x=true, y=true, z=false，以下逻辑运算表达式值为真的是（ ）。
A. (y∨z)∧x∧z
B. x∧(z∨y) ∧z
C. (x∧y) ∧z
D. (x∧y)∨(z∨x)
【解析】离散数学基础联结词。
【答案】D。
第 4 题 现有一张分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这张图像，需要多大的存储空间？（ ）。
A. 16MB
B. 4MB
C. 8MB
D. 2MB
[解析]
【答案】B。
第 5 题 冒泡排序算法的伪代码如下：
输入：数组L, n ≥ k。输出：按非递减顺序排序的 L。
算法 BubbleSort：
FLAG ← n //标记被交换的最后元素位置
while FLAG > 1 do
k ← FLAG -1
FLAG ← 1
for j=1 to k do
if L(j) > L(j+1) then do
L(j) ? L(j+1)
FLAG ← j
对 n 个数用以上冒泡排序算法进行排序，最少需要比较多少次?（ ）。
A.
B. n-2
C. n-1
D. n
【解析】先选定一个元素，让其它 n-1 个元素与其比较，如果没有发生变量交换，则证明当前序列是有序的。
【答案】C。
第 6 题 设A是n个实数的数组，考虑下面的递归算法：
XYZ (A[1..n])
if n=1 then return A[1]
else temp ← XYZ (A[1..n-1])
if temp < A[n]
then return temp
else return A[n]
请问算法XYZ的输出是什么？（ ）。
A. A数组的平均
B. A数组的最小值
C. A数组的中值
D. A数组的最大值
【解析】返回 temp 和 A[n] 中最小的一个，temp 存储的的 A[1…n-1] 中最小的元素。
【答案】B。
第 7 题 链表不具有的特点是（ ）。
A. 可随机访问任一元素
B. 不必事先估计存储空间
C. 插入删除不需要移动元素
D. 所需空间与线性表长度成正比
【解析】随机访问是数组的特点。
【答案】A。
第 8 题 有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图。
A. 9
B. 10
C. 11
D. 12
【解析】10 个顶点构成一个线性序列。
【答案】A。
第 9 题 二进制数 1011 转换成十进制数是（ ）。
A. 11
B. 10
C. 13
D. 12
【解析】按照权值展开。
【答案】A。
第 10 题 5 个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有（ ）种不同排列方法?
A. 48
B. 36
C. 24
D. 72
【解析】捆绑法：。
【答案】A。
第 11 题 下图中所使用的数据结构是（ ）。
A. 栈
B. 队列
C. 二叉树
D. 哈希表
【解析】栈：先进后出。
【答案】A。
第 12 题 独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）。
A. 7
B. 8
C. 5
D. 6
【解析】。
【答案】D。
第 13 题 干支纪年法是中国传统的纪年方法，由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干 =（公历年份）除以10所得余数
地支 =（公历年份）除以12所得余数
例如，今年是 2020 年，2020 除以 10 余数为 0，查表为"庚”；2020 除以 12，余数为 4，查表为“子” 所以今年是庚子年。
请问 1949 年的天干地支是（ ）。
A. 己酉
B. 己亥
C. 己丑
D. 己卯
【解析】1949%10=9 1949%12=5
【答案】C。
第 14 题 10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有（ ）种不同的分配方案。
A. 84
B. 72
C. 56
D. 504
【解析】隔板法：9 个空位插入 6 个板：
【答案】A。
第 15 题 有五副不同颜色的手套（共 10 只手套，每副手套左右手各 1 只），一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有（ ）种。
A. 120
B. 180
C. 150
D. 30
【解析】。
【答案】A。
二、阅读程序
(程序输入不超过数组或字符串定义的范围；判断题正确填 √，错误填 × 。)
阅读程序1
#include
#include
using namespace std;
char encoder[26] = {'C','S','P',0};
char decoder[26];
string st;
int main() {
int k = 0;
for (int i = 0; i < 26; ++i)
if (encoder[i] != 0) ++k;
for (char x ='A'; x <= 'Z'; ++x) {
bool flag = true;
for (int i = 0; i < 26; ++i)
if (encoder[i] ==x) {
flag = false;
break;
}
if (flag) {
encoder[k]= x;
++k;
}
}
for (int i = 0; i < 26; ++i)
decoder[encoder[i]- 'A'] = i + 'A';
cin >> st;
for (int i = 0; i < st.length( ); ++i)
st[i] = decoder[st[i] -'A'];
cout << st;
return 0;
}
【程序分析】
判断题
- 输入的字符串应当只由大写字母组成，否则在访问数组时可能越界。
【解析】decoder 长度为 26，st[i] -'A' 会超过 25，越界。
【答案】T。
- 若输入的字符串不是空串，则输入的字符串与输出的字符串一定不一样。
【解析】例如输入 T，输出还是 T。
【答案】F。
- 将第 12 行的“i < 26”改为“i < 16”，程序运行结果不会改变。
【解析】k 正常结果为 3。
【答案】T。
- 将第 26 行的"i < 26”改为“i < 16”，程序运行结果不会改变。
【解析】decoder 数组不完整。
【答案】F。
单选题
- 若输出的字符串为 “ABCABCABCA”，则下列说法正确的是（ ）。
A. 输入的字符串中既有S又有P
B. 输入的字符串中既有S又有B
C. 输入的字符串中既有A又有P
D. 输入的字符串中既有A又有B
【解析】查表。
【答案】A。
- 若输出的字符串为 “CSPCSPCSPCSP”，则下列说法正确的是（ ）。
A. 输入的字符串中既有P又有K
B. 输入的字符串中既有J又有R
C. 输入的字符串中既有J又有K
D. 输入的字符串中既有P又有R
【解析】查表。
【答案】D。
阅读程序2
#include
using namespace std;
long long n, ans;
int k, len;
long long d[1000000];
int main() {
cin >> n >> k;
d[0] = 0;
len = 1;
ans = 0;
for (long long i = 0; i < n; ++i) {
++d[0];
for (int j = 0; j + 1 < len; ++j) {
if (d[j] == k) {
d[j] = 0;
d[j + 1] += 1;
++ans;
}
}
if (d[len - 1] == k) {
d[len - 1] = 0;
d[len] = 1;
++len;
++ans;
}
}
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 的正整数，k都是不超过 10000 的正整数，完成下面的判断题和单选题：
【题意分析】十进制数 n 转化为 k 进制的高精度计算方法。ans 为进位次数。
判断题
- 若 k=1，则输出 ans 时，len=n。
【解析】代入 n=1，k=1，结果 len=2。
【答案】F。
- 若 k>1，则输出 ans 时，len —定小于 n。
【解析】代入 n=1，k=2，结果 len=n=1。
【答案】F。
- 若 k>1，则输出 ans 时，—定大于n。
【解析】假定 k 进制数长度为 len，其中每一位最大值为 k-1，求和
【答案】T。
单选题
- 若输入的n等于： ，输入的 k 为 1，则输出等于（ ）。
A.
B.
C.
D.
【解析】代入计算。
【答案】D。
- 若输入的 n 等于205,891,132,094,649（即 ），输入的 k 为 3，则输出等于（ ）。
A.
B.
C.
D.
【解析】，等比数列求和。
【答案】B。
- 若输入的 n 等于 100,010,002,000,090，输入的 k 为 10，则输出等于（ ）。
A. 11,112,222,444,543
B 11,122,222,444,453
C. 11,122,222,444,543
D. 11,112,222,444,453
【解析】。
【答案】D。
阅读程序3
#include
#include
using namespace std;
int n;
int d[50][2];
int ans;
void dfs(int n, int sum) {
if (n == 1) {
ans = max(sum, ans);
return;
}
for (int i = 1; i < n; ++i) {
int a = d[i - 1][0], b = d[i - 1][1];
int x = d[i][0], y = d[i][1];
d[i - 1][0] = a + x;
d[i - 1][1] = b + y;
for (int j = i; j < n - 1; ++j)
d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
int s = a + x + abs(b - y);
dfs(n - 1, sum + s);
for (int j = n - 1; j > i; --j)
d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
d[i - 1][0] = a, d[i - 1][1] = b;
d[i][0] = x, d[i][1] = y;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> d[i][0];
for (int i = 0; i < n; ++i)
cin >> d[i][1];
ans = 0;
dfs(n, 0);
cout << ans << endl;
return 0;
}
假设输入的 n 是不超过 50 的正整数，、 都是不超过10000的正整数，完成下面的判断题和单选题：
判断题
- 若输入 n 为 0，此程序可能会死循环或发生运行错误。
【解析】代入 n=0，结果为 0。
【答案】F。
- 若输入 n 为 20，接下来的输入全为 0，则输出为 0。
【解析】代入计算，结果为 0。
【答案】T。
- 输出的数一定不小于输入的 和 的任意一个。
【解析】代入 n=1，结果为 0。
【答案】F。
单选题
- 若输入的 n 为 20，接下来的输入是 20 个 9 和 20 个 0，则输出为（ ）。
A. 1890
B. 1881
C. 1908
D. 1917
【解析】代入计算，。
【答案】B。
- 若输入的 n 为 30，接下来的输入是 30 个 0 和 30 个 5，则输出为（ ）。
A. 2000
B. 2010
C. 2030
D. 2020
【解析】代入计算，。
【答案】C。
- 若输入的 n 为 15，接下来的输入是 15 到 1，以及 15 到 1，则输出为（ ）。
A. 2440
B. 2220
C. 2240
D. 2420
【解析】代入计算，。
【答案】C。
#include
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment {
int a, b;
} A[MAXN];
void sort() // 排序
{
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
if ( ① ) {
segment t = A[j];
②
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> A[i].a >> A[i]?b;
sort();
int p = 1;
for (int i = 1; i < n; i++)
if ( ③ )
A[p++] = A[i];
n = p;
int ans = 0, r = 0;
int q = 0;
while (r < m) {
while ( ④ )
q++;
⑤;
ans++;
}
cout << ans << endl;
return 0;
}
- ① 处应填（ ）
A. A[j].b>A[j-1].b
B. A[j].a
C. A[j].a>A[j-1].a
D. A[j].b
【解析】按照区间左端点从小到大排序。
【答案】B。
- ② 处应填（ ）
A. A[j+1]=A[j];A[j]=t;
B. A[j-1]=A[j];A[j]=t;
C. A[j]=A[j+1];A[j+1]=t;
D. A[j]=A[j-1];A[j-1]=t;
【解析】冒泡排序，第 j 号区间和第 j-1 号区间进行变量交换。
【答案】D。
- ③ 处应填（ )
A. A[i].b>A[p-1].b
B. A[i].b
C. A[i].b>A[i-1].b
D. A[i].b
【解析】过滤掉一定不符合要求的区间，如后面区间的右端点小于前面区间的右端点。
【答案】A。
- ④ 处应填（ ）
A. q+1
B. q+1
C. q
D. q
【解析】当前被选中区间的左端点要小于等于前面区间右端点。
【答案】A。
- ⑤ 处应填（ )
A. r=max(r,A[q+1].b)
B. r=max(r,A[q].b)
C. r=max(r,A[q+1].a)
D. q++
【解析】当前被选中区间的左端点要小于等于前面区间右端点，且右端点取最大值。
【答案】B。