声明：整个文档为markdown格式，放到公众号中部分格式无法正确转换，有需要的可以留言索取md或pdf格式。

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 八进制数$ (7042)8$ 转化为十六进制数是（ ）A. $(3521){16}$ B. $(F22){16}$ C. $(E22){16}$ D.$(111000100010)_{16}$
2. 设栈 S 和队列 Q 初始状态为空，元素 a1, a2, ..., a6 依次通过栈 S， 一个元素出栈后就进入队列Q，若出队的顺序分别是 a2，a1，a3，a6， a5，a4则栈 S 的容量至少是（ ）   A. 2 B. 5 C. 3 D.4
3. 逻辑表达式（ ）的值与变量 A 的真假无关。   A. (A ∧ B) ∨ (¬A ∧ B) B. (A ∨ B) ∧ ¬A
      C. (A ∨ B) ∧ ¬B D.(A ∨ B) ∧ ¬A ∧ B
4. n 是一个三位数,那 n 的十位数为（ ）。   A. (n%100)/10 B. (n/100)%10 C. (n/100)%100 D.(n%10)/10
5. 基于比较的排序时间复杂度的下限是（ ），其中 n 表示待排序的元素个数。   A. $O(n^2)$ B. $O(nlogn)$ C. $O(n)$ D.$O(logn)$
6. 完全二叉树共有 2N-1 个结点，则它的叶节点数是（ ）。   A. N-1 B. 2N C. 2*N-1 D.N
7. 45 和 30 的最小公倍数是（ ）   A. 45 B. 30 C. 90 D.180
8. 一棵 7 节点二叉树的中序遍历为 ABDGECF ，先序遍历为DBACEGF ，后序遍历为（ ）   A. ABCDEFG B. DGBEFAC C. GBEACFD D. ABGEFCD
9. 一个 n 个顶点的强连通图最少有几条边（ ）   A. n B. n+1 C. n-1 D. D. n*(n-1)
10. 若有如下程序段，其中 s、a、b、c 均已定义为整型变量，且 a、c 均已赋值（c > 0）

s = a;for (b = 1; b <= c; b++) s = s - 1;

则与上述程序段功能等价的赋值语句是（ ）。

A. s = a - b; B. s = s - c; C. s = a - c; D.s = b - c;

A. 所有顶点的度数之和不一定等于边数的 2 倍

B. 所有顶点的度数之和等于边数的 2 倍

C. 在有向图中顶点的入度之和等于出度之和

D. 任意一个图一定有偶数个度数为奇数的点

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 T，错误填 F；除特殊说明外，判断题1.5 分，选择题 3 分，共计 40 分）

阅读下面程序，完成第16~21题。

#includeusing namespace std;typedef long long ll;const int mod = 2048;ll c,n;ll func(ll x, ll mi){  ll res = 1;  while (mi) {  if (mi&1) res=(res*x)%mod;  x = (x*x)%mod;  mi>>=1;  }  return res;}intmain(){  cin>> n>> c;  if (n ==3){    printf(”%lld”,c*(c-1));    return 0;  }  ll ans=((func(c-1,n)+(c-1)*func(-1,n))%mod+mod)%mod;  cout << ans;  return 0;}

18.（2分）若输入为 4 4 ，则输出为 78 。（ ）

阅读下面程序，完成第 22~27 题。

#includeusing namespace std;intmain() {int num = 0;	cin >>num;//保证num>= 100,且在int范围内int max_primedivisor = 0;int cnt = 1;for (int i= 2; i * i <= num; i++) {if (num % i == 0) {            int tmp = 1;            while (num % i == 0) num /= i, tmp++;            max_primedivisor = max(max_primedivisor, i);            cnt *= tmp;		}	}	max_primedivisor = max(max_primedivisor, num);if (num > 1) cnt *= 2;	cout << max_primedivisor <<” ”<< cnt << ”\n”;return 0;}

A. O(log num)

B. $O( \sqrt{num} )$

C. O(num)

