GESP第八次认证真题解析IC++六级真题回顾

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

1、⾯向对象编程(OOP)是⼀种特殊的程序设计⽅法 。下⾯(  )不是重要的OOP特性。

A.抽象

B.封装

C.继承

D.模块化答案: D

解析:面向对象编程的三大特性是封装、继承和多态，而模块化是结构化编程的一个特点，不属于OOP的特性。

2、 以下关于C++中类的说法 ，哪⼀项是正确的？

A.类中定义的所有成员变量和成员函数默认是public访问权限。
B.类的构造函数必须显式声明返回类型为void。

C.在C++中 ，类的数据⼀般设置为私有 ，其公有成员函数提供访问私有数据的唯⼀途径。

D.同⼀个类的实例有各⾃的成员数据和成员函数。

答案: C
解析:在C++中，类的成员变量和成员函数默认是私有的（private），构造函数没有返回类型，同一个类的不同实例共享成员函数，但每个实例有自己的成员变量。

3、以下C++代码段中存在语法错误或逻辑错误，（ ）是正确的。

A. NULL 在C++中⽆法⽤于指针初始化 ，应使⽤  nullptr。

B. obj 的定义应该是 MyClass obj; ⽽不是指针类型。

C. obj->display() 语句存在空指针访问错误，obj应该初始化为⼀个有效的对象。

D. obj->display() 语句会调⽤ display()函数 ，但它没有输出任何内容。答案：C
解析:使用NULL初始化指针后，直接调用指针指向的成员函数会导致空指针访问错误。应该先将指针初始化为一个有效的对象，或者使用nullptr代替NULL。

4、阅读以下代码 ，下⾯哪⼀项是正确的？

A. 栈s的输出顺序是1 2 3 4 5 ，队列q 的输出顺序是5 4 3 2 1 。B. 栈s的输出顺序是5 4 3 2 1 ，队列q 的输出顺序是1 2 3 4 5 。 

C. 栈s的输出顺序是1 2 3 4 5 ，队列q的输出顺序是1 2 3 4 5 。

D. 栈s的输出顺序是1 2 3 4 5 ，队列q的输出顺序是1 2 3 4 5 ，程序不会正常执⾏。答案: A
解析:栈是后进先出（LIFO），所以输出顺序是1 2 3 4 5；队列是先进先出（FIFO），所以输出顺序是5 4 3 2 1。

5、N个节点的双向循环链 ，在其中查找某个节点的平均时间复杂度是( )。

A. O(1)

B. O(N)

C. O(logN)
D. O(N³)
答案: B

解析:链表中查找元素需要从头指针开始逐个遍历，其实就是顺序查找，时间复杂度为O(N)。

6、以下关于树的说法，（ ）是正确的。

A.在⼀棵⼆叉树中 ，叶⼦结点的度⼀定是2。

B.满⼆叉树中每⼀层的结点数等于O (2!层数 1))。

C.在⼀棵树中，所有结点的度之和等于所有叶⼦结点的度之和。 
D.⼀棵⼆叉树的先序遍历结果和中序遍历结果⼀定相同。答案: B

解析:叶子结点的度为0，先序遍历和中序列遍历相同是要满足所有结点均不包含左子树这个前提条件的。

7、已知字符集 {A, B, C, D} 的出现频率如下表所⽰：

根据哈夫曼编码法，下⾯（）是正确的哈夫曼树。

答案：A
解析:


8、上⼀题中各字符的哈夫曼编码是（ ）。
A. A：0，B：10，C：110，D：111

B. A：0，B：10，C：11，D：10

C. A：0，B：101，C：100，D：11

D. A：11，B：10，C：01，D：88
答案: C

解析:

9、( )是3位格雷编码。

A. 000 001 011 010 110 111 101 100    

B. 000 001 010 011 100 101 110 111    

C. 000 001 100 101 011 010 111 110    

D. 000 010 001 011 100 110 101 111    

答案: A

解析:
1位格雷码：0 1
2位格雷码:  先镜像 → 0 1 1 0  镜像部分加前缀1序列加前缀0 → 00  01 11 10
3位：先镜像00 01 11 10 10 11 01 00  
同上加前缀 → 000 001 011 010   110  111  101  100

10、根据下⾯⼆叉树和给定的代码

给定以下二叉搜索树，调用函数search(root,7)时，输出的结果是（ ）。

A. 5 3 7

B. 5 7

C. 2 3 4 5 6 7
D. 8 7
答案：B
解析：二叉搜索树 先从根遍历 输出 5，然后7比5大看右子树找到后结束。

11、阅读以下⼆叉树的深度优先搜索算法，横线上应填写（ ）。

A. TreeNode* node = s.top();

B. TreeNode* node = s.top();  s.pop();

