1. 小杨要从A城到B城，⼜想顺路游览⼀番。他有两个选项：1、坐⾼铁路到C城游览，再坐⾼铁或飞机到B城；2、坐船到D城游览，再坐船、⾼铁或飞机到B城。请问小杨从A城到B城共有几种交通⽅案可以选择？（ ）。

   A. 2

   B. 3

   C. 5

   D. 6

   【答案】C

   【解析】本题可抽象为分类计数问题，应使用加法原理，而不是乘法原理。答案 为ACB的方案数2加上ADB的方案数3=5，选C。

2. 以下哪个函数声明是符合语法的 ，且在调⽤时可以将⼆维数组的名字作为实 际参数传递给形式参数 a ？ ( ) 。

   A. void QuickSort(int a[][10], int n);

   B. void QuickSort(int a[5][], int m)；

   C. void QuickSort(int a[][], int n, int m);

   D. void QuickSort(int ** a, int n, int m);

   【答案】A

   【解析】C++在函数中把数组作为参数进行传递时，只会传递数组的首地址，函数中如果想要通过首地址计算数组中任意一位元素所处的地址时，就需要知道第二维数组的长度，比如第二维数组长度为10时，a[1][3]的地址就是a[0][0]的地址+13，本题的选项中只有选项A给出了数组第二维长度，所以本题选A。

3. 下⾯有关C++类和对象的说法 ，错误的是（ ）。

   A. 对象的⽣命周期开始时 ，会执⾏构造函数。

   B. 对象的⽣命周期结束时 ，会执⾏析构函数。

   C. 类的析构函数可以为虚函数。

   D. 类的构造函数可以为虚函数。

   【答案】D

   【解析】对象的声明周期开始和结束时会分别执行构造函数和析构函数，选项A、 B正确。对于选项C、D，虚函数是指被virtual关键字修饰的成员函数，定义虚函数是为了允许用基类的指针来调用派生类的该函数。允许将析构函数定义为虚函数，是因为有使用“delete 基类指针”来销毁对象的需求，选项C正确。但对象构造时必须指定准确的类，不能使用基类名构造派生类的对象，没有将构造函数定义为虚函数的需要，选项D错误。

4. 使⽤邻接矩阵表达 n 个顶点的有向图 ，则该矩阵的⼤⼩为（ ）。

   A. $n× (n+1 )$

   B. $n×n$

   C. $n× (n-1 )$

   D. $n× (n- 1 )/2$

   【答案】B

   【解析】邻接矩阵的行列均为[0~n-1],所以矩阵的大小为$n*n$，本题选B。

5. 5 位同学排队，其中⼀位同学不能排在第⼀，则共有多少种可能的排队⽅式？ （ ）。

   A. 5

   B. 24

   C. 96

   D. 120

   【答案】C

   【解析】按照第1,2,3,4,5位的顺序依次安排同学，某位同学不能在第一位，所以第1位有4种安排方法，第二位可以从剩余的4名同学中选一位，有4种方法，依次类推，第3,4,5各有3,2,1种，总方案数为$4*4*3*2*1=96$，选C。

6. ⼀个⽆向图包含 n 个顶点 ，则其最⼩⽣成树包含多少条边？（ ）

   A. n- 1

   B. n

   C. n + 1

   D. 最⼩⽣成树可能不存在。

   【答案】D

   【解析】n个顶点组成的树包含n-1条边，但是题目没有保证图连通，所以可能 不存在最小生成树，选D。

7. 已知三个 double 类型的变量a、b和theta分别表⽰⼀个三角形的两条边长及⼆者的夹角（弧度），则下列哪个表达式可以计算这个三角形的⾯积？（ ）。

   A. $a*b*sin(theta) / 2$

   B. $(a +b)*sin(theta) / 20$

   C. $a*b*cos(theta) / 2$

   D. $sqrt(a * a + b * b- 2 * a* b * cos(theta))$

   【答案】A

   【解析】若△ABC中,已知两边a.b和它们的夹角theta,作边a上的高h. 则 $S=(1/2)ah$,而 $h/b=sin(theta)$,即$h=b*sin(theta)$ ∴$S=(1/2)absin(theta)$选 A。

