第4节基础算法

您的姓名：



一、单项选择题（共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}进行二分查找，等概率的情况下查找成功的平均查找长度(平均比较次数)是（）。

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。【多选题】

3.以A0作为起点，对下面的无向图进行深度优先遍历时(遍历的顺序与顶点字母的下标无关)，最后一个遍历到的顶点可能是（）。【多选题】

A.A1

B.A2

C.A3

D.A4

4.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（）。【多选题】

A. 1

B. 2

C. 3

D. 4

第4节 基础算法

第4节基础算法