204 基础算法

您的姓名：

【NOIP2016】周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负 责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜 10 分钟，然后切菜 10 分钟， 最后炒菜 10 分钟。那么做一道菜需要 30 分钟。注意： 两道不同的菜的相同步骤不可以 同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短 时间需要（）分钟。

【NOIP2017】2017 年 10 月 1 日是星期日，1999 年 10 月 1 日是（）。

【NOIP2018】下面的故事与（）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....

【NOIP2011】（）是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。

【NOIP2013】将(2, 6, 10, 17)分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h(x) = （），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。

【NOIP2012】（）就是把一个复杂的问题分成两个或者更多的相同或相似的子问题，再 把子问题分成更小的子问题……直到最后的子问题可以简单的直接求解。而原问题的解就是 子问题解的并。

【NOIP2016】给定含有 n 个不同的数的数组 L=<x1, x2, ..., xn>。如果 L 中存在 xi(1<i<n)使得 x1<x2< ... < xi-1 < xi > xi+1 > ... > xn，则称 L 是单 峰的，并称 xi 是 L 的“峰顶”。现在已知 L 是单峰的，请把 a-c 三行代码补全到算法中使得算法正确找到 L 的峰顶。
a. Search(k+1, n) b. Search(1, k-1) c. return L[k]
Search(1, n)
1. k← ⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then __________
6. else __________
正确的填空顺序是()。

【NOIP2017】在 n（ n≥3）枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重）， 如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的 算法。请把 a-c 三行代码补全到算法中。
（a） A←X ∪ Y
（b） A←Z
（c） n←|A|
算法 Coin(A, n)
（1） k ←⌊n/3」
（2） 将 A 中硬币分成 X，Y，Z 三个集合，使得|X| = |Y| = K , |Z| = n - 2K
（3） ifW(X) ≠ W(Y) //W(X), W(Y)分别为 X 或 Y 的重量
（4） then _________
（5） else _________
（6） _________
（7） if n>2 then goto 1
（8） if n=2then 任取 A 中 1 枚硬币与拿走硬币比较，若不等， 则它不合格； 若相等， 则 A 中剩下的硬币不合格 .
（9） if n=1 then A 中硬币不合格正确的填空顺序是（）。

【NOIP2011】应用快速排序的分治思想，可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

【NOIP2014】设有 100 个数据元素，采用折半搜索时，最大比较次数为（）。

【NOIP2009】有一个由 4000个整数构成的顺序表，假定表中的元素已经按升序排列， 采用二分查找定位一个元素。则最多需要（）比较就能确定是否存在所查找的元素。

【NOIP2008】对有序数组{5, 13, 19, 21, 37, 56, 64, 75,88，92，100}进行二分查找，成功查找元素 19 的查找长度（比较次数）是（）。

【NOIP2008】对有序数组{5, 13, 19, 21, 37, 56, 64, 75,88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。

【NOIP2015】在数据压缩编码的应用中，哈夫曼(Huffman)算法是一种采用了（）思想的算法。

【NOIP2008】将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。

【NOIP2018】给定一个含 N 个不相同数字的数组，在最坏情况下， 找出其中最大或最 小的 数，至少需要 N - 1 次比较操作。则最坏情况下，在该数组中同时找最大与 最小的 数至少需要（）次比较操作。 (⌈⌉表示向上取整， ⌊⌋表示向下取整）

【NOIP2017】有正实数构成的数字三角形排列形式如图所示。

【NOIP2009】散列表的地址区间为 0-10,散列函数为 H(K)=K%11。采用开地址法的线 性探查法处理冲突，并将关键字序列 26，25，72，38，8，18，59 存储到散列表中，这些 元素存入散列表的顺序并不确定。假定之前散列表为空，则元素 59存放在散列表中的可能地址有()。【多选题】

【NOIP2012】从顶点 A0 出发，对有向图(AD)进行广度优先搜索(BFS)时，一种可能的遍历顺序是 A0 , A1 , A2, A3, A4。【多选题】

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

【多选题】

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