CSP-S 卷

一次期末考试，某班有 $15$ 人数学得满分，有 $12$ 人语文得满分，并且有 $4$ 人语、数都是满分，那么这个班至少有一门得满分的同学有多少人？（ ）

现有一段 $8$ 分钟的视频文件，它的播放速度是每秒 $24$ 帧图像，每帧图像是一幅分辨率为 $2048\times1024$ 像素的 $32$ 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。

今有一空栈 $S$，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈底元素为（ ）。

广度优先搜索时，一定需要用到的数据结构是（ ）。

二进制数 $00101010_2$ 和 $00010110_2$ 的和为（ ）。

在程序运行过程中，如果递归调用的层数过多，可能会由于（ ）引发错误。

小明希望选到形如 省A·LLDDD 的车牌号。车牌号在 · 之前的内容固定不变；后面的 $5$ 位号码中，前 $2$ 位必须是大写英文字母，后 $3$ 位必须是阿拉伯数字（$L$ 代表 A 至 Z，$D$ 代表 $0$ 至 $9$，两个 $L$ 和三个 $D$ 之间可能相同也可能不同）。总共有多少个可供选择的车牌号？（ ）

下面哪个数据结构最适合实现先进先出（FIFO）的功能？

设变量 x 为 float 型且已赋值，则以下语句中能将 x 中的数值保留到小数点后两位，并将第三位四舍五入的是（ ）

由数字 $1,1,2,4,8,8$ 所组成的不同的 $4$ 位数的个数是（ ）。

有一个等比数列，共有奇数项，其中第一项和最后一项分别是 $2$ 和 $118098$，中间一项是 $486$，请问以下哪个数是可能的公比？（ ）

表达式 a*(b+c)-d 的后缀表达形式为（ ）。

定义一种字符串操作为交换相邻两个字符。将 DACFEB 变为 ABCDEF 最少需要（ ）次上述操作。

若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（ ）。

共有 $8$ 人选修了程序设计课程，期末大作业要求由 $2$ 人组成的团队完成。假设不区分每个团队内 $2$ 人的角色和作用，请问共有多少种可能的组队方案。（ ）

以下对数据结构的表述不恰当的一项是（ ）。

一位玩家正在玩一个特殊的掷骰子游戏，游戏要求连续掷两次骰子，收益规则如下：玩家第一次掷出 $x$ 点，得到 $2x$ 元；第二次掷出 $y$ 点，当 $y=x$ 时玩家会失去之前得到的 $2x$ 元，而当 $y\ne x$ 时玩家能保住第一次获得的 $2x$ 元。其中 $x,y\in\{1,2,3,4,5,6\}$。

例如，玩家第一次掷出 $3$ 点得到 $6$ 元后，第二次再次掷出 $3$ 点，会失去之前得到的 $6$ 元，最终收益为 $0$ 元；如果第二次掷出 $4$ 点，则最终收益为 $6$ 元。假设骰子掷出任意一点的概率均为 $\frac{1}{6}$，玩家连续掷两次骰子后，所有可能情形下收益的平均值是多少？（ ）

对数组进行二分查找的过程中，以下哪个条件必须满足？（ ）

一些数字可以颠倒过来看，例如 $0$、$1$、$8$ 颠倒过来还是本身，$6$ 颠倒过来是 $9$，$9$ 颠倒过来看还是 $6$，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如 $106$ 颠倒过来是 $901$。假设某个城市的车牌只有 $5$ 位数字，每一位都可以取 $0$ 到 $9$。请问这个城市有多少个车牌倒过来恰好还是原来的车牌，并且车牌上的 $5$ 位数能被 $3$ 整除？（ ）

以下哪些算法不属于贪心算法？（ ）

一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 $n$ 在以下哪个区间？已知 $n<60$。（ ）

