当前位置:首页 >> 学科竞赛 >>

2009-2013年NOIP初赛提高组C++语言试题及参考答案


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

等)或查阅任何书籍资料。

一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项) 1.一个 32 位整型变量占用(B)个字节。 2.二进制数 11.01 在十进制下是() 。 A.4 A.3.25 B.8 C.32 B.4.125 D.128 C.6.25 D.11.125

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

4.1948 年, (C)将热力学中的熵引入信息通信领域,标志着信息论研究的开端。 A.冯·诺伊曼(John von Neumann) C.欧拉(Leonhard Euler) B.图灵(Alan Turing) D.克劳德·香农(Claude Shannon)

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

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

7.斐波那契数列的定义如下:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。如果用下面的函数计算斐 波那契数列的第 n 项,则其时间复杂度为(D) 。 int { 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) F(int n)

1

8.二叉查找树具有如下性质:每个节点的值都大于其左子树上所有节点的值、小于其右子树 上所有节点的值。那么,二叉查找树的(B)是一个有序序列。 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 位地址,随着其不断被分配,地址资源日趋枯竭。因此,它正逐渐被使 用(D)位地址的 IPv6 协议所取代。 A.40 B.48 C.64 D.128

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

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

13.把 64 位非零浮点数强制转换成 32 位浮点数后,不可能(B) 。 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)的是(AC) 。 A. for(i=1;i<=100;i++) sum+=i; B. i=1; while(i>100){ sum+=i; i++; } C. i=1; D. i=1;

2

do{ sum+=i; i++; }while(i<=100);

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.源程序文件名大小写错误 C.输出文件的文件名错误 B.源程序保存在指定文件夹以外的位置 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 时,平均一共跳_________次。

3

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

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

isPlalindrome = true; i =0; i<n/2;i++){ isPlalindrome = false;

for (int

if (str[i] !=str[n-i-1]) } if(isPlalindrome) cout << ”Yes” << endl; else cout << ”No” << endl; } 输入:abceecba 输出:___yes______ 2. #include<iostream> using namespace std;

int {

main( )

int

a,b,u,v,i, num;

cin >>a>>b>>u>>v; num for =0; ( i= a; i<=b; i++)
4

if (((i%u) ==0)||((i%v)==0)) num ++; cout <<num<<endl; return } 输入:1 1000 10 15 输出:__133_______ 3. #include<iostream> using namespace std; 0;

int {

main( )

const int

int

SIZE = 100; num[SIZE], n, ans;

height[SIZE],

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
5

输出:_________ 4.#include<iostream> #include<string > using namespace std;

const int n,

int m,

SIZE = 100; p, a[SIZE] [SIZE], count;

void {

colour

(int

x,

int

y)

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

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

memset(a,

0,

sizeof(a));

cin >>n>>m>>p; for(i =1 ; I <=p; cin>>x>>y; a[x][y] }
6

i++) {

= 1;

ans for

=

0;

(i =1; i <=n; i++) for (j =1; j <=m;j++) if (a[i][j] {count colour if = == 0; 0)

(i , j);

(ans <count) ans <count;

} count<<ans<<endl; return } 输入: 6 5 9 1 4 2 3 2 4 3 2 4 1 4 3 4 5 5 4 6 4 输出:_________ 五、完善程序(第 1 题 15 分,第 2 题 13 分,共计 28 分) 1.(序列重排)全局数组变量 a 定义如下: Const int int SIZE = 100; 0;

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):
7

void swap1(int p) { int i, j, b[SIZE];

for (i = 1; i <= p; i++) b[ ( 1) ] = a[i]; //(2 分)

for (i = p + 1; i <= n; i++) b[i - p] = a[i]; for (i = 1; i <= n; i++) a[i] = b[i]; } 我们也可以用时间换空间,使用时间复杂度为 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--) //(2 分 )

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

start1 = 1; end1 = p; start2 = p + 1; end2 = n;
8

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( s t a r t 1= endl = ( 4 ) ( 5 ) ( 6 ) ){ //(3 分 ) //(3 分 ) //(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,
9

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 = 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 分 ) ( 1 ) //(3 分 )

while (count2 > 0) { if (a[i] == cur1) count1--; else count2--; i++; } cur2 = a[j];
10

count2 = 1; } else { while (count1 > 0) { if (a[i] == cur1) (3) else (4) i++; } (5) 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; } //(3 分 ) //(2 分 ) //(2 分 )

11

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

一、单项选择题(共 10 题,每题 1.5 分,共计 15 分;每题有且仅有一个正确选项) 1.目前计算机芯片(集成电路)制造的主要原料是(A) ,它是一种可以在沙子中提炼出的物 质。 A.硅 B.铜 C.锗 D.铝

2.(B)是主要用于显示网页服务器或者文件系统的 HTML 文件内容,并让用户与这些文件交 互的一种软件。 A.资源管理器 B.浏览器 C.电子邮件 D.编译器

3.目前个人电脑的(B)市场占有率最靠前的厂商包括 Intel、AMD 等公司。 A.显示器 B.CPU C.内存 D.鼠标

4.无论是 TCP/IP 模型还是 OSI 模型,都可以视为网络的分层模型,每个网络协议都会被归入 某一层中。如果用现实生活中的例子来比喻这些“层” ,以下最恰当的是( B) 。 A.中国公司的经理与伊拉克公司的经理交互商业文件

B.军队发布命令

12

C.国际会议中,每个人都与他国地位对等的人直接进行会谈

D.体育比赛中,每一级比赛的优胜者晋级上一级比赛

5.如果不在快速排序中引入随机化,有可能导致的后果是()B。 A.数组访问越界 C.排序结果错误 B.陷入死循环 D.排序时间退化为平方级

6.1946 年诞生于美国宾夕法尼亚大学的 ENIAC 属于(A)计算机。 A.电子管 B.晶体管 C.集成电路 D.超大规模集成电路

7.在程序运行过程中,如果递归调用的层数过多,会因为(A)引发错误。 A.系统分配的栈空间溢出 C.系统分配的队列空间溢出 B.系统分配的堆空间溢出 D.系统分配的链表空间溢出

8.地址总线的位数决定了 CPU 可直接寻址的内存空间大小,例如地址总线为 16 位,其最大的 可寻址空间为 64KB。如果地址总线是 32 位,则理论上最大可寻址的内存空间为(D) 。 A.128KB B.1MB C.1GB D.4GB

9.以下不属于目前 3G(第三代移动通信技术)标准的是(B) 。 A.GSM B.TD-SCDMA C.CDMA2000 D.WCDMA

10.仿生学的问世开辟了独特的科学技术发展道路。 人们研究生物体的结构、 功能和工作原理, 并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述,错误的是(B) 。 A.由研究蝙蝠,发明雷达 C.由研究海豚,发明声纳 B.由研究蜘蛛网,发明因特网 D.由研究电鱼,发明伏特电池

二、不定项选择题(共 10 题,每题 1.5 分,共计 15 分;每题有一个或多个正确选项,多选
13

或少选均不得分) 1.如果对于所有规模为 n 的输入,一个算法均恰好进行()次运算,我们可以说该算法的时 n 间复杂度为 O(2 )。 A.2n+1 B.3n C.n*2n D.22n )进行广度优先搜索( BFS )时,一种可能的遍历顺序是

