noip2015提高组初赛
一、单项选择题(共15题,每题1.5分,共计22.5分;每题有且仅有一个正确选项)
- 线性表若采用链表存储结构,要求内存中可用存储单元地址( )。
A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
答案:D
解析:比如链式前向星?
设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n(n为正整数)及T(0) = 1,则 该算法的时间复杂度为( )。
A. O(log n) B. O(n log n) C. O(n) D. O(n2)
答案:D
解析:跟之前一样的坑,又踩进去了
- 在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了( )思想的算法
A. 贪心 B. 分治 C. 递推 D. 回溯
答案:A
详解见博客
- 对图G中各个结点分别指定一种颜色,使相邻结点颜色不同,则称为图G的一个正常 着色。正常着色图G所必需的最少颜色数,称为G的色数。那么下图的色数是( )。
A. 3 B. 4 C. 5 D. 6
答案:A
解析:自己搞出来个 B,看别人都是暴力……以后这种题目就多试几遍吧
二、不定项选择题(共5题,每题1.5分,共计7.5分;每题有一个或多个正确选项,多选或少选均不得分)
- 下列属于视频文件格式的有( )。 A. AVI B. MPEG C. WMV D. JPEG
答案:ABC
常见的视频格式:视频文件格式有不同的分类,如:
微软视频 :wmv、asf、asx
Real Player :rm、 rmvb
MPEG视频 :mpg、mpeg、mpe
手机视频 :3gp
Apple视频 :mov
Sony视频 :mp4、m4v
其他常见视频:avi、dat、mkv、flv、vob
——来自百度百科
3下列选项不是正确的IP地址的有( )。
A. 202.300.12.4 B. 192.168.0.3 C. 100:128:35:91 D. 111-103-35-21
答案:ACD
解析:对了还是写一下。IP地址的要求是
四个0~255的十进制数
用三个点 . 隔开
下列有关树的叙述中,叙述正确的有( )。
A. 在含有n个结点的树中,边数只能是(n-1)条
B. 在哈夫曼树中,叶结点的个数比非叶结点个数多1
C. 完全二叉树一定是满二叉树
D. 在二叉树的前序序列中,若结点u在结点v之前,则u一定是v的祖先
答案:AB
解析:还是哈夫曼树的问题……
三、
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
解析:写的时候是深搜一个一个枚举,还发现情况是左右对称的,所以只用算左边或右边就行。别人的解析是卡特兰数。
四
五.
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]
会迪杰斯特拉就行。
最新文章
- C#读取Excel,或者多个excel表,返回dataset
- 使用ikmv将jar转换为dll,在.NET中直接调用
- Android IOS WebRTC 音视频开发总结(八十三)-- 使用WebRTC广播网络摄像头视频(上)
- SharePoint Server 2013开发之旅(二):使用在线的开发人员网站进行SharePoint App开发
- 用 unoconv 将 xls 转换成 csv
- 操作haproxy配置文件教师版
- 将ASCII码位于32~126的95个字符输出到屏幕上,为了美观
- 14.5.2 Changing the Number or Size of InnoDB Redo Log Files 改变InnoDB Redo Log Files的数量
- 《InsideUE4》UObject(四)类型系统代码生成
- adb 查看 android手机的CPU架构
- 破解第一课:NOP绕过登录界面
- 04-Python入门学习-流程控制
- .net代码修改webconfig
- nginx路径设置(web)
- 【转】Context Switches上下文切换性能详解
- excel文字格式设置
- 【剑指Offer学习】【面试题3 :二维数组中的查找】
- 多线程编程,CPU是如何解决多线程内存访问问题的
- (字典树)Revenge of Fibonacci -- HDU -- 4099
- Javascript中判断变量是数组还是对象(array还是object)