D. $O( num\sqrt{num} )$

阅读下面程序，完成第 28 ~33 题。

#includeusing namespace std;#define maxn 110struct node {int r,c;int A[maxn][maxn];} G[maxn];voidchange(int id){int B[maxn][maxn];for(int i=1;i <= G[id].r; i++){for(int j=1;j<= G[id].c; j++){		B[j][i] = G[id].A[i][j];	}}swap(G[id].r,G[id].c);for(int i=1;i<= G[id].r; i++){for(int j=1;j<= G[id].c;j++){		G[id].A[i][j] = B[i][j];	}}}voidAdd(int a,int b){for(int i=1;i<= G[a].r;i++){for(int j=1;j<= G[a].c; j++){		G[a].A[i][j] += G[b].A[i][j];	}}}voidSubtract(int a,int b){for(int i=1;i<=G[a].r; i++){for(int j=1;j<= G[a].c; j++){		G[a].A[i][j] -= G[b].A[i][j];	}}}voidMultiply(int a,int b){int sum[maxn][maxn];for(int i=1;i<=G[a].r; i++){for(int j=1;j<= G[b].c; j++){for(int k=1;k<= G[a].c;k++){			sum[i][j]= G[a].A[i][k]*G[b].A[k][j];		}	}}G[a].c = G[b].c;for(int i=1;i<=G[a].r;i++){for(int j=1;j<=G[a].c;j++){		G[a].A[i][j]= sum[i][j];	}}}voidprint1(int id){for(int i=1;i <= G[id].r; i++){for(int j=1;j<= G[id].c; j++){printf(”%d%c”,G[id].A[i][j],j < G[id].c ?' ':'\n');	}}}voidprint2(char str[]){printf(”%s\n”,str);}intmain(){int n, m;scanf(”%d %d”,&n,&m);for(int k=1;k<=n; k++){scanf(”%d %d”,&G[k].r,&G[k].c);for(int i=1;i<= G[k].r; i++){for(int j=1;j<=G[k].c;j++){scanf(”%d”,&G[k].A[i][j]);		}	}}for(int i=1;i <= m;i++){int op,x,y;scanf(”%d%d%d”,&op,&x,&y);if(op ==0){change(x);change(y);if(i % 2){print1(x);		}else {print1(y);		}	}else if(op==1){if(G[x].r!=G[y].r|| G[x].c!= G[y].c){print2(”error1”);continue;		}Add(x,y);print1(x);	}else if(op==2){if(G[x].r != G[y].r || G[x].c != G[y].c){print2(”error2”);continue;		}Subtract(y,x);print1(y);	}else {if(G[x].c != G[y].r){print2(”error3”);continue;		}Multiply(x,y);print1(x);	}}return 0;}

提示:

矩阵转置：将第 i 行 ，变为第 i 列，如：

1 2 3 1 4 7

4 5 6 --> 2 5 8

7 8 9 3 6 9

矩阵加减法：要保证两个矩阵的 数和列数相同，且相同位置相加减， 如:

1 4 7 1 2 3 2 6 10

2 5 6 + 4 5 6 = 6 10 12

3 6 9 7 8 9 10 14 18

矩阵乘法：矩阵A×矩阵B=矩阵C，要保证A的列数和B的行数相同。则 $C_{i,j} =\sum{k=1}^{第i行的元素个数} A{i,k}×B_{k,j}$，如:

1 4 7 1 2 3 66 78 90

2 5 6 x 4 5 6 = 64 77 90

3 6 9 7 8 9 90 108 126

29.（2分）第 85~88 行不能预防第 x 和第 y 个矩阵不能相加的情况。

2 2

3 3

1 2 3

4 5 6

7 8 9

3 3

1 4 7

2 5 6

3 6 9

0 1 2

1 1 2

则正确输出为：

A.

1 2 3

4 5 6

7 6 9

2 6 10

6 10 14

10 12 18

B.

1 4 7

2 5 8

3 6 9

error1

