试卷总分：100分
选择题 15题 30分
阅读程序 17题 40分
完善程序 10题 30分
01 #include <iostream> 02 #include <cmath> 03 using namespace std; 04 bool IsPrime(int num) { 05 for (int i=2; i<=sqrt(num); i++) { 06 if (num % i == 0) return false; 07 } 08 return true; 09 } 10 int main() { 11 int num = 0; 12 cin >> num; 13 if (IsPrime(num)) cout << "YES" << endl; 14 else cout << "NO" << endl; 15 return 0; 16 }
输入 97 时，输出为 NO。
01 #include <bits/stdc++.h> 02 using namespace std; 03 const int mod = 2048; 04 long long c,n; 05 long long kasumi(long long x,long long mi) { 06 long long res=1; 07 while (mi) { 08 if (mi & 1){ 09 res = (res * x) % mod; 10 } 11 x = (x * x) % mod; 12 mi >>= 1; 13 } 14 return res; 15 } 16 int main() { 17 cin >> n >> c; 18 if (n == 3) { 19 printf("%lld", c * (c - 1)); 20 return 0; 21 } 22 long long ans = (kasumi(c-1,n) + (c-1) * kasumi(-1,n)) % mod + mod; 23 cout << ans << endl; 24 return 0; 25 }
将第 9 行和第 11 行中的圆括号去掉，程序输出不变。
01 #include <cstdio> 02 int n,r,num[10000]; 03 bool mark[10000]; 04 void print() { 05 for (int i=1; i<=r; i++) 06 printf("%d ", num[i]); 07 printf("\n"); 08 } 09 void search(int x) { 10 for (int i=1; i<=n; i++) 11 if (!mark[i]) { 12 num[x] = i; 13 mark[i] = true; 14 if (x == r) print(); 15 search(x + 1); 16 mark[i] = false; 17 } 18 } 19 int main() { 20 scanf("%d%d", &n, &r); 21 search(1); 22 }
程序结束时，对任意 1 ≤ i ≤ n，都有 mark[i] = 0。
Kruskal 求最小生成树的思想：首先将 n 个点看作 n 个独立的集合，将所有边排序（从小到大）。然后按排好的顺序枚举每一条边，判断这条边连接的两个点是否属于同一集合。若不属于同一集合，则将这条边加入最小生成树，并将两个点所在的集合合并为一个集合。若属于同一集合，则跳过。直到找到 n－1 条边为止。
01 #include <iostream> 02 #include <algorithm> 03 using namespace std; 04 struct point { int x, y, v; } a[10000]; 05 int cmp(const point &a, const point &b) { 06 if ( ① ) return 1; 07 return 0; 08 } 09 int fat[101]; 10 int father(int x) { 11 if (fat[x] != x) return fat[x] = ②; 12 return fat[x]; 13 } 14 void unionn (int x, int y) { 15 int fa = father(x), fb = father(y); 16 if (fa != fb) fat[fa] = fb; 17 } 18 int main() { 19 int i, j, n, m, k=0, ans=0, cnt=0; 20 cin >> n; 21 for (i=1; i<=n; i++) 22 for (j=1; j<=n; j++) { 23 cin >> m; 24 if (m != 0) { 25 k++; a[k].x=i; a[k].y=j; a[k].v=m; 26 } 27 } 28 sort(a+1, a+1+k, ③); 29 for (i=1; i<=n; i++) fat[i] = i; 30 for (i=1; i<=k; i++) { 31 if (father(a[i].x) != ④) { 32 ans += a[i].v; 33 unionn(a[i].x, a[i].y); 34 cnt++; 35 if ( ⑤ ) break; 36 } 37 } 38 cout << ans << endl; 39 return 0; 40 }
① 处应填 ( )。
欧拉路径问题是指从图中的一个顶点出发，是否能够一次性不回头地走遍所有的边（一次且仅一次）。算法代码如下。
01 #include <iostream> 02 using namespace std; 03 int G[5][5]; 04 int visited[5][5]; 05 int n = 5; 06 void euler(int u) { 07 for (int v=0; v < n; v++) { 08 if (G[u][v] && ①) { 09 cout << u << "->" << v << endl; 10 visited[u][v] = visited[v][u] = ②; 11 ③ 12 } 13 } 14 } 15 int main() { 16 G[1][2] = G[2][1] = G[1][3] = ④ = 1; 17 G[2][4] = G[4][2] = G[3][4] = ⑤ = 1; 18 euler(1); 19 return 0; 20 }