文档库 最新最全的文档下载
当前位置:文档库 › NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案
NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案

?

一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项)?

1. 从( )年开始,NOIP 竞赛将不再支持 Pascal 语言。

A. 2020

B. 2021

C. 2022

D. 2023

?

2.在 8 位二进制补码中,10101011 表示的数是十进制下的( )。

A. 43

B. -85

C. -43

D.-84

?

3.分辨率为 1600x900、16 位色的位图,存储图像信息所需的空间为( )。

A. 2812.5KB

B. 4218.75KB

C. 4320KB

D. 2880KB

?

4. 2017年10月1日是星期日,1949年10月1日是( )。

A. 星期三

B. 星期日

C. 星期六

D. 星期二

?

5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图,必须删去 G 的( )条边,才能使得 G 变成一棵树。

A.m–n+1

B. m-n

C. m+n+1

D.n–m+1

?

6. 若某算法的计算时间表示为递推关系式:

T(N)=2T(N/2)+NlogN

T(1)=1

则该算法的时间复杂度为( )。

A.O(N)

B.O(NlogN)

C.O(N log2N)

D.O(N2)

?

7. 表达式a * (b + c) * d的后缀形式是()。

A. abcd*+*

B. abc+*d*

C. a*bc+*d

D. b+c*a*d

?

8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32

B. 35

C. 38

D. 41

?

9. 将7个名额分给4个不同的班级,允许有的班级没有名额,有( )种不同的分配方案。

A. 60

B. 84

C. 96

D.120

?

10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2,则随着i的增大,f[i]将接近与( )。

A. 1/2

B. 2/3

D. 1

?

11. 设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。

A. n2

B. nlogn

C. 2n

D.2n-1

?

12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把

a-c三行代码补全到算法中。

a. A XUY

b. A Z

c. n |A|

算法Coin(A,n)

1. k n/3

2. 将A中硬币分成X,Y,Z三个集合,使得|X|=|Y|=k, |Z|=n-2k

3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量

4. then_______

5. else_______

6. __________

7. if n>2 then goto 1

8. if n=2 then 任取A中1枚硬币与拿走硬币比较,若不等,则它不合格;若相等,则A 中剩下的硬币不合格

9. if n=1 then A中硬币不合格

正确的填空顺序是( )。

A. b,c,a

B. c,b,a

C. c,a,b

D.a,b,c

?

13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为a11;第二行的数从左到右依次为a21,a22;…第n行的数为an1,an2,…,ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径,使得该路径上的数之和达到最大。

令C[i,j]是从a11到aij的路径上的数的最大和,并且C[i,0]=C[0,j]=0,则C[i,j]=( )。

A. max{C[i-1,j-1],C[i-1,j]}+aij

B. C[i-1,j-1]+c[i-1,j]

C. max{C[i-1,j-1],C[i-1,j]}+1

D. max{C[i,j-1],C[i-1,j]}+aij

?

14. 小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第1个航班准点的概率是0.9,第2个航班准点的概率为0.8,第3个航班准点的概率为0.9。如果存在第i个(i=1,2)航班晚点,第i+1个航班准点,则小明将赶不上第i+1个航班,旅行失败;除了这种情况,其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。

A. 0.5

B. 0.648

C. 0.72

D.0.74

?

15. 欢乐喷球:儿童游乐场有个游戏叫“欢乐喷球”,正方形场地中心能不断喷出彩色乒乓球,以场地中心为圆心还有一个圆轨道,轨道上有一列小火车在匀速运动,火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点,包括火车车厢。小朋友玩这个游戏时,只能坐在同一个火车车厢里,可以在自己的车厢里捡落在该车厢内的所有乒乓球,每个人每次游戏有三分钟时间,则一个小朋友独自玩一次游戏期望可以得到( )个乒乓球。假设乒乓球喷出的速度为2个/秒,每节车厢的面积是整个场地面积的1/20。

A. 60

B. 108

C. 18

D. 20

?

二、不定项选择题(共5题,每题1.5分,共计7.5分;每题有一个或多个正确选项,多选或少选均不得分)

?

1. 以下排序算法在最坏情况下时间复杂度最优的有( )。

A. 冒泡排序

B. 快速排序

C. 归并排序

D. 堆排序

?

2. 对于入栈顺序为 a, b, c, d, e, f, g 的序列,下列()不可能是合法的出栈序列。

A. a,b,c,d,e,f,g

B. a,d,c,b,e,g,f

C. a,d,b,c,g,f,e

D.g,f,e,d,c,b,a

?

3. 下列算法中,( )是稳定的排序算法。

A. 快速排序

B.堆排序

C.希尔排序

D. 插入排序

?

4. 以下是面向对象的高级语言的是( )。

A. 汇编语言

B. C++

C. Fortan

D. Java

?

5. 以下和计算机领域密切相关的奖项是( )。

A. 奥斯卡奖

B. 图灵奖

C. 诺贝尔奖

D.王选奖

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

?

1. 如图所示,共有 13 个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由 1 变0,或由 0 变 1)。现在要使得所有的格子中的数

字都变为 0,至少需要3次操作。

2. 如图所示,A到B是连通的。假设删除一条细的边的代价是1,删除一条粗的边的代价是

2,要让A、B不连通,最小代价是 4 (2分),最小代价的不同方案数是9(3分)。

(只要有一条删除的边不同,就是不同的方案)

四、阅读程序写结果(共 4 题,每题 8 分,共计 32 分)

