完整wordNOIP初赛提高组试题解析Word文件下载.docx

资源描述

完整wordNOIP初赛提高组试题解析Word文件下载.docx

《完整wordNOIP初赛提高组试题解析Word文件下载.docx》由会员分享，可在线阅读，更多相关《完整wordNOIP初赛提高组试题解析Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。

完整wordNOIP初赛提高组试题解析Word文件下载.docx

A．O

（1）B．O（n）C．O（n2）D．O（Fn）

【分析】计算F1需要1次，计算F2需要一次，计算Fn需要计算F（n-1）的次数加上F（n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O（（（1+sqrt（5））/2）^n）.

8．二叉查找树具有如下性质：

每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。

那么，二叉查找树的（B）是一个有序序列。

A．先序遍历B．中序遍历C．后序遍历D．宽度优先遍历

9．将（2，6，10，17）分别存储到某个地址区间为0～10的哈希表中，如果哈希函数h（x）=（D），将不会产生冲突，其中amodb表示a除以b的余数。

A．xmod11B．x2mod11

C．2xmod11D．

mod11，其中

表示

下取整

【分析】A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突

10．IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。

因此，它正逐渐被使用（D）位地址的IPv6协议所取代。

A．40B．48C．64D．128

11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。

那么12个顶点的二分图至多有（C）条边。

A．18B．24C．36D．66

【分析】二分为6个和6个的顶点，此时边最多，有36条边。

12．（B）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。

目前它已经收录了超过十万个不同字符。

A．ASCIIB．UnicodeC．GBK2312D．BIG5

UNICODE与ASCII的区别.

1.ASCII的特点

（1）ASCII是用来表示英文字符的一种编码规范。

每个ASCII字符占用1个字节，因此，ASCII编码可以表示的最大字符数是255（00H—FFH）。

这对于英文而言，是没有问题的，一般只什么用到前128个（00H--7FH,最高位为0）。

而最高位为1的另128个字符（80H—FFH）被称为“扩展ASCII”，一般用来存放英文的制表符、部分音标字符等等的一些其它符号。

（2）但是对于中文等比较复杂的语言，255个字符显然不够用。

于是，各个国家纷纷制定了自己的文字编码规范，其中中文的文字编码规范叫做“GB2312—80”，它是和ASCII兼容的一种编码规范，其实就是利用扩展ASCII没有真正标准化这一点，把一个中文字符用两个扩展ASCII字符来表示，以区分ASCII码部分。

但是这个方法有问题，最大的问题就是中文的文字编码和扩展ASCII码有重叠。

而很多软件利用扩展ASCII码的英文制表符来画表格，这样的软件用到中文系统中，这些表格就会被误认作中文字符，出现乱码。

另外，由于各国和各地区都有自己的文字编码规则，它们互相冲突，这给各国和各地区交换信息带来了很大的麻烦。

2.UNICODE的产生

（1）要真正解决这个问题，不能从扩展ASCII的角度入手，UNICODE作为一个全新的编码系统应运而生，它可以将中文、法文、德文……等等所有的文字统一起来考虑，为每一个文字都分配一个单独的编码。

3.什么是UNICODE

Unicode与ASCII一样也是一种字符编码方法，它占用两个字节（0000H—FFFFH）,容纳65536个字符，这完全可以容纳全世界所有语言文字的编码。

在Unicode里，所有的字符都按一个字符来处理，它们都有一个唯一的Unicode码。

13．把64位非零浮点数强制转换成32位浮点数后，不可能（D）。

A．大于原数B．小于原数C．等于原数D．与原数符号相反

【分析】64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位

14．对一个n个顶点、m条边的带权有向简单图用Dijkstr算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（B）。

A．O（mn+n3）B．O（n2）C．O（（m+n）logn）D．O（（m+n2）logn）

【分析】Dijkstra算法（双重for循环）计算单源最短路时间复杂度如果不借助堆或优先队列优化，是O（n^2）.

15．T（n）表示某个算法输入规模为n时的运算次数。

如果T

（1）为常数，且有递归式

T（n）=2*T（n/2）+2n，那么T（n）=（B）。

A．Θ（n）B．Θ（nlogn）C．Θ（n2）D．Θ（n2logn）

【分析】Θ的含义和“等于”类似，而大O的含义和“小于等于”类似

设N×

（1/2）^X=1,X=log2N

T（n）=2*T（n/2）+2n=2×

（2×

（T（n/4）+2×

（n/2））+2n=22×

T（n/4）+（2n）×

=2X×

（1）+（2n）×

X=2^log2N×

（1）+（2N）×

log2N

=N+（2N）×

log2N=O（N×

log2N）

二、不定项选择题（共5题，每题1.5分，共计7.5分；

每题有一个或多个正确选项，多选或少选均不得分）

1．下列程序中，正确计算1，2，…，100这100个自然数之和sum（初始值为0）的是（AC）。

2．（AD）的平均时间复杂度为O（nlogn），其中n是待排序的元素个数。

A．快速排序B．插入排序C．冒泡排序D．归并排序

【分析】只有快速排序和归并排序是nlogn的，冒泡和插入都是n^2的时间复杂度。

