试卷总分：100分
选择题 15题 30分
阅读程序 18题 40分
完善程序 10题 30分
01 #include <bits/stdc++.h> 02 using namespace std; 03 const int Maxn = 10005; 04 int n, b[Maxn]; 05 void mergesort(int *a, int l, int r) { 06 if (l == r) return; 07 int mid = l + r >> 1; 08 mergesort(a, l, mid), mergesort(a, mid + 1, r); 09 int i = l, j = mid + 1, cnt = 0; 10 while (i <= mid && j <= r) { 11 if (a[i] <= a[j]) b[++cnt] = a[i++]; 12 else b[++cnt] = a[j++]; 13 } 14 while (i <= mid) b[++cnt] = a[i++]; 15 while (j <= r) b[++cnt] = a[j++]; 16 for (i = l; i <= r; i++) a[i] = b[i - l + 1]; 17 } 18 19 int a[Maxn]; 20 int main(void) { 21 cin >> n; 22 for (int i = 1; i <= n; i++) cin >> a[i]; 23 mergesort(a, 1, n); 24 for (int i = 1; i <= n; i++) cout << a[i] << (i == n ? '\n' : ' '); 25 return 0; 26 }
该算法中参数 int *a 采用的不是传值方式。
01 #include <bits/stdc++.h> 02 using namespace std; 03 int i, j, k, n, m, f[10010], p1, p2, p3; 04 int find(int k) { 05 if (f[k] == k) return k; 06 return f[k] = find(f[k]); 07 } 08 int main() { 09 cin >> n >> m; // 假设 n, m 同量级 10 for (i = 1; i <= n; i++) f[i] = 1; 11 for (i = 1; i <= m; i++) { 12 cin >> p1 >> p2 >> p3; 13 if (p1 == 1) 14 f[find(p2)] = find(p3); 15 if (p1 == 2) { 16 if (find(p2) == find(p3)) 17 printf("Y\n"); 18 else 19 printf("N\n"); 20 } 21 } 22 return 0; 23 }
该算法中 p1 的作用是确定操作类型。
01 #include <bits/stdc++.h> 02 using namespace std; 03 int t, x[100], a[100]; 04 void work(int d, int i, int n) { 05 int k; 06 if (n == 1) { 07 for (k = 0; k < d; k++) 08 printf("%3d", a[k]); 09 printf("\n"); 10 } else for (k = i; k < t; k++) { 11 if (n % x[k] == 0) { 12 a[d] = x[k]; 13 work(d + 1, k, n / x[k]); 14 } 15 } 16 } 17 int main() { 18 int i, k, n; 19 cin >> n; 20 for (i = n; i > 1; i--) 21 if (n % i == 0) x[t++] = i; 22 work(0, 0, n); 23 return 0; 24 }
main() 函数里的 for 循环的作用是求出 n 的所有因数。
01 #include <iostream> 02 using namespace std; 03 const int SIZE = 100; 04 int x[SIZE], y[SIZE], f[SIZE]; 05 int n, i, j, max_f, ans; 06 int main() { 07 cin >> n; 08 for (i = 1; i <= n; i++) cin >> x[i] >> y[i]; 09 max_f = 0; 10 for (i = 1; i <= n; i++) { 11 f = ①; 12 for (j = 1; j <= n; j++) { 13 if (x[j] < x[i] && ②) 14 ③; 15 } 16 if ④ { 17 max_f = f[i]; 18 ⑤; 19 } 20 } 21 for (int i=1; i<=n; i++) cout << f[i] << endl; 22 cout << ans << endl; 23 return 0; 24 }
① 处应填 ( )。
01 #include <iostream> 02 #include <cstring> 03 using namespace std; 04 const int SIZE=25; 05 bool used[SIZE]; 06 int data[SIZE]; 07 int n, m, i, j, k; 08 bool flag; 09 10 int main() { 11 cin >> n >> m; 12 memset(used, false, sizeof(used)); 13 for (i=1; i<=m; i++) { 14 data[i] = i; 15 used[i] = true; 16 } 17 flag = true; 18 while (flag) { 19 for (i=1; i<=m-1; i++) 20 cout << data[i] << " "; 21 cout << data[m] << endl; 22 flag = ①; 23 for (i=m; i>=1; i--) { 24 ②; 25 for (j=data[i]+1; j<=n; j++) 26 if (!used[j]) { 27 used[j] = true; 28 data[i] = ③; 29 flag = true; 30 break; 31 } 32 if (flag) { 33 for (k=i+1; k<=m; k++) 34 for (j=1; j<= ④; j++) 35 if (!used[j]) { 36 data[k] = j; 37 used[j] = true; 38 break; 39 } 40 ⑤; 41 } 42 } 43 } 44 return 0; 45 }