第十七届NOIP2011 提高组初赛试题及答案解析

第十七届全国青少年信息学奥林匹克联赛初赛试题（提组 Pascal 语言两小时完成）

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

一、单项选择题（共10题，每题1.5分，共15分，每题有且仅有一个正确选项。）

1. 在二进制下，1011010+（）=1100111。

A.1011

B.1101

C.1010

D.1111

解析：简单的二进制运算，炮灰都会。直接用减法：1100111-1011010=00001101；也可用补码计算：

1100111-1011010=（1100111）补+（-1011010）补=（01100111）+（11011010）补=（01100111）+（10100101+00000001）=（01100111）+10100110）=100001101=1101（超过8位者溢出）。答案：B

2. 字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66 B.5A C.50 D.视具体的计算机而定

解析：每年必考进制转换题。若记得ASCII码的可以直接算出Z的码然后转回16进制，A的ASCII码是65，则Z的ASCII码为65+25=90，（90）10=（5A）16。若不记得的就把十六进制的41转回十进制，4*16+1=65，然后+25得90，再转成16进制得5A。

答案：B

A．ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF

解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。然后就ABDEFC出来了。

答案：A

4. 寄存器是（）的重要组成部分。

A. 硬盘

B. 高速缓存

C. 内存

D. 中央处理器（CPU）

解析：每年必考硬件知识题。计算机中能存储数据的部件有：寄存器，一级缓存，二级缓存，只读存储器ROM，随机存储器RAM和外存。其中寄存器和一级缓存在CPU内，一级缓存又名片上的缓存。二级缓存，只读存储器ROM和随机存储器RAM都在主板上，二级缓存又名板上的缓存，只读存储器ROM和随机存储器RAM共同构成内存。外存指硬盘、光盘和可移动磁盘等。CPU包括运算逻辑部件ALU、寄存器部件和控制部件等。

答案：D

5. 广度优先搜索时，需要用到的数据结构是（）。

A. 链表

B. 队列

C. 栈

D. 散列表

解析：数据结构题。广搜需要存每一层的一大堆东西，继续向下一层搜时需要用到，所以要用存取方便的队列。链表取数不便，栈是深搜用的，散列表就是hash表，和宽搜没啥必然联系。

答案：B

6. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）

A. 程序运行时理论上所占的内存空间

B. 程序运行时理论上所占的数组空间

C. 程序运行时理论上所占的硬盘空间

D. 程序源文件理论上所占的硬盘空间

解析：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。常识题。BCD均明显错。

答案：A

7. 应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。

A. O（n^2）

B. O（n log n）

C. O（n）

D. O（1）

解析：快排的时间复杂度是O（nlogn），利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。

答案：C

8. 为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。

A. 微软

B. 美国计算机协会（ACM）

C. 联合国教科文组织

D. 万维网联盟（W3C）

解析：微软的业绩主要是开发操作系统和软件，但是这种标准一般不是微软定制的；联合国教科文组织总部设在法国巴黎。其宗旨是促进教育、科学及文化方面的国际合作，以利于各国人民之间的相互了解，维护世界和平。美国计算机协会（ACM）犹如中国计算机学会，没有这样大的权限。WWW是环球信息网（World Wide Web ）的缩写，中文名字为“万维网”,万维网联盟（World Wide Web Consortium，W3C），又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。建立者是万维网的发明者蒂姆·伯纳斯-李。W3C为解决Web 应用中不同平台、技术和开发者带来的不兼容问题，保障Web 信息的顺利和完整流通，万维网联盟制定了一系列标准并督促Web 应用开发者和内容提供者遵循这些标准。所以就是D了。

答案：D

9. 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。

A. 快速排序

B. 插入排序

C. 冒泡排序

D. 归并排序

解析：此题考查学员对各种排序思想的掌握。

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

插入排序的基本思想：每次将一个待排序的记录按其关键字的大小插入到前面已经排好序的子文件的适当位置，直到全部的记录插入完成为止。

冒泡排序的基本思想是：将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。

两路归并算法基本思路

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。

重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。

答案：B

10. 1956年（）授予肖克利（William Shockley）巴丁（John Bardeen）和布拉顿（Walter

Brattain）,以表彰他们对半导体的研究和晶体管效应的发现。

A. 诺贝尔物理学奖

B. 约翰·冯·诺依曼奖

C. 图灵奖

D. 高德纳奖（Donald

E.Knuth Prize）

解析：此题考查学生对IT方面的新闻和名人名事的相关熟知度。

