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

2006第十二届noip提高组初赛试题


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

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

一、 单项选择题 (共 10题,每题 1.5分,共计 15分。每题有且仅有一个正确答案.) 。 1. 在以下各项中。 ( A. 控制器 )不是 CPU的组成部

分。 C. 寄存器 D. ALU E. RAM )上一个 ROM芯片上的程序。 D. 内存条 E. 硬盘

B. 运算器

2. BIOS(基本输入输出系统)是一组固化在计算机内( A. 控制器 B. CPU C. 主板

3.在下面各世界顶级的奖项中, 为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是 ( 。 ) A. 沃尔夫奖 D. 图灵奖 B. E. 诺贝尔奖 南丁格尔奖 C. 菲尔兹奖

4. 在编程时 (使用任一种高级语言, 不一定是 C) , 如果需要从磁盘文件中输入一个很大的二维数组 (例 如 1000*1000 的 double 型数组) ,按行读(即外层循环是关于行的)与按列读(即外层循环是关于 列 的)相比,在输入效率上( ) 。 A. 没有区别 C. 按行读的方式要高一些 B. 有一些区别,但机器处理速度很快,可忽略不计 D. 按列读的方式要高一些 )
由 OIFans.cn 收集

E. 取决于数组的存储方式。

5.在 C语言中,表达式 21^2的值是( A. 441 B. 42 C.23

D.24

E.25 )

6.在 C语言中,判断 a不等于 0且 b不等于 0的正确的条件表达式是( A. !a==0 || !b==0 B. !((a==0)&&(b==0)) C. !(a==0&&b==0) D. a!=0 || b!=0 E. a && b

7.某个车站呈狭长形,宽度只能容下一台车, 并且只有一个出入口。已知某时刻该车站状态为空, 从 这一时刻开始的出入记录为: “进,出,进,进,进,出,出,进,进,进,出,出” 。假设车辆入站的 顺 序为 1,2,3,??,则车辆出站的顺序为( A. 1, 2, 3, 4, 5 D. 1, 4, 3, 7, 2 。 ) C. 1, 4, 3, 7, 6
由 OIFans.cn 收 集

B. 1, 2, 4, 5, 7 E. 1, 4, 3, 7, 5

8.高度为 n的均衡的二叉树是指:如果去掉叶结点及相应的树枝,它应该是高度为 n-1的满二叉树。 在这里,树高等于叶结点的最大深度,根结点的深度为 0,如果某个均衡的二叉树共有 2381个结 点, 则该树的树高为( A. 10 B. 11 。 ) C. 12 D. 13 E. 2 – 1
10

1

9. 与十进制数 1770.625 对应的八进制数是( A. 3352.5 D. 3350.1151 B. 3350.5

。 ) C. 3352.1161

E. 前 4个答案都不对 ) 次比较, 完成从小到大的

10. 将 5个数的序列排序, 不论原先的顺序如何, 最少都可以通过 ( 排序。
由 OIFans.cn 收 集

A. 6

B. 7

C. 8

D. 9

E. 10

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

11. 设 A=B=D=true,C=E=false,以下逻辑运算表达式值为真的有( A. (? A∧B)∨(C∧D)∨ ? E C. A∧(B∨C∨D∨E) 12. (2010) + (32) 的结果是(
16 8

)。

B.? (((A∧B)∨C)∧D∧E) D. (A∧(B∨C)) ∧D∧E 。 )
16

A. (8234)

10

B. (202A)
2

C. (100000000110)

D. (2042)

16

13. 设栈 S 的初始状态为空,元素 a, b, c, d, e 依次入栈,以下出栈序列不可能出现的有 ( )。 B. b, c, a, e, d D. d, c, e, b, a

A. a, b, c, e, d C. a, e, c, b, d

14. 已知 6个结点的二叉树的先根遍历是 1 2 3 4 5 6(数字为结点的编号,以下同) ,后根遍历是 3 2 5 6 4 1,则该二叉树的可能的中根遍历是( A. 3 2 1 4 6 5 C. 2 3 1 5 4 6 B. 3 2 1 5 4 6 D. 2 3 1 4 6 5 。 ) )

15. 在下列各数据库系统软件中,以关系型数据库为主体结构的是 SQL 和 bas 一定是( A. ACCESS C. Oracle 微软的 稳定性更高 B. SQL Server D. Foxpro 。 )
由 OIFans.cn 收集

