noip2010提高组PASCAL初赛试题和答案

第十六届全国青少年信息学奥林匹克联赛初赛试题试题（提高组Pascal语言两小时完成）一、单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确选项。

）1.与16进制数 A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制组成。

A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。

A.P∨（┓P∧Q）∨(┓P∧┓Q)B.Q∨（┓P∧Q）∨（P∧┓Q）C.P∨Q∨（P∧┓Q）∨（┓P∧Q）D.P∨┓Q∨（P∧┓Q）∨(┓P∧┓Q)4.Linux下可执行文件的默认扩展名是( )。

A. exeB. comC.dllD. 以上都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。

A. 100B. 144C. 164D. 1966.提出“存储程序”的计算机工作原理的是（）。

A. 克劳德•香农B.戈登•摩尔C. 查尔斯•巴比奇D. 冯•诺依曼7.前缀表达式“+ 3 * 2 + 512 ” 的值是（）。

A. 23B. 25C. 37D. 658.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了( )。

A. 寄存器B.高速缓存C. 闪存D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（）号位置。

A.2kB.2k+1C. k/2下取整D.(k+1)/210.以下竞赛活动中历史最悠久的是（）。

A. NOIPB. NOIC. IOID. APIO二、不定项选择题（共10题，每题1.5分，共计15分。

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;}输入：114 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找最长的路径的程序。

NOIP2010初赛模拟试题（六）（普及 Pascal语言二小时完成）●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●●一．单项选择题（共20题,每题1.5分,共计30分。

每题有且仅有一个正确答案。

）1、.在所有由两个1和六个0组成的8位二进制整数（补码）中，最小的数是：（）A．-127B．-64 C．-128 D．-652、.在一棵二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序（）A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同3、下面有效的IP地址是：（）A．202.280.130.45 B．130.192.33.45C．192.256.130.45 D．280.192.33.4564、一台具有1024*768分辨率、可显示65 536种颜色的显示器，其显示适配器（显示卡）上显示存储器容量的配置为：（）A．512K B．1MB C．大于1.6MB，小于2MB D．2MB5、进行二分法查找，则线性表（）A．必须顺序方式存储B．必须以链接方式存储，且数据元素已按值排好序C．必须以链接方式存储D．必须以顺序方式存储，且数据元素已按值排好序6、机器语言是用（）编写的。

A．二进制码B．ASCII码C．十六进制码D．国标码7、一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若 A[k]是叶子结点,则k的最小值是：（）A．51 B．50 C．49 D．488、不同的计算机，其指令系统也不相同，这主要取决于（）A. 所用的操作系统B. 系统的总体结构C. 所用的CPUD. 所用的程序设计语言9、计算机主机是由CPU 与（）构成的。

A．控制器B。

输入、输出设备C．运算器D．内存储器10、计算机系统总线上传送的信号有（）。

A．地址信号与控制信号B．数据信号、控制信号与地址信号C．控制信号与数据信号D．数据信号与地址信号11、计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。

作者：钟野梓序今年Noip2010初赛刚结束，网上便铺天盖地地响起了“今年初赛好容易”“分数线一定很高，怎么办……”之类的声音。

确实，自2008年起，Noip初赛难度确有逐年下降的趋势，然而这并不是出题水平降低的缘故，相反，我认为这是中国计算机协会（下称CCF）对于N oip考核目的的审视和改变所导致的必然结果。

因此，我试图通过深入解析本届Noip初赛试囗题，来探寻这种变化下面深层的规律，从而令信息学竞赛选手能更好地备战往后数届的Noip初赛，让初赛不再成为一个问题。

由于条件所限，本文仅以Pascal语言的提高组试囗题作为对象进行分析，相对于普及组而言提高组试囗题一向具有较高的难度和较好的区分度，作为研究对象是个很好的选择；至于说语言的选择，仅是因为笔者个人选择原因。

一、概况本届题目在设置方面与往年相似，由选择题（普及组仅有单项选择题，提高组则有单项选择题与不定项选择题）、问题求解、阅读程序写结果及完善程序四大部分组成；但值得注意的是，今年提高组试囗题的分值设计与往年出现了较大的不同，除了选择题仍然是30分（15分单项+15分不定项），其余部分分值均发生了变化，其中问题求解由10分上升到15分，阅读程序由32分下降到28分，完善程序由28分下降到27分。