诺贝尔物理学奖是根据诺贝尔的遗嘱而设立的，是诺贝尔奖之一。该奖项旨在奖励那些对人类物理学领域里作出突出贡献的科学家。由瑞典皇家科学院颁发奖金，每年的奖项候选人由瑞典皇家自然科学院的瑞典或外国院士、诺贝尔物理和化学委员会的委员、曾被授与诺贝尔物理或化学奖金的科学家、在乌普萨拉、隆德、奥斯陆、哥本哈根、赫尔辛基大学、卡罗琳医学院和皇家技术学院永久或临时任职的物理和化学教授等科学家推荐。

约翰·冯·诺依曼奖由IEEE成立于于1990年，目的是表杨在计算机科学和技术上具有杰出成就的科学家。该奖牌是以对计算机科学具有重大贡献的现代电脑创始人之一约翰·冯·诺伊曼命名。2011年获奖者: 东尼·霍尔

图灵奖（A.M. Turing Award，又译“杜林奖”），由美国计算机协会（ACM）于1966年设立，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·麦席森·图灵。由于图灵奖对获奖条件要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。2011年获奖者：Judea Pearl犹大·伯尔

高德纳奖（Donald E. Knuth Prize），授予为计算机科学基础做出杰出贡献的人，以计算机科学家高德纳（Donald E. Knuth）命名。

高德纳奖始于1996年，每1.5年颁发一次，包括5000美元奖金。现在奖项由 ACM计算机理论研讨会和IEEE计算机科学基础研讨会交替颁发。

答案：A

二、不定项选择题（共10题，每题1.5分，共15分。每题有一个或多个正确选项。多选或

少选均不得分。）

1. 如果根节点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（）。

A. 10

B. 11

C. 12

D. 2011

解析：此题考查二叉树的性质方面的有关知识。

深度为n的叶子结点最多的二叉树是满二叉树，所能有的叶子结点数为2^（n-1），2^10=1024，2^11=2048，深度为11的二叉怎么搞都搞不出2011个结点，所以10和11不选。深度为n的一根树也可以有n个叶子结点。

答案：CD

2. 在布尔逻辑中，逻辑“或”的性质有（）。

A. 交换律：PVq=qVp

B. 结合律：P V（Q V R）=（P V Q）V R

C. 幂等律：P V P = P

D. 有界率：P V 1 = 1 （1表示逻辑真）

解析：基础题。考查逻辑运算方面的知识。“或”运算是双目运算，二者当中只要有一个为真，“或”的结果就为真。

答案：ABCD

3. 一个正整数在十六进制下有100位，则它在二进制下可能有（）位。

A. 399

B. 400

C. 401

D. 404

解析：此题考查二进制与十六进制相互转换的方法。一个十六进制数字可用4个二进制数字表示，方法同十进制数转换为二进制数的方法，如果不够四位，则在左面用数字0补够四位，所以100位的十六进制可以用400位二进制表示，当然最高位（最左面）那几位可能是0，最多是前三位为0，所以也可能是399、398、397位二进制表示。

答案：AB

4. 汇编语言（）。

A. 是一种与硬件无关的程序设计语言

B. 在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试

C. 可以直接访问寄存器、内存单元、I/O端口

D. 随着高级语言的诞生，如今已完全被淘汰，不再使用

解析：汇编语言是一种功能很强的程序设计语言，汇编语言也是利用计算机所有硬件特性并能直接控制硬件的语言。汇编语言，作为一门语言，对应于高级语言的编译器，需要一个“汇编器”来把汇编语言原文件汇编成机器可执行的代码。汇编语言像机器指令一样，是硬件操作的控制信息，因而仍然是面向机器的语言，使用起来还是比较繁琐费时，通用性也差。但是，汇编语言用来编制系统软件和过程控制软件，其目标程序占用内存空间少，运行速度快，有着高级语言不可替代的用途。

优点

1、面向机器的低级语言，通常是为特定的计算机或系列计算机二进制码专门设计的。

2、保持了机器语言的优点，具有直接和简捷的特点。

3、可有效地访问、控制计算机的各种硬件设备，如磁盘、存储器、CPU、I/O端口等。

4、目标代码简短，占用内存少，执行速度快，是高效的程序设计语言。

5、经常与高级语言配合使用，应用十分广泛。

缺点

同时还应该认识到，汇编语言是一种层次非常低的语言，它仅仅高于直接手工编写二进制的机器指令码，因此不可避免地存在一些缺点：

（1）编写的代码非常难懂，不好维护；

（2）很容易产生bug，难于调试；

（3）只能针对特定的体系结构和处理器进行优化；

（4）开发效率很低，时间长且单调。

答案：BC

5. 现有一段文言文，要通过二进制哈弗曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（）。

A. 1

B. 2

C. 3

D. 4

解析：初赛常考的哈夫曼编码。

给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

哈夫曼树的构造方法：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

