SkyWT

我们的征途是星辰大海。

NOIP 初赛题目整理(C++)

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

选择/问题求解部分

算法/数据结构系列

排序与复杂度

CCF 可喜欢了 🌚


在各种查找算法中,平均查找长度(与关键字比较次数的期望值)与查找表中元素个数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)$。

关于冒泡排序,其步骤是:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

下列关于排序说法正确的是()。 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

  • 答案: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),用以下方法确定它们的地址:

  1. 线性探测
    若当前 key 与原来 key 产生相同的哈希地址,则当前 key 存在该地址之后没有存任何元素的地址中:
    key1:hash(key)+0
    key2:hash(key)+1
    key3:hash(key)+2
  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

则满足条件的三角形个数为()
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 个数……



Related posts

gdb 调试的使用
发表评论
撰写评论