一. 单选题（每题 2 分，共 30 分）

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

• 2
• 3
• 5
• 6

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

{{ select(2) }}

• void QuickSort(int a[][10], int n);
• void QuickSort(int a[5][], int m)
• void QuickSort(int a[][], int n, int m)
• void QuickSort(int ** a, int n, int m)

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

{{ select(3) }}

• 对象的⽣命周期开始时，会执⾏构造函数。
• 对象的⽣命周期结束时，会执⾏析构函数。
• 类的析构函数可以为虚函数。
• 类的构造函数可以为虚函数。

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

{{ select(4) }}

• n*(n+1)
• n*n
• n*(n-1)
• n*(n-1)/2

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

{{ select(5) }}

• 5
• 24
• 96
• 120

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

{{ select(6) }}

• n-1
• n
• n+1
• 最⼩⽣成树可能不存在

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

{{ select(7) }}

• a * b * sin(theta) / 2
• (a + b) * sin(theta) / 2
• a * b * cos(theta) / 2
• sqrt(a * a + b * b - 2 * a * b * cos(theta))

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

{{ select(8) }}

• $O(1)$
• $O(log(n))$
• $O(n)$
• $O(n^2)$

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

{{ select(9) }}

• $O(log(n))$
• $O(n)$
• $O(n * m)$
• $O(m * log(n))$

10. 下⾯程序的时间复杂度为（ ）。

{{ select(10) }}

• $O(n)$
• $O(a^n)$
• $O(log(n))$
• $O(log(n) * a)$

11. 下⾯程序的时间复杂度为（ ）。

    

{{ select(11) }}

• O(2^n)
• O(2^m * (n-m))
• O(C(n,m))
• O(m * (n-m))

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

{{ select(12) }}

• 
• 
• 
• 

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

{{ select(13) }}

• 12
• 18
• 36
• 42

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

{{ select(14) }}

• 3
• 6
• 11
• 12

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

{{ select(15) }}

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

二. 判断题（每题 2 分，共 20 分）

1. C++语⾔⾮常强⼤，可以⽤来求解⽅程的解。例如，如果变量x为double类型的变量，则执⾏语句x * 2 - 4 = 0;后，变量x的值会变为2.0。 {{ select(16) }}

• 对
• 错

2. ⼀个袋⼦中有3个完全相同的红⾊⼩球、2个完全相同的蓝⾊⼩球。每次从中取出1个，且不放回袋⼦，这样进⾏3次后，将取出的⼩球依次排列，则可能的颜⾊顺序有7种。 {{ select(17) }}

• 对
• 错

3. 杨辉三角，是⼆项式系数的⼀种三角形排列，在中国南宋数学家杨辉1261年所著的《详解九章算法》⼀书中出现，是中国数学史上的⼀项伟⼤成就
4. {{ select(18) }}

• 对
• 错

4. N个顶点的有向完全图（不带⾃环）有N*(N-1)/2条边。 {{ select(19) }}

• 对
• 错

5. 如果待查找的元素确定，只要哈希表的⼤⼩不⼩于查找元素的个数，就⼀定存在不会产⽣冲突的哈希函数。 {{ select(20) }}

• 对
• 错

6. 动态规划算法的时间复杂度⼀般为：必要状态的数量，乘以计算⼀次状态转移⽅程的时间复杂度。 {{ select(21) }}

• 对
• 错

7. 已知int类型的变量a、b和h中分别存储着⼀个梯形的顶边长、底边长和⾼，则这个梯形的⾯积可以通过表达式(a + b) * h / 2求得。

   {{ select(22) }}

• 对
• 错

8. 判断图是否连通只能⽤⼴度优先搜索算法实现。 {{ select(23) }}

• 对
• 错

9. 在N个元素的⼆叉排序树中查找⼀个元素，最好情况的时间复杂度是0(logN)。 {{ select(24) }}

• 对
• 错

10. 给定double类型的变量x，且其值⼤于等于，我们可以通过⼆分法求出

$$\sqrt{x}$$

的近似值

{{ select(25) }}

• 对
• 错