C. TreeNode* node = s.front();

D. TreeNode* node = s.front();  s.pop();
答案：B
解析：用栈遍历，取出栈顶元素，删除栈顶元素。

12、阅读以下⼆叉树的⼴度优先搜索的代码，横线上应填写（   ）。

A. TreeNode* node = q.top();

B. TreeNode* node = q.top();  q.pop();

C. TreeNode* node = q.front();

D. TreeNode* node = q.front();  q.pop();
答案：D
解析：用队列遍历，取出队头，删除队头

13、使⽤上题中的宽度优先搜索算法遍历以下这棵树 ，可能的输出是( )。

1. 1 2 8 9 4 5 3 6 7

2. 1 2 34 5 6 6 8 9  

3. 1 2 3 8 9 6 4 5 7

4. 8 4 5 9 2 1 3 6 7

答案：C
解析：BFS遍历又称为层次遍历，逐层进行,

1 2 3 8 9 6 4 5 7

14、以下关于动态规划的描述，（ ）是正确的 。 

A.动态规划适⽤于没有重叠⼦问题的优化问题 。 

B.动态规划要求问题具有最优⼦结构和⽆后效性。

C.动态规划通常通过递归来实现。

D.动态规划与贪⼼算法不同 ，贪⼼算法不适⽤于有重叠⼦问题的问题。答案：B
解析：判断一道题目能否用动态规划解决的前提有3点。1.该问题有最优子结构；2.该问题有重叠子问题；2.问题具有无后效性。

15、假设背包的最⼤容量w = 8kg ，共有有4个物品可供选择 ，4个物品的重量分别为weights =  [2, 3, 5, 7] ，对应的价值分别为values = [30, 40, 60, 80] ，则该0/1背包问题中 ，背包的最⼤价值为（  ）。

A. 70   

B. 90   

C. 100

D. 120
答案：C
解析：选择重量为3 和 5 的物品 得到的价值为100，没有比100更大的价值了。

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

1、构造函数是⼀种特殊的类成员函数 ，构造函数的名称和类名相同 。但通过函数重载 ，可以创建多个同名的构 造函数 ，条件是每个构造函数的参数列表不同。答案:正确解析:•构造函数名称和类名相同：这是构造函数的一个显著特点。

•函数重载：C++支持函数重载，因此可以有多个构造函数，前提是它们的参数列表不同（参数的数量或类型不同）。

这种重载允许根据不同的初始值或条件来灵活地创建类的对象。

2、类的静态成员函数既能访问类的静态数据成员 ，也能访问⾮静态数据成员。答案:错误解析:类的静态成员函数只能访问类的静态数据成员，不能访问非静态数据成员（除非通过对象指针或引用）。

3、栈中元素的插⼊和删除操作都在栈的顶端进⾏ ，所以⽅便⽤单向链表实现。

答案：正确

解析：栈是后进先出的数据结构，插入和删除操作都在栈顶进行。单向链表可以实现栈的操作，因为链表可以在头部方便地插入和删除元素。

4、下⾯代码构建的树⼀定是完全⼆叉树：

答案：正确

解析：按代码逻辑先构造根，再构造根的左右子树，再构造左子树的左右子树，再构造右子树的左子树，这种构造方法和完全二叉树一致。

5、在⼆叉排序树中 ，左⼦树所有节点的值都⼤于根节点的值 ，右⼦树所有节点的值都⼩于根节点的值。答案：错误解析：二叉排序树又称二叉搜索树，左孩子小于根节点，右孩子大于根结点。

6、在⽣成⼀个派⽣类的对象时 ，只调⽤派⽣类的构造函数。

答案:错误解析:在生成一个派生类的对象时，会先调用基类的构造函数（如果有的话），然后再调用派生类的构造函数。这是构造函数链的一个例子。

7、下⾯的代码实现了⼆叉树的前序遍历 ，它通过递归⽅法访问每个节点并打印节点值。

答案：正确解析：前序遍历的顺序是根左右，若遍历到空结点则返回。

8、宽度优先搜索算法（BFS）保证了每个节点在最短路径的情况下被访问。

答案：错误解析：宽度优先搜索算法（BFS）按照层次遍历图或树，但它并不保证找到从起始节点到目标节点的最短路径（除非图是无权的）。对于有权图，应使用迪杰斯特拉算法或A*等算法来找到最短路径。

9、在解决简单背包问题时，动态规划的状态转移方程如下：

该方程表示：在考虑第 i个物品时 ，当前背包容量为 w，如果不放物品i，则最⼤价值是dp[i-1][w]；如果放入物品i，则最大价值是dp[i-1][w - weights[i-1]] + values[i-1] ，其中数组weights和values分 别表⽰所有物品的重量和价值 ，数组下标从 0开始。