1.

#include

using namespacestd;

int g(int m, intn, int x){

int ans = 0;

int i;

if( n == 1)

return 1;

for (i=x; i <=m/n; i++)

ans += g(m –i, n-1, i);

return ans;

}

int main() {

int t, m, n;

cin >> m >> n;

cout << g(m, n, 0) << endl;

return 0;

}

输入: 8 4

输出: 15

2.

#include

using namespacestd;

int main() {

int n, i, j, x, y, nx, ny;

int a[40][40];

for (i = 0; i< 40; i++)

for (j = 0;j< 40; j++)

a[i][j]= 0;

cin >> n;

y = 0; x = n-1;

n = 2*n-1;

for (i = 1; i <= n*n; i++){

a[y][x] =i;

ny = (y-1+n)%n;

nx = (x+1)%n;

if ((y == 0 && x == n-1) || a[ny][nx] !=0)

y= y+1;

else {y = ny; x = nx;}

}

for (j = 0; j < n; j++)

cout << a[0][j]<< “”;

cout << endl;

return 0;

}

输入: 3

输出: 17 24 1 8 15

3.

#include

using namespacestd;

int n, s,a[100005], t[100005], i;

void mergesort(intl, int r){

if (l == r)

return;

int mid = (l + r) / 2;

int p = l;

int i = l;

int j = mid + 1;

mergesort (l, mid);

mergesort (mid + 1, r);

while (i <= mid && j<= r){

if (a[j] < a[i]){

s += mid – i+1;

t[p] = a[j];

p++;

j++;

}

else {

t[p] = a[i];

p++;

i++;

}

}

while (i <= mid){

t[p] = a[i];

p++;

i++;

}

while (j <= r){

t[p] = a[j];

p++;

j++;

}

for (i = l; i <= r; i++ )

a[i] = t[i]; }

int main() {

cin >> n;

for (i = 1; i <= n; i++)

cin>> a[i];

mergesort (1, n);

cout << s << endl;

return 0;

}

输入:

6

2 6

3

4

5 1

输出: 8

4.

#include

using namespacestd;

int main() {

int n, m;

cin >> n >> m;

int x = 1;

int y = 1;

int dx = 1;

int dy = 1;

int cnt = 0;

while (cnt != 2) {

cnt = 0;

x = x + dx;

y = y + dy;

if (x == 1 || x == n) {

++cnt;

dx = -dx;

}

if (y == 1 || y == m) {

++cnt;

dy = -dy;

}

}

cout << x << " " << y<< endl;

return 0;

}

输入1: 4 3

输出1: 1 3 (2 分)

输入2: 2017 1014

输出2: 2017 1 (3 分)

输入3: 987 321

输出3: 1 321 (3分)

五、完善程序(共 2 题,每题 14 分,共计 28 分)

1.

大整数除法:给定两个正整数p和q,其中p不超过10100,q不超过100000,求p除以q 的商和余数。(第一空2分,其余3分)?

输入:第一行是p的位数n,第二行是正整数p,第三行是正整数q。

输出:两行,分别是p除以q的商和余数。

#include

using namespacestd;

int p[100];

int n, i, q,rest;

char c;

int main(){

cin >> n;

for (i = 0; i < n; i++){

cin >> c;

p[i] = c –‘0’;

}

cin >> q;

rest = p[0];

i = 1;

while (rest< q && i < n){

rest = rest * 10 + p[i];

i++;

}

if (rest < q)

cout << 0 <

else {

cout << rest / q;

while (i < n){

rest = rest % q * 10 + p[i];

i++;

cout<< rest / q;

}

cout << endl;

}

cout << rest % q<< endl;

return 0;

}

2.

最长路径:给定一个有向五环图,每条边长度为1,求图中的最长路径长度。(第五空 2 分,其余 3 分)

输入:第一行是结点数n(不超过100)和边数m,接下来m行,每行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。

输出:最长路径长度。

提示:先进行拓扑排序,然后按照拓扑排序计算最长路径。

#include

using namespacestd;

int n, m, i, j,a, b, head, tail, ans;

int graph[100][100]; // 用邻接矩阵存储图

int degree[100]; // 记录每个结点的入度

int len[100]; // 记录以各结点为终点的最长路径长度

int queue[100]; // 存放拓扑排序结果

int main() {

cin >> n >> m;

for (i = 0; i < n; i++)

for (j = 0;j < n; j++)

graph[i][j]= 0;

for (i = 0; i < n; i++)

degree[i] =0;

for (i = 0; i < m; i++){

cin>> a >>b;

graph[a][b]= 1;

degree[b]++;

}

tail = 0;

for (i = 0; i < n; i++)

if (degree[i] == 0){

queue[tail]= i;

tail++;

}

head = 0;

while (tail < n-1){

for (i = 0;i < n; i++)

if(graph[queue[head]] [i] == 1){

degree[i]--;

if(degree[i] == 0){ queue[tail]= i;

tail++;

}

}

head++;

}

ans = 0;

for (i = 0; i < n; i++){

a = queue[i];

len[a] = 1;

for (j = 0;j < n; j++)

if(graph[j][a] == 1 && len[j] + 1 >len[a])

len[a]= len[j] + 1;

if (ans < len[a])

ans= len[a];

}

cout << ans << endl;

return 0;

}

NOIP2001提高组初赛试题答案