由于是第一年实行这种分值，目前暂时无法定言背后的含义，然而或许CCF在初赛更加重视选手的数学素质，而弱化了对于阅读程序能力的考察。

众所周知，阅读程序的能力并不能非常真实地反映选手的程序能力，并且纵观近几年的阅读程序题已没有了什么新意，这也可看做是一个“求新求变”的信号。

至于试囗题整体难度方面较上年有了明显下降，其中问题求解第一题可以看做是考察选手的语文水平，而阅读程序更是没有了以往的“死算”题（即给定若干常数，在程序中设置一系列运算过程，让选手进行阅读计算类型的题目），完善程序给定的源代码风格良好，第二题竟然还加上了注释，这不能不说就是一种降低难度的举动。

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找最长的路径的程序。

NOIP2010第十六届初赛试题及答案(普及组Pascal)NOIP2010第十六届初赛试题及答案(普及组Pascal) PDF格式第十六届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一. 单项选择题（共20题，每题1.5分，共计30分。

每题有且仅有一个正确答案。

）1.2E＋03表示（）。

A.2.03B.5C.8D.20002.一个字节（byte）由（）个二进制位组成。

A.8B.16C.32D.以上都有可能3.以下逻辑表达式的值恒为真的是（）。

A.P∨(﹁P∧Q) ∨(﹁P∧﹁Q)B.Q∨(﹁P∧Q) ∨(P∧﹁Q)C. P∨Q∨(P∧﹁Q) ∨(﹁P∧Q)D.P∨﹁Q∨(P∧﹁Q) ∨(﹁P∧﹁Q)4.Linux下可执行文件的默认扩展名为（）。

A.exeC.dllD.以是都不是5.如果树根算是第1层，那么一棵n层的二叉树最多有（）结点。

A.2n-1B.2nC.2n+1D.2n+16.提出“存储程序”的计算机工作原理的是（）。

A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.设X、Y、Z分别代表三进制下的一位数字，若等式XY＋ZX＝XYX在三进制下成立，那么同样在三进制下，等式XY×ZX＝（）也成立。

A.YXZB.ZXYC.XYZD.XZY9.前缀表达式“＋3×2＋5 12”的值是（）。

A.23B.25C.37D.6510.主存储器的存取速度比中央处理器（CPU）的工作速度慢得多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了（）。

A.寄存器B.高速缓存C.闪存D.外存11.一个字长为8位的整数的补码是11111001,则它的原码是（）。

CSP-S（提高组）模拟题1.以下关于CSP-J/S的描述错误的是()分值2分A.任何人都可以自愿报名参加CSP-J/SB.CSP-J/S是CCF独立主办的认证，和任何其他机构主办的等级考试无关C.CSP-J/S和NOIP有密切关系D.CSP-J/S认证成绩优异者，可参加NOI省级选拔，省级选拔成绩优异者可参加NOI C2.-128的补码表示为()分值2分A.00000000B.00000001C.10000000D.111111113.以下不属于TCP拥塞控制算法的是()分值2分A.慢启动B.拥塞避免C.快启动D.快速重传4.以下不是基于UDP协议的是()分值2分A.DNSB.RIPC.TELNETD.TFTP5.定义如下函数add_edge和全局变量：int to[MAX],nxt[MAX],h[MAX],top;void add_edge(int u,int v){to[++top]=v,nxt[top]=h[u],h[u]=top;}如下图节点编号从1开始，按边的编号顺序，以前向星的方式存储，请问nxt[h[3]]的值为()分值2分A.6B.3C.8D.76.如下图所示，从节点1走6步走到节点5的方案数有多少种()A.5B.8C.7D.67.同时查找2n个数中的最大值和最小值，最少比较次数为()。

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

分值2分A.n2B.nlog2nC.2nD.2n-19.G是一个非连通简单无向图，共有36条边，则该图至少有()个顶点分值2分A.10B.9C.8D.710.由四个不同的点构成的简单无向连通图的个数是()分值2分A.32B.35C.38D.3111.前缀表达式-+*4+2315的值为()分值2分A.16B.17C.19D.1512.2+3*(4-(5+6))/7的逆波兰表达式为()分值2分A.23456-+*7/+B.23456-+*/7+C.23456+-*7/+D.23456++*/7-13.若某算法的计算时间表示为递推关系：则该算法的复杂度为()分值2分A.O(n)B.O(nlog2n)C.O(nlog22n)D.O(nlong23n)14.若某算法的计算时间表示为递推关系：T(n)=3T(n/4)+nlong2n则该算法的复杂度为()分值2分A.O(n)B.O(nlog2n)C.O(nlog22n)D.O(nlong23n)15.现有变量a,b,c,d，取值范围均为[0,15]，假设每个值出现的概率相同，则表达式的值能被3整除的概率()(为计算机中的异或运算符，结果用分数形式表达)分值2分A．3/8B.1/2C.1/4D.1/8二、阅读程序写结果(共4题，每题10分，共计40分)1.#include<iostream>using namespace std;int a,b,c;int*cal(int*p,int&q,int r){q+=r;*p+=q;return p;}int main(){cin>>a>>b>>c;c=*cal(&a,b,c);cout<<a<<""<<b<<""<<c;}1.1cal函数中参数p使用指针传递，q和r则是值传递分值2.5分对错1.2cal函数返回一个指向int类型存储空间的地址分值2.5分对错1.3当输入123时，程序输出结果为()分值2.5分A.623B.653C.656D.1261.4当输入234511时，程序的输出结果为()分值2.5分A.795611B.795679C.445679D.7956442.#include<iostream>#include<cmath>#define MAX1000#define p sqrt(3)using namespace std;int n,dp[1000][3];int h0=1,h1=3;double ans1=(2+p)/(2*p),ans2=(-2+p)/(2*p);int main(){cin>>n;dp[1][0]=dp[1][1]=dp[1][2]=1;for(int i=2,tmp;i<=n;i++){dp[i][0]=dp[i-1][1]+dp[i-1][2];dp[i][1]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];dp[i][2]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];tmp=h1;h1=2*(h1+h0);h0=tmp;}for(int i=1;i<=n;i++){ans1=ans1*(1+p);ans2=ans2*(1-p);}cout<<h1<<endl;cout<<dp[n][0]+dp[n][1]+dp[n][2]<<endl;cout<<ans1+ans2<<endl;}2.1上述程序的输出中h1和dp[n][0]+dp[n][1]+dp[n][2]的值相等分值2.5分对错2.2上述程序的输出中dp[n][0]+dp[n][1]+dp[n][2]和ans1+ans2的值相等分值2.5分对错2.3当n等于5时，第一行输出(即h1)结果为()分值2.5分A.164B.60C.448D.128当n等于10时，第三行输出(即ans1+ans2)结果为()分值2.5分A.9136B.68192C.24960D.33443.#include<iostream>#include<cstring>#define LL long longusing namespace std;LL l,r;LL f[12][10][10][2][2][2],a[20];LL Dfs(LL now,LL p,LL pp,LL_4,LL_8,LL top,LL hw){if(_4&&_8)return0;if(!now)return hw;if(!top&&f[now][p][pp][_4][_8][hw]!=-1)return f[now][p][pp][_4][_8][hw];LL Up=top?a[now]:9;LL ret(0);for(LL i=0;i<=Up;++i)ret+=Dfs(now-1,i,p,_4|(i==4),_8|(i==8),top&&(i==Up),hw|(i==pp&&i==p));if(!top)f[now][p][pp][_4][_8][hw]=ret;return ret;}inline LL Solve(LL x){LL tot(0);while(x){a[++tot]=x%10;x/=10;}if(tot!=11)return0;LL ret(0);for(LL i=1;i<=a[tot];++i)ret+=Dfs(tot-1,i,0,(i==4),(i==8),i==a[tot],0);return ret;}int main(){cin>>l>>r;memset(f,-1,sizeof(f));cout<<Solve(r)-Solve(l-1);return0;}3.1同时包含4和8的数字都不会被统计分值2.5分对错3.2相邻数位中，超过3个数位相同的数字都不会被统计分值2.5分对错3.3下列哪个是合法(会被统计)的数字()分值2.5分A.2323234823B.1015400080C.23333333333D.100100120223.4当输入1212128400012121285550时，程序输出结果为()分值2.5分A.5B.457C.455D.64.4.1上述程序实现大整数加法分值2.5分对错4.2上述程序的算法复杂度大于（其中n为max(s1.length(),s2.length())）分值2.5分对错4.3当输入111011时程序输出为()分值2.5分A.10B.4C.21D.24.4当输入10101101010时程序输出为()分值2.5分A.441B.882C.1764D.220五、完善程序(每题15分，共计30分)1.（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的，1->2->3->4->5，反转后成为5->4->3->2->1。