第二十届全国青少年信息学奥林匹克竞赛初赛提高组C语言试题_中学教育-竞赛题.pdf

《第二十届全国青少年信息学奥林匹克竞赛初赛提高组C语言试题_中学教育-竞赛题.pdf》由会员分享，可在线阅读，更多相关《第二十届全国青少年信息学奥林匹克竞赛初赛提高组C语言试题_中学教育-竞赛题.pdf（6页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第二十届全国青少年信息学奥林匹克竞赛初赛 提高组 C语言试题 一、单项选择题（每题 1.5 分，共 22.5 分）。1.以下哪个是面向对象的高级语言().A.汇编语言 B.C+C.FORTRAN D.Basic 2.1TB代表的字节数量是().A.2的 10 次方 B.2的 20 次方 C.2的 30 次方 D.2的 40 次方 3.二进制数 00100100 和 00010101 的和是().A.00101000 B.001010100 C.01000101 D.00111001 4.TCP协议属于哪一层协议().A.应用层 B.传输层 C.网络层 D.数据链路层 5.下列几个 32 位 I

2、P地址中，书写错误的是().A.162.105.128.27 B.192.168.0.1 C.256.256.129.1 D.10.0.0.1 6.在无向图中，所有定点的度数之和是边数的()倍.A.0.5 B.1 C.2 D.4 7.对长度位 n 的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为().A.n/2 B.(n+1)/2 C.(n-1)/2 D.n/4 8.编译器的主要功能是().A.将一种高级语言翻译成另一种高级语言 B.将源程序翻译成指令 C.将低级语言翻译成高级语言 D.将源程序重新组合 9.二进制数 111.101 所对应的十进制数是().A.

3、5.625 B.5.5 C.6.125 D.7.625 10.若有变量 int a,float x,y,且 a=7,x=2.5,y=4.7,则表达式 x+a%3*(int)(x+y)%2/4 的值大约是().A.2.500000 B.2.750000 C.3.500000 D.0.000000 11.有以下结构体说明和变量定义，如图所示，指针 p、q、r 分别指向一个链表中的三个续 结点。struct node int data;struct node*next;*p,*q,*r;现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是().A.q-next=r-next

4、;p-next=r;r-next=q;B.p-next=r;q-next=r-next;r-next=q;C.q-next=r-next;r-next=q;p-next=r;D.r-next=q;q-next=r-next;p-next=r;12.同时查找 2n 个数中的最大值和最小值，最少比较次数为().A.3(n-2)/2 B.4n-2 C.3n-2 D.2n-2 13.设 G 是有 6 个结点的完全图，要得到一颗生成树，需要从 G 中删去()条边.A.6 B.9 C.10 D.15 14.以下时间复杂度不是 O(n2)的排序方法是().A.插入排序 B.归并排序 C.冒泡排序 D.选择排

5、序 欢迎下载 2 15.以下程序实现了找第二小元素的算法。输入时 n 个不等的数构成的数组 S，输出 S 中第 二小的数 SecondMin。在最坏的情况下，该算法需要做()次比较。if(S1 S2)FirstMin=S1;SecondMin=S2;else FirstMin=S2;SecondMin=S1;for(i=3;i=n;i+)if(S1 SecondMin)if(S1 FirstMin)SecondMin=FirstMin;FirstMin=S1;else SecondMin=S1;A.2n B.n-1 C.2n-3 D.2n-2 二、不定项选择题（每题 1.5 分，共 7.5 分

6、）。1.若逻辑变量 A、C为真，B、D 为假，以下逻辑运算表达式真的有().A.(BCD)DA B.(-A B)C)B C.(AB)(CD-A)D.A(D-C)B 2.下列()软件属于操作系统软件。A.Microsoft Word B.Windows XP C.Android D.Mac OS X E.Oracle 3.在 NOI比赛中，对于程序设计题，选手提交的答案不得包含下列哪些内容().A.试图访问网络 B.打开或创建题目规定的输入/输出文件之外的其他文件 C.运行其他程序 D.改变文件系统的访问权限 E.读写文件系统的管理信息 4.以下哪些结构可以用来存储图().A.邻接矩阵 B.栈

