题目：https://www.zhihu.com/question/51865837/answer/127892121
注：我是HE的，不是JS的，照片是ZYJ神犇的
单选
一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确
选项）
1. 以下不是微软公司出品的软件是（ ）。
A. Powerpoint B. Word
C. Excel D. Acrobat Reader
2. 如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、
字母键A、字母键S 和字母键D 的顺序来回按键，即CapsLock、A、S、D、
S、A、CapsLock、A、S、D、S、A、CapsLock、A、S、D、S、A、……，
屏幕上输出的第81 个字符是字母（ ）。
A. A B. S C. D D. a
3. 二进制数00101100 和01010101 异或的结果是（ ）。
A. 00101000 B. 01111001 C. 01000100 D. 00111000
4. 与二进制小数0.1 相等的八进进制数是（ ）。
A. 0.8 B. 0.4 C. 0.2 D. 0.1
5. 以比较作为基本运算，在N 个数中找最小数的最少运算次数为（ ）。
A. N B. N-1 C. N2 D. log N
6. 表达式a*(b+c)-d 的后缀表达形式为（ ）。
A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd
7. 一棵二叉树如右图所示，若采用二叉树链表存储该二叉
树（各个结点包括结点的数据、左孩子指针、右孩子指
针）。如果没有左孩子或者右孩子，则对应的为空指针。
那么该链表中空指针的数目为（ ）。
A. 6 B. 7 C. 12 D. 14
8. G 是一个非连通简单无向图，共有28 条边，则该图至少有（ ）个顶点。
A. 10 B. 9 C. 8 D. 7
9. 某计算机的CPU 和内存之间的地址总线宽度是32 位（bit），这台计算机最
多可以使用（ ）的内存。
A. 2GB B. 4GB C. 8GB D. 16GB
10. 有以下程序：
#include <iostream>
using namespace std;
int main() {
int k = 4, n = 0;
while (n < k) {
n++;
if (n % 3 != 0)
continue;
k--;
}
cout << k << "," << n << endl;
return 0;
}
程序运行后的输出结果是（ ）。
A. 2,2 B. 2,3 C. 3,2 D. 3,3
11. 有7 个一模一样的苹果，放到3 个一样的盘子中，一共有（ ）种放法。
A. 7 B. 8 C. 21 D. 37
12. Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们
之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表
不是朋友。这个社交网站的规则是：如果某人A 向他（她）的朋友B 分享了
某张照片，那么B 就可以对该照片进行评论；如果B 评论了该照片，那么他
（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照
片进行评论（除非A 也向他（她）分享了该照片）。现在Lucia 已经上传了
一张照片，但是她不想让Jacob 看见这张照片，那么她可以向以下朋友（ ）
分享该照片。
A. Dana, Michael, Eve B. Dana, Eve, Monica
C. Michael, Eve, Jacob D. Micheal, Peter, Monica
13. 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责
切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜10 分钟，然后切
菜10 分钟，最后炒菜10 分钟。那么做一道菜需要30 分钟。注意：两道不
同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，
也不能同时切。那么做完三道菜的最短时间需要（ ）分钟。
A. 90 B. 60 C. 50 D. 40
14. 假设某算法的计算时间表示为递推关系式
T(n) = 2T(n/4)+sqrt(n)
T(1) = 1
则算法的时间复杂度为（ ）。
A. O(n) B. O(sqrt(n)) C. O(sqrt(n) log n) D. O(n^2)
15. 给定含有n 个不同的数的数组L=<x1, x2, ..., xn>。如果L 中存在xi （
1 < i < n）
使得x1 < x2 < ... < xi-1 < xi > xi+1 > ... > xn， 则称L 是单峰的，并称xi 是L 的
“峰顶”。现在已知L 是单峰的，请把a-c 三行代码补全到算法中使得算法
正确找到L 的峰顶。
a. Search(k+1, n)
b. Search(1, k-1)
c. return L[k]
Search(1, n)
1. k←.n/2.
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then __________
6. else __________
正确的填空顺序是（ ）。
A. c, a, b B. c, b, a C. a, b, c D. b, a,
(第7题图)
(第12题图)
第一题，水过，小学生都会。D
第二题，当时我们场好多人错了。。坑点如下：
1.和pj组的不同，是来回按键。
2.让你求第81个字符，而不是第81个按键。
所以我们可以得出输出的是是个字符一循环：ASDSAasdsa
所以第81个是A，选A
第三题，异或运算就是不同得1，相同得0，列竖式算一下不得了。
我们考场某人竟然不知道异或是什么。选B
第四题，我记得去年考的是16进制小数是0.8，今年成了8进制了。
想一想就明白了。选B。
第五题，可以想成N个人打乒乓球，决出冠军，最少打N-1场。选B。
第六题，得仔细说说啊。后缀表达式又叫做逆波兰表达式，就是按照从前到后的顺序把操作数和运算符压进一个栈，如果压进了一个运算符，就把栈顶的两个操作数弹出，并与该运算符进行运算，把运算结果放入栈。这题按照计算顺序，应该是先算a*(b+c)，然后是分别算a和b+c并把乘号压进栈，b+c的逆波兰式是bc+，所以应该是abc+*，然后把d压进去，再压进去减号，表达式就变成了abc+*d-。答案为B。
第七题，答案是sum(每一个节点孩子为空的数目)。根节点的左孩子是叶子节点，答案+=2。根节点右孩子的左孩子也是空节点，答案+=2。根节点右孩子的右孩子左孩子为空，答案+=1，其右孩子是空节点，答案+=2.所以答案是7。(我是智障，一张图解决一段话不得了)
下面这张图中，黑色部分表示原二叉树，红线表示指向NULL指针，红圈表示NULL，所以一共有7个。选B。
第八题，我是这么想的，先构建一个8个顶点的最稠密无向连通图，可以根据公式((8-1)*8)/2知道这张图有28条边。再添加一个孤立的节点使得这张图成为非连通图，所以选B。
第九题，常识性问题。我们说的"32位系统"理论上最多支持4GB内存就是说的这个。所以选B。
第十题。自己模拟去。用devc++或人脑均可。选D。
第十一题。枚举。注意重复情况，设三个盘子苹果量是a,b,c，在枚举时使a<=b<=c即可。下面是那八种情况。选B。
第十二题。只要找到所有是Lucia的朋友而不是Jacob的朋友就行了(Jacob本人除外)。选A。
第十三题，自己想即可。很简单。选C。
第十四题，我不会233333333333，选C。
第十五题，Search函数的第二行判断的是当前元素是否为峰顶，所以第三行是c.return L[k]。第四行判断的是当前元素从左到右是否呈上升趋势，据题意可知，如果呈上升趋势峰顶应该在右边，所以是a.search(k+1,n)。第六行就是b了。所以选A。
不定项
第一题。常识问题。最重要的是我尽然选错了，把D也选上了。以太网不是无线的。。。答案是ABC
第二题。同理也是常识问题。光驱是连接光盘的，鼠标是连接手的，显卡是连接显示屏的。答案是A
第三题。看过书的都知道。(计数排序比较少见，可能有人也选了)答案是AB
第四题。自己想就行了。我这里没有图。答案是A
第五题。有人竟然选C，不带衣服进考场。。。此人一定是受到pj组单选第20题的迷惑了。答案是ABD
问题求解
第一题。我这个约瑟夫竟然画了个树状图，画到第6层发现可以直接求结果，然后算出来是55(竟然对了)。
正解是斐波那契数列，设f(1)=2,f(2)=3,求f(8)。f(1)=2,f(2)=3,f(3)=5,f(4)=8,f(5)=13,f(6)=21,f(7)=34,f(8)=55。
第二题。答案是3,，通用技术、化学、政治一起考，物理、历史一起考，生物、地理一起考。
阅读程序写结果
我把代码弄过来了。。。若君问吾代码从何来？吾曰："手打。"
第一题。
输出：6,5,4,3,2,1,
#include <iostream>
using namespace std;
int main() {
int a[6] = {1, 2, 3, 4, 5, 6};
int pi = 0;
int pj = 5;
int t , i;
while (pi < pj) {
t = a[pi];
a[pi] = a[pj];
a[pj] = t;
pi++;
pj--;
}
for (i = 0; i < 6; i++)
cout << a[i] << ",";
cout << endl;
return 0;
}
考点：将数组倒序存储
坑点：最后一个逗号
第二题。
输入：3
AB:ACDEbFBkBD
AR:ACDBrT
SARS:Severe Atypical Respiratory Syndrome
输出：YES,NO,YES,
#include <iostream>
using namespace std;
int main() {
char a[100][100], b[100][100];
string c[100];
string tmp;
int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
cin >> n;
getline(cin, tmp);
for(i = 0; i < n; i++) {
getline(cin, c[i]);
total_len[i] = c[i].size();
}
for(i = 0; i < n; i++) {
j = 0;
while (c[i][j] != ':') {
a[i][k] = c[i][j];
k = k + 1;
j++;
}
length[i][1] = k-1;
a[i][k] = 0;
k = 0;
for (j = j + 1; j < total_len[i]; j++) {
b[i][k] = c[i][j];
k = k + 1;
}
length[i][2] = k - 1;
b[i][k] = 0;
k = 0;
}
for(i = 0; i < n; i++) {
if(length[i][1] >= length[i][2])
cout << "NO,";
else {
k=0;
for (j = 0; j < length[i][j]; j++) {
if(a[i][k] == b[i][j])
k = k + 1;
if(k > length[i][1])
break;
}
if (j == length[i][2])
cout << "NO,";
else
cout << "YES,";
}
}
cout << endl;
return 0;
}
考点：匹配不连续的字串
坑点：同第一题
第三题。
输出：5
#include <iostream>
using namespace std;
int lps(string seq, int i, int j) {
int len1, len2;
if (i == j)
return 1;
if (i > j)
return 0;
if (seq[i] == seq[j])
return lps(seq, i + 1, j - 1) + 2;
len1 = lps(seq, i, j - 1);
len2 = lps(seq, i + 1, j);
if (len1 > len2)
return len1;
return len2;
}
int main() {
string seq = "acmerandacm";
int n = seq.size();
cout << lps(seq, 0, n - 1) << endl;
return 0;
}
考点：不知道 最长回文字串(模拟即可)
坑点：没什么
第四题。
输入：11
1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 11
6 9
9 10
输出：2 5
#include <iostream>
#include <cstring>
using namespace std;
int map[100][100];
int sum[100], weight[100];
int visit[100];
int n;
void dfs(int node) {
visit[node] = 1;
sum[node] = 1;
int v, maxw = 0;
for (v = 1; v <= n; v++) {
if (!map[node][v] || visit[v])
continue;
dfs(v);
sum[node] += sum[v];
if (sum[v] > maxw)
maxw = sum[v];
}
if (n - sum[node] > maxw)
maxw = n - sum[node];
weight[node] = maxw;
}
int main() {
memset(map, 0, sizeof(map));
memset(sum, 0, sizeof(sum));
memset(weight, 0, sizeof(weight));
memset(visit, 0, sizeof(visit));
cin >> n;
int i, x, y;
for (i = 1; i < n; i++) {
cin >> x >> y;
map[x][y] = 1;
map[y][x] = 1;
}
dfs(1);
int ans = n, ansN = 0;
for (i = 1; i <= n; i++)
if (weight[i] < ans) {
ans = weight[i];
ansN = i;
}
cout << ansN << " " << ans << endl;
return 0;
}
考点：深度优先遍历求树的重心
坑点：无
完善程序
1. （交朋友）根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。
现在有n 名身高两两不相同的同学依次走入教室，调查人员想预测每个人在
走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名
同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高
为1.80 米的同学进入教室时，有一名身高为1.79 米的同学和一名身高为1.81
米的同学在教室里，那么这名身高为1.80 米的同学会更想和身高为1.81 米
的同学做朋友。对于第一个走入教室的同学我们不做预测。
由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线
的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他
之前进入教室的并且和他身高最相近的人。（第一空2 分，其余3 分）
2. （交通中断）有一个小国家，国家内有n 座城市和m 条双向的道路，每条道
路连接着两座不同的城市。其中1 号城市为国家的首都。由于地震频繁可能
导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第
i(i>1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会
发生改变。如果因为无法通过第i 个城市而导致从首都出发无法到达某个城
市，也认为到达该城市的最短路径长度改变。
对于每一个城市i，假定只有第i 个城市与外界交通中断，输出有多少个
城市会因此导致到首都的最短路径长度改变。
我们采用邻接表的方式存储图的信息，其中head[x]表示顶点x 的第一条
边的编号，next[i]表示第i 条边的下一条边的编号，point[i]表示第i 条边的终
点，weight[i]表示第i 条边的长度。（第一空2 分，其余3 分）
第一题。答案在上面。第一空是快排条件，第二空、第三空和第五空照抄即可(上面有差不多的)，第四孔就是判断应该选高的还是矮的。
第二题。答案在上面。第一空是spfa的d[1]=0，第二空是松弛，判断是否可以更新，第三空是取消访问标记，第四空是判断是否走得这条路径(我没写上来)，第五空是标记访问。