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

1. 定义变量 double x ，如果下面代码输入为 100 ，输出最接近( )。

A、0

B、-5

C、 -8

D、 8

【答案】：B

【解析】：log10(x)表示 10 的多少次方是 x，log2(x)表示 2 的多少次方是 x，这里的 x 是输入的 100，所以，log10(100)=2，又因为 26=64，所以 log2(100)是 6.多，两者作差，约为-4.多，选 B。

2. 对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为( )。

【答案】：D 【解析】：首先看代码，s 数组是前缀和数组，f 数组是dp 数组，初始化f 数组为正无穷，只有 f[i][i]=0（1<=i<=n）的值为 0，接着进行了区间dp，i 和j 分别是区间 dp 的两个端点，k 是枚举的分界点，k 的取值范围是[i,j)，所以选项C 错误，根据第 15 行转移方程，发现后面的 s[j]-s[i-1]是 a[i]+a[i+1]+…+a[j]的和，且与k无关，可以单独拎出来，所以转移方程为选项 D。选项 A,B 的错误点在于 f(i,j)的初始值为正无穷，所以f(i,j)是不参与转移方程的。

3. 下面代码可以用来求最长上升子序列（LIS）的长度，如果输入是： 5 1 7 3 5 9 ，则输出是( )。

A、 9 7 5 1 1 9

B、 1 2 2 3 4 4

C、1 3 5 7 9 9

D、 1 1 1 1 1 1

【答案】：B

【解析】：题目已经提示我们这是在求最长上升子序列，f 数组的含义是以i 结尾的最长上升子序列长度，ans 是整个序列的最长上升子序列长度，代码中先依次输出了 f[1],f[2],…,f[n],最后再输出 ans，接着我们可以进行手算，1 7 3 5 9 序列的f 值分别为 1,2,2,3,4,ans=4，所以正确答案为 B。

4. C++语言中，下列关于关键字 static 的描述不正确的是( )。

A、可以修饰类的成员函数。

B、 常量静态成员可以在类外进行初始化。

C、 若 a 是类 A 常量静态成员，则 a 的地址都可以访问且唯一。

D、 静态全局对象一定在 main 函数调用前完成初始化，执行完 main 函数后被析构。

【答案】：C

【解析】：static 是静态意思，可以修饰成员变量和成员方法，static 修饰成员变量表示该成员变量在内存中只存储一份，可以被共享访问，修改。选项C 中a 的地址都可以访问是不对的，所以本题选 C。

5. G 是一个非连通无向图，共有 28 条边，则该图至少有( )个顶点。

A、 6

B、7

C、 8

D、9

【答案】：D

【解析】：注意到题目里说的是非连通无向图，那么在同样的点数n 下，为了有尽量多的边，可以分为两张连通图，一张 n-1 个点的完全图，另一张只有单独一个点，手算后可以发现，8 个点的完全图有 8*7/2=28 个点，正好满足题目要求，所以总点数为 9 个，选 D。

6. 哈希表长31，按照下面的程序依次输入 4 17 28 30 4 ，则最后的 4 存入哪个位置？（ ）

A、 3

B、4

C、5

D、 6

【答案】：D

【解析】：题目提示我们这是哈希表，根据代码，发现是按照%13 进行哈希并且在发生冲突的情况下， 对应放到下一个位置，我们依次计算17 28 30 4 会放置在什么位置，17 放置在 4,28 放置在 2,30 本来放置在 4，但是发生冲突，最终放置在 5,4 本来放置在 4，但是 4 和 5 都被占用了，所以最终放置在6，选D。

7. 某二叉树T的先序遍历序列为： {A B D F C E G H} ，中序遍历序列为： {B F D A G E H C} ，则下列说法中正确的是( )。

A、 T的度为1

B、T的高为4

C、 T有4个叶节点

D、 以上说法都不对

【答案】：B

【解析】：先序遍历是根左右，中序遍历是左根右，首先可以根据先序遍历和中序遍历画出完整的树，如下图： 所以正确答案为 B。

8. 下面代码段可以求两个字符串 s1 和 s2 的最长公共子串（LCS），下列相关描述不正确的是（ ）。

A、 代码的时间复杂度为$O(n^2)$

B、代码的空间复杂度为$O(n^2)$

C、空间复杂度已经最优

D、采用了动态规划求解

【答案】：C