答案：错误解析：如果 放⼊物品 i，则最大价值是dp[i-1][w - weights[i]] + values[i]

10、栈中元素的插⼊和删除操作都在栈的顶端进⾏ ，所以⽅便⽤双向链表⽐单向链表更合适表实现。

答案：错误解析：栈是后进先出的数据结构，插入和删除操作都在栈顶进行。链表可以实现栈的操作，因为链表可以在头部方便地插入和删除元素，这和单链表或双链表无关。

三、编程题(每题25分，共50分)

1、树上游走

题目描述

小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外，每个节点都有父节点)，其中根节点的编号为1，对于节点i，其左儿子的编号为2×i，右儿子的编号为2×i+1。

小杨会从节点s开始在二叉树上移动，每次移动为以下三种移动方式的任意一种：•第1种移动方式：如果当前节点存在父亲节点，向上移动到当前节点的父亲节点，否则不移动;

• 第2种移动方式：移动到当前节点的左儿子；

• 第3种移动方式：移动到当前节点的右儿子。

小杨想知道移动n次后自己所处的节点编号。数据保证最后的所处的节点编号不超过10¹²。

输入格式

第一行包含一个正整数n,8，代表移动次数和初始节点编号。

第二行包含一个长度为n且仅包含大写字母U,L,R的字符串，代表每次移动的方式，其中U代表第1种移动方式L代表第2种移动方式，R代表第3种移动方式。

输出格式

输出一个正整数，代表最后所处的节点编号。

样例

样例解释

小杨的移动路线为2-1-3-7。

对于全部数据，保证有1≤n ≤10⁶。1≤s ≤10¹²。

参考程序

解析：首先想到的是模拟，但是在模拟的过程中需要注意若当前结点已经是根结点了就不要再向上跳了。

【10分代码】为什么不能拿满分，S的范围是10^6 ~ 10^12，在计算的过程中很容易就超过long long 的范围，那怎么解决？高精度嘛？不完全可以，10^6的运算 再加 高精处理 会有超时的风险，

那怎么做？为什么在计算的过程中会超过long long， 是因为L和R的操作，但是在L或R的操作前要是有u的操作，L或R的操作就可以被抵消

2、运送物资

题面描述

小杨管理着m辆货车，每辆货车每天需要向A市和B市运送若干次物资。小杨同时拥有n个运输站点，这些站点位于A市和B市之间。

每次运送物资时，货车从初始运输站点出发，前往A市或B市，之后返回初始运输站点。A市、B市和运输站点的位置可以视作数轴上的三个点，其中A市的坐标为0,B市的坐标为x，运输站点的坐标为p且有0<p<x，货车每次去A市运送物资的总行驶路程为2p，去B市运送物资的总行驶路程为2(x-p)。

对于第i个运输站点，其位置为p_i且至多作为c_i辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。

输入格式

第一行包含三个正整数n,m,x，代表运输站点数量，货车数量和两市距离。

之后n行，每行包含两个正整数p_i,c_i，代表第i个运输站点的位置和最多容纳车辆数。

之后m行，每行包含两个正整数a_i,b_i，代表第i辆货车每天需要向A市运送a_i次物资，向B市运送b_i次物资。

输出格式

输出一个正整数，代表所有货车每天的最短总行驶路程。

样例

样例解释

第1辆车的初始运输站点为站点3，第2辆撤的初始运输站点为站点2。第3辆车的初始运输站点为站点1，第4辆车的初始运输站点为站点3。此时总行驶路程最短，为40186。

对于全部数据，保证有1≤n,m≤10⁵，2≤ x ≤10⁸，0<p_i<x,1≤ c_i≤10⁵，0≤a_i，b_i≤10⁵。数据保证∑c_i≥m。

解析：本题的核心是优化所有货车的总行驶路程，通过合理分配每辆货车的初始运输站点来实现。

为了最小化总行驶路程，我们应该尽可能让那些更频繁去A市或B市的货车从离目标城市更近的运输站点出发。具体来说：对于一辆需要更多次前往A市的货车，应该尽量安排在距离A市（坐标0）较近的运输站点。对于一辆需要更多次前往B市的货车，应该尽量安排在距离B市（坐标x）较近的运输站点。

基于上述贪心策略，我们首先对货车的需求（ai,bi）进行排序，根据(ai,bi)的值。如果ai > bi 则该货车更适合靠近A市；反之，则更适合靠近B市。

然后，我们同样对运输站点按照它们的位置pi进行排序，并尝试从两端开始分配货车到最合适的运输站点，直到所有货车都被分配完毕。

参考程序

技术支持：GESP技术委员会委员 赵晨泽

策划：GESP技术委员会副主席 刘晓庆