单选题

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) }}

• 代码的时间复杂度为0($n^2$)
• 代码的空间复杂度为0($n^2$)
• 空间复杂度已经最优
• 采⽤了动态规划求解

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) }}

• 1024
• 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

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

{{ select(16) }}

• 对
• 错

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

{{ select(17) }}

• 对
• 错

18 假设⼀棵完全⼆叉树共有 个节点，则树的深度为log(N)+1。( ) {{ select(18) }}

• 对
• 错

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

• 对
• 错

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

• 对
• 错

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

• 对
• 错

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

• 对
• 错

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

• 对
• 错

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

• 对
• 错

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

• 对
• 错