第 1 题 从A城到C城需要经过B城，其中A到B可选高铁和飞机，B到C可以自驾或打的，请问A到C有几种交通选择（ ）。

第 2 题 下面程序输出的n的值是（ ）。

#include <iostream>
#include <string>
#include <cmath>

using namespace std;
int main() {
    int a,b,c,d, n=0;
	
    for(a=1; a<5; a++)
        for (b=1; b<5; b++)
            for(c=1; c<5; c++)
for (d=1; d<5; d++)
    if(a!=b && a!=c && a!=d && b!=c && b!=d && c!=d)
        if(a!=4) {
            cout << a*1000+b*100+c*10+d <<" ";
            n++;
        }
    cout<<endl<< n <<endl;
    return 0;
}

第 3 题 对$(a+b)^5$ ,想求出 $a^3b^2$ 的系数可以使用（ ）

第 4 题 对于 4 个结点的简单有向图，最少（ ）条边可以形成一条覆盖所有顶点的环。

第 5 题 对正整数 $a$ 和 $n$ （ $n$ 为 $2$ 的正整数次幂），下面求 值的方法是（ ）

int fan(int a, int n) {
    if(n==0) return 1 ;
    if(n==1) return a;
    long long s = fan(a, n/2) ;
    return s*s;
}

第 6 题 平面内，通过一点可以作( )条平行于给定直线的直线？

第 7 题 定义常量const double pi=3.14159。如果一个等边三角形的边长为4，下列（ ）表达式可以求其面积 。

第 8 题 下面程序使用BFS遍历一个有n个顶点、边权都为1的无向图G，下面说法正确的是（ ）。

#include <vector>
using namespace std;

#define N 2023

int n,m;
vector<int> G[N] ;
int q[N] ,hd,tl;
int dis[N] ;

void BFS(int st)
{
    hd=1,tl=0;
    for(int i=1; i<=n; i++) dis[i]=-1;
    q[++tl]=st,dis[st]=0;
    while (hd<=tl) {
        int u=q[hd++] ;
        for(int i=0; i<G[u].size(); i++) {
            int v=G[u][i];
            if(dis[v] !=-1) continue;
            dis[v]=dis[u]+1;
            q[++tl]=v;
        }
    }
}

第 9 题 下面的冒泡排序中尝试提前结束比较过程，横线处应该填写的代码是（ ）。

void BubbleSort(int R[], int n)
{
    int i,j, lastExchangeIndex;

    i=n;
    while (i>1) {
        lastExchangeIndex = 1;
        for(i=1; j<i; j++)
            if (R[j+1] < R[j]) {
int t;
t=R[j], R[j] = R[j+1], R[j+1] = t;
lastExchangeIndex = j ;
            } //if
        ______________;
    } // while
} // BubbleSort

第 10 题 对数列3、4、7、12、19、28、39求和，除简单累加外，还可以用下面（ ）来直接计算。

第 11 题 约定杨辉三角形第0行只有1个元素是1，第1行有2个元素都是1，第四行的所有元素之和是（ ）？

第 12 题 下列程序的输出是 ( ) 。

int main() {
    int sum =0, x;
    for(x=-10; x<=10; x++)
        if((3*x+5 >= -11) && (3*x+5 <= 11) )
            sum += x;
    cout << sum ;
    cout << endl ;
    return 0;
}

第 13 题 对于具有n个元素的二叉排序树（又名二分查找树）进行前序遍历，其时间复杂度是( )？

第 14 题 Dijkstra的算法在实现时一般可以选用（ ）来提高效率？

第 15 题 有关下列代码的说法正确的是（ ）。

#include <iostream>

class Node {
public:
    int Value;
    Node* Next;
    
    Node(int Val, Node* Nxt = nullptr) {
        Value = Val ;
        Next = Nxt;
    }
};

int main() {
    Node* firstNode = new Node (10) ;
    firstNode->Next = new Node (100) ;
        firstNode->Next->Next = new Node(111,  firstNode) ;
    return 0;
}

二、判断题（每题 2 分，共 20 分）

第 1 题 学校组织班际排球赛，每个班级可以派男女各一个参赛队伍，每队5人。班级A的每位同学都可以报名，那可以用加法原理来计算A班有多少支候选队伍。( )

第 2 题 若a,x,b都是double类型，则对方程a*x+b=0求解的程序中可以直接用x=-b/a来求解。( )

第 3 题 从15本不同的书中选3本，总共有455种方法。 ( )

第 4 题 连通图G有n个顶点m条边，须删除m-n+1条边后才能变成一棵生成树。( )

第 5 题 在C++语言中，所有int类型的值，经过若干次左移操作（<<）后，它们的值总会变为0。( )

第 6 题 如果一个四边形的对角线互相平分，并且两条对角线的长度都为8，那么这个四边形的面积一定是32。( )

第 7 题 最小生成树的权值是指生成树所有边的权值之和最小。( )

第 8 题 如果一个图中所有边的权重都为正数，则Floyd算法可以求出该图中任意两个顶点间的最短路径。 ( )

第 9 题 下面是图的深度遍历的代码，则横线处可以填入：if(vis[x]) return。（ ）

void dfs(int x) {
    __________;//补充代码
    vis[x]=1;
    cout<<x<<endl; //访问当前节点
    for(int i=vFirst[x]; i!=-1; i=e[i].next) { // 遍历每-一个相邻的顶点
        dfs(e[i].v);
    }
}

第 10 题 下图中A到E的Dijkstra单源最短路可以在第2次探索中找到。（ )

三、编程题（每题 25 分，共 50 分）

第 1 题 区间

题面描述

小杨有一个长度为 $n$ 的正整数序列 $A$。

小杨有 $q$ 次询问。第 $i$ 次（ $1 \le i \le q$ ）询问时，小杨会给出 $l_i,r_i,x_i$ ，请你求出 $x_i$ 在 $A_li,A_{l_i+1}, \cdots, A_ri $ 中出现的次数。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据：第一行包含一个正整数 $n$，表示序列 $A$ 的长度。第二行包含 $n$ 个正整数 $A_1,A_2,\cdots,,A_n$，表示序列。第三行包含一个正整数 $q$，表示询问次数。接下来 $q$ 行，每行三个正整数$l_i,r_i,x_i$ ，表示一组询问。

输出格式

对于每组数据，输出 $q$ 行。第 $i$ 行（$1 \le i \le q$ ）输出一个非负整数，表示第 $i$ 次询问的答案。

2
5
7 4 6 1 1
2
1 2 3
1 5 1
5
1 2 3 4 5
2
5 5 3
1 4 3

0
2
0
1

数据要求

对于全部数据，保证有 $1 \le T \le 5$，$1 \le n \le 10^5$ ，$1 \le q \le 10^5$ ，$1 \le A_i \le 10^5$ 。

第 2 题 小杨的旅游

题面描述

小杨准备前往 B 国旅游。

B 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。

小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 单位时间。

B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1,b_2,\cdots,b_k$。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。

注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。

小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游（ $1 \le i \le q$ ），小杨计划从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市，小杨希望你能求出所需要的最短时间。

输入格式

第一行包含三个正整数 $n,k,q$，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。

接下来 $n-1$ 行，每行包含两个正整数 $x_i,y_i$ ，表示一条双向道路连接的两座城市的编号。

第 $n+1$ 行包含 $k$ 个正整数 $b_1,b_2,\cdots,b_n$ ，表示设有传送门的城市的编号。

接下来 $q$ 行，每行包含两个正整数 $u_i,v_i$，表示小杨第 $i$ 次旅游行程的起点城市编号与终点城市编号。

输出格式

输出共 $q$ 行。第 $i$ 行（ $1 \le i \le q$ ）输出一个非负整数，表示小杨计划第 $i$ 次旅游从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市所需要的最短时间。

7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7

4

5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3

2
1
4

数据要求

对于全部数据，保证有 $1\le k \le n \le 2 \times 10^5$ ，$1 \le q \le 2 \times 10^5$ ，$1 \le x_i,y_i \le n$ ，$1 \le u_i,v_i \le n$ 。

对于所有 $1 \le i \le n-1$，有 $x_i \not= y_i$。