谁有2007年第十三届全国信息学奥林匹克竞赛初试试题(P)？

a、单项选择题(* * 10题，每题1.5分，* * 15分。每个问题有且只有一个正确答案)。

1.在下列各项中，(d)不是中央处理器的一部分。

A.控制器b .算术单元c .寄存器d .主板e .算术逻辑单元(ALU)

2.在关系数据库中，存储在数据库中的数据的逻辑结构主要是(B)。

A.二叉树B .多分支树c .哈希表D. B+树e .二维表

3.下列各项中，只有(D)不是计算机存储容量的常用单位。

A.字节

4.4的含义。ASCII码是(b)。

A.二进制-十进制转换码b .美国信息交换标准码c .数字的二进制编码

D.能被计算机处理的字符的唯一编码。常用字符的二进制编码

5.在C语言中，表达式23 | 2 ^ 5的值是(a)。

A.23 B. 1 C.18 D.32 E.24

6.在C语言中，判断A等于0或B等于0或C等于0的正确条件表达式是(B)。

A.！((a！=0)||(b！=0)||(c！=0)) B！((a！= 0)& amp；& amp(b！= 0)& amp；& amp(c！=0))

C.！(a = = 0 & amp& ampb==0)||(c！= 0)d .(a = 0)& amp；& amp(b = 0)amp；& amp(c=0)

E.！((a=0)||(b=0)||(c=0))

7.地面上有编号为A、B、C的三根细柱，在A柱上放置10个中间有孔直径相同的圆盘，编号为1，2，3，...从上到下。a柱上的部分光盘可通过B柱移入C柱或暂时存放在B柱上。如果B柱上的操作记录是“进，进，出，进，进，出，进，进，出，进，进，出，进，出”。然后，在C柱上，从下到上的车牌号码是(D)。

A.2 4 3 6 5 7 b . 2 4 1 2 5 7 c . 2 4 3 1 7 6d . 2 4 3 6 7 5 e . 2 1 4 3 7 5

8.十进制数17.5625对应的八进制数是(b)。

a . 21.5625 b . 21.44 c . 21.73d . 21.731 e .前四个答案都不正确。

9.欧拉图G是指能形成一个闭环的图，图G的每条边在这个闭环上恰好出现一次(即画一笔)。在下面的描述中，是(d)不一定是欧拉。

图g中没有奇数度的顶点。

B.包含欧拉环行导航的图(欧拉环行导航是指通过图的每条边恰好一次的闭合路径)。

C.包含欧拉闭迹的图(欧拉迹是指通过图的每条边恰好一次的路径)。

有一个循环恰好通过每个顶点一次。

E.本身是闭迹的图

10.不能被自身控制终止的循环称为“无限循环”。例如，在C语言程序中，语句“while(1)”

printf(" * ")；”是一个无限循环，它将在运行时无休止地打印*号。下列关于无限循环的说法中，只有(a)是正确的。

A.没有算法可以判断任何程序和相应的输入数据是否会出现无限循环。因此，

任何编译系统都不做无限循环检查。

一些编译系统可以检测无限循环。

C.无限循环是一个语法错误。既然编译系统可以检查各种语法错误，那么它也应该能够检查无限循环。

D.死循环类似于多个进程中的“死锁”，死锁是可以检测到的，所以死循环也是可以检测到的。

关于

E.对于死循环，只能等到它发生了再做现场处理，没有更主动的手段。

二、不定选择题(* * 10题，每题1.5分，* * * 15分。每个问题的正确答案数大于或等于1。选多选少都不计分)。

11.设A = B =真，C = D =假，下列逻辑运算表达式值为真(ABC)。

A.(?A∧B)∨(C∧D∨A) B？(((A∧B)∨C)∧D)

C.A∧(B∨C∨D)∨D .(A∧(D∨C))∧B

12.命题“P→Q”可以读作P蕴涵Q，这里P和Q是两个独立的命题。只有当命题P成立，命题Q不成立时，命题“P→Q”的值为假，其他情况均为真。与命题“P→Q”等价的逻辑关系是(AD)。

A.？P∨Q B. P∧Q C？(P∨Q) D？(?Q∧P)

13.(2070) 16+(34) 8的结果是(ABD)。

A.(8332)10

C.(100000000110)2d .(20214)8

14.已知有7个节点的二叉树的第一次根遍历是1 2 4 5 6 3 7(编号是节点的编号，下同)，最后一次根遍历是4 6 5 2 7 3 1，所以二叉树可能的中间根遍历是(ABD)。

A.4 2 6 5 1 7 3 B. 4 2 5 6 1 3 7

C.4 2 3 1 5 4 7 D. 4 2 5 6 1 7 3

15.冗余数据是指可以从其他数据中导出的数据。例如，学生的数学、语文和英语成绩已经存储在数据库中。如果还存储了三科总成绩，则总成绩可视为冗余数据。冗余数据往往导致数据不一致。比如以上四项数据全部输入，由于操作失误，总成绩不等于三科成绩之和，就会产生矛盾。下列关于冗余数据的说法中，正确的是(BC)。

A.应该从数据库中删除所有冗余数据。

B.与用高级语言编写的数据处理系统相比，用关系数据库编写的系统更容易消除冗余数据。

C.为了提高查询效率，可以在数据库中适当保留一些冗余数据，但更新时要进行兼容性检查。

D.做兼容性测试会降低效率，所以可以忽略数据库中的冗余数据。

16.在以下软件中，推荐NOIP竞赛(复赛)使用的语言环境是(ABD)。

A.gcc B. g++

C.Turbo C D. free pascal

17.以下为断电后仍能保存数据(AB)。

A.硬盘B. rom C .视频存储器D. RAM

18.下列关于计算机语言的说法中，正确的是(CD)。

A.高级语言比汇编语言更高级，因为它的程序运行效率更高。

B.随着Pascal、C等高级语言的出现，机器语言和汇编语言退出了历史舞台。

c高级语言程序比汇编语言程序更容易从一台计算机移植到另一台计算机。

D.c是一种面向过程的高级计算机语言。

19.下列关于算法复杂度的说法中，正确的是(BC)。

a算法的时间复杂度是指在计算机上实现时的运行时间。

b算法的时间复杂度是指对于算法的一个或多个主要运算，运算次数与问题规模之间的函数关系。

C.如果一个问题是NPC，说明在求解该问题时不存在多项式时间复杂度的算法。但这一点在理论上没有得到证实，也没有被否定。

D.如果一个问题是NP级的，那么它的结论和c一样。

20.近20年来，许多计算机专家大力提倡递归算法作为解决更复杂问题的有力工具。下列关于递归算法的说法中，正确的是(AC)。

A.1977左右形成的标准计算机高级语言FORTRAN77禁止程序中的递归，原因之一是这种方法可能会占用更多的内存空间。

B.与非递归算法相比，递归算法解决同样的问题一般运行速度更快。

对于更复杂的问题，用递归方式编程往往比用非递归方式更容易。

d .对于定义的标准数学函数sin(x)，应用程序中的语句“y = sin(sin(x))；这是一个递归调用。3.解题(***2题，每题5分，* * * 10分)

1.给定n个编号球，数字依次为1，2，…，n。把这N个球放进R个相同的盒子里，这是不允许的。

如果有空盒子，不同放置方法的总数记录为S(n，r)。例如S(4，2)=7，七种不同的放置方式如下。

{(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)},

{(14),(23)}。当n = 7，r = 4时，s (7，4) = _ _ _ _ _ _ _。

2.n个人在操场上围成一个圈，从1到n顺时针编号，然后从第一个人开始，每

其他每个人都要求下一个人离开操场。显然，第一轮结束后，偶数的人都离开了操场。依次做，直着做