第七届分区联赛提高组初赛 (提高组PASCAL语言二小时完成) 一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分) 1、中央处理器CPU能访问的最大存储器容量取决于( ) A)地址总线B)数据总线C)控制总线 D)内存容量 2、计算机软件保护法是用来保护软件( )的。 A)编写权B)复制权C)使用权D)著作权 3、64KB的存储器用十六进制表示,它的最大的地址码是( ) A)10000 B)FFFF C)1FFFF D)EFFFF 4、在树型目录结构中,不允许两个文件名相同主要指的是( ) A)同一个磁盘的不同目录下B)不同磁盘的同一个目录下 C)不同磁盘的不同目录下 C)同一个磁盘的同一个目录下 5、下列设备哪一项不是计算机输入设备( ) A)鼠标B)扫描仪C)数字化仪D)绘图仪 6、在计算机硬件系统中,cache是( )存储器 A)只读B)可编程只读C)可擦除可编程只读D)高速缓冲 7、若我们说一个微机的CPU是用的PII300,此处的300确切指的是( ) A)CPU的主时钟频率B)CPU产品的系列号 C)每秒执行300百万条指令D)此种CPU允许最大内存容量 8、Email邮件本质上是一个( ) A)文件B)电报C)电话D)传真 9、2KB的内存能存储( )个汉字的机内码 A)1024 B)516 C)2048 D)218 10、以下对Windows的叙述中,正确的是( ) A)从软盘上删除的文件和文件夹,不送到回收站 B)在同一个文件夹中,可以创建两个同类、同名的文件 C)删除了某个应用程序的快捷方式,将删除该应用程序对应的文件 D)不能打开两个写字板应用程序 11、运算式(2047)10—(3FF)16+(2000)8的结果是( ) A)(2048)10B)(2049)10C)(3746)8D)(1AF7)16 12、TCP/IP协议共有( )层协议 A)3 B)4 C)5 D)6 13.若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是( ) A)i B)n-1 C)n-i+1 D)不确定 14.计算机病毒是( ) A)通过计算机传播的危害人体健康的一种病毒 B)人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C)一种由于计算机元器件老化而产生的对生态环境有害的物质 D)利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 15.下面关于算法的错误说法是( ) A)算法必须有输出B)算法必须在计算机上用某种语言实现

NOIP2017全国青少年信息学奥林匹克联赛提高组初赛试题卷答案解析

NOIP 2017全国青少年信息学奥林匹克联赛提高组初赛试题答案 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确选项) 1. 从( )年开始,NOIP 竞赛将不再支持 Pascal 语言。 A. 2020 B. 2021 C. 2022 D. 2023 2.在 8 位二进制补码中,10101011 表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D.-84 3.分辨率为 1600x900、16 位色的位图,存储图像信息所需的空间为( )。 A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日,1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设 G 是有 n 个结点、m 条边(n ≤m)的连通图,必须删去 G 的( )条边,才能使得 G 变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式: T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。 A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。 A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。

A. 32 B. 35 C. 38 D. 41 9. 将7个名额分给4个不同的班级,允许有的班级没有名额,有( )种不同的分配方案。 A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2,则随着i的增大,f[i]将接近与( )。 A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。 A. n2 B. nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把 a-c三行代码补全到算法中。 a. A XUY b. A Z c. n |A| 算法Coin(A,n) 1. k n/3 2. 将A中硬币分成X,Y,Z三个集合,使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较,若不等,则它不合格;若相等,则A 中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。 A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为a11;第二行的数从左到右依次为a21,a22;…第n行的数为an1,an2,…,ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径,使得该路径上的数之和达到最大。

(完整word)NOIP2010提高组初赛试题及详细解析

第十六届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 C++ 语言 两小时完成 ) ? ? 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ?? 、单项选择题 (共 10 题,每题 1.5 分,共计 15 分。每题有且仅有一个正确选项。 ) 1.与十六进制数 A1.2 等值的十进制数是( ) A . 101.2 B . 111.4 C . 161.125 D . 177.25 &主存储器的存取速度比中央处理器 (CPU )的工作速度慢的多,从而使得后者的效率受到影响。而 根据局部性原理,CPU 所访问的存储单元通常都趋于一个较小的连续区域中。于是,为了提高系统 整体的执行 效率,在 CPU 中引入了( )。 A .寄存器 B .高速缓存 C .闪存 D .外存 9.完全二叉树的顺序存储方案,是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序 结构的数组中。假定根结点存放在数组的 1 号位置上,则第 k 号结点的父结点如果存在的话,应当 存放在数组中的( )号位置。 A .2k B .2k+1 C .k/2 下取整 D .(k+1)/2 2.一个字节( byte )由( )个二进制组成。 A .8 B .16 上都有可能 3.以下逻辑表达式的值恒为真的是( )。 A . P V (n P A Q )V (n P 心 Q ) B C . P V Q V ( P A n Q )V (n P A Q ) D 4 . Linux 下可执行文件的默认扩展名是 ( ) 。 A. exe B. com 都不是 C . 32 D .以 Q V( n P A Q )V (P A n Q ) P V n Q V( P A n Q V (n P A n Q) C. dll D. 以上 5 .如果在某个进制下等式 7*7=41 成立,那么在该进制下等式 12*12= ( A. 100 B. 144 C. 164 )也成立。 D. 196 6 .提出“存储程序”的计算机工作原理的是( A. 克劳德 ?香农 B. 戈登?摩尔 )。 C. 查尔斯 ?巴比奇 D. 冯?诺依曼 7 .前缀表达式“ + 3 * 2 + 5 12 ” 的值是( )。 A. 23 B. 25 C. 37 D. 6

NOIP提高组初赛历年试题及答案求解题篇

NOIP提高组初赛历年试题及答案求解题篇问题求解题(每次2题,每题5分,共计10分。每题全部答对得5分,没有部分分)注:答案在文末 提高组的问题求解题的知识点大多涉及计数问题、鸽巢原理、容斥问题、逻辑推理、递推问题、排列组合问题等。 NOIP2011-1.平面图可以画在平面上,且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边,如图所示。那么,5个顶点的平面图至多有_________条边。 NOIP2011-2.定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字符串“BCA”可以将A移到B之前,变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要_________次操作。 NOIP2012-1. 本题中,我们约定布尔表达式只能包含p,q, r三个布尔变量,以及“与”(∧)、“或”(∨)、“非”(?)三种布尔运算。如果无论p, q,r如何取值,两个布尔表达式的值总是相同,则称它们等价。例如,(p∨q)∨r和p∨(q∨r)等价,p∨?p 和q∨?q 也等价;而p∨q 和p∧q不等价。那么,两两不等价的布尔表达式最多有_________个。 NOIP2012-2. 对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图1有5个不同的独立集(1个双点集合、3个单点集合、1个空集),

图2有14个不同的独立集。那么,图3有_________个不同的独立集。 NOIP2013-1. 某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn,均为0或1。该系统每次随机生成n个数a1,a2,…,an,均为0或1,请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。 然而,事与愿违。例如,当n=4时,有人窃听了以下5次问答: 就破解出了密码s1=_________,s2=_________,s3=_________, s4=_________。 NOIP2013-2. 现有一只青蛙,初始时在n号荷叶上。当它某一时刻在k号荷叶上时,下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上,直至跳到1号荷叶

noip2017提高组复赛解题报告

noip2017提高组复赛解题报告 定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,融科教育信息学竞赛培训等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!以下解题思路及代码未经官方评测,仅供参考,复赛成绩以官方(CCF)评测结果为准。 Day1 1.小凯的疑惑(math.cpp/c/pas)【问题描述】小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。【输入格式】输入文件名为math.in。输入数据仅一行,包含两个正整数a 和b,它们之间用一个空格隔开,表示小凯手中金币的面值。【输出格式】输出文件名为math.out。输出文件仅一行,一个正整数N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。【输入输出样例1】math.in3 7 math.out11【数据规模与约定】对于30%的数据: 1 ≤a,b ≤50。对于60%的数据: 1 ≤a,b ≤10,000。对于100%的数据:1 ≤a,b ≤1,000,000,000。数学太差只找规律吧。

设:其中一个数为2则:2、3=>1;2、5=>3;2、7=>5;2、11=>9得:2、n=>n-2设:其中一个数为3则:3、5=>7;3、7=>11;3、11=>19;3、13=>23得:3、n=>2n-3设:其中一个数为5则:5、7=>23;5、11=>39;5、13=>47;5、17=>63得:5、n=>4n-5所以:m、n=>(m-1)n-m #includeusing namespace std;int main(){ long long a,m,n; scanf('%lld %lld',&m,&n); a=(m-1)*n-m; printf('%lld',a); return 0;} 2.时间复杂度(complexity.cpp/c/pas)【问题描述】小明正在学习一种新的编程语言A++,刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序,于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。A++语言的循环结构如下:其中“F i x y”表示新建变量(i 变量i 不可与未被销毁的变量重名)并初始化为x,然后判断i 和y 的大小关系,若i 小于等于y 则进入循环,否则不进入。每次循环结束后i都会被修改成i +1,一旦i 大于y 终止循环。x和y 可以是正整数(x 和y 的大小关系不定)或变量n。n 是一个表示数据规模的变量,在时间复杂度计算中需保留该变量而不能将其视为常数,该数远大于100。“E”表示循环体结束。循环体结束时,这个循环体新建的变量也被销毁。注:本题中为了书写方便,在描述复杂度时,使用大

noip2017提高组试题

CCF 全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day1 (请选手务必仔细阅读本页内容) 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz, 内存4G,上述时限以此配置为准。 4、只提供Linux 格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒:评测在当前最新公布的NOI Linux 下进行,各语言的编译器版本以其为准。

【问题描述】1.小凯的疑惑 (math.cpp/c/pas) 小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。 【输入格式】 输入文件名为math.in。 输入数据仅一行,包含两个正整数a 和b,它们之间用一个空格隔开,表示小凯手中金币的面值。 【输出格式】 输出文件名为math.out。 输出文件仅一行,一个正整数N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。 见选手目录下的math/math1.in 和math/math1.ans。 【输入输出样例1 说明】 小凯手中有面值为3 和7 的金币无数个,在不找零的前提下无法准确支付价值为1、2、4、5、8、11 的物品,其中最贵的物品价值为11,比11 贵的物品都能买到,比如: 12 = 3 * 4 + 7 * 0 13 = 3 * 2 + 7 * 1 14 = 3 * 0 + 7 * 2 15 = 3 * 5 + 7 * 0 …… 【输入输出样例2】 见选手目录下的math/math2.in 和math/math2.ans。 【数据规模与约定】 对于30%的数据: 1 ≤ a,b ≤ 50。 对于60%的数据: 1 ≤ a,b ≤ 10,000。 对于100%的数据:1 ≤ a,b ≤ 1,000,000,000。

NOIP2013初赛提高组Pascal试题

第十九届全国青少年信息学奥林匹克联赛初赛 提高组Pascal语言试题 竞赛时间: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) B. 图灵(Alan Turing) C. 欧拉(Leonhard Euler) D. 克劳德·香农(Claude Shannon) 5. 已知一棵二叉树有2013 个节点,则其中至多有()个节点有2 个子节点。 A. 1006 B. 1007 C. 1023 D. 1024 6. 在一个无向图中,如果任意两点之间都存在路径相连,则称其为连通 图,至少要删去其中的()条边。

