CSP初赛 第12节 基础算法

第二章 程序设计基础知识
本题库配套信息学奥赛一本通(初赛真题解析)第68页-第74页真题在线评测。
本套题目共21题,满分105分。
需要下载错题集微信联系tony老师:makytony
*
您的姓名:
一、单项选择题(共17题,每题5分,共计85分;每题有且仅有一个正确选项)
*
1.周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是:先洗菜10 分钟,然后切菜10 分钟,最后炒菜10 分钟。那么做一道菜需要30 分钟。注意:两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗,也不能同时切。那么做完三道菜的最短时间需要()分钟。
A. 90
B. 60
C. 50
D. 40
*
2.2017 年10 月1 日是星期日,1999 年10 月1 日是()。
A. 星期三
B. 星期日
C. 星期五
D. 星期二
*
3.下面的故事与()算法有着异曲同工之妙。从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:“从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事……’”
A. 枚举
B. 递归
C. 贪心
D. 分治
*
4.()是一种选优搜索法,按选优条件向前搜索,以达到目标。当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择。
A. 回溯法
B. 枚举法
C. 动态规划
D. 贪心法
*
5.将(2, 6, 10, 17)分别存储到某个地址区间为0~10的哈希表中,如果哈希函数h(x) = (),将不会产生冲突,其中a mod b表示a除以b的余数。
Ax mod 11
Bx^2 mod 11
C(2x) mod 11
D⌊sqrt(x) ⌋mod 11,其中⌊sqrt(x) ⌋表示sqrt(x)下取整
*
6.()就是把一个复杂的问题分成两个或者更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后的子问题可以简单的直接求解。而原问题的解就是子问题解的并。
A.动态规划
B.贪心
C.分治
D.搜索
*
7.给定含有n 个不同的数的数组L=<x1, x2, ..., xn>。如果L 中存在x (1 < i < n)使得x1 < x2 < ... < xi-1 < xi > xi+1 > ... > xn, 则称 L 是单峰的,并称xi 是L 的“峰顶”。现在已知L 是单峰的,请把a-c 三行代码补全到算法中使得算法正确找到L 的峰顶。
A. c, a, b
B. c, b, a
C. a, b, c
D. b, a, c
*
8.在n(n ≥ 3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把a-c 三行代码补全到算法中。

正确的填空顺序是()。*
A. b, c, a
B. c, b, a
C. c, a, b
D. a, b, c
*
9.应用快速排序的分治思想,可以实现一个求第K大数的程序。假定不考虑极端的最坏情况,理论上可以实现的最低的算法时间复杂度为()。
A. O( n^2)
B. O(n log n)
C. O(n)
D. O(1)
*
10.设有100个数据元素,采用折半搜索时,最大比较次数为()。
A.6
B.7
C.8
D.10
*
11.有一个由4000个整数构成的顺序表,假定表中的元素已经按升序排列,采用二分查找定位一个元素。则最多需要()几次比较就能确定是否存在所查找的元素:
A.11次
B.12次
C.13次
D.14次
*
12.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88,92,100}进行二分查找,成功查找元素19的查找长度(比较次数)是()。
A. 1
B. 2
C. 3
D. 4
*
13. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找,等概率的情况下查找成功的平均查找长度(平均比较次数)是()。
A. 35/11
B. 34/11
C. 33/11
D. 32/11
E. 34/10
*
14.在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了()思想的算法。
A.贪心
B.分治
C.递推
D.回溯
*
15.将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列,每次可以交换任意两个元素,最少需要交换()次。
A. 4
B. 5
C. 6
D. 7
*
16.给定一个含N 个不相同数字的数组,在最坏情况下,找出其中最大或最小的数,至少需要N - 1 次比较操作。则最坏情况下,在该数组中同时找最大与最小的数至少需要()次比较操作。(⌈ ⌉表示向上取整,⌊ ⌋表示向下取整)
A. ⌈3N / 2⌉ - 2
B. ⌊3N / 2⌋ - 2
C. 2N - 2
D. 2N - 4
*
17.有正实数构成的数字三角形排列形式如图所示。

第一行的数为a11;第二行的数从左到右依次为a21, a22;…第n 行的数为an1, an2, …, ann。从a11开始,每一行的数aij 只有两条边可以分别通向下一行的两个数a(i+1)j 和a(i+1)(j+1)。用动态规划算法找出一条从a11 向下通到an1, an2, …, ann 中某个数的路径,使得该路径上的数之和达到最大。
令C[i,j]是从a11 到aij 的路径上的数的最大和,并且C[i,0]=C[0,j]=0,则C[i,j]=()。*
A. max{C[i-1,j-1], C[i-1,j]} + aij
B. C[i-1,j-1] + C[i-1,j]
C. max{C[i-1,j-1], C[i-1,j]} + 1
D. max{C[i,j-1],C[i-1,j]} + aij
二、不定项选择题(共4题,每题5 分,共计20分;每题有一个或多个正确选项,多选或少选均不得分)
*
1.散列表的地址区间为0-10,散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突,并将关键字序列26,25,72,38,8,18,59存储到散列表中,这些元素存入散列表的顺序并不确定。假定之前散列表为空,则元素59存放在散列表中的可能地址有(ABC):【多选题】
A.5
B.7
C.9
D.10
*
2.从顶点A0出发,对有向图()进行广度优先搜索(BFS)时,一种可能的遍历顺序是A0, A1, A2, A3, A4。【多选题】
A.
B.
C.
D.
*
3.以A0作为起点,对下面的无向图进行深度优先遍历时(遍历的顺序与顶点字母的下标无关),最后一个遍历到的顶点可能是()。
【多选题】
A.A1
B.A2
C.A3
D.A4
*
4.现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为700、600、300、400。那么,“也”字的编码长度可能是()。【多选题】
A. 1
B. 2
C. 3
D. 4
问卷星提供技术支持
举报