第 1 题 如果下面代码输入整数为10，输出是1，则横线处填写？（ ）

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main ( ) {
    int x;
    cin >>x;
    cout << _______ <<endl;
    return 0 ;
}

第 2 题 下面定义的函数用来求斐波那契数列的F(n)，其中 ，描述正确的是（ ）。

int fab (int n)
{    
    int f[n+1];
    
    f[0]=0, f[1]=1;
    
    for (int i=2; i<=n; i++)
        f[i]= f[i-1] + f[i-2];
        
    return f[n] ;
}

第 3 题 下列关于C++语言中函数的叙述，正确的是（ ）。

第 4 题 4个结点的简单有向图，最多可以有多少条边（ ）。

第 5 题 哈希表上可以执行的操作不包括（ ）

第 6 题 将关键码集合 {100，300，500，700，800，900}逐一保存在一个长度为100的哈希表中，选取哈希函数为 Hash(key)=key/100，则800保存在表中的位置应该是（ ）。

第 7 题 定义double型常量pi=3.14和变量x，x代表等边三角形边长，则该三角形的面积是（ ）。

第 8 题 动态规划将一个问题分解为一系列子问题后来求解。下面关于子问题的描述正确的是（ ）。

第 9 题 阅读以下代码，visited起到的作用是（ ）。

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int visited [100],k=0 ;

void dfs(int graph [] [100],int start, int vexnum)
{
    visited [ start]=++k;
    cout << start <<" ";
    for (int i=0; i<vexnum; i++) {
        if ( (start!=i) && !visited[i]) {
            dfs(graph, i, vexnum) ;
        }
    }
}

第 10 题 下面函数尝试使用动态规划方法求出如下递推公式的函数，则横线处填写下列哪段代码可以完成预期功能?

int rec_C[MAXN][MAXM];
int C(int n, int m) {
    for(int i=0; i<=n; i++)
        rec_C[i][0] = 1;
    for(int j=0; j<=m; j++)
        rec_C[0][j] = 1;
    ____________// 在此处填入代码
    rec_C[i][j] = rec_C[i - 1][j - 1] + rec_C[i - 1][j];    
    return rec_C[n][m];
}

（ ） 当 或 当 且

第 11 题 深度为4的完全二叉树，结点总数最少有多少个？（ ）

第 12 题 下面有向图中的数字表示顶点序号，则从1号顶点出发的BFS遍历的输出顶点序列可能是（ ）。

第 13 题 一个简单有向图有20个结点，假设图中已经存在300条边，请问增加多少条边可以成为完全图。（ ）

第 14 题 在下面的有向图中，强连通分量有多少个？（ ）

第 15 题 下面有关格雷码的说法，错误的是（ ）。

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

第 1 题 定义变量double x=exp(-1)，则x<0为真。( )

第 2 题 假设x和y都是double型正数，如果说x比y大一个数量级，log(x/y)等于10。( )

第 3 题 如果double型变量x代表锐角对应的弧度角，则可以编程来确定sin(x)>cos(x)的近似区间。( )

第 4 题 pow(1,2)返回的结果是浮点数。( )

第 5 题 如果哈希表足够大，哈希函数确定后，不会产生冲突。( )

第 6 题 动态规划最终要推导出状态转移方程才能求解。( )

第 7 题 简单有向图的深搜结果和广搜结果一样。( )

第 8 题 判断图是否连通可以用深搜实现。( )

第 9 题 在C++中，可以使?二分法查找链表中的元素。( )

第 10 题 有些算法或数据结构在C/C++语言中使用指针实现，一个典型的例子就是链表。因此，链表这一数据结构在C/C++语言中只能使用指针来实现。( )

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

第 1 题 迷宫统计

题面描述

在神秘的幻想大陆中，存在着 $n$ 个古老而神奇的迷宫，迷宫编号从 $1$ 到 $n$。有的迷宫之间可以直接往返，有的可以走到别的迷宫，但是不能走回来。玩家小杨想挑战一下不同的迷宫，他决定从$m$ 号迷宫出发。现在，他需要你帮助 他统计：有多少迷宫可以直接到达 $m$ 号迷宫，$m$ 号迷宫可以直接到达其他的迷宫有多少，并求出他们的和。

需要注意的是，对于 $i$ ( $1 \le i \le n$ ) 号迷宫，它总可以直接到达自身。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示结点迷宫总数 $n$ ，指定出发迷宫的编号 $m$。

下面 $n$ 行，每行 $n$ 个整数，表示迷宫之间的关系。对于第 $i$ 行第 $j$ 列的整数，$1$ 表示能从 $i$ 号迷宫直接到达 $j$ 号迷宫，$0$ 表示不能直接到达。

输出格式

一行输出空格分隔的三个整数，分别表示迷宫 $m$ 可以直接到达其他的迷宫有多少个，有多少迷宫可以直接到达$m$ 号迷宫，这些迷宫的总和。

6 4
1 1 0 1 0 0
0 1 1 0 0 0
1 0 1 0 0 1
0 0 1 1 0 1
0 0 0 1 1 0
1 0 0 0 1 1

3 3 6

数据要求

【样例解释】

$4$ 号迷宫能直接到达的迷宫有 $3,4,6$ 号迷宫，共 $3$ 个。

能直接到达 号迷宫的迷宫有 $1,4,5$ 号迷宫，共 $3$ 个。总和为 $6$ 。

子任务编号 分值

1 30

2 30

3 40

对于全部数据，保证有 $4 \le n \le 1000$，$1 \le m \le n$ 。

第 2 题 最长不下降子序列

题面描述

小杨有一个包含 $n$ 个节点 $m$ 条边的有向无环图，其中节点的编号为 $1$ 到 $n$。

对于编号为 $i$ 的节点，其权值为 $A_i$ 。对于图中的一条路径，根据路径上的经过节点的先后顺序可以得到一个节点权值的序列，小杨想知道图中所有可能序列中最长不下降子序列的最大长度。

注：给定一个序列 $S$，其最长不下降子序列 $S'$ 是原序列中的如下子序列：整个子序列 单调不降，并且是序列中 最长的单调不降子序列。例如，给定序列 $S=[11,12,13,9,8,17,19]$，其最长不下降子序列为$S'=[11,12,13,17,19]$，长度为 $5$。

输入格式

第一行包含两个正整数 $n,m$，表示节点数和边数。第二行包含 $n$ 个正整数 $A_1,A_2,\cdots,A_n$，表示节点 $1$ 到 $n$ 的点权。之后 $m$ 行每行包含两个正整数 $u_i,v_i$，表示第 $i$ 条边连接节点 $u_i$ 和 $v_i$，方向为从 $u_i$ 到 $v_i$。

输出格式

输出一个正整数，表示该图中所有可能序列中最长不下降子序列的最大长度。

5 4
2 10 6 3 1
5 2
2 3
3 1
1 4

3

6 11
1 1 2 1 1 2
3 2
3 1
5 3
4 2
2 6
3 6
1 6
4 6
1 2
5 1
5 4

4

6 11
5 9 10 5 1 6
5 4
5 2
4 2
3 1
5 3
6 1
4 1
4 3
5 1
2 3
2 1

4

数据要求

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