版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第十九届全国青少年信息学奥林匹克联赛初赛普及组C+正言试题竞赛时间:2013年10月13日14:3016:30选手注意:试题纸共有9页,答题纸共有2页,满分100分。请在答题纸上作答,写在试题纸上的一律无效。不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。一、单项选择题(共20题,每题1.5分,共计30分;每题有且仅有一个正确选项)1 .一个32位整型变量占用()个字节。A.4B.8C.32D.1282 .二进制数11.01在十进制下是()。A.3.25B.4.125C.6.25D.11.1253 .下面的故事与()算法有着异曲同工之妙。从前有座山,山里有座庙,庙里有个老
2、和尚在给小和尚讲故事:从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事.'A.枚举B.递归C.贪心D.分治4 .逻辑表达式()的值与变量A的真假无关。A.(AVB)AAB.(AVB)ABC.(AAB)V(AAB)D.(AVB)AAAB5.将(2,6,10,17)分别存储到某个地址区间为010的哈希表中,如果哈希函数h(x)=(),将不会产生冲突,其中amodb表示a除以b的余数。A.xmod11B.x2mod11C.2xmod11D.|,2|mod11,其中,X表示,X下取整6 .在十六进制表示法中,字母A相当于十进制中的()
3、。A.9B.10C.15D.167 .下图中所使用的数据结构是()。A.哈希表B.栈C.队列D.二叉树8 .在Windows资源管理器中,用鼠标右键单击一个文件时,会出现一个名为“复制”的操作选项,它的意思是()。A.用剪切板中的文件替换该文件8 .在该文件所在文件夹中,将该文件克隆一份C.将该文件复制到剪切板,并保留原文件D.将该文件复制到剪切板,并删除原文件9 .已知一棵二叉树有10个节点,则其中至多有()个节点有2个子节点。A.4B.5C.6D.710 .在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通图。下图是一个有4个顶点、6条边的连通图。若要使它不再是连通图,至少要删去
4、其中的()条边。B.2C.3D.4A.11.A.12.1二叉树的(先序遍历)第一个访问的节点是根节点。B.中序遍历C.后序遍历D.以上都是以A0作为起点,对下面的无向图进行深度优先遍历时,遍历顺序不可能是(A.A0,A1,A2,A3B.A0,A1,A3,A2C.A0,A2,A1,A3D.A0,A3,A1,A213.IPv4协议使用32位地址,随着其不断被分配,地址资源日趋枯竭。因此,它正逐渐被使用(A.14.A.15.)位地址的IPv6协议所取代。40B.48C.64D.128()的平均时间复杂度为O(nlogn),其中快速排序B.插入排序C.冒泡排序卜面是根据欧几里得算法编写的函数,它所计算
5、的是inteuclid(inta,intb)if(b=0)returna;elsereturneuclid(b,a%b);nD.是待排序的元素个数。基数排序a和b的()。A.C.16.A.B.C.D.17.A.18.A.C.19.最大公共质因子最大公约数B.最小公共质因子D.最小公倍数通常在搜索引擎中,对某个关键词加上双引号表示(排除关键词,不显示任何包含该关键词的结果将关键词分解,在搜索结果中必须包含其中的一部分精确搜索,只显示包含整个关键词的结果站内搜索,只显示关键词所指向网站的内容中国的国家顶级域名是(.cnB.ch)。C.chn把64位非零浮点数强制转换成大于原数等于原数B.小于原数D
6、.与原数符号相反D.china32位浮点数后,不可能()。卜列程序中,正确计算1,2,?,100这100个自然数之和sum(初始值为0)的是(A.i=1;sium+-i+;while(i<=100):B.I=1;dosum+=i:r+;while(i>100);C.i=1;white(I<100)sum+=i;i+,).D.i=1;while(1>=100)sum+=i;r+;20.CCFNOIP复赛全国统一评测时使用的系统软件是()。A.NOIWindowsB.NOILinuxC.NOIMacOSD.NOIDOS二、问题求解(共2题,每题5分,共计10分;每题全部答对
7、得5分,没有部分分)1.7个同学围坐一圈,要选2个不相邻的作为代表,有种不同的选法。2.某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,?,sn,均为。或1。该系统每次随机生成n个数a1,a2,?,an,均为。或1,请用户回答(s1a1+s2a2+?+snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码一一因为用户并没有直接发送密码。然而,事与愿违。例如,当n=4时,有人窃听了以下5次问答:H答编号系统生成的n个数孽握密码的用户的回答at02睨3411100120011030110041110051D000就破
8、解出了密码s1=,s2=,s3=,s4=。三、阅读程序写结果(共4题,每题8分,共计32分)1. #include<iostream>usingnamespacestd;intmain()inta,b;cin>>a>>b;cout<<a<<"+"<<b<<"="<<a+b<<endl;输入:35输出:2. #include<iostream>usingnamespacestd;intmain()inta,b,u,i,num;cin>
9、;>a>>b>>u;num=0;for(i=a;i<=b;i+)if(i%u)=0)num+;cout<<num<<endl;return0;输入:110015输出:3. #include<iostream>usingnamespacestd;intmain()constintSIZE=100;intn,f,i,left,right,middle,aSIZE;cin>>n>>f;for(i=1;i<=n;i+)cin>>ai;left=1;right=n;domiddle=(lef
10、t+right)/2;if(f<=amiddle)right=middle;elseleft=middle+1;while(left<right);cout<<left<<endl;return0;输入:121724691115171819202125输出:4.#include<iostream>usingnamespacestd;intmain()constintSIZE=100;intheightSIZE,numSIZE,n,ans;cin>>n;for(inti=0;i<n;i+)cin>>heighti;nu
11、mi=1;for(intj=0;j<i;j+)if(heightj<heighti)&&(numj>=numi)numi=numj+1;ans=0;for(inti=0;i<n;i+)if(numi>ans)ans=numi;cout<<ans<<endl;输入:625311124输出:四、完善程序(共2题,每题14分,共计28分)1. (序列重排)全局数组变量a定义如下:constintSIZE=100;intaSIZE,n;它记录着一个长度为n的序列a1,a2,?,an。现在需要一个函数,以整数p(1<p<n
12、)为参数,实现如下功能:将序列a的前p个数与后n-p个数对调,且不改变这p个数(或n-p个数)之间的相对位置。例如,长度为5的序列1,2,3,4,,当p=2时重排结果为3,4,5,1,2。有一种朴素的算法可以实现这一需求,其时间复杂度为O(n)、空间复杂度为O(n):void swap1(int p)int i, j, bSIZE;for (i = 1; i <= p; i+)b (1) = ai;for (i = p + 1; i <= n; i+) bi - p =(2) ;for (i = 1; i <= ai = bi;/( 3 分)/( 3 分)(3) ; i+)/
13、( 2 分)我们也可以用时间换空间,使用时间复杂度为O(n2)、空间复杂度为O(1)的算法:voidswap2(intp)inti,j,temp;for(i=p+1;i<=n;i+)temp=ai;for(j=i;j>=(4);j-)/(3分)aj=aj-1;(5) =temp;/(3分)2. (二叉查找树)二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。输入的第一行包含一个整数n,表示这棵树有n个顶点,编号分别为1,2,?,n,其中编号为1的为根结点。之后的第i行有三个数value,left_child,
14、right_child,分别表示该节点关键字的值、左子节点的编号、右子节点的编号;如果不存在左子节点或右子节点,则用0代替。输出1表示这棵树是二叉查找树,输出0则表示不是。#include<iostream>usingnamespacestd;constintSIZE=100;constintINFINITE=1000000;structnodeintleft_child,right_child,value;nodeaSIZE;intis_bst(introot,intlower_bound,intupper_bound)intcur;if(root=0)return1;cur=a
15、root.value;if(cur>lower_bound)&&(1)&&(is_bst(aroot.left_child,lower_bound,cur)=1)&&(is_bst(2),(3),(4)=1)return1;return0;intmain()inti,n;cin>>n;for(i=1;i<=n;i+)cin>>ai.value>>ai.left_child>>ai.right_child;cout<<is_bst(5),-INFINITE,INFINITE)<<endl;return0;第十九届全国青少年信息学奥林匹克联赛初赛普及组参考答案20题,每题1.5分,共计30分)7891011121314151617181920AADACCADAB二、问题求解(共2题,每题5分,共计10分;每题全部答对得5分,没有部分分)1. 142. s
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 数据仓库与数据挖掘第一章-数据仓库和数据挖掘概述
- 报关员资格管理制度改革公告后工作范文
- 人教部编版四年级语文上册习作《我和-过一天》精美课件
- 【同步提优】部编版三语下第四单元各类阅读真题(含小古文、非连续性文本等)名师解析连载
- 算法设计与分析 课件 6.8-贪心法总结
- 2024年惠州客运从业资格证考试培训试题和答案
- 2024年日照旅客运输从业资格证考试题库
- 2024年泰安道路旅客运输从业资格考试
- 2024年扬州客运从业资格证模拟考试练习题
- 吉首大学《媒体编辑》2021-2022学年第一学期期末试卷
- 动物细胞培养技术.ppt
- 金属压型夹芯板屋面施工工艺工法
- 色谱柱Agilent安捷伦化色谱柱介绍
- 海上风电基本术语(中英文对照)
- 井下电机车管理规定
- 银行分行“职工之家”活动室管理暂行规定
- 医疗器械生产场地的相关要求
- 西安赛格国际购物中心市场调查报告(31页)
- 《产品合格证》(通用格式模板)
- 电梯控制器DP30使用手册应用篇
- 综合门诊部设置标准
评论
0/150
提交评论