16.在下列各软件中,属于 NOIP竞赛(复赛)推荐使用的语言环境有( A. gcc/g++ C. Turbo C B. Turbo Pascal D. free pascal )。 D. RAM )。

17. 以下断电之后将不能保存数据的有( A. 硬盘 B. ROM C. 显存

18. 在下列关于计算机语言的说法中,正确的有( A. Pascal 和 C 都是编译执行的高级语言

2

B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C. C++是历史上的第一个支持面向对象的计算机语言 D. 高级语言比汇编语言更高级,是因为它的程序的运行效率更高 19. 在下列关于计算机算法的说法中,正确的有( A. 一个正确的算法至少要有一个输入 B. 算法的改进,在很大程度上推动了计算机科学与技术的进步 C. 判断一个算法的好坏,主要依据它在某台计算机上具体实现时的运行时间 D. 目前仍然存在许多涉及到国计民生的重大课题,还没有找到能够在计算机上实施的有效算法 20. 在下列关于青少年信息学竞赛的说法中,你赞成的是 ( ) (本题不回答为 0 分,答题一 )。

律满分)。 A. 举行信息学竞赛的目的,是为了带动广大青少年学科学、爱科学,为造就一大批优秀 的计算机科学 与技术人才奠定良好的基础 B. 如果竞赛优胜者不能直接保送上大学,我今后就不再参与这项活动了 C. 准备竞赛无非要靠题海战术,为了取得好成绩,就得拼时间、拼体力 D. 为了取得好成绩, 不光要看智力因素, 还要看非智力因素。 优秀选手应该有坚韧不拔的意志, 有 严谨求实的作风,既要努力奋进,又要胜不骄败不馁 三.问题求解(共 2题,每题 5分,共计 10分) 1.将 2006个人分成若干不相交的子集,每个子集至少有 3个人,并且: (1)在每个子集中,没有人认识该子集的所有人。
由 OIFans.cn 收集

(2)同一子集的任何 3个人中,至少有 2个人互不认识。

由 OIFans.cn 收集

(3)对同一子集中任何 2个不相识的人,在该子集中恰好只有 1个人认识这两 个人。 则满足上述条件的子集最多能有___________个? 没有任何节点与其它节点都相连 2. 将边长为 n的正三角形每边 n等分, 过每个分点分别做另外两边的平行线, 得到若干个正三角 形, 我们称为小三角形。 正三角形的一条通路是一条连续的折线, 起点是最上面的一个小三角形, 终点是最 下面一行位于中间的小三角形。在通路中,只允许由一个小三角形走到另一个与其有公 共边的且位于同 一行或下一行的小三角形,并且每个小三角形不能经过两次或两次以上(图中 是 n=5 时一条通路的例 子) 。设 n=10,则该正三角形的不同的通路的总数为_____________。

四.阅读程序写结果(共 4题,每题 8分,共计 32分) 1. #include <stdio.h> int main() {int i,u[4],v[4],x,y=10; for(i=0;i<=3;i++)
3

scanf("%d", &u[i]); v[0]=(u[0]+u[1]+u[2]+u[3])/7; v[1]=u[0]/((u[1]-u[2])/u[3]); v[2]=u[0]*u[1]/u[2]*u[3]; v[3]=v[0]*v[1]; x=(v[0]+v[1]+2)-u[(v[3]+3)%4]; if(x>10)
由 OIFans.cn 收集

y+= (v[2]*100-v[3])/(u[u[0]%3]*5); else y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5); printf("%d,%d\n", x,y); return 0; } /*注:本例中,给定的输入数据可以避免分母为 0或下标越界。 */ 输入:9 3 9 4 输出:_______________

2.#include <stdio.h> main() {int i,j,m[]={2,3,5,7,13}; long t; for (i=0;i<=4;i++) {t=1; for(j=1;j<m[i];j++) t*=2; printf("%ld ",(t*2-1)*t); } printf("\n"); } 输出:____________________ 3.#include "stdio.h" #define 7 int fun1(char s[],char a,int n) {int j; j=n; while(a<s[j] && j>0) j--;
4
由 OIFans.cn 收 集

return j; } int fun2(char s[],char a,int n) {int j; j=1; while(a>s[j] && j<=n) j++; return j; } void main() {char s[8]; int k,p; for(k=1;k<=7;k++) s[k]=65+2*k+1; p=fun1(s,77,7); printf(“%d\n”,p+fun2(s,77,7)); } 输出:_____________ 4.#include <stdio.h> void digit(long n,long m) {if(m>0) printf("%2ld",n%10); if(m>1) digit(n/10,m/10); printf("%2ld",n%10); } main() {long x,x2; printf("Input a number:\n"); scanf("%ld",&x); x2=1; while(x2<x) x2*=10; x2/=10;
由 OIFans.cn 收 集 由 OIFans.cn 收 集

digit(x,x2); printf("\n"); }
5

输入:9734526 输出:______________________________

五.完善程序 (前 5空,每空 2分,后 6空,每空 3分,共 28分) 1 (选排列) . 下面程序的功能是利用递归方法生成从 1到 n(n<10)的 n个数中取 k(1<=k<=n)个数的 全部可能的排列(不一定按升序输出) 。例如,当 n=3,k=2时,应该输出(每行输出 5个排列) : 12 13 21 23 32 31 程序: #include <stdio.h> int n,k,a[10]; long count=0; void perm2(int j) {int i,p,t; if( ① )

{for(i=k;i<=n;i++) {count++; t=a[k]; a[k]=a[i]; a[i]=t; for( ② )

printf("%1d",a[p]); /* "%1d"中是数字 1,不是字母 l */ printf(" "); t=a[k];a[k]=a[i];a[i]=t; if(count%5==0) printf("\n"); }
由 OIFans.cn 收集

return; } for(i=j;i<=n;i++) {t=a[j]; a[j]=a[i]; a[i]=t; ③ ; t=a[j]; ④ ;
6

} }

main() {int i; printf("\nEntry n,k (k<=n):\n"); scanf("%d%d",&n,&k); for(i=1;i<=n;i++) a[i]=i; ⑤ } 2. (TSP问题的交叉算子)TSP问题(Traveling Salesman Problem)描述如下:给定 n个城 市, 构成一个完全图, 任何两城市之间都有一个代价 (例如路程、 旅费等) , 现要构造遍历所有城市的环 路, 每个城市恰好经过一次,求使总代价达到最小的一条环路。 遗传算法是求解该问题的一个很有效的近似算法。在该算法中,一个个体为一条环路,其编码 方法 之一是 1到 n这 n个数字的一个排列,每个数字为一个城市的编号。例如当 n=5时, “3 4 2 1 5” 表示该方案实施的路线为 3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作, 产生两 个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下: (1)选定中间一段作为互换段,该段的起止下标为 t1,t2,随机生成 t1,t2后,互换两段。 (2)互换后, 在每个新的排列中可能有重复数字, 因而不能作为新个体的编码, 一般再做两步处理: (2.1) 将两个互换段中,共同的数字标记为 0,表示已处理完。 (2.2) 将两个互换段中其余数字标记为 1,按顺序将互换段外重复的数字进行替 换。 例如:n=12,两个个体分别是:
由 OIFans.cn 收 集

;

a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5, t2=8。 上述每一行中, 两个星号间的部 * 6 7 10 11 *

分为互换段。 假定数组的下标从 1开始, 互换后有: a1: 1 3 5 4 10 12 8 11

a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 然后,将数字 6,7对应的项标记为 0,星号内数字 2,9,10,11 对应的项标记为 1, 并且按顺序对 应关系为:10<->2, 11<->9。 于是, 将 a1[9]=10替换为 a1[9]=2, 将 a2[2]=2替换为 a2[2]=10,

类似再做第 2组替换。这样处理后,就得到了两个新个体: a1: 1 3 5 4 a2: 3 10 1 12 2 6 6 7 10 11 2 12 8 9 7 9 8
7

5 4 11

(3)输出两个新个体 的编码。 程序: #include <stdio.h> #include <stdlib.h> #define N 20 int a1[N],a2[N],kz1[N],kz2[N],n; int rand1(int k) {int t=0; while(t<2|| t>k) t=(int)((double)rand()/RAND_MAX*k); return t; } void read1(int a[],int m) {读入数组元素 a[1]至 a[m],a[0]=0,略。} void wrt1(int a[],int m) {输出数组元素 a[1]至 a[m],略。} void cross(int a1[], int a2[],int t1, int t2, int n)