【解析】：题目告诉我们代码是在求解最长公共子串，代码中使用了双重for 循环，且循环范围为[1~n1]以及[1~n2]，所以选项 A 正确，使用了二维数组dp，两维的长度也均为字符串长度，所以选项 B 正确，空间复杂度还可以使用滚动数组进一步优化为 O(n)，所以选项 C 错误，本题选 C，选项 D 正确，代码中使用的正是动态规划算法。

9. 图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？( )

A、 双向栈

B、 队列

C、队列

D、堆

【答案】：B

【解析】：图的广度优先搜索是从若干点出发，依次向外进行逐层扩展的算法，使用队列存放待遍历节点，本题选 B。

10. 对关键字序列 {44，36，23，35，52，73，90，58} 建立哈希表，哈希函数为 h(k)=k%7 ，执行下面的Insert 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为( )。

A、 7/8

B、 1

C、1.5

D、2

【答案】：C

【解析】：代码采用链地址法来存储哈希，即将所有哈希地址相同的记录都链接在同一链表中，哈希方式为%7，我们依次对每个元素进行判断：44，36，23，35，52，73，90， 58，每个数字的哈希地址分别是 2,1,2,0,3,3,6,2，即哈希值为0~6的元素个数分别有 1,1,3,2,0,0,1，对于之前的 8 个数字，它们查找成功的次数分别是 1,1,2,1,1,2,1,3，总次数为 12 次，平均次数=12/8=1.5 次，答案为C。

11. 学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 G ，有向边 <U, V> 表示课程 U 是课程 V 的先修课，则要找到某门课程 C 的全部先修课下面哪种方法不可行？( )

A、 BFS搜索

B、DFS搜索

C、DFS+BFS

D、动态规划

【答案】：D

【解析】：设一棵完全二叉树有 k 层，则前 k-1 都是满二叉树，第k 层的节点需要从左往右排列，那么第 1 层有 1 个节点，第 2 层有 2 个节点，第3 层有4个节点。。。第 9 层有 512 个节点，此时总节点个数为 1023，第10 层放置剩余的1000 个节点，那么叶节点个数为第 10 层的 1000 个节点，再加上第9 层除去被第 10 层消耗的 500 个节点外剩余的 12 个节点，总共为1012 个，选C。也可以根据完全二叉树的节点编号性质来计算，即：第 2023 号结点的双亲是最后一个非叶结点，序号是 2023/2=1011，所以叶节点个数为：2023-1011=1012。

12. 一棵完全二叉树有 2023 个结点，则叶结点有多少个？( )

A、 1024

B、 1013

C、 1012

D、 1011

【答案】：C

【解析】：

13. 用下面的邻接表结构保存一个有向图 G ， InfoType 和 VertexType 是定义好的类。设 G 有 n 个顶点、e 条弧，则求图 G 中某个顶点 u （其顶点序号为 k ）的度的算法复杂度是( )。

A、 $O(n)$

B、$O(e)$

C、 $O(n + e)$

D、 $O(n +2*e)$

【答案】：B

【解析】：代码中使用了邻接表来存储边的信息，查找某个点的度时需要计算出度和入度。出度直接从该点出发，遍历该点出发的边即可。同时查询入度，可以在反图上进行类似操作，总复杂度为 O(e),选 B。也可以遍历整个邻接表，包含点顶点 u 的弧的数目就是该顶点的度。

14. 给定一个简单有向图 G ，判断其中是否存在环路的下列说法哪个最准确？( )

A、 BFS更快

B、 DFS更快

C、 BFS和DFS一样快

D、 不确定

【答案】：D

【解析】：对于不同的图，BFS 和 DFS 的效率也不一样，有可能DFS更快，也有可能 BFS 更快，所以本题正确答案为 D。

15. 从顶点 v1 开始遍历下图 G 得到顶点访问序列，在下面所给的 4 个序列中符合广度优先的序列有几个？( ) {v1 v2 v3 v4 v5} ， {v1 v2 v4 v3 v5} ， {v1 v4 v2 v3 v5} ， {v1 v2 v4 v5 v3}

A、 4

B、 3

C、 2

D、 1

【答案】：B

【解析】：广度优先遍历会首先搜索和 s 距离为 k 的所有顶点，然后再去搜索和s距离为 k+1 的其他顶点，所以第 1 个序列不是广度优先搜索的序列，因为v3和v1 的距离超过了 v4 和 v1 的距离，但是序列中 v3 确排在v4 前面，其余3个序列都是广度优先搜索的序列，本题选 B。