2022年（初赛J）CCF非专业级别软件能力认证全国卷真题（附详细答案解析）

2022 CCF 非专业级别软件能力认证第一轮 （CSP-J1）入门级 C++语言试题 一、单项选择题(共15题，每题 2 分，共计 30 分；每题有且仅有一个正确选项) 1. 以下哪种功能没有涉及 C++语言的面向对象特性支持：( )。 A. C++中调用 printf 函数 B. C++中调用用户定义的类成员函数 C. C++中构造一个 class 或 struct D. C++中构造来源于同一基类的多个派生类 题目解析 【解析】正确答案:A C++基础知识，面向对象和类有关，类又涉及父类、子类、继承、派生等关系，printf是C语言的与一个输出函数。 2. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的 ( )。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 题目解析 【解析】正确答案C 栈的知识考试，后进先出的特点。 3. 运行以下代码片段的行为是( )。 int x = 101; int y = 201; int *p = &x; int *q = &y; p = q; A. 将 x 的值赋为 201 B. 将 y 的值赋为 101 C. 将 q 指向 x 的地址 D. 将 p 指向 y 的地址 题目解析 【解析】正确答案 D，指针的本质是地址！最开始 p 指向 x 的地址，q 指向 y 的地址，最后 p 指向 q 的地址，所以 p 最终指向 y 的地址。 4. 链表和数组的区别包括( )。 A. 数组不能排序，链表可以 B. 链表比数组能存储更多的信息 C. 数组大小固定，链表大小可动态调整 D. 以上均正确 题目解析 【解析】 正确答案 C，链表和数组都能排序，链表能存储多少信息，数组就能存储多少信息。 5. 对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6六个互不相同的数据，每个数据按照 进栈 S、出栈 S、进队列Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知 栈S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、 e6、e5 和 e1 出队列。则栈 S 的容量至少是( )个数据。 A. 2 B. 3 C. 4 D. 6 题目解析 【解析】正确答案 B，栈：先入后出，队列：先入先出。 6.对表达式 a+(b-c)*d 的前缀表达式为 ( )，其中+、-、*是运算符。 A. *+a-bcd B. +a*-bcd C. abc-d*+ D. abc-+d 题目解析 【解析】正确答案 B，画二叉树的形态，写出前序遍历即可。 7. 假设字母表 {a, b, c, d, e} 在字符串出现的频率分别为 10%, 15%, 30%, 16%, 29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母 d 的编码长度为 ( ) 位。 A. 1 B. 2 C. 2 或 3 D. 3 题目解析 【解析 】正确答案 B，哈夫曼编码的构造，注意哈夫曼编码不唯一，但是WPL是唯一的，很容易误选 C。 8. 一棵有 n 个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第 1 个位置。若存储在数组第9 个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是 ( )。 A. 8、18 B. 10、18 C. 8、19 D. 10、19 题目解析 【解析】正确答案C，二叉树的基本知识，数组下标表示法。 9. 考虑由 N 个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在 ( ) 个非零元素。 A. N-1 B. N C. N+1 D. N2 题目解析 【解析】正确答案B，有向图连通至少的边围成一个环，且有向图方向一致。 10.以下对数据结构的表述不恰当的一项为：( )。 A. 图的深度优先遍历算法常使用的数据结构为栈。 B. 栈的访问原则为后进先出，队列的访问原则是先进先出。 C. 队列常常被用于广度优先搜索算法。 D. 栈与队列存在本质不同，无法用栈实现队列。 题目解析 【解析】正确答案D，栈:先入后出 队列:先入先出 一个队列存入入队 一个队列存储出队 11.以下哪组操作能完成在双向循环链表结点p 之后插入结点 s 的效果（其中，next 域为结点的直接后继，prev 域为结点的直接前驱）：( )。 A. p->next->prev=s; s->prev=p; p->next=s; s->next=p->next; B. p->next->prev=s; p->next=s; s->prev=p; s->