全国青少信息学奥林匹克联赛初赛练习卷(十)new答案

1、全国青少年信息学奥林匹克联赛初赛练习卷（十二）答案（普及组 PASCAL 语言 二小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 、单项选择题（ 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确答案）1. 在网络上，若某 台电脑的设备及数据可由其他电脑共享，这台电脑称为（ ）。D. 个人计算机）地址， 该地址共含（）个字节，）。为了避免使用数字，人们经常使A. 主机 B. 服务器 C. 副机2. 连接到 Intern et 上的每台计算机都必须有一个（ 前面若干字节表示（ ），后面若干字节表示（ 用字母代替，这些名字称为（ ）。A. IP 、四、网络地址、计

2、算机地址、网名B. 网络、四、 IP 地址、网内计算机地址、域名C. 网络、不超过十、网页、网址、网名D. IP 、四、网络地址、网内计算机地址、域名3. 产生 100 至 300 之间的随机整数（包含 100 、300 ）的表达式是（）。A. Random（100）+200B. Random（200）+100C. Random（201）+100D. Random（300）4. OSI 七层协议中，最底层的协议是（ ）。A. 会话层 B. 数据链路层 C. 物理层 D. 网络层5. 设x为值大于零的实型变量，在PascaI中，计算x8的表达式为（）。A. In（ 8*（exp（x）B. exp

3、（8*（l nx）C. xA8D. sqr（sqr（sqr（x）*x6. 十进制数 -103 的补码是（ ）。A. 10011001 B. 11100111 C. 10110011D. 000110017. 为了区分汉字与 ASCII码，计算机中汉字编码的最高位为（）。A. 0B. 1C. 2D. 48. 在微型计算机系统中，I/O接口位于（ ）之间。A. CPU 和内存储器B. 外部设备与内存储器C. 总线与输入输出设备D. 主机和输入输出设备9. 在微型计算机中，常用（ ）码实现十进制数与二进制数之间的自动转换。A. BCD 码B. ASCII 码C. 海明码D. 机内码10. 下列关于排

