第二十届全国青少年信息学奥林匹克竞赛初赛提高组C语言试题(附答案).pdf

第二十届全国青少年信息学奥林匹克竞赛初赛提高组 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 位 IP地址中，书写错误的是( ). 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. 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 data next data next data next int data; struct node *next; p q r *p,*q,*r; 现要将 q 和 r 所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( ). A. q-next = r-next; 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. 选择排序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 分） 。1. 若逻辑变量A、 C为真， B、D 为假，以下逻辑运算表达式真的有( ). A. (BCD)D A B. (- AB)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. 栈C. 邻接表D. 二叉树5. 下列各无符号十进制整数中，能用八位二进制表示的数有( ). A. 296 B. 133 C. 256 D. 199 三、问题求解。1. 有数字 1,1,2,4,8,8 所组成的不同的四位数的个数是_. 2. 如图所示，图中每条边上的数字表示该边的长度，则从A 到 E的最短距离是 _. 四、阅读程序写结果(共 4 题，每题8 分，共 32 分)。1. #include int main() int a,b,I,tot,c1,c2; scanf(“ %d%d ” , &a, &d);tot = 0; for (i=a; i=b; i+) c1=i/10; c2=i%10; if (c1+c2)%3 =0) tot+; Printf(“ %dn,tot); Return 0; 输入： 7 31 输出： _ 2. #include Int fun(int n, int minNum, int maxNum) int tot, i; if (n=0) retuen 1; tot=0; for(i=minNum; i=maxNum; i+) tot+=fun(n-1, i=1, maxNum); return tot; int mian() int n, m; Scanf( “ %d%d ” , &n,&m);printf(“ %dn” , fum(m,1,n);return 0; 输入：6 3 输出： _ #include #include const int SIZE=100; const int LENGTH=25; / strcmp(a,b) 0:a 的字典序大于b int main() char dictSIZELENGTH+1; int rankSIZE; int indSIZE; int i,j,n,tmp; scanf(“ %d ” ,&n);for (i=1;i=n;i+) rank i=i indi=i; scanf(“ %s” , dicti); for(i=1;in;i+) for(j=1;j0) tmp=indj; indj=indj+1; indj+1=tmp; for(i=1;i=n;i+) rankindi=i; for(i=1:i=n;i+) ptintf(%d” ,ranki);printf(“n” );return 0; 输入：7 aaa aba bbb aaa aaa ccc aa 输出： _ #niclude const int SIZE=100; int aliveSIZE; int n; int next(int num) do num+; if(numn) num=1; while (alivenum=0); return num; int main() int m,i,j,num; scanf(“ %d%d ” ,&n,&m);for(i=1;i=n;i+) alivei=1; num=1; for(i=1;i=n;j+) for(j+1;j=m;j+) num=next(num); printf(“ %d ” ,num);alivenum=0; if(in) num=next(num); printf(n); return 0; 输入：11 3 输出： _ 五、完善程序1 （双栈模拟数组）只使用两个栈结构stack1 和 stack2，模拟对数组的随机读取。作为栈结构， stack1 和 stack2 只能访问栈顶（最后一个有效元素）。栈顶指针top1 和 top2 均指向栈顶元素的下一个位置。输入第一行包含的两个整数，分别是数组长度n 和访问次数m，中间用单个空格隔开。第二行包含n 个整数，一次歌出数组各项（数组下标从0 到 a-1） 。第三行包含m 个整数，需要访问的数组下标。对于每次访问，输出对应的数组元素。#include consr int SIZE=100; int stack1SIZE,stack2SIZE; int top1,top2; int n,m,i,j; void clearStack() int I; for(i=top1;iSIZE;i+) stacki=0; for(i=top2;iSIZE;i+) stacki=0; int main() scanf(%d,%d ” ,&n,&m);for(i=0in;i+) scanf(“ %d ” ,&stack1i);top1=_（1）_; top2=_（2）_; for(j=0jm;j+) scanf(“ %d ” ,&i);while(itop1-1) top2- -; (4) ; top1+; clearstack(); printf(“ %dn” ,stack1 (5) ); return 0; (最大矩阵和 )给出 M 行 N 列的整数矩阵，就最大的子矩阵和（子矩阵不能为空）。输入第一行包含两个整数M 和 N,即矩阵的行数和列数。之后M 行，每行N 个整数，描述整个矩阵。程序最终输出最大的子矩阵和。（第一空 2 分，其余3 分，共 14 分）#include const int SIZE=100; int matrixSIZE+1SIZE+1; int rowsumSIZE+1SIZE+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 ” ,&matrixij);ans=matrix (1) ; for(i=1;i=m;i+) (2) ; for(i=1;i=m;i+) for(j=1;j=n;j+) rowsumij= (3) ; for(first=1;first=n;first+) for(last=first;last=n;last+) (4) ; for(i=1;ians) ans=area; if(area0) area=0; printf(“ %dn” ,ans);return 0; 二、问题求解（共2 题，每题 4 分，共计8 分；每题全部答对得4 分）1. _ 102 _2. _ 15 _ 三、阅读程序写结果（共4 题，每题8 分，共计32 分）1. _ 8 _2. _ 20 _ 3. _ 2 5 6 3 4 7 1 _4. _ 3 6 9 1 5 10 4 11 8 2 7 _ 四、完善程序（共2 题，每题 10 分，共计20 分）1. (1) _ n _（2 分）(2) _ 0_ （ 2 分）(3) _ stack2top2=stack1top1 _ （2 分）(4) _ stack1top1=stack2top2 _ （2 分）(5) _ top1-1 _ （2 分）2. (1) _ 11 _ （2 分）(2) _rowsumi0=0_ （2 分）(3) _ rowsumij-1 + matrixij _（2 分）(4) _area=0 _ （2 分）(5) _ rowsumilast-rowsumifirst-1 _（2 分）尽 管 人 智 慧 有 其 局 限 ， 爱 智 慧 却 并 不 因 此 就 属 于 徒 劳 。 智 慧 果 实 似 乎 是 否 定 性 ： 理 论 上 “ 我 知 道 我 一 无 所 知 ” ； 实 践 上 “ 我需 要 我 一 无 所 需 ” 。 然 而 ， 达 到 了 这 个 境 界 ， 在 谦 虚 和 淡 泊 哲 人 胸 中 ， 智 慧 痛 苦 和 快 乐 业 已 消 融 为 了 一 种 和 谐 宁 静 了