2025年12月 CCF GESP认证 C++六级试题

国时真机 GESP CCF编程能力等级认证 Grade Examination of Software Programming C++六级 2025年12月 1单选题（每题2分，共30分） 题号123456789101112131415 答案CC CA BB C A BB A C BBB 第1题在面向对象编程中，下列关于虚函数的描述中，错误的是（)。 口A虚函数用于支持运行时多态 口B.通过基类指针调用虚函数时，会根据对象实际类型决定调用版本 口C.构造函数可以声明为虚函数以支持多态 ☐D.基类析构函数常声明为虚函数以避免资源泄漏 第2题执行如下代码，会输出钢琴：叮咚叮咚和吉他：咚咚当当。这体现了面向对象编程的（)特性。 第1页/共13页 1 class Instrument 2 public: virtual void play(){ 4 coUt<"乐器在演奏声音"<endL; 6 virtual ~Instrument(){ 8 了： 9 10 class Piano public Instrument 11 public: 12 void play()override 13 coUt<<"钢琴：叮咚叮咚"<<end1; 14 } 15 }: 16 17 class Guitar public Instrument 18 public: 19 void play()override 20 cout<<"吉他：咚咚当当"<<endl; 21 22 }; 23 24 int main(){ 25 Instrument*instruments[2]; 26 instruments[0]new Piano(); 27 instruments[1]new Guitar(); 28 29 for (int i 0;i<2;++i){ 30 instruments[i]->play(); 31 } 32 33 for (int i=0;i<3;++i) 34 delete instruments[i]; 35 36 return 0; 37 3 ☐A.继承 □B.封装 □C.多态 OD.链接 第3题关于以下代码，说法正确的是()。 第2页/共13页 1 class Instrument 2 public: void play(){ 4 coUt<<"乐器在演奏声音"<endL; 6 virtual ~Instrument(){ 8 9 10 class Piano public Instrument 11 public: 12 void play()override 13 coUt<<"钢琴：叮咚叮咚"<<end1; 14 } 15 }: 16 17 class Guitar public Instrument 18 public: 19 void play()override 20 cout<<"吉他：咚咚当当"<<endl; 21 22 23 24 int main(){ 25 Instrument*instruments[2]; 26 instruments[o]new Piano(); 27 instruments[1]new Guitar(); 29 for (int i 0;i<2;++i){ 30 instruments[i]->play(); 31 32 33 for (int i=0;i<3;++i) 34 delete instruments[i]; 35 36 return 0; 37 ☐A执行代码会输出两行，内容分别为：钢琴：叮咚叮咚和吉他：咚咚当当 ☐B.执行代码会输出两行，内容分别为：乐器在演奏声音和乐器在演奏声音 ☐C.代码编译出现错误 口D.代码运行出现错误 第4题某文本编辑器把用户输入的字符依次压入栈S。用户依次输入A,B,C,D后，用户按了两次撤销（每次 撤销，弹出栈顶一个字符)。此时栈从栈底到栈顶的内容是：(）。 ☐A.AB ☐B.ABC ☐C.ABD ☐D.Bc 第5题假设循环队列数组长度为N,其中队空判断条件为：front=rear,队满判断条件为：(rear+1)% N=front,出队对应的操作为：front=(front+1)%N,入队对于的操作为：rear=(rear+I)% N。循环队列长度N=6,初始front=1,rear=1,执行操作序列为：入队，入队，入队，出队，入队，入队， 则最终(front,rear)的值是()。 ☐A.(2,5) 第3页/共13页 ☐B.(2,0) ☐C.(3,5) ☐D.(3,) 第6题以下函数check()用于判断一棵二叉树是否为()。 1 bool check(TreeNode*root){ 2 if (!root)return true; 4 queue<TreeNode*>q; 5 q.push(root); 6 bool hasNull false; 1 while (!q.empty()){ 8 TreeNode*cur q.front();q.pop(); 9 if (!cur){ 10 hasNull true; 11 else 12 if (hasNUll)return false; 13 q.push(cur->Left); 14 q.push(cur->right); 15 16 3 17 return true; 183 ☐A.满二叉树 口B.完全二叉树 ☐C.二叉搜索树 □D.平衡二叉树 第7题以下代码实现了二叉树的（)。 1 void traverse(TreeNode*root){ 2 if (!root)return; 3 traverse(root->left); traverse(root->right); cout <root->val <"" 6 3 ☐A前序遍历 □B.中序遍历 ☐C.后序遍历 口D.层序遍历 第8题下面代码实现了哈夫曼编码，则横线处应填写的代码是()。 第4页/共13页 struct Symbol 2 char ch; /字符 3 Longlong freq; //频率 4 string code; //哈夫曼编码 6 struct Node Long long w; //权值 9 int l,r; /1左右孩子（节点下标），-1表示空 10 int sym; //叶子对应符号下标；内部节点为-1 11 Node(long long _W=0,int _l=-1,int _r=-1,int _sym=-1) 12 :w(_w),1(_1),r(_),sym(_sym)} 13 14 15 /从A(leafIdx)和B(internalIdx)的队首取最小的-个节点下标 16 static int PopMinNode(const vector<Node>&nodes, const vector<int>&LeafIdx,int n,int&pA 18 const vector<int>&internalIdx,int&pB){ 19 if (pA n &(pB >=(int)internalIdx.size() 20 nodes[leafIdx[pA]].w <nodes[internalIdx[pB]].w)) 21 return LeafIdx[pA++]; 22 23 else 24 return internalIdx[pB++]; 26 27 28 /DFS生成编码（左0，右1） 29 static void DFSBuildcodes(int u,const vector<Node>&nodes,Symbol sym[],string&path){ 30 if (U ==-1)return; 31 32 if (nodes[u].sym !=-1){ //叶子 33 sym[nodes[u].sym].code path; 34 return; 35 36 37 path.push_back('0'); 38 DFSBuildCodes(nodes[u].L,nodes,sym,path); 39 path.pop_back(); 40 41 path.push_back('1'); 42 DFSBuildCodes(nodes[u].r,nodes,sym,path); path.pop_back(); 44 45 46 int BuildHuffmanCodes(Symbol sym[],int n){ for (int i=0;i<n;i++)sym[i].code.cLear(); 48 if (n <0)return -1; 49 50 //只有一个字符：约定编码为"0” 51 if(n=1){ 52 sym[e].code "o"; 53 return 0; 54 56 vector<Node>nodes; 57 nodes.reserve(2 n); 58 59 //1)建立叶子节点 60 vector<int>LeafIdx(n); 61 for (int i=0;i<n;i++) 62 leafIdx[i](int)nodes.size(); 63 nodes.push_back(Node(sym[i].freq,-1,-1,i)); 64 第5页/共13页 65 6 /12)叶子按权值排序(A队列) 67 sort(LeafIdx.begin(),LeafIdx.end(), 68 [&](int a,int b){ 69 if (nodes[a].w !nodes[b].w)return nodes[a].w nodes[b].w; 70 return nodes[a].sym<nodes[b].sym;//稳定-下 71 }); 72 73 /B队列（内部节点下标队列） 74 vector<int>internalIdx; internalIdx.reserve(n); 76 77 int pA 0,pB =0; 78 79 /13)合并n-1次 80 for (int k 1;k n;k++){ 81 int x PopMinNode(nodes,leafIdx,n,pA,internalIdx,pB); 82 int y PopMinNode(nodes,LeafIdx,n,pA,internalIdx,pB); 83 84 int z (int)nodes.size(); 85 //在此收处填写代码 86 87 88 int root internalIdx.back(); 89 90 //4)DFS生成编码 91 string path; 92 DFSBuildCodes(root,nodes,sym,path); 93 return root; 94 □A. nodes.push_back(Node(nodes [x].w nodes[y].w,x,y,-1)); 2 internalIdx.push_back(z); B. nodes.push_back(Node(nodes[x].w nodes[y].w,x,y,-1)); LeafIdx.push_back(z); c. internalIdx.push_back(z); nodes.push_back(Node(nodes[x].w nodes[y].w,x,y,x+y)); □D. nodes.push_back(Node(nodes[x].w nodes[y].w,x,y,x+y)); LeafIdx.push_back(z); 第9题以下关于哈夫曼编码的说法，正确的是(）。 ☐A.哈夫曼编码是定长编码 ☐B.哈夫曼编码中，没有任何一个字符的编码是另一个字符编码的前缀 ☐C.哈夫曼编码一定唯一 ☐D.哈夫曼编码不能用于数据压缩 第10题以下函数实现了二叉排序树(BST)的（)操作。 第6页/共13页 1 TreeNode*op(TreeNode*root,int x){ if (root)return new TreeNode(x); if (x root->val) 4 root->Left op(root->Left,x) 5 else 6 root->right op(root->right,x); 7 return root; 8 ☐A.查找 口B.插入 ☐C.删除 □D.遍历 第11题下列代码实现了树的深度优先遍历，则横线处应填入(）。 1 struct TreeNode int val; TreeNode*left; 4 TreeNode*right; 5 TreeNode(int x):val(x),Left(nullptr),right(nullptr){ 6 } void dfs(TreeNode*root){ 9 if (!root)return; 10 stack<TreeNode*>st; 11 st.push(root); 12 while (!st.empty()) 13 TreeNode*node st.top();st.pop(); 14 cout <node->val <<"" 15 if (node->right)st.push(node->right); 16 17 18 A.if (node->left)st.push(node->left) B.if (node->left)st.pop(node->left); C.if (node->left)st.front(node->left); D.if (node->left)st.push(node->right); 第12题给定一棵普通二叉树（节点值没有大小规律），下面代码判断是否存在值为x的结点，则横线处应填入( ）。 第7页/共13页 1 struct TreeNode int val; 3 TreeNode*Left; 4 TreeNode*right; TreeNode(int x):val(x),left(nullptr),right(nullptr){} 6 8 TreeNode*bfsFind(TreeNode*root,int x){ 9 if (!root)return nullptr; 10 11 queue<TreeNode*>q; 12 q.push(root); 13 14 while (!q.empty()) 15 TreeNode*cur q.front();q.pop() 16 if (cur->val =x)return cur; 17 18 子 19 return nullptr; 20 ☐A.q.push(cur)i B.if (cur->right)q.push(cur->right); ▣c. 1 if (cur->left) q.push(cur->Left); if (cur->right) q.push(cur->right); D. q.push(cur->Left); q.push(cur->right); 第l3题在二叉排序树(Binary Search Tree,.BST)中，假设节点值互不相同。给定如下搜索函数，以下说法一定正 确的是()。 1 bool find(Node*root,int x){ 2 while (root){ 3 if (root->val =x)return true; root (x root->val)?root->left root->right; 5 } 6 return false; 7 口A.最坏情况下，访问结点数是O(1ogn) □B.最坏情况下，访问结点数是O(n) 口C.无论如何，访问结点数都不超过树高的一半 ☐D.一定比在普通二叉树中搜索快 第14题0/1背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ )。 1 for each item (w,v): 2 for (int j=W;j>=w;--j) 3 dp[j]max(dp[j],dp[j-w]v) 第8页/共13页 ☐A内层了必须从小到大，否则会漏解 ☐B.内层了必须从大到小，否则同一件物品会被用多次 □C.方从大到小或从小到大都一样 口D.只要dp初始为o,方向无所谓 第15题以下关于动态规划的说法中，错误的是（)。 ☐A动态规划方法通常能够列出递推公式。 □B.动态规划方法的时间复杂度通常为状态的个数。 ☐C.动态规划方法有递推和递归两种实现形式。 口D.对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。 2判断题（每题2分，共20分） 题号12345678910 答案×√√×√×√××√ 第1题以下代码中，构造函数被调用的次数是1次。 1 class Test 2 public: Test()cout <"T " }: 6 int main(){ 7 Test a; 8 Test b a; 9} 第2题面向对象编程中，封装是指将数据和操作数据的方法绑定在一起，并对外隐藏实现细节。 第3题以下代码能够正确统计二叉树中叶子结点的数量。 1 int countLeaf(TreeNode*root){ 2 if (!root)return 0; 3 if (!root->Left&&!root->right)return 1; return countLeaf(root->left)+countLeaf(root->right); 5} 第4题广度优先遍历二叉树可用栈来实现。 第5题函数调用管理可用栈来管理。 第6题在二叉排序树(B$T)中，若某结点的左子树为空，则该结点一定是整棵树中的最小值结点。 第7题下面的函数能正确判断一棵树是不是二叉排序树（左边的数字要比当前数字小，右边的数字要比当前数字 大)。 1 bool isBST(TreeNode*root,int minVal,int maxVal){ 2 if (!root)return true; 3 if (root->val <minVal root->val >maxVal) return false; 5 return isBST(root->Left,minVal,root->val)&& 6 isBST(root->right,root->val,maxVal); 73 第9页/共13页 第8题格雷编码相邻两个编码之间必须有多位不同，以避免数据传输错误。 第9题小杨在玩一个闯关游戏，从第1关走到第4关。每一关的体力消耗如下（下标表示关卡编号）：c0st=[ 0,3,5,2,4],其中cost[i]表示到达第1关需要消耗的体力，cost[0]=表示在开始状态，体力消耗为 0。小杨每次可以从当前关卡前进1步或2步。按照上述规则，从第1关到第4关所需消耗的最小体力为7。 第10题假定只有一个根节点的树的深度为1，则一棵有n个节点的完全二叉树，则树的深度为1og2(n)小+1。 3编程题（每题25分，共50分） 3.1编程题1 。试题名称：路径覆盖 。时间限制：1.0s 。内存限制：512.0MB 3.1.1题目描述 给定一棵有n个结点的有根树T,结点依次以1,2，，n编号，根结点编号为1。方便起见，编号为的结点称为结 点i。 初始时T中的结点均为白色。你需要将T中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结 点。将结点i染为黑色需要代价℃，你需要在满足以上条件的情况下，最小化染色代价之和。 叶子是指T中没有子结点的结点。 3.1.2输入格式 第一行，一个正整数几，表示结点数量。 第二行，n-1个正整数f2,f3,·,fn,其中f表示结点i的父结点的编号，保证f<i。 第三行，n个正整数c1,c2,·,cn,其中c表示将结点i染为黑色所需的代价。 3.1.3输出格式 一行，一个整数，表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下，染色代价之和的最小值。 3.1.4样例 3.1.4.1输入样例1 14 2123 35623 3.1.4.2 输出样例1 12 3.1.4.3 输入样例2 17 2112233 3 6416154321 第10页/共13页