哈夫曼编码是一种很犀利的编码，把使用频率高的编为短一点的编码，使用频率低的长一点。一般方法是建一棵哈弗曼树，然后左子树为0右子树为1，从上到下的一条路为这个叶子结点的编码。把所有东西放到一个集合F中，在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。这样，

从这题来看，先弄300和400的两个，变成一个根为700的树。然后现在就有600,700,700，选600和其中一个700再做一颗树。这样就会有两种情况，“也”可能是2位也可能是3位，所以选BC。

答案：BC

6. 生物特征识别是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（）。

A. 指静脉验证

B. 步态验证

C. ATM机密码验证

D. 声音验证

解析：通过此题，我们不难想象，NOIP中也考查学生对计算机前沿学科方面的了解。

生物特征识别技术，目前比较成熟并大规模使用的方式主要为，指纹、虹膜、脸、耳、掌纹、手章静脉等，此外近年，语音识别、脑电波识别、唾液提取DNA等研究也有突破，有望进入商用阶段。

答案：ABD

7. 对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（）会使逆序对的个数减少3.

A. 7

B. 5

C. 3

D. 6

解析：对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。现在知道逆序对是啥了，就容易做了。

此序列的逆序列有14对（7，5），（7，1），（7，3），（7，6），（7，4），（5，1），（5，3），（5，4），（9，3），（9，6），（9，8），（9，4），（6，4），（8，4）。如果要使其逆序列的个数减少3

对，则将其中出现了3次的数字删除即可。7出现了5次，5出现了4次，1出现了2次，9出现了4次，3出现了3次，6出现了3次，8出现了2次，4出现了5次。故数字3和6是满足题意思的。 答案：CD

8. 计算机中的数值信息分为整数和实数（浮点数）。实属之所以能表示很大或者很小的数是由于使用了（ ）。 A. 阶码 B. 补码 C. 反码

D. 较长的位数

解析：此题旨在考查科学记数法方面的知识。

答案：A

9. 对右图使用Dijkstra 算法计算S 点到其余各点的最短路径长度时，到B 点的距离d 【B 】初始时赋值为8，在算法的执行过程中还会出现的值有（ ）。 A. 3 B. 7 C. 6

D. 5

解析：此题考查图论当中求单源最短路径的算法Dijkstra 算法的掌握程序。

Dijkstra的思想是建个一维数组记录起点到其他各点的距离（没路为无限大），然后找一个这个距起点最近的点作为中间结点，更新起点到各个点的距离，然后把中心结点加个用过的标记，继续找下一个距离起点最近的点为中心结点，直到所有的点都当过中心结点就结束。这题中，第一个找到的中间结点是A，这时把SB更新为7，然后找到的中心结点为D，这时把SB更新为6，把SC更新为4；下一个找到的中心结点为C，这时把SB更新为5。所以选BCD。

初开始：SA=2，SB=8，SC=∞，SD=3

第一次取最小边SA则更新为：SA=2，SB=7，SC=∞，SD=3

第二次取最小边SD则更新为：SA=2，SB=6，SC=4，SD=3

第一次取最小边SC则更新为：SA=2，SB=5，SC=4，SD=3

答案：BCD

10. 为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为（网络协议。下列英文缩写中，（）是网络协议。

A. HTTP

B. TCP/IP

C. FTP

D. WWW

解析：网络协议不单指某一协议，而是指各种为计算机网络中进行数据交换而建立的规则、标准或约定的集合。常见的网络协议有：HTTP（超文本传输协议）、TCP/IP（传输控制协议/internet协议）、FTP（文件传输协议）、ARP（地址解析协议）、HTTPS(安全超文本传输协议)、POP3(邮局协议-3)SMTP(简单邮件传送协议)等都属于网络协议。WWW是万维网，不是协议。

答案：ABC

三、问题求解（共2题，每题5分，共计10分）

1.平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶点的平面图至多有____条边。

解析：怎么画最多都只能画9条。

答案：9

2.定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”，可以将A移到B之前，变成字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”，最少需要____次操作。

答案：4

解析：这个不是交换位置喔，是取出再插入。先在原序列中找个最长上升子序列（除去某些元素，但不影响相对位置的序列称为子序列），发现是ACEGI，长度为5，最长了，剩下4个移动一下就能成有序的ABCDEFGHI了。

四、阅读程序写结果（共4题，每题8分，共计32分）

1.

const

SIZE=100;

var

n,i,sum,x:integer;

A:array[1..SIZE]of integer;

begin

readln(n);

fillchar(a,sizeof(a),0);

for i:=1 to n do

begin

read(x);

inc(a[x]);

end;

i:=0;

sum:=0;

while sum<(n div 2 + 1) do

