信息学竞赛初中组初赛模拟试题文档格式.docx
《信息学竞赛初中组初赛模拟试题文档格式.docx》由会员分享，可在线阅读，更多相关《信息学竞赛初中组初赛模拟试题文档格式.docx（35页珍藏版）》请在冰点文库上搜索。
非顺序存储的线性表结构
C）
顺序存储的非线性表结构D）
非顺序存储的非线性表结构
特殊的树结构
9.
计算机辅助教学的简写是
（
A）CAI
B）CAM
C）CAD
D）CAS
E）CAT
10.给定一个正整数N=78，现决定依次删除其中6个数位上的数字（每次删除一个数位上的数字），每次删除后按原来的次序组成一个新数M的值均是当前状态下的最小数，则第四次应该删除的数字是（
A）6
B）8
C）7
D）4
E）3
11.算法的基本结构有（
A）顺序
B）选择
C）判断
D）循环
E）重复
12.计算机主机由（
）组成.
A）CPU
B）主板
C）机箱
D）主存
E）显示器
13.算式（1011）2*（11.1）2的结果是（
）.
A）（100110.1）2
B）（1011111）2
C）（38.5）10
D）（26.8）16
E）（46.4）8
14.以下是关于计算机病毒的说法，正确的是（
A）病毒属于计算机软件
B）病毒属于硬件
C）病毒具有破坏性、传播性、可激发性、潜伏性、隐蔽性等特点
D）若软盘染上病毒，能清除病毒的措施是删除该软盘上的所有文件
E）若软盘染上病毒，能清除病毒的措施是格式化该软盘
15.下列关于十进制数-100的正确说法是（
A）原码为BB）反码为E4H
C）反码为9BH
D）补码为64H
E）补码为9CH
16.以下是关于排序的说法正确的是（
A）选择排序、冒泡排序、插入排序是稳定的
B）希尔排序、快速排序、堆排序的时间复杂度为O（nlog2n）
C）线形排序的时间复杂性为O（n）
D）线形排序、二路归并排序的空间复杂度为O（n）
E）希尔排序、快速排序、堆排序、归并排序是不稳定的
17．下列是关于数据结构的说法正确的是（
A）数据结构是带有结构的数据元素的集合
B）线性表的线性存储结构优于链式存储结构
C）队列是一个先进先出的线性表
D）队列是只能在一端插入，另一端删除的线性表
E）栈的插入和删除只能在栈底进行
8.下列IP地址中错误的是（
A）B）C）100:
128:
35:
91
D）111-102-35-21E）
19.关于二叉树的正确说法是（
A）完全二叉树一定是满二叉树B）满二叉树一定是完全二叉树
C）深度为h的二叉树最多有2h-1个结点（h>
=1），最少有h个结点
D）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1
E）在二叉树中，第i层的结点总数不超过2i-1；
20.
以下关于图的正确说法是（
A）所有顶点的度数之和等于边数的2倍
B）所有顶点的度数之和不一定等于边数的2倍
C）任意一个图一定有偶数个奇点
D）任意一个图一定有奇数个偶点
E）在有向图中顶点的入度之和等于出度之和
二.问题求解（5分*2=10分）
1.已知:
1到10中有两个数1、7不能被2，3，5整除，那么1到1000中有多少个数不能被2，3，5
整除？
一个栈（无穷大）的进栈序列为1,2,3,..n,有多少种不同的出栈序列?
如n=3时,出栈序列有1,2,31,3,22,1,32,3,13,2,1共5种，问:
当n=5时的出栈种数是多少（只求种数）？
三.阅读程序写出正确的程序运行结果（4分*8=32分）
1.program
t1;
var
a,b,n:
longint;
begin
readln（n）;
a:
=0;
b:
repeat
=a+1;
=b+a;
until
b>
=n;
writeln（a）;
end.
输入:
20100
输出:
2.program
t2;
const
n=200;
si,pr:
set
of
2..n;
x,j,m:
integer;
readln（m）;
si:
=[2..m];
pr:
=[];
x:
=2;
while
not（x
in
si）
do
=succ（x）;
=pr+[x];
j:
=x;
j
<
=
m
do
begin
=si-[j];
=j+x;
end;
si=[
];
for
=m
downto
2
if
x
pr
then
write（x:
5）;
inc（j）;
mod
10=0
then
writeln;
输入：
50
输出：
3.program
t3;
array[1..9,1..9]
string;
st,x:
i,j,n,m:
writeln（'
please
input
a
string（length<
10）:
'
）;
readln（st）;
n:
=length（st）;
（n
10）
and
odd（n）;
m:
=（n+1）
div
2;
i:
=1
to
n
a[i,j]:
='
;
=i
n+1-i
=copy（st,j,1）;
a[n+1-i,n+1-j]:
=x
=n
1
write（a[i,j]:
2）;
ABCDEFG
4.program
t4;
m,n:
byte;
procedure
fen（i,j:
s:
string）;
k:
s1:
j=1
writeln（m,'
s,i）
else
i-j+1
str（k,s1）;
fen（i-k,j-1,s+s1+'
+'
readln（m,n）;
fen（m,n,'
5
3
四.完善程序题（4分*4+2分*6=28分）
1．单源点最短路径：
给定带权有向图G=（v,e）,源点v1在v中，求 v1到v中其余各结点的最短路径。
数据结构说明：
cost[I,j]:
表示带权有向图的邻接矩阵
d[j]：
表示从v1到vj的最短路径长度
path[j]：
表示从v1到vj的最短路径
程序如下:
program
t5;
n=5;
maxnum=1e10;
type
gr=array[1..n,1..n]
real;
dt=array[1..n]
jh=set
1..n;
pt=array[1..n]
jh;
var
cost:
gr;
d:
dt;
path:
pt;
i,j,k:
mm:
read（cost[i,j]）;
=[1];
=2
d[i]:
=cost[1,i];
d[i]
maxnum
path[i]:
=[1]+[i]
___
（1）___
n-1
=maxnum;
___
（2）___
=d[j];
=j;
=s+[k];
for
not（j
s）
（cost[k,j]
maxnum）
___（3）___
d[j]:
=d[k]+cost[k,j];
path[j]:
=___（4）___
v1->
'
v'
i,'
:
d[i]）;
write（'
v1'
path[i]
->
j）;
问题描述:
将n个整数分成k组（k≤n,要求每组不能为空）,显然这k个部分均可得到一个各自的积
p1,p2,……pk,定义整数S为:
S=（p1-p2）2+（p1-p3）2+……+（p1-pk）2+（p2-p3）2+……+（pk-1-pk）2
问题求解:
求出一种分法,使S为最大（若有多种方案仅记一种〉
程序说明:
数组:
a[1],a[2],...A[N]存放原数
p[1],p[2],...,p[K]存放每个部分的积
b[1],b[2],...,b[N]穷举用临时空间
d[1],d[2],...,d[N]存放最佳方案
程序:
t6;
Var
i,j,n,k
Sum,cmax:
array
[1..100]
b,d:
[0..100]
p
array[1..30]
readln（n,k）;
I:
read（a[I]）;
=0
b[I]:
=1;
cmax:
（b[0]=1）
k
___（5）___;
___（6）___;
sum:
k-1
=___（7）___
=sum+（p[I]-p[j]）*（p[I]-p[j]）;
___（8）___
=sum;
d[I]:
=b[I];
___（9）___
=j-1;
b[j]:
=b[j]+1;
=j+1
___（10）___
writeln（cmax）;
write（d[I]:
40）;
信息学竞赛初中组初赛模拟试题
（二）
一、选择题：
（共20小题，1-15小题为单选题，每题1分；
16-20小题为多选题，每题2分。
共25分）
1.对存储器按字节进行编址，若某存储器芯片共有10根地址线的引脚，则该存储器芯片的存储容量为（
（A）512B
（B）1KB
（C）2KB
（D）4KB
（E）8KB
2.在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（
（A）堆排序
（B）希尔排序
（C）冒泡排序
（D）快速排序
（E）二分排序
3.某数列有1000个各不相同的单元，由低至高按序排列，现要对该数列进行二分法检索，在最坏的情况下，需要检索（
）单元。
（A）1000
（B）10
（C）100
（D）500
（E）300
4.已知数组a中，每个元素a[i,j]在存储时要占3个字节，设i从1变化到8，j从1变化到10，分配内存实是从地址sa开始连续按行存储分配的。
试问：
a[5，8]的起始地址为（
（A）sa+141
（B）sa+180
（C）sa+222
（D）sa+225
（E）sa+155
5.在pascal语言过程调用时，数值形参得到的是实际参数的（
（A）数值
（B）地址
（C）值
（D）变量
（E）以上都不是
6.一个24*24点阵的汉字字形信息所占的字节数为（
（A）2
（B）
8
（C）
24
（D）
32
（E）
72
7.在微机系统中，最基本的输入输出模块BIOS存放在（
）中。
（A）RAM
（B）ROM
（C）硬盘
（D）寄存器
（E）控制器
8.十进制算术表达式:
3*512+5*64+2*8+1的运算中,用二进制表示为（
（A）01（B）（C）（D）
（E）111000
9.设栈S的初始状态为空,现对序列{1,2,3,4,5}在栈S上,依次进行如下操作（从元素1开始,出栈后不再进栈）:
进栈,出栈,进栈,进栈,出栈,出栈。
试问出栈的元素序列是（
（A）{1,2,3}B）{1,3,2}C）{3,2,1}D）{2,3,1}
（E）以上都不对
10.E-mail邮件本质上是一个（
）
（A）文件 （B）电报 （C）电话 （D）传真
（E）电讯
11.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有（
）个结点
（A）2h-1 （B）2h-1 （C）2h+1 （D）h+1
（E）h*h+1
12.无向图G=（V，E），其中V={a,b,c,d,e,f},
E={（a,b）,（a,e）,（a,c）,（b,e）,（c,f）,（f,d）,（e,d）}对该图进行深度优先遍历,得到的顶点序列正确的是（
）
（A）a,b,e,c,d,f （B）a,c,f,e,b,d （C）a,e,b,c,f,d
（D）a,b,e,d,f,c（E）以上都不对
13.pascal编译程序是（
（A）.把pascal源程序转换成可运行的EXE文件的程序
（B）.把pascal源程序转换成等价的目标码的程序
（C）.生成和修改一个pascal语言源程序的等程序
（D）.把pascal的目标码程序转换成可运行的EXE文件的程序
（E）.生成一个等价的汇编程序
14.将三封信投到4个邮筒，最多的投法有（
（A）．
种
（B）．
（C）．
（D）．种
E.
种
15.电子信函（电子邮件）的特点之一是（
（A）.比邮政信函，电报，电话，传真都更快
（B）.在通信双方的计算机之间建立其直接的通信线路后即可快速传递数字信息
（C）.采用存储-转发方式在网络上逐步传递信息,不象电话那样直接、及时,但费用低廉
（D）.在通信双方的计算机都开机工作的情况下即可快速传递数字信息
16.以下属于多媒体硬件的是（
（A）．主机
（B）.光驱
（C）.声卡
（D）.音箱
（E）.超级解霸
17.正确的二维数组类型说明是（
）
（A）typear2=array[1..5,5..1]ofinteger;
（B）typear2=array[1..5]ofarray[5.1]ofinteger;
（C）typear2=array[1..5,1..5]ofinteger;
（D）typear2=array[1..5]ofarray[1..5]ofinteger
（E）typear2=array[1..5,1..5]of0..1
18.下列属于信息处理的是（
（A）信息加工
（B）信息分类
（C）信息技术
（D）信息采集
（E）信息存储
19.在windows中,最小化一个应用程序窗口后，该程序将（
（A）被终止执行（B）被暂停执行（C）被转入后台
（D）继续执行（E）以上答案都不对
20.下面的常量说明中，正确的是（
（A）CONST
（B）CONST
（C）CONST
（D）CONST
（E）CONST
t=true
b,C=45
M=100，15
N=1OR2
a=’A’
二、问题求解：
（第1小题5分，第2-3小题各4分,共13分）
[问题1]:
在所有三位数中，各位数字从高位到低位顺次减小的数共有个。
[问题2]：
"
银条"
一位银矿勘探员无力预付3月份的房租。
他有一根长31英寸的纯银条，因此他和女房东达成如下协议。
他说，他将把银条切成小段。
3月份的第一天，他给女房东1英寸长的一段，然后每天给她增加1英寸，以此作为抵押。
勘探员预期到3月份的最后一天，他能全数付清租金，而届时女房东将把银条小段全部还给他。
3月份有31天，一种办法是把银条切成31段，每段长1英寸。
可是这处花很多功夫。
勘探员希望既履行协议，又能使银条的分段数目尽量减少。
例如，他可以第一天给女房东1英寸的一段，第二天再给1英寸的一段，第三开他取回这两段1英寸的而给她3英寸的一段。
假设银条的各段是按照这种方式来回倒换的话，勘探员至少需要把他的银条切成______段？
[问题3]:
换不开的钞票"
钱柜里有1.15美分，一位顾客提出：
把1美元的钞票换成硬币，但出纳小姐说换不开，后来这位顾客提出：
把50美分的钞票换成硬币，但出纳小姐又说换不开，而实际上，出纳小姐也无法把25美分、10美分、5美分的钞票换成硬币。
请问钱柜里到底有哪些硬币？
他们分别有多少枚？
答：
_________________。
三、写出程序的运行结果：
（每小题6分，共30分）
1.
programtext1;
constn=6;
m=3;
vari,j,k:
begin
fori:
=-ntondo
k:
=n-abs（i）;
write（'
'
39-k）;
forj:
=-ktokdo
ifabs（j）>
k-m
thenwrite（n-（i+n）div2）
elsewrite（'
writeln;
end;
end.
输出的结果为：
2.PROGAMtext2；
VARa:
ARRAY[1..10]OFChar；
Integer；
ch:
Char；
BEGIN
FORk:
=1TO10DOa[k]:
=Chr（Ord（'
A'
）+k）；
=1TO10DO
升级会员 