小明想通过走楼梯来锻炼身体，假设从第 $1$ 层走到第 $2$ 层消耗 $10$ 卡热量，接着从第 $2$ 层走到第 $3$ 层消耗 $20$ 卡热量，从第 $3$ 层走到第 $4$ 层消耗 $30$ 卡热量，依此类推，从第 $k$ 层走到第 $k+1$ 层消耗 $10k$ 卡热量（$k>1$）。如果小明想从 $1$ 层开始，通过连续向上爬楼梯消耗 $1000$ 卡热量，至少要爬到第几层楼？（ ）

令根结点的高度为 $1$，则一棵含有 $2021$ 个结点的二叉树的高度至少为（ ）。

前序遍历和中序遍历相同的二叉树为且仅为（ ）。

计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++ 代码段表示的程序，将分别输出什么结果？（ ）

01unsigned x = 0xDEADBEEF;
02unsigned char *p = (unsigned char *)&x;
03printf("%X", *p);

一个深度为 $5$（根结点深度为 $1$）的完全 $3$ 叉树，按前序遍历的顺序给结点从 $1$ 开始编号，则第 $100$ 号结点的父结点是第（ ）号。

假设有 $n$ 根柱子，需要按照以下规则依次放置编号为 $1,2,3,\ldots$ 的圆环：每根柱子的底部固定，顶部可以放入圆环；每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 $4$ 根柱子时，最多可以放置（ ）个圆环。

最长公共子序列长度常常用来衡量两个序列的相似度。给定两个序列 $X=\{x_1,x_2,x_3,\ldots,x_m\}$ 和 $Y=\{y_1,y_2,y_3,\ldots,y_n\}$，最长公共子序列（LCS）问题的目标是找到一个最长的新序列 $Z=\{z_1,z_2,z_3,\ldots,z_k\}$，使得序列 $Z$ 既是序列 $X$ 的子序列，又是序列 $Y$ 的子序列，且序列 $Z$ 的长度 $k$ 在满足上述条件的序列里最大。

序列 $A$ 是序列 $B$ 的子序列，当且仅当在保持序列 $B$ 元素顺序的情况下，从序列 $B$ 中删除若干个元素，可以使得剩余的元素构成序列 $A$。

序列 ABCAAAABA 和 ABABCBABA 的最长公共子序列长度为（ ）。

有如下递归代码：

01solve(t, n):
02    if t=1 return 1
03    else return 5*solve(t-1,n) mod n

则 solve(23,23) 的结果为（ ）。

有 $8$ 个苹果从左到右排成一排，你要从中挑选至少一个苹果，并且不能同时挑选相邻的两个苹果，一共有（ ）种方案。

设一个三位数 $n=\overline{abc}$，$a$、$b$、$c$ 均为 $1\sim9$ 之间的整数，若以 $a$、$b$、$c$ 作为三角形的三条边可以构成等腰三角形（包括等边），则这样的 $n$ 有（ ）个。

每个顶点度数均为 $2$ 的无向图称为“$2$ 正规图”。由编号为从 $1$ 到 $n$ 的顶点构成的所有 $2$ 正规图中，包含欧拉回路的不同 $2$ 正规图的数量为（ ）。

给定地址区间为 $0\sim9$ 的哈希表，哈希函数为 $h(x)=x\%10$，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 $9$ 冲突了则从地址 $0$ 重新开始探查）。哈希表初始为空表，依次存储 (71, 23, 73, 99, 44, 79, 89) 后，请问 89 存储在哈希表哪个地址中。（ ）

有正实数构成的数字三角形排列形式如下图所示。第一行的数为 $a_{1,1}$；第二行的数从左到右依次为 $a_{2,1},a_{2,2}$；第 $n$ 行的数为 $a_{n,1},a_{n,2},\ldots,a_{n,n}$。从 $a_{1,1}$ 开始，每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1},a_{n,2},\ldots,a_{n,n}$ 中某个数的路径，使得该路径上的数之和最大。

令 $C[i][j]$ 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和，并且 $C[i][0]=C[0][j]=0$，则 $C[i][j]=$（ ）

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（$LCA$）是结点 $4$。那么下列哪个结点的 $LCA$ 组合是不可能出现的？