2011信息学奥林匹克竞赛初赛模拟试题 (16)

信息学竞赛初赛模拟试题（十六）

（初中组PASCAL语言，两小时完成）

◆◆请将正确答案在答卷上填写，在本试题卷上作答无效◆◆

一、选择题：（选出每题正确的一个答案代码，填在横线上，每题1.5分，共30分）

1、执行下列二进制算术加运算11001001+00100111（）。

A. 11101111

B. 11110000

C. 00000001

D. 10100010

2、假设a1，a2，a3是布尔变量，且值均为True，则下列表达式中值为False的是______

A. NOT a1 AND NOT a2

B. a1 OR a2 AND a3

C. (NOT a1 OR a2)AND (a2 OR a3)

D. False OR a1 AND a2 OR NOT a3

3、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用_____算法。

A.先递归后递推

B. 先递推后递归

C.递归

D.递推

4、表达式8 MOD (2*(5-3*(4*(5 DIV 2))DIV 10))的值是_____

A. 0

B. 1

C. 2

D. 3

5、贪婪法是一种______的算法。

A.不求最优，只求满意

B.只求最优

C.求取全部可行解

D.求取全部最优解

6、称一种语言为低级程序语言是由于它_____。

A.离机器特性近

B.离自然语言近

C.编程难度低

D.通用性强

7、排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素作比较，将其放入已排序序列的正确位置上的方法，称为_____.

A. 归并排序

B. 二分法排序

C. 冒泡排序

D.插入排序

8、若进栈序列为3,5,7,9,进栈过程中可以出栈，则_____不可能是一个出栈序列。

A. 7,5,3,9

B. 9,7,5,3

C.7,5,9,3

D. 9,5,7,3

9、中缀表达式(a-b)*(cd)的后缀表达式是_____.

A. abcd*-

B. ab-cd

C. ab-*cd

D. a-bcd *

10、字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成多少个不同的字符串？_____

A. 5

B. 4

C. 6

D. 1

11、一个字长的二进制位数是_____

A.8

B.16

C.32

D.随计算机系统而不同的

12、当a=1,b=3,c=5,d=4时，执行下面一段程序后，x的值为_____

