摘要：已知小写字母b的ASCII码为98，下列C++代码的输出结果是。

1、已知小写字母b的ASCII码为98，下列C++代码的输出结果是。

A. b

B. c

C. 98

D. 99

【答案】B

【考纲知识点】语法知识，ASCII码

【解析】在C++中，字符在计算机中是整数存储，小写字母b的ASCII码为98，对a进行自增操作时，其ASCII码增加到99，程序输出的是ASCII码值为99的字符，即小写字母c

2、已知a为int类型变量 ，下列表达式不符合语法的是。

A. &a + 3

B. +a & 3

C. a - - 4

D. a++3

【答案】D

【考纲知识点】语法知识， 自增运算符

【解析】a++3是语法错误，因为a++作为一个整体，其结果不能直接与其它数值进行连接。

3、下列关于C++语言中指针的叙述 ，不正确的是。

A.指针变量中存储的是内存地址。

B.指针变量指向的内存地址不⼀定能够合法访问。

C.结构类型中的指针成员不能指向该结构类型。

D.定义指针变量时必须指定其指向的类型。

【答案】C

【考纲知识点】语法知识，指针

【解析】结构体类型中的指针成员是可以指向该结构类型的，常见操作如链表。

4、下列关于C++类的说法 ，错误的是。

A.将C++类对象通过值传递给函数参数时 ，会⾃动调用复制构造函数。

B.将⼀个类的对象赋值给该类的另⼀个对象时 ，不会⾃动调用构造函数。

C.定义C++类对象时 ，⼀定会调用默认构造函数。

D.构造派⽣类的对象时 ，⼀定会调用基类的构造函数。

【答案】C

【考纲知识点】语法知识

【解析】如果类中定义了其他构造函数（如有参数的构造函数）但没有定义默认构造函数，且在创建对象时没有提供初始化参数，则不会调用默认构造函数，甚至可能导致编译错误。

例如：

class MyClass {

public:

MyClass(int value) : m_value(value) {}

private:

int m_value;

};

在这个例子中，MyClass有一个接受一个整数参数的构造函数。如果尝试创建一个MyClass对象而不提供初始化参数，如下所示：

MyClass obj;

这将导致编译错误，因为编译器找不到一个无参数的默认构造函数。

5、某⼆叉树T的先序遍历序列为：{AB D C E G H F}， 中序遍历序列为： {D BAH G E C F} ，则下列说法中正确的是。

A. T的⾼为5

B. T有4个叶节点

C. T是平衡树

D.以上说法都不对

【答案】A

【考纲知识点】数据结构-树

【解析】先序可以确定根节点，中序可以确定左右子树节点，根据先序和中序可以构造一棵唯一的二叉树。

如果根节点高度为1，则这棵二叉树的高度为5， 有三个叶子节点。A选择对，B选项错。

平衡树：一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 所以C选项错。

6、⼀棵完全⼆叉树有431个结点 ，则叶结点有多少个？

A. 176

B. 215

C. 216

D. 255

【答案】C

【考纲知识点】数据结构-树

【解析】深度为8的满二叉树共有：28-1（255）个结点，深度为9的满二叉树共有：29 -1（511）个结点。一棵拥有431个结点的完全二叉树，深度为9。第9层结点数量：431-255=176（都是叶结点），第八层总结点数量：

2(8-1) =128，第8层中为叶结点的数量：128-176/2=40，所以这棵二叉树叶结点：176+40=216

7、下列关于树的说法 ，错误的是。

A.⼆叉树的中序遍历与其深度优先遍历总是相同的。

B.所有树都可以构造⼀颗⼆叉树与之⼀⼀对应。

C.如果树的⼀个叶结点有两个不同的祖先结点 ，那么其中⼀个⼀定是另⼀个的祖先结点。

D.树的结点不能有两个⽗结点。

【答案】A

【考纲知识点】数据结构-树、算法-深度优先搜索