C.

1 4 7

2 5 8

3 6 9

66 64 90

78 77 108

90 90 126

D.

1 4 7

2 5 8

3 6 9

2 6 10

6 10 14

10 12 18

三、完善程序（单选题，每小题3分，共计30分） 阅读下面题目，完成第 34 ~38 题。

输入月份 m(1≤m≤12)，按一定格式打印 2015 第 m 月的月历。例如， 2015 年一月的月历打印效果如下（第一列为周日）：

#includeusing namespace std;const int dayNum[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};int m, offset,i;intmain(){  cin >> m;  cout <<”s\tM\tT\tW\tT\tF\ts” << endl;//'\t'为tab制表符  __①__;  for(i=1;i<m; i++)    offset = __②__;  for (i =0;i < offset; i++)    cout << '\t';  for(i=1;i <= __③__;i++){    cout << __④__;  if(i==dayNum[m]||__⑤__ == 0)			cout << endl;  else    cout <<'\t';  }return 0;}

A.  offset=0

B.  offset=1

C. offset=3

D. offset=4

A. dayNum[i]

B. offset+dayNum[i]

C. (offset+dayNum[i]) % 7

D.(offset+dayNum[i - 1]) % 7

36.③处应填（ ）

A. m

B. dayNum[m]

C. offset

D. offset+dayNum[i]

37.④处应填（ ）

A. i

B. i+1

C. i - 1

D. dayNum[i]

38.⑤处应填（ ）

A. offset+i

B. (offset+i) % 7

C. offset+dayNum[i]

D.(offset+dayNum[i]) % 7

阅读下面题目，完成第 39 ∼ 43 题。

给出一张 n 节点 m 条边的有向图，求出该图的一个拓扑排序，若无拓扑排序输出 −1

**输入：**第一行两个正整数 n, m 表示点数和边数。接下来 m 行，每行三个正整数 x, y 表示节点 x− > y 之间有一条边。

**输出：**一个拓扑序：按拓扑序输出点的编号。若拓扑序不唯一，输出任意一个均可。若无拓扑序，输出 −1。

#include#include#include#define N 200020using namespace std;int n, m;vector G[N];int q[N],hd, tl;int du[N];int ans[N], tot;void topo() {	hd =1,tl=0;for(int i=1;i <= n; i++)if(__(1)__)q[++tl]=i;while(hd <= tl){int u= q[hd++];		ans[++tot]= u;for(int i=0;__(2)__;i++){int v= G[u][i];			du[v]--;if(!du[v])__(3)__;		}	}if(tot != n) puts(”-1”);else {for(int i=1;i<=n; i++)printf(”%d ”,ans[i]);	}}int main(){	scanf(”%d%d”,&n,&m);for(int i=1;i<= m; i++){int x,y;		scanf(”%d%d”,&x,& y);		__(4)__;		__(5)__;	}	topo();}

A. du[i]

B. q[i]

C. hd <= tl

D. !du[i]

A. i <= n

B. i < n

C. i < G[u].size()

D. i <= G[u].size()

A. q[++tl] = v

B. q[tl++] = v

C. q[++hd] = v

D.q[hd++] = v

A. G[y].push_back(x)

B. G[x].push_back(y)

C. G[x].push(y)

D.G[y].push(x)

A. G[y].push_back(x)

B. G[y].push(x)

C. du[y]++

D. du[x]++

答案速览

模拟1：

1~5  CCAAC     6~10 DCDAC    11~15 CADCA     16~20 TTFTC

21~25 CFFBD    26~30 BADTFT    31~35 FCDDC     36~40 BABDC 

41~43 ABC

答案解析