NOIP2017提高组初赛试题及答案

NOIP2017提高组初赛试题及答案 一、单项选择题(共15 题,每题1.5 分,共计22.5 分;每题有且仅有一个正确选项) 1. 从( )年开始,NOIP 竞赛将不再支持Pascal 语言。C A. 2020 B. 2021 C. 2022 D. 2023 2.在8 位二进制补码中,10101011 表示的数是十进制下的( )。B A. 43 B. -85 C. -43 D.-84 3.分辨率为1600x900、16 位色的位图,存储图像信息所需的空间为( )。A A. 2812.5KB B. 4218.75KB C. 4320KB D. 2880KB 4. 2017年10月1日是星期日,1949年10月1日是( )。C A. 星期三 B. 星期日 C. 星期六 D. 星期二 5. 设G 是有n 个结点、m 条边(n ≤m)的连通图,必须删去G 的( )条边,才能使得G 变成一棵树。A A.m–n+1 B. m-n C. m+n+1 D.n–m+1 6. 若某算法的计算时间表示为递推关系式:T(N)=2T(N/2)+NlogN T(1)=1 则该算法的时间复杂度为( )。C A.O(N) B.O(NlogN) C.O(N log2N) D.O(N2) 7. 表达式a * (b + c) * d的后缀形式是()。B A. abcd*+* B. abc+*d* C. a*bc+*d D. b+c*a*d 8. 由四个不同的点构成的简单无向连通图的个数是( )。C A. 32 B. 35 C. 38D. 41 9. 将7个名额分给4个不同的班级,允许有的班级没有名额,有( )种不同的分配方案。D A. 60 B. 84 C. 96 D.120 10. 若f[0]=0, f[1]=1, f[n+1]=(f[n]+f[n-1])/2,则随着i的增大,f[i]将接近与( )。B A. 1/2 B. 2/3 D. 1 11. 设A和B是两个长为n的有序数组,现在需要将A和B合并成一个排好序的数组,请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。D A. n2 B. Nlogn C. 2n D.2n-1 12. 在n(n>=3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制,下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。 2. 将A中硬币分成X,Y,Z三个集合,使得|X|=|Y|=k, |Z|=n-2k 3. if W(X)≠W(Y) //W(X), W(Y)分别为X或Y的重量 4. then_______ 5. else_______ 6. __________ 7. if n>2 then goto 1 8. if n=2 then 任取A中1枚硬币与拿走硬币比较,若不等,则它不合格;若相等,则A中剩下的硬币不合格 9. if n=1 then A中硬币不合格 正确的填空顺序是( )。D A. b,c,a B. c,b,a C. c,a,b D.a,b,c 13. 在正实数构成的数字三角形排列形式如图所示,第一行的数为a11;第二行的数从左到右依次为a21,a22;…第n行的数为 an1,an2,…,ann。从a11开始,每一行的数aij只有两条边可以分别通向下一行的两个数a(i+1)j和a(i+1)(j+1)。用动态规划算法找出一条从a11向下通到an1,an2,…,ann中某个数的路径,使得该路径上的数之和达到最大。 令C[i,j]是从a11到aij的路径上的数的最大和,并且C[i,0]=C[0,j]=0,则C[i,j]=( )。A A. max{C[i-1,j-1],C[i-1,j]}+aij B. C[i-1,j-1]+c[i-1,j] C. max{C[i-1,j-1],C[i-1,j]}+1 D. max{C[i,j-1],C[i-1,j]}+aij 14. 小明要去南美洲旅游,一共乘坐三趟航班才能到达目的地,其中第1个航班准点的概率是0.9,第2个航班准点的概率为0.8,第3个航班准点的概率为0.9。如果存在第i个(i=1,2)航班晚点,第i+1个航班准点,则小明将赶不上第i+1个航班,旅行失败;除了这种情况,其他情况下旅行都能成功。请问小明此次旅行成功的概率是( )。D

noip2017提高组试题(day1+day2)-Word版

全国信息学奥林匹克联赛(2017)复赛 提高组 1 (请选手务必仔细阅读本页内容) 一.题目概况 注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、中函数 ()的返回值类型必须是,程序正常结束时的返回值必须是 0。 3、全国统一评测时采用的机器配置为: () x2 240 ,2.8, 内存 4G,上述时限以此配置为准。 4、只提供格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。

6、特别提醒:评测在当前最新公布的下进行,各语言的编译器版本以其为准。

【问题描述】1.小凯的疑惑 () 小凯手中有两种面值的金币,两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下,仅凭这两种金币,有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中,最贵的价值是多少金币?注意:输入数据保证存在小凯无法准确支付的商品。 【输入格式】 输入文件名为。 输入数据仅一行,包含两个正整数 a 和 b,它们之间用一个空格隔开,表示小凯手中金币的面值。 【输出格式】 输出文件名为。 输出文件仅一行,一个正整数 N,表示不找零的情况下,小凯用手中的金币不能准确支付的最贵的物品的价值。 【输入输出样例 1】 见选手目录下的 1 和 1。 【输入输出样例 1 说明】 小凯手中有面值为3 和7 的金币无数个,在不找零的前提下无法准确支付价值为1、 2、4、5、8、11 的物品,其中最贵的物品价值为 11,比 11 贵的物品都能买到,比如: 12 = 3 * 4 + 7 * 0 13 = 3 * 2 + 7 * 1 14 = 3 * 0 + 7 * 2

NOIP2017_提高组复赛试题day2

CCF全国信息学奥林匹克联赛(NOIP2017)复赛 提高组 day2 (请选手务必仔细阅读本页内容) 注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:CPU AMD Athlon(tm) II x2 240 processor,2.8GHz, 内存4G,上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、提交的程序代码文件的放置位置请参照各省的具体要求。 6、特别提醒:评测在当前最新公布的NOI Linux下进行,各语言的编译器版本以其为准。

1.奶酪 (cheese.cpp/c/pas) 【问题描述】 现有一块大奶酪,它的高度为h,它的长度和宽度我们可以认为是无限大的,奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系,在坐标系中,奶酪的下表面为z=0,奶酪的上表面为z=h。 现在,奶酪的下表面有一只小老鼠Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交,则Jerry可以从其中一个空洞跑到另一个空洞,特别地,如果一个空洞与下表面相切或是相交,Jerry则可以从奶酪下表面跑进空洞;如果一个空洞与上表面相切或是相交,Jerry则可以从空洞跑到奶酪上表面。 位于奶酪下表面的Jerry想知道,在不破坏奶酪的情况下,能否利用已有的空洞跑到奶酪的上表面去? 空间内两点P1(x1,y1,z1)、P2(x2,y2,z2)的距离公式如下: dist(P1,P2)=√(x1?x2)+(y1?y2)+(z1?z2) 【输入格式】 输入文件名为cheese.in。 每个输入文件包含多组数据。 输入文件的第一行,包含一个正整数T,代表该输入文件中所含的数据组数。 接下来是T组数据,每组数据的格式如下: 第一行包含三个正整数n,h和r,两个数之间以一个空格分开,分别代表奶酪中空洞的数量,奶酪的高度和空洞的半径。 接下来的n行,每行包含三个整数x、y、z,两个数之间以一个空格分开,表示空洞球心坐标为(x,y,z)。 【输出格式】 输出文件名为cheese.out。 输出文件包含T行,分别对应T组数据的答案,如果在第i组数据中,Jerry能从下表面跑到上表面,则输出“Yes”,如果不能,则输出“No”(均不包含引号)。

NOIP2007初赛提高组试题和答案

第十三届全国青少年信息学奥林匹克联赛初赛试题 (提高组Pascal语言二小时完成) ●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●● 一、单项选择题(共10题,每题 1.5分,共计15分。每题有且仅有一个正确答案.)。 1.在以下各项中。()不是CPU的组成部分。 A.控制器 B.运算器 C.寄存器 D.主板 E.算术逻辑单元(ALU) 2.在关系数据库中,存放在数据库中的数据的逻辑结构以()为主。 A.二叉树 B.多叉树 C.哈希表 D.B+树 E.二维表 3.在下列各项中,只有()不是计算机存储容量的常用单位。 A.Byte B.KB C.MB D.UB E.TB 4.ASCII码的含义是()。 A.二—十进制转换码 B.美国信息交换标准代码 C.数字的二进制数码 D.计算机可处理字符的唯一编码 E.常用字符的二进制编码 5.在Pascal语言中,表达式(23or2xor5)的值是() A.18 B.1 C.23 D.32 E.24 6.在Pascal语言中,判断整数a等于0或b等于0或c等于0的正确的条件表达式是() A.not((a<>0)or(b<>0)or(c<>0)) B.not((a<>0)and(b<>0)and(c<>0)) C.not((a=0)and(b=0))or(c=0) D.(a=0)and(b=0)and(c=0) E.not((a=0)or(b=0)or(c=0)) 7.地面上有标号为A、B、C的3根细柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下次依次编号为1,2,3,……,将A柱上的部分盘子经过B柱移入C柱,也可以在B柱上暂存。如果B柱上的操作记录为:“进,进,出,进,进,出,出,进,进,出,进,出,出”。那么,在C柱上,从下到上的盘子的编号为()。 A.243657 B.241257 C.243176 D.243675 E.214375 8.与十进制数17.5625相对应的8进制数是()。 A.21.5625 B.21.44 C.21.73 D.21.731 E.前4个答案都不对 9.欧拉图G是指可以构成一个闭回路的图,且图G的每一条边恰好在这个闭回路上出现一次(即一笔画成)。在以下各个描述中,不一定是欧拉图的是:()。 A.图G中没有度为奇数的顶点 B.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)