【解析】深度优先搜索是一个更广泛概念，包括三种不同的遍历方式：前序遍历、中序遍历、后序遍历，虽然中序遍 历是深度优先搜索的一种形式，所以不能说二叉树的中序遍与其深度优先搜索遍历总是相同的。

8、⼀个简单无向图有10个结点、30条边 。再增加多少条边可以成为完全图 。

A. 10

B. 15

C. 51

D. 60

【答案】B

【考纲知识点】数据结构-图

【解析】n个结点的完全无向图，最多有n*(n-1)/2条边。10个结点最多：10*9/2=45条边，所以还需要15条边。

9、以下哪个方案可以合理解决或缓解哈希表冲突。

A.丢弃发⽣冲突的新元素。

B.用新元素覆盖发⽣冲突的元素。

C.用新元素覆盖在冲突位置的下⼀个位置。

D.将新元素放置在冲突位置之后的第⼀个空位。

【答案】D

【考纲知识点】数据结构-哈希表

【解析】在哈希表中，冲突（也称碰撞）是指两个不同的键被映射到哈希表的同一位置。

A选项，这个方案显然不是一个好的解决策略，因为它会导致信息丢失。如果频繁发生冲突，大量新元素将被丢弃， 哈希表将失去其存储和检索数据的能力。

B选项，这个方案不可取，因为会导致旧元素被覆盖，从而丢失数据。哈希表应该能够可靠地存储和检索每个键对应 的值。

C选项，这个方案不合理，因为没有明确定义“下一个位置”是什么。在哈希表中，冲突位置之后的“下一个位置” 可能仍然是一个冲突位置，或者可能是一个已经存储了其它元素的位置。此外这种策略也没有提供一种系统化的方法 来遍历哈希表中的所有元素。

D选项，这个方案合理，描述了一种称为开放地址法（Open Addressing）的冲突解决策略。在这种方法中，当发生 冲突时，哈希表会尝试在冲突位置的后续位置找到一个空位来存储新元素。

10、⼀个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有⼀条，则下面说法错误的是。

A.可以使用深度优先搜索找到这条路径。

B.可以使用⼴度优先搜索找到这条路径。

C.该迷宫内与起点连通的结点 ，⼀定也与终点连通。

D.该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图。

【答案】D

【考纲知识点】算法概念

【解析】通过深搜或广搜可以找到这条路径，所以A选项和B选项正确。

C选项，根据题目条件，从起点不经过重复点到达终点的路径仅有一条，这意味着所有与起点连通的节点都在这条路 径上，因此也必然与终点连通。

D选项，尽管从起点不经过重复结点到达终点的路径有且仅有⼀条，但不在这条路径的“冗余”分支上还是可能有环的，比如下图所示的迷宫。因此不一定可以抽象为无向无环图。

11、下面程序的输出为。

A. 2

B. 3

C. 8

D.无法通过编译。

【答案】A

【考纲知识点】语法知识，log函数

【解析】log函数通常返回的是自然对数。8的自然对数约为2.07944154167，然而将log(8)的结果转换为int类型时，仅保留整数部分。

12、下面程序的输出为。

A. 84

B. 495

C. 1012

D.结果是随机的。

【答案】C

【考纲知识点】动态规划

【解析】初始化第0行和第0列，从(1,1)点开始，等于上面值+左边值。

13、上题中程序的时间复杂度为。

A. O(1)

B. O(N)

C. O(NlogN)

D. O(N2)

【答案】D

【考纲知识点】算法-时间复杂度

【解析】代码的核心部分是一个双重循环，每个循环从1~n，所以时间复杂度为O（N2）

A. O(n)

B. o(ϕn) , ϕ

=

C. O(2n)

D.无法正常结束。

【答案】B

【考纲知识点】递归

【解析】这个代码虽然创建了fib_rcd数组，像是要记忆化搜索，但是不是记忆化搜索代码，因为fib_rcd数组内的值没有发生过改变，没有办法去掉重复计算。如果是记忆化搜索解决斐波那契数列数列代码时间复杂度为O(N)，因此,该递 归算法的时间复杂度等于递归树的节点总数,也就是斐波那契数列的前n项之和。