7、C.邻接表 D.二叉树 5.下列各无符号十进制整数中，能用八位二进制表示的数有().A.296 B.133 C.256 D.199 三、问题求解。1.有数字 1,1,2,4,8,8 所组成的不同的四位数的个数是_.2.如图所示，图中每条边上的数字表示该边的长度，则从 A到 E的最短距离是_.级语言汇编语言代表的字节数量是的次方的次方的次方的次方二进制数和的和是协议属于哪一层协议应用层传输层网络层数据链路层下列几个位地址中书写错误的是在无向图中所有定点的度数之和是边数的倍对长度位的有序单链表译成另一种高级语言将程序翻译成指令将低级语言翻译成高级语言将程序重新组合二进制数所对应的十进制数是若有变量

8、且则表达式的值大约是有以下结构体说明和变量定义如图所示指针分别指向一个链表中的三个续结点现要将和较次数为设是有个结点的完全图要得到一颗生成树需要从中删去条边以下时间复杂度不是的排序方法是插入排序归并排序冒泡排序选择排序以下程序实现了找第二小元素的算法输入时个不等的数构成的数组输出中第二小的数在最坏 欢迎下载 3 四、阅读程序写结果(共 4 题，每题 8 分，共 32 分)。1.#include 2.#include int main()Int fun(int n,int minNum,int maxNum)int a,b,I,tot,c1,c2;scanf(“%d%d”,&a,&d);int