if(a

else if(a

if(b

else x=3;

else x=6;

else x=7;

A. 1

B.2

C. 3

D. 6

13、若一个存储器的周期为200ns，且每个周期可访问4个字节，则该存储器带宽为____bit/s。

A.20M

B.40M

C.80M

D.160M

14、在WWW页面访问时，浏览器通过网络与该IP地址处的WEB服务器的_____服务端口间建立一条TCP连接。

A. HTML

B. HTTP

C. SMTP

D. DNS

15、MIDI是一种数字音乐的国际标准，MIDI文件存储的____________。

A.不是乐谱而是波形

B.不是波形而指令序列

C.不是指令序列而是波形

D.不是指令序列而是乐谱

16、已知公式：

2 （x=0）

fun（x）= 1 （x=1）

fun（x-1）+x*fun（x-2）（x>1）

则fun(4)的值是_______

A.25

B.30

C.33

D. 28

17、在完全二叉树中，若一个结点是叶结点，则它没_____

A. 左子结点

B. 右子结点

C. 左子结点和右子结点

D. 左子结点、右子结点和兄弟结点

18、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若A[k]是叶子结点,则

k的最小值是______。

A.51

B. 50

C. 49

D. 48

19、已知数组A中，每个元素A[I,J]在存储时要占３个字节，设I从0变化到８，J从１变化到1０，分配内存时是从地址SB开始连续按行分配的．试问：A[4,8]的起始地址为_____．

A. SB+141

B. SB+180

C. SB+142

D. SB+181

20、下面关于图的存储的叙述中正确的是______。

A. 用相邻矩阵法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关。

B. 用相邻矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

C. 用邻接表法存储图，占用的存储空间大小只与图中结点个数有关，而与边数无关。

D. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

二、问题解答：(4+6=10分)

1、将一支铅笔、一枝原子笔和一个橡皮擦分别放入A、B、C三位女孩的笔盒中，每个笔盒只能放

一种文具，且三个笔盒内放的文具都不相同。下列三句叙述中只有一句为真，其余二句为假。

试问哪一句为真？_____

①A的笔盒中放的是铅笔。

②B的笔盒中没有铅笔。

③C的笔盒中没有橡皮擦。

2、小娟喜欢收集布偶，她将红、蓝、黄色的趴趴熊、kitty猫、狗布偶各1只（共9只）排成三行

三列的方阵，然后请她的北北来猜。小娟提示说：

①红色的动物都在第一列。

②黄色的动物都不在第三列。

③kitty猫只能在四个角或正中间。

④趴趴熊只能在第一行最上面二个位置或在第三行最下面一个位置。

第二行最下面一个位置放的是_______颜色的______布偶。

三、看程序写结果：(8+10+12=30分)

1.var x,y:integer;

function gcd(x,y:integer):integer;

var r:integer;

begin

repeat

r:=x mod y;

x:=y;

y:=r;

until r=0;

gcd:=x;

end;

begin

x:=80;y:=98;

writeln(x*y div gcd(x,y));

end.

输出：

2. const n=12;

var i,j:integer;

list:array[0..n] of integer;

begin

for i:=1 to n do read(list[i]);

for i:=2 to n do

begin

list[0]:=list[i];

j:=i-1;

while list[0]

begin

list[j+1]:=list[j];

dec(j);

end;

list[j+1]:=list[0];

end;

for i:=1 to n do write(list[i]:5);

end.

输入：67 98 7823 2332 2323 64 90 -34 121 -98 22 67 输出：

3. var i,j,k,n:integer;

a:array[1..100,1..100] of integer;

begin

readln(n);

k:=1;

i:=1;j:=1;a[i,j]:=1;

while k

begin

if (i=1) and (j mod 2=1) then inc(j)

else if (j=1) and (i mod 2=0) then inc(i)

else if (i+j) mod 2=0 then begin dec(i);inc(j);end

else if (i+j) mod 2=1 then begin inc(i);dec(j);end;

inc(k);a[i,j]:=k;

end;

writeln(i,'/',j);

end.

输入：1999

输出：

四、程序填空：(12+18=30分)

1、一个数如果正好等于其因子之和，就称其为“完数”。例如6的因子是1，2，3，并且6=1+2+3，所以6是一个“完数”。下面的程序可以输出2──n之间的所有完数之和。其中n为2~1000之间的任意整数。请将程序填写完全。

PROGRAM bs1；

V AR a，n，s:Integer；

FUNCTION func(n:Integer)：Boolean；

V AR s，k:Integer；

BEGIN

s:=0；

FOR k:=1 TO ①DO

IF n MOD k=0 THEN s:= ②；

IF ③THEN func:=True

ELSE func:=False

END；

BEGIN

s:=0；Readln(n)；

FOR a:=2 TO n DO

IF func ④THEN s:=s+a；

Writeln(s)

END.

2.本程序的功能是将中缀表示的算术表达式转换成后缀表示。如中缀表达式(A-(B*C+D)*E)/(F+G)的后缀表示为ABC*D+E*-FG+/

为了方便，假定变量名为单个英语字母，运算符只有＋－×/（均为双目运算符，左结合），并假定所提供的算术表达式非空且语法是正确的。另外，中缀表示形式中无空格符，但整个算术表达式以空格符结束。各数组意义如下：

POLISH[] 存储其后缀表示;

s[] 是一个后进先出栈。

函数PRIOR(CHAR)返回符号CHAR的优先级，各符号的优先级如下表示：CHAR PRIOR(CHAR)

* / 4

+ - 3

( 2

) 1

label 10;

var

input:string;

polish,s:array[1..100] of char;

k,p,i:integer;

function prior(ch:char) : integer;

begin

if (ch='*') or (ch='/') then prior:=4;

if (ch='+') or (ch='-') then prior:=3;

if ch='(' then prior:=2;

if ch=')' then prior:=1;

end;

procedure a;

begin

①;

②;

end;

procedure b;

begin

③;

④;

⑤;

end;

begin

input:='(A-(B*C+D)*E)/(F+G)';

k:=0;p:=0;i:=1;

while i<=length(input) do

begin

if (input[i]='+') or (input[i]='-') or (input[i]='*') or (input[i]='/') then

begin

while p<>0 do

begin

if ⑥then b else goto 10 ;

end;

10: a;

end

else if input[i]='(' then

begin

a;

end

else if input[i]=')' then

begin

while s[p]<>'(' do b;

p:=p-1;

end

else

begin

k:=k+1;

polish[k]:=input[i];

end;

i:=i+1;

end;

while p<>0 do b;

writeln(polish);

end.

NOIP2013第十九届信息学奥林匹克竞赛全国联赛初赛普及组C试题

第十九届全国青少年信息学奥林匹克联赛初赛 普及组C语言试题 竞赛时间：2013年10月13日14:30~16:30 选手注意： ●试题纸共有9页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的 一律无效。 ●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项） 1.一个32位整型变量占用（）个字节。 A. 4 B. 8 C. 32 D. 128 2.二进制数11.01在十进制下是（）。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 3.下面的故事与（）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：?从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’? A. 枚举 B. 递归 C. 贪心 D. 分治 4.逻辑表达式（）的值与变量A的真假无关。 A. (A ? B) ? ?A B. (A ? B) ? ?B C. (A ? B) ? (?A ? B) D. (A ? B) ? ?A ? B 5.将（2, 6, 10, 17）分别存储到某个地址区间为0~10的哈希表中，如果哈希函数h(x) = （），将不会产生冲突，其中a mod b表示a除以b的余数。 A. x mod 11 B. x2 mod 11 C. 2x mod 11 D. ?√ ?mod 11，其中?√ ?表示√下取整 6.在十六进制表示法中，字母A相当于十进制中的（）。 A. 9 B. 10 C. 15 D. 16

信息学奥赛NOIP初赛复习知识点

信息学奥赛NOIP初赛复习知识点 1、计算机相关科学家： A：被西方人誉为“计算机之父”的美籍匈牙利科学家、数学家冯·诺依曼于1945年发表了一个 全新的"存储程序通用电子计算机方案"—EDVAC。EDVAC方案提出了著名的“　冯·诺依曼体系结构”理论：（1）采用二进制形式表示数据和指令（2）采用存储程序方式（3）由运算器、存储器、控制器、输 入设备和输出设备五大部件组成计算机系统 B：“图灵机”与“冯·诺伊曼机”齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另 一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。与计算机有关的最高奖项“图灵奖”。 2、与竞赛有关的知识： A：信息学奥赛相关的软件有：anjuta 1.2.2版； Red Hat 9.0 自带了gcc/g++ 3.2.2版； Lazarus 0.9.10版；free pascal编译器 2.0.1版； gdb 6.3版；RHIDE；（turbo pascal淘汰） 3、与计算机系统相关的知识： A：常见的操作系统有：DOS、WIN32、WIN95、WIN98、WIN2000、WINXP、WIN2003、WIN2007、LINUX、VISTA 4、与计算机软件相关的知识：无 5、与计算机硬件相关的知识： A：断电后能保存信息的有：ROM（只读存储器）、硬盘、软盘、光盘、U盘、MP3、MP4等；不能保存的主要是RAM（读写存储器）。 B：CPU又名中央处理器，它可以拆分成运算器、控制器 6、病毒及防火墙： A：防火墙的作用是防止黑客攻击。 7、与编程语言相关的知识： A：1972年PARC发布了Smalltalk的第一个版本。大约在此时，“面向对象”这一术语正式确定。Smalltalk被认为是第一个真正面向对象的语言 B：第一代语言：机器语言（0101001）；第二代语言：20世纪50年代，汇编语言，第三代语言：高级语言、算法语言，如BASIC，FORTRAN，COBOL，PASCAL，C；高级语言的特点是可读性强，编 程方便；第四代语言：非过程化语言；SQL；第五代语言：智能性语言，PROLOG（代表）；还有：LISP，APL，SNOBOL，SIMULA。

最新中小学信息学竞赛活动开展工作总结

中小学信息学竞赛活动开展工作总结 中小学信息学竞赛活动开展工作总结 今年10月下旬，局领导明确中小学生的信息学竞赛由我站负责。我们当时觉得接受这个任务压力重大，这是因为我区的这一块工作与其他县（市、区）相比，差距较大，而且离开明年市赛只有四个多月的时间。当时的情况是邱隘中心小学有一定基础，华泰小学刚刚起步，其余小学都没有开展，就连前几年在这方面开展相对较好的咸祥镇中心小学也正处在停顿状态。我们设想如果经过100分的努力，也只能是刚刚接近三等奖，这在明年竞赛中还是反映不出成绩来。针对上述情况，我们确定了小学突破、初中紧跟的工作措施。具体小结如下： 一、小学生竞赛辅导起动快，成效显著。 1：统一认识、落实措施 我们迅速分别召开了愿意加入本项活动的小学正职校长及负责教学的校级领导会议。会上大家统一了认识，树立了信心，校长们表示一定会按排好工作，落实好切实可行的措施。 2：师生同学、共同进步

我区小学信息学老师多数是中师毕业，在校没有系统学过PASCAL 语言，带学生参加竞赛有较大难度，如果按常规先办教师培训班，学成后再去辅导学生，至少是一年以后的事情了。为了早出成绩，我们采取了师生同学的办法，教师现学现教，一边教一边学。自1月3日将举行***区小学生信息学竞赛，想利用这次比赛，进一步提高我区小学生信息学竞赛水平，赛后还将全区前30名学生集中起来，举办冬令营。 二、初中生竞赛工作方向确定，措施落实。 1：组织比武，了解师能 为了解掌握我区初中信息学教师的知识水平和教学能力，经教育局同意，组织了初中信息学教师信息学竞赛辅导水平比武活动，比武分初赛和复赛（初赛为笔试，笔试成绩不理想），月底将评出一、二、三等奖。 2：确定训点，强力推动 在了解掌握初中信息学教师师能的基础上，并给合小学竞赛活动开展情况，确定初中信息学竞赛培训点，同时出台相关政策，推

信息学奥赛试题

第19届全国青少年信息学（计算机）奥林匹克BASIC 试题说明： 请考生注意，所有试题的答案要求全部做在答题纸上。 一、基础知识单项选择题（共10题，每小题3分，共计30分） 1、存储容量2GB相当于（） A、2000KB B、2000MB C、2048MB D、2048KB 2、输入一个数（可能是小数），再按原样输出，则程序中处理此数的变量最好使用（） A、字符串类型 B、整数类型 C、实数类型 D、数组类型 3、下列关于计算机病毒的说法错误的是（） A、尽量做到使用正版软件，是预防计算机病毒的有效措施。 B、用强效杀毒软件将U盘杀毒后，U盘就再也不会感染病毒了。 C、未知来源的程序很可能携带有计算机病毒。 D、计算机病毒通常需要一定的条件才能被激活。 4、国标码的“中国”二字在计算机内占（）个字节。 A、2 B、4 C、8 D、16 5、在计算机中，ASCⅡ码是( )位二进制代码。 A、8 B、7 C、12 D、16 6、将十进制数2013转换成二进制数是( )。 A、11111011100 B、11111001101 C、11111011101 D、11111101101 7、现有30枚硬币(其中有一枚假币，重量较轻)和一架天平，请问最少需要称几次，才能找出假币( )。 A、3 B、4 C、5 D、6 8、下列计算机设备中，不是输出设备的是（）。 A、显示器 B、音箱 C、打印机 D、扫描仪 9、在windows窗口操作时，能使窗口大小恢复原状的操作是（） A、单击“最小化”按钮 B、单击“关闭”按钮 C、双击窗口标题栏 D、单击“最大化”按钮 10、世界上第一台电子计算机于1946年诞生于美国，它是出于（）的需要。 A、军事 B、工业 C、农业 D、教学二、问题求解（共2题，每小题5分，共计10分） 1、请观察如下形式的等边三角形： 边长为 2 边长为4 当边长为２时，有4个小三角形。 问：当边长为6时，有________个小三角形。 当边长为n时，有________个小三角形。 2、A、B、C三人中一位是工人，一位是教师，一位是律师。已知：C比律师年龄大，A和教师不同岁，B比教师年龄小。问：A、B、C分别是什么身分？ 答：是工人，是教师，是律师。 三、阅读程序写结果（共4题，每小题8分，共计32分） 1、REM Test31 FOR I =1 TO 30 S=S+I\5 NEXT I PRINT S END 本题的运行结果是：( １) 2、REM Test32 FOR I =1 TO 4 PRINT TAB (13-3*I)； N=0 FOR J =1 TO 2*I-1 N=N+1 PRINT N； NEXT J PRINT NEXT I END 本题的运行结果是：( ２)

信息学奥赛基础知识习题(答案版)

信息学奥赛基础知识习题(答案版) 一、选择题（下列各题仅有一个正确答案，请将你认为是正确的答案填在相应的横线上） 1．我们把计算机硬件系统和软件系统总称为 C 。 (A)计算机CPU (B)固 件 (C)计算机系统 (D)微处 理机 2．硬件系统是指 D 。 (A)控制器，器运算 (B)存储器，控制器 (C)接口电路，I/O设备 (D)包括(A)、(B)、(C) 3. 计算机软件系统包括 B 。 A) 操作系统、网络软件 B) 系统软件、应用软件 C) 客户端应用软件、服务器端系统软件 D) 操作系统、应用软件和网络软件4．计算机硬件能直接识别和执行的只有 D 。 (A)高级语言 (B)符号语言 (C)汇编语言 (D)机器语言 5．硬盘工作时应特别注意避免 B 。 (A)噪声 (B)震动 (C)潮 湿 (D)日光 6．计算机中数据的表示形式是 C 。 (A)八进制 (B)十进制 (C)二进 制 (D)十六进制