(

)

n

是斐波那契数列第n项的一个渐近表达式。

15、下列选项中 ，哪个可能是下图的⼴度优先遍历序列。

A. 1, 3, 5, 7, 4, 2, 6, 8, 9

B. 9, 4, 2, 1, 3, 7, 5, 6, 8

C. 1, 3, 5, 7, 6, 8, 9, 4, 2

D. 9, 4, 7, 2, 1, 3, 5, 6, 8

【答案】A

【考纲知识点】广度优先搜索图

【解析】根据广度优先搜索的概念，从1个点出发，首先搜索所有与该点相邻的点，再进一步搜索相邻点的相邻点。 根据全面扩散，逐层递进，可以画出如下图所示：

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

1、表达式 'a '

【答案】错误

【考纲知识点】语法知识

【解析】'a'是字符常量，在C++中其ASCII码值为97。'a'

2、在C++语言中 ，函数可以定义在另⼀个函数定义之内。

【答案】错误

【考纲知识点】语法知识

【解析】C++不支持函数嵌套定义。

3、选择排序⼀般是不稳定的。

【答案】正确

【考纲知识点】排序算法知识

【解析】选择排序在排序过程中，会选择最小（或最大）的元素与当前元素交换位置。这种交换可能改变相同元素的相对顺序，因此选择排序一般是不稳定的排序算法。

4、 埃氏筛法和欧拉筛法都是使用筛法思想⽣成素数表的算法 ，欧拉筛法的时间复杂度更低。

【答案】正确

【考纲知识点】算法知识

【解析】埃氏筛法的时间复杂度是O(n log logn),欧拉筛法是O(n)。

5、使用math.h或cmath头⽂件中的正弦函数 ，表达式 sin(30)的结果类型为double 、值约为0.5

【答案】错误

【考纲知识点】数学知识

【解析】sin函数输入的是弧度制的角度，角度制下的30度，转换为弧度制是π/6。

6、⼀颗N层的完全⼆叉树 ，⼀定有2N- 1个结点。

【答案】错误

【考纲知识点】数据结构知识

【解析】最后一层可能不满。

7、⼀个图 ，不管是否连通 ，都可以使用深度优先搜索算法进行遍历。

【答案】正确

【考纲知识点】数据结构知识

【解析】与连通性无关。对于非连通图，遍历完一个连通分量后，可以在未访问的节点中选择新的起点，继续进行DFS，直到所有节点都被访问。

8、某个哈希表键值x为整数，H(x) = x % p 是常用的哈希函数之⼀ ，要求 p选择素数是因为这样不会产⽣ 冲突 。

【答案】错误

【考纲知识点】数据结构知识

【解析】当x是p的倍数是会发送冲突。选择素数作为模数p，可以使哈希函数的值分布更均匀，减少冲突的概率，但不能完全避免冲突。

9、使用单链表实现队列时 ，链表头结点作为队⾸⽐链表头结点作为队尾更便于操作。

【答案】 ✔

【考纲知识点】数据结构-链表、队列

【解析】如果头结点作为队首，当新元素入队时，通过尾指针来实现入队操作，时间复杂度O(1)；当删除元素时， 删除链表头结点，更新头指针，时间复杂度O(1)

如果头结点作为队尾，当新新元素入队时，通过头指针实现入队，时间复杂度O(1)；当删除元素时，每次都需要遍历链表找到当前的队尾前一个元素（单链表），让尾指针指向这个元素，时间复杂度O(n)。

10、⼀个图中 ，每个结点表达⼀个人 ，连接两个结点的边表达两个结点对应的人相互认识 ，则这个图可以用来 表达社交⽹络。

【答案】正确

【考纲知识点】数据结构知识

【解析】图属于网状结构可以表示社交网络。

1、小杨寻宝

题面描述

小杨有⼀棵包含n个节点的树 ，树上的⼀些节点放置有宝物。

