1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。
   A. $(269)_{16}$
   B. $(617)_{10}$
   C. $(1001101011)_2$
   D. $(1151)_8$
   【解析】本题由$2$进制数转换为$8$、$16$进制数，可以进行快速判断。$2$进制数从右至左每3位可以转换为一个$8$进制数。$2$进制数从右至左每4位可以转换为一个$16$进制数。
2. 中国计算机学会于（1984 ）年创办全国青少年计算机程序设计竞赛。
3. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照 CapsLock、字母键 A、字母键 S、字母键 D、字母键 F 的顺序循环按键，即 CapsLock、A、 S、D、F、 CapsLock、a、s、d、f、……，屏幕上输出的第 81 个字符是字母（ ）。
   【解析】屏幕上输出的字符：ASDFasdfASDFasdf…。$81\%4=1$，所以输出的字符应该是A或者a。如果按$4$个字符一组，会发现奇数组为大写字符，偶数组为小写字符，$81/4=21$为奇数组，所以屏幕上输出的第 81 个字符是字母A。
4. 根节点深度为 $0$，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。
   【解析】由于$k>1$，不妨设$k = 2$，根节点深度为 $0$的满二叉树，共有$2^{h+1} - 1$个结点，所以答案：$(k^{h+1} - 1)/(k - 1)$。
5. 以下排序算法中，不需要进行关键字比较操作的算法是（ 基数排序）。
   【解析】基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份信息，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定的排序算法，其时间复杂度为$O (nlog(r)m$)，其中$r$为所采取的基数，而$m$为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
6. 给定一个含 $N$ 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 $N - 1$ 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（ ）次比较操作。（$\lceil \rceil$ 表示向上取整，$\lfloor \rfloor$表示向下取整）。
   A. $2N-2$
   B. $2N-4$
   C. $\lfloor 3N/2\rfloor-2$
   D. $\lceil 3N/2\rceil-2$
   【解析】在$N$ 个不相同数字的数组同时查找最大值与最小值的算法思想如下：
   对$N$个数字两两比较，再将较大的数字与最大值打擂台，较小的数字与最小值打擂台。
   最坏情况下的算法时间复杂度：
   • 当$N$是奇数时，$\lceil N / 2 \rceil \times 3$ 。将第一个数赋值给最大值和最小值。然后将剩下$N-1$个整数两两一组，共$(N-1)/2$组，每组组内比较一次，与最大值比较一次，与最小值比较一次，共三次。总比较次数：$3\times(N-1)/2$。
   • 当$N$是偶数时，将前两个数比较一次，将较大数赋值给最大值、较小数赋值给最小值。然后将剩下的$N-2$个数两两一组，共$(N-2)/2$组，每组组内比较一次，与最大值比较一次，与最小值比较一次，共三次。总比较次数$3\times(N-2)/2 + 1$。

本题可以将尝试用$N=3$排除选项C，答案：D。

7. 由四个没有区别的点构成的简单无向连通图的个数是（ ）。
   【解析】简单无向连通图。
   含平行边（重边）的图称为多重图，既不含平行边也不包含自环的图称为简单图。
   4个结点的简单无向连通图，可以有3、4、5、6条边。
   3条边形态如下：
   
   4条边形态如下：
   
   5条边形态如下：
   
   6条边形态如下：
   
   答案：由四个没有区别的点构成的简单无向连通图的个数是6。
8. 设含有 $10$ 个元素的集合的全部子集数为 $S$，其中由 $7$ 个元素组成的子集数为 $T$，则 $T / S$ 的值为（ ）。
   【解析】$S=2^{10}$, $T=C_{10}^7$, $T/S=\frac{120}{1024}=\frac{15}{128}$