7．下列四个不同数制表示的数中，数值最大的是 A 。 (A)二进制数11011101 (B)八进制数334 (C)十进制数219 (D)十六进制 数DA 8．Windows 9x操作系统是一个 A 。 (A)单用户多任务操作系统 (B)单用户单任务操 作系统 (C)多用户单任务操作系统 (D)多用户多任务操 作系统 9．局域网中的计算机为了相互通信，必须安装___B__。 （A）调制解调器（B）网卡（C）声卡（D）电视卡 10．域名后缀为edu的主页一般属于__A____。 （A）教育机构（B）军事部门（C）政府部门（D）商业组织 11. 在世界上注册的顶级域名是__A____。 （A）hk（B）cn（C）tw（D） 12．计算机能够自动、准确、快速地按照人们的意图进行运行的最基本思想是（ D ）。 （A）采用超大规模集成电路（B）采用CPU作为中央核心部件 （C）采用操作系统（D）存储程序和程序控制 13．设桌面上已经有某应用程序的图标，要运行该程序，可以 C 。 (A)用鼠标左键单击该图标 (B)用鼠标右键单击该 图标 (C)用鼠标左键双击该图标 (D)用鼠标右键双击该 图标

高中信息技术奥林匹克竞赛试题

信息学基础知识题库 硬件 1．微型计算机的问世是由于（C）的出现。 A. 中小规模集成电路 B. 晶体管电路 C. (超)大规模集成电路 D. 电子管电路2．中央处理器（CPU）能访问的最大存储器容量取决于（A）。 A. 地址总线 B. 数据总线 C. 控制总线 D. 实际内存容量 3．微型计算机中，（C）的存储速度最快。 A. 高速缓存 B. 外存储器 C. 寄存器 D. 内存储器 4．在计算机硬件系统中，cache是（D）存储器。 A. 只读 B. 可编程只读 C. 可擦除可编程只读 D. 高速缓冲 5．若我们说一个微机的CPU是用的PII300，此处的300确切指的是（A）。 A. CPU的住时钟频率 B. CPU产品的系列号 C. 每秒执行300百万条指令 D. 此种CPU允许的最大内存容量 6．计算机主机是由CPU与（D）构成。 A. 控制器 B. 输入输出设备 C. 运算器 D. 内存储器 7．计算机系统总线上传送的信号有（B）。 A. 地址信号与控制信号 B. 数据信号、控制信号与地址信号 C. 控制信号与数据信号 D. 数据信号与地址信号 8．不同类型的存储器组成了多层次结构的存储器体系，按存储器速度又快到慢的排列是（C）。 A. 快存>辅存>主存 B. 外存>主存>辅存 C. 快存>主存>辅存 D. 主存>辅存>外存 9．微机内存储器的地址是按（C）编址的。 A. 二进制位 B. 字长 C. 字节 D. 微处理器的型号 10．在微机中，通用寄存器的位数是（D）。 A. 8位 B. 16位 C. 32位 D. 计算机字长 11．不同的计算机，其指令系统也不同，这主要取决于（C）。 A. 所用的操作系统 B. 系统的总体结构 C. 所用的CPU D. 所用的程序设计语言 12．下列说法中，错误的是（BDE） A. 程序是指令的序列，它有三种结构：顺序、分支和循环 B. 数据总线决定了中央处理器CPU所能访问的最大内存空间的大小 C. 中央处理器CPU内部有寄存器组，用来存储数据 D. 不同厂家生产的CPU所能处理的指令集是相同的 E. 数据传输过程中可能会出错，奇偶校验法可以检测出数据中哪一位在传输中出了错误 13．美籍匈牙利数学家冯·诺依曼对计算机科学发展所作出的贡献是（C）。 A. 提出理想计算机的数学模型，成为计算机科学的理论基础 B. 世界上第一个编写计算机程序的人 C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDV AC D. 采用集成电路作为计算机的主要功能部件 E. 指出计算机性能将以每两年翻一番的速度向前发展 14．CPU访问内存的速度比下列哪个（些）存储器设备要慢。（AD）