小杨可以任意选择⼀个节点作为起点并在树上移动 ，但是小杨只能经过每条边⾄多⼀次 ，当小杨经过⼀条边后 ，这条边就会消失 。小杨每经过⼀个放置有宝物的节点就会取得该宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

样例1

对于第一组测试用例，小杨从节点2出发，按照2-1-3-4的顺序即可成功取得所有宝物。

对于全部数据，保证有1≤t ≤10,1 ≤n ≤105,0≤ai ≤1，且保证树上一定有至少一个节点放置有宝物。

【题目大意】在一棵有n个结点的树中，有一些点上有宝物，有一些点没有，可以在结点直接移动，但是走过的路不能再走，问能否把所有有宝物的点都走一遍。

【考纲知识点】建树知识，深搜知识

【解题思路】通过题意初步可以想到以每一个点作为起点进行搜索，再搜索过程中记录搜到的ai=1的点，搜索结束后比较和1的总数是否相同。由于数据范围较大，因此明显会超时。

由于每个节点只能走一次，所以可以从最深的宝物开始收集可以确保小杨在返回时不会重复经过已经消失的边（因为边会在经过一次后消失）。然后从这个节点回到根节点，如果是1那么就标记走了一次，如果这里被标记两次那么肯定是不满足题目要求。

【参考程序】

2、矩阵移动

题面描述

小杨有一个有一个n×m的矩阵，仅包含01?三种字符。矩阵的行从上到下编号依次为1,2,...,n，列从左到右编号依次为1,2,…,m编号。小杨开始在矩阵的左上角(1,1)，小杨只能向下或者向右移动，最终到达右下角(n,m)时停止，在移动的过程中每经过一个字符1得分会增加一分(包括起点和终点)，经过其它字符则分数不变。小杨的初始分数为0分。

小杨可以将矩阵中不超过x个字符?变为字符1。小杨在修改矩阵后，会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。

对于第二组测试用例，将(1,1)或者(3,3)变成1均是最优策略。

对于全部数据，保证有1 ≤ t ≤10,1 ≤ n,m ≤ 500,1 ≤ x ≤ 300，同时保证所有测试用例n×m的总和不超过2.5×105。

【题目大意】在一个n*m的矩阵中从(1,1)到(n，m)移动，只能向下或者向右移动，矩阵中有1和0，还有？，在移动的过程中尽可能的拿到1，可以将矩阵中的x个？修改成1，使得最后拿到的1尽可能的多。

【考纲知识点】动态规划

【解题思路】如果不考虑x,问题转换成为从(1,1)到(n，m)只能向下或者向右移动最多拿到多少个1。对于矩阵中的任意一点(i,j)只可能从(i-1,j)或者(i,j-1)移动过来。

状态设计：dp[i][j]表示到达位置(i，j)时可以获得的最大分数。

不难得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (a[i][j] == ‘1’？1:0)。

考了加入x,还是只能向下或者向右移动，之前只有1对结果有贡献，现在？也对结果有贡献。由于x的限制，？不能无限制的修改成1，所以需要记录修改次数。设计状态时增加一维表示修改次数。

状态设计：dp[i][j][k]表示到达位置(i,j)时，已经修改了k个字符所能获得的最大分数。

如果a[i][j]是0或者1，正常转移，和不考虑x时的转移过程一致，如果a[i][j]是？，先考虑当前有没有修改次数，如果没有当前阶段拿到和1和上一阶段比较求最大值，如果有修改次数，，需要看之前修改转移的值是多少，求最大值。

当a[i][j] == 1时，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1,

当a[i][j] == 0时，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

当a[i][j] == ?时，如果没有修改次数，dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

如果有修改次数，再考虑改或不改。

若修改当前节点为1，则有dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1,

若不修改，则有dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

取以上情况的最大值即可，同时需要考虑，若k==x,则不可增加修改次数。

可以观察到每一行的计算只依赖于上一行的信息，第一维可以优化，故可以使用滚动数组对数组进行降维。

【参考程序】

来源：紫璇教育分享