2.从顶点 A0 出发,对有向图( A0,A1,A2,A3,A4。

3.如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为 a,b,c(如右图所示) ,另有元素 d 已经出栈,则可能的入栈顺序有 (D) 。 A.a,b,c,d B.b,a,c,d C.a,c,b,d D.d,a,b,c

4.在计算机显示器所使用的 RGB 颜色模型中, ()属于三原色之一。 A.黄色 B.蓝色 C.紫色 D.绿色

5.一棵二叉树一共有 19 个节点,其叶子节点可能有(B)个。 A.1 B.9 C.10 D.11

6.已知带权有向图 G 上的所有权值均为正整数,记顶点 u 到顶点 v 的最短路径的权值为 d (u, v) 。若 v1 ,v2 ,v3 ,v4 ,v5 是图 G 上的顶点,且它们之间两两都存路径可达,则以下说法正确 的有( ) 。 A. v1 到 v 2 的最短路径可能包含一个环 B. d (v1 , v2 ) ? d (v2 , v1 ) C. d (v1, v3 ) ? d (v1, v2 ) ? d (v2 , v3 ) D.如果 v1 ? v2 ? v3 ? v4 ? v5 是 v1 到 v5 的一条最短路径,那么 v2 ? v3 ? v4 是 v 2 到 v 4 的 一条最短路径 7.逻辑异或( ? )是一种二元运算,其真值表如下所示。 a False False True True b False True False True
a?b

False True True Flase ) 。

以下关于逻辑异或的性质,正确的有( A.交换律: a ? b ? b ? a B.结合律: (a ? b) ? c ? a ? (b ? c)

14

C.关于逻辑与的分配律: a ? (b ? c) ? (a ? b) ? (a ? c) D.关于逻辑或的分配律: a ? (b ? c) ? (a ? b) ? (a ? c) 8.十进制下的无限循环小数(不包括循环节内的数字均为 0 成均为 9 的平凡情况) ,在二进 制下有可能是( ) 。 A.无限循环小数(不包括循环节内的数字均为 0 或均为 9 的平凡情) B.无限不循环小数 C.有限小数 D.整数 9. ( C )是目前互联网上常用的 E-mail 服务协议。 B.FTP C.POP3 D.SMTP ) 。

A.HTTP

10.以下关于计算复杂度的说法中,正确的有(

A.如果一个问题不存在多项式时间的算法,那它一定是 NP 类问题 B.如果一个问题不存在多项式时间的算法,那它一定不是 P 类问题 C.如果一个问题不存在多项式空间的算法,那它一定是 NP 类问题 D.如果一个问题不存在多项式空间的算法,那它一定不是 P 类问题 三、问题求解(共 2 题,每题 5 分,共计 10 分) 1.本题中,我们约定布尔表达式只能包含 p,q,r 三个布尔变量,以及“与” (∧) 、 “或” (∨) 、 “非” (?)三种布尔运算。如果无论 p,q,r 如何取值,两个布尔表达式的值总是相同,则称 它们等价。例如,(p∨q)∨r 和 p∨(q∨r)等价,p∨?p 和 q∨?q 也等价;而 p∨q 和 p∧q 不 等价。那么,两两不等价的布尔表达式最多有_________个。 2.对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图 1 有 5 个不同的 独立集(1 个双点集合、3 个单点集合、1 个空集) ,图 2 有 14 个不同的独立集。那么,图 3 有_________个不同的独立集。

四、阅读程序写结果(共 4 题,每题 8 分,其中第 3 题的 2 个小题各 4 分,共计 32 分) 1. #include<iostream> using namespace std; int n,i,temp,sum,a[100]; int main()
15

{ cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n-1;i++) if(a[i]>a[i+1]){ temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; } for(i=n;i>=2;i--) if(a[i]<a[i-1]){ temp=a[i]; a[i]=a[i-1]; a[i-1]=temp; } sum=0; for(i=2;i<=n-1;i++) sum+=a[i]; cout<<sum/(n-2)<<endl; return 0; } 输入: 8 40 70 50 70 20 40 10 30 输出:___41______

2.

#include<iostream> using namespace std; int n,i,ans; int gcd(int a,int b) {
16

if(a%b==0) return b; else return gcd(b,a%b); } int main() { cin>>n; ans=0; for(i=1;i<=n;i++) if(gcd(n,i)==i) ans++; cout<<ans<<endl; } 输入:120 输出:____16_____

3.

#include<iostream> using namespace std; const int SIZE=20; int data[SIZE]; int n,i,h,ans; void merge() { data[h-1]=data[h-1]+data[h]; h--; ans++; } int main() { cin>>n; h=1;
17

data[h]=1; ans=0; for(i=2;i<=n;i++) { h++; data[h]=1; while(h>1&&data[h]==data[h-1]) merge(); } cout<<ans<<endl; } (1) 输入:8 输出:_7________(4 分) (2) 输入:2012 输出:__2004_______(4 分)

4.

#include<iostream> #include<string> using namespace std; int lefts[20],rights[20],father[20]; string s1,s2,s3; int n,ans; void calc(int x,int dep) { ans=ans+dep*(s1[x]-'A'+1); if(lefts[x]>=0)calc(lefts[x],dep+1); if(rights[x]>=0)calc(rights[x],dep+1); } void check(int x) {
18

if(lefts[x]>=0)check(lefts[x]); s3=s3+s1[x]; if(rights[x]>=0)check(rights[x]); } void dfs(int x,int th) { if(th==n) { s3=""; check(0); if(s3==s2) { ans=0; calc(0,1); cout<<ans<<endl; } return; } if(lefts[x]==-1&&rights[x]==-1) { lefts[x]=th; father[th]=x; dfs(th,th+1); father[th]=-1; lefts[x]=-1; } if(rights[x]==-1) { rights[x]=th; father[th]=x; dfs(th,th+1); father[th]=-1;
19

rights[x]=-1; } if(father[x]>=0) dfs(father } int main() { cin>>s1; cin>>s2; n=s1.size() memset(lefts, memset(rights memset(father dfs(0,1); } 输入: ABCDEF BCAEDF 输出:_________ 五、完善程序(第 1 题第 2 空 3 分,其余每空 2.5 分,共计 28 分) 1.(排列数)输入两个正整数 n,m(1≤n≤20,1≤m≤n),在 1~n 中任取 m 个数,按字典序从 小到大输出所有这样的排列。例如 输入:3 2 输出:1 2 1 3 2 1 2 3 3 1 3 2 #include<iostream> #include<cstring> Using namespace std;

20

Const int

SIZE=25;

bool used[SIZE]; int data[SIZE]; int n,m,i,j,k; bool flag;

int main() { cin>>n>>m; memset(used,false,sizeof(used)); for(i=1;i<=m;i++) { data[i]=i; used[i]=true; } flag=true; while(flag) { for(i=1;i<=m-1;i++)cout<<data[i]<<""; cout<<data[m]<<endl; flag= for(i=m;i>=1;i--) { ② ; ① ;

for(j=data[i]+1;j<=n;j++)if(!used[j]) { used[j]=true; data[i]=③ flag=true; break;
21

;

} if(flag) { for(k=i+1;k<=m;k++) for(j=1;j<=④ { data[k]=j; used[j]=true; break; } ⑤ } } } } 2.(新壳栈)小 Z 设计了一种新的数据结构“新壳栈” 。首先,它和传统的栈一样支持压入、 弹出操作。此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中,c>2 是一个固定的 正整数,表示壳的厚度。小 Z 还希望,每次操作,无论是压入、弹出还是翻转,都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗? 程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c,之后每行输入都 是一条指令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个,应当输出相 应的错误信息。 指令 涵义 ; ;j++)if(!used[j])

1[空格]e 在栈顶压入元素 e 2 3 0 弹出(并输出)栈顶元素 翻转栈顶的前 c 个元素 退出 表 1:指令的涵义

22

栈中的元素 输入 输出 (左为栈底,右 说明 为栈顶) 输入正整数 c 1 1 2 1 2 3 1 2 3 4 1 4 3 2 1 4 3 2 5 1 4 5 2 3 3 2 5 错误信息 4 1 错误信息 1 4 5 2 1 4 5 1 4 1 4 1 空 空 空 压入元素 1 压入元素 2 压入元素 3 压入元素 4 翻转栈顶的前 c 个元素 压入元素 5 翻转栈顶的前 c 个元素 弹出栈顶元素 3 弹出栈顶元素 2 弹出栈顶元素 5 由于栈中元素不足 c 个,无法翻转,故操作失败,输 出错误信息 弹出栈顶元素 4 弹出栈顶元素 1 由于栈中元素不足 c 个,无法翻转,故操作失败,输 出错误信息 退出 表 2:输入输出样例 #include<iostream> using namespace std;

3 1 1 1 2 1 3 1 4 3 1 5 3 2 2 2 3 2 2 2 0

const

int

23

NSIZE=100000, CSIZE=1000; int n,c,r,tail,head,s[NSIZE],q[CSIZE]; //数组 s 模拟一个栈,n 为栈的元素个数 //数组 q 模拟一个循环队列,tail 为队尾的下标,head 为队头的下 bool direction,empty;

int previous(int k) { if(direction) return((k+c-2)%c)+1; else return(k%c)+1; }

int next(int k) { if(direction) ① else return((k+c-2)%c)+1; } ;

void push() { int element;

cin>>element; if(next(head)==tail){ n++; ② ;

tail=next(tail);
24

} if(empty) empty=false; else head=next(head); ③=element; } void pop() { if(empty){ cout<<"Error:the stack is empty!"<< return; } cout<<④<<endl; if(tail==head) empty=true; else{ head=previous(head); if(n>0){ tail=previous(tail); ⑤ n--; } } } =s[n];

void reverse() { int temp; if(⑥ ==tail){

direction=!direction; temp=head;
25

head=tail; tail=temp; } else cout<<"Error:less than"<<c<<"elements in the stack!"<<endl; }

int main() { cin>>c; n=0; tail=1; head=1; empty=true; direction=true; do{ cin>>r; switch(r){ case 1:push();break; case 2:pop();break; case 3:reverse();break; } }while(r!=0); return 0; }

26

2011 第十七届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 ● ● C++语言 两小时完成 ) ●●

全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效

一、单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确选项。 ) 1.在二进制下,1011001 + ( B A.1011 B .1101 )= 1100110。 C.1010 D.1111

2.字符“A”的 ASCII 码为十六进制 41,则字符“Z”的 ASCII 码为十六进制的( A ) 。 A.66 B.5A C.50 D.视具体的计算机而定 ) 。 D.ABCDEF

3.右图是一棵二叉树,它的先序遍历是( A A.ABDEFC 4.寄存器是( C A. 硬盘 B.DBEFAC C.DFEBCA

)的重要组成部分。 C. 内存 D. 中央处理器 (CPU) ) 。 D.散列表 ) 。

B. 高速缓存

5.广度优先搜索时,需要用到的数据结构是( A A.链表 B.队列

C.栈

6.在使用高级语言编写程序时,一般提到的“空间复杂度”中的空间是指( A.程序运行时理论上所占的内存空间 B.程序运行时理论上所占的数组空间 C.程序运行时理论上所占的硬盘空间 D.程序源文件理论上所占的硬盘空间

7. 应用快速排序的分治思想, 可以实现一个求第 K 大数的程序。 假定不考虑极端的最坏情况, 理论上可以实现的最低的算法时间复杂度为( ) 。 A.O (n2) B.O (n log n ) C.O (n) D D. O (1) )制定了一系列标准, D.万维网联盟(W3C)

8.为解决 web 应用中的不兼容问题,保障信息的顺利流通, ( 涉及 HTML、XML、CSS 等,并建议开发者遵循。 A.微软 B.美国计算机协会(ACM)

C.联合国教科文组织

9.体育课的铃声响了,同学们都陆续的奔向操场,按老师的要求从高到低站成一排。每个同 学按顺序来到操场时,都从排尾走到排头,找到第一个比自己高的同学,并站在他的后面。 这种站队的方法类似于( A)算法。 A.快速排序 B.插入排序 C.冒泡排序 D.归并排序

10.1956 年 ( B) 授予肖克利 (William Shockley) 、巴丁(John Bardeen)和布拉顿(Walter Brattain) A.诺贝尔物理学奖 C.图灵奖 B.约翰·冯·诺依曼奖 D.高德纳奖 (Donald E. Knuth Prize)

二、不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数不少于 1。多
27

选或少选均不得分) 。 1.如果根结点的深度记为 1,则一棵恰有 2011 个叶子结点的二叉树的深度可能是( B ) 。 A.10 B.11 C.12 ) 。 D.2011

2.在布尔逻辑中,逻辑“或”的性质有( A.交换律:PVQ = QVP C.幂等律:PVP = P

B.结合律:PV(QVR)=(PVQ)VR D.有界律:PV1 = 1(1 表示逻辑真) )位。 D.404

3.一个正整数在十六进制下有 100 位,则它在二进制下可能有( A.399 4.汇编语言( A B.400 ) 。 C.401

A.是一种与具体硬件无关的程序设计语言 B.在编写复杂程序时,相对于高级语言而言代码量大,且不易调试 C.可以直接访问寄存器、内存单元、I/O 端口 D.随着高级语言的诞生,如今已被完全淘汰,不再使用 5.现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由 4 个汉字“之” 、 “乎” 、 “者” 、 “也”组成,它们出现的次数分别为 700、600、300、400。那么, “也”字的编码长度可能是( D ) 。 A.1 B.2 C.3 D.4

6.生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识别、 虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征 识别技术及其应用的是( B ) 。

A.指静脉验证

B.步态验证

C.ATM 机密码验证

D.声音验证 A )会使逆序

7.对于序列“7、5、1、9、3、6、8、4” ,在不改变顺序的情况下,去掉( 对的个数减少 3。 A.7 B.5 C.3 D.6

8.计算机中的数值信息分为整数和实数(浮点数) 。实数之所以能够表示很大或者很小的数, 是由于使用了( B ) 。 A.阶码 B.补码 C.反码 D.较长的尾数

9. 对右图使用 Dijkstra 算法计算 S 点到其余各点的最短路径长度时, 到 B 点的距离 d[B]初始时赋为 8, 在算法的执行过程中还会出现的 值有( ) 。 A.3 B. 7 C.6 D.5

10.为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英
28

文缩写中, ( A.HTTP

)是网络协议 B.TCP/IP C.FTP D.WWW

三.问题求解(共 2 题,每空 5 分,共计 10 分) 1. 平面图可以在画在平面上, 且它的边仅在顶点上才能相交的简单无向图。 4 个顶点的平面图至少有 6 条边,如右图所示。那么,5 个顶点的平面图至 少有 条边。 2.定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说 明,对于字符串“BCA”可以将 A 移到 B 之前,变字符串“ABC” 。如果要将字符串“DACHEBGIF” 变成“ABCDEFGHI”最少需要________次操作。 四.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. #include<iostream> #include<cstring> using namespace std;

const int SIZE = 100;

int main() { int n,i,sum,x,a[SIZE];

cin>>n; memset(a,0,sizeof(a));

for(i=1;i<=n;i++){ cin>>x; a[x]++; } i=0; sum=0; while(sum<(n/2+1)){ i++; sum+=a[i];

29

} cout<<i<<endl; return 0; }

输入: 11 4 5 6 6 4 3 3 2 3 2 1 输出: 3 2. #include<iostream> using namespace std;

int n;

void f2(int x,int y);

void f1(int x,int y) { if(x<n) f2(y,x+y); }

void f2(int x,int y) { cout<<x<<' '; f1(y,x+y); }

int main() { cin>>n;
30

f1(0,1); return 0;

return 0; }

输入:30 输出:___1 2 5 13 34____________ 3. #include<iostream> using namespace std;

const int V=100;

int n,m,ans,e[V][V]; bool visited[V];

void dfs(int x,int len) { int i; visited[x]= true; if(len>ans) ans=len; for(i=1;i<=n;i++) if( (!visited[i]) && (e[x][i]!=-1) ) dfs(i,len+e[x][i]); visited[x]=false; }

int main() { int i,j,a,b,c;
31

cin>>n>>m; for(i=1;i<=n;i++) for(j=1;j<=m;j++) e[i][j]=-1; for(i=1;i<=m;i++) { cin>>a>>b>>c; e[a][b]=c; e[b][a]=c; } for(i=1;i<=n;i++) visited[i]=false; ans=0; for(i=1;i<=n;i++) dfs(i,0); cout<<ans<<endl;

return 0; }

输入: 4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60 输出:____150__________ 4. #include<iostream> #include<cstring>
32

#include<string> using namespace std;

const int SIZE=10000; const int LENGTH=10;

int n,m,a[SIZE][LENGTH];

int h(int u,int v) { int ans,i; ans=0; for(i=1;i<=n;i++) if( a[u][i]!=a[v][i]) ans++; return ans; }

int main() { int sum,i,j; cin>>n; memset(a,0,sizeof(a)); m=1; while(1) { i=1; while( (i<=n) && (a[m][i]==1) ) i++; if(i>n) break; m++;
33

a[m][i]=1; for(j=i+1;j<=n;j++) a[m][j]=a[m-1][j]; }

sum=0; for(i=1;i<=m;i++) for(j=1;j<=m;j++) sum+=h(i,j); cout<<sum<<endl; return 0; } 输入:7 输出:___57344______ 五.完善程序 (第 1 题,每空 2 分,第 2 题,每空 3 分,共 28 分) 1.(大整数开方) 输入一个正整数 n(1≤n≤10100) ,试用二分法计算它的平方根的整数部分。

#include<iostream> #include<string> using namespace std;

const int SIZE=200; struct hugeint{ int len,num[SIZE]; }; //其中 len 表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推

hugeint times(hugeint a,hugeint b) // 计算大整数 a 和 b 的乘积 { int i,j; hugeint ans; memset(ans.num,0,sizeof(ans.num));
34

for(i=1;i<=a.len;i++) for(j=1;j<=b.len;j++) ① +=a.num[i]*b.num[j];

for(i=1;i<=a.len+b.len;i++){ ans.num[i+1]+=ans.num[i]/10; ② } if(ans.num[a.len+b.len]>0) ans.len=a.len+b.len; else ans.len=a.len+b.len-1; return ans; } ;