信息学奥赛比赛练习题

A类综合习题 1.一种计算机病毒叫黑色星期五，如果当天是13号，又恰好是星期五，就会发作起来毁球计算机的存储系统，试编程找出九十年代中这种病毒可能发作的日期。 2.任意给定一个自然数N，要求M是N的倍数，且它的所有各位数字都是由0或1组成，并要求M尽可能小。 例：N＝3―――＞M＝3*37＝111，N＝31―――＞M＝31*3581＝111011 3．合下面条件的5个正整数： (1)5个数之和为23； (2)从这5个数中选取不同的数作加法，可得1－23中的所有自然数,打印这5个数及选取数组成的1--23的加法式。 4．将数字65535分解成若干个素数之积。 5．由1..9这九个数字组成的九位数（无重复数字）能被11整除，求最大、最小值。 6．某次智力测验，二等奖获得者共三人，以下奖品每人发给两样： ①钢笔②集邮本③影集④日记本⑤圆珠笔⑥象棋 打印各种分配方案及总分配数。 7．个同样种类的零件，已知其中有一个是次品，比正品较轻，仅限用天平称4次，把次品找出来，要求打印每次称量过程。 8．输入N个数字（0－9），然后统计出这组数中相邻两数字组成的数字对出现的次数。 如：0,1,5,9,8,7,2,2,2,3,2,7,8,7,9,6,5,9中可得到： （7,8）数字对出现次数2次，（8,7）数字对出现次数为3次。 9．由M个数字构成一个圆，找出四个相邻的数，使其和为最大、最小。 10．输一个十进制数，将其转换成N进制数（0＜N＜＝16)。 11．读入N，S两个自然数（0＜＝S，N＜＝9），打印相应的数字三角形（其中，S表示确定三角形的第一个数，N表示确定三角形的行数）。 例：当N＝4，S＝3时打印：当N＝4。S＝4时打印： 3{首位数为奇数} {首位数为偶数} 4 4 5 &nb sp; 6 5 6 7 8 9 8 7 9 1 2 3 4 3 2 1 12．如图所示的9*9的矩阵中，除了10个格是空的外，其余的都填上了字符"*"，这10个空的格子组成了一个五角星图案的10个交叉点。 下矩阵为输入（1，5）时的输出 * * * * * * * * * * * * 0 * * * * * * * * * * * * * * * * * * * * * * * * * * * 4 * * 7 * 3 * * 6 * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 * * * 9 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 5 * * * * * * * * * * * * * * * * * * * * * *

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 ? 一、单项选择题（共 15 题，每题 1.5 分，共计 22.5 分；每题有且仅有一个正确选项）? 1. 从( )年开始，NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 ? 2.在 8 位二进制补码中，10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 ? 3.分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB ? 4. 2017年10月1日是星期日，1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 ? 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图，必须删去 G 的( )条边，才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 ? 6. 若某算法的计算时间表示为递推关系式： T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) ? 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d

