nbhkdz.com冰点文库

NOIP2015提高组C试题

时间:2015-10-11


第二十一届全国青少年信息学奥林匹克联赛初赛
提高组 C 语言试题 竞赛时间:2015 年 10 月 11 日 14:30~16:30
选手注意:
? ? 试题纸共有 9 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写在试题纸上的 一律无效。 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。

一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确 选项)
1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以( A. 2. 二进制码 B. 八进制码 )。 C. 十进制码 D. )形式进行的。 智能拼音码

下列说法正确的是( A. B. C. D.

CPU 的主要任务是执行数据运算和程序控制 存储器具有记忆能力,其中信息任何时候都不会丢失 两个显示器屏幕尺寸相同,则它们的分辨率必定相同 个人用户只能使用 Wifi 的方式连接到 Internet )。 C. 0.2 D. 0.1

3.

与二进制小数 0.1 相等的十六进制数是( A. 0.8 B. 0.4

4.

下面有四个数据组,每个组各有三个数据,其中第一个数据为八进制数,第二个数据为 十进制数,第三个数据为十六进制数。这四个数据组中三个数据相同的是( A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. ) 。

1762 1010 3F2

5.

线性表若采用链表存储结构,要求内存中可用存储单元地址( A. C. 必须连续 一定不连续 B. D. 部分地址必须连续 连续不连续均可

)。

6.

今有一空栈 S,对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈,进栈,出栈, 进栈,进栈,出栈的操作,则此操作完成后,栈 S 的栈顶元素为( A. f B. c C. a D. )。 b

CCF NOIP2015 初赛提高组 C 语言试题 第 1 页,共 9 页

7.

前序遍历序列与后序遍历序列相同的二叉树为( A. C. 非叶子结点只有左子树的二叉树 根结点无右子树的二叉树 B. D.

)。

只有根结点的二叉树 非叶子结点只有右子树的二叉树 )。 D. )。 7 D. 4 8

8.

如果根的高度为 1,具有 61 个结点的完全二叉树的高度为( A. 5 B. 6 C. 7

9.

6 个顶点的连通图的最小生成树,其边数为( A. 6 B. 5 C.

10. 设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n(n 为正整数)及 T(0) = 1,则 该算法的时间复杂度为( A. O(log n) B. )。 C. O(n) D. O(n2) O(n log n)

11. 具有 n 个顶点,e 条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运 算的时间复杂度均为( A. Θ(n )
2

)。 Θ(e2) C. Θ(ne) D. Θ(n + e) )思想的算法。 回溯

B.

12. 在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了( A. 贪心 B. 分治 C. 递推 D.

13. 双向链表中有两个指针域,llink 和 rlink,分别指回前驱及后继,设 p 指向链表中的 一个结点,q 指向一待插入结点,现要求在 p 前插入 q,则正确的插入为( A. B. C. D. p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink; q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink; q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p; p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q; 14. 对图 G 中各个结点分别指定一种颜色,使相邻结点颜色不同,则称为图 G 的一个正常 着色。 正常着色图 G 所必需的最少颜色数, 称为 G 的色数。 那么下图的色数是 ( ) 。 )。

CCF NOIP2015 初赛提高组 C 语言试题 第 2 页,共 9 页

A.

3

B.

4

C.

5

D.

6

15. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。 下列物品中不允许选 手自带的是( A. 鼠标 )。 B. 笔 C. 身份证 D. 准考证

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个或多个正确 选项,多选或少选均不得分)
1. 以下属于操作系统的有( A. 2. Windows XP B. )。 C. )。 C. )。 C. 100:128:35:91 D. 111-127-35-21 WMV D. JPEG Linux D. Mac OS

UNIX