hugeint add(hugeint a,hugeint b) //计算大整数 a 和 b 的和 { int i; hugeint ans; memset(ans.num,0,sizeof(ans.num)); if(a.len>b.len) ans.len=a.len; else ans.len=b.len; for(i=1;i<=ans.len;i++){ ans.num[i]+= ③ ;

ans.num[i+1]+= ans.num[i]/10; ans.num[i]%=10; } if(ans.num[ans.len+1]>0) ans.len++; return ans;
35

}

hugeint average(hugeint a,hugeint b) //计算大整数 a 和 b 的平均数的整数部分 { int i; hugeint ans; ans=add(a,b); for(i=ans.len;i>=2;i--){ ans.num[i-1]+=( ④ )*10;

ans.num[i]/=2; } ans.num[1]/=2; if(ans.num[ans.len]==0) ans.len--; return ans; }

hugeint plustwo(hugeint a) // 计算大整数 a 加 2 之后的结果 { int i; hugeint ans; ans=a; ans.num[1]+=2; i=1; while( (i<=ans.len)&&(ans.num[i]>=10) ){ ans.num[i+1]+=ans.num[i]/10; ans.num[i]%=10; i++; }
36

if(ans.num[ans.len+1]>0) ⑤ return ans; } ;

bool over(hugeint a,hugeint b) // 若大整数 a>b 则返回 true,否则返回 false { int i; if( ⑥ )

return false; if( a.len>b.len ) return true; for(i=a.len;i>=1;i--){ if(a.num[i]<b.num[i]) return false; if(a.num[i]>b.num[i]) return true; } return false; }

int main() { string s; int i; hugeint target,left,middle,right; cin>>s; memset(target.num,0,sizeof(target.num)); target.len=s.length(); for(i=1;i<=target.len;i++) target.num[i]=s[target.len-i]⑦ ;
37

memset(left.num,0,sizeof(left.num)); left.len=1; left.num[1]=1; right=target; do{ middle=average(left,right); if(over( ⑧ ))

right=middle; else left=middle; }while(!over(plustwo(left),right) ); for(i=left.len;i>=1;i--) cout<<left.num[i]; return 0; } 2. (笛卡尔树)对于一个给定的两两不等的正整数序列,笛卡尔树是这样的一棵二叉树:首 先,它是一个最小堆,即除了根结点,每个节点的权值都大雨父节点的权值;其次,它的中 序遍历恰好就是给定的序列。例如,对于序列 7、2、12、1、10、5、15、3,下图就是一棵 对应的笛卡尔树。现输入序列的规模 n(1≤n<100)和序列的 n 个元素,试求其对应的笛卡 尔树的深度 d(根节点深度为 1) ,以及有多少个叶子节点的深度为 d。 #include<iostream>

using namespace std;

const int SIZE=100+5; const int INFINITY=1000000; int n,a[SIZE],maxDeep,num;

void solve(int left,int right,int deep) { int i,j,min;

if(deep>maxDeep){

38

maxDeep=deep; num=1; } else if(deep==maxDeep) ① ;

min= INFINITY; for(i=left;i<=right;i++) if(min>a[i]){ min=a[i]; ② } if(left<j) ③ if(j<right) ④ } ; ; ;

int main() { int i; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; maxDeep=0; solve(1,n,1); cout<<maxDeep<<' '<<num<<endl; return 0; }

39

2010 第十六届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 ● ● C++语言 两小时完成 ) ●●

全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效

一、单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确选项。 ) 1.与十六进制数 A1.2 等值的十进制数是( A.101.2 B.111.4 A C ) D.177.25

C.161.125 )个二进制组成。 C.32

2.一个字节(byte)由( A.8 B.16

D.以上都有可能 ) 。 B.Q∨(┓P∧Q)∨(P∧┓Q) D.P∨┓Q∨(P∧┓Q)∨(┓P∧┓Q) )。 D. 以上都不是 B )也成立。

