第一次参加提高组这个级别的考试，感觉好难呀，看着这些数学式直接懵了。。。好吧，哪里难了？每年都是这样，不要乱说，要从自己身上找原因，都这么久了，有没有认真学习。。。

下面是本次考试的真题及解析：

单项选择题

1.在linux 系统终端中，以下哪个命令用于创建一个新的目录?
A. newdir
B.mkd:
C.creat
D.mkfold
【答案:】B
【解析】 linux 中创建目录命令是“mkdir”。 mkdir 命令是 make directories 的缩写

2. 0，1,2,3，4中选取 4个数字，能组成 ( )个不同四位数。(注: 最小的四位数是 1000，最大的四位数是 9999)
A.96
B.18
C.120
D.84
【答案】A
【解析】最高位 4种选择，后面的百位、十位、个位分别是 4、3、2 种，因此: 4*4*3*2=96

3.假设 n 是图的顶点的个数，m 是图的边的个数，为求解某一问题有下面四种不同时间复杂度的算法。对于 m=O(n)的稀疏图而言，下面的四个选项，哪一项的渐进时间复杂度最小 ()
A. O(m√logn * loglogn)
B.O(n²+m)
C.O(n²/logm+mlogn)
D.O(m+nlogn)
【答案】A
【解析】 渐进时间复杂度就是当 n 趋于无穷大的时候，f(n)得到的极限值; m=O(n)指当 n 趋于无穷大的时候，m 趋近于 n。显然排除 B，C，而O(loglogn) < O(√logn), O(m√logn loglogn) = O(n√logn loglogn) < O(n√logn√logn) = 0(nlogn + m) ,故 选择 A。

4.假设有n根柱子，需要按照以下规则依次放置编号为 1.2.3，的圆柱:每根柱子的底部固定，顶部可以放入圆环:每次从柱子顶部放入圆环时，需要保证任何两个相邻圆环的编号之和是一个完全平方数。请计算当有 4个根柱子时，最多可以放置 ( ) 个圆环
A.7
B.9
C.11
D.5
【答案】C
解析: 假设四根柱子分别为a、b、c、d，放置的顺序和编号为a1、b2、c3、d4、d5、c6、b7.a8、b9、c10、d11，最多可以放置 11 个圆环

5.以下对数据结构表述不恰当的一项是()
A.队列是一种先进先出(FIFO)的线性结构
B.哈夫曼树的构造过程主要是为了实现图的深度优先搜索
C.散列表是一种通过散列函数将关键字映射到存储位置的数据结构
D.二叉树是一种每个结点最多有两个子结点的树结构
【答案】B
【解析】可参考哈夫曼树的定义

6.以下连通无向图中，() 一定可以用不超过两种颜色进行染色
A.完全三叉树
B.平面图
C.边双连通图
D.欧拉图
【答案】 A
【解析】完全三叉树可以用 2 种颜色进行染色，其他数据结构不一定会少于 2 种

7.最长公共子序列长度常常用来衡量两个序列的相似度。其定义如下，给定两个序列X={x1,x2,x3,..xm)和 Y=y1,y2,y3,…yn]，最长公共子序列 (LCS) 问题的目标是找到一个最长的新序列Z=fz1,z2.z3…zk，使得序列Z 既是序列X的子序列，又是序列Y的子序列，且序列Z的长度k在满足上述条件的序列里是最大的。(注: 序列A是序列 B 的子序列，当且仅当再保持序列 B 元素顺席的情况下，从序列B中删除若干个元素，可以使得剩余的元素构成序列 A.)则序列“ABCAAAABA和“ABABCBABA”的最长公共子序列长度为() 。
A.4
B.5
C.6
D.7
【答案】C
【解析】 分析一下2个字符串
ABCAAAABA
ABABCBABA
发现前 2 个和后 3 个是一样的，中间有 1 个公共子序列，因此答案是 C

