2024CSP-J原创初赛模拟卷7

5.下列关于栈与队列描述错误的是（）。

A.只要确定了入栈次序，即可确定出栈次序

B.栈只允许在栈顶的一端进行入栈与出栈的操作

C.队列进行删除操作总是删除最早入队的元素

D.队列只允许在表的一端进行插入，而在表的另外一端进行删除的线性表

7.下列关于邻接表的描述正确的是（）

A.对于稀疏图，邻接表存储造成存储空间的浪费

B.图邻接表表示方法唯一

C.求有向图顶点的入度需要遍历全部邻接表

D.在无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的两倍

8.在一个单链表中，已知 a 所指向的结点是 b 所指向结点的前驱结点，若在 a 和 b 之间插入一个结点 c，则执行（）

A.a -> next = c; c -> next = b;

B.c -> next = b -> next; b -> next = c;

C.b -> next = c -> next; c -> next = b;

D.b -> next = c; c -> next = a;

14.下列关于排序算法的描述正确的是（）

A.冒泡排序的时间复杂度为 O(n2)，是一个不稳定的排序方法

B.选择排序的时间复杂度为 O(n2)，是一个稳定的排序方法

C.快速排序在糟糕的情况下时间复杂度为 O(n2)

D.希尔排序是对选择排序算法的优化

二、程序阅读理解题（共3大题。程序输入不超过数组或字符串定义的范围，除特殊说明外，判断题1.5分，选择题3分，共计40分）

1. （12分）

l判断题

2.（13.5分）

l判断题

3.（14.5分）

假设程序输入的 n 和 m 保证不超过 100。

l判断题

29.当程序输入的 n = 2, m = 2，紧接着输入

48 56

24 72

程序的运行结果是 12。（）

对

错

31(1)若程序输入

3 3

12 4 9

6 12 2

8 6 12

程序的运行结果是（）

A.3 4

B. 3 2

C.3 3

D. 3 3

三、程序完善题（共2大题，每个选择题3分，共计30分）

1.题目描述

花店有 n(n <= 500) 朵花束，每朵花束有自己的价格、新鲜度与美丽值（范围都在0~500的范围内），小明有 cj(0 <= cj <= 500) 元，小明用自己的钱购买一定数量的花束，要求购买的花束的新鲜度之和至少为 k(0 <= k <= 500) 的前提下最大美丽值是多少。

例如有 5 朵花束，小明有 10 元，期待花束的新鲜度之和至少为 10，第一朵花束到第五朵花束的价格、新鲜度与美丽值分别是：

2 4 5

4 3 3

1 3 2

3 4 3

3 2 5

小明在不超过 10 元的前提下保证购买花束的新鲜度之和至少为 10 的前提下，购买花束的最大美丽值之和为 15。

2..题目描述

一棵有 n 个结点的无根树，每个结点的编号从 1 到 n，这棵树有 n-1 条边，给出每条边连接的两个结点信息，如果某个结点可以成为根节点，问这棵树哪些结点可能是根结点，注意与根结点直接相连的结点，它们的子树大小都相同。

例如: n = 2

1 2

树中只有一条边，连接的结点是 1 和 2，根节点可能是 1，可能是 2，因此输出可能作为根节点是 1 2。

姓名：
姓名：
班级：
班级：
学校:
学校: