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

第 1 题 定义变量double x，如果下⾯代码输⼊为100，输出最接近 ( )。

{{ select(1) }}

• 0
• -5
• -8
• 8

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

{{ select(2) }}

• 
• 
• 
• 

第 3 题 下⾯代码可以⽤来求最长上升⼦序列（ LIS ）的长度，如果输⼊是：5 1 7 3 5 9，则输出是 ( )。

{{ select(3) }}

• 9 7 5 1 1 9
• 1 2 2 3 4 4
• 1 3 5 7 9 9
• 1 1 1 1 1 1

第 4 题 C++语⾔中，下列关于关键字static的描述不正确的是 ( ) 。 {{ select(4) }}

• 可以修饰类的成员函数。
• 常量静态成员可以在类外进⾏初始化。
• 若a是类A常量静态成员，则a的地址都可以访问且唯⼀。
• 静态全局对象⼀定在main函数调⽤前完成初始化，执⾏完main函数后被析构。

第 5 题 G是⼀个⾮连通⽆向图，共有28条边，则该图⾄少有 ( ) 个顶点。 {{ select(5) }}

• 6
• 7
• 8
• 9

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

{{ select(6) }}

• 3
• 4
• 5
• 6

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

• T的度为 1
• T的⾼为 4
• T有4个叶节点
• 以上说法都不对

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

{{ select(8) }}

• 代码的时间复杂度为
• 代码的空间复杂度为
• 空间复杂度已经最优
• 采⽤了动态规划求解

第 9 题 图的⼴度优先搜索中既要维护⼀个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？ ( ) {{ select(9) }}

• 双向栈
• 队列
• 哈希表
• 堆

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

{{ select(10) }}

• 7/8
• 1
• 1.5
• 2

第 11 题 学⽣在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成⼀个有向图G，有向边<U, V>表⽰课程U是课程V的先修课，则要找到某门课程C的全部先修课下⾯哪种⽅法不可⾏？ ( ) {{ select(11) }}

• BFS搜索
• DFS搜索
• DFS+BFS
• 动态规划

第 12 题 ⼀棵完全⼆叉树有2023个结点，则叶结点有多少个？ ( ) {{ select(12) }}

• 1024
• 1013
• 1012
• 1011

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

{{ select(13) }}

• O(n)
• O(e)
• O(n + e)
• O(n + 2 * e)

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

• BFS更快
• DFS更快
• BFS和 DFS⼀样快
• 不确定

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

{{ select(15) }}

• 4
• 3
• 2
• 1

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

16、1 题 ⼩杨这学期准备参加 GESP 的 7 级考试，其中有关于三角函数的内容，他能够通过下⾯的代码找到结束循环的角度值。 ( )

{{ select(16) }}

• 对
• 错

17、2 题 ⼩杨在开发画笔刷⼩程序（ applet ），操作之⼀是选中黄颜⾊，然后在下⾯的左图的中间区域双击后，就变成了右图。这个操作可以⽤图的泛洪算法来实现。 ( )

{{ select(17) }}

• 对
• 错

18、3 题 假设⼀棵完全⼆叉树共有个节点，则树的深度为。( ) {{ select(18) }}

• 对
• 错

19、4 题 给定⼀个数字序列A1 ，A2 ， A3 ， ... ， An，要求i和j（1<=i<=j<=n)，使Ai+…+Aj最⼤，可以使⽤动态规划⽅法来求解。 ( ) {{ select(19) }}

• 对
• 错

20、5 题 若变量x为double类型正数，则log(exp(x)) > log10(x)。( ) {{ select(20) }}

• 对
• 错

21、6 题 简单有向图有n个顶点和e条弧，可以⽤邻接矩阵或邻接表来存储，⼆者求节点u的度的时间复杂度⼀样。 ( ) {{ select(21) }}

• 对
• 错

22、7 题 某个哈希表键值x为整数，为其定义哈希函数H(x)=x%p，则p选择素数时不会产⽣冲突。 ( ) {{ select(22) }}

• 对
• 错

23、8 题 动态规划只要推导出状态转移⽅程，就可以写出递归程序来求出最优解。 ( ) {{ select(23) }}

• 对
• 错

24、9 题 ⼴度优先搜索（ BFS ）能够判断图是否连通。 ( ) {{ select(24) }}

• 对
• 错

25、10 题 在C++中，如果定义了构造函数，则创建对象时先执⾏完缺省的构造函数，再执⾏这个定义的构造函数。 ( ) {{ select(25) }}

• 对
• 错