当前位置:首页 >> 学科竞赛 >> 全国青少年信息学奥林匹克联赛初赛练习卷(十二)new

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


全国青少年信息学奥林匹克联赛初赛练习卷(十二)
(普及组 PASCAL 语言 二小时完成)
●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●●

一、单项选择题(20 题,每题 1.5 分,共计 30 分。每题有且仅有一个正确答案) 1. 在网络上,若某台电脑的设备及数据可由其他电脑共享,这台电脑称为( A. 主机 2. B.

服务器 C. 副机 D. 个人计算机 )地址,该地址共含( )个字节, ) 。为了避免使用数字,人们经常使 ) 。

连接到 Internet 上的每台计算机都必须有一个( 前面若干字节表示( ) ,后面若干字节表示( 用字母代替,这些名字称为( ) 。 A. IP、四、网络地址、计算机地址、网名 B. 网络、四、IP 地址、网内计算机地址、域名 C. 网络、不超过十、网页、网址、网名 D. IP、四、网络地址、网内计算机地址、域名

3.

产生 100 至 300 之间的随机整数(包含 100、300)的表达式是( A. Random(100)+200 C. Random(201)+100 B. Random(200)+100 D. Random(300) ) 。 C. 物理层

) 。

4.

OSI 七层协议中,最底层的协议是( A. 会话层 B. 数据链路层

D. 网络层

5.

设 x 为值大于零的实型变量,在 Pascal 中,计算 x8 的表达式为( ) 。 A. ln(8*(exp(x)) B. exp(8*(lnx)) ) 。 C. 10110011 D. 00011001 ) 。 C. x^8 D. sqr(sqr(sqr(x)))*x

6.

十进制数-103 的补码是( A. 10011001

B. 11100111

7.

为了区分汉字与 ASCII 码,计算机中汉字编码的最高位为( A. 0 B. 1 C. 2 D. 4 )之间。

8.

在微型计算机系统中,I/O 接口位于( A. CPU 和内存储器 C. 总线与输入输出设备

B. 外部设备与内存储器 D. 主机和输入输出设备 )码实现十进制数与二进制数之间的自动转换。 C. 海明码 D. 机内码

9.

在微型计算机中,常用( A. BCD 码

B. ASCII 码

1

10. 下列关于排序算法的说法中,正确的是( A. 快速排序就是最快的排序 C. 选择排序比插入排序好 11. 含 5 个结点的不同的二叉树有( A. 22 12. JPG 是一种( A. 有损压缩 B. 30 C. 40

) 。

B. 归并排序是稳定的排序 D. 无论如何,排序的时间复杂度不小于(NlogN) )种。 D. 42

)的静态图像文件存储格式。 B. 无损压缩 C. 不可压缩 D. 以上都正确

13. 插入排序是一种简单实用的排序算法,在对数据进行排序时,我们可能用二分查找,对 要插入的元素快速找到在已经排好的元素序列中的位置。 下面的描述中正确的是 ( ) 。 A. 二分查找的时间复杂度为 O(lgN),因此排序的时间复杂度为 O(N*lgN) B. 二分查找的时间复杂度为 O(N),因此排序的时间复杂度为 O(N*lgN) C. 二分查找的时间复杂度为 O(lgN),排序的时间复杂度不变,为 O(N*N) D. 二分查找的时间复杂度为 O(N),排序的时间复杂度不变,为 O(N*N) 14. 某班有 30 个同学报名参加 100、400、800 米三个运动项目的比赛。已知有 6 人获 100 米参赛资格,8 人获 400 米参赛资格,15 人获 800 米参赛资格,且其中有 3 人获全部三 项参赛资格,则至少有( )人没有获任何项目参赛资格。 A. 5 B. 7 C. 9 D. 10 )

15. 如下的叙述中,哪一个是关于数据类型的正确描述?( A. 是一组值的集合 B. 不包含子结构的信息 C. 一条信息或是其值属于某个类型的一条记录 D. 指一组值的集合以及定义在该集合上的一组操作

16. 通信时, ,模拟信号也可以用数字信道来传输,实现模拟信号与数字信号之间转换功能 的是( ) 。 A. D/A B. A/D C. Modem D. Codec )

17. 在 TCP/IP 协议中,TCP 和 IP 分别提供什么服务?( A. 传输层、网络层 C. 传输层、会话层 B. 链路层、网络层 D. 物理层、链路层

18. 逻辑代数式 f=AB+ABC+AB(C+D),则 f 的简化式子为( A. AB B. A+B C. ABC D. ABCD

) 。

19. 设有一个十阶的对称矩阵, 采用压缩的存储方式, 以行序为主存储, a11 为第一个元素,
2

其存储地址为 1,每个元素占 1 个地址空间,则 a85 的的地址为( ) 。 A. 13 B. 33 C. 18 D. 50 ) 。

20. 当用一个带符号的字节来表示整数(可正可负)时,最小的二进制数是( A. 10000000 B. 11111111 C. 01111111 D. 00000000

二、问题求解(三小题,每题 4 分,共 12 分) 1. 某校有学号分别为 1,2,3,…,n 的 n 位学生要去音乐厅听音乐,音乐老师手里有座 位号分别为 1,2,3,…,n 的票要分给学生,希望每个学生的座位号与自己的学号都 不相同,请问老师有多少种不同的方案来分配这些票?例如,当 n=2 时,只有一种方 案,n=3 时,有 2 种方案。现对任意的 n>1,记 F(n)为不同的方案数,请写出 F(n)的递 归关系式。

2.

以正 2n+1(n>0)边形的顶点为顶点的三角形的集合记为 Mn。求: Mn 中有多少个锐角三角形? 当 N=10 时,Mn 中有多少个两两不全等的三角形。

3.

将 n 个不同颜色的球放入 k 无标号的盒子中(n>=k,且盒子不允许为空)的方案数为 S(n, k)。例如,当 n=4,k=3 时,S(n, k)=6。当 n=6,k=3 时,S(n, k) = 。

三、阅读程序(共 4 题,每题 7 分,共计 28 分) 1. program ex12_3_1; var m, n: byte; procedure fen(I, j: byte; s: string); var k: byte; s1: string; begin if j = 1 then write(m, ‘=’, s, i);
3

else for k := 1 to I – j + 1 do begin str(k, s1); fen(I-k, j-1, s+s1+’+’); end; end; begin readln(m, n); fen(m, n, ‘ ‘); end. 输入:6 3 输出:

2. program ex12_3_2; var a: array[2..6] of integer; i, j, m: integer; begin for i := 2 to 6 do a[i] := i + 1; repeat m := 2; for i := 3 to 6 do if a[m] > a[i] then m := i; a[m] := a[m] + m; m := 1; for i := 2 to 5 do for j := i+1 to 6 do if a[i] < a[j] then m:=0; until m <> 0; write(a[2]:6); end. 输出: 3. program ex12_3_3; const n = 200; var si, pr: set of 2..n; x, j, m: integer;

4

begin writeln(‘Please input m: ‘); readln(m); si := [2..m]; pr := []; x := 2; repeat while not(x in si) do x := succ(x); pr := pr + [x]; j := x; while j <= m do begin si := si – [j]; j := j + x; end; until si = []; j := 0; for x := 2 to m do if x in pr then begin write(x:5); inc(j); if j mod 10 = 0 then writeln; end; writeln end. 输入:m=30 输出: 4. program ex12_3_4; var link: array[1..13] of integer; count, I, pre, next: integer; begin for I := 1 to 13 do link[i] := I + 1; link[13] : = 1; pre := 13; next := 1; count := 0; repeat until count = 13; writeln(‘Last pice: ’, next); for I := 1 to 13 do write(link[i]:4); end.

5

四、完善程序(19 个空,共 30 分) 1. OIM 地形 题目描述: 二维离散世界有一种地形叫 OIM(OI Mountain) ,这种山的坡度只能上升(’/’)或下降 (’\’) ,而且两边的山脚都与地平线等高,山上所有地方都不低于地平线。例如: ∧ ∧ / ∨\是一座 OIM; 而 / \ 不是 ∨ 这个世界的地理学家们为了方便记录,给 OIM 所有可能的形状用正整数编号,而且每 个正整数恰好对应一种山形。他们规定,若两座山的宽度不同,则较宽的编号较大;若宽度 相同,则比较从左边开始第 1 个坡度不同的地方,坡度上升的编号较大。以下 3 座 OIM 的 编号由小到大递增: ∧ ∧ ∧ ∧ / ∨\ / ∨∨\ / ∨ \。 显然∧的编号为 1,但是地理学家在整理记录时发觉,查找编号与山形的对应关系不 是很方便。他们希望能快速地从编号得到山的形状。你自告奋勇答应他们写一个程序,输入 编号,能马上输出山形。 【输入】一个编号(编号大小不超过 600,000,000) 【输出】 输入编号所对应的山形, 一座山所占行数恰为它的高度, 即山顶上不能有多余空行。 【输入样例】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;

6

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] := 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 ② ①

pic[y,x] := up; y := y + 1; x := x + 1; draw( ③ 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]; ④
7

);

end; draw( ⑤ );

for i := h downto x – 1 do begin for e := 0 to x – 1 do write(pic[i, e]); writeln(‘ ‘); end; end. 2. 表的操作 【问题描述】 设有一个表,记为 L=(a1, a2, … , an) ,其中: L:表名; a1, a2, …, an 为表中的元素; 当 ai 为 0~9 数字时,表示元素;ai 为大写字母时, 表示是另一个表,但不能循环定义。 例如,下列表的定义是合法的(约定 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 表示。 设计一个字符入队的过程 inqueue,一个出队的函数 outqueue。表中最大元素及元素 求和均采用递归计算。 【程序清单】 const maxlen = 100; type list = record length : integer; element: array[1..maxlen] of char; var max : integer; tabno: char; q : array[] procedure inqueue(q,c); {过程需要二个参数,q 为记录类型,c 字符类型}
8

q.rear := ①

__;

q.base[q.rear] := c; end; function outqueue(q); {q 为记录类型} q.front := ② ; outqueue := q.base[q.front] end; function maxnumber(c: char): char; var m: char; begin max := chr(0); for i := 1 to t[c].length do begin ch := t[c].element[i]; if __③ if end; __④_ end; _ then m := maxnumber(ch) else m := ch; max < m then max := m _

function total (c: char): integer; var k, i , m : integer; begin k := 0; for i:= 1 to t[c].length do begin ch := t[c].elelment[i]; if __⑤_ k := k + m end; total := k; end; begin {main program} max := 36; for tabno := 'a' to 'z' do t[tabno].length := 0; q.front := 0; q.rear := 0; inqueue(q, 'L' ); while (q.front <>q .rear ) do begin _ then m := total (ch); else m := ord (ch) – ord ( '0' );

9

tabno := outqueue(q); write(tabno, ‘=' ); readln ( s ); i := 1; while s[i] <> ' ( ' do i := i+ 1; while s[i] <> ' ) ' do begin if (s[i]>='a') and (s[i]<='z') then begin s[i]:=chr(ord(s[i])+ord('a')-ord('a')); if (s[i]>='a') and (s[i]<='z') then begin inc(t[tabno].length); t[tabno].element[t[tabno].length] := s[i]; inqueue(q, s[i]); end; end else if (s[i]>='0') andn (s[i]<='9') then begin inc(t[tabno].length); t[tabno].element[t[tabno].length] := s[i] end; inc(i) end; edn; write('the max number in table L is:', maxnumber('L')); write('total is:', total('L')) end. 3. 最小修路费用 【问题描述】 现在政府计划在某个区域内的城市间架设高速公路, 以使任意两个城市间能够直接或间 接到达。现在问怎样修路,才能使得费用最小。 【输入文件】 第一行一个整数 n (n <= 100) 表示城市数目; 第二行至第 n+1 行每行两个数 xi, yi (0 <= xi, yi <= 100)表示第 i 个城市的坐标(单位:千 米)。 【输出】 最小费用(每千米一个单位价格) 。 【程序清单】 program ex12_4_3; const maxn=100; type

10

tcity = record x, y : real end; var c : array[1..maxn] of tcity; d : array[1..maxn,1..maxn] of real; p : array[1..maxn] of integer; n, i, j, k : integer; a , min : real; begin readln(n); for i:=1 to n do readln(c[i].x,c[i].y); for i:=1 to n do for j:=1 to n do d[i,j]:=sqrt(sqr(c[i].x-c[j].x)+sqr(c[i].y-c[j].y)); p[1]:=0; for i:=2 to n do ___(4)___ for i:=1 to n-1 do begin min:=1e10; for j:=1 to n do if ___(5)___ then begin min:=d[p[j],j]; ___(6)___ end; a:=a+d[p[k],k]; p[k]:=0; for j:=1 to n do if ___(7)___ then p[j]:=k; end; writeln(a:0:2); end.

11


更多相关文档:

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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_初中教育_教育专区...12. 数字图像文件可以用下列哪个(些)软件来编辑( )。 A) 画笔(Paintbrush) ...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十二)new答案_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛练习卷(十二)答案 (普及组 PASCAL 语言 二小时...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...我们给需 要用到的斜线编号,以 5 阶方阵为例: 11 16 20 23 25 7 12 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new答案_学科竞赛_高中教育_教育...,N*N 个数,并要求构成如下的格式:例: N=4 1 12 11 2 12 16 3 14 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十三)new_学科竞赛_高中教育_教育专区。...,N*N 个数,并要求构成如下的格式:例: 5 N=4 1 12 11 10 N=5 1 16...

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

全国青少年信息学奥林匹克联赛初赛练习卷()new答案_学科竞赛_高中教育_教育专区...最后有: 34 26 15 44 12 +) 23 46 4 0 18 23 46 4 0 18 34 26 ...

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

全国青少年信息学奥林匹克联赛初赛练习卷(十一)new答案_学科竞赛_高中教育_教育...两个十进制数 13 和 14,将它们进行“与”运算,结果为( A. 27 B. 12 C...

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

全国青少年信息学奥林匹克联赛初赛练习卷(一)答案_...(n,m); new(head);q:=head;head^.data:=1;...4 8 12 1 6 11 2 9 15 10 5 3 7 14 the...

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

全国青少年信息学奥林匹克联赛初赛练习卷(二)答案_其它课程_高中教育_教育专区。...E 12. 美籍匈牙利数学家 冯·诺依曼 对计算机科学发展所做出的贡献是: () A...

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

全国青少年信息学奥林匹克联赛初赛练习卷(三)答案_IT认证_资格考试/认证_教育...答:4*3=12(条),3*4=12(条),16*2 – 1212 = 8(条),因其他...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com