NOIP 初赛题目整理（C++）

This blog post is only available in Simplified Chinse.

据说今年所有学校都没有推荐名额？？？

选择/问题求解部分

算法/数据结构系列

排序与复杂度

CCF 可喜欢了 :new_moon_with_face:

在各种查找算法中，平均查找长度（与关键字比较次数的期望值）与查找表中元素个数n无关的查找方法是 A、顺序查找 B、散列查找 C、折半查找 D、动态查找

答案：B
解析：顺序查找是 $O(n)$ 的，折半查找（即二分查找）是 $\log(n)$ 的，显然都与 $n$ 有关。动态查找长度是不确定的（其实和使用哪种动态查找有关）。而散列查找实质上就是哈希。

选择合适的散列函数 $h(key)$ ，散列法的查找效率期望是 $\Theta(1)$ 。它几乎与关键字的空间大小无关，也适合于关键字直接比较计算量大的问题。[1]

在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（）。 A、堆排序 B、希尔排序 C、冒泡排序 D、快速排序

答案：D
解析：堆排序，花费时间显然不改变，希尔排序和插入排序都不一定，因为有可能从前往后、从后往前比较，有两种情况。我们都学过，快速排序在数据有序的时候会退化成 $O(n^2)$ （也就是最差情况）。

快速排序是把数列按一个枢纽值分成两部分分别排序，所以效率高。但是若原数据为有序，并且选择的枢纽值为第一个数时，那在分块时会将一个第一个数前面的数（也就是没有）分为一块，将除第一个数的所有数分成了另一块。这样一来，每一次分块都只减少了一个值，而每次分块的时间为O（N），所以总时间为O（N^2）。[2]

在待排序的数据表已经为有序时，下列排序算法中时间复杂度会减少的是（） A、堆排序 B、希尔排序 C、冒泡排序 D、插入排序

答案：BD
解析： A：堆排序，复杂度与数据表是否有序无关； B：希尔排序（是对插入排序的一个优化），显然会减少的，降为 $\Theta (n)$ C：冒泡排序，比较次数不变； D：也降为 $\Theta (n)$ 。

关于冒泡排序，其步骤是：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

下列关于排序说法正确的是（）。 A、插入排序、冒泡排序是稳定的 B、选择排序的时间复杂度为 $O(n^2)$ C、选择排序、希尔排序、快速排序、堆排序是不稳定的 D、希尔排序、快速排序、堆排序的时间复杂度为 $O(n\log n)$

答案：ABC
解析：

是否稳定看排序后原来相等两数是否会交换位置，因此，如果不是相邻两数比较交换的往往是不稳定。shell 是 $O(n^{1.3})$ ，一般达不到 $O(n\log n)$ ——来自老师的官方题解……

插入排序、冒泡排序都是相邻数字比较交换的，所以稳定；而选排、shell、快排、堆排都不是。维基百科上其实说 shell 复杂度是 $\Theta(n \log^2 n)$ 。总之不可能是 $\Theta (n\log n)$ 。

图论

假设我们用 $d=(a_1,a_2,\dots,,a_5)$ ，表示无向图 $G$ 的5个顶点的度数，下面给出的哪（些）组 $d$ 值合理（） A、 ${5,4,4,3,1}$ B、 ${4,2,2,1,1}$ C、 ${3,3,3,2,2}$ D、 ${2,2,2,2,2}$

答案：BD
解析：其实一开始看到这题可能会画图，但是最后发现可以直接利用无向图的一条性质：所有点的度数之和为偶数。

以下关于图的正确说法是（）。 A、所有顶点的度数之和等于边数的2倍 B、所有顶点的度数之和不一定等于边数的2倍 C、任意一个图一定有偶数个奇点 D、在有向图中顶点的入度之和等于出度之和

答案：ACD
解析：这题不难，只要画几张图看看就可以了。

下列逻辑运算正确的是（） A、A∧(A∨B)=A B、A∨(A∧B)=A C、A∧(C∨B)=A∧B∨A∧C D、A∨(B∧C)=(A∨B)∧(A∨C)

答案：ABCD
解析：这题是非常典型的“逻辑运算表达式比较”。一个很神奇的做法就是：可以把参数看成集合， $∧$ 与 $∨$ 分别看成集合的 $∩$ 与 $∪$ ，就可以直接通过画韦恩图的方式判断了！那么我们思考：为什么可以把 $∧$ 与 $∨$ 分别看成集合的 $∩$ 与 $∪$ 呢？根据意思来理解，“与”可以理解为“两个集合里都有”，也就是交；“或”可以理解为“两个集合之一有或都有”，自然就是集合并了。

