精英班CSP-J第四套题目

1. 以下哪种功能没有涉及 C++语言的面向对象特性支持：（ ）**。 {{ select(1) }}

• C++中调用 printf 函数
• C++中调用用户定义的类成员函数
• C++中构造一个 class 或 struct
• C++中构造来源于同一基类的多个派生类

2. 有 6 个元素，按照 6、5、4、3、2、1 的顺序进入栈 S，请问下列哪个出栈序列是非法的( )**。 {{ select(2) }}

• 5 4 3 6 1 2
• 4 5 3 1 2 6
• 3 4 6 5 2 1
• 2 3 4 1 5 6

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

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

{{ select(3) }}

• 将 x 的值赋为 201
• 将 y 的值赋为 101
• 将 q 指向 x 的地址
• 将 p 指向 y 的地址

4. 链表和数组的区别包括（ ）。 {{ select(4) }}

• 数组不能排序，链表可以
• 链表比数组能存储更多的信息
• 数组大小固定，链表大小可动态调整
• 以上均正确

5. 对假设栈 S 和队列 Q 的初始状态为空。存在 e1~e6 六个互不相同的数据，每个数据按照 进栈 S、出栈 S、进队列 Q、出队列 Q 的顺序操作，不同数据间的操作可能会交错。已知 栈 S 中依次有数据 e1、e2、e3、e4、e5 和 e6 进栈，队列 Q 依次有数据 e2、e4、e3、 e6、e5 和 e1 出队列。则栈 S 的容量至少是（ ）个数据**。 {{ select(5) }}

• 2
• 3
• 4
• 6

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

• *+a-bcd
• +a*-bcd
• abc-d*+
• abc-+d

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

• 1
• 2
• 2 或 3
• 3

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

• 8、18
• 10、18
• 8、19
• 10、19

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

• N-1
• N
• N+1
• N2

10. 以下对数据结构的表述不恰当的一项为：（ ）**。 {{ select(10) }}

• 图的深度优先遍历算法常使用的数据结构为栈。
• 栈的访问原则为后进先出，队列的访问原则是先进先出。
• 队列常常被用于广度优先搜索算法。
• 栈与队列存在本质不同，无法用栈实现队列。

11. 以下哪组操作能完成在双向循环链表结点 p 之后插入结点 s 的效果（其中， next 域为结点的直接后继， prev 域为结点的直接前驱）：（ ）**。 {{ select(11) }}

• p->next->prev=s; s->prev=p; p->next=s; s->next=p->next;
• p->next->prev=s; p->next=s; s->prev=p; s->next=p->next;
• s->prev=p; s->next=p->next; p->next=s; p->next->prev=s;
• s->next=p->next; p->next->prev=s; s->prev=p; p->next=s;

12. 以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）**。 {{ select(12) }}

• 冒泡排序算法是稳定的
• 简单选择排序是稳定的
• 简单插入排序是稳定的
• 归并排序算法是稳定的

13. 八进制数 32.1 对应的十进制数是（ ）。 {{ select(13) }}

• 24.125
• 24.250
• 26.125
• 26.250

14. 一个字符串中任意个连续的字符组成的子序列称为该字符串的子串，则字符串 abcab 有 ( )个内容互不相同的子串。 {{ select(14) }}

• 12
• 13
• 14
• 15

15. 以下对递归方法的描述中，正确的是：( ) {{ select(15) }}

• 递归是允许使用多组参数调用函数的编程技术
• 递归是通过调用自身来求解问题的编程技术
• 递归是面向对象和数据而不是功能和逻辑的编程语言模型
• 递归是将用某种高级语言转换为机器代码的编程技术