? 8. 由四个不同的点构成的简单无向连通图的个数是( )。 A. 32 B. 35 C. 38 D. 41 ? 9. 将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 ? 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2，则随着i的增大，f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 ? 11. 设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 ? 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币（质量过轻或质量过重），如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合，使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较，若不等，则它不合格；若相等，则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c ?

noip205信息学奥赛普及组初赛c++试题

2015 年第二十一届全国青少年信息学奥林匹克联赛初赛普及组 C++语言试题竞赛日寸间： 2015 年 10 月 l 1 日 14:30~16:30 选手注意： ?试题纸共有 7 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的一律无效。?不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项) 1.1MB 等于( ) 。 A ．1000 字节 B ．1024 字节 C ． 1000X 1000 字节 D ．1024X 1024 字节 2．在 PC机中， PENTIUM(奔腾)、酷睿、赛扬等是指 ( ) 。 A ．生产厂家名称 B ．硬盘的型号 C ．CPU的型号 D ．显示器的型号 3．操作系统的作用是( ) 。 A ．把源程序译成目标程序 B ．便于进行数据管理 C ．控制和管理系统资源 D ．实现硬件之间的连接 4．在计算机内部用来传送、存贮、加工处理的数据或指令都是以( ) 形式进行的。 A ．二进制码 B ．八进制码 C ．十进制码 D ．智能拼音码 5．下列说法正确的是 ( ) 。 A ． CPU的主要任务是执行数据运算和程序控制 B ．存储器具有记忆能力，其中信息任何时候都不会丢失 C ．两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D ．个人用户只能使用 Wifi 的方式连接到 Internet 6．二进制数 00100100 和 00010100 的和是 ( ) 。 A.00101000 B. 01001001 C. 01000100 D.00111000 7．与二进制小数 0.1 相等的十六进制数是( ) 。 A ． 0.8 B ． 0.4 C ． 0.2 D ． 0.1 8．所谓的“中断”是指 ( ) 。 A ．操作系统随意停止一个程序的运行 B ．当出现需要时， CPU暂时停止当前程序的执行转而执行处理新情况的过程 C ．因停机而停止一个程序的运行 D ．电脑死机 9．计算机病毒是 ( ) 。 A ．通过计算机传播的危害人体健康的一种病毒 B ．人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C ．一种由于计算机元器件老化而产生的对生态环境有害的物质 D ．利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 10． FTP可以用于 ( ) 。 A ．远程传输文件 B ．发送电子邮件 C ．浏览网页 D ．网上聊天 11．下面哪种软件不属于即时通信软件 ( ) 。 A ．QQ B ． MSN C ．微信 D ． P2P 12.6 个顶点的连通图的最小生成树，其边数为 ( ) 。 A ． 6 B ． 5 C ． 7 D ． 4 13. 链表不具备的特点是 ( ) 。 A ．可随机访问任何一个元素 B ．插入、删除操作不需要移动元素 C ．无需事先估计存储空间大小 D ．所需存储空间与存储元素个数成正比 14. 线性表若采用链表存储结构，要求内存中可用存储单元地址( ) 。 A ．必须连续 B ．部分地址必须连续 c ．一定不连续 D ．连续不连续均可 15．今有一空栈 S，对下列待进栈的数据元素序列 a,b ，c， d，e，f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈S 的栈顶元素为 ( ) 。 A． f B ．c C ．a D ． b

信息学奥赛初赛试题(第十六届)

第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一．单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案。） 1.与16进制数 A1.2等值的10进制数是（） A.101.2 B.111.4 C.161.125 D.177.25 2.一个字节（byte）由（）个二进制组成。 A.8 B.16 C.32 D.以上都有可能 3.以下逻辑表达式的值恒为真的是（）。 A.P∨（┓P∧Q）∨(┓P∧┓Q) B.Q∨（┓P∧Q）∨（P∧┓Q） C.P∨Q∨（P∧┓Q）∨（┓P∧Q） D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q) 4.Linux下可执行文件的默认扩展名是( )。 A. exe B. com C. dll D.以上都不是 5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。 A. 100 B. 144 C. 164 D. 196 6.提出“存储程序”的计算机工作原理的是（）。 A. 克劳德?香农 B.戈登?摩尔 C.查尔斯?巴比奇 D.冯?诺依曼 7.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。A. 23 B. 25 C. 37 D. 65 8.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了( )。A.寄存器 B.高速缓存 C.闪存 D.外存 9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。 A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2 10.以下竞赛活动中历史最悠久的是（）。A. NOIP B.NOI C. IOI D. APIO 二．不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数不少于1。多选或少选均不得分）。 1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是( )。A.R1 B.R2 C.R4 D.R5 2. Pascal语言，C语言和C++语言都属于( )。A.高级语言 B.自然语言 C.解释性语言 D.编译性语言

广东信息学竞赛普及组初赛模拟试题