8.一位玩家正在玩一个特殊的掷骰子的游戏，游戏要求连续掷两次骰子，收益规则如下: 玩家第一次掷出x点，得到 2x 元;第二次掷出y点，当y=x 时玩家会失去之前的得到 2x 元。而当y 时玩家能保住第一次获得的 2x元上述x,yE[1，2，3，4，5，6。例如:玩家第一次掷出3点得到6元后，但第二次再次掷出3点会失去之前得到的6元，玩家最终受益为 0元:如果玩家第一次掷出3 点，第二次掷出 4点，则最终受益是6元。假设般子挑出任意一点的概率为1/6，玩家连续掷两次般子后，所有可能情形下收益的平均值是多少?
A.7元
B.35/6 元
C.16/3 元
D.19/3 元
【答案】 B
【解析】共有 6*6=36种情况其中
(1) x=y: 6种，受益为 0
(2) xzy，x=1: 5种，受益为 2
(3) xzy，x=2: 5种，受益为4
(4) xzy,x=3: 5种，受益为 6
(5) xzy,x=4: 5种，受益为 8
(6) xzy，x=5: 5种，受益为 10
(7) xty，x=6: 5种，受益为 12
受益期望为: (6/36)*0+(5/36) * (2+4+6+8+10+12) =35/6

9.假设我们有以下的 c++代码
int a=5,b=3,c=4.bool res=a&blc^b&&alc
请问 res 的值是什么? (提示: 在 c++中，逻辑运算的优先级从高到低依次为: 逻辑非 ()，逻辑与 (&&)，逻辑或)位运算的优先级从高到低依次为: 位非 (~)，位与&)，位异或()，位或)。同时，双目位运算的优先级高于双目逻辑运算: 逻辑非和位非优先级相同，且高于所有双目运算符。
A、true
B、false
C、1
D、0
【答案】A
【解析】 根据优先级计算 3&5=1，后面跟着|运算，之后的计算可以不做，数据类型是 bool 类型答案选 A

10.假设快速排序算法的输入是一个长度为 n 的已排序数组，且该快速排序算法在分治过程总是选择第一个元素作为基准元素。以下哪个选项描述的是在这种情况下的快速排序行为?
A. 快速排序对于此类输入的表现最好，因为数组已经排序。
B. 快速排序对于此类输入的时间复杂度是 O(nlogn)。
C.快速排序对于此类输入的时间复杂度是 O(n²)
D.快速排序无法对此类数组进行排序，因为数组已经排序.
【答案】 C
【解析】 该数列是有序数列，是快速排序中遇到的最坏的情况，时间复杂度是 O(n)。因此选 C

11.以下哪个命令，能将一个名为”main .cpp”的 C++源文件，编译并生成一个名为”main”的可执行文件? ()
A.g++ -o main main.cpp
B.g++-o main.cpp main
C.g++ main -o main.cpp
D.g++ main.cpp -o main.cpp
【答案】 A
【解析】 g++的命令格式，选 A。

12.在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数量最少。一棵树可能有多个重心。请问下面哪种树一定只有一个
重心?( )
A.4个结点的树
B.6 个结点的树
C.7 个结点的树
D.8 个结点的树
【答案】C
【解析】 树的重心可以是 1到2个，奇数个结点，重心只有 1 个

13.如图是一张包含6个顶点的有向图，但顶点间不存在拓扑序。如果要删除其中一条边，使这 6 个顶点能进行拓扑排序，请问总共有多少条边可以作为候选的被删除边?

A.1
B.2
C.3
D.4
【答案】 C
【解析】 根据图发现，3 条边 (1-3,3-4.4-1) 构成1个回路，去掉任意1条即可，因
此有3条边可作为候选，选C。

14.若

定义

