⼩杨想点一杯奶茶外卖 ，但还差5元起送 。于是 ，⼩杨决定点一些⼩料 。可选的⼩料包括：珍珠1元、 椰果2 元、 奶冻3元、 奶盖4元 。每种⼩料最多点1份 。请问共有多少种满⾜起送条件的点⼩料⽅案？（  ）。

⼩杨和⼩刘是好朋友 ，她们在逛商场时发现新设置的⼤头贴⾃拍机 ，于是决定一起拍一组照⽚ 。一组照⽚包 括4张 ，这4张照⽚没有顺序区分 。拍每张照⽚时 ，可以选择有相框或⽆相框、 两⼈可以分别选择有头饰或⽆头饰、还可以从2种位置（⼩杨在左 ，或⼩刘在左） 中选出一种 。她们不希望一组照⽚中出现完全相同的相框、 头饰、 位置 的组合 。请问一组照⽚共有多少种不同的⽅案？（  ）。

下列关于C++类的说法 ，错误的是（  ）。

下列关于树和图的说法 ，错误的是（  ）。

一对夫妻⽣男⽣⼥的概率相同 。这对夫妻希望⼉⼥双全 。请问这对夫妻⽣下三个孩⼦时 ，实现⼉⼥双全的概率是多少？（  ）。

⼆项式(x + y) ⁶ 的展开式中x²y⁴项的系数是（  ）。

对一个包含V个顶点、E条边的图 ，执⾏⼴度优先搜索 ，其最优时间复杂度是（  ）。

以下关于贪⼼法和动态规划的说法中 ，错误的是（  ）。

下⾯C++程序的输出为（  ）。

#include  <iostream>   
using  namespace  std ; 
int  main()  {
    int  N  =  15 ,  cnt  =  0 ;
    for  (int  x  =  1;  x  +  x  +  x  <=  N ;  x++)
        for  (int  y  =  x;  x  +  y  +  y  <=  N ;  y++)
            for  (int  z  =  y;  x  +  y  +  z  <=  N ;  z++)
                cnt++;
    cout  <<  cnt  <<  endl;
    return  0 ; 
}

下⾯C++程序的时间复杂度为（  ）。

int  primes [MAXP] ,  num  =  0 ;
bool  isPrime [MAXN]  =  {false} ; 
void  sieve()  {
    for  (int  n  =  2;  n  <=  MAXN ;  n++)  {
        if  ( !isPrime [n ])
            primes [num++]  =  n ;
        for  (int  i  =  0 ;  i  <  num  &&  n  *  primes [i ]  <=  MAXN ;  i++)  { 
            isPrime [n  *  primes [i ]]  =  true ;
            if  (n  %  primes [i ]  ==  0 )
                break;
        }
    }
}

下列Dijkstra算法 ，假设图graph 中顶点数 v、 边数 e ，则程序的时间复杂度为（  ）。

下⾯ count_triple 函数的时间复杂度为(  )。

int  gcd(int  m ,  int  n )  {
    if  (m  ==  0 ) return  n ;
    return  gcd(n  %  m ,  m ) ; 
}
int  count_triple(int  n )  {
    int  cnt  =  0 ;
    for  (int  v  =  1;  v  *  v  *  4  <=  n ;  v++)
        for  (int  u  =  v  +  1;  u  *  (u  +  v )  *  2  <=  n ;  u  +=  2 ) 
            if  (gcd(u ,  v )  ==  1 )  {
                int  a  =  u  *  u  -  v  *  v;
                int  b  =  u  *  v  *  2;
                int  c  =  u  *  u  +  v  *  v;
                cnt  +=  n  /  (a  +  b  +  c ) ; 
            }
    return  cnt ; 
}

下⾯ merge_sort 函数试图实现归并排序算法 ，横线处应该填⼊的是（  ）。

下面Prim算法程序中，横线处应该填入的是（ ）。

下面的C++程序使用出边邻接表表达的带权无向图，则从顶点0到顶点3的最短距离为（ ）。

C++语⾔中 ，表达式 '9 '  ^  3 的结果值为 '999 ' 。

下列C++语⾔代码 ，能够安全地输出 arr [5 ] 的值。

int  n  =  5 ;
int  arr [n ]  =  {1 ,  2 ,  3} ;
std : :cout  <<  arr [5 ] ;

对n个元素的数组进⾏排序 ，最差情况的时间复杂度为O(n²) 。

有4个红球、 3个蓝球和2个绿球排成一排（相同⾊球视为完全相同） ，则不同的排列⽅案数为1260种。

运算符重载是C++语⾔静态多态的一种典型体现 ，⽽使⽤C语⾔则⽆法实现运算符重载。