begin

inc(i);

sum:=sum+a[i];

end;

writeln(i);

end.

输入：

11

4 5 6 6 4 3 3 2 3 2 1

输出：__________

答案：3

解析：这是个求中位数的程序。注意读入的时候不是把数读进a[i]，而是让a[x]+1。简单模拟也可以。

2.

var

n:ineger;

procedure f2(x,y:integer);

forward;

procedure f1(x,y:integer);

begin

if x

f2(y,x+y);

end;

procedure f2(x,y:integer);

begin

write(x,? …);

f1(y,x+y);

end;

begin

readln(n);

f1(0,1);

end.

输入：30

输出：__________

答案：1 2 5 13 34

解析：模拟一下，发现是隔一个输出一个的斐波那契数列，注意主程序调用的是f1而不是f2，我没注意看以为是f2结果整个都错位了囧。

3. 啊

const

v = 100;

var

visited:array[1..v]of boolean;

e:array[1..v,1..v]of integer;

n,m,ans,i,j,a,b,c:integer;

procedure dfs(x,len:integer);

var

i:integer;

begin

visited[x] := true;

if len > ans then

ans:=len;

for i:=1 to n do

if (not visited(i)) and(e[x,i] <> -1) then

dfs(I,len+e[x,i]);

visited[x] := false;

end;

begin

readln(n,m);

for i:=1 to n do

for j:=1 to n do

e[i][j] := -1;

for i:=1 to m do

begin

readln(a,b,c);

e[a][b]:=c;

e[b][a]:=c;

end;

for i:=1 to n do

visited[i]:=false;

ans:=0;

for i:=1 to n do

dfs(i,0);

writeln(ans);

end.

输入：

4 6

1 2 10

2 3 20

3 4 30

4 1 40

1 3 50

2 4 60

输出：______

答案：150

解析：一眼看去，过程名叫DFS，输入是个无向图，len>ans的话ans:=len，可以得知这是个在图中用DFS找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，60 50 40,可以一次走完，即走2-4-1-3可以走完这3条边，所以ans是150。

4. 啊

const

SIZE = 10000;

LENGTH = 10;

var

sum : longint;

n,m,I,j : integer;

a:array[1..SIZE , 1..LENGTH]of integer;

function h(u , v :integer):integer;

var

ans,i : integer;

begin

ans:=0;

for i:=1 to n do

if a[u][i] <> a[v][i] then

inc(ans);

h := ans;

end;

begin

readln(n);

fillchar(a,sizeof (a),0);

m:=1;

repeat

i := 1;

while (i <=n) and (a[m][i] =1 ) do

inc(i);

if i>n then

break;

a[m][i]:=1;

for j:=i + 1 to n do

a[m][j] := a[m-1][j];

until false;

sum := 0;

for i := 1 to m do

for j := 1 to m do

sum := sum + h(i,j);

writeln(sum);

end.

输入：7

输出：______

答案：57344

解析：这题比起前几题难多了，我看了半天也看不懂这是干啥的，然后手工模拟，还是不懂是干啥的。于是输入小n，得出sum，找规律。

n=1,sum=2

n=2,sum=16

n=3,sum=96

n=4,sum=512

算这个费了很长时间- -然后还得花时间找规律…我这方法是很不好的方法，大家不要学我。

然后规律是sum=2^(2n-1) *n，然后就能算出n=7的情况了。（其实我当时还没找到这个规律，找到的是sum=2^n*m，m是个很难算的数，用到了杨辉三角…考完后我发现蛋疼了）

57344=2^13 *7。

五、完善程序（第一题，每空2分，第二题，每空3分，共计28分）

1.（大整数开方）输入一个正整数n（1<=n<10^100）,试用二分法计算它的平方根的整数部分。

const

SIZE=200;

type

hugeint = record

len : integer;

num : array[1..SIZE] of integer;

end;

//len表示大整数的位数；num[1]表示个位、num[2]表示十位，以此类推（这个注释不是我带鱼灰写的，是原试题带有的）

var

s : string;

i : integer;

target, left, middle, right : hugeint;

function times(a, b : hugeint) : hugeint;

var

i, j : integer;

ans : hugeint;

begin

fillchar(ans,sizeof(ans),0);

for i:=1 to a.len do

for j:=1 to b.len do

① :=ans.num[i + j - 1] + a.num[i] * b.num[j];

for i:=1 to a.len+b.len do

begin

ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;

②

if ans.num[a.len + b.len] > 0

then ans.len := a.len + b.len

else ans.len := a.len + b.len - 1;

end;

times := ans;

end;

function add(a,b : hugeint) : hugeint;

var

i : integer;

ans: hugeint;

begin

