历年noip初赛普及组试题.pdf

历年 noip 普及组初赛试题汇编 芜湖县实验学校 NOIP 初赛复习资料 word 格式-可编辑-感谢下载支持 第十五届全国青少年信息学奥林匹克联赛初赛试题(2009)（普及组 C+语言 二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一 单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确答案。）1、关于图灵机下面的说法哪个是正确的：A)图灵机是世界上最早的电子计算机。B)由于大量使用磁带操作，图灵机运行速度很慢。C)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。D)图灵机只是一个理论上的计算模型。2、关于计算机内存下面的说法哪个是正确的：A)随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。B)1MB 内存通常是指 1024*1024 字节大小的内存。C)计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。D)一般内存中的数据即使在断电的情况下也能保留 2 个小时以上。3、关于 BIOS 下面说法哪个是正确的：A)BIOS 是计算机基本输入输出系统软件的简称。B)BIOS 里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。C)BIOS 一般由操作系统厂商来开发完成。D)BIOS 能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。4、关于 CPU 下面哪个说法是正确的：A)CPU 全称为中央处理器（或中央处理单元）。B)CPU 可以直接运行汇编语言。C)同样主频下，32 位的 CPU 比 16 位的 CPU 运行速度快一倍。D)CPU 最早是由 Intel 公司发明的。5、关于 ASCII，下面哪个说法是正确的：A)ASCII 码就是键盘上所有键的唯一编码。B)一个 ASCII 码使用一个字节的内存空间就能够存放。C)最新扩展的 ASCII 编码方案包含了汉字和其他欧洲语言的编码。D)ASCII 码是英国人主持制定并推广使用的。6、下列软件中不是计算机操作系统的是：A)Windows B)Linux C)OS/2 D)WPS 7、关于互联网，下面的说法哪一个是正确的：A)新一代互联网使用的 IPv6 标准是 IPv5 标准的升级与补充。B)互联网的入网主机如果有了域名就不再需要 IP 地址。C)互联网的基础协议为 TCP/IP 协议。D)互联网上所有可下载的软件及数据资源都是可以合法免费使用的。word 格式-可编辑-感谢下载支持 8、关于 HTML 下面哪种说法是正确的：A）HTML 实现了文本、图形、声音乃至视频信息的统一编码。B）HTML 全称为超文本标记语言。C）网上广泛使用的 Flash 动画都是由 HTML 编写的。D）HTML 也是一种高级程序设计语言。9、关于程序设计语言，下面哪个说法是正确的：A)加了注释的程序一般会比同样的没有加注释的程序运行速度慢。B)高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。C)高级语言相对于低级语言更容易实现跨平台的移植。D)以上说法都不对。10、已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：A)71 B)72 C)73 D)以上都不是 11、十进制小数125.125对应的8进制数是 A)100.1 B)175.175 C)175.1 D)100.175 12、有六个元素 FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？A)EDCFAB B)DECABF C)CDFEBA D)BCDAEF 13、表达式 a*(b+c)-d 的后缀表达式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd 14、一个包含 n 个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：A)2n+1 B)2n-1 C)n-1 D)n+1 15、快速排序最坏情况下的算法时间复杂度为：A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)16.有一个由 4000 个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素：A)11 次 B)12 次 C)13 次 D)14 次 17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：A)冒泡排序 B)插入排序 C)归并排序 D)快速排序 18、已知 n 个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？A)n B)n+1 C)n-1 D)n*(n-1)19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：20、在参加 NOI 系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：A)携带书写工具，手表和不具有通讯功能的电子词典进入赛场。B)在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。word 格式-可编辑-感谢下载支持 C)通过互联网搜索取得解题思路。D)在提交的程序中启动多个进程以提高程序的执行效率。二问题求解（共 2 题，每空 5 分，共计 10 分）1小陈现有 2 个任务 A，B 要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陈从 B 任务的 b1 步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务 A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有 种。2有如下的一段程序：1.a=1;2.b=a;3.d=-a;4.e=a+d;5.c=2*d;6.f=b+e-d;7.g=a*f+c;现在要把这段程序分配到若干台（数量充足）用电缆连接的 PC 上做并行执行。每台 PC执行其中的某几个语句，并可随时通过电缆与其他 PC 通讯，交换一些中间结果。假设每台 PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 单位时间内执行完毕。注意：任意中间结果只有在某台 PC 上已经得到，才可以被其他PC 引用。例如若语句 4 和 6 被分别分配到两台 PC 上执行，则因为语句 6 需要引用语句 4的计算结果，语句 6 必须在语句 4 之后执行。三阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1#include using namespace std;int a,b;int work(int a,int b)if(a%b)return work(b,a%b);return b;word 格式-可编辑-感谢下载支持 int main()cin a b;cout work(a,b)endl;return 0;输入：20 12 输出：_ 2#include using namespace std;int main()int a3,b3;int i,j,tmp;for(i=0;i bi;for(i=0;i3;i+)ai=0;for(j=0;j=i;j+)ai+=bj;bai%3+=aj;tmp=1;for(i=0;i3;i+)ai%=10;bi%=10;tmp*=ai+bi;word 格式-可编辑-感谢下载支持 cout tmp endl;return 0;输入：2 3 5 输出：_ 3#include using namespace std;const int c=2009;int main()int n,p,s,i,j,t;cin n p;s=0;t=1;for(i=1;i=n;i+)t=t*p%c;for(j=1;j=i;j+)s=(s+t)%c;cout s endl;return 0;输入：11 2 输出：4#include using namespace std;const int maxn=50;word 格式-可编辑-感谢下载支持 void getnext(char str)int l=strlen(str),i,j,k,temp;k=l-2;while(k=0&strkstrk+1)k-;i=k+1;while(istrk)i+;temp=strk;strk=stri-1;stri-1=temp;for(i=l-1;ik;i-)for(j=k+1;jstrj+1)temp=strj;strj=strj+1;strj+1=temp;return;int main()char amaxn;int n;cin a n;while(n0)getnext(a);n-;cout a endl;return 0;输入：NOIP 3 输出：四完善程序(前 8 空，每空 3 分，后 2 空，每空 2 分，共 28 分)1（最大连续子段和）给出一个数列（元素个数不多于 100），数列元素均为负整数、word 格式-可编辑-感谢下载支持 正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为 4，-5，3，2，4 时，输出 9 和 3；数列为 1 2 3-5 0 7 8 时，输出 16 和 7。#include using namespace std;int a101;int n,i,ans,len,tmp,beg;int main()cin n;for(i=1;i ai;tmp=0;ans=0;len=0;beg=;for(i=1;ians)ans=tmp+ai;len=i-beg;else if(&i-beglen)len=i-beg;if(tmp+ai )beg=;tmp=0;else ;cout ans len endl;return 0;2.(国王放置)在 n*m 的棋盘上放置 k 个国王，要求 k 个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读 入 三 个 数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为 0n-1，列标号为 0m-1。word 格式-可编辑-感谢下载支持#include using namespace std;int n,m,k,ans;int hash55;void work(int x,int y,int tot)int i,j;if(tot=k)ans+;return;do while(hashxy)y+;if(y=m)x+;y=;if(x=n)return;for(i=x-1;i=0&in)for(j=y-1;j=0&jm);for(i=x-1;i=0&in)for(j=y-1;j=0&j n m k;ans=0;memset(hash,0,sizeof(hash);cout ans endl;return 0;第十四届全国青少年信息学奥林匹克联赛初赛试题 2008 （普及组 C+语言 二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（共 20 题，每题 1.5 分，共计 30 分。每题有且仅有一个正确答案.）。1微型计算机中，控制器的基本功能是（）。A.控制机器各个部件协调工作 B.实现算术运算和逻辑运算 C.获取外部信息 D.存放程序和数据 2.设A=true，B=false，C=true，D=false，以下逻辑运算表达式值为真的是（）。A.(AB)(CDA)B.(AB)C)D C.(BCD)DA D.A(DC)B 3.在下列关于图灵奖的说法中，不正确的是（）。A.图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B.图灵奖有“计算机界诺贝尔奖”之称 C.迄今为止，还没有华裔计算机科学家获此殊荣 D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰图灵 4计算机在工作过程中，若突然停电，（）中的信息不会丢失。A.ROM 和 RAM B.CPU C.ROM D.RAM 5完全二叉树共有 2*N-1 个结点，则它的叶节点数是（）。A.N-1 B.N C.2*N D.2N-1 6.在以下各项中，（）不是操作系统软件。A.Solaris B.Linux C.Windows Vista D.Sybase 7设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈 S，出栈的序列为 b，d，f，e，c，a，则栈 S 的容量至少应该是（）。word 格式-可编辑-感谢下载支持 A.6 B.5 C.4 D.3 8.与十进制数 28.5625 相等的四进制数是（）。A.123.21 B.131.22 C.130.22 D.130.21 9.设字符串S=”Olympic”，S的非空子串的数目是（）。A.28 B.29 C.16 D.17 10Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（）是典型的 Web2.0 应用。A.Sina B.Flickr C.Yahoo D.Google 11 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。A.队列 B.多维数组 C.线性表 D.栈 12.(2008)10+(5B)16的结果是（）。13.二叉树 T，已知其先根遍历是 1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是 2 4 1 5 7 3 6，则该二叉树的后根遍历是（）。A.4 2 5 7 6 3 1 B.4 2 7 5 6 3 1 C.7 4 2 5 6 3 1 D.4 2 7 6 5 3 1 14将数组8,23,4,16,77,-5,53,100中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。A.4 B.5 C.6 D.7 15 对有序数组5,13,19,21,37,56,64,75,88，92，100进行二分查找，成功查找元素 19 的查找长度（比较次数）是（）。A.1 B.2 C.3 D.4 16.面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，不正确的是（）。A.面向对象程序设计通常采用自顶向下设计方法进行设计。B.面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。C.支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有 C+、JAVA、C#等。D.面向对象的程序设计的雏形来自于 Simula 语言，后来在 SmallTalk 语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk 语言仍然被视为面向对象语言的基础。17.在 32*32 点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（）。A.512 B.256 C.384 D.128 word 格式-可编辑-感谢下载支持 18.设 T 是一棵有 n 个顶点的树，下列说法不正确的是（）。A.T 有 n 条边 B.T 是连通的 C.T 是无环的 D.T 有 n-1 条边 19.下列不属于NOIP竞赛推荐使用的语言环境的是（）。A.Dev-C+B.Visual C+C.free pascal D.Lazarus 20在 C+程序中，表达式 200|10 的值是（）A.20 B.1 C.220 D.202 二问题求解（共 2 题，每题 5 分，共计 10 分）1.书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的，C 和 D 是黑皮的。把这 4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_种。满足 A 必须比 C靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有_种摆法。2有 6 个城市，任何两个城市之间都有一条道路连接，6 个城市两两之间的距离如下表所示，则城市 1 到城市 6 的最短距离为_。城市 1 城市 2 城市 3 城市 4 城市 5 城市 6 城市 1 0 2 3 1 12 15 城市 2 2 0 2 5 3 12 城市 3 3 2 0 3 6 5 城市 4 1 5 3 0 7 9 城市 5 12 3 6 7 0 2 城市 6 15 12 5 9 2 0 三阅读程序写结果（共 4 题，每题 8 分，共计 32 分）1.#include using namespace std;int main()int i,a,b,c,d,f4;for(i=0;i fi;a=f0+f1+f2+f3;a=a/f0;b=f0+f2+f3;b=b/a;c=(b*f1+a)/f2;word 格式-可编辑-感谢下载支持 d=f(b/c)%4;if(f(a+b+c+d)%4 f2)cout a+b endl;else cout c+d endl;return 0;输入：9 19 29 39 输出：_ 2#include using namespace std;void foo(int a,int b,int c)if(a b)foo(c,a,b);else couta,b,c a b c;foo(a,b,c);return 0;输入:3 1 2 输出:_ 3#include using namespace std;void func(int ary,int n)int i=0,j,x;word 格式-可编辑-感谢下载支持 j=n-1;while(ij)while(i0)i+;while(ij&aryj0)j-;if(ij)x=aryi;aryi+=aryj;aryj-=x;int main()int a20,i,m;m=10;for(i=0;iai;func(a,m);for(i=0;im;i+)coutai;cout endl;return 0;输入：5 4-6-11 6-59 22-6 1 10 输出：_ 4.#include#include using namespace std;word 格式-可编辑-感谢下载支持#define MAX 100 void solve(char first,int spos_f,int epos_f,char mid,int spos_m,int epos_m)int i,root_m;if(spos_f epos_f)return;for(i=spos_m;i=epos_m;i+)if(firstspos_f=midi)root_m=i;break;solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1);solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m);cout len;cin first mid;solve(first,0,len-1,mid,0,len-1);cout endl;return 0;输入：7 ABDCEGF BDAGECF 输出：_ word 格式-可编辑-感谢下载支持 四完善程序(前 4 空，每空 2.5 分，后 6 空，每空 3 分，共 28 分)1（字符串替换）给定一个字符串 S（S 仅包含大小写字母），下面的程序将 S 中的每个字母用规定的字母替换，并输出 S 经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串 S，第二个字符串 S由 26 个字母组成，它是 a-z 的任一排列，大小写不定，S规定了每个字母对应的替换字母：S中的第一个字母是字母 A 和a 的替换字母，即 S 中的 A 用该字母的大写替换，S 中的 a 用该字母的小写替换；S中的第二个字母是字母 B 和 b 的替换字母，即 S 中的 B 用该字母的大写替换，S 中的 b 用该字母的小写替换；以此类推。#include#include char change26,str5000;using namespace std;void CheckChangeRule()int i;for(i=0;i 26;i+)if()changei-=A-a;void ChangeString()int i;for(i=0;i str;cin change;CheckChangeRule();cout str endl;return 0;2.(找第 k 大的数)给定一个长度为 1,000,000 的无序正整数序列,以及另一个数 n(1=n=1000000),然后以类似快速排序的方法找到序列中第 n 大的数（关于第 n大的数：例如序列1，2，3，4，5，6中第 3 大的数是 4）。#include using namespace std;int a1000001,n,ans=-1;void swap(int&a,int&b)int c;c=a;a=b;b=c;int FindKth(int left,int right,int n)int tmp,value,i,j;if(left=right)return left;tmp=rand()%(right-left)+left;swap(atmp,aleft);value=i=left;j=right;while(i j)word 格式-可编辑-感谢下载支持 while(i j&)j-;if(i j)ai=aj;i+;else break;while(i j&)i+;if(i j)aj=ai;j-;else break;if(i n)return return i;int main()int i;int m=1000000;for(i=1;i ai;cin n;ans=FindKth(1,m,n);cout aans;return 0;第十三届全国青少年信息学奥林匹克联赛初赛试题2007（普及组 C+语言二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（共 20 题，每题1.5 分，共计30 分。每题有且仅有一个正确答案.）。1.在以下各项中，（）不是CPU 的组成部分。A.控制器 B.运算器 C.寄存器 D.主板 2在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。A.二叉树 B.多叉树 C.哈希表 D.二维表 3在下列各项中，只有（）不是计算机存储容量的常用单位。A.Byte B.KB C.UB D.TB 4ASCII 码的含义是（）。word 格式-可编辑-感谢下载支持 A.二十进制转换码 B.美国信息交换标准代码 C.数字的二进制编码 D.计算机可处理字符的唯一编码 5.一个完整的计算机系统应包括（）。A.系统硬件和系统软件 B.硬件系统和软件系统 C.主机和外部设备 D.主机、键盘、显示器和辅助存储器 6.IT 的含义是（）。A.通信技术 B.信息技术 C.网络技术 D.信息学 7LAN 的含义是（）。A.因特网 B.局域网 C.广域网 D.城域网 8.冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致，例如，上面4 个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（）。A.应该在数据库中消除一切冗余数据 B.用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据 C.为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检验 D.做相容性检验会降低效率，可以不理睬数据库中的冗余数据 9.在下列各软件中，不属于NOIP 竞赛（复赛）推荐使用的语言环境有（）。A.gcc B.g+C.Turbo C D.free pascal 10.以下断电之后仍能保存数据的有（）。A.硬盘 B.高速缓存 C.显存 D.RAM 11.在下列关于计算机语言的说法中，正确的有（）。A.高级语言比汇编语言更高级，是因为它的程序的运行效率更高 B.随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台 C.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 D.C是一种面向对象的高级计算机语言 12.近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（）。A.在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间 B.和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C.对于较复杂的问题，用递归方式编程一般比非递归方式更难一些 D.对于已经定义好的标准数学函数sin(x)，应用程序中的语句“y=sin(sin(x);”就是一种递归调用 13.一个无法靠自身的控制终止的循环称为“死循环”，例如，在C+语言程序中，语句“while(1)printf(“*”);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。word 格式-可编辑-感谢下载支持 A.不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检验 B有些编译系统可以检测出死循环 C.死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D.死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的 14在C+程序中，表达式23|25 的值是（）A.23 B.1 C.32 D.18 15在C+程序中，判断a 等于0 或b 等于0 或c 等于0 的正确的条件表达式是（）A.!(a!=0)|(b!=0)|(c!=0)B.!(a!=0)&(b!=0)&(c!=0)C.!(a=0&b=0)|(c!=0)D.(a=0)&(b=0)&(c=0)16 地面上有标号为A、B、C 的3 根细柱，在A 柱上放有10 个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3，将A 柱上的部分盘子经过B 柱移入C 柱，也可以在B 柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C 柱上，从下到上的盘子的编号为（）。A.2 4 3 6 5 7 B.2 4 1 2 5 7 C.2 4 3 1 7 6 D.2 4 3 6 7 5 17.与十进制数1770 对应的八进制数是（）。A.3350 B.3351 C.3352 D.3540 18.设A=B=true，C=D=false，以下逻辑运算表达式值为假的有（）。A.(AB)(CDA)B.(AB)C)D)C.A(BCD)D D.(A(DC)B 19.(2070)16+(34)8 的结果是（）。A.(8332)10 B.(208A)16 2 D.(20212)8 20.已知7 个结点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为结点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（）A.4 6 5 2 7 3 1 B.4 6 5 2 1 3 7 C.4 2 3 1 5 4 7 D.4 6 5 3 1 7 2 二问题求解（共 2 题，每题5 分，共计10 分）1（子集划分）将n 个数1，2，n划分成r 个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为(1),(234),(2),(134),(3),(124),(4),(123),(12),(34),(13),(24),(14),(23)。当n=6,r=3 时，S(6,3)=_。（提示：先固定一个数，对于其余的5 个数考虑S(5,3)与 S(5,2)，再分这两种情况对原固定的数进行分析）。word 格式-可编辑-感谢下载支持 2（最短路线）某城市的街道是一个很规整的矩形网格（见下图），有7 条南北向的纵街，5 条东西向的横街。现要从西南角的A 走到东北角的B，最短的走法共有多少种？_.B A 三阅读程序写结果（共4 题，每题8 分，共计32 分）1.#include void main()int i,p5,a,b,c,x,y=20;for(i=0;ipi;a=(p0+p1)+(p2+p3+p4)/7;b=p0+p1/(p2+p3)/p4);c=p0*p1/p2;x=a+b-p(p3+3)%4;if(x10)y+=(b*100-a)/(pp4%3*5);else y+=20+(b*100-c)/(pp4%3*5);coutx,yendl;/注：本例中，给定的输入数据可以避免分母为0 或数组元素下标越界。输入：6 6 5 5 3 输出：_ 2#include void fun(int*a,int*b)int*k;k=a;a=b;b=k;void main()int a=3,b=6,*x=&a,*y=&b;fun(x,y);couta,bendl;输出:_ 3#include#include#include math.h word 格式-可编辑-感谢下载支持 void main()int a151=0;int i,j,t,t2,n=50;for(i=2;i=sqrt(n);i+)if(a1i=0)t2=n/i;for(j=2;j=t2;j+)a1i*j=1;t=0;for(i=2;i=n;i+)if(a1i=0)coutsetw(4)i;t+;if(t%10=0)coutendl;coutendl;输出：_ _ 4.#include#include ctype.h void expand(char s1,char s2)int i,j,a,b,c;j=0;for(i=0;(c=s1i)!=0;i+)if(c=-)a=s1i-1;b=s1i+1;if(isalpha(a)&isalpha(b)|isdigit(a)&isdigit(b)/函数isalpha(a)用于判断字符a 是否为字母，isdigit(b)用于判断字符b 是否为数/字，如果是，返回1，否则返回0 j-;do s2j+=a+;while(tolower(a)s1;expand(s1,s2);word 格式-可编辑-感谢下载支持 couts2endl;输入：wer2345d-h454-82qqq 输出：_ 四完善程序(前4 空，每空2.5 分，后6 空，每空3 分，共28 分)1（求字符串的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1 终止程序。请将程序补充完整。#include#include int maxline=200,kz;int reverse(char s)int i,j,t;for(i=0,j=strlen(s)-1;ij;，)t=si;si=sj;sj=t;return 0;void main()char line100;coutcontinue?-1 for end.kz;while()cinline;coutlineendl;coutcontinue?-1 for end.kz;2.（棋盘覆盖问题）在一个2k 2k 个方格组成的棋盘中恰有一个方格与其他方格不同（图中标记为-1 的方格），称之为特殊方格。现用L 型（占3 个小格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是(4k 1)/3。在下表给出的一个覆盖方案中，k=2，相同的3个数字构成一个纸片。下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。2 2 3 3 2-1 1 3 4 1 1 5 4 4 5 5#include#include word 格式-可编辑-感谢下载支持 int board6565,tile;/tile 为纸片编号 void chessboard(int tr,int tc,int dr,int dc,int size)/dr,dc 依次为特殊方格的行、列号 int t,s;if(size=1);t=tile+;s=size/2;if()chessboard(tr,tc,dr,dc,s);else boardtr+s-1tc+s-1=t;if(dr=tc+s)chessboard(tr,tc+s,dr,dc,s);else boardtr+s-1tc+s=t;if(dr=tr+s&dc=tr+s&dc=tc+s)chessboard(tr+s,tc+s,dr,dc,s);else boardtr+stc+s=t;void prt1(int b65,int n)int i,j;for(i=1;i=n;i+)for(j=1;j=n;j+)coutsetw(3)bij;coutendl;word 格式-可编辑-感谢下载支持 void main()int size,dr,dc;coutinput size(4/8/16/64):size;coutinput the position of special block(x,y):drdc;boarddrdc=-1;tile+;chessboard(1,1,dr,dc,size);prt1(board,size);第十二届全国青少年信息学奥林匹克联赛初赛试题 2006（普及组 C+语言二小时完成）全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案.）1.在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是（）。A.沃尔夫奖 B.诺贝尔奖 C.菲尔兹奖 D.图灵奖 2.在下列各软件中，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A.gcc/g+B.Turbo Pascal C.RHIDE D.free pascal 3.以下断电之后仍能保存数据的有（）。A.寄存器 B.ROM C.RAM D.高速缓存 4Linux是一种()。A.绘图软件 B.程序设计语言 C.操作系统 D.网络浏览器 5.CPU是()的简称。A.硬盘 B.中央处理器 C.高级程序语言 D.核心寄存器 6.在计算机中，防火墙的作用是（）。A.防止火灾蔓延 B.防止网络攻击 C.防止计算机死机 D.防止使用者误删除数据 7.在下列关于计算机语言的说法中，不正确的是（）。A.Pascal和C都是编译执行的高级语言 B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C.C+是历史上的第一个支持面向对象的计算机语言 D.与汇编语言相比，高级语言程序更容易阅读 8.在下列关于计算机算法的说法中，不正确的是（）。A.一个正确的算法至少要有一个输入 B.算法的改进，在很大程度上推动了计算机科学与技术的进步 word 格式-可编辑-感谢下载支持 C.判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 9.在下列各种排序算法中，不是以“比较”作为主要操作的算法是（）。A.选择排序 B.冒泡排序