信息学竞赛普及组初赛模拟试题(一) (本试题全部为笔试，满分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.表示计算机的时钟脉冲

NOIP2016信息学奥赛普与组初赛C试题与答案解析较完美版

NOIP2016第二十二届全国青少年信息学奥林匹克联赛初赛 试 题 普及组C++语言 时间：2016 年10 月22 日14:30 ～16:30 竞赛 项） 一、单项选 择题（共20 题，每题 1.5 分，共计30 分；每题有且仅有一个正确选 1．以下不是微软公司出品的软件是( ) 。 A ．Powerpoint B ．Word C.Excel D. Acrobat Reader 2．如果256 种颜色用二进制编码来表示，至少需要( ) 位。 A ．6 B ．7 C ．8 D ．9 3．以下不属于无线通信技术的是( ) 。 A ．蓝牙B．WiFi C ．GPRS D ．以太网 4．以下不是CPU生产厂商的是( ) 。 A.Intel B.AMD C.Microsoft D.IBM 5．以下不是存储设备的是( ) 。 A ．光盘 B ．磁盘 C ．固态硬盘 D ．鼠标 6．如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照C apsLock、字母键A、字母键S ，即 C apsLock、A、S、D、CapsLock、A、S、D、??，屏幕上输出的第81 个 D的顺序循环按键 和字母键 字符是字母( ) 。 A ．A B ．S C ． D D ．a 7．二进制数00101100 和00010101 的和是( ) 。 A.00101000 B.01000001 C.01000100 D.00111000 8．与二进制小数0.1 相等的八进制数是( ) 。 A ．0.8 B ．0.4 C ．0.2 D ．0.1 9．以下是32 位机器和64 位机器的区别的是( ) 。 A．显示器不同B．硬盘大小不同 C．寻址空间不同D．输入法不同 10．以下关于字符串的判定语句中正确的是( ) A．字符串是一种特殊的线性表 B ．串的长度必须大于零 C．字符串不可以用数组来表示 D ．空格字符组成的串就是空串 11．一棵二叉树如右图所示，若采用顺序存储结构，即用一维数组元素存储该二 叉树中的结点（根结点的下标 为i ，则其左孩子位于下标 2i 为1，若某结点的下标 大下标为( ) 。 处、右孩子位于下标 (2i+1) 处），则图中所有结点的最 A.6 B ．10 C ．12 D ．15 12．若有如下程序段，其中s、a、b、c 均己定义为整型变量，且a、c 均己赋值（ c 大于0）。 s=a; for (b=1;b<=c;b++) s=s+1; 则与上述程序段修改 s值的功能等价的赋值语句是( ) 。 A. s=a+b; B. s=a+c; C. s=s+c; D. s=b+c; 13．有以下程序： #include using namespace std; int main() { int k=4,n=0; while(n

信息学竞赛复习材料(一)信息学与名人知识

信息学竞赛复习材料（一）信息学与名人知识 图灵英国科学家，他是计算机人工智能技术的鼻祖。1937年他提出了能思考的计算机——图灵机的概念，推进了计算机理论的发展。图灵机模型是一种抽象计算模型，用来精确定义可计算函数，是实现机器人的最基本的一个理论模型。1950年，艾伦图灵发表题为《计算技能思考吗》的论文，设计了著名的图灵测验，解决了如何判定机器人是否具有同人类相等的智力问题 冯·诺依曼(John Von Neuman)凭他的天才和敏锐，在电脑初创期，提出了现代计算机的理论基础，从而规范和决定了电脑的发展方向。时至今日，我们所有的电脑都叫“冯·诺依曼计算机”，即计算机是由控制器、运算器、存储器、输入设备、输出设备组成的，是对这位数学天才最好的评价。 对于冯·诺依曼来说，人类第一台电脑造了一半时才参与开发，多少有些遗憾。但是，他刚好在那大机器程序存储问题无法解决的关键时刻出现，这使得冯·诺依曼的天才得到淋漓尽致的发挥。他明确指出：一定要彻底实现程序由外存储向内存储的转化，原有的设计必须作修改，经费不够再追加。在冯·诺依曼的影响下，整个研制工作取得了突破性的进展。冯·诺依曼提出了新的改进方案：一是用二进制代替十进制，进一步提高电子元件的运算速度；二是存储程序，即把程序放在计算机内部的存储器中，即把程序本身当作数据来对待。1945年6月，他写了一篇题为《关于离散变量自动电子计算机的草案》的论文，第一次提出了在数字计算机内部的存储器中存放程序的概念，这是所有现代电子计算机的范式，被称为“冯·诺依曼结构”。按这一结构建造的电脑称为存储程序计算机，

又称为通用计算机。时至今日，所有的电脑都逃脱不了冯·诺依曼的掌心，我们所有的电脑，都有一个共同的名字，叫“冯·诺依曼机器”，它超越了品牌、国界、速度和岁月。 摩尔定律与高登·摩尔 当人们不断追逐新款PC时,殊不知这后面有一只无形的大手在推动,那就是摩尔定律,而这著名定律的发明人就是高登·摩尔(Gordon Moore)。 1965年的一天，摩尔顺手拿了把尺子和一张纸，画了一张草图，纵坐标代表不断发展的集成电路，横坐标是时间。他在月份上逐个描点，得到一幅增长的曲线图。这条曲线显示出每24个月，集成电路由于内部晶体管数量的几何级数的增长，而使性能几乎翻倍提高，同时集成电路的价格也恰好减少一倍。后来高登·摩尔把时间调整为18个月。摩尔是在集成电路技术的早期作出结论的，那时候，超大规模集成电路技术还远未出现，所以他在1965年的预言并未引起世人的注意。 高登·摩尔的另一壮举是在1968年与罗伯特·诺伊斯带头率领一群工程师离开仙童公司，成立了一家叫集成电子的公司，简称“Intel”，这就是今日名震世界的英特尔公司。 阿达·奥古斯塔，19世纪诗人拜伦的女儿，数学家。穿孔机程序创始人，建立了循环和子程序概念。为计算程序拟定“算法”，写作的第一份“程序设计流程图”，被珍视为“第一个给计算机写程序的人”。

2019-2020年中学生信息学奥林匹克初赛模拟试题附参考答案

2019-2020 年中学生信息学奥林匹克初赛模拟试题附参考答案 一、选择题(共20题，每题 1.5 分，共计30分。前10 题为单选题；后10题为不定项选择题) 1. 微型计算机的性能主要取决于( )。 A)内存B)主板C)中央处理器D)硬盘 E )显示器 2. 128KB 的存储器用十六进制表示，它的最大的地址码是( ) A)10000 B)EFFF C)1FFFF D)FFFFF E)FFFF 3. 能将高级语言程序转换为目标程序的是( ). A)调试程序B) 解释程序C) 编辑程序D) 编译程序E) 连接程序 4．A=11001010B,B=00001111B,C=01011100B,则A∨B∧C=( )B A)01011110 B)00001111 C)01011100 D)11001110 E)11001010 5. 计算机病毒传染的必要条件是( ) 。 A) 在内存中运行病毒程序B) 对磁盘进行读写操作 C) 在内存中运行含有病毒的可执行程序D) 复制文件E) 删除文件 6. TCP ／IP 协议共有( ) 层协议 A)3 B)4 C)5 D)6 E)7 7.192.168.0.1 是属于( ). A)A 类地址B)B 类地址C)C 类地址D)D 类地址E)E 类地址 8. 对给定的整数序列(54,73,21,35,67,78,63,24,89) 进行从小到大的排序时, 采用快速排序的第一趟扫描的结果是( ). A)(24,21,35,54,67, 78,63,73,89) B)(24,35,21,54,67, 78,63,73,89) C) (24,21,35,54,67, 63,73,78,89) D)(21,24,35,54,63, 67,73,78,89) E)(24,21,35,54,67, 63,73,78,89) 9. 一棵n 个结点的完全二叉树, 则二叉树的高度h 为( ). n log 2 n A) B) log 2 n C) 2D) log 2 n 1 E)2n-1 22 10. 对右图进行广度优先拓扑排序得到的顶点序列正确的是( ). A)1,2,3,4,5,6 B)1,3,2,4,5,6 C)1,3,2,4,6,5 D) 1,2,3,4,6,5 E)1,3,2,4,5,6 11. 下列属于冯.诺依曼计算机模型的核心思想是( ). A) 采用二进制表示数据和指令B) 采用“存储程序”工作方式

