NOIp2015 tg初赛

单项选择题

1.A 学过计算机的都应该知道 计算机是由二进制…

2.A 只有A是对的,B存储Ram在断电后丢失,分辨率不是由尺寸决定 是可以手动调的 .D可以用网卡啊 宽带
Internet上网的几种常用连接方式：1、拨号上网2、ISDN 3、宽带上网 4.无线上网
3.A (0.1)2=(0.5)10=(0.8)16

4.D 手动计算即可

5.D 数组需要连续 链表连不连续都行

6.B 模拟

7.B 很明显是B 具体的例子 我将在课程中提到 前序遍历：根左右，后序遍历：左右根，然后画个图试试就知道了

8.B 画图 1+2+4+8+16+32>61<1+2+4+8+16

9.B 6-1=5

10.D
T(n)=T(n-1)+n

=T(n-2)+n-1+n

……

=T(0)+1+2+3+……+n

=1+n*(n+1)/2

所以是O（n^2)
11.D
邻接矩阵 邻接表 详情请看y总的算法基础课
遍历算法中，时间复杂度主要取决于搜索邻接点的个数；

邻接矩阵存储时，对于n个顶点每个顶点要遍历n次，显然是O(n^2)的

邻接表存储时，有n个头结点和e个表结点，所有节点遍历一遍，所以是D
12.A
合并果儿!!

13.D 模拟

14.A 画下图 1\2\3

15.A 带鼠标是不可以的o!

不定项选择题

1.ABCD

常用的操作系统：UNIX、Linux、Mac OS X、Windows、iOS、Android、WP、Chrome OS等

操作系统的五大类型是：批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统。

2.ABC

常见的视频格式：视频文件格式有不同的分类，如：

微软视频 ：wmv、asf、asx

Real Player ：rm、 rmvb

MPEG视频 ：mpg、mpeg、mpe

手机视频 ：3gp

Apple视频 ：mov

Sony视频 ：mp4、m4v

其他常见视频：avi、dat、mkv、flv、vob

——来自百度百科

3.ACD IP地址的范围0~225 2014考过了!

4.AB
A显然对，B的话了解哈夫曼树的形成的话显然是对的，

C完全二叉树：只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树，

D：根左右，在前面的也可能是根的左结点
5.AC 二分图 树 一定不会 出现 奇环
若一个图的每一对不同顶点恰有一条边相连，则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边，B显然是不可以的；

对于连通图，形成环的话也是显然不行的，所以是不一定的.

问题求解

1.1075

容斥原理，反着想

1~2015，有503个能被4整除的，有403个能被5整除的，有335个能被6整除的

其中能被4、5的最小公倍数20整除的算了两遍有100个，

能被4、6 的最小公倍数12整除的算了2遍有167个，

能被5、6 的最小公倍数30整除的算了两遍有67个，

所以503+403+335-100-167-67=907；

在减的时候，能被4、5、6 的最小公倍数120整除的数减了3遍，

在一开始算的时候也算了3遍，所以907种中没有能被120整除的数，所以907+33=940；

所以共有940个能被4、 5、 6 中任意一个数整除的数

答案就是：2015-940=1075

（当然你最小公倍数求错了的话怪我喽=。=）

2.

42

二叉树的按结点个数，不同形态数按照Catalan序列

其中，结点数为5的有(10)!/(5!*5!)/(5+1) = 42种

四

1、3，2

2、Ab （其实我也不大懂，旁边的一位大神告诉我，其实在草稿上画出指针和修改过程就很清楚了）

3、citizen（就是输出最长的字符串

4、31(递归，其实推着推着会发现凡是fun(0,，）的结果都为0，

然后凡是fun（1，，）=0+1+0=1

然后凡是fun(2,,)=1+1+1=3

然后凡是fun(3,,)=3+3+1=7

然后凡是fun(4,,)=7+7+1=15

最后凡是fun(5,,)=15+1+15=31

五．

1、（1）rmax[n]:=x[n];

（2）rmax[i]:=x[i];

（3）rmax[i]:=rmax[i-1]+x[i];

（4）rmax[i]:=rmax[i+1];

（5）lmax[i-1]+rmax[i+1]（因为要最少间隔一个数）

2、（1）v:=-1

(2)dist[i]<dist[v]

（3）v:=i;

(4)used[v]:=1;

(5)dist[i]>dist[v]+w[v,i]