以补码存储的 8 位有符号整数 10110111 的十进制表示为 ( )。
-73
184
72
-72
1946 年，( )提出了存储程序原理，奠定了现代电子计算机基本结构，开创了程序设计的新时代。
艾伦·麦席森·图灵(Alan Mathison Turing)
约翰·冯·诺依曼(John von Neumann)
克劳德·艾尔伍德·香农(Claude Elwood Shannon)
罗伯特·塔扬(Robert Tarjan)
有 4 个结点和 4 条边的有标号简单无向图的数量是 ( )。
15
16
6
4
以下排序算法中最好情况下时间复杂度与最坏情况下时间复杂度相同的是 ( )。
选择排序
冒泡排序
插入排序
快速排序
在一条长度为 1 的线段上随机取一个点，再在以原线段的左端点和取的 该点为端点的线段上随机取一个点，则以取的两个点为端点的线段的期望 长度是( )。
1/2
1/3
1/4
2/3
假设某算法的计算时间表示为递推关系式 𝑇(𝑛) = 3𝑇 (n/2) + Θ(𝑛)，𝑇(1) = Θ(1)，则算法的时间复杂度为 ( )
Θ(𝑛)
Θ(𝑛log2 3)
Θ(𝑛 log 𝑛)
Θ(𝑛log2 3 log 𝑛)
设 x=true,y=false,z=true。以下逻辑运算表达式值为true的是( )。
(¬𝑥∨𝑦)∧𝑧
(𝑦∧𝑧)∨(𝑥∧𝑦)
(𝑥∧𝑦)∨𝑧
(𝑥∧𝑧)∧𝑦
有 5 个从 1 到 5 标号的小球和 5 个同样标号的盒子，现将小球随机放 入盒子，每个盒子仅放 1 个小球，问每个盒子中的小球都与盒子标号不同 的概率是( )。
24/625
7/20
43/120
11/30
前缀表达式*+a b+c d的中缀形式是( )。
(a + b) * (c + d)
+ b * c + d
a * b + c * d
(d + c) * (b + a)
下列算法中，没有运用分治思想的一项是 ( )。
归并排序算法
求二叉树的前序遍历
快速排序算法
求二叉树的层次遍历
具有 n 个顶点，m 条边的连通图采用邻接矩阵存储结构，进行深度优先遍历运算的时间复杂度为( )。
Θ(𝑛3)
Θ(𝑛2)
Θ(𝑛 + 𝑚)
Θ(𝑚2)
对一个 n 个顶点，m 条边的带正权有向简单图使用 Dijkstra 算法计算 单源最短路时，如果再使用一个可以在 Θ(log n) 时间复杂度内查询堆内最
小值、在 Θ(√𝑛) 时间复杂度内合并两个堆、在 Θ(1) 时间复杂度内将堆内 一个元素变小、在 Θ(log𝑛) 时间复杂度内弹出堆内最小值的堆优化
Dijkstra 算法，则整个 Dijkstra 算法的时间复杂度为 ( )。
Θ(𝑛√𝑛 + 𝑚 log 𝑛)
Θ((𝑛 + 𝑚) log 𝑛)
Θ(𝑚+𝑛log𝑛)
Θ(𝑚√𝑛 + 𝑛 log 𝑛)
链接器的功能是 ( )。
把源代码转换成特定硬件平台的机器指令
把机器指令组合成完整的可执行程序
把源代码转换成可执行程序
把高级语言翻译成低级语言
现有一段 24 分钟的视频文件，它的帧率是 30Hz，分辨率是 1920×1080， 每帧图像都是 32 位真彩色图像，使用的视频编码算法达到了 25% 的压 缩率。则这个视频文件占用的存储空间大小约是( )。
668GiB
334GiB
85GiB
500GiB
在计算机非专业级别软件能力认证 CSP-S 进行时，下列行为中被允许的 是( )。
使用 SSH 协议远程登录其它计算机以获取试题等文件
写程序在评测环境中修改输入文件
使用 U 盘拷贝题目及下发文件或自己的代码供赛后复盘
通过枚举输入文件的可能情况获得答案并写入源代码
阅读程序：
#include <cstdio>
#include <cstring>
using namespace std;
char s[10000];
int cnt[26];
int main() {
scanf("%s", s)；
for (int i = 0; i < strlen(s); ++i) {
if (cnt[s[i] - 'a'] <= 50) {
s[strlen(s)] = s[i];
}
++cnt[s[i] - 'a'];
}
printf("%s\n", s);
return 0;
}假设设初始时输入的字符串长度不超过 500，且不是空串。完成下面的判 断题和单选题:
将程序第11行中的“++i”改为“i++”，程序运行结果不会改变( )
将程序第11行改为“for(int i=0,len=strlen(s);i<len;++i)”，程序的运行结果不会改变，同时程序的运行效率将得到提升( )
对于任意一个出现了a到z中所有的字符、且各字符出现的次数不小于50 的字符串 b，总存在一个字符串 a，使得将字符串 a 输入程序后的运 行结果为字符串b。( )
程序的输出字符串长度一定不小于1300(注:1300=50×26)。( )
设输入字符串长度为x(1≤x≤500)，输出字符串长度为y，则关于x和y的大小关系正确的是( )。
对于全部的输入字符串，都有x=y。
对于全部的输入字符串，都有x<y。
存在一部分输入字符串，使得 x=y;也存在一部分输入字符串，使得x<y;但是不存在 x>y 的情况。
存在一部分输入字符串，使得 x=y;也存在一部分输入字符串，使得x>y;还存在一部分输入字符串，使得 x<y。
设字符串w为abcd...z，即从a到z在w中依次出现一次， 共 26 个字符。若输入为 w 重复出现两次的结果(即abcdefg...zabcdefg...z，则输出结果为( )。
w重复出现50次的结果。
w重复出现51次的结果。
w重复出现52次的结果。
w重复出现53次的结果。
阅读程序：
#include <cstdio>
const int N = 5010;
const int M = 20010;
const int inf = 1073741823;
int e, bg[N], nx[M], to[M], wt[M];
inline void link(int u, int v, int w) {
to[++e] = v;
nx[e] = bg[u];
wt[e] = w;
bg[u] = e;
}
int n, m, u, v, w;
int f[N], h[N << 1];
void update(int x, int y) {
x += n - 1;
for (h[x] = y; x; x >>= 1)
h[x >> 1] = f[h[x]] < f[h[x^1]] ? h[x] : h[x^1];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i != m; ++i) {
scanf("%d%d%d", &u, &v, &w);
link(u, v, w);
}
int nn = n << 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j != nn; ++j)
h[j] = 0;
for (int j = 0; j <= n; ++j)
f[j] = inf;
f[i] = 0;
update(i, i);
for (int j = i; true; j = h[1]) {
if (f[j] == inf) break;
for (int k = bg[j]; k; k = nx[k]) {
if (f[j] + wt[k] < f[to[k]]) {
f[to[k]] = f[j] + wt[k];
update(to[k], to[k]);
}
}
update(j, 0);
}
for (int j = 1; j <= n; ++j)
printf("%d%c", f[j], "\n "[j != n]);
}
return 0;
}以下程序的输入是一张带边权的有向图，完成下面的判断题和单选题:
将程序中所有的 “!=” 替换为 “<”，程序将仍然正常运行且输出的结果不会改变。 ( )
为了保证程序正常运行，输入的边数必须不大于 2 × 104。 ( )
程序的输出是一个 n×n 的整数矩阵。 ( )
将程序第 34 行的 “j=0” 替换为 “j=1”，程序将仍然正常运行且输 出的结果不会改变。 ( )
当输入的图中所有边的边权均为一个相同的正整数，且有∑ 𝑤𝑖 < 1073741823 时，“update” 函数被调用的次数为( )。
Θ(𝑛2)
Θ(𝑛𝑚)
Θ(𝑛2 + 𝑛𝑚)
Θ(𝑛min(𝑛,𝑚))
当输入的边权均为正整数时，程序在最坏情况下的时间复杂度为( )。
Θ(𝑛3)。
Θ(𝑛2 log 𝑛 + 𝑛𝑚)。
Θ(𝑛𝑚 log 𝑛)。
Θ(𝑛2𝑚)。
阅读程序：
#include <bits/stdc++.h>
using namespace std;
#define N 105
#define INF 1e9
int dis1[N][N], dis2[N][N];
int mp[N][N], n, m;
void fun1(int dis[N][N]) {
static bool vis[N];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = mp[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) vis[j] = 0;
for (int k = 1; k <= n; k++) {
int now = 0;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (!now || dis[i][now] > dis[i][j])) now = j;
}
vis[now] = 1;
for (int j = 1; j <= n; j++) {
if(!vis[j]&&dis[i][j] > dis[i][now]+mp[now][j]){
dis[i][j] = dis[i][now] + mp[now][j];
}
}
}
}
}
void fun2(int dis[N][N]) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dis[i][j] = mp[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) mp[i][j] = 0;
else mp[i][j] = INF;
}
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
mp[u][v] = w;
}
fun1(dis1);
fun2(dis2);
int ans = 0;
for (int i = 1; i <= n; i++) {
for(intj=1;j<=n;j++){
if (dis1[i][j] != dis2[i][j])
ans++;
}
}
cout << ans << endl;
return 0;
}以下程序的输入数据满足 𝟏 ≤ 𝒏 ≤ 𝟏𝟎𝟎, 𝟏 ≤ 𝒎 ≤ 𝒏(𝒏−𝟏) ，且只保证不存在 𝟐重边，即不存在 (𝒖𝒊, 𝒗𝒊) = (𝒖𝒋, 𝒗𝒋) (𝒊 ≠ 𝒋)，边权 𝒘𝒊 ∈ [𝟏, 𝟏𝟎𝟔] 。如果 u 到 v不可达，则认为距离为 INF 。完成下面的判断题和单选题:
该代码的 dis1[i][j] 不一定是 i 到 j 的最短路。( )
输出可能为 1 。( )
将第19行的k<=n修改为k<n，不影响答案。( )
对于稀疏图(n,m 不同阶)，fun1() 对于单个 i 求 dis[i][j] (1≤𝑗≤𝑛) ，最快可以做到Θ((𝑛+𝑚)log𝑚) 。（ ）
对于以下的输入数据，输出结果为( )。
5 8
3 2 2
2 4 2
1 4 3
3 1 2
4 3 3
5 2 3
1 5 1
1 2 2
2
3
4
5
若输入数据 “n=5” ，输出 ans 的最大可能值为 ( )。
4
5
6
7
(装备穿戴问题)有 n 件装备，穿戴第 i 件装备需要玩家的力量值至少为 𝑎𝑖，穿戴该装备后会让玩家的力量值增加 𝑏𝑖。现在请问玩家的初始力量 值最小是多少，才能以某种顺序穿戴上所有的装备? 输入:第一行是一个整数 n(1 ≤ 𝑛 ≤ 103);第二行有 n 个整数，第 i 个 整数表示 𝑎𝑖(0 ≤ 𝑎𝑖 ≤ 109);第三行有 n 个整数，第 i 个整数表示 𝑏𝑖 ( 0 ≤ 𝑏 𝑖 ≤ 1 0 6 )。 提示:使用二分+贪心的方法解决这个问题，先对装备按顺序进行排序，然 后二分答案，并贪心地进行选择。
试补全程序。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int n;
int a[maxn], b[maxn], c[maxn];
bool Comp(const int &x, const int &y) {
// 你可以简单地认为括号内的内容等价于 (int x, int y)
return 1;
}
bool check(int x) {
for(int i = 1; i < =n; ++i){
int u = c[i];
if (2) {
x += b[u];
} else {
return false;
}
}
return true;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <=n; ++i) scanf("%d", a + i);
for (int i = 1; i <=n; ++i) scanf("%d", b + i);
for (int i = 1; i <=n; ++i) c[i] = i;
sort(c + 1, c + 1 + n, Comp);
int ans = 1145141919;
for (int l=1, r=ans, mid=(l+r)/2; 3; mid=(l+r)/2)
if (check(mid)) {
ans = mid;
4;
} else {
5;
}
printf("%d\n", ans);
return 0;
}
1处应填( )。
a[x] > a[y]
a[x] < a[y]
a[x] >= a[y]
a[x] <= a[y]
2处应填( )。
x < a[i]
x<a[u]
x >= a[i]
x>=a[u]
3处应填( )。
l<r
l<=r
check(l)
check(r)
4处应填( )。
r = mid – 1
r=mid+ 1
l = mid – 1
l=mid+ 1
5处应填( )。
r = mid – 1
r=mid+ 1
l = mid – 1
l=mid+ 1
(打音游)小 A 最近喜欢上了一款音游，并希望在结算时得到特定分数， 例如 1919810 分。这款音游的得分计算方式如下:一共有 n 个音符，将 一千万(107)分平分给所有音符得到基础得分 𝑥 = 107/n(保留非整数部 分)，其中有 m 个音符根据是否击中可以获得 x+1 分或者 0 分，剩下的 n-m 个音符根据击中精度可以获得 x+1，x，x/2，0 分中的一个，最后将总 得分向下取整即可得到最终得分。
给定 n,m，小 A 想知道他可以得到多少种不同的分数。 输入为两个非负整数，分别表示 n,m;满足1 ≤ 𝑛 ≤ 107，0 ≤ 𝑚 ≤ 𝑛。输出 为一个正整数表示答案。试补全程序。
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if(m==n){
cout<<1<<end1;
return o;
}
long long m=1000000;
int ans=2;
int lst=0;
for(int i=1;i<=n ++1 ){
for(int j=1; j>=0; --j){
int lower=max(0,3);
int upper=i-j;
int base=4;
ans+=upper-lower+1;
if(lower+base<=lst) ans-=lst-(lower+base)+1;
lst=5;
}
}
cout<<ans<<endl;
return 0;
}
1处应填
-1
n-1
n
n+1
2处应填
-1
0
1
n
3处应填
i–(n-m)-1
i–(n-m)-j
i–(n-m)
i–(n-m)+j
4处应填
(2*i+j) * M / (2*n)
(2*i-j) * M / (2*n)
i * M / n +j * M / (2*n)
i * M / n -j * M / (2*n)
5处应填
base + upper
base + upper + 1
base + lower
base + lower + 1