2022 CCF 非专业级别软件能力认证第一轮 (CSP-J1) 入门级 C++语言试题 认证时间：2022 年9 月18 日09:30~11:30 一、单项选择题(每题2 分，共计 30 分) 【答案】A 【解析】printf 函数是 C 语言中的函数，C 语言是面向过程的语言，因此选 A
【答案】C 【解析】模拟入栈出栈，C 选项中"6 5"不可能实现
【答案】D 【解析】初始时p 指向 x 的地址，q 指向 y 的地址，执行第5 行程序后，将 p 指向 y 的地址
【答案】C 【解析】A 选项，数组可以排序；B 选项，链表不能存储比数组更多的信息；C 选项正确
【答案】B 【解析】栈的特点是后进先出，队列的特点是先进先出
依题意模拟过程，括号中表示栈中数据的个数：e1 入栈(1)，e2 入栈(2)，e2 出栈(1)，e3 入栈(2)，e4 入栈(3)，e4 出栈(2)，e3 出栈(1)，e5 入栈(2)，e6 入栈(3)，e6 出栈(2)，e5 出栈(1)，e1 出栈(0)
栈的容量至少为 3
【答案】B 【解析】中缀表达式转换为前缀表达式的方法： ①将所有运算按照优先级加上小括号，(a+((b-c)*d)) ②将运算符移到对应小括号前，+(a*(-(b c) d) ③去掉小括号，+a*-bcd 【答案】B 【解析】按照哈夫曼编码规则画出哈夫曼树，如下图结点d到根节点的边数即编码长度为2
【答案】C 【解析】9 的父结点是 4，兄弟结点是 8，左儿子结点是 18，右儿子结点是 19 【答案】B 【解析】n个点有向连通图，至少有n条边，连成一圈，邻接矩阵中非零元素即为边数最少为n
【答案】D 【解析】使用两个栈，一个栈存放入队的操作，另一个栈用来出队，即可用栈实现队列
【答案】D 【解析】画图模拟，选项 D 正确
【答案】B 【解析】选择排序是不稳定排
