当前位置:首页 >> 学科竞赛 >>

NOIP2008第十四届全国青少年信息学奥林匹克联赛初赛试题(含答案)汇总

2008 第十四届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 C 语言 二小时 完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、 单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确答 案)。 1. 在以下各项中,( )不是操作系统软件。 Symbian 2.微型计算机中,控制器的基本功能是( )。 A. 控制机器各个部件协调工作 B. 实现算术运算和逻辑运算 C. 存储各种控制信息 D. 获取外部信息 3. 设字符串 S=”Olympic”,S 的非空子串的数目是( )。 A. 29 B. 28 C. 16 D. 17 E. 7 4.完全二叉树共有 2*N-1 个结点,则它的叶节点数是( )。 A. N-1 B. 2*N C. N D. 2N-1 E. N/2 5.将数组{8, 23, 4, 16, 77, -5, 53, 100}中的元素按从大到小的顺序排列,每次可以 交换任意两个元素,最少需要交换( )次。 A. 4 B. 5 C. 6 D. 7 E. 8 6.设栈 S 的初始状态为空,元素 a,b,c,d,e,f 依次入栈 S,出栈的序列为 b,d,c,f,e,a,则栈 S 的容量至少应该是( )。 A. 6 B. 5 C. 4 D. 3 E. 2 7. 与十进制数 28.5625 相等的四进制数是( )。 A. 123.21 B. 131.22 C. 130.22 D. 130.21 E. 130.20 8. 递归过程或函数调用时,处理参数和返回地址,通常使用一种称为()的数 据结构。 A. 队列 B. 多维数组 C. 线性表 D. 链表 E. 栈 1 A. Solaris B. Linux C. Sybase D. Windows Vista E. E. 存放程序和数据 9. TCP/IP 是一组构成互联网基础的网络协议,字面上包括两组协议:传输控制协 议(TCP)和网际协议(IP)。TCP/IP 协议把 Internet 网络系统描述成具有四个 层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务,包括寻址 和路由器选择等功能的是()。 A. 链路层 B.网络层 C. 传输层 D. 应用层 E.会话层 10. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找,等概率的 情况下查找成功的平均查找长度(平均比较次数)是( )。 A. 35/11 B. 34/11 C. 33/11 D. 32/11 E. 34/10

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数大 于或等于 1。多选或少选均不得分)。 11. 在下列关于图灵奖的说法中,正确的有( )。 A. 图灵奖是美国计算机协会于 1966 年设立的,专门奖励那些对计算机事业作出 重要贡献的个人 B. 图灵奖有“计算机界诺贝尔奖”之称 C. 迄今为止,还没有华裔计算机科学家获此殊荣 D. 图灵奖的名称取自计算机科学的先驱、英国科学家阿兰· 图灵 12.计算机在工作过程中,若突然停电,( )中的信息不会丢失。 A. 硬盘 B. CPU C.ROM D. RAM 13. 设 A=true,B=false,C=true,D=false,以下逻辑运算表达式值为真的有 ( )。 A. (A∧B)∨(C∧D∨? A) B. ((? A∧B)∨C)∧? D C. (B∨C∨D)∨D∧A D. A∧(D∨? C)∧B 14.Web2.0 是近年来互联网的热门概念之一,其核心思想是互动与分享。下列网 站中,( )是典型的 Web2.0 应用。 A. Sina B. Flickr C. Yahoo D. Google 15. (2008)10 + (5B)16 的结果是( )。 A. (833)16 B. (2099)10 C. (4063)8 D. (100001100011)2 16. 二叉树 T,已知其先根遍历是 1 2 4 3 5 7 6(数字为结点的编号,以下同), 后根遍历是 4 2 7 5 6 3 1,则该二叉树的可能的中根遍历是( )。 A. 4 2 1 7 5 3 6 B. 2 4 1 7 5 3 6 C. 4 2 1 7 5 6 3 D. 2 4 1 5 7 3 6 17. 面向对象程序设计(Object-Oriented Programming)是一种程序设计的方法 论,它将对象作为程序的基本单元,将数据和程序封装在对象中,以提高软件的 重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中,正确的是 ( )。 A. 面向对象程序设计通常采用自顶向下设计方法进行设计。 B. 面向对象程序设计方法具有继承性(inheritance)、封装性(encapsulation)、 多态性(polymorphism)等几大特点。 C. 支持面向对象特性的语言称为面向对象的编程语言,目前较为流行的有 C++、 JAVA、C#等。 D. 面向对象的程序设计的雏形来自于 Simula 语言,后来在 SmallTalk 语言的完善 和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今,SmallTalk 语 言仍然被视为面向对象语言的基础。

18. 设 T 是一棵有 n 个顶点的树,下列说法正确的是( )。 A. T 是连通的、无环的 B. T 是连通的,有 n-1 条边 C. T 是无环的,有 n-1 条边 D. 以上都不对 19. NOIP 竞赛推荐使用的语言环境有( )。 A. Dev-C++ B. Visual C++ C. free pascal D. Lazarus 20. 在下列防火墙(firewall)的说法中,正确的有( )。 A. 防火墙是一项协助确保信息安全的设备,其会依照特定的规则,允许或是限制 数据通过 B. 防火墙可能是一台专属的硬件或是安装在一般硬件上的一套软件 C. 网络层防火墙可以视为一种 IP 数据包过滤器,只允许符合特定规则的数据包 通过,其余的一概禁止穿越防火墙 D. 应用层防火墙是在 TCP/IP 的“应用层”上工作,可以拦截进出某应用程序的所 有数据包 三.问题求解(共 2 题,每题 5 分,共计 10 分) 1.有 6 个城市,任何两个城市之间都有一条道路连接,6 个城市两两之间的距离 如下表所示,则城市 1 到城市 6 的最短距离为_____________。

