1723: CSP-S20选择题
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Special Judger
Creator：
Submit：11
Solved：0
Description
第 1 题
请选出以下最大的数（ ）。
A. (550)10
B. (777)8
C. 2^10
D. (22F)16
第 2 题
操作系统的功能是（ ）
A. 负责外设与主机之间的信息交换
B. 控制和管理计算机系统的各种硬件和软件资源的使用
C. 负责诊断机器的故障
D. 将源程序编译成目标程序
第 3 题
现有一段 88 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是 一幅分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。
A. 30G
B. 90G
C. 150G
D. 450G
第 4 题
今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。
A. b
B. a
C. d
D. c
第 5 题
将 (2,7,10,18) 分别存储到某个地址区间为 0∼10 的哈希表中，如果哈希函数 h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。
A. x^2 mod 11
B. 2x mod 11
C. x mod 11
D. ⌊x/2⌋ mod 11，其中⌊x/2⌋表示二分之x下取整
第 6 题
下列哪些问题不能用贪心法精确求解？（ ）
A. 霍夫曼编码问题
B. 0-1 背包问题
C. 最小生成树问题
D. 单源最短路径问题
第 7 题
具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。
A. O(n+e)
B. O(n^2)
C. O(e^2)
D. O(n)
第 8 题
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。
A. 144
B. 100
C. 48
D. 122
第 9 题
广度优先搜索时，一定需要用到的数据结构是( )
A. 栈
B. 二叉树
C. 队列
D. 哈希表
第 10 题
—个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 nn 在以下哪个区间？已知 n<60。( ）
A. 30<n<40
B. 40<n<50
C. 50<n<60
D. 20<n<30
第 11 题
小明想通过走楼梯来锻炼身体，假设从第 1 层走到第 2 层消耗 10 卡热量，接着从第 2 层走到第 3 层消耗 20 卡热量，再从第 3 层走到第 4 层消耗 30 卡热量，依此类推，从第 k 层走到第 k+1 层消耗 10k 卡热量 (k>1)？如果小明想从 1 层开始，通过连续向上爬楼梯消耗 1000 卡热量，至少要爬到第几层楼？ （ ）。
A. 14
B. 16
C. 15
D. 13
第 12 题
表达式 a*(b+c)-d 的后缀表达形式为（ ）。
A. abc*+d-
B. -+*abcd
C. abcd*+-
D. abc+*d-
第 13 题
从一个 4×4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。
A. 60
B. 72
C. 86
D. 64
第 14 题
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
A. O((m+n^2)logn)
B. O(mn+n^3)
C. O((m+n)logn)
D. O(n^2)
第 15 题
1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A. 欧拉(Leonhard Euler)
B. 冯·诺伊曼(John von Neumann)
C. 克劳德·香农(Claude Shannon)
D. 图灵(Alan Turing)
请选出以下最大的数（ ）。
A. (550)10
B. (777)8
C. 2^10
D. (22F)16
第 2 题
操作系统的功能是（ ）
A. 负责外设与主机之间的信息交换
B. 控制和管理计算机系统的各种硬件和软件资源的使用
C. 负责诊断机器的故障
D. 将源程序编译成目标程序
第 3 题
现有一段 88 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是 一幅分辨率为 2048×1024 像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。
A. 30G
B. 90G
C. 150G
D. 450G
第 4 题
今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。
A. b
B. a
C. d
D. c
第 5 题
将 (2,7,10,18) 分别存储到某个地址区间为 0∼10 的哈希表中，如果哈希函数 h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。
A. x^2 mod 11
B. 2x mod 11
C. x mod 11
D. ⌊x/2⌋ mod 11，其中⌊x/2⌋表示二分之x下取整
第 6 题
下列哪些问题不能用贪心法精确求解？（ ）
A. 霍夫曼编码问题
B. 0-1 背包问题
C. 最小生成树问题
D. 单源最短路径问题
第 7 题
具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。
A. O(n+e)
B. O(n^2)
C. O(e^2)
D. O(n)
第 8 题
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。
A. 144
B. 100
C. 48
D. 122
第 9 题
广度优先搜索时，一定需要用到的数据结构是( )
A. 栈
B. 二叉树
C. 队列
D. 哈希表
第 10 题
—个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 nn 在以下哪个区间？已知 n<60。( ）
A. 30<n<40
B. 40<n<50
C. 50<n<60
D. 20<n<30
第 11 题
小明想通过走楼梯来锻炼身体，假设从第 1 层走到第 2 层消耗 10 卡热量，接着从第 2 层走到第 3 层消耗 20 卡热量，再从第 3 层走到第 4 层消耗 30 卡热量，依此类推，从第 k 层走到第 k+1 层消耗 10k 卡热量 (k>1)？如果小明想从 1 层开始，通过连续向上爬楼梯消耗 1000 卡热量，至少要爬到第几层楼？ （ ）。
A. 14
B. 16
C. 15
D. 13
第 12 题
表达式 a*(b+c)-d 的后缀表达形式为（ ）。
A. abc*+d-
B. -+*abcd
C. abcd*+-
D. abc+*d-
第 13 题
从一个 4×4 的棋盘中选取不在同一行也不在同一列上的两个方格，共有（ ）种方法。
A. 60
B. 72
C. 86
D. 64
第 14 题
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
A. O((m+n^2)logn)
B. O(mn+n^3)
C. O((m+n)logn)
D. O(n^2)
第 15 题
1948 年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A. 欧拉(Leonhard Euler)
B. 冯·诺伊曼(John von Neumann)
C. 克劳德·香农(Claude Shannon)
D. 图灵(Alan Turing)