历年CSP

学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：历年CSP-J初赛真题解析 | 汇总-CSDN博客

1、以下哪种功能没有涉及C++语言的面向对象特性支持：（ ）。

A.C++中调用printf函数

B.C++中调用用户定义的类成员函数

C.C++中构造一个class或struct

D.C++中构造来源于同一基类的多个派生类

【答案】：A

【解析】

A：printf是C语言中的函数，C语言是面向过程语言

B/C/D选项中均有class，所以涉及面向对象特性

2、有6个元素，按照6、5、4、3、2、1的顺序进入栈S，请问下列哪个出栈序列是非法的（ ）。

A.543612

B.453126

C.346521

D.234156

【答案】：C

【解析】

A/B/D按照6、5、4、3、2、1顺序进栈，可以实现该顺序出栈

C：需要6出栈时，6不是栈顶，而是5，所以无法出栈

3、运行以下代码片段的行为是（ ）。

A.将x的值赋为201

B.将y的值赋为101

C.将q指向x的地址

D.将p指向y的地址

【答案】：D

【解析】

D：p = q，将p也指向y的地址

4、链表和数组的区别包括（ ）。

A.数组不能排序，链表可以

B.链表比数组能存储更多的信息

C.数组大小固定，链表大小可动态调整

D.以上均正确

【答案】：C

【解析】

A：数组可以排序

B：不一定，数组也可以是结构体数组，可以放任意多的信息

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

【解析】

依次有e2、e4、e3、e6、e5和e1出队列，即表示有e2、e4、e3、e6、e5、e1顺序出栈。

栈S最大容量为3，即存放e1、e3、e4或e1、e5、e6时需要（从栈底到栈顶）

6、对表达式a+(b-c)*d的前缀表达式为（ ），其中+、-、*是运算符。

A.*+a-bcd

B.+a*-bcd

C.abc-d*+

D.abc-+d

【答案】：B

【解析】

a+(b-c)*d是常见的中缀表达式，中缀表达式转为前缀表达式，可以使用

1.加括号：a+(b-c)*d --> (a+((b-c)*d))

2.将运算符移到每对运算式的左边：+(a(*(-bc)d))

3.去括号：+a*-bcd

7、假设字母表{a, b, c, d, e}在字符串出现的频率分别为10%，15%，30%，16%，29%。若使用哈夫曼编码方式对字母进行不定长的二进制编码，字母d的编码长度为（ ）位。

A.1

B.2

C.2或3

D.3

【答案】：B

【解析】

哈夫曼编码每次就是选择两个最小的频率合成出一个新的数，依次往复，构成一棵树。

此题先用10和15合成25，再选16和25合成41，再选29和30合成59，最后把41和59合成100。

构建哈夫曼树后，往左走的都是0，往右走的都是1，d的编码长度为2位，编码为00。

8、一棵有n个结点的完全二叉树用数组进行存储与表示，已知根结点存储在数组的第1个位置。若存储在数组第9个位置的结点存在兄弟结点和两个子结点，则它的兄弟结点和右子结点的位置分别是（ ）。

A.8、18

B.10、18

C.8、19

D.10、19

【答案】：C

【解析】

完全二叉树在数组中存放的形式为[1,2,3,4,5,6,7,8,9,...]。

9为奇数，即右节点，其兄弟节点是8，其右子节点是n*2+1，即19。

9、考虑由N个顶点构成的有向连通图，采用邻接矩阵的数据结构表示时，该矩阵中至少存在（ ）个非零元素。

A.N-1

B.N

C.N+1

D.N2

【答案】：B

【解析】

可以举一个简单的有向连通图，1->2->3->4->1。n个顶点需要n条边连接。

构成二维矩阵时（行编号依次为1234，列编号依次为1234），有4个非零元素。

10、以下对数据结构的表述不恰当的一项为：（ ）。

A.图的深度优先遍历算法常使用的数据结构为栈。

B.栈的访问原则为后进先出，队列的访问原则是先进先出。

C.队列常常被用于广度优先搜索算法。

D.栈与队列存在本质不同，无法用栈实现队列。

【答案】：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；

【答案】：D

【解析】

先将s节点与p的next节点连接起来，即s->next = p->next; p->next->prev = s。

然后再将p与s相连，s->prev = p; p->next = s;

所以选择D

12、以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。

A.冒泡排序算法是稳定的

B.简单选择排序是稳定的

C.简单插入排序是稳定的

D.归并排序算法是稳定的

【答案】：B

【解析】

排序算法是否稳定，就是看相同的元素在排序前和排序后，相对位置是否稳定。如两个2排序，排序后第1个2必须还是在第2个2前面。

简单记忆规则如下：

1.选择、冒泡、插入排序算法中选择不稳定

2.归并、堆排序算法中堆不稳定

3.快排、希尔排序算法，两个都不稳定

4.基数、桶、计数排序算法，都稳定

13、八进制数32.1对应的十进制数是（ ）。

A.24.125

B.24.250

C.26.125

D.26.250

【答案】：C

【解析】

其他进制转十进制的方法为按权展开求和。

3*8^1 + 2*8^0 + 1*8^-1 = 26.125

14、一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串abcab有（ ）个内容互不相同的子串。

A.12

B.13

C.14

D.15

【答案】：B

【解析】

一种方法就是列出所有的子串，注意需要包括空串。另一种可以按插空法计算。

左端点有6种选择方式，右端点有5种选择方式，所以共6*5=30种，此时没有考虑右端点小于左端点，所以需要30/2=15种，再加上1个空串，共16种

相同子串中，ab有2个，a有2个，b有2个，相同的子串可以只算1个，所以需要16-3=13种，选B。

15、以下对递归方法的描述中，正确的是：（ ）

A.递归是允许使用多组参数调用函数的编程技术

B.递归是通过调用自身来求解问题的编程技术

C.递归是面向对象和数据而不是功能和逻辑的编程语言模型

D.递归是将用某种高级语言转换为机器代码的编程技术

【答案】：B

【解析】

递归就是通过调用自身来解决问题的一种编程技术