其中x_i E{0,1,…..,15}对于给定自然数n0、存在序列四n₁,n₂….n_m、其中对于1<=i<=m都有n_i=f(n_i-1),且n_m = n_m-1，称为n_m为n₀关于f的不动点。问在100₁₆至1A0₁₆中，关于f的不动点为 9 的自然数个数为()
A、10
B、11
C、12
D、13
【答案】B
【解析】f的作用是求某 16 进制数的各位数字之和，如果不动点为9，那么该数字有两种情况:(1)各位数字之和为 9,这种情况有108/117/126/135/144/153/162/171/180共9个数字，(2) 各位数字之和为 24- (18)₁₆，所以f (24) =9，这种情况有18F和19E共2个数字。总共 11 个数字。

15、现在用如下代码来计算下 2”，其时间复杂度为 ( )

double quick_power(double x,unsigned n)
    if(n == 0) return 1;
    if(n == 1) return x;
    return quick_power(x,n/2)
        * quick_power(x,n/2)
        * ((n&1))?x:1)
}

A、 O(n)
B、O(1)
C、O(logn)
D、 O(nlogn)
【答案】A
【解析】根据代码，要处理数据规模是 n 的函数可以推出 T(n)-2T(n/2)，可以根据主定理，或者变量带入 n=2”求出时间复杂度是 O(n)。(主定理: a=2,b=2.f(n)=0)

阅读程序

(1)

#include <iostream>
using namespace std;

unsigned short f(unsigned short x){
    x^=x<<6.

    x^=x>>8.

    return x;
}

int main(){
    unsigned short x;
    cin>>x
    unsigned short y=f(x);
    cout << y << endl;
    return 0.
}

假设输入的x是不超过 65535 的自然数，完成下面的判断题和单选题
判断题
16.当输入非零时，输出一定不为零。()
【答案】 对
【解析】只有 X=0的时候，运算才可以是 0。

17.(2 分)将f函数的输入参数的类型政为 unsigned int，程序的输出不变。( )
【答案】 错
【解析】 unsignedint 是4个字节，unsigned shot 是 2个字节，会溢出

18.当输入为“65535”时，输出为“63”。( )
【答案】 对
【解析】 65535，二进制是 1111111111111111，位运算可以得出答案。

19.当输入为“1”时，输出为“64”。( )
【答案】 错
【解析】 1，二进制是 0000000000000001，位运算可以得出答案。

单选题
20.当输入为“512”时，输出为 ( )
A. “33280”
B. “33410”
C. “33106”
D. “33346”
【答案】 B
【解析】512的二进制是 1000000000，计算可得 B 选项

21.当输入为“64”时，执行完第 5行后x 的值为( )
A. “8256”
B. “4130”
C. “4128”
D. “4160”
【答案】D
【解析】64的二进制是 0000000001000000，计算可得 D 选项

(2)

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std,

long long solve1(int n){
    vector<bool> p(n+1,true);
    vector<long long> f(n+1,0),g(n+1,0)
    f[1]=1;
    for(int i=2;i*i<=n;i++){
        if(p[i]){
            vector<int>d;
            for(int k=i; k<=n;k*=1)  d.push_back(k);
            reverse(d.begin(),d.end())
            for(int k:D){
                for(int j=k;j<=n;j+=k){
                    if(p[j]){
                    p[j]=false;
                    f[j]=i;
                    g[j]=k;
                }
            }
        }
    }
    for(int i=sqrt(n)+1;i<=n;i++){
        if(p[i]){
            f[i]=i;
            g[i]=i;
        }
    }
    long long sum=1;
    for(int i=2;i<=n;i++){
        f[i]=f[i/g[i]] * (g[i]*f[i]-1)/(f[i]-1)
        sum+=f[i];
    }
    return sum;
}

long long solve2(int n){
    long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=i*(n/i);
    }
    return sum;
}

int main(){
    int n;
    cin>>n;
    cout<<solve1(n)<<endle;
    cout<<solve2(n)<<endle;
    return 0;
}