无向图 $G=(V,E)$ ，其中 $V={a,b,c,d,e,f}$ ， $E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}$ 。对该图进行深度优先遍历，得到的顶点序列正确的是（）。 A、 $a,b,e,c,d,f$ B、 $a,c,f,e,b,d$ C、 $a,e,b,c,f,d$ D、 $a,b,e,d,f,c$

答案：D
解析：图画出来是这样的：

graph TD;
a---b
a---e
a---c
b---e
c---f
f---d
e---d

需要注意的是 C 选项， $a,e,b,c,f,d$ ，其实当 $b$ 点“无路可走”时并非会走回 $a$ 点，而是从 $e$ 点继续向 $d$ 点走。只要稍微注意下就好了。

下列关于图的说法正确的是： A、欧拉图的每一个顶点都能作为某条欧拉闭迹的起点: B、一个图有欧拉闭迹当且仅当该图有零个奇点 C、若一个无向图有奇数条边，则它必然不是二分图 D、若 G 是汉密尔顿图，则对 G 上的汉密尔顿圈 C，任意删去 n 个点，最多可将 C 划分为 n 段，反之亦然

答案：A
解析：这种定义题目最烦了…… B 因为没有说是联通图，所以是错的（坑点）。 C 显然是错的，二分图的定义是“顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。” D 也是错的，前面半句是对的，错就错在“反之亦然”，这个事实的逆命题显然是不成立的。
补充一下相关概念：

哈密顿图（Hamiltonian path 或 Traceable path）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径。

数据结构

若已知一个栈的入栈顺序 $1,2,3,\dots,n$ ，其输出序列为 $P_1,P_2,P_3,\dots,P_n$ （它是输入序列的一个排序），则在输出序列中可能出现的情况是（） A、 $Pj<Pk<Pi$ ，其中 $i<j<k$ B、 $Pk<Pj<Pi$ ，其中 $i<j<k$ C、 $Pj<Pi<Pk$ ，其中 $i<j<k$ D、 $Pi<Pk<Pj$ ，其中 $i<j<k$

答案：BCD
解析：直接搞个序列 1,2,3，所有情况都试试就可以了。

设有一个含有 13 个元素的 Hash 表（0-12），Hash函数是：H(key)=key%13，其中%是求余数运算。用二次探查法解决冲突，则对于序列 (8,31,20,33,18,53,27)，则下列说法正确的是（） A、18 在 4 号格子中 B、33 在 6 号格子中 C、31 在 5 号格子中 D、20 在 7 号格子中

答案：ABCD
解析：什么叫“二次探查法”呢？这里要补充一下哈希冲突以及各种处理方法：

哈希冲突/哈希碰撞 不同的 Key 值经过哈希函数 Hash(Key) 处理以后可能产生相同的值哈希地址，我们称这种情况为哈希冲突。任意的散列函数都不能避免产生冲突。

处理哈希碰撞的方法 若 key1,key2,key3 产生哈希冲突 (key1,key2,key3 值不相同，映射的哈希地址同为 key)，用以下方法确定它们的地址：

线性探测 若当前 key 与原来 key 产生相同的哈希地址，则当前 key 存在该地址之后没有存任何元素的地址中： key1：hash(key)+0 key2：hash(key)+1 key3：hash(key)+2

二次探测 若当前 key 与原来 key 产生相同的哈希地址，则当前 key 存在该地址后偏移量为（1,2,3...）的二次方地址处： key1：hash(key)+0 key2：hash(key)+1^2 key3：hash(key)+2^2 [4]

计算机常识系列

你确定这是常识？？？

下列哪些属于内存储器？ A、硬盘 B、RAM C、ROM D、Cache

答案：BCD

按通信距离划分，计算机网络可以分为局域网和广域网。下列网络中属于局域网的是（）。 A、Internet B、CERNET C、Novell D、以太网

答案：CD

如果互连的局域网高层分别采用 TCP/IP 协议与 SPX/IPX 协议，那么我们可以选择的互连设备应该是（） A、中继器 B、网桥 C、网卡 D、路由器

答案：D

在微机系统中，最基本的输入输出模块BIOS存放在（）中。
A、RAM B、ROM C、硬盘 D、寄存器