3.以下逻辑表达式的值恒为真的是( A.P∨(┓P∧Q)∨(┓P∧┓Q) C.P∨Q∨(P∧┓Q)∨(┓P∧Q)

4.Linux 下可执行文件的默认扩展名是( D A. exe B. com C. dll

5.如果在某个进制下等式 7*7=41 成立,那么在该进制下等式 12*12=( A. 100 B. 144 C. 164 D. 196 D ) 。

6.提出“存储程序”的计算机工作原理的是( A. 克劳德?香农 B. 戈登?摩尔

C. 查尔斯?巴比奇 ) 。

D. 冯?诺依曼

7.前缀表达式“+ 3 * 2 + 5 A. 23 B. 25

12 ” 的值是( D. 65

C. 37

8.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多,从而使得后者的效率受到影 响。而根据局部性原理,CPU 所访问的存储单元通常都趋于一个较小的连续区域中。于是, 为了提高系统整体的执行效率,在 CPU 中引入了( B )。 A.寄存器 B.高速缓存 C.闪存 D.外存

9.完全二叉树的顺序存储方案,是指将完全二叉树的结点从上到下、从左到右依次存放到一 个顺序结构的数组中。假定根结点存放在数组的 1 号位置上,则第 k 号结点的父结点如果存 在的话,应当存放在数组中的( C )号位置。 A.2k B.2k+1 C.k/2 下取整 ) 。 B.全国青少年信息学奥林匹克竞赛(NOI) D.亚太地区信息学奥林匹克竞赛(APIO) D.(k+1)/2

10.以下竞赛活动中历史最悠久的是( B

A.全国青少年信息学奥林匹克联赛(NOIP) C.国际信息学奥林匹克竞赛(IOI)

二、不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数不少于 1。多 选或少选均不得分) 。 1.元素 R1、R2、R3、R4、R5 入栈的顺序为 R1、R2、R3、R4、R5。如果第 1 个出栈的是 R3, 那么第 5 个出栈的可能是( )。
40

A.R1

B.R2

C.R4

D.R5 )。 C.解释性语言 D.编译性语言

2.Pascal 语言,C 语言和 C++语言都属于( D A.高级语言 B.自然语言

3. 原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关 的排序算法。以下属于原地排序的有( )。 A.冒泡排序 B.插入排序 C.基数排序 ) 。 D.选择排序

4.在整数的补码表示法中,以下说法正确的是( A.只有负整数的编码最高位为 1

B.在编码的位数确定后,所能表示的最小整数和最大整数的绝对值相同 C.整数 0 只有一个唯一的编码 D.两个用补码表示的数相加时,如果在最高位产生进位,则表示运算溢出 5.一颗二叉树的前序遍历序列是 ABCDEFG,后序遍历序列是 CBFEGDA,则根结点的左子树的 结点个数可能是( B ) 。 A.0 B.2 C.4 D. 6 ) 。

6.在下列 HTML 语句中,可以正确产生一个指向 NOI 官方网站的超链接的是( A.<a url="http://www.noi.cn">欢迎访问 NOI 网站</a> B.<a href="http://www.noi.cn">欢迎访问 NOI 网站</a> C.<a>http://www.noi.cn</a> D.<a name"http://www.noi.cn">欢迎访问 NOI 网站</a> 7.关于拓扑排序,下列说法正确的是( )。

A.所有连通的有向图都可以实现拓扑排序 B.对同一个图而言,拓扑排序的结构是唯一的 C.拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面 D.拓扑排序结果序列中的第一个结点一定是入度大于 0 的点 8.一个平面的法线是指与该平面垂直的直线。过点(1,1,1)、 (0,3,0) 、(2,0,0)的平面的法 线是( ) 。 A.过点(1,1,1) 、 (2,3,3)的直线 C.过点(0,3,0) 、 (-3,1,1)的直线 B.过点(1,1,1) 、 (3,2,1)的直线 D.过点(2,0,0) 、 (5,2,1)的直线

9.双向链表中有两个指针域 llink 和 rlink,分别指向该结点的前驱及后继。设 p 指向链表 中的一个结点,他的左右结点均为非空。现要求删除结点 p ,则下列语句序列中正确的是 ( )。 A.p->rlink->llink=p->rlink; p->llink->rlink=p->llink; B.p->llink->rlink=p->rlink;
41

delete p;

p->rlink->llink = p->llink; delete p; C.p->rlink->llink = p->llink; p->rlink->llink ->rlink = p->rlink; delete p; D.p->llink->rlink = p->rlink; p->llink->rlink->link = p->llink; delete p; 10.今年(2010 年)发生的事件有( ABC ) 。

A.惠普实验室研究员 Vinay Deolalikar 自称证明了 P≠NP B.英特尔公司收购计算机安全软件公司迈克菲(McAfee) C.苹果公司发布 iPhone 4 手机 D.微软公司发布 Windows 7 操作系统 三.问题求解(共 2 题,每空 5 分,共计 10 分) 1.LZW 编码是一种自适应词典编码。在编码的过程中,开始时只有一部基础构造元素的编码 词典,如果在编码的过程中遇到一个新的词条,则该词条及一个新的编码会被追加到词典中, 并用于后继信息的编码。 举例说明,考虑一个待编码的信息串: “xyx yy yy xyx” 。初始词典只有 3 个条目,第一 个为 x,编码为 1;第二个为 y,编码为 2;第三个为空格,编码为 3;于是串“xyx”的编码 为 1-2-1(其中-为编码分隔符) ,加上后面的一个空格就是 1-2-1-3。但由于有了一个空格, 我们就知道前面的“xyx”是一个单词,而由于该单词没有在词典中,我们就可以自适应的把 这个词条添加到词典里,编码为 4,然后按照新的词典对后继信息进行编码,以此类推。于 是,最后得到编码:1-2-1-3-2-2-3-5-3-4。 我们可以看到,信息被压缩了。压缩好的信息传递到接受方,接收方也只要根据基础词 典就可以完成对该序列的完全恢复。解码过程是编码过程的逆操作。现在已知初始词典的 3 个条目如上述,接收端收到的编码信息为 2-2-1-2-3-1-1-3-4-3-1-2-1-3-5-3-6,则解码后 的信息串是“ ” 。 2.无向图 G 有 7 个顶点,若不存在由奇数条边构成的简单回路,则它至多有____ 边。 ____条

3.记 T 为一队列,初始时为空,现有 n 个总和不超过 32 的正整数依次入列。如果无论这些 数具体为何值,都能找到一种出队的方式,使得存在某个时刻队列 T 中的数之和恰好为 9, 那么 n 的最小值是___________。 四.阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. #include<iostream> using namespace std; int main() { const int SIZE=10;

42

int data[SIZE],i,j,cnt,n,m; cin>>n>>m; for(i=1;i<=n;i++) cin>>data[i]; for(i=1;i<=n;i++) { cnt=0; for(j=1;j<=n;j++) if( (data[i]<data[j]) || (data[j]==data[i] && j<i) ) cnt++; if (cnt==m) cout<<data[i]<<endl; } return 0; } 输入: 5 2 96 -8 0 16 87 输出: 2. #include<iostream> using namespace std; int main() { const int SIZE=100; int na,nb,a[SIZE],b[SIZE],i,j,k; cin>>na; for(i=1;i<=na;i++) cin>>a[i]; cin>>nb; for(i=1;i<=nb;i++) cin>>b[i];
43

16

i=1; j=1; while( (i<=na)&&(j<=nb) ) { if(a[i]<=b[j]) { cout<<a[i]<<' '; i++; } else { cout<<b[j]<<' '; j++; } } if(i<=na) for(k=i;k<=na;k++) cout<<a[k]<<' '; if(j<=nb) for(k=j;k<=nb;k++) cout<<b[k]<<' '; return 0; } 输入: 5 1 3 5 7 9 4 2 6 10 14 输出:____1 2 3 5 6 7 9 10 14___________ 3. #include<iostream> using namespace std;
44

const int NUM=5; int r(int n) { int i; if(n<=NUM) return 0; for(i=1;i<=NUM;i++) if( r(n-i)<0) return i; return -1; }

int main() { int n; cin>>n; cout<<r(n)<<endl; return 0; } 输入: 16 输出:_____4_________ 4. #include<iostream> #include<cstring> using namespace std; const int SIZE=100; int n,m,r[SIZE]; bool map[SIZE][SIZE],found;

bool successful() { int i;
45

for(i=1;i<=n;i++) if(!map[r[i]][r[i%n+1]]) return false; return true; } void swap(int *a,int *b) { int t; t=*a; *a=*b; *b=t; } void perm(int left,int right) { int i; if(found) return ; if(left>right) { if(successful()) { for(i=1;i<=n;i++) cout<<r[i]<<' '; found=true; } return ; } for(i=left;i<=right;i++) { swap(r+left,r+i); perm(left+1,right); swap(r+left,r+i);
46

} } int main() { int x,y,i; cin>>n>>m; memset(map,false,sizeof(map)); for(i=1;i<=m;i++) { cin>>x>>y; map[x][y]=true; map[y][x]=true; } for(i=1;i<=n;i++) r[i]=i; found=false; perm(1,n); if(!found) cout<<"No solution!"<<endl; return 0; } 输入: 9 12 1 2 2 3 3 4 4 5 5 6 6 1 1 7 2 7 3 8
47