第十六届全国青少年信息学奥林匹克联赛初赛试题_提高组(c语言)

第十六届全国青少年信息学奥林匹克联赛初赛试题 （提高组 C 语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一.单项选择题（共10题，每题 1.5分，共计15分。每题有且仅有一个正确选项。） 1.与16进制数A1.2等值的10进制数是（） A.101.2 B.111.4 C.161.125 D.177.25 2.一个字节（byte）由（）个二进制位组成。 A.8 B.16 C.32 D.以上都有可能 3.一下逻辑表达式的值恒为真的是（ A.P∨（┐P∧Q)∨（┐P∧┐Q) C.P∨Q∨(P∧┐Q)∨(┐P∧Q) ） B.Q∨（┐P∧Q)∨(P∨┐Q) D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q) 4.Linux下可执行文件的默认扩展名为（） A.exe https://www.wendangku.net/doc/3217276217.html, C.dll D.都不是 5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。 A.100 B.144 C.164 D.196 6.提出“存储程序”的计算机工作原理的是（）。 A.克劳德·香农 B.戈登·摩尔 C.查尔斯·巴比奇 D.冯·诺依曼 7.前缀表达式“+3*2+5 12”的值是（） A.23 B.25 C.37 D.65 8.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（） A.寄存器 B.高速缓存 C.闪存 D.外存 9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。 A.2k B.2k+1 C.k/2下取整 D.(k+1)/2下取整 10.一下竞赛活动中历史最悠久的是（） A.全国青少年信息学奥林匹克联赛（NOIP）

全国信息学奥林匹克竞赛中级指导教师培训班

全国信息学奥林匹克竞赛中级指导教师培训班 教学大纲 中国计算机学会将定期举办全国信息学奥林匹克中级指导教师培训班，旨在提高各地中学从事信息学奥林匹克培训指导教师的整体水平，从而更好地在中学里开展计算机应用和程序设计的普及教育，为培养高水平的计算机专业人才奠定良好的基础。 培训班将依据《全国青少年信息学奥林匹克联赛（NOIP）大纲》确定教学内容。鉴于培训时间较短（一般在一周左右），教学以传授相关知识为主，学员业务能力的提高主要依靠个人自身的努力。通过培训，应使学员了解参与信息学竞赛必备的知识要点；掌握基本的程序设计、算法和数据结构的有关内容；经过继续努力，可以独立承担NOIP 提高组的培训工作。 培训班还将为从事信息学奥林匹克培训的一线教师提供一个直接交流的平台，交流和探讨各校的培训内容、方法、培训模式和成功的经验，以便推动全国各省市信息学奥林匹克竞赛水平的均衡发展。 二、教学内容 （1）程序设计语言概要 由于学员水平不一，使用的程序设计语言不同，有必要用一定的时间介绍培训中将要使用的程序设计语言的核心内容（条件语句、循环语句、指针、结构、函数（或过程）的定义和引用等）。建议任课教师使用C/C++语言，也可以使用Pascal语言。程序运行环境由任课教师参照NOIP竞赛环境选定。 建议适当介绍如何检验程序的正确性和如何设计测试数据。 （2）算法设计与数据结构基础 （2.1 ）递归回溯与基本搜索方法（递归的基本思想与实现过程，深度优先搜索，n 后问题、0-1背包问题、图的m着色、连续邮资问题、最大团问题等；近几年NOIP相关试题）。 （2.2 ）贪心算法（单源最短路径、最小生成树、哈夫曼编码等）。 （2.3 ）线性结构、图与树的相关问题（链表、堆栈、队列、串、哈希表、树的存贮结构、几类典型的二叉树、树的遍历、图的存贮结构、图的遍历、图的连通性、拓扑排序与关键路径等；近几年NOIP相关试题） （2.4 ）分治算法（二分搜索、棋盘覆盖问题、快速排序、跳马问题） （2.5 ）动态规划（基本思想、0-1背包问题、矩阵连乘问题、最长公共子列、最 优二叉搜索树等；近几年NOIP相关试题） （3）历届NOIP综合性试题分析（适当选择各届联赛（提高组）的最后一题进行分析研究）

(信息学奥赛辅导)排列和组合基础知识