2.书架上有 21 本书,编号从 1 到 21,从其中选 4 本,其中每两本的编号都不相 邻的选法一共有______种。 四.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. #include<stdio.h> int main() { int i, a, b, c, d, f[4]; for(i = 0; i < 4; i++) scanf("%d", &f[i]); a = f[0] + f[1] + f[2] + f[3]; a = a / f[0]; b = f[0] + f[2] + f[3]; b = b / a; c = (b * f[1] + a) / f[2]; d = f[(b / c ) % 4]; if(f[(a + b + c + d) % 4] > f[2]) printf("%d\n", a + b); else printf("%d\n", c + d); return 0; } 输入:9 19 29 39 输出:_______________ 2.#include<stdio.h> void foo(int a, int b, int c) {

if(a > b)

foo(c, a, b); else } int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); foo(a, b, c); return 0; } printf("%d,%d,%d\n", a, b, c); 输入:2 1 3 输出:__________ 3.#include<stdio.h> void f(int a, int b, int c) { printf("%d%d%d/", a, b, c); if(a == 3 && b == 2 && c == 1) return; if(b < c) f(a, c, b); else if(a < b) { } } int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); f(a, b, c); printf("\n"); return 0; if(a < c) f(c, a, b); else f(b, c, a);

} 输入: 1 3 2 输出: ________________________________________ 4. #include <stdio.h> #include <string.h> int i,j,len; char s[50]; int main() { scanf("%s", s); len = strlen(s); for (i = 0;i < len; ++i) { } for (i = 0;i < len; ++i) { } printf("%s/", s); for (j = 1;j < 4;j ++) { } printf("%s\n", s); return 0; } if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a'; if (s[i] < 'x') s[i] += 3; else s[i] += -23; for (i = 0;i < len-j; i = i + j) { } s[i] = s[i + j] ; 输入:ABCDEFGuvwxyz 输出:___________________________________________ 五.完善程序 (前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分) 1.(找第 k 大的数) 给定一个长度为 1,000,000 的无序正整数序列,以及另一个数 n(1<=n<=1000000),接下来以类似快速排序的方法找到序列中第 n 大的数(关于 第 n 大的数:例如序列{1,2,3,4,5,6}中第 3 大的数是 4)。 #include <stdlib.h> #include <stdio.h> int a[1000001],n,ans = -1;

void swap(int *a,int *b) { int c; c = *a; *a = *b; *b = c; } int FindKth(int left, int right, int n) { int tmp,value,i,j; if (left == right) return left; tmp = rand()% (right - left) + left; swap( &a[tmp], &a[left] ); value = ① i = left; j = right; while (i < j) { } ④ if (i < n) return FindKth( ⑤ ); if (i > n) return ⑥ return i; } int main() { int i; while (i < j && ② ) j --; if (i < j) {a[i] = a[j]; i ++;} else break; while (i < j && ③ ) i ++; if (i < j) {a[j] = a[i]; j - -;} else break; int m = 1000000; for (i = 1;i <= m;i ++) scanf("%d", &a[i]); scanf("%d", &n); ans = FindKth(1,m,n); printf("%d\n", a[ans]); return 0; }

2.(矩阵中的数字)有一个 n*n(1<=n<=5000)的矩阵 a, 对于 1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素,右边的元素一定 比左边的大。上下相邻的两个元素,下面的元素一定比上面的大。给定矩阵 a 中 的一个数字 k,找出 k 所在的行列(注意:输入数据保证矩阵中的数各不相 同)。 #include <stdio.h> int n,k,answerx,answery; int a[5001][5001]; void FindKPosition() { int i = n,j = n; while (j > 0) { } ① while (a[i][j] != k) { } ④ ⑤ } int main() while ( ② && i > 1) i --; while ( ③ && j <= n) j ++; if (a[n][j] < k) break; j -; { int i,j; scanf( "%d", &n ); for (i = 1;i <= n;i ++) for (j = 1;j <= n;j ++) scanf( "%d", &a[i][j]); scanf( "%d", &k ); FindKPosition(); printf("%d %d\n", answerx, answery); return 0; } 参考答案与评分标准 一、单项选择题:(每题 1.5 分) 1. C 2. A 3. B 4. C 5. B 6. D 7. D 8. E 9. B 10. C

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数大 于或等于 1。多选或少选均不得分)。 11. ABD 12. AC 13. BC 14. B 15. ABC 16. ABD 17. BCD 18. ABC 19. ACD 20. ABCD 三、问题求解:(共 2 题,每题 5 分,共计 10 分) 1.7 2.3060 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. 23 (信心题) 2. 1,3,2 (简单递归) 3. 132/213/231/312/321/ (全排列) 4. defghijxyzabc/hfizxjaybcccc (字符串替换) 五.完善程序 (前 6 空,每空 3 分,后 5 空,每空 2 分,共 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上 机验证,不一定上报科学委员会审查) 1. ① a[left] ② ③ ④ ⑤ a[j] < value (或 a[j] <= value) a[i] > value (或 a[i] >= value) a[i] := value; i,right,n ⑥ FindKth(left, i, n) 2. ① inc(j); (或者 j := j+1;) ② a[i,j] > k ③ a[i,j] < k ④ answerx := i; ⑤ answery := j;


相关文章:
NOIP2008全国青少年信息学奥林匹克联赛获奖名单(提...
NOIP2008 全国青少年信息学奥林匹克联赛获奖名单(提高组)一等奖序号 姓名 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25...
更多相关标签: