广东省高一信息技术历年NOIP初赛试题07Word文档下载推荐.docx
- 文档编号:8167046
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:11
- 大小:48.36KB
广东省高一信息技术历年NOIP初赛试题07Word文档下载推荐.docx
《广东省高一信息技术历年NOIP初赛试题07Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《广东省高一信息技术历年NOIP初赛试题07Word文档下载推荐.docx(11页珍藏版)》请在冰点文库上搜索。
A.SA+141 B.SA+180 C.SA+222 D.SA+225
14.不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是( )
A.快存/辅存/主存 B.外存/主存/辅存C.快存/主存/辅存D.主存/辅存/外存
15.某数列有1000个各不相同的单元,由低至高按序排列;
现要对该数列进行二分法检索(binary-search),在最坏的情况下,需检视( )个单元。
A.1000 B.10 C.100 D.500
16.请仔细阅读下列程序段:
Var
a:
array[1..3,1..4]ofinteger;
b:
array[1..4,1..3]ofinteger;
x,y:
integer;
begin
forx:
=1to3do
fory:
=1to4do
a[x,y]:
=x-y;
=4downto1do
b[x,y]:
=a[y,x];
writeln(b[3,2]);
end.
上列程序段的正确输出是( )
A.-1 B.-2 C.-3 D.–4
17.线性表若采用链表存储结构,要求内存中可用存储单元地址( )
A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续不连续均可
18.下列叙述中,正确的是( )
A.线性表的线性存储结构优于链表存储结构
B.队列的操作方式是先进后出
C.栈的操作方式是先进先出
D.二维数组是指它的每个数据元素为一个线性表的线性表
19.电线上停着两种鸟(A,B),可以看出两只相邻的鸟就将电线分为了一个线段。
这些线段可分为两类;
一类是两端的小鸟相同;
另一类则是两端的小鸟不相同。
已知:
电线两个顶点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是( )。
A.奇数 B.偶数 C.可奇可偶 D.数目固定
20.一个文本屏幕有25列及80行,屏幕的左上角以(1,1)表示,而右下角则以(80,25)表示,屏幕上每一个字符占用两字节(byte),整个屏幕则以线性方式存储在电脑的存储器内,由内屏幕左上角开始,位移为0,然后逐列存储。
求位于屏幕(X,Y)的第一个字节的位移是( )
A.(Y*80+X)*2-1 B.((Y-1)*80+X-1)*2C.(Y*80+X-1)*2 D.((Y-1)*80+X)*2-1
二.问题求解(每题6分,共12分)
1.已知,按中序遍历二叉树的结果为:
abc
问:
有多少种不同形态的二叉树可以得到这一遍历结果,并画出这些二叉树。
2.设有一个共有n级的楼梯,某人每步可走1级,也可走2级,也可走3级,用递推公式给出某人从底层开始走完全部楼梯的走法。
例如:
当n=3时,共有4种走法,即1+1+1,1+2,2+1,3。
三.阅读程序,并写出正确的运行结果(每题10分,共20分)
1.PROGRAMNOI_003;
CONST
N=7;
M=6;
VAR
I,J,X0,Y0,X1,Y1,X2,Y2:
INTEGER;
D:
REAL;
P:
BOOLEAN;
G:
ARRAY[0..N,0..M]OF0..1;
FUNCTIONDISP(X1,Y1,X2,Y2:
INTEGER):
REAL;
BEGIN
DISP:
=SQRT((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2));
END;
BEGIN
FORI:
=0T0NDO
FORJ:
=0TOMDO G[I,J]:
=0
READLN(X1,Y1,X2,Y2);
G[X1,Y1]:
=1;
G[X2,Y2]:
P:
=TRUE;
WHILEPDO
BEGIN
=FALSE;
D:
=DISP(X1,Y1,X2,Y2);
X0:
=X1;
Y0:
=Y1;
FORI:
=4TONDO
FORJ:
=0TOMDO
IF(D>
DISP(I,J,X2,Y2))AND(G[I,J]=0)
THENBEGIN
=DISP(I,J,X2,Y2);
=I;
=J;
END;
IF(X0<
>
X1)OR(Y0<
Y1)
X1:
=X0;
Y1:
=Y0;
=X2;
=Y2;
=0TO3DO
FORJ:
IF(D<
DISP(X1,Y1,I,J)AND(G[I,J]=0)
THENBEGIN
D:
=DISP(X1,Y1,I,J);
X0:
=J
X2)OR(Y0<
Y2)
THENBEGIN
X2:
Y2=Y0;
G[X2,Y2]:
WRITELN(X1,Y1,X2,Y2)
END.
输入:
7600
输出:
2.PROGRAMNOI_002;
I,J,L,N,K,S,T:
B:
ARRAY[1..10]OF0..9;
READLN(L,N);
S:
=L;
K:
T:
IFN>
LTHENBEGIN
WHILES<
NDO
BEGIN
K:
=K+1;
=T*L;
S:
=S+T
=S-T;
N:
=N-S-1;
=1TO10DOB[I]:
=0;
J:
=11;
WHILEN>
0DO
=J-1;
B[J]:
=NMODL;
=NDIVL
=10-K+1TO10DO
WRITE(CHR(ORD(‘A’)+B[I]));
READLN;
END
ELSE
WRITELN(CHR(ORD(‘A’)+N-1))
4 167
四.完善程序(共38分)
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统计二进制数是否已出现过。
【程序清单】
PROGRAMNOI00;
VAR
A:
ARRAY[1..36]OF0..1;
ARRAY[0..31]OFINTEGER;
I,J,K,S,P:
INTEGER;
=1TO36DOA[I]:
=28TO32DOA[I]:
A[6]:
WHILE(P=1)DO
=27;
WHILEA[J]=1DOJ:
(①)
=J+1TO27DO(②)
=0TO31DOB[I]:
=O;
=1TO32DO
(③)
FORK:
=ITOI+4DOS:
=S*2+A[K];
(④)
=0TO31DOS:
=S+B[I];
IF(⑤)THENP:
=0
FORJ:
=ITOI+4DOWRITE(A[J]);
WRITELN
2.【问题描述】
求出一棵树的深度和宽度。
例如有如右的一棵树:
其树的深度为从根结点开始到叶结点结束的最大深度,树的宽度为同一层上结点数的最大值。
在右图中树的深度为4,宽度为3。
用邻接表来表示树,右图中的树的邻接表示如下:
PROGRAMNOI00_6;
I,J,SP1,SP2,L,MAX:
TREE:
ARRAY[1..20,1..6]OFINTEGER;
Q:
ARRAY[1..100,0..6]OFINTEGER;
ARRAY[0..20]OFINTEGER;
=1TO14DO
=1TO6DOTREE[I,J]:
=1TO14DOTREE[J,1]:
TREE[1,2]:
=2;
TREE[1,3]:
=3;
TREE[1,4]:
=4;
TREE[2,2]:
=5;
TREE[2,3]:
=6;
TREE[3,2]:
=7;
TREE[3,3]:
=8;
TREE[4,2]:
=9;
TREE[4,3]:
=10;
TREE[4,4]:
TREE[7,2]:
=12;
TREE[7,3]:
=13;
TREE[13,2]:
=14;
SP1:
SP2:
=1TO6DOQ[1,I]:
=TREE[1,I];
Q[1,0]:
WHILE(①)DO
L:
=(②);
WHILE(③)DO
=SP2+1;
Q[SP2,0]:
Q[SP2,1]:
=Q[SP1,J];
=2TO6DO
Q[SP2,I]:
=TREE[Q[SP1,J],I];
=J+1
=SP1+1
WRITELN(④)
=0TO20DOD[I]:
=1TOSP2DO
D[Q[I,0]]:
=(⑤)
MAX:
=D[1];
=2TO20DO
IFD[I]>
MAXTHENMAX:
=D[I];
WRITELN(MAX);
第六届全国青少年信息学(计算机)奥林匹克分区联赛初赛(高中组)
答案
一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分)
题号
1
2
3
4
5
6
7
8
9
10
选择
C
B
D
A
11
12
13
14
15
16
17
18
19
20
二.问题求解(每题6分,共12分)
1.答:
有5种不同形态的二叉树可以得到这一遍历结果;
可画出的这些二叉树为:
①②③④⑤
2.递推公式(用F(N)记录不同案数):
F
(1)=1 F
(2)=2 F(3)=4
F(N)=F(N-3)+F(N-2)+F(N-1) (N≥4)
三.阅读程序,并写出程序的正确运行结果:
(每题10分,共20分)
1.本题的运行结果是:
4 3 0 2
2.本题的运行结果是:
BBAC
1.①A[J]:
②A[I]:
③S:
④B[S]:
⑤S=32
2.①SP1<
=SP2
②Q[SP1,0]+1
③Q[SP1,J]<
0
④(Q[SP2,0]);
⑤D[Q[I,0]]+1;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 广东省 信息技术 历年 NOIP 初赛 试题 07
![提示](https://static.bingdoc.com/images/bang_tan.gif)