4 8 5 9 6 9 输出:_1 6 9 5 4 8 3 2 7________ 五.完善程序 (第 1 题,每空 2 分,第 2 题,每空 3 分,共 28 分) 1.(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到 河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯. 另外,独木桥上最多能承受两个人同时经过 ,否则将会坍塌.每个人单独过独木桥都需要一定 的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时 间是较慢的那个人单独过桥所花费的时间.现在输入 N(2<=N<1000)和这 N 个人单独过桥需要 的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸. 例如,有 3 个人甲、乙、丙,他们单独过桥的时间分别为 1、2、4,则总共最少需要的时间 为 7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙在 一起过桥到河的左岸,总时间为 2+1+4=7. #include<iostream> #include<cstring> using namespace std; const int SIZE=100; const int INFINITY = 10000; const bool LEFT=true; const bool RIGHT =false; const bool LEFT_TO_RIGHT=true; const bool RIGHT_TO_LEFT=false;

int n,hour[SIZE]; bool pos[SIZE];

int max(int a,int b) { if(a>b) return a; else return b; }

48

int go(bool stage) { int i,j,num,tmp,ans; if(stage==RIGHT_TO_LEFT) { num=0; ans=0; for(i=1;i<=n;i++) if(pos[i]==RIGHT) { num++; if( hour[i]>ans) ans=hour[i]; } if( ① return ans; ans=INFINITY; for(i=1;i<=n-1;i++) if(pos[i]==RIGHT) for(j=i+1;j<=n;j++) if(pos[j]==RIGHT) { pos[i]=LEFT; pos[j]=LEFT; tmp=max(hour[i],hour[j])+ if(tmp<ans) ans=tmp; pos[i]=RIGHT; pos[j]=RIGHT; ② ; )

} return ans;
49

} if(stage==LEFT_TO_RIGHT) { ans=INFINITY; for(i=1;i<=n;i++) if( { pos[i]=RIGHT; tmp= if(tmp<ans) ans=tmp; ⑤ } return ans; } return 0; } ; ④ ; ③ )

int main() { int i; cin>>n; for(i=1;i<=n;i++) { cin>>hour[i]; pos[i]=RIGHT; } cout<<go[RIGHT_TO_LEFT)<<endl; return 0; } 2. (烽火传递)烽火台又称烽燧,是重要的军事防御设施,一般建在险要处或交通要道上。 一旦有敌情发生,白天燃烧柴草,通过浓烟表达信息;夜晚燃烧干柴,以火光传递军情。在 某两座城市之间有 n 个烽火台,每个烽火台发出信号都有一定的代价。为了使情报准确地传
50

递,在连续的 m 个烽火台中至少要有一个发出信号。现输入 n、m 和每个烽火台发出信号的代 价,请计算总共最少花费多少代价,才能使敌军来袭之时,情报能在这两座城市之间准确传 递。 例如,有 5 个烽火台,他们发出信号的代价依次为 1,2,5,6,2, ,且 m 为 3,则总共最少 花费代价为 4,即由第 2 个和第 5 个烽火台发出信号。 #include<iostream> #include<cstring> using namespace std; const int SIZE=100; int n,m,r,value[SIZE],heap[SIZE], pos[SIZE],home[SIZE],opt[SIZE]; //hep[i]表示用顺序数组储存的堆 heap 中第 i 个元素的值 //pos[i]表示 opt[i]在堆 heap 中的位置,即 heap[pos[i]]=opt[i] //home[i]表示 heap[i]在序列 opt 中的位置,即 opt[home[i]]=heap[i]

void swap(int i,int j)//交换堆中的第 i 个和第 j 个元素 { int tmp; pos[home[i]]=j; pos[home[j]]=i; tmp=heap[i]; head[i]=head[j]; heap[j]=tmp; tmp=home[i]; home[i]=home[j]; home[j]=tmp; } void add(int k)//在堆中插入 opt[k] { int i; r++; heap[r]= pos[k]=r;
51



;

② i=r;

;

while( (i>1) && (heap[i]<heap[i/2]) ) { swap(i,i/2); i/=2; } } void remove(int k)//在堆中删除 opt[k] { int i,j; i=pos[k]; swap(i,r);; r--; if(i==r+1) return ; while( (i>1)&&(heap[i]<heap[i/2]) ) { swap(i,i/2); i/=2; } while(i+i<=r) { if( (i+i+1<=r) && (heap[i+i+1]<heap[i+i]) ) j=i+i+1; else ③ if(hea[i]>heap[j]) { ④ i=j; }
52

;

;

else break; } }

int main() { int i; cin>>n>>m; for(i=1;i<=n;i+++) cin>>value[i]; r=0; for(i=1;i<=m;i++) { opt[i]=value[i]; add(i); } for(i=m+1;i<=n;i++) { opt[i]= remove( add(i); } cout<<heap[1]<<endl; return 0; } ⑤ ⑥ ; );

53

2009 第十五届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 ● ● C++语言 二小时完成 ) ●●

全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效

一. 单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确答案。 ) 1、关于图灵机下面的说法哪个是正确的:C A) 图灵机是世界上最早的电子计算机。 B) 由于大量使用磁带操作,图灵机运行速度很慢。 C) 图灵机只是一个理论上的计算模型。 D) 图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 2、关于 BIOS 下面的说法哪个是正确的:A A) BIOS 是计算机基本输入输出系统软件的简称。 B) BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C) BIOS 一般由操作系统厂商来开发完成。 D) BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 3、已知大写字母A的ASCII编码为65(十进制) ,则大写字母J的 十六进制 ASCII编码为D: A) 48 B) 49 C) 50 D) 以上都不是

4、在字长为 16 位的系统环境下,一个 16 位带符号整数的二进制补码为 1111111111101101。 其对应的十进制整数应该是:B A) 19 B) -19 C) 18 D) -18

5、一个包含 n 个分支结点(非叶结点)的非空满 k 叉树,k>=1,它的叶结点数目为:D A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1

6. 表达式 a*(b+c)-d 的后缀表达式是:B A) abcd*+B) abc+*dC) abc*+dD) -+*abcd

7、最优前缀编码,也称 Huffman 编码。这种编码组合的特点是对于较频繁使用的元素给与较 短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。 A)(00,01,10,11) B)(0,1,00,11) C)(0,10,110,111) D)(1,01,000,001) 8、快速排序平均情况和最坏情况下的算法时间复杂度分别为: A) 平均情况 O(nlog2n),最坏情况 O(n2) B) 平均情况 O(n), C) 平均情况 O(n), 最坏情况 O(n2) 最坏情况 O(nlog2n)
54

D) 平均情况 O(log2n), 最坏情况 O(n2) 9、 右图给出了一个加权无向图, 从顶点 V0 开始用 prim 算法求最 小生成树。 则依次加入最小生成 树的顶点集合的顶点序列为: A) B) C) D) V0, V1, V2, V3, V5, V4 V0, V1, V5, V4, V3, V3 V1, V2, V3, V0, V5, V4 V1, V2, V3, V0, V4, V5

10、 全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源, 请问全国信息学奥林匹克官方网站的网址是:C A) http://www.noi.com/ C) http://www.noi.cn/ B) http://www.noi.org/ D) http://www.xinxixue.com/

二. 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数不少于 1。 多选或少选均不得分) 。 1、关于 CPU 下面哪些说法是正确的:ABCD A) B) C) D) CPU 全称为中央处理器(或中央处理单元) 。 CPU 能直接运行机器语言。 CPU 最早是由 Intel 公司发明的。 同样主频下,32 位的 CPU 比 16 位的 CPU 运行速度快一倍。

2、关于计算机内存下面的说法哪些是正确的: A) 随机存储器(RAM)的意思是当程序运行时,每次具体分配给程序的内存位置是随机 而不确定的。 B) 一般的个人计算机在同一时刻只能存/取一个特定的内存单元。

C) 计算机内存严格说来包括主存(memory) 、高速缓存(cache)和寄存器(register) 三个部分。 D) 1MB 内存通常是指 1024*1024 字节大小的内存。

3、关于操作系统下面说法哪些是正确的: A. 多任务操作系统专用于多核心或多个 CPU 架构的计算机系统的管理。 B. 在操作系统的管理下,一个完整的程序在运行过程中可以被部分存放在内存中。 C. 分时系统让多个用户可以共享一台主机的运算能力,为保证每个用户都得到及时的响 应通常会采用时间片轮转调度的策略。 D. 为了方便上层应用程序的开发,操作系统都是免费开源的。 4、关于计算机网络,下面的说法哪些是正确的:
55