fillchar(ans.num,sizeof(ans.num),0);

if a.len>b.len

then ans.len := a.len

else ans.len := b.len;

for i := 1 to ans.len do

begin

ans.num[i]:=③；

ans.num[i+1] := ans.num[i+1] + ans.num[i] div 10;

ans.num[i] := ans.num[i] mod 10;

end;

if ans.num[ans.len + 1]>0

then inc(ans.len);

add := ans;

end;

function average(a,b: hugeint) : hugeint;

var

i : integer;

ans : hugeint;

begin

ans := add(a,b);

for i:= ans.len downto 2 do

begin

ans.num[i-1] := ans.num[i-1] + (④) *10;

ans.num[i]:=ans.num[i] div 2;

end;

ans.num[1]:=ans.num[1] div 2;

if ans.num[ans.len] = 0

then dec(ans.len);

average := ans;

end;

function plustwo(a : hugeint) : hugeint;

var

i : integer;

ans : hugeint;

begin

ans := a;

ans.num[1] := ans.num[1] + 2;

i:=1;

while (i <= ans.len) and (ans.num[i] >= 10) do

begin

ans.num[i + 1] := ans.num[i + 1] + ans.num[i] div 10;

ans.num[i] := ans.num[i] mod 10;

inc(i);

NOIP2011普及组复赛(试题+源程序)

NOIP2011 普及组复赛 1 .数字反转(reverse.cpp/c/pas ) 【问题描述】 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为 零，否则反转后得到的新数的最高位数字不应为零。(参见样例2) 【输入】 输入文件名为reverse. in 。 输入共一行，一个整数No 【输出】 输出文件名为reverse.out 。 输出共1行，一个整数，表示反转后的新数。 【输入输出样例1】 -1,000,000,000 < N< 1,000,000,000 。 【解题】这道题非常简单，可以读字符串处理，也可以读数字来处理，只不过要注意符号问题(以及但测试数据没出)。 -0 , 【法一】字符串处理 Var i,l,k:i nteger; s:stri ng; p:boolea n; begin assig n(i nput, 'reverse.i n'); reset(i nput); assig n(o utput, 'reverse.out'); rewrite(output); readl n( s); l:=le ngth(s); k:=1; if s[1]=' -' the n begin write('-'); k:=2; en d; p:=true;; for i:=l dow nto k do begin if(p)a nd((s[i]='0')) the n continue else begin write(s[i]); p:=false;; en d; en d; close(i nput); close(output); en d. 【法二】数字处理 Var f:i nteger; n,an s:lo ngint; begin assig n(i nput, 'reverse.i n'); reset(i nput); assig n(o utput, 'reverse.out'); rewrite(output); readl n(n); if n<0 the n begin f:=-1; n :=-n;

NOIP2009提高组初赛试题及答案

第十五届全国青少年信息学奥林匹克联赛初赛试题 （提高组 Pascal语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一．单项选择题（共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、在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是： 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） C)（0，10，110，111） D)（1，01，000，001） 8、快速排序平均情况和最坏情况下的算法时间复杂度分别为： A) 平均情况O(nlog2n)，最坏情况O(n2) B) 平均情况O(n)，最坏情况O(n2) C) 平均情况O(n)，最坏情况O(nlog2n)

NOIP2014提高组复赛精彩试题(卷)

CCF全国信息学奥林匹克联赛（NOIP2014）复赛 提高组 day1 1．生活大爆炸版石头剪刀布 (rps.cpp/c/pas) 【问题描述】 石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第8集中出现了一种石头剪刀布的升级版游戏。升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势： 斯波克：《星际迷航》主角之一。 蜥蜴人：《星际迷航》中的反面角色。 这五种手势的胜负关系如表一所示，表中列出的是甲对乙的游戏结果。 表一石头剪刀布升级版胜负关系 现在，小A和小B尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小A以“石头-布-石头-剪刀-蜥蜴人-斯波克”长度为6的周期出拳，那么他的出拳序列就是“石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-……”，而如果小B 以“剪刀-石头-布-斯波克-蜥蜴人”长度为5的周期出拳，那么他出拳的序列就是“剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-……” 已知小A和小B一共进行N次猜拳。每一次赢的人得1分，输的得0分；平局两人都得0分。现请你统计N次猜拳结束之后两人的得分。 【输入】 输入文件名为rps.in。 第一行包含三个整数：N，NA，NB，分别表示共进行N次猜拳、小A出拳的周期长度，小B出拳的周期长度。数与数之间以一个空格分隔。 第二行包含NA个整数，表示小A出拳的规律，第三行包含NB个整数，表示小B出拳的规律。其中，0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”， 4表示“斯波克”。数与数之间以一个空格分隔。

