CSP-J 数据结构基础与代码阅读综合测试

本试卷共 25 道单项选择题，每题 4 分，满分 100 分。

一、结构体、指针与链表

1. 定义结构体类型时，结构体定义结束后不能省略的是（ ）。

{{ select(1) }}

• 左大括号 {
• 分号 ;
• 关键字 using
• 关键字 return

2. 已知 Student *p 指向一个结构体对象，访问其成员 score 的正确写法是（ ）。

{{ select(2) }}

• p.score
• p::score
• p->score
• *p.score

3. 对于代码 int num=4; int *p=#，变量 p 中保存的是（ ）。

{{ select(3) }}

• num 的地址
• 整数 4
• 指针本身的大小
• num 的类型

4. 执行下面代码后，num 的值是（ ）。

int num = 4;
int *p = #
*p = 10;

{{ select(4) }}

• 4
• 6
• 10
• 无法确定

5. 下列关于单链表的说法正确的是（ ）。

{{ select(5) }}

• 节点必须连续存放
• 可以像数组一样用下标进行 O(1) 随机访问
• 节点通过指针连接，内存中不要求连续
• 每个节点都不需要额外存储指针

6. 在带头节点的单链表中，判断链表没有有效数据节点的条件通常是（ ）。

{{ select(6) }}

• head == nullptr
• head->next == nullptr
• head->data == 0
• head->next == head

7. 在单链表节点 p 后插入新节点 s，正确的指针修改顺序是（ ）。

{{ select(7) }}

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

8. 已知 pre 指向待删除节点 p 的前驱，删除 p 的正确操作是（ ）。

{{ select(8) }}

• delete pre; pre=p;
• delete p; pre->next=p->next;
• pre->next=p->next; delete p;
• p->next=pre; delete p;

9. 按下标访问第 i 个元素时，数组与单链表的常见时间复杂度分别是（ ）。

{{ select(9) }}

• O(1)、O(1)
• O(n)、O(1)
• O(1)、O(n)
• O(n)、O(n)

二、栈、队列与循环队列

10. 栈遵循的基本规律是（ ）。

{{ select(10) }}

• 先进先出
• 后进先出
• 随机进出
• 只能进不能出

11. 关于 stack<int> s 的 s.pop()，正确的是（ ）。

{{ select(11) }}

• 返回并删除栈顶元素
• 只返回栈顶元素
• 只删除栈顶元素，不返回值
• 清空整个栈

12. 阅读下面代码，输出结果是（ ）。

stack<int> s;
s.push(2);
s.push(5);
s.push(8);
s.pop();
cout << s.top();

{{ select(12) }}

• 2
• 5
• 8
• 程序一定报错

13. 队列遵循的基本规律是（ ）。

{{ select(13) }}

• 后进先出
• 先进先出
• 只能从队尾删除
• 只能从队头加入

14. 阅读下面代码，输出结果是（ ）。

queue<int> q;
q.push(4);
q.push(7);
q.push(9);
q.pop();
cout << q.front() << " " << q.back();

{{ select(14) }}

• 4 9
• 7 9
• 7 7
• 9 7

15. 使用长度为 N 的数组实现循环队列，并故意空出一个位置区分队空与队满。队满条件是（ ）。

{{ select(15) }}

• front == rear
• (front + 1) % N == rear
• (rear + 1) % N == front
• rear == N

16. 使用“空出一个位置”的循环队列时，长度为 N 的数组最多能保存（ ）个元素。

{{ select(16) }}

• N-1
• N
• N+1
• 2N

三、STL 容器

17. 关于 set，下列说法正确的是（ ）。

{{ select(17) }}

• 允许重复元素且自动降序
• 不允许重复元素，默认自动升序
• 允许重复元素且保持插入顺序
• 只能保存字符串

18. 阅读下面代码，输出结果是（ ）。

set<int> s;
s.insert(5);
s.insert(2);
s.insert(5);
s.insert(3);
for (int x : s) cout << x << " ";

{{ select(18) }}

• 5 2 5 3
• 2 3 5
• 5 3 2
• 2 3 5 5

19. 已知 map<int,int> mp;，执行 cout << mp[8]; 后，正确的是（ ）。

{{ select(19) }}

• 编译错误
• 输出随机值
• 输出 0，并自动创建键 8
• 输出 0，但 map 不发生变化

20. 若 vector<int> a 当前有 n 个元素，则合法下标范围是（ ）。

{{ select(20) }}

• 1 到 n
• 0 到 n
• 0 到 n-1
• 任意整数

21. vector 在中间位置执行 erase 的常见时间复杂度是（ ）。

{{ select(21) }}

• O(1)
• O(log n)
• O(n)
• O(n^2)

22. 下列最适合实现广度优先搜索 BFS 的数据结构是（ ）。

{{ select(22) }}

• 栈
• 队列
• set
• map

四、表达式

23. 中缀表达式 a+b*c 对应的后缀表达式是（ ）。

{{ select(23) }}

• ab+c*
• abc*+
• +a*bc
• abc+*

24. 后缀表达式 8 2 - 的值是（ ）。

{{ select(24) }}

• -6
• 6
• 10
• 16

25. 对后缀表达式求值时，遇到二元运算符并从栈中弹出两个数，正确的顺序是（ ）。

{{ select(25) }}

• 先弹出左操作数，再弹出右操作数
• 先弹出右操作数，再弹出左操作数
• 两个操作数顺序可以任意
• 只需要弹出一个操作数