信息学初赛模拟试题(四)
一、 选择题：（选出每题正确的答案**，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）
1、二进制数***转换成十六进制数是（ ）
a．32 b．64 c．128 d．100 e．256
2、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（ ）
a．j**a b．ms-dos c．linux d．windows2000 e．unix
3、计算机病毒的传染是以计算机运行和（ ）为基础的，没有这两个条件，病毒是不会传染的。
a．编辑文稿 b．读写磁盘 c．编程序 d．扫描图画 e．打印。
4、因特网不属于任何个人，也不属于任何组织。其中在网络知识这一块中有一个英文简写isp，它的中文意思是（ ）
a．因特网连接 b．因特网使用 c．因特网设计 d．因特网服务提供者 e．信息传输。
5、internet给我们提供了资源共享、浏览、检索信息和远程登录等多种服务，下面几个选项中用于远程登录的是（ ）
a．www b．tcp/ip c．telnet d．e-mail e．ftp
6、ie是目前流行的浏览器软件，它的工作基础是解释执行用（ ）语言书写的文件。
a．vc b．html c．basic d．http e．vb
7、给出3种排序：插入排序、冒泡排序、选择排序。这3种排序的时间代价分别是（ ）
a．o(n)、o(n2)、o(logn) b．o(logn) 、o(n)、o(n2) c．o(n2)、o(n)、o(logn)
d．o(n2)、o(n)、o(n) e．o(n2)、o(n2)、o(n2)
8、一棵完全二叉树的结点总数为18，其叶结点数为。
a．7个 b．8个 c．9个 d．10个 e．11个。
9、在流程图的符号中，菱形框一般作为（ ）
a．起始框 b．判断框 c．输入输出框 d．处理工作框 e．结速框。
10、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主要将要输出打印的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。
a．堆栈 b．数组 c．线性表 d．队列 e．链表。
11、多**技术中的“多**”的含义主要是指如（ ）等多种表达信息的形式。
a．磁盘 b．音箱 c．显示器 d．声音 e．图像。
12、下面有关计算机知识说明，正确的是（ ）
a． 在windows98操作系统下，删除磁盘中的文件时都先存放在**站中。
b． foxmail是用于收发电子邮件的工具。
c． 文件夹组织是一个有层次的树状结构，其中最顶层的是桌面。
d．存储器具有记忆能力，其中的信息任何时候都不会丢失。
e． 为了提高软件的测试效率，应该选择发现错误的可能性大的测试数据。
13、对按关键字排序好的线性表进行二分查找，该线性表适合的存储结构为（ ）
a．链接存储 b．索引存储 c．散列存储 d．顺序存储 e．循环存取。
14、一个栈的输入顺序为，下列序列中可能是栈的输出序列的是（ ）
a．54312 b．24135 c．21543 d．12534 e．12345
15、评价一个算法的好坏有多种指标，下列是算法评价指标的是（ ）
a． 正确性 b．运行时间 c．占用空间 d．迭代次数 e．简单性。
16、下面描述用多维数组表示的数据结构的语句中，正确的是（ ）
a． 多维数组存放的都是同一种类型的数据。
b． 多维数组各维的下标范围必须一样。
c． 多维数组在内存中的地址是连续的。
d． 多维数组中的下标不能是表达式。
e． 多维数组是随机存取的数据结构。
17、若已知一个栈的入栈顺序1，2，3，…，n，其输出序列为p1，p2，p3，…，pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（ ）
a．pjb．pk< pjc．pjd．pie．以上都不可能出现。
18、线性表具有如下的结构特点：（
a．均匀性 b．单一性 c．简单性 d．无序性 e．有序性。
19、下列关于数据结构的叙述中正确的是（ ）
a．数据结构是带有结构的数据元素的集合。
b．线性表的线性存储结构优于链式存储结构。
c．队列是限定仅在一端进行插入，在另一端进行删除的线性表。
d．二维数组是其数据元素为线性表的线性表。
e．图是一种非线性数据结构。
20、任意一棵树均可惟一地转换成与它对应的二叉树。由树转换成的二叉树中，顶点n的左右子女分别是n在原树里对应顶点的（ ）
a． 最左子顶点/最邻近的右兄弟。
b． 最右子顶点/最右的兄弟。
c．最邻近的右兄弟/最左的兄弟。
d．最邻近的左兄弟/最邻近的右兄弟。
f． 最邻近的右兄弟/最右的兄弟。
二、 问题解答：（共2题，每题5分，共10分）
1、 光明中学开设数学、英语和信息学三个兴趣学习小组，其中数学小组30人，英语小组15人，信息学小组18人，参加三个小组总人数为50人，其中有3人同时参加3个小组，那么同时只参加两个小组的同学有多少人？
2、 给出一组顶点（顶点值用a，b，c，d，e，f表示），其对应权值分别为2，3，1，7，8，4。请以a，b，c，d，e，f为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度wpl的值。
三、 写出程序的运行结果（共4题，每题8分，共32分）
第1题：program test1；
var n：integer；
function count(n：integer)：integer；
beginif n=1 then count：=0
elseif n mod 2=0 then count：=count(n div 2)+1
else count：=count(n*3+1)+1；
end；begin
readln(n)；
writeln(count(n))；
end.输入：99
输出：第2题：
program test2(input,output);
vari,j,k,s:integer;
begins:=0
for i:=3 downto 1 do
beginfor j:=1 to 3 do
begink:=0;
repeat
k:=k+1;s:=s+k;
until k=j;
end;s:=s-(k+1);
end;write(‘s=’,s);
end.输出：
第3题：program test3;
var a,b,n:longint;
beginreadln(n);
a:=0;b:=0;
repeat
a:=a+1;b:=b+a;
until b>=n;
writeln(a);
end.输入：415377
输出：program test4;
var m,n,i,p,k：integer;
r:array[1…200] of integer;
b:boolean;
beginm:=6;n:=2;
for i:=1 to m-1 do r[i]:=i+1;
r[m]:=1;i:=0;p:=1;b:=true;
while b do
begini:=i+1;k:=p;p:=r[p];
if k=p then
begin writeln(p);b:=false end
else if i=n+1 then
beginwrite(p,‘ i:=0;p:=r[p];r[k]:=p;
endend
end.输出：
四、完善程序（共2题，每题14分，共28分）
第1题（7分）
【问题描述】
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为xk，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于xk，而价值的和为最大。
程序清单】program package;
const maxxk=400;maxn=20;
type tlist=array[1…maxn] of byte;
tmake=array[0…maxn,0…maxxk] of integer;
var n,xk:integer;
w,u:tlist;
f:tmake;
procedure init;
var i:byte;
beginfillchar(w,sizeof(w),0);
fillchar(u,sizeof(u),0);
readln(n,xk);
for i:=1 to n do
end;procedure make;
var i,j:byte;
beginfor i:=1 to n do
beginfor j:=1 to w[i]-1 do
f[i,j]:=f[i-1,j];
for j:=w[i] to xk do
if f[i-1,j]>f[i,j-w[i]]+u[i] then
elseend;
end;procedure print;
var get:tlist;
i,j:byte;
2019信息学奥林匹克竞赛初赛模拟试题 14
信息学竞赛初赛模拟试题 十四 中学组pascal语言，两小时完成 一 选择题 前15个题为单选题，后5题为不定项选择题 1 email邮件本质上是一个。a.文件 b.电报 c.d.传真 e.信封。2 计算机病毒通常是 a.一条命令 b.一个文件 c.一个标记 d.一段计算机程序 e.一条虫。3 计算...
2019信息学奥林匹克竞赛初赛模拟试题 13
全国青少年信息学 计算机 奥林匹克分区联赛模拟试题 一 单项选择题 1 人们在谈论计算机的时候，经常提到的 586 和 奔腾 是指 a 显示器 b 存储器 c 处理器 d 运算器。2 关于windows的说法，正确的是 a windows是迄今为止使用最广泛的应用软件。3 使用windows时，必须...
2019信息学奥林匹克竞赛初赛模拟试题 16
信息学竞赛初赛模拟试题 十六 初中组pascal语言，两小时完成 请将正确答案在答卷上填写，在本试题卷上作答无效 一 选择题 选出每题正确的一个答案 填在横线上，每题1.5分，共30分 1 执行下列二进制算术加运算11001001 00100111 a.11101111 b.11110000 c.0...