noip2011初赛试题及答案(完美Word版)

第十七届全国青少年信息学奥林匹克联赛初赛试题 （提高组 Pascal语言两小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分。共计30分。每题有且仅有一个正确选项。） B 1．在二进制下，1100011 +（）= 1110000。 A．1011 B．1101 C．1010 D．1111 B 2．字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66 B．5A C．50 D．视具体的计算机而定 A 3．右图是一棵二叉树，它的先序遍历是（）。 A．ABDEFC B．DBEFAC C．DFEBCA D．ABCDEF D 4．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） B 5．广度优先搜索时，需要用到的数据结构是（）。 A．链表B．队列C．栈D．散列表 A 6．在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）。 A．程序运行时理论上所占的内存空间 B．程序运行时理论上所占的数组空间 C．程序运行时理论上所占的硬盘空间 D．程序源文件理论上所占的硬盘空间 C 7．应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。 A．O(n2)B．O(n log n)C．O(n) D．O(1) D 8．为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A．微软 B．美国计算机协会（ACM） C．联台国教科文组织D．万维网联盟（W3C）

NOIP2008提高组复赛试题及题解

全国信息学奥林匹克联赛（NOIP2008）复赛 提高组 一、题目概览 二、提交源程序文件名 三、编译命令（不包含任何优化开关） 四、运行内存限制 注意事项： 1. 文件名（程序名和输入输出文件名）必须使用大写。 2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。 3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。

1. 笨小猴 (word.pas/c/cpp) 【问题描述】 笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！ 这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn 是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。 【输入】 输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。【输出】 输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”； 第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。 【输入输出样例1】 【输入输出样例1解释】 单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。 【输入输出样例2】 【输入输出样例2解释】 单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。 基本的字符串处理，细心一点应该没问题的，不过判断素数时似乎需要考虑下0和1的情况。var a:array['a'..'z']of integer; s:string; l,i,max,min,n:integer; ch:char;flag:boolean; begin assign(input,'word.in'); reset(input); assign(output,'word.out'); rewrite(output); readln(s);

