2017noip提高组初赛试卷

学了三个月感觉过浙江初赛没戏

T(N)=2T(N/2)+NlogN

T(1)=1

则该算法的时间复杂度为( )。

A.O(N) B.O(NlogN)

C.O(N log2N) D.O(N2)
老师讲了大半天这题我没听。。。
听说可以递推，得到通项，然后找到时间复杂度最大的一项就是答案

8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32 B. 35 C. 38 D. 41
C(3,6)+C(4,6)+C(5,6)+C(6,6)-4=38
三条边时有四种成环情况

9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。

A. 60 B. 84 C. 96 D.120
隔板 C(3,10)

10. 若f[0]=0, f[1]=1,f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。

A. 1/2 B. 2/3

C. (√5-1)/2 D. 19
[解法1]不定根得等比数列，写出通项求极限
[解法2]多带几个值看看=。=最快了

14.?小明要去南美洲旅游，一共乘坐三趟航班才能到达目的地，其中第1个航班准点的概率是0.9，第2个航班准点的概率为0.8，第3个航班准点的概率为0.9。如果存在第i个（i=1,2）航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败；除了这种情况，其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。
A. 0.5 B. 0.648 C. 0.72 D.0.74
emmm玄学算错
0.10.8+0.20.9=0.26

1. 以下排序算法在最坏情况下时间复杂度最优的有( )。

A. 冒泡排序O(n²) B. 快速排序O(n²)（退化成冒泡排序）

C. 归并排序O(nlogn) D. 堆排序O(nlogn)

3. 下列算法中，( )是稳定的排序算法。

A. 快速排序 B.堆排序

C.希尔排序 D. 插入排序

• sort O(nlogn)
• https://baike.baidu.com/item/排序算法/5399605?fr=aladdin#3_1
  

三、问题求解

2.如图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是___________ (2分)，最小代价的不同方案数是__________(3分)。（只要有一条删除的边不同，就是不同的方案）

=。=除了模拟想不到别的方法，，，然后不出意外的少了一条，，，还是要多试几次啊 千万别漏解

四、阅读程序写结果

2.17 24 1 8 15幻方

4.1 3 2017 1 1 321
求出输入的两个数的最小公倍数
然后用最小公倍数分别除以两个输入的数

• 把两个数都转化为质数
• 相乘（？）
• =最小公倍数

五、完善程序

degree记录的是入度 我这个智商是怎么进队的
后面心态炸裂加上已经下课emmmm全猜，只有13分