当前位置:首页 >> 学科竞赛 >>

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


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

一、单项选择题(共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确答案) 1. 微机内的存储器的地址是以( A.二进制位 2. B.字长 )编址的。 C.字节 ) 。

D.湿度 ) 。 D.微处理器的型号

下列诸因素中,对微机工作影响最小的是( A.尘土 B.噪声 C.温度

3.

在 24*24 点阵的字库中,汉字“一 ”与“编”的字模占用字节数分别是( A.32、32 B.32、72 C.72、72 ) 。 D.72、32

4.

计算机能直接执行的指令包括两部分,它们是( A.源操作数与目标操作数 C.ASCII 码与汉字代码

B.操作码与操作数 D.数字与字符 ) 。 C.计算机字长 )位二进制代码。 C.12 D.16 D.32 位

5.

在微机中,通用寄存器的位数是 ( A.8 位 B.16 位

6.

在计算机中,ASCII 码是( A.8 B.7

7.

计算机中的数有浮点与定点数两种,其中用浮点数表示的数,通常由( )这两部分 组成。 A.指数与基数 B.尾数与小数 C.阶码与尾数 D.整数与小数 启动计算机引导 DOS 是将操作系统( A.从磁盘调入中央处理器 C.从软盘调入硬盘 ) 。 B.从内存储器调入高速缓冲存储器 D.从系统盘调入内存储器 ) 。

8.

9.

不同的计算机,其指令系统也不相同,这主要取决于 ( A.所用的操作系统 C.所用的 CPU

B.系统的总体结构 D.所用的程序设计语言 )。

10. 在有 N 个叶子节点的哈夫曼树中,其节点总数为( A. 不确定 B. 2N-1 C. 2N+1 D. 2N

二、不定项选择题(共10题,每题1.5分,共计15分。多选或少选均不得分)。 11. 二叉树T的宽度优先遍历序列为A B C D E F G H I, 已知A是C的父结点, D 是G 的父结 点,F 是I 的父结点,树中所有结点的最大深度为3(根结点深度设为0),可知E的父
1

结点可能是( )。 A. A B. B C. C

D. D

E. F

12. 下列外设接口中可以通过无线连接的方式连接设备的是( )。 A. USB 2.0高速版 B. 红外 C. 蓝牙 D. 串口 E. IEEE 802.11g无线网卡

13. 处理器A 每秒处理的指令数是处理器B 的2 倍。某一特定程序P 分别编译为处理器A 和处理器B 的指令,编译结果处理器A 的指令数是处理器B 的4 倍。已知程序P 的算 法时间复杂度为O(n2),如果处理器A执行程序P时能在一小时内完成的输入规模为n,则 处理器B执行程序P时能在一小时内完成的输入规模为( )。 A. 4 * n B. 2 * n C. n D. n / 2 E. n / 4

无论在哪一个处理器上,该程序P的算法复杂度都是一样的,因此,产生影响的主要是 指令数及两个处理器的速度。综合起来看,处理器B有两倍的速度优势,因此,在同样的一 小时内,B可以处理多一倍的数据,即输入数据规模可以是2*n。 14. 下列关于高级语言的说法正确的有( )。 A. Ada 是历史上的第一个高级语言 {1954年,IBM的John Backus和他的研究小组开 始开发FORTRAN(FORRmula TRANslation) ,1957年完成。这是一种适合科学研究使用的 计算机高级语言。} B. Pascal和C都是编译执行的高级语言 C. C++是历史上的第一个支持面向对象的语言 D. 编译器将高级语言程序转变为目标代码 E. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 15. 美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献包括( ) 。 A. 提出理想计算机的数学模型,成为计算机科学的理论基础。 {是图灵提出的} B. 提出存储程序工作原理,对现代电子计算机的发展产生深远影响。 C. 设计出第一台具有存储程序功能的计算机 EDVAC。 D. 采用集成电路作为计算机的主要功能部件。 E. 指出计算机性能将以每两年翻一番的速度向前发展。 16. 下列哪个(些)是 64 位处理器( ) 。 A. Intel Itanium (安腾,64 位处理器) B. Intel Pentium III C. AMD Athlon64 (速龙,64 位的处理器;Sempron:闪龙;Turion:炫龙,双核 64 位) D. AMD Opteron (皓龙,64 位) E. IBM Power 5 (64 位微处理器芯片)

2

17. 下列哪个(些)不是数据库软件的名称( ) 。 A. MySQL B. SQL Server C. Oracle D. Outlook 18. 下列哪个(些)不是计算机的存储设备( ) 。 A. 文件管理器 B. 内存 C. 显卡 D. 硬盘 19. 下列哪个(些)软件属于操作系统软件( ) 。 A. Microsoft Word B. Windows XP C. Foxmail

E. FoxPro

E. U 盘

D. 金山影霸

E. Red Hat Linux

20. 下列说法中正确的有( ) 。 9. CPU 的基本功能就是执行指令。 10. CPU 的主频是指 CPU 在 1 秒内完成的指令周期数, 主频越快的 CPU 速度一定越快。 11. 内部构造不同的 CPU 运行相同的机器语言程序,一定会产生不同的结果。 12. 在一台计算机内部,一个内存地址编码对应唯一的一个内存单元。 13. 数据总线的宽度决定了一次传递数据量的大小,是影响计算机性能的因素之一。 二、问题求解(请在空格处填上答案,每空 5 分,共 10 分) (NOIP1995T) 1. 有标号为 A、B、C、D 和 1、2、3、4 的 8 个球,每两个球装一盒,分装 4 盒。标号为 字母的球与标号为数字的球有着某种一一对应的关系(称为匹配) ,并已知如下条件: ① 匹配的两个球不能在一个盒子内。 ② 2 号匹配的球与 1 号球在一个盒子里。 ③ A 号和 2 号球在一个盒子里。 ④ B 匹配的球和 C 号球在一个盒子里。 ⑤ 3 号匹配的球与 A 号匹配的球在一个盒子里。 ⑥ 4 号是 A 或 B 号球的匹配球。 ⑦ D 号与 1 号或 2 号球匹配。 请写出这四对球匹配的情况。 答: 这四对球匹配的情况为: A 4 B 3 C 1 D 2

1. 2. 在圆周上有 N 个点(N≥6),在任意两个点之间连一条弦,假 设任何 3 条弦在圆的内部都没有公共点,问这些弦彼此相交 能在圆内构成多少个三角形(只要求写出三角形总数的表示 式而无需化简)?(提示:右图是 N=6 的情况,图中所示的 4 个三角形从某种意义上说具有一定的代表性。 ) 答: 可对三角形的顶点是否落在圆周上, 来对三角形进行划分: 三个顶点都落在圆周上,

3

两个顶点落在圆周上,一个顶点落在圆周上,0 个顶点落在圆周上。 ? ?
3 三个顶点落在圆周上:总数为 CN

两个顶点落在圆周上:就是任选 4 个点相连,形成 4 个满足本条件的三角形,故总
4 数为 4* CN

?

一个顶点落在圆周上:就是任选 5 个点相连,形成 5 个满足本条件的三角形,所以
5 总数为 5* CN

?

0 个顶点落在圆周上:就是任选 6 个点相连,形成 1 个满足本条件的三角形,所以
6 总数为 CN

3 4 5 6 因此,总数为 CN ? 4 ? CN ? 5 ? CN ? 6 ? CN

三、阅读程序(共 4 题,每题 8 分,共计 32 分) 1. prgoram chu7_4; var n,k,i:integer; a:array[1..40]of integer; procedure find(x:integer); var s,i1,j1:integer; p:boolean; begin i1 := 0; p := true; while p do {找第 x 大的数} begin i1 := i1 + 1; s := 0; for j1 := 1 to n do if a[j1] > a[i1] then s := s+1; if (s = x-1) then begin writeln(a[i1]); p:=false end; end end;{of procedure} begin readln(n,k); for i:=1 to n do read(a[i]); find(k);
4

find(n-k); end. 输入:10 4 12 34 5 65 67 87 7 90 120 13 输出:67 34 2. program noi_002; var i,j,l,n,k,s,t: integer; b: array[1..10] of 0..9; begin readln(l,n);s:=l;k:=1;t:=l; while s < n do begin k:=k+1; s:=s-t; n:=n-s-1; for i:=1 to 10 do j:=11; while n > 0 do begin j:=j-1; b[j]:=n mod l; n:=n div l end; for i:=10-k+1 to 10 do write(chr(ord('a')+b[i])); end. 输入:4 输出:bbac 3. program noi_004; var i,j,j1,j2,p,q: integer; p1: boolean; b,c: array[1..100] of integer; begin readln(q,p); j:=1; p1:=true; b[j]:=q; j1:=0; while(q>0)and p1 do begin j1:=j1+1; c[j1]:=q*10 div p; q:=q*10-c[j1]*p; if q>0 then begin j2:=1; while (b[j2]<>q) and (j2<=j) do j2:=j2+1; if b[j2]=q then 167 b[i]:=0; t:=t*l; s:=s+t end;

5

begin p1:=false; write(‘{‘); for i:=j2 to j1 do writeln('}') end else end; if q=0 then begin write(‘0.’); for i:=1 to j1 do write(c[i]:1); writeln end; readln end. 输入 输入 4. ①1 ②2 8 7 输出:0.125 输出:0.{285714} begin j:=j+1; b[j]:=q end end {of while} write(c[i]:1); write(‘0.’); write(c[i]:1); for i:=1 to j2-1 do

Program EXP4 (input,output); const n=4; type se=array[1..n*2] of char; var i,j,i1,j1,k,s,t,s1,l,swap:integer; temp :char; a :se; begin for i:=1 to n*2 do read(a[i]); readln; s:=0; t:=0; for i:=1 to n*2 do if a[i]='1' then s:=s+1 else if a[i]='0' then t:=t+1; if (s<>n) or (t<>n) then writeln('error') else begin s1:=0; for i:=1 to 2*n-1 do if a[i]<>a[i+1] then s1:=s1+1; writeln('jamp=',s1); swap:=0; for i:=1 to 2*n-1 do for j:=i+1 to 2*n do if a[i]<>a[j] then begin

6

temp:=a[i];a[i]:=a[j] ;a[j]:=temp; s:=0; for l:=1 to 2*n-1 do if a[l]<>a[l+1] then s:=s+1; if s>swap then begin swap:=s; i1:=i; j1:=j end; temp:=a[i]; a[i]:=a[j]; a[j]:=temp end; if swap>0 then writeln('maxswap=',swap-s1,' i=',i1,' j=',j1) end END. 输入:10101100 输出:jamp=5

maxswap=2 i=6 j=7

四、完善程序(10 个空,前 7 个空每空 2.5 分,后三个空每空 3 分,共 28 分) 1. 问题描述: 将 2n 个 0 和 2n 个 1,排成一个圈。从任一个位置开始,每次按逆时针的方向以长度为 n+1 的单位进行数二进制数。要求给出一种排法,用上面的方法产生出来的 2n+1 个二进制数 都不相同。 例如,当 n=2 时,即 22 个 0 和 22 个 1 排成如下一圈:

比如, 从 A 位置开始, 逆时针方向取三个数 000, 然后再从 B 位置上开始取三个数 001, 接着从 C 开始取三个数 010,…,可以得到 000,001,010,101,011,111,110,100 共 8 个二进制数且都不相同。 程序说明: 以 N=4 为例,即有 16 个 0,16 个 1,数组 A 用以记录 32 个 0,1 的排法,数组 B 统计 二进制数是否已出现过。 程序清单 program noi00; var a : array[1..36] of 0..1;
7

b : array[0..31] of integer; i, j, k, s, p : integer; begin for i := 1 to 36 do a[i] := 0; for i := 28 to 32 do a[i] := 1; p := 1; a[6] := 1; while (p = 1) do begin j := 27; while (a[j]=1) do j := j-1; ( ①A[J]:=1; ) for i := j + 1 to 27 do( ②A[I]:=0; ) for i := 0 to 31 do b[1] := 0; for i := 1 to 32 do begin ( ③S:=0;) for k := i to i + 4 do s := s * 2 + a[k]; ( ④B[S]:=1;) end; s := 0; for i := 0 to 31 do s := s + b[i]; if( end; for i := 1 to 32 do for j := i to i + 4 do write(a[j]); writeln end. 2. 求关键路径 设有一个工程网络如下图表示(无环路的有向图): ⑤S=32 )then p := 0

其中,顶点表示活动,①表示工程开始,⑤表示工程结束(可变,用 N 表示),边上的 数字表示活动延续的时间。 如上图中所示,活动①开始 5 天后活动②才能开始工作,而活动③则要等①、②完成 之后才能开始,即最早也要 7 天后才能工作。

8

在工程网络中,延续时间最长的路径称为关键路径。上图中的关键路径为:①—②—③ —④—⑤共 18 天完成。 关键路径的算法如下: (1)数据结构: r[1..n,1..n] of integer; eet[1..n] et[1..n] 表示活动的延续时间,若无连线,则用-1 表示; 表示活动最早可以开始的时间 表示活动最迟应该开始的时间

关键路径通过点 j,具有如下的性质:eet[j]=et[j]。 (2)约定: 结点的排列已经过拓扑排序,即序号前面的结点会影响序号后面结点的活动。 【程序清单】 program gao7_6; var i,j,n,max,min,w,x,y:integer; r:array[1..20,1..20] of integer; eet,et:array[1..20] of integer; begin readln(n); for i:=1 to n do for j:=1 to n do r[i,j]:=-1; {r[i,j]=-1 表示 i、j 之间无直接关系} readln(x,y,w);{输入从活动 x 到活动 y 的延续时间,以 0 为结束} while x<>0 do begin r[x,y]:=w; ①readln(x,y,w); end; eet[1]:=0; {认为工程从第 0 天开始} for i:=2 to n do begin max:=0; {计算 i 活动的最早开工时间,前面活动 j 的用时 eet[j]加上 j 到 i 的用 时的最大值} for j:=1 to n do if r[j,i]<>-1 then { r[j,i]<>-1 表示 j、i 之间有直接关系} if ②r[j,i]+eet[j]>max then max:=r[j,i]+eet[j]; eet[i]:=max; {i 的最早开工时间} end; ③et[n] := eet[n]; {工程最后结点的最迟结束时间就是工程结束的用时} for i:=n-1 downto 1 do begin min:=10000; {计算 i 的最迟开工时间,前面活动 j 的用时 et[j]减去 i 到 j 的 用时的最小值} for j:=1 to n do if r[i,j]<>-1 then

9

if ④et[j]-r[i,j]<min then min:=et[j] - r[i,j]; et[i]:=min; {i 的最迟开工时间} end; writeln(eet[n]); {“最早开工时间=最迟开工时间”的结点为关键结点} for i:=1 to n -1 do if ⑤eet[i] = et[i] then write(i,'→'); write(n);readln end.

10


相关文章:
全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(十四)new答案_英语考试_外语学习_教育...因特网互联协议 D. 文件传输协议/邮件传输协议 7. Pascal 编译程序的功能是(...
全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(八)new答案_学科竞赛_初中教育_教育专区...( A.8 B.7 7. 计算机中的数有浮点与定点数两种,其中用浮点数表示的数,...
全国青少年信息学奥林匹克联赛初赛练习卷(六)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。...780 E. 60 (8*7!)/(2!*4!) – (5+4+3+2+1)*4 = 780 亦即,...
全国青少年信息学奥林匹克联赛初赛练习卷(七)答案
全国青少年信息学奥林匹克联赛初赛练习卷(七)答案_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档全国青少年信息学奥林匹克联赛初赛练习卷(七)答案...
全国青少年信息学奥林匹克联赛初赛练习卷(一)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_学科竞赛_高中教育_教育专区。全国青少年信息学奥林匹克联赛初赛练习卷()答案 2007. 7 一、单项选择题(15 题,...
全国青少年信息学奥林匹克联赛初赛练习卷(二)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_其它课程_高中教育_教育专区。...(A∨B)∧(C∧D) 7. 8. 9. 10. (3725)8 + (B)16 的运算结果是( ...
全国青少年信息学奥林匹克联赛初赛练习卷(三)答案
全国青少年信息学奥林匹克联赛初赛练习卷()答案_IT认证_资格考试/认证_教育...7 n=4,表示由[a,b,c,d]组成单词,其单词编码如下:{先透过例子找出单词...
全国青少年信息学奥林匹克联赛初赛试题2009-2015
第十五届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 单项...
全国青少年信息学奥林匹克联赛初赛练习卷(九)new答案
全国青少年信息学奥林匹克联赛初赛练习卷(九)new答案_学科竞赛_高中教育_教育专区...(7 分) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B 答: 对...
第十七届全国青少年信息学奥林匹克联赛初赛试题
第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 普及组●● Pascal 语言 两小时完成 )●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一、 单项...
更多相关标签: