下载文档原格式
2012年全国青少年信息学奥林匹克联赛初赛模拟试题一.单项选择题（共10题,每题1.5分,共计15分,每题有且仅有一个正确答案。
）1、以下说法正确的是（）A、第一个提出“goto语句有害论”的计算机科学家是Donald E.KnuthB、被誉为“迄今最伟大的计算机程序员、算法学家”的是Edsger Wybe DijkstraC、世界上第一位程序员是V on NoumaD、被誉为“计算机语言之母”的是Grace Hopper2、关于CPU的说法正确的是（）A、计算机的运算速度取决于给定的时间内,它的处理器所能处理的数据量。
B、64位计算机指的是CPU每秒钟可处理的数据为2^64位。
C、双核CPU,是指在一个主板上放入两个CPU并行进行工作。
D、我国自主产权的CPU龙芯3A集成了两个处理器核心3、ASCII码表中的大写字母后有6个其它字符,接着便是小写字母。
现已知:A字母的ASCII码为（41）16{表示16进制数41 },那么f应为( )10A、46B、78C、102D、1084、Pascal的创始人是（）。
（A）Donald E.Knuth （B）Steve Jobs （C）Charles Bachman D （D）Niklaus Wirth5、若二叉树的先序遍历序列为ABDECF,中序遍历序列DBEAFC,则其后序遍历序列为（）A. DEBAFCB. DEFBCAC. DEBCFAD. DEBFCA6、已知后缀表达式abc+*d-,则它的中缀表达式和前缀表达式分别是:A） (a+b)*c-d -+*abcd B）a+b*c-d -+a*bcdC）a*(b+c)-d -*a+ bcd D）a*(b+c)-d -a b*+cd7、由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为（）A.23B.37C.44D.468、排序算法是稳定的意思是:关键码相同的记录排序前后相对位置不发生改变,下列哪种排序算法是不稳定的:A) 冒泡排序 B) 插入排序 C) 归并排序 D) 快速排序9、下图给出了一个加权有向图,从顶点V1出发,以下哪个是活动中的关键路径（）A. V1,V5,V3,V2B. V1,V4,V3,V2C. V1,V4, V2D. V1,V4,V5,V3,V210、以下有关全国信息学奥林匹克竞赛说法有误的是（）A、 NOI评测只检查按照要求输出的结果,而不涉及过程和算法。
第十八届全国青少年信息学奥林匹克联赛初赛〔普与组C++语言试题〕竞赛时间：2012年10月13日14:30~16:30选手注意：●试题纸共有10页，答题纸共有2页，总分为100分。
请在答题纸上作答，写在试题纸上一律无效。
●不得使用任何电子设备〔如计算器、手机、电子词典等〕或查阅任何书籍资料一、单项选择题〔共20题，每题1.5分，共计30分；每题且仅有一个正确选项〕1．计算机如果缺少〔〕，将无法正常启动。
A．内存 B．鼠标C． U盘 D．摄像头2．〔〕是一种先进先出的线性表。
A．栈B．队列 C．哈希表〔散列表〕 D．二叉树3．目前计算机芯片〔集成电路〕制造的主要原料是〔〕，它是一种可以在沙子中提炼出的物质。
A．硅B．铜 C．锗 D．铝4．十六进制数9A在〔〕进制下是232。
A．四 B．八 C．十 D．十二5．〔〕不属于操作系统。
A．Windows B．DOS C．Photoshop D．NOI Linux6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是〔〕。
A．ABC B．CBA C．ACB D．BAC7．目前个人电脑的〔〕市场占有率最靠前的厂商包括Intel、AMD等公司。
A．显示器 B．CPU C．内存 D．鼠标8．使用冒泡排序对序列进展升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行〔〕次操作，才能完成冒泡排序。
A．0 B．5 C．10 D．159． 1946年诞生于美国宾夕法尼亚大学的ENIAC属于〔〕计算机。
A．电子管 B．晶体管 C．集成电路 D．超大规模集成电路10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。
如果用现实生活中的例子来比喻这些“层〞，以下最恰当的是〔〕。
A．中国公司的经理与波兰公司的经理交互商业文件B．军队发布命令C．国际会议中，每个人都与他国地位对等的人直接进展会谈D．体育比赛中，每一级比赛的优胜者晋级上一级比赛11．矢量图〔Vector Image〕图形文件所占的贮存空间比拟小，并且无论如何放大、缩小或旋转等都不会失真，是因为它〔〕。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）竞赛时间：2012年10月13日14:30~16:30选手注意：●试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项）1．计算机如果缺少（），将无法正常启动。
A．内存B．鼠标C．U盘D．摄像头2．（）是一种先进先出的线性表。
A．栈B．队列C．哈希表（散列表）D．二叉树3．目前计算机芯片（集成电路）制造的主要原料是（），它是一种可以在沙子中提炼出的物质。
A．硅B．铜C．锗D．铝4．十六进制数9A在（）进制下是232。
A．四B．八C．十D．十二5．（）不属于操作系统。
A．Windows B．DOS C．Photoshop D．NOI Linux6．如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（）。
A．ABC B．CBA C．ACB D．BAC7．目前个人电脑的（）市场占有率最靠前的厂商包括Intel、AMD等公司。
A．显示器B．CPU C．内存D．鼠标8．使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列5，4，3，2，1需要执行（）次操作，才能完成冒泡排序。
A．0 B．5 C．10 D．159．1946年诞生于美国宾夕法尼亚大学的ENIAC属于（）计算机。
A．电子管B．晶体管C．集成电路D．超大规模集成电路10．无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。
如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。
A．中国公司的经理与波兰公司的经理交互商业文件B．军队发布命令C．国际会议中，每个人都与他国地位对等的人直接进行会谈D．体育比赛中，每一级比赛的优胜者晋级上一级比赛11．矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。
第十八届全国青少年信息学奥林匹克联赛初赛（普及组C++语言试题）2012 年 10 月 13 日 14:30~16:30选手注意:试题纸共有10页，答题纸共有2页，满分100分。
请在答题纸上作答，写在试题纸上一律无效。
不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料、单项选择题（共 20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1 •计算机如果缺少（ ），将无法正常启动。
A .内存B .鼠标C . U 盘D . 摄像头2 . ( ）是一种先进先出的线性表。
A .栈B .队列C .哈希表（散列表）D .二叉树3 . 目前计算机芯片（集成电路） 制造的主要原料是（）,它是一种可以在沙子中提炼出的物质。
A . 硅B .铜C .锗D . 铝 4 . 十六进制数9A 在（ ） 进制下是232。
A . 四B .八C .十D . 十二5 . ( ）不属于操作系统。
A . WindowsB . DOSC . PhotoshopD . NOI Linux6.如果一棵二叉树的中序遍历是 BAC ，那么它的先序遍历不可能是（ ）。
8 .使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 1个逆序对，因此序列 5, 4, 3, 2, 1需要执行（）次操作，才能完成冒泡排序。
A . 0B . 5C . 10D . 159 . 1946年诞生于美国宾夕法尼亚大学的 ENIAC 属于（ ）计算机。
10 .无论是TCP/IP 模型还是OSI 模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层 中。
如果用现实生活中的例子来比喻这些“层” ，以下最恰当的是（ ）。
竞赛时间: A . ABC B . CBA C . ACB D . BAC7.目前个人电脑的（ ）市场占有率最靠前的厂商包括 A .显示器 B . CPU C .内存 In tel 、AMD 等公司。
D .鼠标A .电子管B .晶体管C .集成电路D .超大规模集成电路B •军队发布命令11.矢量图（Vector Image）图形文件所占的贮存空间比较小，并且无论如何放大、缩小或旋转等都不会失真，是因为它（）。
NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题8 分，共计32 分）阅读程序的最好方法并非是依次从头到尾。
程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。
因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。
1、分层读：高层入手，逐层深入，正确理解程序。
2、写注解：固化、总结、提炼已有的理解成果。
3、先模拟：根据代码顺序跟踪变量，模拟运算。
4、找规律：先模拟几次循环后，找出背后的规律。
5、看功能：从代码结构和运算结果判断程序功能。
6、猜算法：有时不知道算法，通过结构和函数猜一猜。
7、换方法：了解程序本质后，换一个熟悉的方法试试。
对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。
其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。
阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。
如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。
当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。
祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-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];}cout<<i<<endl; return 0;}输入：4 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-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;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x>=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include <iostream>using namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){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;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 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如len>ans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。
CCF全国信息学奥林匹克联赛（NmP2012）复赛提高组day22． 1 ·同余方程〖问题描述〗求关于的同余方程三1 (mod句的最小正整数解。
输入〗输入文件为mod.ino输入只有一行，包含两个正整数用一个空格隔开输出〗输出文件为mod.outo输出只有一行，包含一个正整数№即最小正整数解。
输入数据保证一定有解。
〖输入输出样例〗对于40％的数据，2 L000：对于60％的数据，2 50，000，000：对于100％的数据，2，2，000，000，000。
2 ·借教室 (classroom. cpp/c/pas)问题描述〗在大学期间，经常需要租借教室。
大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。
教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。
我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。
共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。
即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。
借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。
如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。
这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。
现在我们需要知道，是否会有订单无法完全满足。
如果有，需要通知哪一个申请人修改输入〗输入文件为classroom.in第一行包含两个正整数n，m,表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dJ,s]，t]，表示租借的数量，租借开始、结束分别在第几天。