A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 B) 新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。 C) TCP/IP 是互联网的基础协议簇,包含有 TCP 和 IP 等网络与传输层的通讯协议。 D) 互联网上每一台入网主机通常都需要使用一个唯一的 IP 地址,否则就必须注册一个 固定的域名来标明其地址。 5、关于 HTML 下面哪些说法是正确的: A) HTML 全称超文本标记语言,实现了文本、图形、声音乃至视频信息的统一编码。 B) HTML 不单包含有网页内容信息的描述,同时也包含对网页格式信息的定义。 C) 网页上的超链接只能指向外部的网络资源,本网站网页间的联系通过设置标签来实 现。 D) 点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符(URL)请求 网络资源或网络服务。 6、若 3 个顶点的无权图 G 的邻接矩阵用数组存储为{{0,1,1},{1,0,1},{0,1,0}}, 假定在具体存储中顶点依次为: v1,v2,v3。关于该图,下面的说法哪些是正确的: A) 该图是有向图。 B) 该图是强连通的。 C) 该图所有顶点的入度之和减所有顶点的出度之和等于 1。 D) 从 v1 开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。 7、在带尾指针(链表指针 clist 指向尾结点)的非空循环单链表中每个结点都以 next 字段 的指针指向下一个节点。假定其中已经有 2 个以上的结点。下面哪些说法是正确的: A) 如果 p 指向一个待插入的新结点,在头部插入一个元素的语句序列为: p->next = clist->next; clist->next = p; B) 如果 p 指向一个待插入的新结点,在尾部插入一个元素的语句序列为: p->next = clist;clist->next = p; C) 在头部删除一个结点的语句序列为: p = clist->next; clist->next = clist->next->next; delete p; D) 在尾部删除一个结点的语句序列为。 p = clist; clist = clist ->next; delete p; 8、散列表的地址区间为 0-10,散列函数为 H(K)=K mod 11。采用开地址法的线性探查法处理 冲突,并将关键字序列 26,25,72,38,8,18,59 存储到散列表中,这些元素存入散列 表的顺序并不确定。假定之前散列表为空,则元素 59 存放在散列表中的可能地址有: A) 5 B) 7 C) 9 D) 10

9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变,下列哪些排序 算法是稳定的: A) 插入排序 B) 基数排序 C) 归并排序 D) 冒泡排序
56

10、在参加 NOI 系列竞赛过程中,下面哪些行为是被严格禁止的:ABC A) 携带书写工具,手表和不具有通讯功能的电子词典进入赛场。 B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C) 通过互联网搜索取得解题思路。 D) 在提交的程序中启动多个进程以提高程序的执行效率。 三.问题求解(共 2 题,每空 5 分,共计 10 分) 1.拓扑排序是指将有向无环图 G 中的所有顶点排成一个线性序列,使得图中任意一对顶 点 u 和 v,若<u,v> ∈E(G),则 u 在线性序列中出现在 v 之前,这样的线性序列成为拓扑序 列。 如下的有向无环图, 对其顶点做拓扑排序, 则所有可能的拓扑序列的个数为 482 。

2

5 6

8

1

4 7 9

3

2.某个国家的钱币面值有 1, 7, 72, 73 共计四种,如果要用现金付清 10015 元的货物, 假设买卖双方各种钱币的数量无限且允许找零, 那么交易过程中至少需要流通 35 张钱 币。

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

int a,b;

int work(int a,int b){ if (a%b) return work(b,a%b); return b; }

int main(){
57

cin >> a >> b; cout << work(a,b) << endl; return 0; }

输入:123 321 输出:___3______

2. #include <iostream> using namespace std; int main() { int a[4],b[4]; int i,j,tmp; for (i=0;i<4;i++) cin >> b[i]; for (i=0;i<4;i++) { a[i]=0; for (j=0;j<=i;j++) { a[i]+=b[j]; b[a[i]%4]+=a[j]; } } tmp=1; for (i=0;i<4;i++) { a[i]%=10; b[i]%=10; tmp*=a[i]+b[i];
58

} cout << tmp << endl; return 0; }

输入:2 3 5 7 输出:___5850____________

3. #include <iostream> using namespace std;

const int maxn=50; const int y=2009; int main() { int n,c[maxn][maxn],i,j,s=0; cin >> n; c[0][0]=1; for(i=1;i<=n;i++) { c[i][0]=1; for(j=1;j<i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; c[i][i]=1; } for(i=0;i<=n;i++) s=(s+c[n][i])%y; cout << s << endl; return 0; }

59

输入:17 输出: 487

4. #include <iostream> using namespace std;

int main() { int n,m,i,j,p,k; int a[100],b[100]; cin >> n >> m; a[0]=n; i=0; p=0; k=0; do { for (j=0;j<i;j++) if (a[i]==a[j]) { p=1; k=j; break; } if (p) break; b[i]=a[i]/m; a[i+1]=a[i]%m*10; i++; }while (a[i]!=0);

60

cout << b[0] << "."; for (j=1; j<k; j++) cout << b[j]; if (p) cout << "("; for (j=k;j<i;j++) cout << b[j]; if (p) cout << ")"; cout << endl; return 0; }

输入:5 13 输出:___0______

五.完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分)

1. (最大连续子段和)给出一个数列(元素个数不多于 100) ,数列元素均为负整数、正 整数、0。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大,在 和最大的前提下还要求该子数列包含的元素个数最多,并输出这个最大和以及该连续子数列 中元素的个数。例如数列为 4,-5,3,2,4 时,输出 9 和 3;数列为 1 2 3 -5 0 7 8 时, 输出 16 和 7。 #include <iostream> using namespace std;

int a[101]; int n,i,ans,len,tmp,beg,end; int main(){ cin >> n; for (i=1;i<=n;i++) cin >> a[i]; tmp=0;

61

ans=0; len=0; beg= ① ;

for (i=1;i<=n;i++){ if (tmp+a[i]>ans){ ans=tmp+a[i]; len=i-beg; } else if ( len=i-beg; if (tmp+a[i] beg= tmp=0; } else ⑤ } cout << ans << " " << len << endl; return 0; } ; ④ ③ ; ){ ② &&i-beg>len)

2. (寻找等差数列) 有一些长度相等的等差数列(数列中每个数都为 0~59 的整数) ,设 长度均为 L,将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数,问原先, L 最大可能为多大?先读入一个数 n(1<=n<=60) ,再读入 n 个数,代表打乱后的数。输出等 差数列最大可能长度 L。 #include <iostream> using namespace std;

int hash[60]; int n, x, ans, maxnum;

int work(int now) { int first, second, delta, i;
62

int ok; while ( ++now; if (now > maxnum) return 1; first = now; for (second = first; second <= maxnum; second++) if (hash[second]) { delta = ② ; ③ > maxnum) ① && !hash[now])

if (first + delta * break; if (delta == 0) ok = ( else{ ok = 1; ④

);

for (i = 0; i < ans; i++) ok = } if (ok){ for (i = 0; i < ans; i++) hash[first+delta*i]--; if (work(first)) return 1; for (i = 0; i < ans; i++) hash[first+delta*i]++; } } return 0; } ⑤ && (hash[first+delta*i]);

int main(){ int i;
63

memset(hash, 0, sizeof(hash)); cin >> n; maxnum = 0; for (i = 0; i < n; i++){ cin >> x; hash[x]++; if (x > maxnum) maxnum = x; } for (ans = n; ans >= 1; ans--) if ( n%ans==0 && ⑥ ) {

cout << ans << endl; break; } return 0; }

64

2013 第十九届全国青少年信息学奥林匹克联赛初赛答案解析 一、单选题(15*1.5) 1、A, 2、A, 3、B, 4、D, 5、A, 6、B, 7、D 13、D, 14、B, 15、B, 二、不定项选择题(5*1.5) 1、AC, 2、AD, 3、CD, 4、AB, 5、ABCD, 8、B, 9、D, 10、D, 11、C,12、B,