假设输入的 n 是不超过 1000000 的自然数，完成下面的判断题和单选题

判断题
22.将第 15 行删去，输出不变。( )
【答案】 错
【解析】 reverse(d.begin0,d.end0); 这条语句是翻转整个数组，删除 15 行之后排列
的数组是正序，输出内容就发生改变。

23.当输入为“10”时，输出的第一行大于第二行。( )
【答案】 错
【解析】 solve2()和 solve1()求的是接近 n²的值，输出的结果都是相同的

24. 当输入为“1000”时，输出的第一行与第二行相等。( )
【答案】 对
【解析】 solve2()和 solve1()输出结果相同。

单选题样。
25.solve1 (n)的时间复杂度为 ( )
A. O(nlog²n)
B. O(n)
C. O(n log n)
D. O(n log log n)
【答案】 D
【解析】主要看 for 循环嵌套的循环次数，和埃氏筛法相似，每次循环变量变化不一

26.solve2 (n) 的时间复杂度为 ( )
A. O(n²)
B. O(n)
C. O(n log n)
D. O(√n)
【答案】 B
【解析】观察函数，里面是一重循环，时间复杂度是 O(n)。

27.输入为“5”时，输出的第二行为 ()
A.”20″
B.”21″
C.”22″
D.”23″
【答案】B
【解析】带入代码计算可得。

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool f0(vector<int>&a,int m,int k){
    int s=0;
    for(int i=0,j=0;i<a.size();i++){
        while (a[i]-a[j]>m)j++;
        s+=i-j;
    }
    return s>=k;
}

int f(vector<int>&a,int k){
    sort(a.begin(),a.end())
    int g=0;
    int h=a.back()-a[0];
    while(g<h){
        int m=g+(h-g)/2;
        if(f0(a,m,k)){
            h=m;
        }else{
            g=m+1
        }
    }

    return g;
}

int main(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n,0);
    for(int i=0;n<=n;i++){
        cin>>a[i];
    }
    cout<<f(a,k)<<endl;
    return 0
}

判断题
28.将第 24行的“m”改为“m-1”，输出有可能不变，而剩下情况为少1。()
【答案】对
【解析】原来的代码，在左区间查找，挪动h=m，包含了中间值m的情况，如果改成 m-1，即中间-1，不包含中间值，那么在中间值不是我们要找的结果的时候，是正确的。所以题里面说输出有可能不变是正确的，剩下的情况，因为把中间值-1，不包含中间值的情况，因此题里面说剩下情况少 1，也是正确的。

29.将第22行的“g+(h-g)/2”改为“(h+g)>>1”，输出不变( )
【答案】 对
【解析】“g+(h-g)/2=g+h/2-g/2=(g+h)/2=(g+h)>>1

30.当输入为“572-451-3”，输出为“5”。()
【答案】对
【解析】本题二分求逆序对的数量，2-451-3 共计5个逆序对

单选题
31.设 a 数组中最大值减最小值加 1为 A，则f函数的时间复杂度为 ()
A. O(nlogA)
B. O(n²logA)
C. O(nlog(nA))
D. O(nlogn)
【答案】 C
【解析】f函数的 sot 排序是 nogn,二分时间复杂度是 logA,fo 函数是双指针算法
是0(n),时间复杂度是 nlogn+nlogA=O(nlog(An))

32.将第 10 行中的”>”替换为“>=”，那么原输出与现输出的大小关系为 ( )
A.一定小于
B.一定小于等于且不一定小于
C.一定大于等于且不一定大于
D.以上三种情况都不对
【答案】B
【解析】加上>=相同的数也统计，所以一定小于等于且不一定小于是正确的

33.当输入为”582-538-12”时，输出为 ()
A.”13” B.“14”C.“8” D. 15”
【答案】B
【解析】此题为二分求逆序对的数量，如: (2,-5)、(2,12) …，可以数出一共有14对

完善程序

