2003年第九届NOIP复赛试题(提高组) 发布日期: 2006-01-22 访问总次数: 4865 题一 神经网络【问题背景】 人工神经网络(Artificial Neural Network)是一种新兴的具有自我学习能力的计算系统,在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向,兰兰同学在自学了一本神经网络的入门书籍后,提出了一个简化模型,他希望你能帮助他用程序检验这个神经网络模型的实用性。【问题描述】 在兰兰的模型中,神经网络就是一张有向图,图中的节点称为神经元,而且两个神经 图中,X1—X3是信息输入渠道,Y1-Y2是信息输出渠道,C1表示神经元目前的状态,Ui是阈值,可视为神经元的一个内在参数。 神经元按一定的顺序排列,构成整个神经网络。在兰兰的模型之中,神经网络中的神经无分为几层;称为输入层、输出层,和若干个中间层。每层神经元只向下一层的神经元输出信息,只从上一层神经元接受信息。下图是一个简单的三层神经网络的例子。兰兰规定,Ci服从公式:(其中n是网络中所有神经元的数目) 公式中的Wji(可能为负值)表示连接j号神经元和 i号神经元的边的权值。当 Ci大于0时,该神经元处于兴奋状态,否则就处于平静状态。当神经元处于兴奋状态时,下一秒它会向其他神经元传送信号,信号的强度为Ci。 如此.在输入层神经元被激发之后,整个网络系统就在信息传输的推动下进行运作。现在,给定一个神经网络,及当前输入层神经元的状态(Ci),要求你的程序运算出最后网络输出层的状态。【输入格式】输入文件第一行是两个整数n(1≤n≤20)和p。接下来n行,每行两个整数,第i+1行是神经元i最初状态和其阈值(Ui),非输入层的神经元开始时状态必然为0。再下面P行,每行由两个整数i,j及一个整数Wij,表示连接神经元i、j的边权值为Wij。【输出格式】 输出文件包含若干行,每行有两个整数,分别对应一个神经元的编号,及其最后的状态,两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态,并且按照编号由小到大顺序输出! 若输出层的神经元最后状态均为 0,则输出 NULL。【输入样例】5 61 01 00 10 10 11 3 11 4 11 5 12 3 12 4 12 5 1【输出样例】3 14 15 1 题二 侦探推理【问题描述】明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明明不知情的情况下),明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被询问者可能会说:证词中出现的其他话,都不列入逻辑推理的内容。明明所知道的是,他的同学中有N个人始终说假话,其余的人始终说真。现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个!【输入格式】 输入由若干行组成,第一行有二个整数,M(1≤M≤20)、N(1≤N≤M)和P(1≤P≤100);M是参加游戏的明明的同学数,N是其中始终说谎的人数,P是证言的总数。接下来M行,每行是明明的一个同学的名字(英文字母组成,没有主格,全部大写)。往后有P行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句证词,符合前表中所列格式。证词每行不会超过250个字符。 输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。【输出格式】 如果你的程序能确定谁是罪犯,则输出他的名字;如果程序判断出不止一个人可能是罪犯,则输出 Cannot Determine;如果程序判断出没有人可能成为罪犯,则输出 Impossible。【输入样例】3 1 5MIKECHARLESKATEMIKE:I am guilty.MIKE:Today is Sunday.CHARLES:MIKE is guilty.KATE:I am guilty.KATE:How are you 【输出样例】MIKE 题三 加分二叉树【问题描述】 设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下: subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数 若某个子树为主,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出; (1)tree的最高加分 (2)tree的前序遍历【输入格式】 第1行:一个整数n(n<30),为节点个数。 第2行:n个用空格隔开的整数,为每个节点的分数(分数<100)。【输出格式】 第1行:一个整数,为最高加分(结果不会超过4,000,000,000)。 第2行:n个用空格隔开的整数,为该树的前序遍历。【输入样例】 5 5 7 1 2 10【输出样例】 145 3 1 2 4 5 题四 传染病控制 【问题背景】 近来,一种新的传染病肆虐全球。蓬莱国也发现了零星感染者,为防止该病在蓬莱国大范围流行,该国政府决定不惜一切代价控制传染病的蔓延。不幸的是,由于人们尚未完全认识这种传染病,难以准确判别病毒携带者,更没有研制出疫苗以保护易感人群。于是,蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。经过 WHO(世界卫生组织)以及全球各国科研部门的努力,这种新兴传染病的传播途径和控制方法已经研究消楚,剩下的任务就是由你协助蓬莱国疾控中心制定一个有效的控制办法。 【问题描述】 研究表明,这种传染病的传播具有两种很特殊的性质; 第一是它的传播途径是树型的,一个人X只可能被某个特定的人Y感染,只要Y不得病,或者是XY之间的传播途径被切断,则X就不会得病。 第二是,这种疾病的传播有周期性,在一个疾病传播周期之内,传染病将只会感染一代患者,而不会再传播给下一代。 这些性质大大减轻了蓬莱国疾病防控的压力,并且他们已经得到了国内部分易感人群的潜在传播途径图(一棵树)。但是,麻烦还没有结束。由于蓬莱国疾控中心人手不够,同时也缺乏强大的技术,以致他们在一个疾病传播周期内,只能设法切断一条传播途径,而没有被控制的传播途径就会引起更多的易感人群被感染(也就是与当前已经被感染的人有传播途径相连,且连接途径没有被切断的人群)。当不可能有健康人被感染时,疾病就中止传播。所以,蓬莱国疾控中心要制定出一个切断传播途径的顺序,以使尽量少的人被感染。你的程序要针对给定的树,找出合适的切断顺序。【输入格式】 输入格式的第一行是两个整数n(1≤n≤300)和p。接下来p行,每一行有两个整数i和j,表示节点i和j间有边相连(意即,第i人和第j人之间有传播途径相连)。其中节点1是已经被感染的患者。【输出格式】 只有一行,输出总共被感染的人数。【输入样例】 7 6 1 2 1 3 2 4 2 5 3 6 3 7【输出样例】 3
HYPERLINK "http://www./" \t "_blank"
元
之间至多有一条边相连,下图是一个神经元的例子:
2004年第十届NOIP初赛试题(普及组) 发布日期: 2006-02-09 访问总次数: 6304 第十届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一.选择一个正确答案代码(A/B/C/D/E),填入每题的括号内 (每题1.5分, 共30分) 1. 美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是(C)。A. 提出理想计算机的数学模型,成为计算机科学的理论基础。B. 是世界上第一个编写计算机程序的人。C. 提出存储程序工作原理,并设计出第一台具有存储程序功能的计算机EDVAC。D. 采用集成电路作为计算机的主要功能部件。E. 指出计算机性能将以每两年翻一番的速度向前发展。 2. 下列哪个不是CPU(中央处理单元)(B)。A. Intel Itanium B. DDR SDRAM C. AMD Athlon64D. AMD Opteron E. IBM Power 5 3. 下列网络上常用的名字缩写对应的中文解释错误的是(D)。A. WWW(World Wide Web):万维网。B. URL(Uniform Resource Locator):统一资源定位器。C. HTTP(Hypertext Transfer Protocol):超文本传输协议。D. FTP(File Transfer Protocol):快速传输协议。E. TCP(Transfer Control Protocol):传输控制协议。 4. 下面哪个部件对于个人桌面电脑的正常运行不是必需的(C)。A. CPU B. 图形卡(显卡) C. 光驱 D. 主板 E. 内存 5. 下列哪个软件属于操作系统软件(D)。A. Microsoft Word B. 金山词霸 C. Foxmail D. WinRAR E. Red Hat Linux 6. 下列哪个不是计算机的存储设备(E)。A. 文件管理器 B. 内存 C. 高速缓存 D. 硬盘 E. U盘 7. 下列说法中错误的是(E)。A. CPU的基本功能就是执行指令。B. CPU访问内存的速度快于访问高速缓存的速度。C. CPU的主频是指CPU在1秒内完成的指令周期数。D. 在一台计算机内部,一个内存地址编码对应唯一的一个内存单元。E. 数据总线的宽度决定了一次传递数据量的大小,是影响计算机性能的因素之一。 8. 彩色显示器所显示的五彩斑斓的色彩,是由红色、蓝色和(D)色混合而成的。A. 紫 B. 白 C. 黑 D. 绿 E. 橙 9. 用静电吸附墨粉后转移到纸张上,是哪种输出设备的工作方式(E)。A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪 10. 一台计算机如果要利用电话线上网,就必须配置能够对数字信号和模拟信号进行相互转换的设备,这种设备是(B)。A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥 11. 下列哪个不是数据库软件的名称(E)。A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro 12. 下列哪个程序设计语言不支持面向对象程序设计方法(D)。A. C++ B. Object Pascal C. C D. Smalltalk E. Java 13. 由3个a,1个b和2个c构成的所有字符串中,包含子串“abc”的共有(E)个。A. 20 B. 8 C. 16 D. 12 E. 24 14. 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状态为空,从这一时刻开始的出入记录为:“进,出,进,进,出,进,进,进,出,出,进,出”。假设车辆入站的顺序为1,2,3,……,则车辆出站的顺序为(C)。A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7 15. 二叉树T,已知其前序遍历序列为1 2 4 3 5 7 6,中序遍历序列为4 2 1 5 7 3 6,则其后序遍历序列为(B)。A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1 16. 满二叉树的叶结点个数为N,则它的结点总数为(C)。A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 17. 十进制数2004等值于八进制数(B)。A. 3077 B. 3724 C. 2766 D. 4002 E. 3755 18. (2004)10 + (32)16的结果是(D)。A. (2036)10 B. (2054)16 C. (4006)10 D. (100000000110)2 E. (2036)16 19. 在下图中,从顶点(D)出发存在一条路径可以遍历图中的每条边一次,而且仅遍历一次。 A. A点 B. B点 C. C点 D. D点 E. E点 20. 某大学计算机专业的必修课及其先修课程如下表所示: 课程代号C0C1C2C3C4C5C6C7课程名称高等数学程序设计语言离散数学数据结构编译技术操作系统普通物理计算机原理先修课程 C0, C1C1, C2C3C3, C7C0C6 请你判断下列课程安排方案哪个是不合理的(D)。A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4E. C0, C1, C2, C3, C6, C7, C5, C4 二.问题求解 (每题5分,共10分) 1. 一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材,售价是30元;每张椅子要使用16个单位的木材,售价是20元。使用已有的木材生产桌椅(不一定要把木材用光),最多可以卖 元钱。 2. 75名儿童到游乐场去玩。他们可以骑旋转木马,坐滑行铁道,乘宇宙飞船。已知其中20人这三种东西都玩过,55人至少玩过其中的两种。若每样乘坐一次的费用是5元,游乐场总共收入700,可知有 名儿童没有玩过其中任何一种。 三.阅读程序 (每题8分,共32分) 1.program program1;var a, b, c, d, e: integer;begin a := 79; b := 34; c := 57; d := 0; e := -1; if (a < c) or (b > c) then d := d + e else if (d + 10 < e) then d := e + 10 else d := e - a; writeln(d);end.输出:80。 2.program program2;var i, j: integer; str1, str2: string;begin str1 := 'pig-is-stupid'; str2 := 'clever'; str1[1] := 'd'; str1[2] := 'o'; i := 8; for j := 1 to 6 do begin str1[i] := str2[j]; inc(i); end; writeln(str1);end.输出:dog-is-clever。 3.program progam3;var u: array [0..3] of integer; a, b, c, x, y, z: integer;begin read(u[0], u[1], u[2], u[3]); a := u[0] + u[1] + u[2] + u[3] - 5; 18 b := u[0] * (u[1] - u[2] div u[3] + 8); 18 c := u[0] * u[1] div u[2] * u[3]; 4 x := (a + b + 2) * 3 - u[(c + 3) mod 4]; 109 y := (c * 100 - 13) div a div (u[b mod 3] * 5); 10 if((x+y) mod 2 = 0) then z := (a + b + c + x + y) div 2; z := (a + b + c – x - y) * 2; writeln(x + y - z);end输入:2 5 7 4输出:263。 4.program program4;var c: array[1..3] of string[200]; s: array[1..10] of integer; m, n, i: integer;procedure numara;var cod: boolean; i, j, nr: integer;begin for j := 1 to n do begin nr := 0; cod := true; for i := 1 to m do if c[i, j] = '1' then begin if not cod then begin cod := true; inc(s[nr]); nr := 0; end end else begin if cod then begin nr := 1; cod := false; end else inc(nr); end; if not cod then inc(s[nr]); end;end;begin readln(m, n); for i := 1 to m do readln(c[i]); numara; for i := 1 to m do if s[i] <> 0 then write(i, ' ', s[i], ' ');end.输入:3 101110000111 11000011111000000011输出:1 4 2 1 3 3。 四、完善程序 (前4空,每空2分,后5空,每空4分,共28分) 1.三角形内切圆的面积题目描述:给出三角形三边的边长,求此三角形内切圆(如下图所示,三角形的内切圆是和三角形三边都相切的圆)的面积。 输入:三个正实数a、b、c(满足a+b>c,b+c>a,c+a>b), 表示三角形三边的边长。输出:三角形内切圆的面积,结果四舍五入到小数点后面2位。输入样例:3 4 5输出样例:3.14程序:program program1;var a, b, c, r, s, t: real;begin read(a, b, c); s := ( ① ) / 2; t := ② (s * (s - a) * (s - b) * (s - c)); r := t / s; writeln(3.1415927 * r * ③ : 0 : ④ );end. 2.Joseph题目描述:原始的Joseph问题的描述如下:有n个人围坐在一个圆桌周围,把这n个人依次编号为1,…,n。从编号是1的人开始报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m个人又出列,…,如此反复直到所有的人全部出列为止。比如当n=6,m=5的时候,出列的顺序依次是5,4,6,2,3,1。现在的问题是:假设有k个好人和k个坏人。好人的编号的1到k,坏人的编号是k+1到2k。我们希望求出m的最小值,使得最先出列的k个人都是坏人。输入:仅有的一个数字是k(0 < k <14)。输出: 使得最先出列的k个人都是坏人的m的最小值。输入样例:4输出样例:30程序:program program2;var i, k, m, start: longint; find: boolean;function check(remain: integer): boolean;var result: integer;begin result:=( ① ) mod remain; if( ② )then begin start := result; check := true; end else check := false;end;begin find := false; read(k); m := k; while ( ③ ) do begin find := true; start := 0; for i := 0 to k-1 do if( not check( ④ )) then begin find := false; break; end; inc(m); end; writeln( ⑤ );end. 信息学竞赛普及组初赛模拟试题(一)
(本试题全部为笔试,满分100分)
试题由四部分组成:1、选择题 2、问题求解题 3、程序阅读理解题 4、程序完善题
一、选择题:共20题,每题1.5分,共计30分。每题有5个备选答案,前10个题为单选题(即每题有且只有一个正确答案,选对得分),后10题为不定项选择题(即每题有1至5个正确答案,只有全部选对才得分)。
1、计算机网络最大的优点是 。
A、精度高 B、资源共享 C、运行速度快 D、存储容量大 E、逻辑判断能力强
2、计算机病毒是指 。
A、编制有错误的计算机程序 B、设计不完善的计算机程序 C、计算机的程序已被破坏
D、以危害系统为目的的特殊的计算机程序 D、没有经过编译的计算机程序
3、在各种查找算法中,平均查找长度(与关键字比较次数的期望值)与查找表中元素个数 n 无关的查找方法是____。
A. 顺序查找 B. 散列查找 C. 折半查找 D. 动态查找 E、二分查找
4、下列各数中最大的是____。
A、 11010110.0101(二进制) B、D6.53(十六进制) C、 214.32(十进制)
D、326.25(八进制) E、23.26(三十二进制)
5.已知英文字母a的ASCll代码值是十六进制数61H,那么字母d的ASCll 代码值是
A)34H B)54H C)24H D)64H E)74H
6、若一台计算机的字长为 32 位,则表明该机器___。
A. 能处理的数值最大为 4 位十进制数 B. 能处理的数值最多为 4 个字节
C. 在 CPU 中能够作为一个整体加以处理的二进制数据为 4 个字节
D. 在 CPU 中运算的结果最大为 232 E.表示计算机的时钟脉冲
7、编译程序和解释程序是两类高级语言翻译程序,它们的根本区别在于__。
A. 是否进行优化处理 B. 执行效率不同 C. 对源程序中的错误处理不同
D. 是否形成目标程序 E.编写方式不同
8、在字符串“abcde”中有___个子串 C
A. 14 B. 15 C. 16 D. 17 E.18
9、假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为 。
A、ABCDEFGHIJ B、ABDEGHJCFI C、ABDEGHJFIC D、ABDEGJHCFI E、ABEDGHCJFI
10、某硬盘中共有9个盘片,16个记录面,每个记录面上有2100个磁道,每个磁道分为64个扇区,每扇区为512字节,则该硬盘的存储容量为 。
A、590.6MB B、9225MB C、1050MB D、1101MB E、1200M
11、以下属于文件管理的是(D)
A. 删除文件 B. 拷贝文件 C. 移动文件 D. 运行文件 E、剪切文件
12、图标是Windows操作系统中的一个重要概念,它表示Windows的对象。它可以指B 。
A、文档或文件夹 B、应用程序 C、设备或其它的计算机 D、系统文件 E、以上都不正确
13、发送电子邮件可包含的信息有: A、B
A、文字 B、图片 C、声音 D、程序 E、视频
14、下列哪些是属于内存储器:B、C
A、硬盘 B、RAM C、ROM D、CACHE E、光盘
15、计算机中声音、图形图像信息都是以文件的形式存储的,它们的文件格式有许多种,可以通过扩展名来识别,常见的文件扩展名有:① BMP ② AIF ③ JPG ④ WAV ⑤ GIF ⑥ VOC 其中,表示声音文件的有D,
A、 ①② B、③⑤ C、④⑥ D、 ②④⑥ E、②③④
16、以下数据结构中哪些不是线性结构 A
A、有向图 B、栈 C、线索二叉树 D、B树 E、队列
17、如果互连的局域网高层分别采用TCP/IP协议与SPX/IPX协议,那么我们可以选择的互连设备应该是:A
A、中继器 B、网桥 C、网卡 D、路由器 E、调制解调器
18、软件测试中,发现错误产生的原因依赖于所使用的调试策略,而主要的调试方法包括了B
A、试探法 B、回溯法、C、演绎法 D、归纳法 E、平均法
19、不能将高级语言源程序转换成目标程序的是
A、调试程序 B、解释程序 C、编译程序 D、编辑程序 E、目标程序
20、 设二维数组F的行下标为1至5,列下标为0至8,F的每个数据元素均占4个字节。在按行存贮的情况下,已知数据元素F[2,2]的第一个字节是1044,则F[3,4]和F[4,3]的第一个字节的地址分别为A 和 ,
A、1088 B、1084 C、1092 D、1120 E、1124
二、填空题:共2题,第一题5分,第二题5分,共计10分。
1、十位数abcdefghij,其中不同的字母表示不同的数字。a是1的倍数,两位数ab是2的倍数,三位数abc是3的倍数,四位数abcd是4的倍数,……,十位数abcdefghij是10的倍数,则这个十位数是___ _____。
2、若今天是星期六,从今天起102001天后的那一天是星期______。
三、程序阅读理解题:共4题,每题8分,共计32分。
1、PROGRAM exarm( output);
VAR x,y,x:integer;
PROEDURE silly(x:integer;VAR y:integer);
BEGIN
x:=5;y:=6;z:=3;
writeln(x,y,z)
END;
BEGIN
x:=1;y:=2;z:=3;
silly(x,y);
writeln(x,y,z)
END.
输出结果为:
2、有下面程序段
FOR I:=1 TO 3 DO
BEGIN
FOR J:=1 TO 3 DO
BEGIN
IF I=3 THEN A[I,J]:=A[I-1,A[I-1,J]]+1
ELSE A[I,J]=J;
WRITE(A[I,J]:2)
END;
WRITELN
END
该程序的执行结果是:
3、PROGRAM TEST(INPUT,OUTPUT);
VAR A,B,C:INTEGER;
PROCEDURE P(VAR X:INTEGER;Y:INTEGER);
VAR M,N:INTEGER;
BEGIN
M:=X*Y;
X:=X+5;
Y:=Y+5;
N:=X*Y;
WRITELN(M:4,N:4)
END;
BEGIN
A:=3;B:=3;
P(A,B);
P(A,B)
END
运行结果为:
4、PROGRAM EXAM(INPUT,OUTPUT);
VAR A:ARRAY[1..6] OF INTEGER;
I,J,K:INTEGER;
BEGIN
FOR I:=1 TO 6 DO
READ(A[I]);
READLN;
FOR I:=1 TO 6 DO
BEGIN
IF I=1 THEN K:=1
ELSE K:=8-I;
FOR J:=1 TO 6 DO
BEGIN
WRITE(A[K]:2);
IF K=6 THEN K:=1
ELSE K:=K+1;
END;
WRITELN
END
END
输入:8 1 4 2 5 6
输出结果为:
四、程序完善题:共2题,每题14分,共计28分。
1、对给定的10个国家名,按其字母的顺序输出。
程序如下:
program ex8_3;
var i,j,k:integer;
t:string[20];
cname:array[1..10] of string[20];
begin
for i:=1 to 10 do readln(cname[i]);
for i:=1 to 9 do
begin
(1) ;
for j:=i+1 to 10 do
if cname[k]>cname[j] then (2);
(3); cname[i]:=cname[k];cname[k]:=t;
end;
for i:=1 to 10 do writeln(cname[i]);
end.
2、编制用筛法求1-n(n≤200)以内素数的程序。
分析: 由希腊著名数学家埃拉托色尼提出的所谓“筛法”,步骤如下:
①将所有候选数放入筛中;
②找筛中最小数(必为素数)next,放入集合primes中;
③将next的所有倍数从筛中筛去;
④重复②~④直到筛空。
编程时,用集合变量sieve表示筛子,用集合primes存放所有素数。
源程序如下:
program ex10_3;
const n=200;
var sieve,primes:set of 2..n;
next,j:integer;
begin
sieve:=[2..n];{将所有候选数放入筛中}
primes:=[];{素数集合置空}
next:=2;
repeat
{找筛sieve中最小一个数}
while not(next in sieve) and(next<=n)do
next:=succ(next);
(4) ;{将最小数放入素数集合中}
{将这个素数的倍数从筛中删去}
j:=next;
while j<=n do
begin
(5) ;
(6) ;
end
until sieve=[];
j:=0;
for next:=2 to n do{打印出所有素数}
if next in primes then
begin
write(next:5);
(7) ;
if j mod 10=0 then writeln;
end;
writeln;
end.
信息学奥林匹克联赛初赛模拟试题一参考答案(普及组)
一、选择题:共20题,每题1.5分,共计30分。每题有5个备选答案,前10个题为单选题(即每题有且只有一个正确答案,选对得分),后10题为不定项选择题(即每题有1至5个正确答案,只有全部选对才得分)。
1、B 2、D、 3、B 4、D 5、D 6、C 7、D 8、C 9、B 10、C
11、ABCE 12、ABCD 13、ABCDE 14、BCD 15、CD
16、ACD 17、D 18、ABCD 19、ABD 20、AD
二、填空题:共2题,第一题5分,第二题5分,共计10分。
1、3816547290
2、星期五
解法如下:
10︿1 mod 7 =3
10︿2 mod 7 =2
10︿3 mod 7 =6
10︿4 mod 7 =4
10︿5 mod 7 =5
10︿6 mod 7 =1
10︿7 mod 7 =3
10︿8 mod 7 =2
……………………
出现余数循环:3、2、6、4、5、1、3、2……
2001 mod 6 = 3
所以,10的2001次方天后的情况与10的3次方天后的情况相同。
即余数为6。
因此,这天是星期五。
三、程序阅读理解题:共4题,每题8分,共计32分。
1、输出结果为:5 6 3
1 6 3
2、该程序的执行结果是:1 2 3
1 2 3
2 3 4
3、运行结果为:9 64
24 104
4、 输入:8 1 4 2 5 6
输出结果为:8 1 4 2 5 6
6 8 1 4 2 5
5 6 8 1 4 2
2 5 6 8 1 4
4 2 5 6 8 1
1 4 2 5 6 8
四、程序完善题:共2题,每题14分,共计28分。
1、 (1)k:=i; (2)k:=j; (3) t:=cname[i];
2、(4)primes:=primes+[next]; (5)sieve:=sieve-[j]; (6)j:=j+next; (7)j:=j+1;
衢州信息学奥赛网——..第九届分区联赛提高组初赛试题
(提高组 PASCAL 语言 二小时完成)
●● 全部答案均要写在答案卷子上,写在试卷纸上一律无效 ●●一.单项选择题 (共10题,每题1.5分,共计15分。每题有且仅有一个正确答案.)。
1. 图灵 (Alan Turing) 是 ( )。
A) 美国人 B) 英国人 C) 德国人 D) 匈牙利人 E) 法国人2. 第一个给计算机写程序的人是( )。
A) Alan Mathison Turing B) Ada Lovelace C) John von Neumann
D) John Mc-Carthy E) Edsger Wybe Dijkstra3. 十进制数2003等值于二进制数( )。
A) 0100000111 B) 10000011 C) 110000111 D) 11111010011 E) 11110100114. 假设A=true,B=false,C=ture,D=ture,逻辑运算表达式A∧B∨C∧D的值是( )。
A) ture B) false C) 0 D) 1 E) NULL5. 一个高度为h 的二叉树最小元素数目是( )。
A) 2h+1 B) h C) 2h-1 D) 2h E) 2h-16. 已知队列(13,2,11,34,41,77,5,7,18,26,15),第一个进入队列的元素是13,则第五个出队列的元素是( )。
A) 5 B) 41 C) 77 D) 13 E) 187. 下面一段程序是用( )语言书写的。
int func1(int n){
int i,sum=0;
for(i=1;i<=n;i++)
sum+=i*i;
return sum;
}
A) FORTRAN B) PASCAL C) C D) PROLOG E) BASIC8. 设全集E={1,2,3,4,5},集合A={1,4},B={1,2,5},C={2,4},则集合(A ∩B)∪~C 为( )。
A) 空集 B) {1} C) {3,5} D){1,5} E) {1,3,5}9. 表达式(1+34)*5-56/7 的后缀表达式为( )。
A) 1+34*5-56/7 B) -*+1 34 5/56 7 C) 1 34 +5*56 7/-
D) 1 34 5* +56 7/- E) 1 34+5 56 7-*/
10. 下列计算机设备,即是输入设备,又是输出设备的是( )。
A) 键盘 B) 触摸屏 C) 扫描仪 D)投影仪 E) 数字化仪 二.不定项选择题(共10题,每题1.5分,共计15分。多选少选均不得分)。
11. 下列分辨率的显示器显示出的图像,最清晰的是( )。
A) 800*600 B) 1024*768 C) 640*480 D) 1280*1024 E) 800*100012. 下列说法中,哪个(些)是错误的( )。
A)程序是指令的序列,它有三种结构:顺序、分支和循环。
B)数据总线决定了中央处理器CPU所能访问的最大内存空间的大小。
C)中央处理器CPU内部有寄存器组,用来储存数据。
D)不同厂家生产的CPU所能处理的指令集是相同的。
E)数据传输过程中可能会出错,奇偶校验法可以检测出数据中那一为在传输中出了差错。13. CPU访问内存的速度比访问下列哪个(些)存储设备要慢( )。
A)寄存器 B)硬盘 C)软盘 D)高速缓存 E)光盘14. 下列电子邮件地址,哪个(些)是正确的( )。
A)wang@ ( mailto:wang@ ) B) cai@jcc.pc.tool.rf.edu.jp ( mailto:cai@jcc.pc.tool.rf.edu.jp ) C) 162.105.111.22
D) ccf. E)http://www.15. 数字图像文件可以用下列哪个(些)软件来编辑( )。
A)画笔(Paintbrush) B)记事薄(Notepad) C) Photoshop D) WinRAR E)Midisoft16. 下列哪个(些)软件不是操作系统软件的名字( )。
A)WindowsXP B) DOS C) Linux D) OS/2 E) Arch/Info17. 下列哪个(些)不是个人计算机的硬件组成部分( )。
A)主板 B)虚拟内存 C)电源 D)硬盘 E)总线18. 运算试(2008)10-(3723)8 的结果是( )。
A)(-1715)10 B) (5)10 C) (5)16 D) (101)2 E) (3263)819. 已知元素(8,25,14,87,51,90,6,19,20),问这些元素以怎样的顺序进入栈,才能使出栈的顺序满足:8在51前面;90在87的后面;20在14的后面;25在6的前面;19在90的后面。( )。
A)20,6,8,51,90,25,14,19,87
B)51,6,19,20,14,8,87,90,25
C)19,20,90,7,6,25,51,14,87
D)6,25,51,8,20,19,90,87,14
E)25,6,8,51,87,90,19,14,2020. 假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点的度数,下面给出的哪(些)组d 值合理( )。
A){5,4,4,3,1} B){4,2,2,1,1} C){3,3,3,2,2}
D){5,4,3,2,1} E){2,2,2,2,2}三、问题求解(共2题,每题5分,共计10分)1. 无向图G有16条边,有3个4度顶点、4个3度顶点,其余顶点的度均小于3,则G至少_______个顶点。2. 某年级学生共选修6门课程,期末考试前,必须提前将这6门课程考完,每人每天只在下午至多考一门课程,设6门课程为C1,C2,C3,C4,C5,C6,S(Ci)为学习Ci 的学生集合。已知S(Ci)∩S(C6)≠ф,i=1,2,...,5,S(Ci)∩S(Ci+1)≠ф,i=1,2,3,4,S(C5)∩S(C1)≠ф,问至少安排_____天才能考完这6门课程。四.阅读程序(共4题,每题8分,共计32分)
1. program Program1;
var a,b,c,d,sum : longint;
begin
read(a,b,c,d);
a := a mod 23; b := b mod 28; c := c mod 33;
sum := a * 5544 + b * 14421 + c * 1228 - d;
sum := sum + 21252; sum := sum mod 21252;
if (sum = 0 ) then sum := 21252;
writeln(sum);
end.输入:283 102 23 320 输出____________2. program Program2;
const
u : array[1..4] of integer = (0,5,3,1);
v : array[1..4] of integer = (0,7,6,5);
var a,b,c,d,e,f,x,y,z: integer; begin
read(a,b,c,d,e,f);
z := f+ e + d + (c+3) div 4; y := 5 * d + u[c mod 4];
if (b > y) then
begin
z := z + (b - y + 8) div 9;
x := ((b - y + 8) div 9 * 9 -(b - y)) * 4 + 11 * e + v[c mod 4];
end
else
x := (y - b) * 4 + 11 * e + v[c mod 4];
if (a > x) then
z := z + (a - x + 35) div 36;
writeln(z)
end.输入: 4 7 9 20 56 47 输出____________________3. program Program3;
var m,n: integer; mark: Boolean;function test(m,N:integer):integer;
var i,p: integer; flag: boolean;
begin
m := m - 1; i := 0; flag := False;
for p:= 2*N downto (N+1) do
begin
i:= (i+m) mod p;
if (i
begin
test := 0; flag := Ture; Break;
end
end;
if not(flag) then test:=1;
end;begin
read(n); m:=1; Mark := False;
repeat
if (test(m,n)=1) then
begin writeln(m); break; end;
m:= m+1;
until Mrak;
end.输入:7 输出_________ 4. program Program4;var m,n,i,j: integer;
p,w,a,b: array[0..19] of integer;
begin
read(n); m:= 0;
for i:= 0 to n-1 do
begin read(p[i]); b[i]:=1; end;
for i:=0 to n-1 do
begin
if (i>0) then
a[m]:=p[i]-p[i-1]
else
a[m]:=p[i];
m:=m+1;
while ((m>1) and (a[m-1]=0)) do
begin
m:=m-1; b[m]:=1;
end;
if (m>0) then
w[i]:=b[m-1];
else
w[i]:=b[0];
a[m-1]:=a[m-1]-1;
for j:=0 to m-1 do b[j]:=b[j]+1;
while ((m>1) and (a[m-1]=0)) do
begin
m:=m-1; b[m]:=1;
end;
end;
for i:= 0 to n-1 do
begin
write(w[i]); write(' ');
end;
writeln(' ');
end.输入:9
4 6 6 6 6 8 9 9 9 9
输出:____________________五. 完善程序(共2题,第1题每空3分;第2题每空2分。共计28分)。
1. 翻硬币题目描述:
一摞硬币共有m枚,每一枚都是正面朝上。取下最上面的一枚硬币,将它翻面后放回原处。然后取下最上面的2枚硬币,将他们一起翻面后放回原处。在取3枚,取4枚……直至m枚。然后在从这摞硬币最上面的一枚开始,重复刚才的做法。这样一直做下去,直到这摞硬币中每一枚又是正面朝上为止。例如,m为1时,翻两次即可。
输 入:仅有的一个数字是这摞硬币的枚数m ,0< m <1000。
输 出:为了使这摞硬币中的每一枚都是朝正面朝上所必须翻的次数。
输入样例:30
输出样例:899程 序:
program Program1;
var m:integer;
function solve(m: integer):integer;
var i,t,d: integer;
flag: Boolean;
begin
if (m = 1) then
solve := (1)
else begin
d := 2*m+1; t := 2; i := 1; flag := False;
repeat
if (t = 1) then
begin
solve := (2) ; flag := True;
end
else if ( (3) ) then
begin
solve := i*m-1; flag := True;
end
else
t := (4) ;
i:=i+1;
until flag;
end
end;
begin
read(m); if (( (5) ) and (m<1000)) then
writeln( (6) );
end.2. OIM地形题目描述:
二维离散世界有一种地形叫OIM(OI Mountain)。这种山的坡度只能上升('/')或下降('\'),而且两边的山脚都与地平线等高,山上所有地方都不低于地平线.例如:
/\ /\
/ \/\ 是一座OIM;而 / \ 不是。
\/
这个世界的地理学家们为了方便纪录,给OIM所有可能的形状用正整数编好号,而且每个正整数恰好对应一种山形。他们规定,若两座山的宽度不同,则较宽的编号较大;若宽度相同,则比较从左边开始第1个坡度不同的地方,坡度上升的编号较大。以下三座OIM的编号有小到大递增: /\ /\ /\ /\
/ \/\ / \/\/\ / \/ \。显然/\的编号为1。但是地理学家在整理纪录是发觉,查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序,输入编号,能马上输出山形。输 入:一个编号(编号大小不超过600,000,000),
输 出:输入编号所对应的山形,1座山所占行数恰为它的高度,即山顶上不能有多余空行。输入样例:15输出样例: /\ /\
/ \/ \程 序:
program Program2;
const
L:integer =19; SZ: integer =50;
UP: char = '/'; DN: char = '\';
Var
i,nth,x,y,h,e,f:integer;
m: array[0..1,0..38,0..19] of integer;
pic: array[0..49,0..49] of char;
procedure init;
var k,s,a,b,c: integer;
begin
for a:=0 to 1 do
for b:=0 to 2*L do
for c:=0 to L do
m[a,b,c]:=0; m[0,0,0]:=1;
for k:=0 to 2*L-1 do
begin
for s:=1 to L do
begin
m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1];
m[1,k+1,s]:= (1) ;
end;
m[0,k+1,0] :=m[0,k,1]+m[1,k,1];
end;
end;
procedure draw(k,s,nth:integer);
begin
if (k=0) then exit;
if ((nth-m[1,k,s])>=0) then
begin
nth:=nth-m[1,k,s];
if (y>h) then (2) ;
pic[y,x]:=UP; y:=y+1; x:=x+1; draw( (3) );
end
else begin
y:=y - 1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-1,nth);
end;
end;
begin
init;
read(nth);
for e:=0 to SZ-1 do
for f:=0 to SZ-1 do
pic[e,f]:= ' ';
x:=0;
y:=0
h:=0;
i:=0;
while ((nth-m[0,2*i,0])>=0) do
begin
nth:= nth-m[0,2*i,0];
(4) ;
end; draw( (5) );
for i:=h downto x-1 do
begin
for e:=0 to x-1 do
write(pic[i,e]);
writeln(' ');
end;
end. 第十四届全国青少年信息学奥林匹克联赛初赛试题
( 普及组 Pascal语言 二小时完成 )
●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●
一、单项选择题(共20题,每题1.5分。每题有且仅有一个正确答案。)
1.微型计算机中,控制器的基本功能是( )。
A.控制机器各个部件协调工作 B.实现算术运算和逻辑运算
C.获取外部信息 D.存放程序和数据
2.设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
3.在下列关于图灵奖的说法中,不正确的是( )。
A.图灵奖是美国计算机协会于1966年设立的,专门奖励那些对计算机事业作出重要贡献的个人
B.图灵奖有“计算机界诺贝尔奖”之称
C.迄今为止,还没有华裔计算机科学家获此殊荣
D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰 图灵
4.计算机在工作过程中,若突然停电,( )中的信息不会丢失。
A.ROM 和 RAM B.CPU C.ROM D.RAM
5.完全二叉树共有2*N-1个结点,则它的叶节点数是( )。
A.N-1 B.N C.2*N D.2N-1
6.在以下各项中,( )不是操作系统软件。
A.Solaris B.Linux C.Windows Vista D.Sybase
7.设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈S,出栈的序列为b,d,f,e,c,a,则栈S的容量至少应该是( )。
A.6 B.5 C.4 D.3
8.与十进制数28.5625相等的四进制数是( )。
A.123.21 B.131.22 C.130.22 D.130.21
9.设字符串S=”Olympic”,S的非字串的数目是( )。
A.28 B.29 C.16 D.17
10.Web2.0 是近年来互联网的热门概念之一,其核心思想是互动与分享。下列网站中,( )是典型的Web 2.0应用。
A.Sina B.Flicker C.Yahoo D.Google
11.递归过程或函数调用时,处理参数和返回地址,通常使用一种称为( )的数据结构。
A.队列 B.多维数组 C.线性表 D.栈
12.(2008)10+(5B)16的结果是( )。
A.(833)16 B.(2089)10 C.(4163)8 D.(100001100011)2
13.二叉树T,已知其先根遍历是1 2 4 3 5 7 6(数字为节点的编号,下同),中根遍历2 4 1 5 7 3 6,则该二叉树的后根遍历是( )。
A.4 2 5 7 6 3 1 B.4 2 7 5 6 3 1 C.7 4 2 5 6 3 1 D.4 2 7 6 5 3 1
14.将数组{8,23,4,16,77,-5,53,100}中的元素按从小到大的顺序排列,每次可以交换任意两个元素,最少需要交换( )次。
A.4 B.5 C.6 D.7
15.对有序数组{ 5,13,19,21,37,56,64,75,88,92,100}进行二分查找,成功查找元素19的查找长度(比较次数)是( )。
A.1 B.2 C.3 D.4
16 .面向对象程序设计(Object-Oriented Programming)是一种程序设计的方法论,它将对象作为程序的基本单元,将数据和程序封装在对象中,以提高软件的重用性、灵活性和扩展性。下面关于面向对象设计的说法中,不正确的是( )
A.面向对象程序设计通常采用自顶向下设计方法进行设计。
B.面向对象程序设计方法具有继承性(inheritance)、封装性(encapsulation)、多态性 (polymorphism)等几大特点。
C.支持面向对象特性的语言称为面向对象的编程语言,目前较为流行的有C++,JAVA,C# 等。
D.面向对象的程序设计的雏形来自于Simula语言,后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今,SmallTalk语言仍然被视为面向对象语言的基础
17.在32*32点阵的“字库”中,汉字“北”与“京”的字模占用字节数之和是( )。
A.512 B.256 C.384 D.128
18.设T是一棵有n个顶点的树,下列说法不正确的是( )。
A.T有n条边 B.T是连通的 C.T是无环的 D.T有n-1条边
19.下列不属于NOIP竞赛推荐使用的语言环境的是( )。
A.Dev-C++ B.Visual C++ C.Free Pascal D.Lazarus
20.在Pascal程序中,表达式(200 or 10)的值是( )。
A.20 B.1 C.220 D.202
二、问题求解(共2题,每题5分,共计10分)
1.书架上有4本不同的书A、B、C、D。其中A和B是红皮的,C和D是黑皮的。把这4本书摆在书架上,满足所有黑皮的书都排在一起的摆法有_________种。满足A必须比C靠左,所有红皮的书要摆在一起,所有黑皮的书要摆放在一起,共有_________种摆法。
2.有6个城市,任何两个城市之间都有一条道路连接,6个城市两两之间的距离如下表所示,则城市1到城市6的最短距离为__________________。
城市1 城市2 城市3 城市4 城市5 城市6
城市1 0 2 3 1 12 15
城市2 2 0 2 5 3 12
城市3 3 2 0 3 6 5
城市4 1 5 3 0 7 9
城市5 12 3 6 7 0 2
城市6 15 12 5 9 2 0
三、阅读程序写结果(共4题,每题8分,共计32分)
1.VAR i,a,b,c,d:integer;
f:array[0..3] of integer;
BEGIN
for i:=0 to 3 do
read(f[i]);
a:=f[0]+f[1]+f[2]+f[3];
a:=a div f[0];
b:=f[0]+f[2]+f[3];
b:=b div a;
c:=(b*f[1]+a) div f[2];
d:=f[(b div c) mod 4];
if (f[(a+b+c+d) mod 4]>f[2]) then
begin
a:=a+b;
writeln(a);
end else
begin
c:=c+d;
writeln(c);
end;
END.
输入:9 19 29 39
输出:__________________________
2.procedure foo(a,b,c:integer);
begin
if a>b then foo(c,a,b)
else writeln(a,',',b,',',c);
end;
var
a,b,c:integer;
begin
read(a,b,c);
foo(a,b,c);
end.
输入:3 1 2
输出:_________________________
3.type TT=array[0..20]of integer;
prodecure func(var ary:TT;n:integer);
var i,j,x:integer;
begin
i:=0;j:=n-1;
while iwhile (i0) do inc(i);
while (iif iary:=ary[j];
ary[j]:=x;
inc(i);
dec(j);
end;
end;
end;
var
a:TT;
i,m:integer;
begin
m:=10;
for i:=0 to m-1 do
read(a);
func(a,m);
for i:=1 to m-1 do
write(a,' ');
writeln;
end.
输入:5 4 -6 -11 6 -59 22 -6 1 10
输出:___________________________________________
4.procedure solve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer);
var i,root_m:integer;
begin
if spos_f > epos_f then exit;
for i:=spos_m to epos_m do
if first[spos_f]=mid[i] then begin
root_m:=i;
break;
end;
solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1);
solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);
write(first[spos_f]);
end;
var first,mid:string;
len:integer;
begin
readln(len);
readln(first);
readln(mid);
solve(first,1,len,mid,1,len);
writeln;
end.
输入:7
ABDCEGF
BDAGECF
输出:_________________________________
四.完善程序(前四空,每空2.5分,后6空,每空3分,共28分)
1.(字符串替换)给定一个字符串S(S仅包含大小写字母),下面的程序将S中的每个字母用规定的字母替换,并输出S经过替换后的结果。程序的输入是两个字符串,第一个字符串是给定的字符串S,第二个字符串S’由26个字母组成,它是a~z的任一排列,大小写不定,S’规定了每个字母对应的替换字母:S’中的第一个字母是字母A和a的替换字母,即 S中的A用该字母的大写替换,S中的a用该字母的小写替换;S’中的第二个字母是字母B 和b的替换字母,即S中的B用该字母的大写替换,S中的b用该字母的小写替换;… …以此类推。
Var change:string;
Str:string;
Procedure CheckChangeRule;
Var i:integer;
Begin
for i:=1 to 26 do begin
if ____①_____ then
change[i]:=chr(ord(change[i])-ord('A')+ord('a'));
end;
end;
Procedure ChangeString;
Var len,i:integer;
begin
len:=length(str);
for i:=1 to len do begin
if ______②______ then
begin
str[i]:=upcase(change[ord(str[i]-ord('A')+1]);
end;
else
begin
_______④_______
end;
end;
end;
begin
readln(str);
readln(change);
CheckChangeRule;
_______⑤_______
writeln(str);
end.
2.(找第k大的数)给定一个长度为1,000,000的无序正整数序列,以及另一个数n(1≤n≤1000000),然后以类似快速排序的方法找到序列中第n大的数(关于第n大的数:例如序列{1,2,3,4,5,6}中第3大的数是4。)
VAR a:array[1..1000000] of integer;
n,m,ans:integer;
Procedure swap(var a,b:integer);
var t:integer;
begin
if (a<>b) then begin
t:=a; a:=b; b:=t;
end;
end;
function FindKth(left,right,n:integer):integer;
var tmp,value,i,j:integer;
begin if left=right then exit(left);
tmp:=random(right-left)+left;
swap(a[tmp],a[left]);
value:=_____①______;
i:=left; j:=right;
while iwhile (iif ia[i]:=a[j]; inc(i);
end else break;
while (iif ia[j]:=a[i]; dec(j);
end else break;
end;
______④_______
if iif i>n then begin dec(i); exit(_____⑥_____); end;
exit(i);
end;
var i:integer;
begin
randomize;
m:=1000000;
for i:=1 to m do read(a[i]));
read(n);
ans:=FindKth(1,m,n);
writeln(a[ans]);
end.NOIP2008年普及组(Pascal语言)参考答案与评分标准
一、单项选择题:(每题1.5分)
1. A 2. B 3. C 4. C 5. B
6. D 7. C 8. D 9. A 10. B
11. D 12. A 13. B 14. B 15. B
16. A 17. B 18. A 19. B 20. D
二、问题求解:(共2题,每题5分,共计10分)
1.12 4
2.7(1->2->5->6)
三、阅读程序写结果(共4题,每题8分,共计32分)
1. 23
2. 2,3,1
3. 5 4 10 1 6 22 -59 -6 -11 -6
4. DBGEFCA (求树的后序遍历)
四.完善程序 (前4空,每空2.5分,后6空,每空3分,共28分)
(说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不一定上报科学委员会审查)
1. ① (change[i] >= 'A') and (change[i] <= 'Z') (只写(change[i] <= 'Z')也对)
② (str[i] >= 'A') and (str[i] <= 'Z') (只写str[i] <= 'Z'也对)
③ str[i] := change[ord(str[i]) - ord('a') +1];
④ ChangeString;
2. ① a[left]
② a[j] < value (或a[j] <= value)
③ a[i] > value (或a[i] >= value)
④ a[i] := value;
⑤ i,right,n
⑥ FindKth(left, i, n)
衢州信息学奥赛网——.. 第十四届全国青少年信息学奥林匹克联赛初赛试题( 提高组 Pascal语言 二小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项选择题(共10题,每题1.5分,共计15分。每题有且仅有一个正确答案)。 1.在以下各项中,( )不是操作系统软件。A.Solaris B.Linux C.Sybase D.Windows Vista E.Symbian 2.微型计算机中,控制器的基本功能是( )。A.控制机器的各个部件协调工作 B.实现算数运算与逻辑运算 C.存储各种控制信息
D.获取外部信息 E.存放程序和数据 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依次入栈,出栈顺序为b,d,c,f,e,a那么栈容量至少应该是( )。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.栈 9.TCP/IP 是一组构成互联网基础的网络协议,字面上包括两组协议:传输控制协议(TCP)和网际互联协议(IP)。TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务,包括寻址和路由器选择等功能的是()。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)V(C∧DV A) B.(( A∧B)VC)∧ B C.(BVCVD)VD∧A D.A∧(DV 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 4 D.2 4 1 5 7 3 617.面向对象的程序设计(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的最短距离为____________。 城市1城市2城市3城市4城市5城市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920 2.书架上有21本书,编号从1 到 21 从中选4 本,其中每两本的编号都不相邻的选法一共有___________________种。 四、阅读程序写结果(共4题,每题8分,共计32分)。1.var i,a,b,c,d:integer; f:array[0..3] of integer;begin for i:=0 to 3 do read(f[i]); a:=f[0]+f[1]+f[2]+f[3]; a:=a div f[0]; b:=f[0]+f[2]+f[3]; c:=(b*f[1]+a) div f[2]; d:=f[(b div c) mod 4]; if (f[(a+b+c+d) mod 4]>f[2]) then begin a:=a+b; writeln(a) endelsebegin c:=c+d; writeln(c);end;end. 输入: 9 19 29 39输出:_______________________________ 2.procedure foo(a,b,c:integer); begin if a>b then foo(c,a,b)else writeln(a,',',b,',',c)end;var a,b,c:integer;begin readln(a,b,c); foo(a,b,c);end. 输入:2 1 3输出:_________________ 3.procedure f(a,b,c:integer);begin write(a,b,c,'/'); if (a=3)and(b=2)and(c=1) then exit; if (b=ord('A')) and (ord(s[i])<=ord('Z')) then s:=chr(ord(s[i])-ord('A')+ord('a'));for i:=1 to len doif (ord(s[i])b) then begint:=a; a:=b; b:=t;end;end;Function FindKth(left,right,n:integer):integer;Var tmp,value,i,j:integer;begin if left=right then exit(left); tmp:=random(right-left)+left; swap(a[tmp],a[left]); value:=____①_____ i:=left; j:=right;while in then begin dec(j); exit(______⑥________);end; exit(i);end; var i:integer;begin randomize; ans:=-1;m:=5;for i:=1 to m do read(a[i]);read(n);ans:=FindKth(1,m,n);writeln(a[ans]);end. 2.(矩阵中的数字)有一个n*n(1≤n≤5000)的矩阵a,对于1≤ivar n,k,answerx,answery:integer; a:array[1..5000,1..5000] of integer;Procedure FindKPosition;Var I,j:integer;Begin i:=n; j:=n; while j>0 do begin if a[n,j]k do begin while (___②_____) and (i>1) do dec(i); while (___③_____) and (j<=n) do inc(j); end; _______④________ _______⑤________end; var i,j:integer;begin read(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); read(k); FindKPosition; writeln(answerx,' ',answery);end. NOIP2008年提高组(Pascal语言)参考答案与评分标准
一、单项选择题:(每题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; 信息学竞赛普及组初赛模拟试题(二)
(pascal语言)限时2小时完成,满分100分
一、选择题:(共20小题,1-15小题为单选题,每题1分;16-20小题为多选题,每题2分。共25分)
1.对存储器按字节进行编址,若某存储器芯片共有10根地址线的引脚,则该存储器芯片的存储容量为( 。
(A) 512B (B) 1KB (C) 2KB (D)4KB (E)8KB
2.在待排序的数据表已经为有序时,下列排序算法中花费时间反而多的是( 。
(A)堆排序 (B)希尔排序 (C)冒泡排序 (D)快速排序 (E)二分排序
3.某数列有1000个各不相同的单元,由低至高按序排列,现要对该数列进行二分法检索,在最坏的情况下,需要检索( 单元。
(A)1000 (B)10 (C)100 (D)500 (E) 300
4.已知数组a中,每个元素a[i,j]在存储时要占3个字节,设i从1变化到8,j从1变化到10,分配内存实是从地址sa开始连续按行存储分配的。试问:a[5,8]的起始地址为( 。
(A)sa+141 (B)sa+180 (C)sa+222 (D)sa+225 (E)sa+155
5.在pascal语言过程调用时,数值形参得到的是实际参数的( 。
(A) 数值 (B) 地址 (C)值 (D)变量 (E)以上都不是
6.一个24*24点阵的汉字字形信息所占的字节数为( 。
(A) 2 (B) 8 (C) 24 (D) 32 (E) 72
7. 在微机系统中,最基本的输入输出模块BIOS存放在( 中。
(A) RAM (B) ROM (C) 硬盘 (D)寄存器 (E)控制器
8. 十进制算术表达式:3*512+5*64+2*8+1的运算中,用二进制表示为( 。
(A)1011010001 (B) 10110100011 (C) 11101010001 (D) 11110100011 (E)111000
9.设栈S的初始状态为空,现对序列{1,2,3,4,5}在栈S上,依次进行如下操作(从元素1开始,出栈后不再进栈):进栈,出栈,进栈,进栈,出栈,出栈。试问出栈的元素序列是( 。
(A){1,2,3} B) {1,3,2} C) {3,2,1} D) {2,3,1} (E)以上都不对
10.E-mail邮件本质上是一个(
(A)文件 (B)电报 (C)电话 (D)传真 (E)电讯
11.一棵二叉树的高度为h,所有结点的度为0,或为2,则此树最少有( 个结点
(A)2h-1 (B)2h-1 (C)2h+1 (D)h+1 (E)h*h+1
12.无向图G=(V,E),其中V={a,b,c,d,e,f}
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行深度优先遍历,得到的顶点序列正确的是(
(A)a,b,e,c,d,f (B)a,c,f,e,b,d (C)a,e,b,c,f,d (D)a,b,e,d,f,c (E)以上都不对
13.pascal 编译程序是(
(A). 把pascal 源程序转换成可运行的EXE文件的程序
(B). 把pascal 源程序转换成等价的目标码的程序
(C). 生成和修改一个pascal语言源程序的等程序
(D). 把pascal的目标码程序转换成可运行的EXE文件的程序
(E). 生成一个等价的汇编程序
14. 将三封信投到4个邮筒,最多的投法有( )
(A). 种 (B). 种 (C). 种 (D).34种 E.
15. 电子信函(电子邮件)的特点之一是( )。
(A).比邮政信函,电报,电话,传真都更快
(B).在通信双方的计算机之间建立其直接的通信线路后即可快速传递数字信息
(C).采用存储-转发方式在网络上逐步传递信息,不象电话那样直接、及时,但费用低廉
(D).在通信双方的计算机都开机工作的情况下即可快速传递数字信息
16. 以下属于多媒体硬件的是( )
(A).主机 (B).光驱 (C).声卡 (D). 音箱 (E). 超级解霸
17. 正确的二维数组类型说明是( )
(A) type ar2=array[1..5,5..1] of integer;
(B) type ar2=array[1..5] of array[5.1] of integer;
(C) type ar2=array[1..5,1..5] of integer;
(D)type ar2=array[1..5] of array[1..5] of integer
(E)type ar2=array[1..5,1..5] of 0..1
18.下列属于信息处理的是( )
(A)信息加工 (B)信息分类 (C)信息技术 (D)信息采集 (E)信息存储
19.在windows中,最小化一个应用程序窗口后,该程序将( )。
(A)被终止执行 (B) 被暂停执行 (C)被转入后台 (D)继续执行 (E)以上答案都不对
20. 下面的常量说明中,正确的是( )
(A)CONST (B)、CONST (C)、CONST (D)、CONST (E)CONST
t = true b, C = 45 M = 100,15 N = 1 OR 2 a= ’A’
二、问题求解:(第1小题5分,第2-3小题各4分,共13分)
[问题1]: 在所有三位数中,各位数字从高位到低位顺次减小的数共有 个。
[问题2]:"银条"
一位银矿勘探员无力预付3月份的房租。他有一根长31英寸的纯银条,因此他和女房东达成如下协议。他说,他将把银条切成小段。3月份的第一天,他给女房东1英寸长的一段,然后每天给她增加1英寸,以此作为抵押。勘探员预期到3月份的最后一天,他能全数付清租金,而届时女房东将把银条小段全部还给他。3月份有31天,一种办法是把银条切成31段,每段长1英寸。可是这处花很多功夫。勘探员希望既履行协议,又能使银条的分段数目尽量减少。例如,他可以第一天给女房东1英寸的一段,第二天再给1英寸的一段,第三开他取回这两段1英寸的而给她3英寸的一段。假设银条的各段是按照这种方式来回倒换的话,勘探员至少需要把他的银条切成______段?
[问题3]:"换不开的钞票"
钱柜里有1.15美分,一位顾客提出:把1美元的钞票换成硬币,但出纳小姐说换不开,后来这位顾客提出:把50美分的钞票换成硬币,但出纳小姐又说换不开,而实际上,出纳小姐也无法把25美分、10美分、5美分的钞票换成硬币。请问钱柜里到底有哪些硬币?他们分别有多少枚?
答:_________________。
三、写出程序的运行结果:(每小题6分,共30分)1. program text1;
const n=6;m=3;
var i,j,k:integer;
begin
for i:=-n to n do
begin
k:=n-abs(i);
write(' ': 39-k);
for j:=-k to k do
if abs(j)>k-m
then write(n-(i+n)div 2)
else write(' ');
writeln;
end;
end.
输出的结果为:
2. PROGAM text2;
VAR a:ARRAY[1..10] OF Char;
k:Integer; ch:Char;
BEGIN
FOR k:=1 TO 10 DO a[k]:=Chr(Ord('A')+k);
FOR k:=1 TO 10 DO
BEGIN
ch:=a[k];
a[k]:=a[11-k];
a[11-k]:=ch;
END;
FOR k:=1 TO 10 DO Write(a[k]);
Writeln
END.
输出的结果为:
3. program text3(input,output);
Var m,n,p:integer;
x:real;
procedure mm(var m:integer;x:real);
var n:integer;
begin
m:=m+1;
n:=m+1;
x:=n*3;
p:=n;
end;
begin
m:=8;n:=5;p:=3;x:=1.0;
mm(n,x);
writeln (m:5,n:5,p:5,x:6:1);
end.
输出的结果为:
4. program text4;
const n=5;
type ary=array[0..n-1,0..n-1]of integer;
var a:ary;i,j,k:integer;
begin
for i:=0 to n-1 do
for j:=0 to n-1 do a[i,j]:=0;
k:=1;
for i:=1 to n do
for j:=n-1 downto i do
begin
a[j,j-i]:=k;
k:=k+1;
end;
for i:=0 to n-1 do
begin
for j:=0 to n-1 do
write(a[I,j]:4);
writeln;
end;
end.
输出的结果为:
5.program text5(input,output);
var ch:char;
i,n,sum:integer;
begin sum:=0;
read(ch);
case ch of
'A':for i:=4 to 6 do
begin
read(n):
sum:=sum+n
end;
'B':begin read(n);
for i:=1 to n do
begin read(n);sum:=sum+n end;
end;
'C':repeat
read(n);sum:=sum+n
until sum>10;
'D':begin read(n);
while n<=3 do
begin sum:=sum+n;read(n) end
end
end; writeln(sum:4)
end.
当程序运行
(1) 输入 A 4 1 2 3 4 5 6 7 8 9时,其输出为_____________。
(2) 输入 B 4 1 2 3 4 5 6 7 8 9时,其输出为_____________。
(3) 输入 C 4 1 2 3 4 5 6 7 8 9时,其输出为_____________。
(4) 输入 D 4 1 2 3 4 5 6 7 8 9时,其输出为_____________。
四、完善程序(第1题每空2分第2、3题每空3分,共32分)
第1题
孪生素数是指两个相差为2的素数,例如:3和5,5和7,11和13等。
下面程序可输出15对孪生素数,其中函数q判断整数a是否为素数。
program p(output);
var k,n:integer
function q (a:integer):booklean;
var k:integer;
flag:boolean;
begin
flag:___(1)____
k:=2
___(2)____ (k<=a div 2) and flag do
if a mod k=0 then ______(3)_______
else
k:=k+1
q:=flag
end;
begin
n:=0;
k:=2;
repeat
if q(k) and ___(4)___ then
begin
n:=n+1;
writeln(k,k+2)
end;
k:=K+1
until n=5
end.
第二题
已知有类型arr=array[1..16] of string; arr型数组a中存放着从第1届到第16届足球世界杯冠军国家的名字,下面的函数可求出历界世界杯比赛共有几个国家曾获得过世界杯冠军,请填空完成。
Function text2(a:arr):integer;
var k,j,s:integer;
mult:boolean;
begin
___(5)___;
for j:=2 to 16 do
begin
k:=1;
mult:=false;
while not mult and ___(6)___ do
if ___(7)__ then mult:=ture
else k:=k+1;
if not mult then s:=___(8)___
end;
text2:=s
end;
第三题
Fibonacci(裴波那契)数列的规律是:前2个数均为1,从第3个数开始每个数等于它前面两个数之和,即:1,1,2,3,5,8,13,21,34,55,89,144,233,377,...。已知任意一个大于0的整数可以表示为若干个互不相同的fibonacci之数和。
例如:121=89+21+8+3
下面的程序是由键盘输入一个正整数n,输出组成n的互不相同的fibonacci数。
例如:若输入121
则输入121=+89+21+8+3
本程序的算法如下:(n=121为例)
1)寻找小于或等于n的最大的fibonacci数a(例如89),并以a作为组成n的一个数输出。
2)若n≠a则以n-a作为新的任意正整数(例如32),重复步骤1.若n=a,则结束。程序中的函数find返回小于或等于n的最大的fibonacci数。
program text3(input,output);
var n:integer;
function find(n:integer):integer;
var a,b,c:integer;
begin
a:=1; b:=1;
repeat
c:=___(9)___;
a:=b;b:=c;
until b>=n;
if b=n then find:=___(10)___
else find:=___(11)___
end;
procedure p(n:integer);
var a:integer;
begin
a:=find(n);
write('+',a:4);
if a p ___(12)___
end;
begin
readln(n);
write(n:5,'=');
p(n);
writeln
end.
南海信息学竞赛初中组初赛模拟试题参考答案
一、选择题:(本题共20小题,1-15小题为单选题,每题1分;16-20小题为多选题,每题2分。共25分)
题号 1 2 3 4 5 6 7 8 9 10
答案 B D B A B E B C B A
题号 11 12 13 14 15
答案 B D B C C
题号 16 17 18 19 20
答案 ABCD CE ABDE CD AE
二、问题求解:(第1小题3分,第2-3小题各5分,共13分)
[问题1]: 120
[问题2]: 5
[问题3]: 50美分1枚,25美分1枚,10美分4枚,5美分1枚,1美分4枚
三、写出程序的运行结果:(每小题6分,共30分)1、输出结果为: 2、输出结果为:
BCDEFGHIJK
6
6 6 6
5 5 5 5 5
5 5 5 5 5 5
4 4 4 4 4 4
4 4 4 4 4 4
3 3 3 3 3 3
3 3 3 3 3 3
2 2 2 2 2 2
2 2 2 2 2 2
1 1 1 1 1
1 1 1
0
3、输出结果为: 4、输出结果为:
8 6 7 1.0 0 0 0 0 0
4 0 0 0 0
7 3 0 0 0
9 6 2 0 0
10 8 5 1 0
5、当程序运行
(1) 输入 A 4 1 2 3 4 5 6 7 8 9时,其输出为______7_____。
(2) 输入 B 4 1 2 3 4 5 6 7 8 9时,其输出为______10____。
(3) 输入 C 4 1 2 3 4 5 6 7 8 9时,其输出为_______14___。
(4) 输入 D 4 1 2 3 4 5 6 7 8 9时,其输出为________0___。
四、完善程序(第1题每空2分第2、3题每空3分,共32分)
第1题 (1) true
(2) while
(3) flag:=false
(4) F(K+2)=true或F(K+2)
第2题 (5) s:=1
(6) (k (7) a[j]=a[k]
(8) s+1或s+1;或succ(s)
第3题 (9) a+b或b+a
(10) b或c或n
(11) a或a;
(12) n-a