一、单项选择题(共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]
会迪杰斯特拉就行。