4、序算法的说法中，正确的是()。A. 快速排序就是最快的排序B. 归并排序是稳定的排序C. 选择排序比插入排序好11. 含 5 个结点的不同的二叉树有(A. 22 B. 30 C. 40D. 无论如何，排序的时间复杂度不小于 (NlogN)种。D. 4212. JPG 是一种()的静态图像文件存储格式。A. 有损压缩 B. 无损压缩 C. 不可压缩 D. 以上都正确13. 插入排序是一种简单实用的排序算法， 在对数据进行排序时， 我们可能用二分查找， 对 要插入的元素快速找到在已经排好的元素序列中的位置。 下面的描述中正确的是 ( )。B. 二分查找的时间复杂度为A. 二分查找的时间复杂度为 O

5、(lgN) ，因此排序的时间复杂度为 O(N*lgN)O(N) ，因此排序的时间复杂度为 O(N*lgN)C. 二分查找的时间复杂度为O(lgN) ，排序的时间复杂度不变，为O(N*N)D. 二分查找的时间复杂度为O(N) ，排序的时间复杂度不变，为O(N*N)二分查找的时间复杂度为 O(lgN) ，排序的时间复杂度为 O(N 2)，故答案为 C。14. 某班有 30 个同学报名参加 100、 400、 800 米三个运动项目的比赛。已知有6 人获 100米参赛资格， 8人获 400米参赛资格， 15 人获 800米参赛资格， 且其中有 3人获全部三 项参赛资格，则至少有( )人没有获任何项目

6、参赛资格。A. 5 B. 7 C. 9D. 10设至少有 x 人没有获任何项目的参赛资格。 剩下的 30-3-x 个人必须参加 100、400、800 米，其中有 6-3 人获 100 米的参赛资格， 8-3 人获 400 米的参赛资格， 15-3 人获 800 米的参 赛资格，即 30-3-x=3+5+12 。显然， x=7 。答案： B。15. 如下的叙述中，哪一个是关于数据类型的正确描述？( )A. 是一组值的集合B. 不包含子结构的信息C. 一条信息或是其值属于某个类型的一条记录D. 指一组值的集合以及定义在该集合上的一组操作16. 通信时， 模拟信号也可以用数字信道来传输， 实现模拟

7、信号与数字信号之间转换功能的 是( )。A. D/AB. A/DC. Modem D. Codec通常， 模拟信号要转换成数字信号才能在数字传输系统上进行传输， 模拟信号转换成数 字信号要使用脉码调制技术，即PCM ，经过对模拟信号采样、量化、编码三个步骤，使之变换成数字信号。在接收方，收到数字信号后，再将它还原为原来的模拟信号。这种在发送方将模拟信号变换为数字信号的装置称为编码器(Coder)，在接收方将数字信号变换为模拟信号的装置称为解码器(Decoder)。通常进行的双向通信使用既能编码又能解码的装置，称为编码解码器(Codec)。17.在TCP/IP协议中，TCP和IP分别提供什么服务

8、？(18.A.传输层、C.传输层、逻辑代数式A. AB网络层会话层B.链路层、网络层D.物理层、链路层f=AB+ABC+AB(C+D)，贝U f的简化式子为(B. A+BC. ABCD. ABCD19.设有一个十阶的对称矩阵, 其存储地址为米用压缩的存储方式，1, 每个元素占1个地址空间，则以行序为主存储，a11为第一个元素, a85的的地址为()。20.A. 13B. 33C. 18D. 50当用一个带符号的字节来表示整数(可正可负)时，最小的二进制数是(A.10000000B. 11111111C. 01111111D. 00000000二、问题求解(三小题，每题4分，共12分)1. 某校

9、有学号分别为1, 2, 3,，n的n位学生要去音乐厅听音乐，音乐老师手里有座 位号分别为1, 2, 3,，n的票要分给学生，希望每个学生的座位号与自己的学号都 不相同，请问老师有多少种不同的方案来分配这些票？例如，当n=2时，只有一种方案，n=3时，有2种方案。现对任意的n>1,记F(n)为不同的方案数，请写出 F(n)的递归关系式。答：本题是“错排”问题。禾U用容斥原理，可知错排的方案数为：f(n )=n!(1-1/1!+1/2!-1/3!+(-1)A n1/n!)其对应的递归/递推公式为：f(n) = (n-1) * (f(n-1) + f(n-2)f(1)=0f(2)=12. 以正

10、2n+1 (n>0)边形的顶点为顶点的三角形的集合记为Mn。求：Mn中有多少个锐角三角形？当N=10时，Mn中有多少个两两不全等的三角形。答：(1)设锐角三角形的某个顶点为 V。连接V与O (O为圆心)，将剩下的2n个点分作两半。 左边的点从上到下依次是A1、A2、An,右边的点从上到下依次是B1、B2、Bn。B1B n-1记A=A1, A2,An , B=B1, B2,Bn。以V为顶点的锐角三角形的另外两个顶 点不能同属于 A，若不然，设为 Ai , Aj (l<j)，则/ AjAiV为钝角。同理，不能同属于 B。于是，可以设这个三角形VAiBj。/ AiBjV和/ BjAiV必

11、然都是锐角，因此，只要 / AiVBj为锐角即可。如果i=1,稍加分析可以发现，j的取值范围是n;如果i=2 , j的取值范围是n-1, n;如果l=n , j的取值范围是1 , 2, 3，,n。因此，(i, j)总共有1+2+3+n= n(n+1)/2种不同的取法。V是任意的，有2n+1种取法。每个锐角三角形被重复算了3次，故而此问题的答案就是：n(n+1)/2*(2n+1) / 3 = n(n+1)(2n+1)/6。(2) Mn中有a个等边三角形、b个等腰三角形、c个不等边三角形，那么，a+b+c就 是我们要求的答案。 从2n+1个点中任取3个点有C(2n+1,3)种取法。考察这C(2n+

12、1,3)种取 法：a) 分析等边三角形。 在2n+1个点中，任意确定一个点 V，那么就能唯一确定一个以V为顶点的等边三角形；按照这样计算，位于一个固定位置的等边三角形会计算3次。所以，在C(2n+1,3)种取法中，同一个等边三角形会被计算(2n+1)/3次。b) 分析等腰非等边三角形。 在2n +1个点中，任意确定一个点 V，那么，就能唯一确 定一个以V为顶点的等腰非等边三角形。所以，在 C(2n+1, 3)种取法中，同一个等边三角形 会被计算(2n+1)次。c) 同理，一个不等边三角形会被计算2(2 n+1)次。总的来说，就是(2n+1)/3*a+(2n+1)*b+2(2n+1)*c=C(2

13、n+1,3)(* )然后分分两种情况讨论。1、 (2n+1)是3的倍数。此时，a=1, b=n-1，通过(*)式解出 c=(n2-2n+1)/3，所以2a+b+c=( n +n+1)/3 ;222、(2 n+1)不是 3 的倍数。此时，a=0, b=n,通过(* )式解出 c=( n -2n )/3,故 a+b+c=( n +n)/3; 综合起来，就是(n?+n+1)/3(表示高斯函数)。具体到此题，n=10就是(10*10+10+1)/3=37。答案：37。3. 将n个不同颜色的球 放入k个无标号的盒子中(n>=k,且盒子不允许为空)的方案数为 S(n, k)。例如，当 n=4, k=

14、3 时，S (n, k)=6。当 n=6, k=3 时，S(n, k) = 90。答：将n个不同颜色的球放到 k个无标号的盒子中的方案数可以分为以下两种情况来 讨论：(1) 第n个球单独成堆，此时有S(n-1, k-1)种方案；(2) 第n个球不单独成堆，而是和其他若干个球合成一堆。此时，我们先将前(n-1)个球分成k堆，然后将第n个球插入某一堆中。对于每一种将前(n-1)个球分成k堆的方案，我们都有k种插法，所以此时有k*S(n-1, k)种方案。综上所述，S(n, k)的递推式为：(注意此处采用了递推方法)S(1, 1) = 1S( n, k) = 0 (n < k)S(n, k)

15、= S(n-1, k-1) + k * S(n-1, k) (n >=k)利用递推式，我们可以比较方便地计算出结果。N、7、1231100211031314176511525613190三、阅读程序（共 4题，每题7分，共计28分） 1.program ex12_3_1; varm, n: byte;procedure fen (I, j: byte; s: stri ng);var begink: byte; s1: stri ng;beginif j = 1 the n write In elsefor k := 1 to Ibeginstr(k, s1);fen( I-k, j-e

16、n d;en d;(m, =' , s, i);+ 1 do1, S+S1+ ' +');readl n(m, n); fen(m, n,en d.输入：6 3输出：6 = 1 + 1 + 46 = 1 + 2 + 36 = 1 + 3 + 26 = 1 + 4 + 16 = 2 + 1 + 36 = 3 + 2 + 16 = 4 + 1 + 1 【分析】fen(m-k, n-1) 是从fen(m, n)是一个递归过程，其功能是将m拆成n个数相加的形式,m 中拆分出 k 。2.program ex12_3_2;vara: array2.6 of integer;i, j

17、, m: integer;begin for i := 2 to 6 doai := i + 1;repeatm := 2;for i := 3 to 6 doif am > ai then m := i;am := am + m;m := 1;for i := 2 to 5 dofor j := i+1 to 6 do if ai < aj then m:=0;until m <> 0;write(a2:6);end.输出： 613.program ex12_3_3;const n = 200;varsi, pr: set of 2.n;x, j, m: intege

18、r;beginwriteln( Please input m:); readln(m);si := 2.m; pr := ;x := 2;repeatwhile not(x in si) dox := succ(x);pr := pr + x;j := x;while j <= m dobeginsi := si - j;j ：= j + x;en d;un til si =;j ：= 0;for x := 2 to m doif x in pr the nbeginwrite(x:5);in c(j);if j mod 10 = 0 the n write In;en d;writel

19、nen d.输入：m=30输出：23571113171923294. (此题有问题，不完整) program ex12_3_4;varlink: array1.13 of in teger;coun t, I, pre, n ext: in teger;beginfor I := 1 to 13 do lin ki := I + 1;link13: = 1;pre := 13; n ext := 1; count := 0; repeat un til cou nt = 13;writeln( Last pice:' , next);for I := 1 to 13 do write(

20、li nki:4); en d.四、完善程序(19个空，共30分)1. OIM地形题目描述：二维离散世界有一种地形叫OIM ( 01 Mountain)，这种山的坡度只能上升(7')或下降(''),而且两边的山脚都与地平线等高，山上所有地方都不低于地平线。例如：AA/ V是一座OIM ; 而/ 不是V这个世界的地理学家们为了方便记录，给OIM所有可能的形状用正整数编号，而且每个正整数恰好对应一种山形。他们规定，若两座山的宽度不同，则较宽的编号较大；若宽度相同，则比较从左边开始第1个坡度不同的地方，坡度上升的编号较大。以下3座OIM的编号由小到大递增：A AA A/ V

21、/ VV / V 。显然A的编号为1,但是地理学家在整理记录时发觉，查找编号与山形的对应关系不是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序，输入编号，能马上输出山形。【输入】一个编号（编号大小不超过600,000,000）【输出】输入编号所对应的山形，一座山所占行数恰为它的高度，即山顶上不能有多余空行。【输入样例】15问题：从手工角度来看，本问题的本质是什么？【输出样例】A A 已知和求解的各是什么？该如何下手来分析？ / V 【源程序】program program2;const L: in teger = 19;sz: in teger = 50;up: ch

22、ar =/ 'dn: char =''var i, n th, x, y, h, e, f: in teger;m: array0.1,0.38, 0.19 of integer; m数组的作用是什么？pic: array0.49, 0.49 of char; pic数组的作用是什么？ procedure in it;var k, s, a, b, c: in teger;beginfor a := 0 to 1 dofor b := 0 to 2 * L dofor c := 0 to L doma,b,c := 0;m0,0,0 := 1;for k := 0 to

23、 2 * L-1 do beginfor s := 1 to L do begi nm0,k+1,s := m0,k,s+1 + m1,k,s+1;m1,k+1,s:= m0,k,s-1 + m1,k,s-1;en d;m0,k+1,0 := m0,k,1 + m1,k,1;end;end; of procedure in it procedure draw(k, s, n th: in teger);beginif (k=0) then exit;if (nth - m1,k,s) >= 0) then beginnth := nth - m1,k,s;if (y > h) th

24、e n_ h := y; picy,x := up; y := y + 1; x := x + 1; y 是行，x 是列draw( _ k - 1, s + 1, nth);endelse begi n-1, nth);y := y 1; picy, x := dn; x := x + 1; draw(k-1, sen d;en d;begi n main program in it;read(nth); 读入编号for e := 0 to sz- 1 dofor f := 0 to sz-1 do pice, f:=;x :=();x是源点/左下角的横坐标y :=();y是源点/左卜角的纵坐

25、标h :=(:一 n);h是山的高度i 一 wwhile (nth-m0,2*i,0) >= 0) do beginnth := nth - m0,2*i,0; i := i + 1;end;-1 do begi n-1 dodraw( 2 * i, 0, nth_);for i := h dow nto x for e := 0 to x write(pici, e);writel n( en d;en d.2. 表的操作【问题描述】设有一个表，记为L= (ai, 32,，an),其中：L :表名；ai,32,an为表中的元素；当&为09数字时，表示元素；a为大写字母时，表示是

26、另一个表，但不能循环定义。 例如，下列表的定义是合法的(约定 L是第一个表的表名)：L = (1, 3, K, 8, 0, 4)K = (3, P, 4, H, 7)P = (2, 3)H = (4, 0, 5, 3)【程序要求】当全部表给出之后，求出表中所有元素的最大元素，以及表中全部元素的和。【算法及数据结构简要说明】表用记录类型定义，该记录包含以下两个域：长度(LENGTH );表体(是元素为字符类型的数组ELEMENT );队列用数组BASE表示，队列指针用整型变量FRONT与REAR表示。设计一个字符入队的过程in queue, 一个出队的函数 outqueue。表中最大元素及元素求

27、和均采用递归计算。【程序清单】const maxle n = 100;type list = recordlen gth : in teger;eleme nt: array1.maxle n of char;varmax : in teger;tab no: char;q : arrayprocedure inqueue(q, c); 过程需要二个参数，q为记录类型，c字符类型q.rear := ;q.baseq.rear := c;en d;function outqueue(q); q 为记录类型q.fro nt :=;outqueue := q.baseq.fro nten d;fun

28、ction maxnu mber(c: char): char;var m: char;beginmax := chr(O);for i := 1 to tcen gth dobeginch := tc.eleme nti;if _ then m := maxnumber(ch)else m := ch;if max < m the n max := men d;_-en d;function total (c: char): in teger;var k, i , m : in teger;begink := 0;for i:= 1 to tc.le ngth dobeginch :=

29、 tc.elelme nti;if _ the nm := total (ch);else m := ord (ch) -ord ( 'O'); k := k + men d;total := k;en d;begi n ma in programmax := 36;for tab no :='a' to 'z' do ttab no .le ngth := 0;q.front := 0; q.rear := 0;inq ueue(q, 'L');while (q.fro nt <>q .rear ) dobegint

30、ab no := outqueue(q);write(tab no, =;read In ( s );i := 1;while si <> ' ( ' do i := i+ 1;while si <> ' ) ' dobeginif (si>='a') and (si<='z')thenbeginsi:=chr(ord(si)+ord('a')-ord('a');if (si>='a') and (si<='z') th

31、enbegininc(ttabno.length);ttabno.elementttabno.length := si; inqueue(q, si);end;endelseif (si>='0') andn (si<='9') thenbegininc(ttabno.length);ttabno.elementttabno.length := siend;inc(i)end;edn;write('the max number in table L is:', maxnumber('L');write('tot

32、al is:', total('L')end.3. 最小修路费用【问题描述 】现在政府计划在某个区域内的城市间架设高速公路， 以使任意两个城市间能够直接或间 接到达。现在问怎样修路，才能使得费用最小。【输入文件 】第一行一个整数 n( n <= 100)，表示城市的数目；第二行至第 n+1 行每行两个数 xi、yi(0 <= xi, yi <= 100 )，表示第 i 个城市的坐标(单 位：千米)。【输出 】最小费用(每千米一个单位价格) 。【程序清单 】program ex12_4_3;const maxn=100;typetcity = recordx, y: realend;varc : array1.maxn of tcity;d : arr