第一篇：高中信息技术 全国青少年奥林匹克联赛教案 排序算法
全国青少年信息学奥林匹克联赛
排序算法
一、插入排序(Insertion Sort)
1.基本思想：
每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2.排序过程： 【示例】：
[初始关键字] [49] 38 65 97 76 13 27 49 J=2(38)[38 49] 65 97 76 13 27 49 J=3(65)[38 49 65] 97 76 13 27 49 J=4(97)[38 49 65 97] 76 13 27 49 J=5(76)[38 49 65 76 97] 13 27 49 J=6(13)[13 38 49 65 76 97] 27 49 J=7(27)[13 27 38 49 65 76 97] 49 J=8(49)[13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType);//对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I];J := I1 end R[J + 1] := R[0];//插入R[I] // end End;//InsertSort //
二、选择排序 1.基本思想：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。2.排序过程： 【示例】：
初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97 Procedure SelectSort(Var R : FileType);//对R[1..N]进行直接选择排序 // Begin for I := 1 To N1趟选择排序// begin K := I;For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]// begin If R[J] < R[K] Then K := J end;If K <> I Then //交换R[I]和R[K] // begin Temp := R[I];R[I] := R[K];R[K] := Temp;end;end End.//SelectSort //
三、冒泡排序(BubbleSort)1.基本思想：
两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2.排序过程：
设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。【示例】：
13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType)//从下往上扫描的起泡排序// Begin For I := 1 To N-1 Do //做N-1趟排序// begin NoSwap := True;//置未排序的标志// For J := N1 //从右向左扫描，查找第1个小于 X的元素// If I < J Then //已找到R[J] 〈X// begin R[I] := R[J];//相当于交换R[I]和R[J]// I := I + 1 end;While(R[I] <= X)And(I < J)Do I := I + 1 //从左向右扫描，查找第1个大于 X的元素/// end;If I < J Then //已找到R[I] > X // begin R[J] := R[I];//相当于交换R[I]和R[J]// J := J-1 end Until I = J;R[I] := X //基准X已被最终定位// End;//Parttion // Procedure QuickSort(Var R :FileType;S,T: Integer);//对R[S..T]快速排序// Begin If S < T Then //当R[S..T]为空或只有一个元素是无需排序// begin Partion(R, S, T, I);//对R[S..T]做划分// QuickSort(R, S, I-1);//递归处理左区间R[S,I-1]// QuickSort(R, I+1,T);//递归处理右区间R[I+1..T] // end;End.//QuickSort//
五、堆排序(Heap Sort)1.基本思想：
堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
2.堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：
Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])
堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。3.排序过程：
堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。
【示例】：对关键字序列42，13，91，23，24，16，05，88建堆 Procedure Sift(Var R :FileType;I, M : Integer);//在数组R[I..M]中调用R[I]，使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1 <=M时)均是堆// Begin X := R[I];J := 2*I;//若J <=M, R[J]是R[I]的左孩子// While J <= M Do //若当前被调整结点R[I]有左孩子R[J]// begin If(J < M)And R[J].Key < R[J+1].Key Then J := J + 1 //令J指向关键字较大的右孩子// //J指向R[I]的左、右孩子中关键字较大者// If X.Key < R[J].Key Then //孩子结点关键字较大// begin R[I] := R[J];//将R[J]换到双亲位置上// I := J;J := 2*I //继续以R[J]为当前被调整结点往下层调整// end;6
Else Exit //调整完毕，退出循环// end R[I] := X;//将最初被调整的结点放入正确位置// End;//Sift// Procedure HeapSort(Var R : FileType);//对R[1..N]进行堆排序// Begin
For I := N Div Downto 1 Do //建立初始堆//
Sift(R, I , N)
For I := N Downto 2 do //进行N-1趟排序//
begin
T := R[1];R[1] := R[I];R[I] := T;//将当前堆顶记录和堆中最后一个记录交换//
Sift(R, 1, I-1)//将R[1..I-1]重成堆//
end End;//HeapSort//
六、几种排序算法的比较和选择
1.选取排序方法需要考虑的因素：(1)待排序的元素数目n；(2)元素本身信息量的大小；(3)关键字的结构及其分布情况；(4)语言工具的条件，辅助空间的大小等。2.小结：
(1)若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。
(2)若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4)在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n 7
个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O(nlog2n)的时间。(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。
第二篇：高中信息技术 全国青少年奥林匹克联赛教案 枚举法
信息学奥赛中的基本算法(枚举法)
枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
采用枚举算法解题的基本思路：
（1）确定枚举对象、枚举范围和判定条件；（2）一一枚举可能的解，验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。
枚举算法应用
例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？
算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。
下面是解这个百鸡问题的程序 var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do{枚举所有可能的解} if(x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);{验证可能的解，并输出符合题目要求的解} end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（x,y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，请看下面的程序： var x,y,z:integer;begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y;if(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x,'y=',y,'z=',z);end;end.未经优化的程序循环了101 次，时间复杂度为O(n)；优化后的程序只循环了
2（102*101/2）次，时间复杂度为O(n)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。
在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：
3例
2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.例如:三个三位数192,384,576满足以上条件.(NOIP1998pj)算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：
for a:=1 to 9 do for b:=1 to 9 do ………
for i:=1 to 9 do
９这样下去，枚举次数就有9次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，３穷举的范围就减少为９，在细节上再进一步优化，枚举范围就更少了。程序如下： var t,x:integer;s,st:string;c:char;begin for x:=123 to 321 do{枚举所有可能的解} begin t:=0;str(x,st);{把整数x转化为字符串，存放在st中} str(x*2,s);st:=st+s;str(x*3,s);st:=st+s;for c:='1' to '9' do{枚举9个字符，判断是否都在st中} if pos(c,st)<>0 then inc(t)else break;{如果不在st中，则退出循环} if t=9 then writeln(x,' ',x*2,' ',x*3);end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果，我们再看看下面的例子。例３ 一元三次方程求解(noip2001tg)
32问题描述 有形如：ax+bx+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1 样例 输入：1-5-4 20 输出：-2.00 2.00 5.00 算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍 2 （-10000<=x<=10000），再以根为枚举对象，枚举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。 有的同学在比赛中是这样做 var k:integer;a,b,c,d,x :real;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' ');end;end.用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。 这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？ 看到这里大家可能有点迷惑了。 在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用 32错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax+bx+cx+d 32中，所得的结果也就不一定等于0，因此用原方程ax+bx+cx+d=0作为判断条件是不准确的。 32我们换一个角度来思考问题，设f(x)=ax+bx+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)<0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，哪么就说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<0)和(f(x-0.005)=0)作为判定条件。为了 32程序设计的方便，我们设计一个函数f(x)计算ax+bx+cx+d的值，程序如下： {$N+} var k:integer;a,b,c,d,x:extended; 32function f(x:extended):extended;{计算ax+bx+cx+d的值} begin f:=((a*x+b)*x+c)*x+d;end;begin read(a,b,c,d);for k:=-10000 to 10000 do begin x:=k/100;if(f(x-0.005)*f(x+0.005)<0)or(f(x-0.005)=0)then write(x:0:2,' ');{若x两端的函数值异号或x-0.005刚好是方程的根，则确定x为方程的根} end;end.用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调 试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。 全国青少年信息学奥林匹克联赛 目录 高考加分和保送 联赛命题宗旨 普及的内容 竞赛形式和成绩评定 试题的知识范围 全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces简称NOIP)自1995年至今已举办16次。每年由中国计算机学会统一组织。NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。获得提高组复赛一等奖的选手即可免高考，而通过大学的保送生考试直接被录取。 高考加分和保送 NOIP的部分一等奖具有保送名校或者高考加分(分数的多少视该校自主招生考试结果而定)的资格。NOIP的部分一等奖有参加省队选拔赛的资格，省队的选手可以参加NOI，NOI获奖选手有保送资格。 联赛命题宗旨 全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。 竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。 普及的内容 ．计算机的基本组成； ．计算机操作系统使用（windows等）； ．计算机工作的基本原理； ．计算机程序设计的基本方法； ．至少一门高级程序设计语言； ．程序设计中常用的数据结构。 普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些本质和核心的东西有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。 对学生的能力培养注重 ．想象力与创造力； ．对问题的理解和分析能力； ．数学能力和逻辑思维能力； ．对客观问题和主观思维的口头和书面表达能力； ．人文精神。包括与人的沟通和理解能力，团队精神与合作能力，恒心和毅力，审美能力等。 竞赛形式和成绩评定 联赛分两个年龄组：初中组和高中组(普及组和提高组)。每组竞赛分两轮：初试和复试。 ．初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Basic（2005年被取消）、C/C++或Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的第二个星期六下午 2:30-4:30举行。 ．复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Basic（2005年后被取消）、Pascal、C或C++。各省市竞赛的等第奖在复试的优胜者中产生。时间为 3小时。只进行一试，约在当年的11 月的第三个周六进行。 试题形式 每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。 * 初试：初试全部为笔试，满分100分。试题由四部分组成： 1、选择题：共20题，每题1．5分，共30分。每题有4个备选方案。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。 2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。 3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。 4、程序完善题：共 2题，第一题10分，共4空，每空2.5分；第二题18分，共6空，每空3分。两题共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。 （2009年普及组试题为第一题5空，每空3分，第二题前三空每空3分，后两空每空2分） *复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）、数据范围（数据限制条件）。测试时，测试程序为每道题提供了5~10组测试数据，考生程序每答对一组得10~20 分；累计分即为该道题的得分。 试题的知识范围 考试内容主要包括：计算机发展史、计算机组成、计算机基本原理、计算机程序设计、计算机日常应用等。要求考生掌握至少一门高级程序设计语言（详见竞赛大纲）。为了保持竞赛内容的相对连续性，试题涵盖的知识点和题型至少60％应出现在普及类的参考书目中，其余内容可能超出该范围。 为了考核学生的基础知识、综合应用能力，激发学生的求知欲和创新思维，体现“与时俱进”的特点，竞赛题型在保持大纲相对稳定、优秀学生可能接受和理解的基础上，按照下述趋势适当变化 1、增大与课内知识结合的紧密度； 2、增大解题方法的多样性和灵活程度； 3、增大开放性试题的比例。 试题的知识范围具体如下： 一．初赛内容与要求： A．计算机的基本常识： 1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化） 2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式） 3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构） 4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理） 5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点） 6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）） 7．信息技术的新发展、新特点、新应用等。 B．计算机的基本操作： 1.Windows和LINUX的基本操作知识 2.互联网的基本使用常识（网上浏览、搜索和查询等） 3.常用的工具软件使用（文字编辑、电子邮件收发等） C．数据结构： 1．程序语言中基本数据类型(字符、整数、长整数、浮点) 2.浮点运算中的精度和数值比较 3．一维数组（串）与线性表 4．记录类型（PASCAL）/ 结构类型（C） D．程序设计： 1．结构化程序设计的基本概念 2．阅读理解程序的基本能力 3．具有将简单问题抽象成适合计算机解决的模型的基本能力 4．具有针对模型设计简单算法的基本能力 5．程序流程描述（自然语言/伪码/NS图/其他） 6．程序设计语言（PASCAL/C/C++，2003仍允许BASIC） E．基本算法处理： 1．初等算法（计数、统计、数学运算等） 2．排序算法（冒泡法、插入排序、合并排序、快速排序） 3．查找（顺序查找、二分法） 4．回溯算法 二、复赛内容与要求： 在初赛的内容上增加以下内容： A．数据结构： 1．指针类型 2．多维数组 3．单链表及循环链表 4．二叉树 5．文件操作（从文本文件中读入数据，并输出到文本文件中） B．程序设计 1．算法的实现能力 2．程序调试基本能力 3．设计测试数据的基本能力 4．程序的时间复杂度和空间复杂度的估计 C．算法处理 1．离散数学知识的应用（如排列组合、简单图论、数理逻辑） 2．分治思想 3．模拟法 4．贪心法 5．简单搜索算法（深度优先 广度优先）搜索中的剪枝 6．动态规划的思想及基本算法 评测环境 NOIP2010比赛环境规范依照使用Linux平台、统一编译器、提供多种集成开发环境选择的原则制定。 NOIP2010的比赛环境中，操作系统平台选择Linux；在固定的操作系统平台下，对应不同的语言，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。 在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。 以下是NOIP2010比赛环境要求的详细描述： 使用Linux操作系统平台： （1）Linux操作系统必须使用NOI linux,基于ubuntu开发； （2）Pascal语言，必须使用Free Pascal 2.0.4版本作为编译器； （3）C语言，必须使用gcc 3.2.2作为编译器； （4）C++语言，必须使用g++ 3.2.2作为编译器。 第十四届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言 二小时完成） ●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 一、单项选择题（共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.栈 E.存放程序和数据 A.Solaris B.Linux C.Sybase D.Windows Vista 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(100001100011)2 16.二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。）D.）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.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.输入：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 s:string;i,j,len,k:integer;begin read(s);len:=length(s);for i:=1 to len do if(ord(s[i])>= ord('A'))and(ord(s[i])<= ord('Z'))then s[i] := chr(ord(s[i])-ord('A')+ ord('a'));for i:=1 to len do if(ord(s[i]) 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 i if i 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<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵a中的一个数字k，找出k所在的行列（注意：输入数据保证矩阵中的数各不相同）。 var 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 then break;dec(j);end;① while a[i,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. 第十三届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言 二小时完成） ● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。） 1．在以下各项中，（）不是CPU的组成部分。A．控制器 B．运算器 C．寄存器 D．主板 2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。A．二叉树 B．多叉树 C．哈希表 D．二维表 3．在下列各项中，只有（）不是计算机存储容量的常用单位。A．Byte B．KB C．UB D．TB 4．ASCII码的含义是（）。 A．二→十进制转换码 B．美国信息交换标准代码 C．数字的二进制编码 D．计算机可处理字符的唯一编码 5．一个完整的计算机系统应包括（）。 A．系统硬件和系统软件 B．硬件系统和软件系统 C．主机和外部设备 D．主机、键盘、显示器和辅助存储器 6．IT的含义是（）。 A．通信技术 B．信息技术 C．网络技术 D．信息学 7．LAN的含义是（）。 A．因特网 B．局域网 C．广域网 D．城域网 8．冗余数据是指可以由其它数据导出的数据。例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致。例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（）。A．应该在数据库中消除一切冗余数据 B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据 C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验 D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据 9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A．gcc B．g++ C．Turbo C D．Free Pascal 10．以下断电后仍能保存数据的有（）。 A．硬盘 B．高速缓存 C．显存 D．RAM 11．在下列关于计算机语言的说法中，正确的有（）。A．高级语言比汇编语言更高级，是因为它的程序的运行效率更高 B．随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台 C．高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上 D．C是一种面向对象的高级计算机语言 12．近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（）。 A．在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D．对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用 13．一个无法靠自身的控制终止的循环成为“死循环”，例如，在C语言程序中，语句“while(1)printf(“*”);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。A．不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查 B．有些编译系统可以检测出死循环 C．死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D．死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的 14．在Pascal语言中，表达式（23 or 2 xor 5）的值是（）。A．18 B．1 C．23 D．32 15．在Pascal语言中，判断整数a等于0或b等于0或c等于0的正确的条件表达式是（）。A．not((a<>0)or(b<>0)or(c<>0))B．not((a<>0)and(b<>0)and(c<>0))C．not((a=0)and(b=0))or(c<>0)D．(a=0)and(b=0)and(c=0) 16．地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（）。 A．2 4 3 6 5 7 B．2 4 1 2 5 7 C．2 4 3 1 7 6 D．2 4 3 6 7 5 17．与十进制数1770对应的八进制数是（）。 A．3350 B．3351 C．3352 D．3540 18．设A=B=True，C=D=False，一下逻辑运算表达式值为假的有（）。A．(﹁A∧B)∨(C∧D∨A) B．﹁(((A∧B)∨C)∧D)C．A∧(B∨C∨D)∨D D．(A∧(D∨C))∧B 19．(2070)16 +(34)8 的结果是（）。A．（8332）10 B．（208A）16 C．（100000000110）2 D．(20212)8 20．已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（）。 A．4 6 5 2 7 3 1 B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7 D．4 6 5 3 1 7 2 二、问题求解（共2题，每题5分，共计10分）。 1、（子集划分）将n个数（1，2，…，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=______________。（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。） 2、（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？___________ B A 三、阅读程序写结果（共4题，每题8分，共计32分。） 1、program j301;var i,a,b,c,x,y:integer; p:array[0..4] of integer;begin y:=20; for i:=0 to 4 do read(p); readln; a:=(p[0]+p[1])+(p[2]+p[3]+p[4])div 7; b:=p[0]+p[1] div((p[2]+p[3])div p[4]); c:=p[0]*p[1] div p[2]; x:=a+b-p[(p[3]+3)mod 4]; if(x>10) then y:=y+(b*100-a)div(p[p[4] mod 3]*5) else y:=y+20+(b*100-c)div(p[p[4] mod 3]*5); writeln(x,',',y);end.{注：本例中，给定的输入数据可以避免分母为0或数组元素下表越界。} 输入：6 6 5 5 3 输出：______________________ 2、program j302;var a,b:integer;var x,y:^integer;procedure fun(a,b:integer);var k:integer;begin k:=a;a:=b;b:=k;end;begin a:=3;b:=6; x:=@a;y:=@b; fun(x^,y^); writeln(a,',',b);end.输出：_______________________________ 3、program j303;var a1:array[1..50] of integer;var i,j,t,t2,n,n2:integer;begin n:=50; for i:=1 to n do a1:=0; n2:=round(sqrt(n)); for i:=2 to n2 do if(a1=0)then begin t2:=n div i; for j:=2 to t2 do a1[i*j]:=1; end; t:=0; for i:=2 to n do if(a1=0)then begin write(i:4);inc(t); if(t mod 10=0)then writeln; end; writeln;end.输出：_____________________________________________ _____________________________________________ 4、Program j304;Type str1=string[100]; Str2=string[200];Var S1:str1;s2:str2;Function isalpha(c:char):Boolean;Var i:integer;Begin i:=ord(c); if((i>=65)and(i<=90))or((i>=97)and(i<=122))then isalpha:=true else isalpha:=false;end;function isdigit(c:char):Boolean;var i:integer;begin i:=ord(c);if(i>=48)and(i<=57)then isdigit:=true else isdigit:=false;end;procedure expand(s1:str1;var s2:str2);var i,j:integer;a,b,c:char;begin j:=1;c:=char(1);i:=0; while(i<=ord(s1[0]))do begin inc(i);c:=s1; if c='-' then begin {1} a:=s1[i-1];b:=s1[i+1]; if(isalpha(a)and isalpha(b))or(isdigit(a)and isdigit(b))then begin dec(j); while(ord(upcase(a)) begin s2[j]:=a;inc(j);inc(a);end; end else begin s2[j]:=c;inc(j);end;end{1} else begin s2[j]:=c;inc(j);end;end;s2[0]:=char(j-2);end;begin readln(s1);expand(s1,s2);writeln(s2);end.输入：wer2345d-h454-82qqq 输出：__________________________ 四、完善程序（前4空，每空2.5分，后6空，每空3分，共28分）。 1、（求字符的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1终止程序。 请将程序补充完整。Program j401;type str1=string[100];var line:str1;kz:integer;procedure reverse(var s:str1);var I,j:integer;t:char;begin i:=1;j:=length(s); while(i t:=s;s:=s[j];s[j]:=t; ;; end;end;begin writeln(„continue?-1 for end.‟); readln(kz); while()do begin readln(line); ; writeln(line); writeln(„continue?-1 for end.‟); readln(kz); end;end.2 3 3 2-1 1 3 4 1 1 5 4 4 5 5 2、（棋盘覆盖问题）在一个2k×2 k个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为-1的方格），称之为特殊方格。现用L型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是（4 k-1）/3。在下表给出的一个覆盖方案中，k=2，相同的3各数字构成一个纸片。 下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。 Program j402;type arr1=array[1..65] of integer; arr2=array[1..65] of arr1;var board:arr2;tile:integer;size,dr,dc:integer;procedure chessboard(tr,tc:integer;dr,dc:integer;var size:integer);var t,s:integer;begin if(size=1)then; t:=tile;inc(tile); s:=size div 2; if then chessboard(tr,tc,dr,dc,s)else begin board[tr+s-1]:=t;;end;if(dr else begin board[tr+s-1][tc+s]:=t; ;end;if(dr>=tr+s)and(dc board[tr+s][tc+s]:=t; ;end;if(dr>=tr+s)and(dc>=tc+s)then chessboard(tr+s,tc+s,dr,dc,s)else begin board[tr+s][tc+s]:=t;;end;end;procedure prt1(n:integer);var I,j:integer;begin for I:=1 to n do begin for j:=1 to n do write(board[j]:3); writeln;end;end;begin writeln(„input size(4/8/16/64):‟); readln(size);writeln(„input the position of special block(x,y):‟); readln(dr,dc);board[dr][dc]:=-1; tile:=1;chessboard(1,1,dr,dc,size);prt1(size);end.NOIP2007年普及组（Pascal语言）参考答案与评分标准 一、单项选择题：（每题1.5分） 题号 2 3 4 5 6 7 8 9 10 答案 D D C B B B B C C A 题号 12 13 14 15 16 17 18 19 20 答案 C A A A B D C D A A 二、问题求解：（每题 5分） 1．90 2．210 三、阅读程序写结果 1.15, 46（对1个数给4分，无逗号扣1分）2.3, 6 3.2 3 5 7 11 13 17 19 23 29 47 4.wer2345defgh45456782qqq 四、完善程序(前4空（①--④），每空2.5分，后6空（⑤--⑩），每空3分) （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1．① inc(i)或i:=i+1 ② dec(j)或 j:=j-1 ③ kz<>-1 ④ reverse(line)2.⑤ exit ⑥(dr第三篇：全国青少年信息学奥林匹克联赛
第四篇：第十四届全国青少年信息学(计算机)奥林匹克分区联赛初赛汇总
第五篇：第十三届全国青少年信息学奥林匹克联赛初赛试题
点击咨询 