3．以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（CD）。

A．A1B．A2C．A3D．A4

4．（AB）属于NP类问题。

A．存在一个P类问题B．任何一个P类问题

C．任何一个不属于P类的问题

D．任何一个在（输入规模的）指数时间内能够解决的问题

1.时间复杂度：

（1）时间复杂度：

是指执行算法所需要的计算工作量。

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

（2）多项式时间算法：

如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。

2.P类、NP类问题

（1）P类问题的概念：

如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。

（2）NP类问题：

NP（Non-deterministicPolynomial）问题是指可以在多项式的时间里验证一个解的问题。

NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。

（3）所有的P类问题都是NP问题。

NP问题不是非P类问题

3.NPC问题（NP完全问题）：

Cook在1971年给出并证明了有一类问题具有下述性质：

（1）这类问题中任何一个问题至今未找到多项式时间算法；

（2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法这类问题就是所谓的NP完全问题。

（3）NPC问题的定义非常简单。

同时满足下面两个条件的问题就是NPC问题。

首先，它得是一个NP问题；

然后，所有的NP问题都可以约化到它。

5．CCFNOIP复赛考试结束后，因（ABCD）提出的申诉将不会被受理。

A．源程序文件名大小写错误

B．源程序保存在指定文件夹以外的位置

C．输出文件的文件名错误

D．只提交了可执行文件，未提交源程序

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

每题全部答对得5分，没有部分分）

1．某系统自称使用了一种防窃听的方式验证用户密码。

密码是n个数s1，s2，…，sn，均为0或1。

该系统每次随机生成n个数a1，a2，…，an，均为0或1，请用户回答（s1a1+s2a2+…+snan）除以2的余数。

如果多次的回答总是正确，即认为掌握密码。

该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。

然而，事与愿违。

例如，当n=4时，有人窃听了以下5次问答：

就破解出了密码s1=0，s2=1，s3=1，s4=1。

（1）由第5组得到s1=0；

（2）由第1组、第5组得到s2=1；

（3）由第1组、第3组得到s3=1；

（3）由第2组、第3组得到s4=1；

2．现有一只青蛙，初始时在n号荷叶上。

当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1，2，…，k号荷尔蒙叶之一上，直至跳到1号荷叶为止。

当n=2时，平均一共跳2次；

当n=3时，平均一共跳2.5次。

则当n=5时，平均一共跳37/12次。

【分析——递推】

（1）由n=2时，跳法2→2，2→1共2次，平均跳的次数f2=2次，说明在求平均时编号1不统计在内。

（2）由n=3时，跳法3→3，3→2，3→1，再从2号跳跳法2→2，2→1共5次，平均跳的次数f3=2.5次；

f3=（3+f2）/2=2.5

（3）由n=4时，跳法分别是落在1号、2号、3号、4号；

平均跳的次数

f4=（4+f2+f3）/3=（4+2+2.5）/3=8.5/3

（4）由n=5时，跳法分别是落在1号、2号、3号、4号、5号；

f5=（5+f2+f3+f4）/4=（5+2+2.5+8.5/3）/4=37/12

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

1．【字符串——判定输入的字符串是否是回文串】

var

n,i:

integer;

str:

string;

isPlalindrome:

Boolean;

readln（str）;

=Length（str）;

isPlalindrome:

=true;

fori:

=1to（nidv2）do

begin

if（str[i]<

str[n-i+1]）then

isPlalindrome:

=false;

end;

if（isPlalindrome）then

writeln（‘Yes’）

writeln（‘No’）;

end.

输入：

abceecba

输出：

Yes

【分析】str[1]——str[8]、str[2]——str[7]、str[3]——str[6]、str[4]——str[5]这4对字符相同则返回true

2．【数学——１到1000中是１０或１５的倍数的数的个数】

Vara,b,u,v,I,num:

readln（a,b,u,v）;

num:

=0;

fori:

=atobdo

if（Imodu=0）or（Imodv=0）theninc（num）;

writeln（num）;

110001015

133

【分析】此题计数1-1000范围内能够整除10或15的数有多少个，使用容斥原理或者集合求并很容易可以得到1000/10+1000/15-1000/30=133.

3．【动态规划——最长上升子序列的长度】

constSIZE=100;

varn,ans,I,j:

height,num:

array[1..SIZE]ofinteger;

read（n）;

=1tondo

read（height[i]）;

num[i]:

=1;

forj:

=1toi-1do

begin

if（（height[j]<

height[i]）and（num[j]>

=num[i]））then

num[i]:

=num[j]+1;

end;

ans:

if（num[i]>

ans）thenans:

=ans+num[i];

writeln（ans）;

32511127410

【1.状态描述】

（1）height[i]存放的数组

（2）num[i]：

数组height[1]——height[i]中中包含height[i]上升序列长度

【2.状态转移】

1.初始状态：

num[i]:

num[1]:

2.状态转移：

从下标1逐步递推到n，求解num[i]

num[i]=Max{num[j],（1<

=j<

=i-1,height[j]<

height[i]）}+1

