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

/ 0评 /

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

选择/问题求解部分

算法/数据结构系列

排序与复杂度

CCF 可喜欢了 :new_moon_with_face:


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

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


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

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


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

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

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

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

是否稳定看排序后原来相等两数是否会交换位置,因此,如果不是相邻两数比较交换的往往是不稳定。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}


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


下列逻辑运算正确的是()
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)


无向图 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

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


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


数据结构


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


设有一个含有 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 号格子中

哈希冲突/哈希碰撞
不同的 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


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


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


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


下列地址中,属于 B 类 IP 地址的是()
A、27.33.119.2
B、192.97.32.121
C、133.201.189.32
D、126.33.82.107

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

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、编译器将高级语言程序转变为目标代码


数学题系列


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


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 的个数


特别变态系列

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

下列形状的三角形中,字母 a-i 分别表示数字 1,2,3,…,9。

       a
     b   c
   d       e
 f   g   h   i

字母 a-i 同时满足下列条件:
(1) a
(2) b
(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


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

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


#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;
}


知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/noip-precontest/


发表评论

电子邮件地址不会被公开。 必填项已用*标注