第十一届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组 pascal 语言二小时完成 ) 全部试题答案均要求写在答卷纸上, 写在试卷纸上一律无效 一. 选择一个正确答案代码 (A/B/C/D/E), 填入每题的括号内 ( 每题 1.5 分, 共 30 分 ) 1. 在字符串 ababacbabcbdecced 中出现次数最多的字母出现了 ( ) 次 A. 6 B. 5 C. 4 D. 3 E. 2 2. 设全集 I = {a, b, c, d, e, f, g, h}, 集合 A = {a, b, c, d, e, f},b = {c, d, e},c = {a, d}, 那么集合 A B ~ C 为 ( ) A. {c, e} B. {d, e} C. {e} D. {c, d, e} E. {d, f} 3. 和十进制数 23 的值相等的二进制数是 ( ) A. 10110 B. 11011 C. 11011 D. 10111 E. 10011 4. 完全二叉树的结点个数为 11, 则它的叶结点个数为 ( ) A. 4 B.3 C.5 D. 2 E. 6 5. 平面上有五个点 A(5, 3), B(3, 5), C(2, 1), D(3, 3), E(5, 1) 以这五点作为完全图 G 的顶点, 每两点之间的直线距离是图 G 中对应边的权值 以下哪条边不是图 G 的最小生成树中的边 ( ) A. AD B. BD C. CD D. DE E. EA 6. Intel 的首颗 16 位处理器是 ( ) A. 8088 B. 80386 C. 80486 D. 8086 E. Pentium 7. 处理器 A 每秒处理的指令数是处理器 B 的 2 倍 某一特定程序 P 分别编译为处理器 A 和处理器 B 的指令, 编译结果处理器 A 的指令数是处理器 B 的 4 倍 已知程序 P 在处理器 A 上执行需要 1 个小时, 那么在输入相同的情况下, 程序 P 在处理器 B 上执行需要 ( ) 小时 A. 4 B. 2 C. 1 D. 1 / 2 E. 1 / 4 8. 以下哪个不是计算机的输出设备 ( ) A. 音箱 B. 显示器 C. 打印机 D. 扫描仪 E. 绘图仪 9. 下列活动中不属于信息学奥赛的系列活动的是 ( ) A. NOIP B. NOI C. IOI D. 冬令营 E. 程序员等级考试 10. 以下断电之后仍能保存数据的是 ( ) 1
A. 硬盘 B. 寄存器 C. 显存 D. 内存 E. 高速缓存 NOIP2005 普及 pascal 11. 以下哪个软件不是即时通信软件 ( ) A. 网易泡泡 B. MSN Messenger C. Google Talk D. 3DS Max E. QQ 12. 下列关于高级语言的说法错误的是 ( ) A. Fortran 是历史上的第一个面向科学计算的高级语言 B. Pascal 和 C 都是编译执行的高级语言 C. C++ 是历史上的第一个支持面向对象的语言 D. 编译器将高级语言程序转变为目标代码 E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 13. 下列设备不具有计算功能的是 ( ) A. 笔记本电脑 B. 掌上电脑 C. 智能手机 D. 电子计算器 E. 液晶显示器 14. 常见的邮件传输服务器使用 ( ) 协议接收邮件 A. HTTP B. SMTP C. TCP D. FTP E. POP3 15. 下列浏览器中, 由微软公司开发的浏览器是 ( ) A. Internet Explore B. Netscape C. Opera D. Firefox E. Mozilla 16. 一位艺术史学家有 20000 幅真彩色图像, 每幅图像约占 3M 空间 如果将这些图像以位图形式保存在 CD 光盘上 ( 一张 CD 光盘的容量按 600M 计算 ), 大约需要 ( ) 张 CD 光盘 A. 1 B. 10 C. 100 D. 1000 E. 10000 17. 设 A = true,b = false,c = false,d = true, 以下逻辑运算表达式值为真的是 ( ) A. (A B) (C D) B. ((A B) C) D C. A ((B C) D) D. (A (B C)) D E. (A B) (C D) 18. (3725) 8 + (B) 16 的运算结果是 ( ) A. (3736) 8 B. (2016) 10 C. (1111110000) 2 D. (3006) 10 E. (7B0) 16 19. 二叉树 T 的宽度优先遍历序列为 A B C D E F G H I, 已知 A 是 C 的父结点,D 是 G 的父结点,F 是 I 的父结点, 树中所有结点的最大深度为 3( 根结点深度设为 0), 可知 F 的父结点是 ( ) A. 无法确定 B. B C. C D. D E. E 20. 设栈 S 的初始状态为空, 元素 a, b, c, d, e, f, g 依次入栈, 以下出栈序列不可能出现的是 ( ) A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, d, c, b, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a 2
二. 问题求解 ( 请在空格处填上答案, 每空 5 分, 共 10 分 ) 1. 将数组 {32, 74, 25, 53, 28, 43, 86, 47} 中的元素按从小到大的顺序排列, 每次可以交换任 意两个元素, 最少需要交换次 2. 有 3 个课外小组 : 物理组, 化学组和生物组 今有张 王 李 赵 陈 5 名同学, 已知张 王为物理组成员, 张 李 赵为化学组成员, 李 赵 陈为生物组成员 如果要在 3 个小组中分别选出 3 位组长, 一位同学最多只能担任一个小组的组长, 共有种选择方案 三. 阅读程序 ( 共 4 题, 每题 8 分, 共计 32 分 ) 1. var a, b : integer; 输入 :10 read(a); b := (a * (a * a)) + 1; if b mod 3 = 0 then b := b div 3; if b mod 5 = 0 then b := b div 5; if b mod 7 = 0 then b := b div 7; if b mod 9 = 0 then b := b div 9; if b mod 11 = 0 then b := b div 11; if b mod 13 = 0 then b := b div 13; if b mod 15 = 0 then b := b div 15; writeln((100 * a - b) div 2); 2. var str : string; i : integer; str := 'Today-is-terrible!'; for i := 7 to 11 do if str[i] = '-' then str[i - 1] := 'x'; for i := 13 downto 1 do if str[i] = 't' then str[i + 1] := 'e'; writeln(str); 3. var a, b, c, p, q : integer; 3
r : array[0..2] of integer; read(a, b, c); p := a div b div c; q := b - c + a + p; r[0] := a * p div q * q; r[1] := r[0] * (r[0] - 300); if (3 * q - p mod 3 <= r[0]) and (r[2] = r[2]) then r[1] := r[r[0] div p mod 2] else r[1] := q mod p; writeln(r[0] - r[1]); 输入 :100 7 3 4. var str : string; len, i, j : integer; nchr : array [0..25] of integer; mmin : char; mmin := 'z'; readln(str); len := length(str); i := len; while i >= 2 do if str[i - 1] < str[i] then break; dec(i); if i = 1 then writeln('no result!'); exit; for j := 1 to i - 2 do write(str[j]); fillchar(nchr, sizeof(nchr), 0); for j := i to len do if (str[j] > str[i - 1]) and (str[j] < mmin) then mmin := str[j]; inc(nchr[ord(str[j]) - ord('a')]); dec(nchr[ord(mmin) - ord('a')]); inc(nchr[ord(str[i - 1]) - ord('a')]); write(mmin); for i := 0 to 25 do for j := 1 to nchr[i] do writeln; write(chr(i + ord('a'))); 4
输入 :zzyzcccbbbaaa 四. 完善程序 ( 前 4 空, 每空 2 分, 后 5 空, 每空 4 分, 共 28 分 ) 1. 判断质数 题目描述 : 输入 : 给出一个正整数, 判断这个数是否是质数 一个正整数 n(1 n 10000) 如果 n 是质数, 输出 YES ; 否则, 输出 NO 输入样例 : 10 输出样例 : NO 程序 : var 1 : integer; read(n); if n = 2 then writeln( 2 ) else if ( 3 ) or (n mod 2 = 0) then writeln('no') else i := 3; while i * i <= n do if 4 then writeln('no'); exit; i := i + 2; writeln('yes'); 2. 木材加工题目描述 : 木材厂有一些原木, 现在想把这些木头切割成一些长度相同的小段木头 ( 木头有可能有剩余 ), 需要得到的小段的数目是给定的 当然, 我们希望得到的小段越长越好, 你的任务是计算能够得到的小段木头的最大长度 木头长度的单位是 cm 原木的长度都是正整数, 我们要求切割得到的小段木头的长度也是正整数 输入 : 第一行是两个正整数 N 和 K(1 N 10000,1 K 10000),N 是原木的数目, K 是需要得到的小段的数目 5
NOIP2005 普及 pascal 接下来的 N 行, 每行有一个 1 到 10000 之间的正整数, 表示一根原木的长度 输出能够切割得到的小段的最大长度 如果连 1cm 长的小段都切不出来, 输出 0 输入样例 : 3 7 232 124 456 输出样例 : 114 程序 : var n, k : integer; len : array [1..10000] of integer; i, left, right, mid : integer; function isok(t : integer) : boolean; var num, i : integer; num := 0; for i := 1 to n do if num >= k then break; num := 1 ; if 2 then isok := true else isok := false; readln(n, k); right := 0; for i := 1 to n do readln(len[i]); if right < len[i] then right := len[i]; inc(right); 3 ; while 4 < right do mid := (left + right) div 2; if 5 then right := mid else left := mid; writeln(left); 6
赛区市学校姓名 ========================== 密封线 ========================== 第十一届全国青少年信息学奥林匹克联赛初赛试题 普及组答卷纸 阅 卷 记 录 总阅卷人 总得分 第 一 大 题 得 分 第二大题得分 题号 1 2 3 4 5 6 7 8 9 10 第三大题得分 得分 1) 2) 3) 4) 题号 11 12 13 14 15 16 17 18 19 20 第四大题得分 得分 (1) (2) ============================ 以下由考生填写 ========================== 答卷部分 一. 选择一个正确答案代码 (A/B/C/D), 填入每题的括号内 ( 每题 1.5 分, 多选无分, 共 30 分 ) 题号 1 2 3 4 5 6 7 8 9 10 选择题号 11 12 13 14 15 16 17 18 19 20 选择 二. 问题解答 ( 每题 5 分, 共 10 分 ) 1. 答 : 2. 答 : 三. 阅读程序, 并写出程序的正确运行结果 :( 每题 8 分, 共 32 分 ) (1) 程序的运行结果是 : (2) 程序的运行结果是 : 7
赛区市学校姓名 ========================== 密封线 ========================== (3) 程序的运行结果是 : (4) 程序的运行结果是 : 四. 根据题意, 将程序补充完整 ( 前 4 空, 每空 2 分, 后 5 空, 每空 4 分, 共 28 分 ) pascal 语言 ================= 1. 1 2 3 4 2. 1 2 3 4 5 8