NOIP2017普及组初赛试题及答案

NOIP2017普及组初赛试题及答案 文字标黑部分为试题答案。 一、单项选择题(共20题,每题1.5分,共计30分;每题有且仅有一个正确选项) 1.在8位二进制补码中,10101011表示的数是十进制下的( )。 A. 43 B. -85 C. -43 D. -84 2.计算机存储数据的基本单位是( )。 A. bit B. Byte C. GB D. KB 3.下列协议中与电子邮件无关的是( )。 A. POP3 B. SMTP C. WTO D. IMAP 4.分辨率为800x600、16位色的位图,存储图像信息所需的空间为( )。 A.937.5KB B. 4218.75KB C.4320KB D. 2880KB 5.计算机应用的最早领域是( )。 A.数值计算 B.人工智能 C.机器人 D.过程控制 6.下列不属于面向对象程序设计语言的是( )。 页脚内容1

A. C B. C++ C. Java D. C# 7.NOI的中文意思是( )。 A.中国信息学联赛 B.全国青少年信息学奥林匹克竞赛 C.中国青少年信息学奥林匹克竞赛 D.中国计算机协会 8. 2017年10月1日是星期日,1999年10月1日是( )。 A.星期三 B.星期日 C.星期五 D.星期二 9.甲、乙、丙三位同学选修课程,从4门课程中,甲选修2门,乙、丙各选修3门,则不同的选修方案共有( )种。 A. 36 B. 48 C. 96 D. 192 10.设G是有n个结点、m条边(n ≤m)的连通图,必须删去G的( )条边,才能使得G变成一棵树。 A.m–n+1 B. m-n C. m+n+1 D.n–m+1 11.对于给定的序列{ak},我们把(i, j)称为逆序对当且仅当i < j且ai> aj。那么 序列1, 7, 2, 3, 5, 4的逆序对数为()个。 页脚内容2