1. C。简单的进制转换。
2. C。模拟栈的行为，可以发现最后需要保持 a4, a5, a6同时处于栈中。
3. A。代入计算即可。
4. A。可以通过模拟计算的方式来验证。A 选项中两个运算首先模去 然后除去了个位，剩下的就是原来的十位
5. C。若数组是有序数组，如冒泡排序的基于比较的排序时间复杂度 即为 O(n)，由于遍历元素就需要 O(n) 的时间，所以不可能存在更低 的下界。
6. D。当 N=1 时有一个叶子结点，之后的 N 每增加一都可以理解为 是把原先的一个叶子结点变成了两个叶子节点。所以叶子结点数为 N 。
7. C。45 和 30 的最小公倍数是 90。
8. D。根据先序遍历找当前子树的根，根据中序遍历再把当前子树拆 成左右子树，递归建树，然后进行后序遍历
9. A。边数最少的强连通图即形成一个“环”。此时边数最小，为 n
10. C。经典 for 循环减法。
11. C。先不考虑车的限制，方案数为 $2^7$，接下来考虑非法情况的数量， 7 人乘同一辆车的方案数 2，6人乘同一辆车的方案数 $C_7^1 × 2 $， 5 人 乘同一辆车的方案数 $C_7^2 × 2$ 答案为 $2^7-2-C_7^1 × 2-C_7^2*2=70 $
12. A。每条边贡献两个度数，所以所有顶点度数之和是边数的两倍。
13. D。可以枚举 9 的数组的个数来分别求解: $C_6^19^5+?C_6^29^4+C_6^39^3+C_6^49^2+C_6^59^1+C_6^6 $
14. C。二叉树是非线性结构。栈、队列和线性表是线性结构。
15. A。先确定剩下 5 个人的位置 $A_5^5$ ,然后将甲乙丙三人插到这五个人 的队列中$A_6^3$

16-21题该段代码是使用快速幂计算某个数的指数幂：$$ans=\left{\begin{aligned}

c*(c-1)  &  & n=3 ((c-1)^n+(c-1)*(-1)^n)mod 2048  &  & n为其他\end{aligned}\right.$$

1. T。
2. T。
3. F。
4. T。
5. C。
6. C。

22-27题：该段代码是在枚举 num 中所包含的质因数，找到最大的质因数，并且 求解出唯一分解中每个质数的指数+1的乘积。因为大小超过 $\sqrt {num}$ 的 质因数只可能有一个，所以这⾥是通过枚举所有小于 $\sqrt {num}$ 的数字并且判断是否为因数的方法来找质因数的。在最坏情况下，num 本身是 质数，需要枚举  $\sqrt {num}$ 次。在最好情况下，num 是 2 的幂次，只需 要循环 log num 次即可。

1. F。
2. F。
3. B。
4. D。
5. A。
6. D。

28.T。根据数组的大小判断。

29.F。第 85 ∼ 88 行就是预防第 x 和第 y 个矩阵不能相加的情况：两 个矩阵存在行数或列数不相等。

30.T。函数 void Multiply(int a, int b) 的功能是计算第 a 个矩阵乘以 第 b 个矩阵的结果。

31.F。程序借助了int B[maxn][maxn];，因此交换后不影响正确性。

32.C。根据矩阵相乘的规则，可以确定答案为 C。

33.D。 读代码后，这个题先转置，然后和样例的数据一样了。

题 1: 这道题主要是对输出的控制部分。我们主要需要控制的就是需要知道 第一天是星期几以及什么时候要换行。在这段代码中，我们使用offset 来解决了这个问题。通过这个变量来这个月的第一天是星期一的后几 天。从题目中给的例子中可以得知，一月份空了4天，所以初始值应该 是4，之后根据每月的天数计算在第 m 个月时的偏移即可。

34.D。

35.C。

36.B。

37.A。

38.B。

题 2: 这段代码实现了拓扑排序，而且跟上道题的代码风格相似，通过数组 的方式维护了队列。拓扑排序中要注意的就是对节点入度 du的维护， 只有入度为0的点才可以被加入到队列（拓扑序）中。对于入度的维护 需要从一开始加边就开始维护，之后每次删点后也要判断涉及到的点 的入度是否为 0。

39.D。

40.C。

41.A。

42.B。

43.C。