存在一个简单⽆向图满⾜：顶点数为6 ，边数为8 ，6个顶点的度数分别为3 、 3 、 3 、 3 、2 、2。

已知两个 double 类型的变量 r 和 theta 分别表⽰一个扇形的圆半径及圆⼼角（弧度） ，则扇形的周长可 以通过表达式 (2  +  theta)  *  r 求得。

Dijkstra算法的时间复杂度为o(v²) ，其中 V 为图中顶点的数量。

从32名学⽣中选出2⼈分别担任男⽣班长和⼥⽣班长（男⽣班长必须是男⽣ ，⼥⽣班长必须是⼥⽣） ，则共 有 C(32, 2)/2 种不同的选法。

试题名称：最短距离

时间限制： 1.0 s

内存限制：512.0 MB

3.1.1     题目描述

给定正整数p, q 以及常数N = 10⁸ 。现在构建一张包含 N 个结点的带权⽆向图 ，结点依次以 1 , 2, .... , N 编号 。对于 任意满⾜ 1 ≤ u < v ≤ N 的 u, v ， 向图中加⼊一条连接结点 u 与结点 v 的⽆向边 ，边权取决于 u, v 是否互质：

  若 u, v 互质（即 u, v 的最⼤公因数为 1） ，则连接结点 u 与结点 v 的⽆向边长度为 p；

  否则连接结点 u 与结点 v 的⽆向边长度为 q。

现在给定 n 组询问 ，第 i（ 1 ≤ i ≤ n） 组询问给定两个正整数a_i , b_i ，你需要回答结点 a_i 与结点 b_i 之间的最短距离。

3.1.2     输入格式

第一⾏ ，三个正整数 n, p, q ，分别表⽰询问数量 ，结点编号互质时的边权 ，以及结点编号不互质时的边权。

接下来 n ⾏ ，每⾏两个正整数 a_i , b_i ，表⽰一组询问。

3.1.3     输出格式

输出共 n ⾏ ，每⾏一个整数 ，表⽰结点 a_i 与结点 b_i 之间的最短距离。

3.1.4     样例

3.1.4.1     输入样例 1

4 4 3

1 2

2 3

4 2

3 5

3.1.4.2     输出样例 1

4

4

3

4

3.1.4.3     输入样例 2

6 5  2  6

1  2

2  3

4  2

3  5

6  6

3.1.4.4 输出样例 2

2

2

4

2

0

3.1.5     数据范围

对于 30% 的测试点 ，保证 1  ≤ n ≤ 10 ， 1≤ a_i , b_i ≤ 50。

对于另外 30% 的测试点 ，保证 1 ≤ a_i , b_i  ≤ 250。

对于所有测试点 ，保证 1 ≤ n ≤ 104 ，1  ≤ a_i , b_i  ≤ 10⁹ ，1 ≤ p, q ≤ 10⁹ 。

试题名称：最⼩⽣成树

时间限制： 1.0 s

内存限制：512.0 MB

3.2.1     题目描述

给定一张包含 n 个结点 m 条边的带权连通⽆向图 ，结点依次以1 , 2,  ....., n 编号  ，第 i 条边（ 1 ≤ i ≤ m）连接结点 u_i与结点 v_i ，边权为 w_i 。

对于每条边 ，请你求出从图中移除该条边后 ，图的最⼩⽣成树中所有边的边权和 。特别地 ，若移除某条边后图的最⼩⽣成树不存在 ，则输出1 。

3.2.2     输入格式

第一⾏ ，两个正整数 n, m ，分别表⽰图的结点数与边数。

接下来 m ⾏中的第 i ⾏（ 1 ≤ i ≤ m） 包含三个正整数 u_i , v_i,wi ，表⽰图中连接结点 u_i 与结点 v_i 的边 ，边权为 w_i 。

3.2.3     输出格式

输出共 m ⾏ ，第 i ⾏（ 1 ≤ i ≤ m）包含一个整数 ，表⽰移除第 i 条边后 ，图的最⼩⽣成树中所有边的边权和 。若移 除第 i 条边后图的最⼩⽣成树不存在 ，则输出   1 。

3.2.4     样例

3.2.4.1     输入样例 1

5  5

1  2  4

2  3  3

3  4  1

2  5  2

3  1  8

3.2.4.2     输出样例 1

14

15

-1

-1

10

3.2.4.3     输入样例 2

6  10

1  2  6

2  3  3

3  1  4

3  4  5

4  5  8

5  6  2

6  4  1

3  2  4

5  4  4

3  3  6

3.2.4.4     输出样例 2

15

16

17

-1

15

17

18

15

15

15

3.2.5     数据范围