9月中旬年CCF初赛结束，CSP-J是CCFCSP非专业级别的软件能力认证，CSP-J1为入门级。通过对新试题的分析，我们注意到今年的考题通过对细节的考核，体现出题人希望学生们更多注意计算机底层基础知识的掌握和综合运用，比如更多的涉及到计算机底层知识如指针、数据结构、基础算法等知识点的综合运用。
学生们需要长时间系统性的扎实学习才能够通过CCF的测试，而那些参加培训机构短时间针对性刷题的同学们由于知识面较狭窄，将更难通过今年的考试。下面我们对部分试题进行讲解和分析。
CCF非专业级别软件能力认证第一轮
（CSP-J1）入门级C++语言试题
考试时间年9月18日09:30-11:30
考生注意事项:
试题纸共有12页，答题纸共有1页，满分分。请在答题纸上作答，写在试题纸上的一律无效。
不得使用任何电子设备（如计算器、手机、电子词典等）或查问任何书籍资料。
单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）
1.以下哪种功能没有涉及C++语言的面向对象特性支持：（）
A.C++中调printf函数
B.C++中调用用户定义的类成员函数
C.C++中构造一个class或struct
D.C++中构造来源于同一基类的多个派生类
第一题就比以前考类似考题更加的细致，以前只会问某种语言是面向对象的，某种语言是面向过程的。现在则需要具体到某种行为使用了面向对象的特性。
对象的特征之一就是封装成类，选项B和D符合，C选项的class也符合，C++中的struct增加了访问权限，且可以和类一样有成员函数。A选项的格式化输出函数printf没有体现出对象特性，所以选A。
有6个元索，按照6、5、4、3、2、1的顺序过入栈S，请问下列哪个出栈列是非法的（）
A.
B.
C.
D.
有关入栈出栈的出栈序列问题是高频考点，我们在《电脑报》年第25期31版已经简单介绍过，不再赘述。记住出栈所遵循的原则是“先进后出”。
根据“先进后出”原则，选项AB都可以实现。选项C，要3出栈，此时栈中还有6、5、4，接下来4可以出栈，但是6的上面还有5，没法按C的顺序要求出栈。所以C非法，选C。
运行以下代码片段的行为是（）。
将×的值赋为
将y的值赋为
将q指向x的地址
将p指向y的地址
“intx=;”定义变量x=；“inty=;”变量y=。“int*p=x”定义指针变量P是整数类型，x取的是变量x的地址，*p为p所指向对象的值，也就是地址x中的值。同理q存储y的地址。p=q就是把y（y的地址）赋值给p。所以程序最终将p指向y的地址，选D。
这一题虽然考察的是指针的基础知识。不过可能预示了CSP的趋势，未来指针是一个新的高频考点。今年的题目虽然比较简单，但是指针相关知识点非常多，未来有关指针的考察形式可能会很灵活，未来学习时要从基础上全面理解才行。
链表和数组的区别包括（）。
数组不能排序，链表可以
链表比数组能存储更多的信息
数组大小固定，链表大小可动态凋整
以上均正确
数组和链表的基本概念。数组和链表都能排序，A错误。数组和链表谁更多不一定，B错误。在C++中建立数组的时候就确定了数组的大小，这个题选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的容量至少是（）个数据。
2
3
4
6
出栈所遵循的原则是“先进后出”。出栈序列问题果然是高频考点。
普通队列的进出规则是“先进先出”。就像排队一样，仅允许在队尾进行插入，在另一端进行删除操作，向队列插入新元素称为进队或入队，新元素进队之后成为新的队尾元素。从队列删除元素称为出队或离队，元素出队后，其直接后继元素就成为新的队首元素。
根据题目信息，队列Q出队的顺序是e2、e4、e3、e6、e5、e1，根据“先进先出”说明进队和出栈的顺序也是e2、e4、e3、e6、e5、e1。
那么问题转化为e1、e2、e3、e4、e5、e6入栈，e2、e4、e3、e6、e5、e1出栈，先确定入栈出栈的具体过程。e1、e2入栈，e2出栈；e3、e4入栈，e4、e3出栈；e5、e6入栈、e6、e5、e1出栈。
题目问栈S的容量，根据过程栈中最多存在过3个数据（e1、e3、e4和e1、e5、e6）。所以选择B。
6.对表达式a+(b-c)*d的前缀表达式为（），其中+、-、*是运算符。
*+a-bcd
+a*-bcd
abc-d*+
abc-+d
这题的知识点为中缀表达式转换成前缀表达式。中缀表达式(中缀记法)是一种通用的算术或逻辑公式表示方法，操作符处于操作数的中间，我们日常用的四则运算就是这种算术表示方法。其主要特点是用括号来规定了运算优先顺序。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，早年计算机中使用栈进行运算，并没有括号来规定其运算顺序，于是波兰逻辑学家JanLukasiewicz发明了一种没有括号的前缀表达式来解决这个问题，前缀表达式也称为“波兰式”，它没有括号所有的运算符号都标注在数字前面。例如，-1+23，它等价于1-(2+3)。
后缀表达式源自于前缀表达式，通常将后缀表示称为逆波兰式。计算机领域中后缀表达式更常用，前两年连续考察了后缀表达式，今年换成了前缀表达式，两者转换的方式类似：加括号、移符号、去括号。
将中缀表达式转化为前缀表达式分三步：
第一步，先按照运算符的优先级对中缀表达式加括号：{a+[(b-c)*d]}第二步，将运算符移到括号的前面（左侧括号外）：+{a*[-(bc)d]}第三步，把所有括号去掉所得即为前缀表达式：+a*-bcd
所以选B。
前缀表达式的运算方式为：从右至左扫描表达式，如果当前字符(或字符串)为数字或变量，则压入栈内；如果是运算符，则将栈顶两个元素弹出栈外并作相应运算，再将结果压入栈内。当前缀表达式扫描结束时，栈里的就是中缀表达式运算的最终结果。对比中缀运算的步骤，不难发现前缀运算在计算机上的优势。
假设字母表{a,b,c,d,e}在字符串出现的频率分别为10%，15%，30%，16%，29%，若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度为（）位。
A.1
B.2
C.2或3
D.3
哈夫曼编码是一种变长的编码，在编码中各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，这样可以获得平均长度最小的编码，可以用来压缩数据。
静态的哈夫曼编码对需要编码的数据进行两遍扫描，第—遍统计原数据中各字符出现的频率，按频率从小到到大排序{a,b,d,e,c}，利用得到的频率值创建哈夫曼树。选择频率最小的两个字符a（10）、b（15）作为最底层的叶子，它俩的顶点是两个字符组合，这个组合的频率为两者频率之和ab（25）。与剩下字符的频率比较，选出频率最小的两个字符d（16）、ab（25），因为其中一个是之前的和，所以继续在这个树直接往上生长。如果是其他字符比较小，比如c（30）、e（29）比abd(41)小，那么就并列生长。重复次步骤，这样我们就会获得一个哈夫曼树。
哈夫曼树又称最优二叉树，它采用贪心策略，获得一种带权路径长度最短的二叉树。
第二遍则根据第一遍扫描得到的哈夫曼树进行编码，从上向下，向左编码0，向右编码1，在哈夫曼树中同级的两个子节点也可以左右交换，比如c可以编码成10也可以编码为11。把编码后得到的码字存储起来，把哈夫曼树的信息也保存下来。在解压数据时用同样的哈夫曼树来解压就行了。
根据题目要求，d的编码是01或00（与ab互换位置），所以长度是2选项B正确。
8.一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子节点的位置分别是（）。
A.8、18
B.10、18
C.8、19
D.10、19
完全二叉树简单说就是上层全满，最底层左边子节点全满的二叉树。复杂来说就是，一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
对于完全二叉树任意节点n，它的左子节点为2n，右子节点为2n+1。9的兄弟节点为8，右子节点为2×9+1=19。本题选C。另外要注意本题根结点是从1开始，如果根结点是从0开始则计算方法也不同哦。感觉做了这么多道题，这题最简单了。
9.考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（）个非零元素。
A.N-1
B.N
C.N+1
D.N2
这里涉及到了有向连通图和邻接矩阵的知识。
边没有方向的图称为无向图。边有方向则称为有向图。有向连通图可以认为是强连通图，即任意两个节点相互可达的有向图。这种图如果顶点顺序形成环路，就可以最少用N条边连接N个顶点。
由于图的结构比较复杂，任意两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。这一点同其他数据结构（如线性表、树）不同。因为图中的顶点具有相对概念，没有固定的位置，且顶点和顶点之间通过添加和删除边，维持着不同的关系。考虑图的定义，图是由顶点和边组成的。所以，分别考虑如何存储顶点和边。图常用的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
我们以比较简单的abc3个顶点的强连通图为例，用邻接矩阵来表示，行分别表示abc，列也表示abc。(a,b)=1表示a向b有边；(a,c)=0表示a向c没有边；(c,a)=1表示c向a有边。这个表示3个顶点有向连通图的邻接矩阵中的非零数据有3个。因此对于N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在N个非零元素，选B。
10.以下对数据结构的表述不恰当的一项为：（）。
A.图的深度优先遍历算法常使用的数据结构为栈。
B.栈的访问原则为后进先出，队列的访问原则是先进先出。
C.队列常常被用于广度优先搜索算法。
D.栈与队列存在本质不同，无法用栈实现队列。
选项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-next=p-next;
C.s-prev=p;s-next=p-next;p-next=s;p-next-prev=s;
D.s-next=p-next;p-next-prev=s;s-prev=p;p-next=s;
本题又考到了指针，再次预示指针将成为新的高频考点。
要形成P-s-“p的next”的形式。
A选项p-next=s;s-next=p-next;有误，成了s-s。
B选项的s-prev=p;s-next=p-next;有误，成了s-s。
C选项的p-next=s;p-next-prev=s;有误，成了s-s。
D选项正确。
12.以下排序算法的常见实现中，哪个选项的说法是错误的：（）。
A.冒泡排序算法是稳定的
B.简单选择排序是稳定的
C.简单插入排序是稳定的
D.归并排序算法是稳定的
排序稳定的意思是当序列中有多个相同数字时，排序后这些项之间的相对顺序不变。常见排序分类如图，所以选B。
13.八进制数32.1对应的十进制数是（）。
A.24.
B.24.
C.26.
D.26.
N进制转十进制，按位权展开再相加。
所以选C。
14.一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串abcab有（）个内容互不相同的子串。