8. 对有 n 个元素的⼆叉排序树进⾏中序遍历，其时间复杂度是（ ）。

   A. $O(1)$

   B. $O(log(n))$

   C. $O(n)$

   D. $O(n^2)$

   【答案】C

   【解析】树的遍历过程需要对每个元素访问一次，因此时间复杂度为$O(n)$，选择C。

9. 假设输⼊参数m和n满⾜$m≤n$，则下⾯程序的最差情况的时间复杂度为（ ）。

   A. $O(log(n))$

   B. $O(n)$

   C. $O(n × m)$

   D. $O(m × log(n)$

   【答案】A

   【解析】本题代码为辗转相除法，复杂度为$O(log(n))$。最差情况，输入为斐波那契数列的相邻两项时，循环次数为输入在数列中的位置。选A。

10. 下⾯程序的时间复杂度为（ ）。 A. $O(n)$

    B. $O(a^n)$

    C. $O(log(n))$

    D. $O(log(n) × a)$

    【答案】C

    【解析】本题代码为快速幂，复杂度为$O(log(n))$。通过观察可得该函数的时间复 杂度只与n相关，假设为$T(n)$，则$T(n)=T(n/2)+$常数，求解可得上述时间复杂度。选C。

11. 下⾯程序的时间复杂度为（ ）。 A. $O(2^n)$

    B. $O(2^m × (n- m))$

    C. $O(C(n, m))$

    D. $O(m × (n- m))$

    【答案】D

    【解析】本题代码是在计算$C[n][m]$,使用了递归的写法并加上了记忆化搜索，可以通过画图来看所有被访问到的二维数组个数，以$n=6，m=2$为例，可以发现访问的元素个数为$n*m-m*m$，本题选D。

12. 下⾯的程序使⽤出边的邻接表表达有向图，则下列选项中哪个是它表达的图？（ ）。

A.

B.

C.

D.

【答案】B

【解析】结构体edge里的next指向的是下一条边，Node里的first指向的是每 个点的第一条边，所以0号点指向1号点，1号点指向2,3号点，2号点指向3号点，3号点指向0号点，选B。

13. 下⾯程序的输出为（ ）。

    A.12

    B. 18

    C. 36

    D. 42

    【答案】B

    【解析】代码中a,b,h的取值范围均为[1,10]，要$(a+b)*h=20$,那么可能的h有 1,2,4,5,10，h 为 1 时，$(a+b)=20$,有 1 种方法，h为2时，$(a+b)=10$,有9种方案， 依次计算出h为4,5,10时，$(a+b)$的方案数依次为4,3,1，总方案数为 $1+9+4+3+1=18$,选 B。

14. 下⾯程序的输出为（ ）。

    A. 3

    B. 6

    C. 11

    D. 22

    【答案】A

    【解析】代码中要求a，b，c都是正整数，满足$a+b+c<=30$且,符合要求的a,b,c 有3 4 5；5 12 13；6 8 10共3种，选A。

15. 下⾯的程序中 ，⼆维数组 h 和 v 分别代表如下图所⽰的⽹格中的⽔平边 的时间消耗和垂直边的时间消耗。 程序使⽤动态规划计算从左下角到右上角的 最⼩时间消耗 ，则横线处应该填写下列哪个选项的代码？（ ）。 A.dis[i][j] = min(dis[i- 1][j] + v[i- 1][j], dis[i][j- 1] + h[i][j- 1]);

    B.dis[i][j] = min(dis[i- 1][j] + h[i- 1][j], dis[i][j- 1] + v[i][j- 1]);

    C.dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);

    D.dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

    【答案】C

    【解析】观察到11行的输出为$dis[y][x]$,而我们枚举的范围是$<y$与$<x$，所以第 10 行计算的肯定是$dis[i+1][j+1]$，排除AB，接着看C选项第一个转移，$dis[i][j+1]$， 说明这里是从第一维转移过来，而第5行也是从第一维转移过来的，使用的是v 数组，选项C正确，排除D选项，本题选C