QQ扫一扫联系
在 Linux 系统终端中,用于切换工作目录的命令为( )。
ls
cd
cp
all
你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的
输出如 下:
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为( )。
30s
24s
18s
6s
若元素 a、b、c、d、e、f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连 续三次 退栈操作,则不可能得到的出栈序列是( )。
dcebfa
cbdaef
bcaefd
afedcb
考虑对 n 个数进行排序,以下最坏时间复杂度低于 `O(n^2)`的排序方法是( )。
插入排序
冒泡排序
归并排序
快速排序
假设在基数排序过程中,受宇宙射线的影响, 某项数据异变为一个完全不同的值。 请问排序算法结束后,可能出现的最坏情况是( )。
移除受影响的数据后,最终序列是有序序列
移除受影响的数据后,最终序列是前后两个有序的子序列
移除受影响的数据后,最终序列是一个有序的子序列和一个基本无序的子序列
移除受影响的数据后,最终序列基本无序
计算机系统用小端( Little Endian) 和大端(Big Endian) 来描述多字节数据的存储地
址顺序模式,其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数 据
存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代 码
段表示的程序,将分别输出什么结果?( )
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
EF、EF
EF、DE
DE、EF
DE、DE
一个深度为 5 (根结点深度为 1) 的完全 3 叉树, 按前序遍历的顺序给结点从 1 开始 编号,则第 100 号结点的父结点是第( )号。
95
96
97
98
强连通图的性质不包括( ):
每个顶点的度数至少为 1
任意两个顶点之间都有边相连
任意两个顶点之间都有路径相连
每个顶点至少都连有一条边
每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的 所有 2 正 规图,其中包含欧拉回路的不同 2 正规图的数量为( )。
n!
(n-1)!
n!/2
(n-1)!/2
共有 8 人选修了程序设计课程, 期末大作业要求由 2 人组成的团队完成。假设不 区分每个 团队内 2 人的角色和作用,请问共有多少种可能的组队方案。( )
28
32
56
64
小明希望选到形如“省 A ·??DDD”的车牌号。车牌号在“ ·”之前的内容固定不 变; 后面 的 5 位号码中, 前 2 位必须是大写英文字母, 后 3 位必须是阿拉伯数字(?代表 A 至 Z,D 表示 0 至 9,两个?和三个D之间可能相同也可能不同)。请问总共有多少个可供选 择的车牌号。( )
20280
52000
676000
1757600
给定地址区间为 0~9 的哈希表,哈希函数为 h(x) = x % 10,采用线性探查的冲 突解决 策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地 址 0 重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请 问 89 存储在哈希表哪个地址中。( )
9
0
1
2
对于给定的 n,分析以下代码段对应的时间复杂度,其中最为准确的时间复杂度为( )。
int i, j, k = 0; for (i = 0; i < n; i++) { for (j = 1; j < n; j*=2) { k = k + n / 2; } }
O(n)
O(n log n)
O(n√n)
O(n^2)
以比较为基本运算, 在 n 个数的数组中找最大的数, 在最坏情况下至少要做( )次 运算。
n/2
n-1
n
n+1
ack 函数在输入参数“(2,2)”时的返回值为( )。
unsigned ack(unsigned m, unsigned n) { if (m == 0) return n + 1; if (n == 0) return ack(m - 1, 1); return ack(m - 1, ack(m, n - 1)); }
5
7
9
13
第16~21题题目
#include <iostream> #include <string> #include <vector> using namespace std; int f(const string &s, const string &t) { int n = s.length(), m = t.length(); vector<int> shift(128, m + 1); int i, j; for (j = 0; j < m; j++) shift[t[j]] = m - j; for (i = 0; i <= n - m; i += shift[s[i + m]]) { j = 0; while (j < m && s[i + j] == t[j]) j++; if (j == m) return i; } return -1; } int main() { string a, b; cin >> a >> b; cout << f(a, b) << endl; return 0; }
假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:
当输入为“abcde fg”时,输出为-1。( )
当输入为“abbababbbab abab”时,输出为 4。( )
当输入为“GoodLuckCsp2022 22”时,第 20 行的“j++”语句执行次数为 2。 ( )
该算法最坏情况下的时间复杂度为( )。
f(a, b)与下列( )语句的功能最类似。
a.find(b)
a.rfind(b)
a.substr(b)
a.compare(b)
当输入为“baaabaaabaaabaaaa aaaa”,第 20 行的“j++”语句执行次数为( )。
9
10
11
12
第22~27题题目
#include <iostream> using namespace std; const int MAXN = 105; int n, m, k, val[MAXN]; int temp[MAXN], cnt[MAXN]; void init() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> val[i]; int maximum = val[0]; for (int i = 1; i < n; i++) if (val[i] > maximum) maximum = val[i]; m = 1; while (maximum >= k) { maximum /= k; m++; } } void solve() { int base = 1; for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) cnt[j] = 0; for (int j = 0; j < n; j++) cnt[val[j] / base % k]++; for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1]; for (int j = n - 1; j >= 0; j--) { temp[cnt[val[j] / base % k] - 1] = val[j]; cnt[val[j] / base % k]--; } for (int j = 0; j < n; j++) val[j] = temp[j]; base *= k; } } int main() { init(); solve(); for (int i = 0; i < n; i++) cout << val[i] << ' '; cout << endl; return 0; }
假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在int
表示范围内,完成下面的判断题和单选题:
这是一个不稳定的排序算法。( )
该算法的空间复杂度仅与 n 有关。( )
该算法的时间复杂度为 00(mm(nn+kk))。( )
当输入为“5 3 98 26 91 37 46”时,程序第一次执行到第 36 行,val[]数组的内 容依次为( )。
91 26 46 37 98
91 46 37 26 98
98 26 46 91 37
91 37 46 98 26
若 val[i]的最大值为 100,k 取( )时算法运算次数最少。
2
3
10
不确定
当输入的 k 比 val[i]的最大值还大时,该算法退化为( )算法。
选择排序
冒泡排序
计数排序
桶排序
第28~33题题目
01 #include <iostream>
02 #include <algorithm>
03
04 using namespace std;
05
06 const int MAXL = 1000;
07
08 int n, k, ans[MAXL];
09
10 int main(void)
11 {
12 cin >> n >> k;
13 if (!n) cout << 0 << endl;
14 else
15 {
16 int m = 0;
17 while (n)
18 {
19 ans[m++] = (n % (-k) + k) % k;
20 n = (ans[m - 1] - n) / k;
21 }
22 for (int i = m - 1; i >= 0; i--)
23 cout << char(ans[i] >= 10 ?
24 ans[i] + 'A' - 10 :
25 ans[i] + '0');
26 cout << endl;
27 }
28 return 0;
29 }
假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和单
选题:
该算法的时间复杂度为 00(logkk nn)。( )
删除第 23 行的强制类型转换,程序的行为不变。( )
除非输入的 n 为 0,否则程序输出的字符数为( )
当输入为“100 7”时,输出为( )。
202
1515
244
1754
当输入为“-255 8”时,输出为“( )”。
1400
1401
417
400
当输入为“1000000 19”时,输出为“( )”。
BG939
87GIB
1CD428
7CF1B
第34~38题题目
(归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调
递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k 小的数
值。
试补全程序。
#include <bits/stdc++.h> using namespace std; int solve(int *a1, int *a2, int n, int k) { int left1 = 0, right1 = n - 1; int left2 = 0, right2 = n - 1; while (left1 <= right1 && left2 <= right2) { int m1 = (left1 + right1) >> 1; int m2 = (left2 + right2) >> 1; int cnt = ①; if (②) { if (cnt < k) left1 = m1 + 1; else right2 = m2 - 1; } else { if (cnt < k) left2 = m2 + 1; else right1 = m1 - 1; } } if (③) { if (left1 == 0) { return a2[k - 1]; } else { int x = a1[left1 - 1], ④; return std::max(x, y); } } else { if (left2 == 0) { return a1[k - 1]; } else { int x = a2[left2 - 1], ⑤; return std::max(x, y); } } }
①处应填( )
(m1 + m2) * 2
(m1 - 1) + (m2 - 1)
m1 + m2
(m1 + 1) + (m2 + 1)
②处应填( )
a1[m1] == a2[m2]
a1[m1] <= a2[m2]
a1[m1] >= a2[m2]
a1[m1] != a2[m2]
③处应填( )
left1 == right1
left1 < right1
left1 > right1
left1 != right1
④处应填( )
y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]
⑤处应填( )
y = a1[k - left2 - 1]
y = a1[k - left2]
y = a2[k - left1 - 1]
y = a2[k - left1]
第39~43题题目
(容器分水)有两个容器,容器 1 的容量为为 a 升,容器 2 的容量为 b 升;同时允许下列
的三种操作,分别为:
1)FILL(i):用水龙头将容器 i(i∈{1,2})灌满水;
2)DROP(i):将容器 i 的水倒进下水道;
3)POUR(i,j):将容器 i 的水倒进容器 j(完成此操作后,要么容器 j 被灌满,要
么容器 i 被清空)。求只使用上述的两个容器和三种操作,获得恰好 c 升水的最少操作数和
操作序列。上述 a、b、c 均为不超过 100 的正整数,且c≤max{a,b}。
试补全程序。
#include <bits/stdc++.h> using namespace std; const int N = 110; int f[N][N]; int ans; int a, b, c; int init; int dfs(int x, int y) { if (f[x][y] != init) return f[x][y]; if (x == c || y == c) return f[x][y] = 0; f[x][y] = init - 1; f[x][y] = min(f[x][y], dfs(a, y) + 1); f[x][y] = min(f[x][y], dfs(x, b) + 1); f[x][y] = min(f[x][y], dfs(0, y) + 1); f[x][y] = min(f[x][y], dfs(x, 0) + 1); int t = min(a - x, y); f[x][y] = min(f[x][y], ①); t = min(x, b - y); f[x][y] = min(f[x][y], ②); return f[x][y]; } void go(int x, int y) { if (③) return; if (f[x][y] == dfs(a, y) + 1) { cout << "FILL(1)" << endl; go(a, y); } else if (f[x][y] == dfs(x, b) + 1) { cout << "FILL(2)" << endl; go(x, b); } else if (f[x][y] == dfs(0, y) + 1) { cout << "DROP(1)" << endl; go(0, y); } else if (f[x][y] == dfs(x, 0) + 1) { cout << "DROP(2)" << endl; go(x, 0); } else { int t = min(a - x, y); if (f[x][y] == ④) { cout << "POUR(2,1)" << endl; go(x + t, y - t); } else { t = min(x, b - y); if (f[x][y] == ⑤) { cout << "POUR(1,2)" << endl; go(x - t, y + t); } else assert(0); } } } int main() { cin >> a >> b >> c; ans = 1 << 30; memset(f, 127, sizeof f); init = **f; if ((ans = dfs(0, 0)) == init - 1) cout << "impossible"; else { cout << ans << endl; go(0, 0); } }
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1
②处应填( )
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1
③处应填( )
x == c || y == c
x == c && y == c
x >= c || y >= c
x >= c && y >= c
④处应填( )
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1
⑤处应填( )
dfs(x + t, y - t) + 1
dfs(x + t, y - t) - 1
dfs(x - t, y + t) + 1
dfs(x - t, y + t) - 1