下列属于视频文件格式的有( A. AVI B. MPEG

3.

下列选项不是正确的 IP 地址的有( A. 202.300.12.4 B. 192.168.0.3

4.

下列有关树的叙述中,叙述正确的有( A. B. C. D.

)。

在含有 n 个结点的树中,边数只能是(n-1)条 在哈夫曼树中,叶结点的个数比非叶结点个数多 1 完全二叉树一定是满二叉树 在二叉树的前序序列中,若结点 u 在结点 v 之前,则 u 一定是 v 的祖先 )。(黑白染色:为各个结点分别指定黑白 C. 树 D. 连通图

5.

以下图中一定可以进行黑白染色的有( 两种颜色之一,使相邻结点颜色不同。) A. 二分图 B. 完全图

CCF NOIP2015 初赛提高组 C 语言试题 第 3 页,共 9 页

三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有部 分分)
1. 在 1 和 2015 之间(包括 1 和 2015 在内)不能被 4、5、6 三个数任意一个数整除的数 有_________个。 2. 结点数为 5 的不同形态的二叉树一共有_________种。(结点数为 2 的二叉树一共有 2 种:一种是根结点和左儿子,另一种是根结点和右儿子。)

四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分)
1. #include <stdio.h> struct point { int x; int y; }; int main() { struct EX{ int a; int b; struct point c; } e; e.a = 1; e.b = 2; e.c.x = e.a + e.b; e.c.y = e.a * e.b; printf("%d,%d\n", e.c.x, e.c.y); return 0; } 输出:_________ 2. #include <stdio.h>

CCF NOIP2015 初赛提高组 C 语言试题 第 4 页,共 9 页

void fun(char *a, char *b) { a = b; (*a)++; } int main() { char c1, c2, *p1, *p2; c1 = 'A'; c2 = 'a'; p1 = &c1; p2 = &c2; fun(p1, p2); printf("%c%c\n", c1, c2); return 0; } 输出:_________ 3. #include <stdio.h> #include <string.h> int main() { int i, len, maxlen; char s[256], ss[256]; maxlen = 0; do { scanf("%s", ss); len = strlen(ss); if (ss[0] == '#') break; if (len > maxlen) { strcpy(s, ss); maxlen = len; } } while (1); printf("%s\n", s); return 0; }

CCF NOIP2015 初赛提高组 C 语言试题 第 5 页,共 9 页

输入: I am a citizen of China # 输出:_________ 4. #include <stdio.h> int fun(int n, int fromPos, int toPos) { if (n == 0) return 0; int t; for (t = 1; t <= 3; t++) if (t != fromPos && t != toPos) break; int tot = 0; tot += fun(n - 1, fromPos, t); tot++; tot += fun(n - 1, t, toPos); return tot; } int main() { int n; scanf("%d", &n); printf("%d\n", fun(n, 1, 3)); return 0; } 输入:5 输出:_________

CCF NOIP2015 初赛提高组 C 语言试题 第 6 页,共 9 页

五、完善程序(共 2 题,每题 14 分,共计 28 分)
1. (双子序列最大和)给定一个长度为 n(3 ≤ n ≤ 1000)的整数序列,要求从中选出两个 连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一 个连续子序列的序列和为该连续子序列中所有数之和。 要求: 每个连续子序列长度至少 为 1,且两个连续子序列之间至少间隔 1 个数。(第五空 4 分,其余 2.5 分) #include <stdio.h> #define MAXN 1000 int n, i, ans, sum; int x[MAXN]; int lmax[MAXN]; // lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和 int rmax[MAXN]; // rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和 int main() { scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", &x[i]); lmax[0] = x[0]; for (i = 1; i < n; i++) if (lmax[i - 1] <= 0) lmax[i] = x[i]; else lmax[i] = lmax[i - 1] + x[i]; for (i = 1; i < n; i++) if (lmax[i] < lmax[i - 1]) lmax[i] = lmax[i - 1]; (1) ; for (i = n - 2; i >= 0; i--) if (rmax[i + 1] <= 0) (2) else (3) ; ;

CCF NOIP2015 初赛提高组 C 语言试题 第 7 页,共 9 页