(1)(第 k小路径)给定一张n个点 m 条边的有向无环图，顶点编号从0到n-1。对于一条路径，我们定义“路径序列”为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中，“路径序列”字典序第k 小的路径。保证存在至少k条路径。上述参数满足 1<=n,m<10⁵和1<k<10¹⁸
在程序中，我们求出从每个点出发的路径数量。超过10¹⁸的数都用10¹⁸表示。然后我们根据k的值和每个顶点的路径数量，确定路径的起点，然后可以类似地依次求出路径中的每个点。
试补全程序.

#include <jostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000
const long long LIM = 100000000000000000011:

int n, m, deglMAXN]
std::vector<int> E[MAXN];
long long k,flMAXN];

int next(std::vector<int> cand, long long &k) {
    std::sort(cand.begin(),cand.end0),
    for (int u : cand) {
        if (①) return u;
        k-=f[u];
    }
    return -1
}

int main(){
    std::cin>>n>>mk;
    for (int i=0; i<m;++i){
        int u,v;
        std::cin>>u>>v; //一条从u到v的边
        E[u].push_back(v);
        ++deg[v];
    }
    std::vector<int> Q;
    for (int i = 0;i<n;++i)
        if(!deg[i]) Q.push_back(i);
    for (int i=0; i < n;++i){
        int u = Q[i];
        for (int v:E[u]){
            if(②) Q.push_back(v);
            --deg[v];
        }
    }
    std::reverse(Q.begin(),Q.end());
    for (int u:Q) {
        f[u] = 1;
        for(int v:E[u])f[u] = ③;
    }
    int u = next(Q,k);
    std::cout<<u<<std::endl;
    while(④){
        ⑤;
        u = next(E[u].k);
        std::cout<<u<<std::endl;
    }
    return 0;
}

34.①处应填()
A. k >= f[u]
B. k <= f[u] C. k > f[u]
D. k < f[u] 【答案】B
【解析】f[u]]记录的是从u开始向后可以走的路径数量，当f[u]>=k 时，说明要走第k
大的路下一步需要走u，故选 B。同时若 f[u]

35.②处应填()
A. deg[v] == 1
B. deg[v] == 0
C. deg[v] > 1
D. deg[v] > 0
【答案】A
【解析】求图的拓扑序，当点度数为 0 时将该点放入队列，因为在–deg[v]之前操作
需要判断 deg[v] == 1，故选 A。

36.③处应填()
A. std::min(f[u] + f[v],LIM)
B. std:min(f[u] + f[v] + 1, LIM)
C. std::min(f[u] * f[v], LIM)
D. std::min(f[u] * (f[v] + 1)， LIM)
【答案】 A
【解析】 求出拓扑序后 dp求f[u],f[u]=1+\sum_{v\in E[u]}f[v],故选A, 与LIM取 min
是为了保证不爆long long。

37.④处应填()
A. u!= -1
B. !E[u].empty()
C. k > 0
D. k> 1
【答案】 D
【解析】 结合38题，当k=1时，再–k后，k=0，此时已经找到了答案，因而不需要再继续循环找新的节点，故需要再 k=1 时退出循环，即 while(k>1),选 D。

38.⑤处应填( )
A. k += f[u]
B. k -= f[u]
C. –k
D. ++k
【答案】C
【解析】每次走到一个新点，需要减去从初始节点走到该节点的方案，所以需要–k，选 C

(2)(最大值之和)给定整数序列a₀…,a_n-1，求该序列所有**非空连续子序列**的最大值之和。上述参数满足 1 < n < 10⁵和1 <= a_i <= 10⁸。
一个序列的非空连续子席列可以用两个下标l和r(其中 0<=l<=r<n)表示,对应的序列为 al,al+1…, ar。两个非空连续子序列不同，当且仅当下标不同。
例如，当原序列为[1,2,1,2] 时，要计算子序列 [1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1].[2,1,2]、[1,2,1,2] 的最大值之和，答案为 18。注意[1,1]和[2,2]虽然是原序列的子序列，但不是连续子席列，所以不应该被计算。另外，注意其中有一些值相同的子序列，但由于他们在原序列中的下标不同，属于不同的非空连续子席列，所以会被分别计算。解决该问题有许多算法，以下程序使用分治算法，时间复杂度 O(nlogn)。试补全程序。