9. $10000$ 以内，与 $10000$ 互质的正整数有（ ）个。
   【解析】欧拉函数$\phi(n)$表示小于或等于n的正整数中与n互质的数的数目。
   $\phi(n)=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times...\times(1-\frac{1}{p_k})$
   $p_1,p_2,...p_k$为n的质因子。
   $10000$的质因子有：$2,5$
   所以$\phi(10000)=10000\times(1-\frac{1}{2})\times(1-\frac{1}{5})=4000$
10. 为了统计一个非负整数的二进制形式中 $1$ 的个数，代码如下：

int CountBit(int x) {int ret = 0;while (x) {++ret;（    ）;}
}

【解析】x&=(x-1)去掉x最低位的1。例如x=18, $(10010)_2$ & $(10001)_2$ = $(10000)_2$。

问题求解

1. 甲乙丙丁四人在考虑周末要不要外出郊游。已知①如果周末下雨，并且乙不去，则甲一定不去；②如果乙去，则丁一定去；③如果丙去，则丁一定不去；④如果丁不去，而且甲不去，则丙一定不去。如果周末丙去了，则甲____（去了/没去），乙____（去了/没去），丁 ___ （去了/没去），周末____（下雨/没下雨）。
   【解析】丙去了，丁一定没去。
   丁没去，如果甲也不去，则丙不去。现在丙去了，所以甲一定去了。
   丁没去，如果下雨，则甲不去。现在甲去了，则一定没下雨。
   乙去了，则丁一定去了。现在丁没去，则乙一定没去。
2. 从 1 到 2018 这 2018 个数中，共有___个包含数字 8 的数。包含数字 8 的数是指有某一位是“8”的数，例如“2018”与“188”。
   【解析】$0-9$ 有1个、$10-19$有1个、…、$70-79$有1个、$80-89$有10个、$90-99$有1个。$0-99$有19个、…、$700-799$有19个、$800-899$有100个、$900-999$有19个。$0-1000$有271个、$0-2000$有542个，$0-2018$有544个。

阅读程序写结果

#include <cstdio>
int main() {int x;scanf("%d", &x);int res = 0;for (int i = 0; i < x; ++i) {if (i * i % x == 1) {++res;}}printf("%d", res);return 0;
}

输入：15
【解析】$0-14$中平方数除15余数为1的数有1、4、11、14，一共4个。
2.

#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {if (n == 0) return m;if (m == 0) return n % 3;return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){cin >> n >> m;cout << findans(n, m) << endl;return 0;
}

输入：5 6
【解析】模拟递归调用，找规律

f(0,0)	f(0,1)	f(0,2)	f(0,3)	f(0,4)	f(0,5)	f(0,6)
0	1	2	3	4	5	6
f(1,0)	f(1,1)	f(1,2)	f(1,3)	f(1,4)	f(1,5)	f(1,6)
1	0	3	2	5	4	7
f(2,0)	f(2,1)	f(2,2)	f(2,3)	f(2,4)	f(2,5)	f(2,6)
2	-1	4	1	6	3	8
f(3,0)	f(3,1)	f(3,2)	f(3,3)	f(3,4)	f(3,5)	f(3,6)
0	1	2	3	4	5	6
f(4,0)	f(4,1)	f(4,2)	f(4,3)	f(4,4)	f(4,5)	f(4,6)
1	0	3	2	5	4	7
f(5,0)	f(5,1)	f(5,2)	f(5,3)	f(5,4)	f(5,5)	f(5,6)
2	-1	4	1	6	3	8

总结规律：f[i][j] = f[i-1][j]-f[i][j-1]+f[i-1][j-1]

3.

#include <cstdio>
int n, d[100];
bool v[100];
int main() {scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", d + i);v[i] = false;}int cnt = 0;for (int i = 0; i < n; ++i) {if (!v[i]) {for (int j = i; !v[j]; j = d[j]) {v[j] = true;}++cnt;}}printf("%d", cnt);return 0;
}

【解析】手动模拟。

0	1	2	3	4	5	6	7	8	9
7	1	4	3	2	5	9	8	0	6

