选择题 共15道
阅读程序 共18道
完善程序 共10道
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 5 using namespace std; 6 7 int f(const string &s, const string &t) 8 { 9 int n = s.length(), m = t.length(); 10 11 vector<int> shift(128, m + 1); 12 13 int i, j; 14 15 for (j = 0; j < m; j++) 16 shift[t[j]] = m - j; 17 18 for (i =0; i<= n - m; i += shift[s[i + m]]){ 19 j =0; 20 while(j < m && s[i +j] == t[j]) j++; 21 if (j == m) return i; 22 } 23 24 return -1; 25 } 26 27 int main() 28 { 29 string a ,b; 30 cin >> a >> b; 31 cout << f(a, b) << endl; 32 return 0; 33 }
假设输入字符串由 ASCII 可见字符组成，完成下面的判断题和单选题：
（1分）当输入为“abcde fg”时，输出为-1。（ ）
第 22 - 27 题 组合题
1 #include <iostream> 2 3 using namespace std; 4 5 const int MAXN = 105; 6 7 int n, m, k, val[MAXN]; 8 int temp[MAXN], cnt[MAXN]; 9 10 void init() 11 { 12 cin >> n >> k; 13 for (int i = 0; i < n; i++) cin >> val[i]; 14 int maximum = val[0]; 15 for (int i = 1; i < n; i++) 16 if (val[i] > maximum) maximum = val[i]; 17 m = 1; 18 while (maximum >= k) { 19 maximum /= k; 20 m++; 21 } 22 } 23 24 void solve() 25 { 26 int base = 1; 27 for (int i = 0; i < m; i++) { 28 for (int j = 0; j < k; j++) cnt[j] = 0; 29 for (int j = 0; j < n; j++) cnt[val[j] / base % k]++; 30 for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1]; 31 for (int j = n - 1; j >= 0; j--) { 32 temp[cnt[val[j] / base % k] - 1] = val[j]; 33 cnt[val[j] / base % k]--; 34 } 35 for (int j = 0; j < n; j++) val[j] = temp[j]; 36 base *= k; 37 } 38 } 39 40 int main() 41 { 42 init(); 43 solve(); 44 for (int i = 0; i < n; i++) cout << val[i] << ; 45 cout << endl; 46 return 0; 47 }
假设输入的 n 为不大于 100 的正整数，k 为不小于 2 且不大于 100 的正整数，val[i]在int 表示范围内，完成 下面的判断题和单选题：
这是一个不稳定的排序算法。（ ）
第 28 - 33 题 组合题
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 const int MAXL = 1000; 7 8 int n, k, ans[MAXL]; 9 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 的正整数，完成下面的判断题和单选题：
该算法的时间复杂度为 O(logk n)。（ ）
第 34 - 39 题 组合题
（归并第 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); } } }
①处应填（ ）
第 40 - 44题 组合题
（容器分水）有两个容器，容器 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); } }