初中信息学竞赛(C语言)试卷
初中信息学笔试试题（C语言）
本试卷分第Ⅰ卷和第Ⅱ卷两部分，共8页。满分100分，考试时间：90分钟。
注意事项：
1. 答题前，考生在试卷、答题纸上务必用黑色签字笔或蓝黑钢笔将自己的学校、
姓名、准考证号写在规定的位置。
2.第Ⅰ卷和第Ⅱ卷的答案必须写在答题纸相应的位置，不能写在试卷上。
第Ⅰ卷（共30分）
一、选择题：（本大题共15小题，每小题2分，共30分，每小题给出的四个
选项中，只有一项是符合要求的，请将答案填写在答题纸相应的位置。）
1.二进制数00100100和00010101的和是（ ）。
A. 00101000 B. 001010100 C. 01000101 D. 00111001
2.一棵具有5层的满二叉树中结点数为（ ）。
A. 31 B. 32 C. 33 D. 16
3.有向图中每个顶点的度等于该顶点的( )。
A.入度 B.出度 C.入度与出度之和 D.入度与出度之差
4.设有100个数据元素，采用折半搜索时，最大比较次数为（ ）。
A.6 B.7 C.8 D.10
5 .1MB等于（ ）。
A.1000字节 B.1024字节 C.1000×1000字节 D.1024×1024字节
6.6个顶点的连通图的最小生成树，其边数为（ ）
A.6 B.5 C.7 D.4
7.前序遍历序列与中序遍历序列相同的二叉树为（ ）
A.根节点无左子树的二叉树 B 、根节点无右子树的二叉树
C.只有根节点的二叉树或非叶子节点只有左子树的二叉树
D.只有根节点的二叉树或非叶子节点只有右子树的二叉树
8.广度优先搜索时，需要用到的数据结构是（ ）。
A.链表 B.队列 C.栈 D.散列表
9.体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走向排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法 。
A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序
10.如果根的高度为1，具有61个节点的完全二叉树的高度为（ ）。
A.5 B.6 C.7 D.8
11.现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只
由 4 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700、600、300、200。那么，“也”字的编码长度是（ ）。
A. 1 B. 2 C. 3 D. 4
12.（ ）是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
A. 回溯法 B. 枚举法 C. 动态规划 D. 贪心法
13.无向完全图是图中每对顶点之间都恰有一条边的简单图。已知无向完全图G
有7个顶点，则它共有（ ）条边。
A. 7 B. 21 C. 42 D. 49
14.在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ）。
A. 程序运行时理论上所占的内存空间
B. 程序运行时理论上所占的数组空间
C. 程序运行时理论上所占的硬盘空间
D. 程序源文件理论上所占的硬盘空间
15.一个正整数在二进制下有 100 位，则它在十六进制下有（ ）位。
A. 7 B. 13 C. 25 D. 不能确定
第Ⅱ卷
二、填空题：（本大题共10个空，每个空2分，共20分）
1 、一个 32 位整型变量占用（ ）个字节。
2、二进制数 11.01 在十进制下是（ ）。
3、下面的故事与（ ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....。
4、前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。
5、设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。
6、二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。
7、按照二叉数的定义，具有3个结点的二叉树有（ ）种。
8、字符串“ababacbab”和字符串“abcba”的最长公共子串是（ ）。
9、设A = true，B = false，C = false，D = true，逻辑运算表达式A∧((B∨C)∨D)的值为（ ）。
三、完善程序（本大题共3个小题，每小题10分，共30分）
1. 若三位数abc，满足a3+b3+c3=abc，则称abc为水仙花数。如153，13+53+33=1+125+27=153，则153称为水仙花数。编程求100～999中的所有的水仙花数。
#include<stdio.h>
int main(){
int i,a,b,c;
for(i=100;i<=999;i++){
a=i/100;
b=____ (1) _____ ;
c=i%10;
if(a*a*a+b*b*b+c*c*c==i)
printf("%d\n",i);
}
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int main()
{
int i,j,k,l,n,m,a[51]={0};
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
int ok=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
for(k=1;k<=n;k++)
for(l=1;l<=n;l++)
if((____(2)_____) ok=1;
if(ok==1) printf("%s\n","yes");
else printf("%s\n","no");
return 0;
}
2. 你和你的朋友在玩一个简单的游戏：你的朋友将写有数字的n个纸片放在他的口袋中，你可以从他的口袋中抽出4次纸片，每次抽出纸片后记下纸片上的数字后再将其放在口袋中，如果这4个数字的和恰好是m，就算你赢，否则你的朋友赢。你挑战了好几回都没赢，于是想写个程序验证是否有赢的可能性，即是否存在抽取4次和为m的方案，如果存在输出yes，否则输出no。
3. 给出正整数n,用递归的方式正序输出1~n。
var
n:longint;
procedure dfs(i:longint);
begin
if i>n then exit;
writeln(i);
____(3)_____;
end;
begin
readln(n);
dfs(1);
end.
四、分析程序，写运行结果（本大题共2个小题，每小题10分，共20分）
1.
var
n,m,i,ans:integer;
begin
readln(n,m);
ans:=0;
i:=n;
while i<=m do
begin
ans:=ans+i;
inc(i);
end;
writeln(ans);
end.
输入：10 20
输出：_________
2.
#include<stdio.h>
int main()
{
int a,b,u,v,i,num;
scanf(“%d%d%d%d”,&a,&b, &u,&v);
num=0;
for(i=a;i<=b;i++)
{
if ((i%u==0) || (i%v==0)) num++;
}
printf(“%d\n”,num);
return 0;
}
输入：1 1000 10 15
输出：_________