(完整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

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提高组试题

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。

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

第十六届全国青少年信息学奥林匹克联赛初赛试题试题及答案 NOIP2010（Pascal提高组） 一、单项选择题 1.与16进制数 A1.2等值的10进制数是（A ） A.101.2 B.111.4 C.161.125 D.177.25 2.一个字节（byte）由（A ）个二进制组成。 A.8 B.16 C.32 D.以上都有可能 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下可执行文件的默认扩展名是(B )。 A.exe https://www.wendangku.net/doc/b113672907.html, C.dll D.以上都不是 5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（C ）也成立。 A.100 B.144 C.164 D.196 6.提出“存储程序”的计算机工作原理的是（B ）。 A. 克劳德?香农 B. 戈登?摩尔 C. 查尔斯?巴比奇 D. 冯?诺依曼 7.前缀表达式“+ 3 * 2 + 512 ” 的值是（C ）。 A.23 B.25 C.37 D.65

8.主存储器的存取速度比中央处理器(CPU)的工作速度慢的多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了(B )。 A.寄存器 B.高速缓存 C.闪存 D.外存 9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（C ）号位置。 A.2k B.2k+1 C.k/2下取整 D.(k+1)/2 10. 以下竞赛活动中历史最悠久的是（D ）。 A. NOIP B. NOI C. IOI D. APIO 二、不定项选择题 1.元素R1、R2、R3、R4、R5入栈的顺序为R1、R2、R3、R4、R5。如果第1个出栈的是R3，那么第5个出栈的可能是(AB )。 A. R1 B. R2 C.R4 D.R5 2. Pascal语言，C语言和C++语言都属于(AD )。 A. 高级语言 B. 自然语言 C. 解释性语言 D. 编译性语言 3. 原地排序是指在排序过程中(除了存储待排序元素以外的)辅助空间的大小与数据规模无关的排序算法。以下属于原地排序的有(AC )。 A. 冒泡排序 B. 插入排序 C. 基数排序 D. 选择排序 4. 在整数的补码表示法中，以下说法正确的是（）。 A．只有负整数的编码最高位为1 B．在编码的位数确定后，所能表示的最小整数和最大整数的绝对值相同 C．整数0只有一个唯一的编码 D．两个用补码表示的数相加时，如果在最高位产生进位，则表示运算溢出 5. 一颗二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（B ）。

NOIP2007_提高组_复赛试题

全国信息学奥林匹克联赛（NOIP2007）复赛提高组 1．统计数字 (count.pas/c/cpp) 【问题描述】 某次科研调查时得到了n 个自然数，每个数均不超过1500000000（1.5*109）。已知不相同的数 不超过10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入】 输入文件count.in包含n+1 行：第1 行是整数 n，表示自然数的个数。 第2~n+1 行每行一个自然数。 【输出】输出文件count.out包含m 行（m 为n 个自然数中不相同数的个数），按照自然数从小到大 的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 【输入输出样例】 【限制】 40%的数据满足：1<=n<=1000 80%的数据满足：1<=n<=50000 100%的数据满足：1<=n<=200000，每个数均不超过1 500 000 000（1.5*109）

2．字符串的展开 (expand.pas/c/cpp) 【问题描述】 在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或“4-8”的子串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：（1）遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧 同为小写字母或同为数字，且按照ASCII 码的顺序，减号右边的字符严格大于左边的字符。 （2）参数p1：展开方式。p1=1 时，对于字母子串，填充小写字母；p1=2 时，对于字母子串， 填充大写字母。这两种情况下数字子串的填充方式相同。p1=3 时，不论是字母子串还是数字子串， 都用与要填充的字母个数相同的星号“*”来填充。 （3）参数p2：填充字符的重复个数。p2=k 表示同一个字符要连续填充k 个。例如，当p2=3 时，子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。 （4）参数p3：是否改为逆序：p3=1 表示维持原有顺序，p3=2 表示采用逆序输出，注意这时仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2 时，子串“d-h”应扩展为“dggffeeh”。 （5）如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII 码的顺序小于或等于左边字符， 输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。 【输入】 输入文件expand.in包括两行： 第1 行为用空格隔开的3 个正整数，依次表示参数p1，p2，p3。 第2 行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。 【输出】 输出文件expand.out只有一行，为展开后的字符串。

noip2011 初赛普及组c++试题及答案

NOIP2011 （普及组 C++语言二小时完成） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。） 1．在二进制下，1011001 + （）= 1100110。 A．1011 B．1101 C．1010 D．1111 2．字符“0”的ASCII码为48，则字符“9”的ASCII码为（）。 A．39 B．57 C．120 D．视具体的计算机而定 3．一片容量为8G的SD卡能储存大约（）张大小为2MB的数码照片。 A．1600 B．2000 C．4000 D．16000 4．摩尔定律（Moore's law)是由英特尔创始人之一戈登·摩尔(Gordon Moor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电驴的集成度大约每（）个月翻一番。A．1 B．6C．18 D．36 5．无向完全图是图中每对顶点之间都恰好有一条边的简单图。已知无向完全图G有7个顶点，则它共有（）条边。 A．7 B．21 C．42 D．49 6．寄存器是（）的重要组成部分。 A．硬盘B．高速缓存C．内存D．中央处理器（CPU） 7．如果根结点的深度记为1，则一棵恰有2011个叶结点的二叉树的深度最少是（）。 A．10 B．11 C．12 D．13 8．体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 A．快速排序B．插入排序C．冒泡排序D．归并排序 9．一个正整数在二进制下有100位，则它在十六进制下有（）位。 A．7 B．13 C．25 D．不能确定 10．有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是（）。 A．正确的，将文件放入回收站以为着彻底删除、无法恢复 B．不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C．不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D．不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除

noip2004 提高组复赛试题及参考程序(pascal)

第十届信息学奥林匹克联赛复赛试题（NOIP2004） 一、津津的储蓄计划(save.pas/c/cpp) 【问题描述】 津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20％还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。 例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。 津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。 现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20％还给津津之后，津津手中会有多少钱。 【输入文件】 输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。 【输出文件】 输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。 【样例输入1】 290 230 280 200 300 170 340 50 90 80 200 60 【样例输出1】 -7 【样例输入2】 290 230

NOIP2011普及组

数字反转题目描述 给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形 式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。【数据范围】 -1,000,000,000 ≤ N≤ 1,000,000,000。 输入格式 输入共 1 行，一个整数N。 输出格式 输出共 1 行，一个整数，表示反转后的新数。 样例输入： 123 －380 样例输出： 321 －83 统计单词数题目描述 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位 置，有的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章 中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。 【数据范围】 1 ≤ 单词长度≤ 10。 1 ≤ 文章长度≤ 1,000,000。 【输入输出样例 1 说明】 输出结果表示给定的单词To 在文章中出现两次，第一次出现的位置为0。 【输入输出样例 2 说明】 表示给定的单词to 在文章中没有出现，输出整数-1。 输入格式 第 1 行为一个字符串，其中只含字母，表示给定单词； 第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章。

输出格式 只有一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开， 分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字 母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一个整数-1。 样例输入： [sample 1] To to be or not to be is a question [sample 2] to Did the Ottoman Empire lose its power at that time 样例输出： [sample 1] 2 0 [sample 2] -1 瑞士轮题目描述 2*N名编号为1~2N的选手共进行R轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。 每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1名和第2名、第3名和第4名、……、第2K-1名和第2K名、……、第2N-1名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。 现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第Q的选手编号是多少。我 们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。 输入格式 输入的第一行是三个正整数N、R、Q，每两个数之间用一个空格隔开，表示有2*N名选手、R轮比赛，以及我们关心的名次Q。 第二行是2*N个非负整数s1，s2，…，s2N，每两个数之间用一个空格隔开，其中si表示编号为i 的选手的初始分数。 第三行是2*N个正整数w1，w2，…，w2N，每两个数之间用一个空格隔开，其中wi表示编号为i 的选手的实力值。 输出格式

NOIP2012提高组复赛试题

全国信息学奥林匹克联赛（2012）复赛提高组2 2． 1 ·同余方程 〖问题描述〗 求关于的同余方程三1 (句的最小正整数解。 输入〗 输入文件为 输入只有一行，包含两个正整数用一个空格隔开 输出〗 输出文件为 输出只有一行，包含一个正整数№即最小正整数解。输入数据保证一定有解。 〖输入输出样例〗 对于40％的数据，2 L000：对于60％的数据， 2 50，000，000： 对于100％的数据，2，2，000，000，000。 2 ·借教室 (. ) 问题描述〗 在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。 面对海量租借教室的信息，我们自然希望编程解决这个问 题。

我们需要处理接下来n天的借教室信息，其中第i天学校有个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为d]，斗t}，表示某租借者需要从第丬天到第t]天租借教室（包括第丬天和第t)天），每天需要租借个教室。 我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供d]个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。 借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第丬天到第t)天中有至少一天剩余的教室数量不足d)个。现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改 输入〗 输入文件为 第一行包含两个正整数n，m,表示天数和订单的数量。 第二行包含n个正整数，其中第i个数为，表示第i天可用于租借的教室数量。 接下来有m行，每行包含三个正整数]，t]，表示租借的数量，租借开始、结束分别在第几天。 每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。 〖输出〗 输出文件为 如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数一1 ,第二行输出需要修改订单的申请人编号。 〖输入输出样例〗

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”（均不包含引号）。