三、问题求解(2*5) 1、0 1 1 1 2、37/12

四、阅读程序写结果(4*8) 1、Yes, 2、133 3、4, 4、7,

五、完善程序(15+13) 1、n-p+i i-p+1 2、j-i cur1 a[i-p] count1--; i>end1 i j-1; cur1=a[j],

count2--;

2012 第十八届全国青少年信息学奥林匹克联赛初赛参考答案

65

2011 第十七届全国青少年信息学奥林匹克联赛初赛试题参考答案与评分标准 一、单项选择题: (每题 1.5 分) 1. B 6. A 2. B 7. C 3. A 8. D 4. D 9. B 5. B 10. A

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数大于或等于 1。多选或少选均不得分) 。 1. CD 6. ABD 1.9 2. ABCD 7. CD 2.4 3. AB 8. A 4. BC 9. BCD 5. BC 10. ABC

三、问题求解: (共 2 题,每空 5 分,共计 10 分) 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1.3 2.1 2 5 13 34 3.150 4.57344 五、完善程序(第 1 题,每空 2 分,第 2 题,每空 3 分,共计 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不 一定上报科学委员会审查) 1. ① ans.num[i + j - 1] ② ans.num[i] = ans.num[i] mod 10 ③ a.num[i] + b.num[i] ④ ans.num[i] % 2 (或 ans.num[i] & 1) ⑤ ans.len++ (或 ans.len = ans.len + 1) ⑥ a.len < b.len ⑦ '0'(或 48) ⑧ times(middle, middle), target 2. ① num++ (或 num = num + 1)
66

② j = i ③ solve(left, j - 1, deep + 1) ④ solve(j + 1, right, deep + 1) 2010 第十六届全国青少年信息学奥林匹克联赛初赛试题参考答案与评分标准 一、单项选择题: (每题 1.5 分) 1 C 2 A 3 A 4 D 5 B 6 D 7 C 8 B 9 C 10 B

二、 不定项选择题 (共 10 题, 每题 1.5 分, 共计 15 分。 每题正确答案的个数大于或等于 1。 多选或少选均不得分) 。 1 ACD 2 AD 3 ABD 4 AC 5 B 6 B 7 D 8 D 9 BCD 10 ABC

三、问题求解: (共 3 题,每空 5 分,共计 15 分) 1.yyxy xx yyxy xyx xx xyx 2.12 3.18 四、阅读程序写结果(共 4 题,每题 7 分,共计 28 分) 1.16 2.1 2 3 5 6 7 9 10 14 3.4 4.1 6 9 5 4 8 3 2 7 五、 、完善程序(第 1 空 2 分,其余 10 空,每空 2.5 分,共计 27 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不 一定上报科学委员会审查) 1. ① num <= 2(或 num < 3 或 num = 2) ② go(LEFT_TO_RIGHT) ③ pos[i] = =LEFT(或 LEFT = pos[i]) ④ hour[i] + go(RIGHT_TO_LEFT)(或 go(RIGHT_TO_LEFT) +hour[i]) ⑤ pos[i] = LEFT 本小题中,LEFT 可用 true 代替,LEFT_TO_RIGHT 可用 true 代替,RIGHT_TO_LEFT 可用 false 代替。 2. ① opt[k] ② home[r] = k ③ j = i + i(或 j = 2 * i 或 j = i * 2) ④ swap(i, j)(或 swap(j, i)) ⑤ value[i] + heap[1](或 heap[1] + value[i]) ⑥ i - m 2009 第十五届全国青少年信息学奥林匹克联赛初赛试题参考答案与评分标准 一、单项选择题: (每题 1.5 分)
67

1. C 6. B

2. A 7. B

3. D 8. A

4. B 9. A

5. D 10. C

二、 不定项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题正确答案的个数大于或等于 1。多选或少选均不得分) 。 1. AB 6. ABD 1.432 2.35 四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分) 1. 3 2. 5850 3. 487 (杨辉三角) 4. 0.(384615)(分数变小数) 五.完善程序 (前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) (说明:以下各程序填空可能还有一些等价的写法,各省可请本省专家审定和上机验证,不 一定上报科学委员会审查) 1. ① 0 ② tmp+a[i]==ans 或者 a[i]+tmp==ans 或者 ans==a[i]+tmp 等 ③ <0 ④ i ⑤ tmp+=a[i] 或者 tmp=tmp+a[i] 2. ① now<=maxnum 或者 !(now>maxnum) ② second-first ③ (ans-1) ④ hash[first]>=ans 或者 hash[second]>=ans 或者 hash[first+delta]>=ans ⑤ ok ⑥ work(0) 或者 work(0)==1 或者 work(0)>0 等 2. BD 7. AC 3. BC 8. ABC 4. C 9. ABCD 5. BD 10. ACD

三、问题求解: (共 2 题,每空 5 分,共计 10 分)

68


相关文章:
2009-2013年NOIP初赛提高组C++语言试题及参考答案
2009-2013年NOIP初赛提高组C++语言试题及参考答案_IT认证_资格考试/认证_教育专区。2009-2013 年 NOIP 初赛提高组 C++语言试题 2013 第十九届全国青少年信息学奥林...
2009noip提高组初赛试题及答案_C语言
2009noip提高组初赛试题及答案_C语言_高三数学_数学_高中教育_教育专区。2009年第十五届全国青少年信息学奥林匹克联赛C语言提高组初赛试题及答案2009...
NOIP2009提高组初赛试题及答案
⑥ then NOIP2009 初赛 提高组 Pascal 9 NOIP2009 提高组(Pascal 语言)参考答案与评分标准一、单项选择题:(每题 1.5 分) 1. C 6. B 2. A 7. B 3...
NOIP2008提高组初赛试题_C++含答案
NOIP2008提高组初赛试题_C++含答案_英语考试_外语学习_教育专区。第十四届全国青少年信息学奥林匹克联赛初赛试题( 提高组 C++ 语言 二小时完成 )●● 全部试题答案...
NOIP2009初赛试题及参考答案和解析(提高组)C++
NOIP2009初赛试题及参考答案和解析(提高组)C++_财会/金融考试_资格考试/认证_教育专区。NOIP2009初赛试题(提高组)C++ 第十五届全国青少年信息学奥林匹克联赛初赛试题...
NOIP2009提高组初赛 pascal试题+答案
⑥ then NOIP2009 初赛 提高组 Pascal 9 NOIP2009 提高组(Pascal 语言)参考答案与评分标准 提高组( 语言)一、单项选择题:(每题 1.5 分) 1. C 6. B...
NOIP2013初赛提高组c试题
NOIP2013初赛提高组c试题_学科竞赛_高中教育_教育专区。第十九届全国青少年信息学奥林匹克联赛初赛提高组 Pascal 语言试题 竞赛时间:2013 年 10 月 13 日 14:30~...
NOIP2013提高组C++试题
NOIP2013提高组C++试题_电子/电路_工程科技_专业资料。第十九届全国青少年信息学奥林匹克联赛初赛提高组 C++语言试题 竞赛时间:2013 年 10 月 13 日 14:30~16:...
NOIP2008提高组初赛试题_C++含答案 改动
NOIP2008提高组初赛试题_C++答案 改动_学科竞赛_高中教育_教育专区。第十四届...NOIP 竞赛推荐使用的语言环境有( A.Dev-C++ B.Visual C++ B. T 是连通的,...
NOIP2008年提高组初赛试题(十四届)(非常详细)
NOIP2008年提高组初赛试题(十四届)(非常详细)_计算机硬件及网络_IT/计算机_专业...【答案】ABC 19.NOIP 竞赛推荐使用的语言环境有( A.Dev-C++答案】ACD 20...
更多相关标签:
noip2009提高组初赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2012提高组初赛 | noip2013提高组初赛 | noip2011提高组初赛 | noip提高组初赛 | noip2014提高组初赛 |