2008noip提高组初赛试题

第十四届全国青少年信息学奥林匹克联赛初赛试题 (提高组Pascal语言二小时完成) ●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●● 一、单项选择题(共10题,每题1.5分,共计15分。每题有且仅有一个正确答案)。 1.在以下各项中,()不是操作系统软件。 A.Solaris B.Linux C.Sybase D.Windows Vista E.Symbian 2.微型计算机中,控制器的基本功能是()。 A.控制机器的各个部件协调工作 B.实现算数运算与逻辑运算 C.存储各种控制信息D.获取外部信息E.存放程序和数据 3.设字符串S=“Olympic”,S的非空字串的数目是()。 A.29 B.28 C.16 D.17 E.7 4.完全二叉树有2*N-1的结点,则它的叶子结点数目是()。 A.N-1 B.2*N C.N D.2N-1 E.N/2 5.将数组{8,23,4,16,77,-5,53,100}中元素从大到小按顺序排序,每次可以交换任意两个元素,最少要交换()次。 A.4 B.5 C.6 D.7 E.8 6.设栈S的初始状态为空,元素a,b,c,d,e,f依次入栈,出栈顺序为b,d,c,f,e,a那么栈容量至少应该是()。 A.6 B.5 C.4 D.3 E.2 7.与十进制数28.5625相等的四进制数是() A.123.21 B.131.22 C.130.22 D.130.21 E.130.20 8.递归过程和函数调用时,处理参数和返回地址,通常使用一种称为()的数据结构。A.队列B.多维数组C.线性表D.链表E.栈 9.TCP/IP 是一组构成互联网基础的网络协议,字面上包括两组协议:传输控制协议(TCP)和网际互联协议(IP)。TCP/IP协议把Internet网络系统描述成具有4个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务,包括寻址和路由器选择等功能的是()。A.链路层B.网络层C.传输层D.应用层E.会话层 10.对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均查找长度(平均比较次数)是()。 A.35/11 B.34/11 C.33/11 D.32/11 E.34/10 二、不定项选择题(共10题,每题1.5分,共计15分。每题正确答案的个数大于或等于1。

NOIP2016提高组C初赛试题

如对您有帮助,请购买打赏,谢谢您! 第二十二届全国青少年信息学奥林匹克联赛初赛 提高组 C++语言试题 竞赛时间:2016 年 10 月 22 日 14:30~16:30 选手注意: ● 试题纸共有 13 页,答题纸共有 2 页,满分 100 分。请在答题纸上作答,写 在试题纸上的一律无效。 ● 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共 15 题,每题 1.5 分,共计 22.5 分;每题有且仅有一个正确 选项) 1. 以下不是微软公司出品的软件是( )。 A. Powerpoint B. Word C. Excel D. Acrobat Reader 2. 如果开始时计算机处于小写输入状态,现在有一只小老鼠反复按照 CapsLock 、 字母键 A 、字母键 S 和字母键 D 的顺序来回按键,即 CapsLock 、A 、S 、D 、S 、A 、CapsLock 、A 、S 、D 、S 、A 、CapsLock 、A 、S 、D 、S 、A 、……,屏幕上输出的第 81 个字符是字母( )。 A. A B. S C. D D. A 3. 二进制数 00101100 和 01010101 异或的结果是( )。 A. 00101000 B. 01111001 C. 01000100 D. 00111000 4. 与二进制小数 0.1 相等的八进进制数是( )。 A. 0.8 B. 0.4 C. 0.2 D. 0.1 5. 以比较作为基本运算,在 N 个数中找最小数的最少运算次数为( )。 A. N B. N-1 C. N 2 D. log N 6. 表达式 a*(b+c)-d 的后缀表达形式为( )。 A. abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 7. 一棵二叉树如右图所示,若采用二叉树链表存储该二叉 树(各个结点包括结点的数据、左孩子指针、右孩子指 针)。如果没有左孩子或者右孩子,则对应的为空指针。 那么该链表中空指针的数目为( )。 A . 6 B . 7 C . 12 D. 14 8. G 是一个非连通简单无向图,共有 28 条边,则该图至少有( )个顶点。 A. 10 B. 9 C.8 D.7 CCF NOIP2016 初赛提高组 C++语言试题 第 1 页,共 13 页