排列与组合基础知识 有关排列与组合的基本理论和公式： 加法原理：做一件事，完成它可以有n 类办法，在第一类办法中有m 1种不同的方法，在第二类中办 法中有m 2种不同的方法，……，在第n 类办法中有m n 种不同方法。那么完成这件事共有 N ＝m 1＋m 2＋…＋m n 种不同的方法，这一原理叫做加法原理。 乘法原理：做一件事，完成它需要分成n 个步骤，做第一步有m 1种不同的方法，做第二步有m 2种 不同的方法，……，做第n 步有m n 种不同的方法，那么完成这件事共有N ＝m 1×m 2×…×m n 种不同的方法，这一原理叫做乘法原理。 公式：阶乘公式!(1)(2) 321n n n n =?-?-??，规定0！＝1； 全排列公式!n n P n = 选排列公式!(1)(2)(1)()! m n n P n n n n m n m =---+=-、m m m n n m P C P = 圆排列：n 个不同元素不分首位围成一个圆圈达到圆排列，则排列数为： !(1)!n n n =- 组合数公式(1)(2)(1)!!!()! m m n n m m P n n n n m n C P m m n m ---+===-、规定01n C = m n m n n C C -=、11m m m n n n C C C -+=+、0122n n n n n n C C C C ++++=） 提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。 （2）书写方式：r n P 记为P （n,r ） ；r n C 记为C （n,r ）。 加法原理例题：图1中从A 点走到B 点共有多少种方法？（答案：4＋2＋3＝9） 乘法原理例题：图2中从A 点走到B 点共有多少种方法？（答案：4×6＝24） 加法原理与乘法原理综合：图3、图4中从A 走到B 共有多少种方法？（答案：28、42） A B 图1 A B 图2

高中信息学奥林匹克竞赛各种问题求解试题及参考答案集锦

高中信息学竞赛各种问题求解试题及 答案 第1题(5分)，将n个不同颜色的球放人k个无标号的盒子中( n>=k，且盒子不允许为空)的方案数 为S(n，k)，例如：n=4，k=3时，S(n，k)=6。当n=6，k=3时，S(n，k)=________。 答案：0 k < n S(n,k)= 1 k = 1 S(n-1,k-1)+k*S(n-1,k) n >= k >= 2 第2题(5分)，有5本不同的数学书分给5个男同学，有4本不同的英语书分给4个女同学，将全部书 收回来后再从新发给他们，与原方案都不相同的方案有________种。 答案： 5!*4!+D(5)*D(4)=1140480 其中：D(n)=(n-1)*(D(n-1)+D(n-2)) (n > 2) D(1)=0 D(2)=1 第3题(6分)，把三角形各边分成n等分，过每一分点分别做各边的平行线，得到一些由三角形的边 和这些平行线所组成的平行四边形。n为已知整数，能组成_______个平行四边形。 答案： 3*C(n+2,4) 第4题(6分)，由a，b，c3个不同的数字组成一个N 位数，要求不出现两个a相邻，也不出现两个b 相邻，这样的N位数的个数为AN，用AN-1和AN-2表示AN的关系式为：AN＝_______________。 答案： AN= 2*AN-1+AN-2 第5题(6分)，在m*n的棋盘上，每个方格(单位正方形，即边长为1的正方形)的顶点称为格点。以格点 为顶点的多边形称为格点多边形。若设格点凸N边形面积的最小值为gn，格点凸N边形内部(非顶点的)格点的个数的最小值为fn，则gn和fn的关系式为： gn=___________。 答案： Gn= fn+N/2-1 ( N >= 3 ) 第6题(4分)，编号为1到13的纸牌顺时针排成一 圈，有人从编号为1的牌从数字1开始顺时针数下去， 1、2、3、…、20、21、…，一圈又一圈。问：当数到数字N 时，所在纸牌的编号为多少? 答案： 1+(N-1) mod 13 第7题(8分)，有位小同学喜欢在方阵中填数字，规则 是按下图示例从右上角开始，按斜线填数字， 碰到边界就重新。显然，数字1在坐标(1，5)位置，数字 25在坐标(5，1)位置。后来这位小朋友想知道， 对于N阶的方阵，随机取一个位置(x，y)，并规定x≤y，问 这个位置上应该填的数字是多少?5阶方阵的 示例图如下： 11 7 4 2 1 16 12 8 5 3 20 17 13 9 6 23 21 18 14 10 25 24 22 19 15 答案： (N-y+x)*(N-y+x-1)/2+x 第8题(5分)，设有质量为1、3、9、27、81、…3n g... 的砝码各一枚，如果砝码允许放在天平的两边， 则用它们来称物体的质量，最多可称出1g到3n+3n/2g之间 的所有质量，如n=4时，可称出18到121g之间的 所有质量；当物体质量为M=14时，有14+9+3+1=27，即天 平一端放M=14g的物体和9g、3g、1g的砝码，另一 端放27g的砝码，即可称出M的质量。当M=518g时，请 你写出称出该物体的质量的方法，并用上述所示的 等式来表示。 答案： 518+243+3+1= 729+27+9 第9题(7分)，在圆周上有N个点(N>=6)，在任意两个 点之间连一条弦，假设任何3条弦在圆的内部 都没有公共点，问这些弦彼此相交能在圆内构成多少个三 角形(只要求写出三角形总数的表示式而无需化 简)? 提示：下图是N=6的情况，图中所示的4个三角形从 某种意义上说具有一定的代表性。 答案： C(N,3)+4*C(N,4)+5*C(N,5)+6*C(N,6) 第10题(6分)，用1个或多个互不相同的正整数之和 表示1～511之间的所有整数 ①至少要多少个不同的正整数_________________; ②这些正整数是_______________ 答案： ①9 ②1,2,4,6,16,32,64,128,256 第11题(7分)，在有m行n列格子的棋盘内，一枚棋 子从棋盘的左上角格子沿上、下、左、右方向行走， 最后走到棋盘的右下角格子。该棋子走过的格子数为奇数 的充分必要条件是________________ 答案：m+n为偶数 完善程序试题及其答案 第1题(14分)以下程序是将一组整数按从小到大的顺 序排列。排序的方法是将长度为n的数a分为两个长度分 别为(n div 2)与(n-n div 2)的子数组a1，a2。然后递归调用排 序过程，将a1，a2分别排序，最后将a1，a2归并成数组 a。例如a=(3，1，2，4)，那么a1=(3，1)，a2=(2，4)。调用 排序过程将a1，a2排序，得到a1=(1，3)，a2=(2，4)，然 后进行合并排序。 从键盘输入数的长度n以及n个整数，存在数组a中，调 用子过程sort进行排序，最后输 出排序结果。 program wsh； const maxn=100；． 各种问题 1