第二章 程序设计基本知识

第4节 基础算法

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

{{ select(1) }}

• 90
• 60
• 50
• 40

2.【NOIP2017】2017年10月1日是星期日，1999年10月1日是()。

{{ select(2) }}

• 星期三
• 星期日
• 星期五
• 星期二

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

{{ select(3) }}

• 枚举
• 递归
• 贪心
• 分治

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

{{ select(4) }}

• 回溯法
• 枚举法
• 动态规划
• 贪心法

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

{{ select(5) }}

• x mod 11
• x²mod 11
• 2x mod 11
• $\lfloor \sqrt{x} \ \rfloor \ mod \ 11$,其中$\lfloor \sqrt{x} \ \rfloor$表示$\sqrt{x} \$下取整

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

{{ select(6) }}

• 动态规划
• 贪心
• 分治
• 搜索

7.【NOIP2016】给定含有n个不同的数的数组L=<x1,x2,…,xn>。如果L中存在x(1<i<n)使得x1<x2< … <xi-1xi+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________

正确的填空顺序是( )。

{{ select(7) }}

• c,a,b
• c,b,a
• a,b,c
• b,a,c

8.【NOIP2017】在n(n≥3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。

(a) A←X U 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) ifn=2 then任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A中剩下的硬币不合格.

(9) if n=1 then A中硬币不合格

正确的填空顺序是()。

{{ select(8) }}

• b,c,a
• c,b,a
• c,a,b
• a,b,c

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

{{ select(9) }}

• O(n²)
• O(n log n)
• O(n)
• O(1)

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

{{ select(10) }}

• 6
• 7
• 8
• 10

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

{{ select(11) }}

• 11次
• 12次
• 13次
• 14次

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

{{ select(12) }}

• 1
• 2
• 3
• 4

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

{{ select(13) }}

• 35/11
• 34/11
• 33/11
• 32/11
• 34/10

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

{{ select(14) }}

• 贪心
• 分治
• 递推
• 回溯

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

{{ select(15) }}

• 4
• 5
• 6
• 7

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

{{ select(16) }}

• $\lceil 3N/2\rceil-2$
• $\lfloor 3N/2 \rfloor -2$
• $2N -2$
• $2N -4$

17.【NOIP2017】有正实数构成的数字三角形排列形式如图所示。第一行的数为$a_{11}$;第二行的数从左到右依次为$a_{21},a_{22},…,$第$n$行的数为$a_{n1},a_{n2},…,a_{nn}$。从$a_{11}$开始，每一行的数$a_{ij}$只有两条边可以分别通向下一行的两个数$a_{(i+1)j}$和 $a_{(i+1)(j+1)}$。用动态规划算法找出一条从$a_{11}$向下通到$a_{n1},a_{n2},…,a_{nn}$中某个数的路径，使得该路径上的数之和达到最大。

令$C[i,j]$是从$a_{11}$到$a_{ij}$的路径上的数的最大和，并$c[i,0]=C[0,j]=0,$则$c[i,j]=()$。

a11
     a21 a22
   a31 a32 a33
    ........
an1  an2  ...  ann

{{ select(17) }}

• max{C[i-1,j-1],c[i-1,j]}+aij
• C[i-1,j-1]+C[i-1,j]
• max{C[i-1,j-1],c[i-1,j]}+1
• max{C[i,j-1],C[i-1,j]}+aij

不定项选择题

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

{{ multiselect(18) }}

• 5
• 7
• 9
• 10

2.【NOIP2012】从顶点$A_0$出发，对有向图( )进行广度优先搜索(BFS)时，一种可能的遍历顺序是$A_{0},A₁,A₂,A₃,A₄$。

{{ multiselect(19) }}

• A
• B
• C
• D

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

{{ multiselect(20) }}

• A₁
• A₂
• A₃
• A₄

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

{{ multiselect(21) }}

• 1
• 2
• 3
• 4