#include <iostream>
#include <algorithm>
#include <vector>

const int MAXN = 100000:
int n;
int a[MAXN];
long long ans;

void solve(int l, int r) {
    if(l+1 == r){
        ans += a[l];
        return;
    }

    int mid = (l+r)>>1;
    std::vector<int> pre(a+mid,a+r);
    for (int i = i; I<r -mid;++i)①;
    std::vector<long long> sum(r - mid +1);
    for (int i=0;i<r - mid,++i) sum[i+1] = sum[i] + pre[i];
    for (int i = mid - 1,j = mid，max = 0； I>=l; --i) {
        while (j < r && ②) ++j;
        max = std::max(max,a[i]);
        ans += ③;
        ans += ④;
    }
    solve(l,mid);
    solve(mid,r);
}

int main(){
    std::cin >> n;
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    ⑤;
    std::cout << ans << std::endl;
    return 0; 
}

39.①处应填())
A. pre[i] = std::max(pre[i – 1], a[i – 1])
B. pre[i + 1] = std::max(pre[i], pre[i + 1])
C. pre[i] = std::max(pre[i – 1], a[i])
D. pre[i] = std::max(pre[i], pre[i – 1])
【答案】 D
【解析】 pre 数组求出[mid,r)中的前缀 max，sum 数组求出[mid,r)中的前缀 max 和，故选择 D

40.②处应填()
A. a[j] < max B. a[j] < a[i] C. pre[j - mid] < max D. pre[j - mid] > max
【答案】 C
【解析】 对于固定的左端点i, 求解右端点在[mid,r)的所有答案，可以发现区间[mid,r)中的点被分为左右两份，对于左半部分[mid,j)，$\forall x\in[mid,j],\max\a_i,a{i+1},…,a_x\
}=max$,其中max就是题中维护的max，由于右侧部分 [j,r), $\forall x\in[j,r),\max\{a_i,a_{i+1},…,a_x\}=max\{a_{mid},a_{mid+1},…,a_x\} = pre_x$,而两部分的边界j，就是第一个满足 pre[j-mid] >= max 的j,即 while (j < r &&pre[j-mid] < max )，因而选择 C

41.③处应填()
A. (long long)(j – mid) * max
B. (long long)(j – mid) * (i – l)* max
C. sum[j – mid]
D. sum[j – mid] * (i – l)
【答案】A
【解析】该部分在统计 40 题的解析提到的左半部分[mid，j)的贡献，由定义可知，左端点为i.右端点在[mid,i)中时，区间的最大值即为统计的 max，故这些区间的总贡献为(r-j)*max，选A。

42.④处应填()
A. (long long)(r – j)* max
B. (long long)(r – j)* (mid – i) * max
C. sum[r – mid] – sumlj – mid]
D. (sum[r – mid] – sum[j – mid]) * (mid – i)
【答案】 C
【解析】 该部分在统计 40 题的解析提到的右半部分)的贡献，由定义可知，左端点为 i右端点在[i,r)中时，区间的最大值即为max{a_mid,a_mid+1,…,a_x}=pre_x,故这些区间的总贡献为

43.⑤处应填()
A. solve(0,n)
B. solve(0, n – 1)
C. solve(1,)
D. solve(1, n – 1)
【答案】A
【解析】根据 solve 中的实现和边界条件 if(l+ 1== r)，可以发现 solve(l,r)在统计区间[l,r)中的答案，故应为 solve(0,n)，选择 A。