NOIP2018提高组复赛试题day2

CCF全国信息学奥林匹克联赛(NOIP2018)复赛 提高组 day2 (请选手务必仔细阅读本页内容) 注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。 2、C/C++中函数main()的返回值类型必须是int,程序正常结束时的返回值必须是0。 3、全国统一评测时采用的机器配置为:Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz,内存 32GB。上述时限以此配置为准。 4、只提供Linux格式附加样例文件。 5、特别提醒:评测在当前最新公布的NOI Linux下进行,各语言的编译器版本以其为准。

1.旅行 (travel.cpp/c/pas) 【问题描述】 小Y是一个爱好旅行的OIer。她来到X国,打算将各个城市都玩一遍。 小Y了解到,X国的 n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小Y只能通过这些道路从一个城市前往另一个城市。 小Y的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小Y回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小Y要求在旅行方案中,每个城市都被访问到。 为了让自己的旅行更有意义,小Y决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为 n 的序列。她希望这个序列的字典序最小,你能帮帮她吗? 对于两个长度均为 n 的序列A和B,当且仅当存在一个正整数x,满足以下条件时,我们说序列A的字典序小于B。 ?对于任意正整数1≤i

noip提高组c初赛试题与答案

2009 第十五届全国青少年信息学奥林匹克联赛初赛试题 提高组 C++ 语言 二小时完成 ) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 . 单项选择题 (共 10 题,每题分,共计 15 分。每题有且仅有一个正确答 案。) 1、关于图灵机下面的说法哪个是正确的: 图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作 用。 2、关于BIOS 下面的说法哪个是正确的: BIOS 里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的 驱动程序。 BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 3、已知大写字母A 的ASCII 编码为65(十进制),则大写字母J 的 十六进制ASCII 编码为: 4、在字长为 16位的系统环境下,一个 16位带符号整数的二进制补码为 101。 其对应的十进制整数应该是: n 个分支结点(非叶结点)的非空满 k 叉树,k>=1,它的叶结点数 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 6. 表达式 a*(b+c )-d 的后缀表达式是: A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 7、最优前缀编码,也称 Huffman 编码。这种编码组合的特点是对于较频繁使用 的元素给与 较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是 合法的前缀编码。 A )(00, 01, 10, 11) A) 图灵机是世界上最早的电子计算机。 B) 由于大量使用磁带操作,图灵机运行速度很慢。 C) 图灵机只是一个理论上的计算模型。 D) A) BIOS 是计算机基本输入输出系统软件的简称。 B) C) BIOS 一般由操作系统厂商来开发完成。 D) A) 48 B) 49 C) 50 D) 以上都不是 A) 19 B) -19 C) 18 D) -18 5、一个包含 目为: A) nk + 1

NOIP提高组C+初赛试题与答案

2009第十五届全国青少年信息学奥林匹克联赛初赛试题 (提高组 C++语言二小时完成) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 一.单项选择题(共10题,每题1.5分,共计15分。每题有且仅有一个正确答案。) 1、关于图灵机下面的说法哪个是正确的: A)图灵机是世界上最早的电子计算机。 B)由于大量使用磁带操作,图灵机运行速度很慢。 C)图灵机只是一个理论上的计算模型。 D)图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 2、关于BIOS下面的说法哪个是正确的: A)BIOS是计算机基本输入输出系统软件的简称。 B)BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程 序。 C)BIOS一般由操作系统厂商来开发完成。 D)BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 3、已知大写字母A的ASCII编码为65(十进制),则大写字母J的十六进制 ASCII编码为: A) 48 B) 49 C) 50 D) 以上都不是 4、在字长为16101101。其对应的十进制整数应该是: A)19 B) -19 C) 18 D) -18 5、一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为: A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 6. 表达式a*(b+c)-d的后缀表达式是: A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 7、最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素 给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。 A)(00,01,10,11) B)(0,1,00,11)

NOIP2015提高组C++试题

第二十一届全国青少年信息学奥林匹克联赛初赛 提高组C++语言试题 竞赛时间:2015 年10 月11 日14:30~16:30 选手注意: ●试题纸共有9页,答题纸共有2页,满分100 分。请在答题纸上作答,写在试题纸上的 一律无效。 ●不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。 一、单项选择题(共15 题,每题1.5 分,共计22.5 分;每题有且仅有一个正确选项) 1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以()形式进行的。 A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码 2. 下列说法正确的是()。 A. CPU 的主要任务是执行数据运算和程序控制 B. 存储器具有记忆能力,其中信息任何时候都不会丢失 C. 两个显示器屏幕尺寸相同,则它们的分辨率必定相同 D. 个人用户只能使用W ifi 的方式连接到I nternet 3. 与二进制小数0.1 相等的十六进制数是()。 A. 0.8 B. 0.4 C. 0.2 D. 0.1 4. 下面有四个数据组,每个组各有三个数据,其中第一个数据为八进制数,第二个数据为 十进制数,第三个数据为十六进制数。这四个数据组中三个数据相同的是()。A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2 5. 线性表若采用链表存储结构,要求内存中可用存储单元地址()。 A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可 6. 今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f 依次进行进栈,进栈,出栈, 进栈,进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为()。 A. f B. c C. a D. b

相关文档
相关文档 最新文档