9、tot,i;tot=0;if(n=0)for(i=a;i=b;i+)return 1;tot=0;c1=i/10;for(i=minNum;i=maxNum;i+)c2=i%10;tot+=fun(n-1,i+1,maxNum);if(c1+c2)%3=0)return tot;tot+;int mian()printf(“%d n,tot);return 0;int n,m;Scanf(“%d%d”,&n,&m);printf(“%d n”,fum(m,1,n);return 0;输入：7 31 输出：_ 输入：6 3 输出：_ 3.#include return 0;#include co

10、nst int SIZE=100;/strcmp(a,b)0:a的字典序大于 b char dict SIZE LENGTH+1;int rank SIZE;int ind SIZE;int i,j,n,tmp;scanf(%d,&n);for(i=1;i=n;i+)rank i=i;ind i=i;scanf(%s,dicti);for(i=1;i n;i+)for(j=1;j 0)tmp=indj;indj=ndj+1;indj+1=tmp;for(i=1 i=n;i+)rank indi=i;for(i=1;i=n;i+)级语言汇编语言代表的字节数量是的次方的次方的次方的次方二进制数和的

11、和是协议属于哪一层协议应用层传输层网络层数据链路层下列几个位地址中书写错误的是在无向图中所有定点的度数之和是边数的倍对长度位的有序单链表译成另一种高级语言将程序翻译成指令将低级语言翻译成高级语言将程序重新组合二进制数所对应的十进制数是若有变量且则表达式的值大约是有以下结构体说明和变量定义如图所示指针分别指向一个链表中的三个续结点现要将和较次数为设是有个结点的完全图要得到一颗生成树需要从中删去条边以下时间复杂度不是的排序方法是插入排序归并排序冒泡排序选择排序以下程序实现了找第二小元素的算法输入时个不等的数构成的数组输出中第二小的数在最坏 欢迎下载 4 printf(%d,rank i);输入：7

12、 aaa aba bbb aaa aaa ccc aa printf(n);输出：_ 4.#include const int SIZE=100;/然而编译器看到这行根本不编译=/可以把 SIZE换成 100。int alive100;int n;int next(int num)do num+;if(num n)num=1;while(alive num=0);return num;int main()int m,i,j,num;scanf(%d%d,&n,&m);for(i=1;i=n;i+)alive i=1;num=1;for(i=1;i=n;i+)for(j=1;j m;j+)num

13、=next(num);printf(%d,num);alivenum=0;if(i n)num=next(num);printf(n);return 0;输入：11 3 输出：_ 五、完善程序（每题 14 分，共计 28 分）1.（双栈模拟数组）只使用两个栈结构 stack1 和 stack2，模拟对数组的随机读取。作为栈 结构，stack1 和 stack2 只能访问栈顶（最后一个有效元素）。栈顶指针 top1 和 top2 均指向栈顶元素的下一个位置。输入第一行包含两个整数，分别是数组长度 n 和访问次数 m，中间用单个空格隔开。第二行包含 n 个整数，依次给出数组各项（数组下标从 0 到

14、 n-1）。第三行包含 m 个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。（前两空每空 2.5 分，其余每空 3 分，共 14 分）级语言汇编语言代表的字节数量是的次方的次方的次方的次方二进制数和的和是协议属于哪一层协议应用层传输层网络层数据链路层下列几个位地址中书写错误的是在无向图中所有定点的度数之和是边数的倍对长度位的有序单链表译成另一种高级语言将程序翻译成指令将低级语言翻译成高级语言将程序重新组合二进制数所对应的十进制数是若有变量且则表达式的值大约是有以下结构体说明和变量定义如图所示指针分别指向一个链表中的三个续结点现要将和较次数为设是有个结点的完全图要得到一颗生成树需要

15、从中删去条边以下时间复杂度不是的排序方法是插入排序归并排序冒泡排序选择排序以下程序实现了找第二小元素的算法输入时个不等的数构成的数组输出中第二小的数在最坏 欢迎下载 5#include const int SIZE=100;int stack1 SIZE,stack2 SIZE;int top1,top2;int n,m,i,j;void clearStack()int i;for(i=top1;i SIZE;i+)stack1 i=0;for(i=top2;i SIZE;i+)stack2 i=0;int main()scanf(%d%d,&n,&m);for(i=0;i n;i+)scan

16、f(%d,&stack1 i);top1=(1);top2=(2);for(j=0;j m;j+)scanf(“%d”,&i);while(i top1-1)top2-;(4);top1+;clearstack();printf(“%d n”,stack1 (5);return 0;2.(最大矩阵和)给出 m 行 n 列的整数矩阵，就最大的子矩阵和（子矩阵不能为空）。级语言汇编语言代表的字节数量是的次方的次方的次方的次方二进制数和的和是协议属于哪一层协议应用层传输层网络层数据链路层下列几个位地址中书写错误的是在无向图中所有定点的度数之和是边数的倍对长度位的有序单链表译成另一种高级语言将程序翻译

17、成指令将低级语言翻译成高级语言将程序重新组合二进制数所对应的十进制数是若有变量且则表达式的值大约是有以下结构体说明和变量定义如图所示指针分别指向一个链表中的三个续结点现要将和较次数为设是有个结点的完全图要得到一颗生成树需要从中删去条边以下时间复杂度不是的排序方法是插入排序归并排序冒泡排序选择排序以下程序实现了找第二小元素的算法输入时个不等的数构成的数组输出中第二小的数在最坏 欢迎下载 6 输入第一行包含两个整数 m 和 n,即矩阵的行数和列数。之后 m 行，每行 n 个整数，描述整个矩阵。程序最终输出最大的子矩阵和。（第一空 2 分，其余 3 分，共 14 分）#include const i

18、nt SIZE=100;int matrix SIZE+1 SIZE+1;int rowsum SIZE+1 SIZE+1;/rowsumij 记录第 i 行前 j 个数的和 int m,n,i,j,first,last,area,ans;int main()scanf(%d%d,&m,&n);for(i=1;i=m;i+)for(j=1;j=n;j+)scanf(%d,&matrix i j);ans=matrix (1);for(i=1;i=m;i+)(2);for(i=1;i=m;i+)for(j=1;j=n;j+)rowsum i j=(3);for(first=1;first=n;f

19、irst+)for(last=first;last=n;last+)(4);for(i=1;i ans)ans=area;if(area 0)area=0;printf(%dn,ans);return 0;级语言汇编语言代表的字节数量是的次方的次方的次方的次方二进制数和的和是协议属于哪一层协议应用层传输层网络层数据链路层下列几个位地址中书写错误的是在无向图中所有定点的度数之和是边数的倍对长度位的有序单链表译成另一种高级语言将程序翻译成指令将低级语言翻译成高级语言将程序重新组合二进制数所对应的十进制数是若有变量且则表达式的值大约是有以下结构体说明和变量定义如图所示指针分别指向一个链表中的三个续结点现要将和较次数为设是有个结点的完全图要得到一颗生成树需要从中删去条边以下时间复杂度不是的排序方法是插入排序归并排序冒泡排序选择排序以下程序实现了找第二小元素的算法输入时个不等的数构成的数组输出中第二小的数在最坏