QQ扫一扫联系
请选出以下最大的数（ ）
(550)10
(777)8
210
(22F)16
操作系统的功能是（ ）
负责外设与主机之间的信息交换
控制和管理计算机系统的各种硬件和软件资源的使用
负责诊断机器的故障
将源程序编译成目标程序
现有一段8分钟的视频文件，它的播放速度是每秒24 帧图像，每帧图像是一幅分辨 率为2048×1024像素的32位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存 储空间?（ ）。
30G
90G
150G
450G
今有一空栈S，对下列待进栈的数据元素序列a, b, c, d, e, f依次进行：进栈，进栈， 出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。
b
a
d
c
将（2，7，10，18）分别存储到某个地址区间为0~10的哈希表中，如果哈希函数 h(x) =（ ），将不会产生冲突，其中 a mod b表示a除以b的余数。
x2 mod 11
2x mod 11
x mod 11
[x/2]mod 11，其中[x/2]表示x/2下取整
下列哪些问题不能用贪心法精确求解?（ ）
霍夫曼编码问题
0-1背包问题
最小生成树问题
单源最短路径问题
具有n 个顶点，e条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂 度为（ ）。
O(n+e)
O(n2)
O(e2)
O(n)
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向 图。那么，24个顶点的二分图至多有（ ）条边。
144
100
48
122
广度优先搜索时，一定需要用到的数据结构是（ ）。
栈
二叉树
队列
哈希表
一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就 多四人，问这个班的学生人数n在以下哪个区间? 已知n<60。（ ）
30<n<40
40<n<50
50<n<60
20<n<30
小明想通过走楼梯来锻炼身体，假设从第1层走到第2层消耗10卡热量，接着从第2 层走到第3层消耗20卡热量，再从第3层走到第4层消耗30卡热量，依此类推，从第k层走到 第k+1层消耗10k 卡热量(k > 1)。如果小明想从1层开始，通过连续向上爬楼梯消耗1000卡 热量，至少要爬到第几层楼?（ ）。
14
16
15
13
表达式a*(b+c)-d的后缀表达形式为（ ）。
abc*+d
-+*abcd
abcd*+-
abc+*d
从一个4×4的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方 法。
60
72
86
64
对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路时，如 果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
O((m + n2) log n)
O(mn + n3)
O((m + n) log n)
O(n2)
1948年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
欧拉(Leonhard Euler)
冯·诺伊曼(John von Neumann)
克劳德·香农(Claude Shannon)
图灵(Alan Turing)
第16~21题题目
1 #include<iostream>
2 using namespace std;
3
4 int n;
5 int d[1000];
6
7 int main() {
8 cin >> n;
9 for (int i = 0; i < n; ++i)
10 cin >> d[i];
11 int ans = -1;
12 for (int i = 0; i < n; ++i)
13 for (int j = 0; j < n; ++j)
14 if (d[i] < d[j])
15 ans = max(ans, d[i] + d[j] - (d[i] & d[j]));
16 cout << ans;
17 return 0;
18 }假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单选题:
n必须小于1000，否则程序可能会发生运行错误。（）
输出一定大于等于0。（）
若将第13行的“j = 0”改为“j = i +1”，程序输出可能会改变。（）
将第14行的“d[i] < d[j]”改为“d[i] != d[j]”，程序输出不会改变。（）
若输入n为100，且输出为127，则输入的d[i]中不可能有（）。
127
126
128
125
若输出的数大于0，则下面说法正确的是（）。
若输出为偶数，则输入的d[i]中最多有两个偶数
若输出为奇数，则输入的d[i]中至少有两个奇数
若输出为偶数，则输入的d[i]中至少有两个偶数
若输出为奇数，则输入的d[i]中最多有两个奇数
第22~27题题目
1 #include<iostream>
2 #include
3 using namespace std;
4
5 int n;
6 int d[10000];
7
8 int find(int L, int R, int k) {
9 int x = rand() % (R - L + 1) + L;
10 swap(d[L], d[x]);
11 int a = L + 1, b = R;
12 while (a < b) {
13 while (a < b && d[a] < d[L])
14 ++a;
15 while (a < b && d[b] >= d[L])
16 --b;
17 swap(d[a], d[b]);
18 }
19 if (d[a] < d[L])
20 ++a;
21 if (a - L == k)
22 return d[L];
23 if (a - L < k)
24 return find(a, R, k - (a - L));
25 return find(L + 1, a - 1, k);
26 }
27
28 int main() {
29 int k;
30 cin >> n;
31 cin >> k;
32 for (int i = 0; i < n; ++i)
33 cin >> d[i];
34 cout << find(0, n - 1, k);
35 return 0;
36 }假设输入的n，k和d[i]都是不超过10000的正整数，且k不超过n，并假设rand()函数产生的
是均匀的随机数，完成下面的判断题和单选题:
第9行的“x”的数值范围是L+1到R，即[L+1, R]。（）
将第19行的“d[a]”改为“d[b]”，程序不会发生运行错误。（）
当输入的d[i]是严格单调递增序列时，第17行的“swap”平均执行次数是（）。
O(n log n)
O(n)
O(log n)
O(n2)
当输入的d[i]是严格单调递减序列时，第17行的“swap”平均执行次数是（）
O(n2)
O(n)
O(n log n)
O(log n)
若输入的d[i]为i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是 （）。
O(n), O(n2)
O(n), O(n log n)
O(n log n), O(n2)
O(n log n), O(n log n)
若输入的d[i]都为同一个数，此程序平均的时间复杂度是（）。
O(n)
O(log n)
O(n log n)
O(n2)
第28~33题题目
输出可能为0。（）
若输入的两个字符串长度均为101时，则m=0时的输出与m=100时的输出是一样 的。（）
若两个字符串的长度均为n，则最坏情况下，此程序的时间复杂度为O(n!)。（）
若输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符 串的倒序，输入的m为0，则输出为（）。
49
50
100
-1
已知当输入为“0123\n3210\n1”时输出为4，当输入为 “012345\n543210\n1”时输出为14，当输入为“01234567\n76543210\n1”时输出 为28，则当输入为“0123456789ab\nba9876543210\n1”输出为（）。其中“\n”为 换行符。
56
84
102
68
若两个字符串的长度均为n，且0<m<n-1，且两个字符串的构成相同（即任何一个
字符在两个字符串中出现的次数均相同），则下列说法正确的是（）。提示：考虑输入与输
出有多少对字符前后顺序不一样。
若n、m均为奇数，则输出可能小于0。
若n、m均为偶数，则输出可能小于0。
若n为奇数、m为偶数，则输出可能小于0。
若n为偶数、m为奇数，则输出可能小于0。
第34~38题题目
（分数背包）小S有n块蛋糕，编号从1到n。第i块蛋糕的价值是wi，体积是vi。他有一个大
小为B的盒子来装这些蛋糕，也就是说装入盒子的蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他可以选择一个α
(0<α<1)，并将一块价值是w，体积为v的蛋糕切割成两块，其中一块的价值是α · w，体积
是α · v，另一块的价值是(1- a)·w，体积是(1-a)·v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3，B=8，三块蛋糕的价值分别是4、4、2，体积分别是5、3、2。那么最优的方案
就是将体积为5的蛋糕切成两份，一份体积是3，价值是2.4，另一份体积是2，价值是1.6，
然后把体积是3的那部分和后两块蛋糕打包进盒子。最优的价值之和是8.4，故程序输出
42/5。
输入的数据范围为：1≤n≤1000，1≤B≤105；1≤wi,vi≤100。提示：将所有的蛋糕按照性
价比wi/vi从大到小排序后进行贪心选择。试补全程序。
①处应填（）
w[j] / v[i] < w[j +1] / v[j +1]
w[j] / v[j] > w[j +1] / v[j+ 1]
v[j] * w[j + 1] < v[j + 1]* w[j]
w[j]* v[j + 1] < w[j +1]* v[j]
②处应填（）
w[1] <= B
v[1] <= B
w[1] >= B
v[1] >= B
③处应填（）
print(v[1], w[1]); return 0;
curV = 0; curW = 0;
print(w[1], v[1]); return 0;
curV = v[1]; curW = w[1];
④处应填（）
curW * v[i] + curV * w[i], v[i]
(curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
curW + v[i], w[i]
curW * v[i] + (B - curV) * w[i], v[i]
⑤处应填（）
curW, curV
curW, 1
curV, curW
curV,1
第39~43题题目
（最优子序列）取m = 16，给出长度为n的整数序列a1, a2,…, an(0≤ ai <2m)。对于一个二进制数x，定义其分值w(x)为x+ popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1, b2…, bk，定义其子序列分值S为w(b1 ⊕ b2) + w(b2 ⊕b3)+w(b3 ⊕ b4)+…+w(bk-1 ⊕ bk)。其中⊕表示按位异或。对于空子序列，规定其子序
列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。输入第一行包含一个整数n(1 ≤n ≤ 40000)。接下来一行包含n个整数a1, a2,…, an。
提示：考虑优化朴素的动态规划算法，将前m/2位和后m/2位分开计算。Max[x][y]表示当前的子序列下一个位置的高8位是x、最后一个位置的低8位是y时的最大价值。
试补全程序。
#include<iostream>
using namespace std;
typedef long long LL;
const int MAXN = 40000, M = 16, B = M >> 1, MS = (1 << B) - 1;
const LL INF = 1000000000000000LL;
LL Max[MS + 4][MS + 4];
int w(int x) {
int s = x;
while(x) {
①;
s++;
}
return s;
}
void to_max(LL &x, LL y) {
if(x < y)
x = y;
}
int main() {
int n;
LL ans = 0;
cin >> n;
for(int x = 0; x <= MS; x++)
for(int y = 0; y <= MS; y++)
Max[x][y] = -INF;
for(int i = 1; i <= n ; i++) {
LL a;
cin >> a;
int x = ② , y = a & MS;
LL v = ③;
for(int z = 0; z < = MS; z++)
to_max(v, ④);
for(int z = 0; z < = MS; z++)
⑤;
to_max(ans , v);
}
cout << ans << endl;
return 0;
}①处应填（）
x >>= 1
x ^= x & (x ^ (x + 1))
x -= x | -x
x ^= x & (x ^ (x - 1))
②处应填（）
(a & MS) << B
a >> B
a & (1 << B)
a & (MS << B)
③处应填（）
-INF
Max[y][x]
0
Max[x][y]
④处应填（）
Max[x][z] + w(y ^ z)
Max[x][z] + w(a ^ z)
Max[x][z] + w(x ^ (z <<B))
Max[x][z] + w(x^ z)
⑤处应填（）
to_max(Max[y][z], v + w(a ^ (z << B)))
to_max(Max[z][y], v + w((x^ z) << B))
to_max(Max[z][y], v + w(a ^ (z << B)))
to_max(Max[x][z], v + w(y ^ z))