【3.算法分析】例height[4]=11>

height[3]=5，num[4]=num[3]+1=3

【4.算法设计】

求解num[i]的最优解

2.状态前驱：

num[i]的前驱状态num[j]：

num[1]——num[i-1]

3.状态转移：

（1）条件：

=num[i]））

（2）转移方程：

4．【深度优先搜索——上下左右找棋盘数字为0的连续单元格数量】

n,m,p,count,ans,x,y,I,j:

array[1..SIZE,1..SIZE]ofinteger;

procedurecolour（x,y:

integer）;

inc（count）;

a[x][y]:

if（x>

1）and（a[x-1][y]=0）thencolour（x-1,y）;

//上

if（y>

1）and（a[x][y-1]=0）thencolour（x,y-1）;

//左

if（x<

n）and（a[x+1][y]=0）thencolour（x+1,y）;

//下

if（y<

m）and（a[x][y+1]=0）thencolour（x,y+1）;

//右

fillchar（a,sizeof（a）,0）;

readln（n,m,p）;

=1topdo

read（x,y）;

forj:

=1tomdo

ifa[i][j]=0then

begin

count:

colour（i,j）;

if（ans<

count）thenans:

=count;

writeln（ans）;

659

（1）棋盘状态：

a[x][y]:

=1或0

（2）count,ans：

数字为0的连续单元格数量，count当前解,ans当前最优解

查找棋盘每个值为0的单元格a[i][j]=0

如果a[i][j]=0则

（1）：

状态修改inc（count）;

a[i][j]:

（2）：

按上下左右4个方向深度搜索下一单元格

【3.算法分析】分上下左右找数字为0的连续单元格数量

查找棋盘每个值为0的单元格，并以它为起点查找数字为0的连续单元格数量count,初始count:

2.父状态a[x][y]=0

procedurecolour（x,y:

1.计算新状态：

inc（count）;

2.父状态访问过标志：

3.试探各种子状态可能——按上下左右4个方向深度搜索下一单元格

4.下一单元格值为0，则深度搜索colour（x-1,y）……

五、完善程序（第1题15分，第2题13分，共计28分）

1．（序列重排）全局数组变量a定义如下：

constintSIZE=100;

inta[SIZE],n;

它记录着一个长度为n的序列a[1]，a[2]，…，a[n]。

现在需要一个函数，以整数p（1≤p≤n）为参数，实现如下功能：

将序列a的前p个数与后n-p个数对调，且不改变这p个数（或n-p个数）之间的相对位置。

例如，长度为5的序列1，2，3，4，5，当p=2时重排结果为3，4，5，1，2。

有一种朴素的算法可以实现这一需求，其时间复杂度为O（n）、空间复杂度为O（n）：

procedureswap1（p:

longint）;

I,j:

array[1..SIZE]oflongint;

fori:

=1topdob[

（1）n-p+i]:

=a[i];

//（2分）

=p+1tondob[i-p]:

=1tondoa[i]:

=b[i];

【算法设计】

1.第一种方法是通过开一个b数组，然后先将a数组中1到p的数复制到b数组中后p个位置：

n-p+1到n。

2.将a数组p+1到n区间的数复制到b数组前段1——n-p。

3.最后再将b数组元素复制回a数组中；

显然第一空是n-p+i。

以p=3为例

我们也可以用时间换空间，使用时间复杂度为O（n2）、空间复杂度为O

（1）的算法：

procedureswap2（p:

varI,j,temp:

=p+1tondo

temp:

=Idownto

（2）i+1-pdoa[j]:

=a[j-1];

//（2分）

（3）a[i-p]:

=temp;

【1.算法分析】前P个数逐渐往后移动

【2.算法设计】

1.初始状态：

将第p+1位置空出——temp:

，将前p个数后移

2.空出位置i从p+1一直到n，移动的数就是i左边的p个数

3.将空出位置i原来的数temp放到i的前面空出的位置i-p——a[i-p]:

事实上，还有一种更好的算法，时间复杂度为O（n）、空间复杂度为O

（1）;

procedureswap3（p:

start1,end1,start2,end2,I,j,temp:

start1:

end1:

=p;

start2:

=p+1;

end2:

=n;

whiletruedo

=star1;

=start2;

while（i<

=end1）and（j<

=end2）do

begin

temp:

a[i]:

=a[j];

a[j]:

inc（i）;

inc（j）;

ifi<

=end1thenstart1:

elseif（4）j<

=end2then//（3分）

start1:

=（5）i;

//（3分）

end1:

=（6）J-1（或start2-1）;

start2:

=j;

end

else

break;

【1.算法分析】

1.将数组分成两段start1——end1；

start2——end2进行交换，

i,j是两段数中当前交换数组的下标

2.状态转移1：

第一段数组全部交换结束，第二段尚有部分数组没有移动，即

if（i>

end1）and（j<

end2）then则交换的两段需要进行调整

（1）第一段start1、end1右移，应该在当前i、j之间：

=i;

end1:

=J-1

（2）第二段start2右移、end2不变——start2:

3.状态转移2：

第二段数组全部交换

展开阅读全文