NOIP普及组初赛历年试题及答案选择题篇

NOIP普及组初赛历年试题及答案选择题篇 单项选择题：每次共20题，每题1.5分，共计30分。每题有且仅有一个正确选项。注：答案在文末 一、计算机基础（每年8-10题，占选择题的一半，找份材料翻几遍就可拿分了） NOIP2011-3. 一片容量为8G的SD卡能储存大约( )张大小为2MB的数码照片。 A.1600 B.2000 C.4000 D.16000 NOIP2011-4. 摩尔定律(Moore'slaw)是由英特尔创始人之一戈登·摩尔(GordonMoor)提出来的。根据摩尔定律，在过去几十年一级在可预测的未来纪念，单块集成电路的集成度大约每( )个月翻一番。 A.1 B.6 C.18 D.36 NOIP2011-6.寄存器是( )的重要组成部分。 A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU) NOIP2011-10. 有人认为，在个人电脑送修前，将文件放入回收站中就是已经将其删除了。这种想法是( )。 A .正确的，将文件放入回收站以为着彻底删除、无法恢复 B.不正确的，只有将回收站清空后，才意味着彻底删除、无法恢复 C.不正确的，即使回收站清空，文件只是被标记为删除，仍可能通过回复软件找回 D.不正确的，只要在硬盘上出现过的文件，永远不可能被彻底删除 NOIP2011-14. 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下不属于生物特征识别技术及其应用的是( )。

NOIP2011-16. 关于汇编语言，下列说法错误的是( )。 A.是一种与具体硬件相关的程序设计语言 B.在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试 C.可以直接访问寄存器、内存单元、以及I/O端口 D.随着高级语言的诞生，如今已完全被淘汰，不再使用 NOIP2011-18. 1956年( )授予肖克利、巴丁和布拉顿，以表彰他们对半导体的研究和晶体管效应的发现。 A.诺贝尔物理学奖 B.约翰·冯·诺依曼奖 C.图灵奖 D.高德纳奖 NOIP2011-20. 从ENIAC到当前最先进的计算机，冯·诺依曼体系结构始终占有重要地位。冯诺依曼体系结构的核心内容是( )。 A.采用开关电路 B.采用半导体器件 C.采用存储程序和程序控制原理 D.采用键盘输入 NOIP2012-1. 计算机如果缺少( )，将无法正常启动。 A.内存 B.鼠标 C.U盘 D.摄像头

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

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.包括欧拉环游的图(欧拉环游是指通过图中每边恰好一次的闭路径)