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

选择/问题求解部分

算法/数据结构系列

排序与复杂度

CCF 可喜欢了 🌚

在各种查找算法中，平均查找长度（与关键字比较次数的期望值）与查找表中元素个数n无关的查找方法是
A、顺序查找
B、散列查找
C、折半查找
D、动态查找
选择合适的散列函数 $h(key)$，散列法的查找效率期望是 $\Theta(1)$。它几乎与关键字的空间大小无关，也适合于关键字直接比较计算量大的问题。[[1]][link1]
在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（）。
A、堆排序
B、希尔排序
C、冒泡排序
D、快速排序
快速排序是把数列按一个枢纽值分成两部分分别排序，所以效率高。但是若原数据为有序，并且选择的枢纽值为第一个数时，那在分块时会将一个第一个数前面的数（也就是没有）分为一块，将除第一个数的所有数分成了另一块。这样一来，每一次分块都只减少了一个值，而每次分块的时间为O（N），所以总时间为O（N^2）。[[2]][link2]
在待排序的数据表已经为有序时，下列排序算法中时间复杂度会减少的是（）
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$
下列关于图的说法正确的是：
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<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$
设有一个含有 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]][link4]

计算机常识系列

你确定这是常识？？？

下列哪些属于内存储器？
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]][link3]
下列关于高级语言的说法正确的是（）
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<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

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

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

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