2015 年第二十一届全国青少年信息学 奥林匹克竞赛初赛 提高组 一、选择题（共 15 题，每题 1.5 分）
1 、在计算机内部用来传送、存贮、加工处理的数据或指令都是以（）形式进行的。 A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码
2 、下列说法正确的是（） A. CPU 的主要任务是执行数据运算和程序控制 B. 存储器具有记忆能力，其中信息任何时候都不会丢失 C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D. 个人用户只能使用 Wifi 的方式连接到 Internet
3 、与二进制小数 0.1 相等的十六进制数是（） A. 0.8 B. 0.4 C. 0.2 D. 0.1
4 、下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（） A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2
5 、线性表若采用链表存储结构，要求内存中可用存储单元地址（） A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
6 、今有一空栈 S ，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（） A. f B. c C. a D. b
7 、前序遍历序列与后序遍历序列相同的二叉树为（） A. 非叶子结点只有左子树的二叉树 B. 只有根结点的二叉树 C. 根结点无右子树的二叉树 D. 非叶子结点只有右子树的二叉树
8 、如果根的高度是 1 ，具有 61 个结点的完全二叉树的高度是（） A. 5 B. 6 C. 7 D. 8
9 、 6 个顶点的连通图的最小生成树，其边数为（） A. 6 B. 5 C. 7 D. 4
10 、设某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n (n 为正整数)及 T(0)=1 ，则该算法的时间复杂度为（） A. O(logn) B. O(nlogn) C. O(n) D. O(n2)
11 、具有 n 个顶点， e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（） A. O(n2) B. O(e2) C. O(ne) D.O(n+e)
12 、在数据压缩编码的应用中，哈夫曼（ Huffman ）算法是一种采用了（）思想的算法。 A. 贪心 B. 分治 C. 递推 D. 回溯
13 、双向链表中有两个指针域， llink 和 rlink ，分别指向前戏及后继，设 p 指向链表中的一个结点， q 指向一待插入结点，现要求在 p 前插入 q ，则正确的插入为（） A. p->llink=q; q->rlink=p; p->llink->rlink=q;q->llink=p->llink; B. q->llink=p->llink; p->llink->rlink=q; q->rlink=p; p->llink-q->rlink; C. q->rlink=p; p->rlink=q; p->llink->rlink=q;q->rlink=p; D.p->llink->rlink=q; q->rlink=p; q->llink=p->llink; p->link=q;
14 、对图 G 中各个结点分别指点一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（）。 A. 3 B. 4 C. 5 D. 6
15 、在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不色诱选手自带的是（） A. 鼠标 B. 笔 C. 身份证 D. 准考证
二、不定项选择题
1 、以下属于操作系统的有（） A. Windows XP B. UNIX C. Linux D. Mac OS
2 、下列属于视频文件格式的有（） A. AVI B. MPEG C. WMV D. JPEG
3 、下列选项不是正确的 IP 地址的有（） A. 202.300.12.4 B. 192.168.0.3 C. 100:128:35:91 D. 111-132-35-21
4 、下列有关树的叙述中，叙述正确的有（） A. 在含有 n 个结点的树中，边数只能是(n-1)条 B. 在哈夫曼树中，叶结点的个数比非叶结点个数多 1 C. 完全二叉树一定是满二叉树 D. 在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先
5 、以下图中一定可以进行黑白染色的有（）。（黑白染色：为各个结点分别指定黑白两种颜色之一，使用相邻结点颜色不同。） A.二分图 B. 完全图 C. 树 D.连通图
三、问题求解
1 、在 1 和 2015 之间（包括 1 和 2015 在内）不能被 4 、 5 、 6 三个数任意一个整除的数有 个。
2 、结点数为 5 的不同形态的二叉树一共有 种。（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。）
http://wenku.baidu.com/view/d56cbcfaf5335a8102d220da.html?from=search
Select Language