9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析



第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:30 选手注意: ? 试题纸共有 12 页,答题纸共有 2 页,满分 100 分。请在答题纸上 作答,写在试题纸上 的一律无效。 ? 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅 任何书籍资料。 一、单项选择题(共 15 题,每题 1.5 分

,共计 22.5 分;每题有且仅 有一个正确选项) 1.一个 32 位整型变量占用()个 字节。 A.4 B.8 C.32 D.128

2.二进制数 11.01 在十进制下是() 。 A.3.25 B.4.125 C.6.25 D.11.125

3.下面的故事与()算法有着异曲同工之妙。 从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:?从 前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事: ‘从前 有座山,山里有座庙,庙里有个老和尚给小和尚讲故事....’? A.枚举 B.递归 C.贪心 D.分治

4.1948 年, ()将热力学中的熵引入信息通信领域,标志着信息论研 究的开端。

A.冯·诺伊曼(John von Neumann) C.欧拉(Leonhard Euler) Shannon)

B.图灵(Alan Turing) D.克劳德·香农(Claude

5.已知一棵二叉树有 2013 个节点,则其中至多有()个节点有 2 个 子节点。 A.1006 B.1007 C.1023 D.1024

6.在一个无向图中,如果任意两点之间都存在路径相 连,则称其为连通图。右图是一个有 5 个顶点、8 条 边的连通图。若要使它不再是连通图,至少要删去其 中的()条边。 A.2 B.3 C.4 D.5

7.斐波那契数列的定义如下:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果 用下面的函数计算斐波那契数列的第 n 项,则其时间复杂度为() 。 int F(int n) { if(n<=2) return 1; else return F(n-1)+F(n-2); } A.O(1) B.O(n) C.O(n2) D.O(Fn)

8.二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节

点的值、小于其右子树上所有节点的值。那么,二叉查找树的()是 一个有序序列。 A.先序遍历 B.中序遍历 C.后序遍历 D.宽度优先遍历

9.将(2,6,10,17)分别存储到某个地址区间为 0~10 的哈希表中,如果 哈希函数 h(x)=() ,将不会产生冲突,其中 a mod b 表示 a 除以 b 的 余数。 A.x mod 11 C.2x mod 11 B.x2mod 11 D.

10.IPv4 协议使用 32 位地址, 随着其不断被分配, 地址资源日趋枯竭。 因此,它正逐渐被使用()位地址的 IPv6 协议所取代。 A.40 B.48 C.64 D.128

11.二分图是指能将顶点划分成两个部分,每一部分内的顶点间没有 边相连的简单无向图。那么,12 个顶点的二分图至多有()条边。 A.18 B.24 C.36 D.66

12.()是一种通用的字符编码,它为世界上绝大部分语言设定了统 一并且唯一的二进制编码,以满足跨语言、跨平台的文本交换。目前 它已经收录了超过十万个不同字符。 A.ASCII B.Unicode C.GBK 2312 D.BIG5

13.把 64 位非零浮点数强制转换成 32 位浮点数后,不可能() 。 A.大于原数 B.小于原数 C.等于原数 D.与原数符号相反

14.对一个 n 个顶点、 m 条边的带权有向简单图用 Dijkstra 算法计算单 源最短路时,如果不使用堆或其它优先队列进行优化,则其时间复杂

度为() 。 A.O(mn+n3) B.O(n2) C.O((m+n)log n) D.O((m+n2)log n)

15.T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数, 且有递归式 T(n)=2*T(n/2)+2n,那么 T(n)=() 。 A.Θ(n) B.Θ(n log n) C.Θ(n2) D.Θ(n2log n)

二、不定项选择题(共 5 题,每题 1.5 分,共计 7.5 分;每题有一个 或多个正确选项,多选或少选均不得分) 1.下列程序中,正确计算 1,2,?,100 这 100 个自然数之和 sum(初始 值为 0)的是() 。 A. for(i=1;i<=100;i++) sum+=i; B. i=1; while(i>100){ sum+=i; i++; } C. i=1; do{ sum+=i; i++; }while(i<=100); D. i=1; do{ sum+=i; i++; }while(i>100);

2.()的平均时间复杂度为 O(n log n),其中 n 是待排序的元素个数。 A.快速排序 B.插入排序 C.冒泡排序 D.归并排序

3.以 A0 作为起点,对下面的无向图进行深度优先遍历时(遍历的顺

序与顶点字母的下标无关) ,最后一个遍历到的顶点可能是() 。

A.A1

B.A2

C.A3

D.A4

4.()属于 NP 类问题。 A.存在一个 P 类问题 B.任何一个 P 类问题 C.任何一个不属于 P 类的问题 D.任何一个在(输入规模的)指数时间内能够解决的问题 5.CCF NOIP 复赛考试结束后,因()提出的申诉将不会被受理。 A.源程序文件名大小写错误 B.源程序保存在指定文件夹以外的位置 C.输出文件的文件名错误 D.只提交了可执行文件,未提交源程序 三、问题求解(共 2 题,每题 5 分,共计 10 分;每题全部答对得 5 分,没有不得分) 1.某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s1,s2,?,sn,均为 0 或 1。该系统每次随机生成 n 个数 a1,a2,?,an,均为 0 或 1,请用户回答(s1a1+s2a2+?+snan)除以 2 的余数。如果多次的回 答总是正确, 即认为掌握密码。 该系统认为, 即使问答的过程被泄露, 也无助于破解密码——因为用户并没有直接发送密码。

然而,事与愿违。例如,当 n=4 时,有人窃听了以下 5 次问答:

就 破 解 出 了 密 码 s1=_________ , s2=_________ , s3=_________ , s4=_________。 2.现有一只青蛙,初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上 时,下一时刻将等概率地随机跳到 1,2,?,k 号荷叶之一上,直至跳到 1 号荷叶为止。当 n=2 时,平均一共跳 2 次;当 n=3 时,平均一共跳 2.5 次。则当 n=5 时,平均一共跳_________次。

四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.#include<iostream> #include<string > using namespace std;

int main( ) { string Str; cin>>str; int n = str.size( );

bool isPlalindrome = true; for (int i =0; i<n/2;i++){ if (str[i] !=str[n-i-1]) isPlalindrome = false; } if(isPlalindrome) cout << ”Yes” << endl; else cout << ”No” << endl; } 输入:abceecba 输出:_________ 2. #include<iostream> using namespace std;

int main( ) { int a,b,u,v,i, num;

cin >>a>>b>>u>>v; num =0; for ( i= a; I <=b; i++) if (((i%u) ==0)||((i%v)==0)) num ++;

count <<num<<endl; return 0; } 输入:1 1000 10 15 输出:_________ 3. #include<iostream> using namespace std;

int main( ) { const int SIZE = 100; int height[SIZE], num[SIZE], n, ans; cin>>n; for (int i=0; i<n; i++) { cin >>height[i]; num[i]= 1; for (int j=0; j<i; j++) { if ((height[j]<height[i])&&(num[j]>= num[i])) num[i] =num[j]+1; } } ans =0;

for(int I = 1; i<n;

i++){

if(num[i] >ans) ans =num[j]; } Cout <<ans<<endl; } 输入: 8 3 2 5 11 12 7 4 10 输出:_________ 4.#include<iostream> #include<string > using namespace std;

const int SIZE = 100; int n, m, p, a[SIZE] [SIZE], count;

void colour (int x, int y) { Count++; a[x][y] = 1; if ((x > 1)&& (a[x-1][y] == 0)) colour( x - 1, y);

if ((y> 1)&& (a[x][y-1] == 0)) colour( x, y- 1); if ((x < n)&& (a[x+1][y] == 0)) colour( x +1, y); if ((y < m)&& (a[x][y+1] == 0)) colour( x, y+1); }

int main( ) { int i, j, x, y, ans;

memset(a, 0, sizeof(a)); cin >>n>>m>>p; for(i =1 ; I <=p; i++) { cin>>x>>y; a[x][y] = 1; } ans = 0; for (i =1; i <=n; i++) for (j =1; j <=m;j++) if (a[i][j] == 0)

{count = 0; colour (i , j); if (ans <count) ans <count; } count<<ans<<endl; return 0; } 输入: 659 14 23 24 32 41 43 45 54 64 输出:_________ 五、完善程序(第 1 题 15 分,第 2 题 13 分,共计 28 分) 1.(序列重排)全局数组变量 a 定义如下:

Const int

SIZE

= 100;

int a[SIZE],n; 它记录着一个长度为 n 的序列 a[1],a[2],?,a[n]。 现在需要一个函数,以整数 p(1≤p≤n)为参数,实现如下功能: 将序列 a 的前 p 个数与后 n–p 个数对调,且不改变这 p 个数(或 n –p 个数)之间的相对位置。例如,长度为 5 的序列 1,2,3,4,5,当 p=2 时重排结果为 3,4,5,1,2。 有一种朴素的算法可以实现这一需求,其时间复杂度为 O(n)、空 间复杂度为 O(n):
void swap1(int p) { int i, j, b[SIZE]; for (i = 1; i <= p; i++) b[ ( 1) ] = a[i]; for (i = p + 1; i <= n; i++) b[i - p] = a[i]; for (i = 1; i <= n; i++) a[i] = b[i];

//(2 分)

} 我们也可以用时间换空间,使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算法: void swap2(int p) { int i, j, temp; for (i = p + 1; i <= n; i++) { temp = a[i]; for (j = i; j >= (2) ; j--) a[j] = a[j - 1]; (3) = temp; }

//(2 分 ) //(2 分 )

} 事 实 上 , 还 有 一 种 更 好 的 算 法 , 时 间 复 杂 度为O( n)、空间复杂度为O(1): void swap3(int p) { int start1, end1, start2, end2, i, j, temp;

start1 = 1; end1 = p; start2 = p + 1; end2 = n; while (true) { i = start1; j = start2; while ((i <= end1) && (j <= end2)) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j++; } if (i <= end1) start1 = i; e l s ei f( ( 4 ) ){ //(3 分 ) s t a r t 1= ( 5 ) //(3 分 ) endl = ( 6 ) //(3 分 ) start2 = j; } else break; } } 2.(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如 有 多 个子序列并列最长,输出任意一个即可。例如,序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中, 有两段满足条件的最长子序列,长度均为 7,分别用下划线和上划线标出。 #include <iostream> using namespace std; int main() { const int SIZE = 100; int n, i, j, a[SIZE], cur1, cur2, count1, count2, ans_length, ans_start, ans_end; //cur1, cur2 分别表示当前子序列中的两个不同整数 //count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数 cin>>n; for (i = 1; i <= n; i++) cin>>a[i]; i = 1; j = 1; //i, j 分别表示当前子序列的首尾,并保证其中至多有两个不同整数 while ((j <= n) && (a[j] == a[i]))

j++; cur1 = a[i]; cur2 = a[j]; count1 = ( 1 ) //(3 分 ) count2 = 1; ans_length = j - i + 1; while (j < n) { j++; if (a[j] == cur1) count1++; else if (a[j] == cur2) count2++; else { if (a[j - 1] == (2) ) { //(3 分 ) while (count2 > 0) { if (a[i] == cur1) count1--; else count2--; i++; } cur2 = a[j]; count2 = 1; } else { while (count1 > 0) { if (a[i] == cur1) (3) //(2 分 ) else (4) //(2 分 ) i++; } (5) //(3 分 ) count1 = 1; } } if (ans_length < j - i + 1) { ans_length = j - i + 1; ans_start = i; ans_end = j; } } for (i = ans_start; i <= ans_end; i++) cout<<a[i]<<' '; return 0; }

答案解析 一、单选题(15*1.5) 1、A,一个字节有 8 个 bit,32 位整型变量占用 4 个字节,故选 A。 2、A,二进制 11.01 转为十进制, (11.01)2 = 1*2+1+0*0.5+1*0.25 = (3.25)10 。 3、B,老和尚给小和尚讲的故事里边有故事本身,递归是函数内部调 用函数本身,故选 B,递归。 4、D,香农信息论鼻祖。 5、A,一定是满二叉树时拥有 2 个字节点的节点数最多,最下一层会 有 2013-1023=990 个节点,于是倒数第二层会有 990/2=495 个节点有 2 个字节点, 从第 1 层到倒数第三层共有 1023-2^9=511 个节点, 且这 些节点都是用 2 个子节点的节点,所以共有 495+511=1006 个,选 A。 6、B,要使图不联通,只要其中某一个节点不连通即可,所有顶点度 最少是 3,所以最少需要删除 3 条边,选 B。 7、D,此题最开始一眼扫到的时候脑子进水,跟学生将选 B,O(n) , 实际上不是,计算 F1 需要 1 次,计算 F2 需要一次,计算 Fn 需要计 算 F(n-1)的次数加上 F(n-2)的次数,所以其实就是计算 Fn 次,于 是答案选择 D,至于这个 Fn 到底是多大,数学上可以计算,它等于 O(((1+sqrt(5))/2)^n). 8、B,这个必须是 B,没有什么好说的,中序遍历保证左边都是小于 根的,右边都是大于根的,所以可以保证是一个有序序列。 9、D,A 项 6 和 17 对 11 取余都是 6 发生冲突,B 项 10 的平方和 17

的平方对 11 取余都是 1 发生冲突,C 项 6 的两倍和 17 的两倍对 11 取余都是 1 发生冲突,D 项分别为 1,2,3,4,不冲突。 10、D,IPV6 地址是 128 位的。谢谢网友指正! 11、C,二分为 6 个和 6 个的顶点,此时边最多,有 36 条边。 12、B,我的学生几乎全选 A 去了,因为之前讲题只介绍过 ASCII 码, 但是看到统一二字也应该想到 Uni...前缀啊。 13、D,64 位非零浮点数强制转换成 32 位浮点数,两个数会有大小 上的细微差别,但不会发生符号变化,因为有专门的符号位。 14、B,Dijkstra 算法计算单源最短路时间复杂度如果不借助堆或优先 队列优化,是 O(n^2). 15、B,此题和学生讲的时候又是脑子进水了,我一眼扫以为选 A, 后来令 n=2,4,8,16 等值带如递推式,发现计算出来的 T(n)和 n 不成线性关系, 也不成 n^2 关系, 仔细研究了一下, 发现其实是 nlgn, 具体可以画图证明。 二、不定项选择题(5*1.5) 1、AC,求 1,2,...100 的和,这个平时练习过很多次。 2、AD,只有快速排序和归并排序是 nlgn 的,冒泡和插入都是 n^2 的 时间复杂度。 3、CD,此题最开始以为选 BD,因为我题目错看成宽度优先搜索了。 4、AB,如果一个问题复杂度是该问题的一个实例规模 n 的多项式函 数,则这种可以在多项式时间内解决的问题属于 P 类问题;可以在多 项式时间内验证一个解是否正确的问题称为 NP 类问题;可以在多项

式时间内解决的问题一定可以在多项式时间内验证, 所以 P 类问题一 定属于 NP 类问题,故此题应选择 AB,D 我看错了,NP 类问题显然 不是说在指数时间内能够解决的问题,谢谢网友提示! 。 5、ABCD,此题完全不会,因为是第一次带学生参赛,对复赛什么情 况完全不了解,个人觉得程序名、输出文件名这类问题不应该是什么 大问题应该允许申诉,但对 BD 这些没按规定要求做的肯定不会受理 的,网友回复说选 ABCD,那就暂时改为 ABCD,如有其他声音,欢迎 批评指正。 三、问题求解(2*5) 1、0 1 1 1;此题应该算是简单题,密码都是 0 或 1,所以根据第 5 项 可以很轻松得到 S1=0,再根据第 1 项可以得到 S2=1,再根据第 3 项 可以 S3=1,最后根据第 2 项得到 S4=1,然后利用第 4 项进行验证发 现可行。 2、37/12,此题最开始看到做不出来,只知道这是一道求数学期望的 题目。 计算 n=2 为什么平均一共跳 2 次的时候, 我最开始是这么想的, 1 次跳到 1 处的概率是 1/2,2 次的概率是 1/4,3 次是 1/8.。 。 。于是数 学期望 Ex=1*1/2+2*1/4+3*1/8+......=2,但是这样的计算对于后边 n=3, 得情况却怎么都算不了,于是想到递归,设从 2 跳到 1 的期望是 f2, 那么有 1/2 的概率是一次跳到 1,还有 1/2 的概率是(1+f2)次跳到 1, 即第一次没有跳到 1,跳到 2 的情况,于是可以列出等式:f2=1*1/2+ (1+f2)*1/2,解出 f2=2;对于 n=3,则有 1/3 的概率一次跳到 1,有 1/3 的概率(1+f2)次跳到 1,即第一次跳到 2,再从 2 跳到 1 的过程,

最后还有 1/3 的概率 (1+f3) 次跳到 1, 于是 f3=1/3+ (1+f2) *1/3+ (1+f3) *1/3,解出 f3=2.5;同理 f4=1/4+(1+f2)*1/4+(1+f3)*1/4+(1+f4) *1/4, 解出 f4=17/6; f5=1/5+ (1+f2)*1/5+(1+f3)*1/5+(1+f4)*1/5+(1+f5)*1/5, 解出 f5=37/12. 四、阅读程序写结果(4*8) 1、 Yes, 此程序判断给定字符串是否是回文串。 显然输入串"abceecba" 是回文串。 2、133,此题计数 1-1000 范围内能够整除 10 或 15 的数有多少个, 使 用 容 斥 原 理 或 者 集 合 求 并 很 容 易 可 以 得 到 1000/10+1000/15-1000/30=133. 3、 4, 此题实际上是一种简单的动态规划的方法找最长递增串的长度, 从输入数据 3 2 5 11 12 7 4 10 来看,显然最长的递增串可以是 3 5 11 12,长度为 4; 4、7,似乎二分图染色问题,手动模拟出结果为 7. 五、完善程序(15+13) 1、n-p+i i-p+1 a[i-p] i>end1 i j-1; 序列重排还是比较简单的一道题目,第一种方法是通过开一个 b 数 组, 然后先将 a 数组中 1 到 p 的数复制到 b 数组中 n-p+1 到 n, 将 p+1 到 n 区间的数复制到 b 数组 1,n-p,最后再将 b 数组元素复制回 a 数组中;显然第一空是 n-p+i。 第二种方法是以时间换空间的方法, 每一次先将要移到前面的数保存 在 temp 中,然后将前面那 p 个数依次往后移,再将空出来的那个位

置存 temp;所以第二个空和第三个空分别是 i-p+1 和 a[i-p]。 第三种方法的实际上是一种递归的思想,第四、五、六空分别是 i〉 end1 i,i,j-1 2、j-i cur1 count1--; count2--; cur1=a[j],此题没什么好说的,题 目中的注释已经讲得很明白了。



更多相关文章:
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:20...
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析
第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:...
2013第十九届全国青少年信息学奥林匹克联赛初赛提高组(C++)
2013第十九届全国青少年信息学奥林匹克联赛初赛提高组(C++)_学科竞赛_高中教育_教育专区。C++ 2013 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 ...
NOIP2013第十九届信息学奥林匹克竞赛全国联赛提高组参考答案
NOIP2013第十九届全国青少年信息学奥林匹克联赛初赛 提高组参考答案一、单项选择题...C++语言 C语言 n-p+i i-p+1 a[i–p] j<=end2 i(或start2, 或end...
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题及答案PASCAL)
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛试题及答案(提高组试题...一个正确选 项) 1.以下哪个是面向对象的高级语言( A. 汇编语言 B. C++ )...
第十二届全国青少年信息学奥林匹克联赛初赛试题及答案(普及组、C语言
第十二届全国青少年信息学奥林匹克联赛初赛试题及答案...C.C++是历史上的第一个支持面向对象的计算机语言 D...2014年注册会计师考试攻略 2013年注会经济法统考真题...
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)
NOIP(2014)第二十届全国青少年信息学奥林匹克联赛初赛(普及组试题及答案)_学科...C++ C. Fortran D. Basic 2、1TB 代表的字节数量是( )。 A.2 的 10 ...
2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)
2015年第二十一届全国青少年信息学奥林匹克联赛提高组初赛试题(C++)_学科竞赛_高中教育_教育专区。2015 年第二十一全国青少年信息学 奥林匹克竞赛初赛 提高组一...
2009-2013年NOIP初赛提高组C++语言试题及参考答案
2009-2013 年 NOIP 初赛提高组 C++语言试题 2013 第十九届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:30...
第十届全国青少年信息学奥林匹克联赛初赛试题及答案 c语言
第十届全国青少年信息学奥林匹克联赛初赛试题及答案 c语言_学科竞赛_初中教育_...A. C++ B. Object Pascal C. C D. Smalltalk E. Java 13. 由 3 个 a...
更多相关标签:
小学奥林匹克信息学    奥林匹克信息学竞赛    青少年信息学奥林匹克    奥林匹克信息学有用吗    奥林匹克信息学    奥林匹克信息学 江苏    奥林匹克信息学试题    中国化学奥林匹克初赛    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图