操场上只剩下一个人了。把这个人的数字记为J(N)，比如J(5)=3，J(10)=5，以此类推。规则

J(400)=______________ .

(提示:分析N=2m+r，其中0 ≤ r

四个。阅读程序写作成绩(***4题，每题8分，32分***)

1.# include & ltstdio.h & gt

int main()

{int i，p[5]，q[5]，x，y = 20

for(I = 0；我& lt=4;i++)

scanf("%d "，& ampp[I])；

q[0]=(p[0]+p[1])+(p[2]+p[3]+p[4])/7；

q[1]= p[0]+p[1]/((p[2]+p[3])/p[4])；

q[2]= p[0]* p[1]/p[2]；

q[3]= q[0]* q[1]；

q[4]= q[1]+q[2]+q[3]；

x =(q[0]+q[4]+2)-p[(q[3]+3)% 4]；

if(x & gt；10)

y+=(q[1]* 100-q[3])/(p[p[4]% 3]* 5)；

其他

y+= 20+(q[2]* 100-q[3])/(p[p[4]% 3]* 5)；

printf("%d，%d\n "，x，y)；

返回0；

}

/*注意:在这个例子中，给定的输入数据可以避免分母为0或者数组元素的下标越界。*/

输入:6 6 5 5 3

输出:_ _ _ _ _ _ _ _ _ _

2.# include & ltstdio.h & gt

void fun(int *a，int *b)

{ int * k；

k = a；a = b；b = k；

}

主( )

{int a=3，b=6，* x = & ampa，* y = & ampb；

fun(x，y)；

printf("No.1: %d，%d "，a，b)；

乐趣(& amp一，& ampb)；

printf(" 2号:%d，%d\n "，a，b)；

}

输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

3.#包含“math.h”

#包含“stdio.h”

主()

{ int a 1[51]= { 0 }；

int i，j，t，t2，n = 50

for(I = 2；我& lt= sqrt(n)；i++)

if(a1[i]==0)

{ T2 = n/I；

for(j = 2；j & lt= t2j++)a 1[I * j]= 1；

}

t = 0；

for(I = 2；我& lt= n；i++)

if(a1[i]==0)

{printf("%4d "，I)；t++；

if(t % 10 = = 0)printf(" \ n ")；

}

printf(" \ n ")；

}

输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

________________________________________

4.#包含“stdio.h”

char ch[]={'q '，' A '，' S '，' O '，' R '，' T '，' E '，' X '，' A '，' M '，' P '，' L '，' E ' }；

int n = 12；

void shift(int k，int n)

{ char v；

int j；

v = ch[k]；j = k+k；

while(j & lt；=n)

{ if((j & lt；n)& amp；& amp(ch[j]& lt；ch[j+1]))j++；

如果(v & ltch[j])

{ ch[j/2]= ch[j]；j * = 2；}

其他

返回；

ch[j/2]= v；

}

}

无效hpsrt(无效)

{ int k；

char tmp

for(k = n/2；k & gt0;k -)移位(k，n)；/*构建一个堆*/

printf(" no . 1:")；

for(k = 1；k & lt= n；k++)putchar(ch[k])；

putchar(' \ n ')；

for(k = n；k & gt0;k -)

{ tmp = ch[1]；ch[1]= ch[k]；ch[k]= tmp；

shift(1，k-1)；

}

}

主()

{ int k；

HP SRT()；

printf(" 2号:")；

for(k = 1；k & lt= n；k++)putchar(ch[k])；

putchar(' \ n ')；

}

输出:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

___________________________________________

动词 （verb的缩写）改进程序(前5个空格2分，后6个空格3分，* * * 28分)。

1.(格雷码)

格雷码是十进制数的二进制代码。编码顺序与对应十进制数的大小不一致。其特征在于:对于

两个相邻的十进制数和两个对应的格雷码之间只有一个二进制位差。另外，最大数量和最小数量之间只有一个

二进制位则不同。以一个4位二进制数为例，编码如下:

十进制数字格雷码

0 0000 8 1100

1 0001 9 1101

2 0011 10 1111

3 0010 11 1110

4 0110 12 1010

5 0111 13 1011

6 0101 14 1001

7 0100 15 1000

如果把每一个二进制位看成一个开关，一个数会变成另一个相邻的数，只需要换一个开关。因此，

格雷码广泛应用于信号处理、数模转换等领域。

以下程序的任务是输入数字n (n

输出m (***n位，数组gr[])对应的格雷码。

为了完成程序，你必须仔细分析上表中的规则，尤其是固定格雷码某一位的十进制数。

从0到1，或从1到0。

# include & ltstdio.h & gt

主()

{int bound=1，m，n，I，j，b，p，gr[15]；

printf("input n，m \ n ")；

scanf("%d%d "，& ampn & amp；m)；

for(I = 1；我& lt= n；i++)bound =①；

如果(m & lt0 | | m & gt=绑定)

{printf("数据错误！\ n ")；

② ;

}

b = 1；

for(I = 1；我& lt= n；i++)

{ p = 0；b = b * 2；

for(③；j & lt= m；j++)

如果(④)

p = 1-p；

gr[I]= p；

}

for(I = n；⑤ )

printf("%1d "，gr[I])；/*数字1出现在“%1d”中，而不是字母l */

printf(" \ n ")；

}

2.(连续邮资问题)某国发行了N种不同面额的邮票，规定每封信最多允许贴M张邮票。这里，

在一定的约束条件下，为了邮寄{1，2，3，…，maxvalue}连续整数集的所有邮费，并使maxvalue最大。

每枚邮票的面值如何设计？例如，当n=5，m=4时，面值设计为{1，3，11，15，32}，可以使

Maxvalue达到最大值70(换句话说，1到4张这些面额的邮票可以代表所有不超过70的邮费，但一张都没有。

方法表明邮费是71。但如果1到4枚其他面额的邮票能代表所有不超过K的邮资，则必须有k≤70)。

下面是用递归回溯法解决连续邮资问题的程序。数组x[1:n]表示n种不同的邮票面额，并指定每个元素。

素数是严格按下标递增的。数组bestx [1:n]存储最大化maxvalue的邮票面值(最优解)。

数组y[maxl]用于记录用当前选择的邮票面值x[1:i]可以投寄的各种邮资所需的最少邮票数量。请放了程

序言完成。

# include & ltstdio.h & gt

#定义NN 20

#定义maxint 30000

#define maxl 500 /*最高邮费*/

int n，m，bestx[NN]，x[NN]，y[maxl]，max value = 0；

无效结果()

{输出结果:最大值和最优解:bestx[1:n](略)

}

void回溯(int i，int r)

{ int j，k，z[maxl]；

for(j = 0；j & lt= ① ;j++)

if(y[j]& lt；m)

for(k = 1；k & lt= m-y[j]；k++)

if(y[j]+k & lt；=y[ ② ])

y[③]= y[j]+k；

while(y[r]& lt；maxint)r++；

如果(i & gtn)

{ if(r-1 & gt；最大值)

{ max value =④；

for(j = 1；j & lt= n；j++)

bestx[j]= x[j]；

}

返回；

}

for(k = 0；k & ltmaxlk++)

z[k]= y[k]；

for(j =⑤；j & lt= r；j++)

{ x[I]= j；

⑥ ;

for(k = 0；k & ltmaxlk++)

y[k]= z[k]；

}

}

void main()

{ int j；

printf("input n，m:\ n ")；

scanf("%d%d "，& ampn & amp；m)；

for(j = 1；j & ltmaxlj++)

y[j]= maxint；

y[0]= 0；x[0]= 0；x[1]= 1；

回溯(2，1)；

结果()；

}