for (i = n - 2; i >= 0; i--) if (rmax[i] < rmax[i + 1]) (4) ; ans = x[0] + x[2]; for (i = 1; i < n - 1; i++) { sum = (5) ; if (sum > ans) ans = sum; } printf("%d\n", ans); return 0; } 2. (最短路径问题)无向连通图 G 有 n 个结点,依次编号为 0,1,2,...,(n-1)。用邻接矩阵的 形式给出每条边的边长,要求输出以结点 0 为起点出发,到各结点的最短路径长度。 使用 Dijkstra 算法解决该问题:利用 dist 数组记录当前各结点与起点的已找到的最 短路径长度;每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展,更新与 v 相邻 的结点的 dist 值;不断进行上述操作直至所有结点均被扩展,此时 dist 数据中记录的值 即为各结点与起点的最短路径长度。(第五空 2 分,其余 3 分) #include <stdio.h> #define MAXV 100 int n, i, j, v; int w[MAXV][MAXV]; // 邻接矩阵,记录边长 // 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度,若无边则为-1 int dist[MAXV]; int used[MAXV]; // 记录结点是否已扩展(0:未扩展;1:已扩展) int main() { scanf("%d", &n); for (i = 0; i < n; i++) for (j = 0; j < n; j++) scanf("%d", &w[i][j]); dist[0] = 0;

CCF NOIP2015 初赛提高组 C 语言试题 第 8 页,共 9 页

for (i = 1; i < n; i++) dist[i] = -1; for (i = 0; i < n; i++) used[i] = 0; while (1) { (1) ; (2) )) for (i = 0; i < n; i++) if (used[i] != 1 && dist[i] != -1 && (v == -1 || (3) if (v == -1) break; (4) ; (5) )) for (i = 0; i < n; i++) if (w[v][i] != -1 && (dist[i] == -1 || dist[i] = dist[v] + w[v][i]; } for (i = 0; i < n; i++) printf("%d\n", dist[i]); return 0; } ;

CCF NOIP2015 初赛提高组 C 语言试题 第 9 页,共 9 页


NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛...

NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言试题_学科竞赛_高中教育_教育专区。NOIP2015第二十一届全国青少年信息学奥林匹克联赛初赛提高组C语言...

NOIP2015提高组复赛试题Day2

第 2 页共 6 页 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day2 2.子串 (substring.cpp/c/pas) 【问题描述】 有两个仅包含小写英文字母的字符串 A...

NOIP2015提高组初赛C++试题_图文

NOIP2015提高组初赛C++试题_学科竞赛_高中教育_教育专区。 文档贡献者 我昰岽人...NOIP2015普及组C++试题 暂无评价 7页 1下载券 NOIP2015普及组C试题 暂无评价...

noip2015提高组复赛试题答案

noip2015 提高组复赛试题答案一. 单项选择题 (共 20 题,每题 1.5 分,共计 30 分;每题有且仅有一个正确 答案。 ) 1. 1MB 等于( A. 1000 字节 C. ...

NOIP2015年初赛提高组模拟试题

NOIP2015年初赛提高组模拟试题_学科竞赛_高中教育_教育专区。信息学初赛模拟试题 ...1.微型计算机的性能主要取决于(C )。 A)内存 信息学初赛模拟试题 一、 选择...

noip2015提高组复赛试题答案

noip2015提高组复赛试题答案_IT认证_资格考试/认证_教育专区。全国信息学奥林...magic.c -lm fpc magic.pas message.cpp message.c message.pas landlords....

NOIP2015提高组day1第二题解题报告

(c>='0'&&c<='9'){ x=x*10+c-'0'; c=getchar(); } if(b) ...NOIP2015提高组复赛试题... 6页 1下载券 NOIP2015提高组解题报告 9页 3下载...

NOIP2015提高组解题报告

NOIP2015提高组解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组的解题报告,有详细的算法和代码 NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你...

NOIP2015提高组初赛试题C++(A3版)

NOIP2015提高组初赛试题C++(A3版)_学科竞赛_高中教育_教育专区。第二十一届...C.Linux D.Mac OS } e.b = 2; e.c.x = e.a + e.b; e.c.y ...

NOIP2015提高组复赛试题Day1+Day2纯Word版

NOIP2015提高组复赛试题Day1+Day2纯Word版_学科竞赛_高中教育_教育专区。NOIP...message.c message.pas landlords.cpp landlords.c landlords.pas g++ -o ...