i = 0
j=0, v[0]=true, j = d[0] = 7
j=7, v[7]=true, j = d[7] = 8
j=8, v[8]=true, j = d[8] = 0
cnt=1
i = 1
j=1, v[1]=true, j = d[1] = 1
cnt=2
i=2
j=2, v[2]=true, j = d[2] = 4
j=4, v[4]=true, j = d[4] = 2
cnt=3
i=3
j=3, v[3]=true, j = d[3] = 3
cnt=4
i=4
i=5
j=5, v[5]=true, j = d[5] = 5
cnt=5
i=6
j=6, v[6]=true, j = d[6] = 9
j=9, v[9]=true, j = d[9] = 6
cnt=6
i=7
i=8
i=9
答案：6

完善程序

（最大公约数之和）下列程序想要求解整数 $n$ 的所有约数两两之间最大公约数的和对 $10007$ 求余后的值，试补全程序。
举例来说，$4$ 的所有约数是 $1,2,4$。$1$ 和 $2$ 的最大公约数为 $1$；$2$ 和 $4$ 的最大公约数为 $2$；$1$ 和 $4$ 的最大公约数为 $1$。于是答案为 $1 + 2 + 1 = 4$。
要求 getDivisor 函数的复杂度为 $\mathcal{O}(\sqrt n)$，gcd 函数的复杂度为$\mathcal{O}(\log\ \max(a,b))$

#include <iostream>
using namespace std;
const int N = 110000, P = 10007;
int n;
int a[N], len;
int ans;
void getDivisor() {len = 0;for (int i = 1; ① <= n; ++i)if (n % i == 0) {a[++len] = i;if ( ② != i) a[++len] = n / i;}}
}
int gcd(int a, int b) {if (b == 0) {③ ;}return gcd(b, ④ );
}
int main() {cin >> n;getDivisor();ans = 0;for (int i = 1; i <= len; ++i) {for (int j = i + 1; j <= len; ++j) {ans = ( ⑤ ) % P;}}cout << ans << endl;return 0;
}

【解析】
空①，要求 getDivisor 函数的复杂度为 $\mathcal{O}(\sqrt n)$，所以此空应填i*i。
空②，不能将相同的约数存入a[]，所以此空应填n/i
空③，辗转相除法求最大公约数，此空应填return a
空④，此空应填a%b
空⑤，求约数两两之间最大公约数的和，此空应填ans+gcd(a[i],a[j])

对于一个 $1$到 $n$ 的排列 $P$（即 $1$ 到 $n$ 中每一个数在 $P$ 中出现了恰好一次），令 $q_i$为第 $i$ 个位置之后第一个比 $P_i$值更大的位置，如果不存在这样的位置，则 $q_i=n+1$。举例来说，如果 $n = 5$ 且 $P$ 为$1 5 4 2 3$，则 $q$为 $2, 6, 6, 5, 6$。
下列程序读入了排列 $P$，使用双向链表求解了答案。试补全程序。
【数据范围】$1 \le n \le 10^5$。

#include <iostream>
using namespace std;
const int N = 100010;
int n;
int L[N], R[N], a[N];
int main() {cin >> n;for (int i = 1; i <= n; ++i) {int x;cin >> x;① ;}for (int i = 1; i <= n; ++i) {R[i] = ② ;L[i] = i - 1;}for (int i = 1; i <= n; ++i) {L[ ③ ] = L[a[i]];R[L[a[i]]] = R[ ④ ];}for (int i = 1; i <= n; ++i) {cout << ⑤ << " ";}cout << endl;return 0;
}

【解析】双链表右侧第一个更大值
空①，保存x在链表中的位置，a[x]=i
空②，初始化链表，将R[i]指向它的右侧位置i+1
空③，从小到大将当前最小的数，从双链表中删除，L[R[a[i]]] = L[a[i]]
空④，R[L[a[i]]] = R[a[i]];
空⑤，输出每个位置之后第一个比当前位置值更大的位置，R[i]。