答案：B

下列地址中，属于 B 类 IP 地址的是（） A、27.33.119.2 B、192.97.32.121 C、133.201.189.32 D、126.33.82.107

答案：C

这种概念题真是完全不知道……

A 类：1.0.0.0 到 126.0.0.0。 B 类：128.0.0.0 到 191.255.255.255。 C 类：192.0.0.0 到 223.255.255.255。设有一个含有13个元素的Hash表（0-12），Hash函数是：H(key)=key%13，其中%是求余数运算。用二次探查法解决冲突，则对于序列(8,31,20,33,18,53,27)，则下列说法正确的是（）。 A、18在4号格子中 B、33在6号格子中
C、31在5号格子中 D、20在7号格子中 D 类：D类IP地址第一个字节以“lll0”开始，它是一个专门保留的地址。它并不指向特定的网络，目前这一类地址被用在多点广播（Multicast）中。多点广播地址用来一次寻址一组计算机，它标识共享同一协议的一组计算机。 E 类：以“llll0”开始，为将来使用保留。[3]

下列关于高级语言的说法正确的是（） A、Fortran 是历史上的第一个面向科学计算的高级语言 B、Pascal 和 C 都是编译执行的高级语言 C、Smalltalk 是历史上的第一个支持面向对象的语言 D、编译器将高级语言程序转变为目标代码

答案：ABD
解析：Smalltalk 是第二个，第一个是 Simula67……（完全没听说过）

数学题系列

由a,b,c三种不同的数字组成一个7位数，要求不出现两个a相邻，也不出现两个b相邻，这样的7位数的个数为（）。

答案：577
解析：这题是人工模拟 DP……（直接排列组合似乎很难算出来） F[i][j] 表示进行到第 i 位、最后一位数字为 j 的方案数。随便推一下就好了。

Kathy 函数是这样定义的：
$f(1)=1$ $f(3)=3$ $f(2n)=f(n)$ $f(4n+1)=2f(2n+1)-f(n)$ $f(4n+3)=3f(2n+1)-2f(n)$ 对于一个给定的数 $m=55$ ，求出所有满足 $f(n)=n,(n<=m)$ 的自然数 $n$ 的个数

答案：13
解析：这题 BZOJ 上有原题！！！总之是规律非常难找，当时做这题的时候~~大多数人都是手模了 55 个~~ 据说正规解法是，把 n 转换为二进制，会发现 $f(n)=n$ 时 n 的二进制是个回文数……这个谁发现得了啊……吐血

特别变态系列

遇到这样的题目……自求多福吧……

下列形状的三角形中，字母 a-i 分别表示数字 1,2,3,…,9。
       a
     b   c
   d       e
 f   g   h   i
字母 a-i 同时满足下列条件：
(1) $a<f<i$ (2) $b<d,g<h,c<e$ (3) $a+b+d+f=f+g+h+i=i+e+c+a=19$

则满足条件的三角形个数为（） A、2 B、3 C、4 D、5

答案：C

除了暴枚，没有什么好方法了。

奇葩题目系列

合唱演出在即，一名团员病倒了，不能参加。指挥排了一下队伍，如果10人一排，有一排少一人，如果12人一排，有一排还是少一人，如果15人一排，有一排仍少一人。请问这个未上百人的合唱团共有多少人？ A、59 B、60 C、61 D、62

答案：C
解析：非常变态，本来算出来是 59 人，但是要加上一个病号和指挥！！！

看程序写输出/完善程序部分

这部分比前面要简单一点了。

#include<iostream>   
using namespace std;
int a[10000];
int gcd(int m,int n){
 while(n){
 	int r=m%n;m=n;n=r;
 }
 return m;
}
int main(){
	int n=1000,r=202;
	for(int i=1;i<=n-r;i++) a[i]=n-i+1;
	for(int i=2;i<=r;i++){
		int k=i;
		for(int j=1;j<=n-r;j++)
		if(gcd(k,a[j])>1){
			int g=gcd(k,a[j]);
			k/=g; a[j]/=g;
			if(k==1) break;
		}
}
int p=1,g=0;
	for(int i=1;i<=n-r;i++){
		p*=a[i];
		while(p%5==0){
			p/=5; g++;
		}
		p%=5;
	}
	cout<<g<<endl;
	return 0;
}

输出：151
解析：手模后可以发现其实这是求较大排列数末尾 0 个数……

9/25/2018