{int i,j,k,t,kj; for(i=t1; i<=t2; i++) {t=a1[i];
a1[i]=a2[i] a2[i]=t ①



} for(i=1;i<=n;i++)
由 OIFans.cn 收集

if(i<t1 || i>t2) kz1[i]=kz2[i]=-1; else
② kz1[i]=k2[i]=1



for(i=t1;i<=t2;i++) for(j=t1;j<=t2;j++) if(a1[i]==a2[j]) { }
8

③ kz1[i]=k2[i]=0

; break;

for(i=t1;i<=t2;i++) if(kz1[i]==1) {for(j=t1;j<=t2;j++) if(kz2[j]==1) {kj=j; break; } for(j=1;j<=n;j++) if(
④a1[j]==a1[i] && kz1[j]==-1

)

{a1[j]=a2[kj];break; } for(j=1;j<=n;j++) if(
⑤ a2[j]==a2[i] && kz2[j]==-1 )

{a2[j]=a1[i]; break; } } kz1[i]=kz2[kj]=0; } main() {int k,t1,t2; printf("input (n>5):\n"); scanf("%d",&n); printf("input array 1 (%d'numbers):\n",n); printf("input array 2 (%d'numbers):\n",n); t1=rand1(n-1); do {t2=rand1(n-1); }while(t1==t2); if(t1>t2) {k=t1; t1=t2; t2=k; }
⑥cross(a1,a2,t1,t2,n)
由 OIFans.cn 收集

read1(a1,n); read1(a2,n);

wrt1(a1,n); wrt1(a2,n); }

9


相关文章:
2006第十二届noip提高组初赛试题
2006第十二届noip提高组初赛试题_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2006第十二届noip提高组初赛试题_学科竞赛_高中教育_教育专区。...
2006第十二届noip提高组初赛试题
11页 免费 noip2010提高组初赛试题及... 8页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP历年复赛提高组试题(2006-2014)
2006~2014 年 NOIP 复赛试题集(提高组) 第十二届全国信息学奥林匹克分区联赛(NOIP2006)复赛试题(提高组 竞赛用时:3 小时) 关于竞赛中不同语言使用限制的说明一...
NOIP2006提高组试卷
第十二届全国青少年信息学奥林匹克 联赛复赛试题(NOIP2006 提高组) 竞赛时间:2006 年 11 月 18 日上午 8:30—11:30 试题名称 目录 输入文件 名 输出文件 名...
NOIP2006 提高组试题
NOIP 2006 复赛试题 (提高组) 第十二届全国青少年信息学奥林匹克 联赛复赛试题提高组) (NOIP2006 提高组) 竞赛时间: 竞赛时间:2006 年 11 月 18 日上午 8:30...
NOIP2006普及组初赛试题
NOIP2006普及组初赛试题_学科竞赛_初中教育_教育专区。NOIP2006届普及组初赛试题 第十二届全国青少年信息学奥林匹克联赛初赛试题( 普及组 Pascal 语言 二小时完成 ) ...
NOIP2006(pascal)第十二届全国青少年信息学奥林匹克联赛初赛试题
NOIP2006(pascal)第十二届全国青少年信息学奥林匹克联赛初赛试题_学科竞赛_高中教育_教育专区。NOIP2006(pascal)第十二届全国青少年信息学奥林匹克联赛初赛试题 ...
NOIP2002提高组初赛试题答案
第八全国青少年信息学奥林匹克联赛( 第八全国青少年信息学奥林匹克联赛(NOIP2002)初赛 ) 试题(提高组参考答案) 提高组参考答案)一、 选择一个正确答案代码(A...
NOIP2006第十二届全国青少年信息学奥林匹克联赛复赛试题提高组
NOIP 2006 复赛试题 (提高组) 第十二届全国青少年信息学奥林匹克 联赛复赛试题提高组) (NOIP2006 提高组) 竞赛时间: 竞赛时间:2006 年 11 月 18 日上午 8:...
NOIP2006-2008初赛(提高组)
马鞍山二中 NOIP2006~2008 初赛(提高组)试题&解析 第十二届全国青少年信息学奥林匹克联赛初赛试题(提高组 Pascal 语言 二小时完成 )●● 全部试题答案均要求写在...
更多相关标签:
noip2006提高组初赛 | noip2006普及组初赛 | noip2006初赛 | noip2015提高组初赛 | noip2016提高组初赛 | noip2012提高组初赛 | noip2013提高组初赛 | noip2011提高组初赛 |