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

 (((A∧B)∨C)∧D∧E)

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

12.  (2010)16 + (32)8的结果是（    ）。

A. (8234)10                  B. (202A)16

C. (100000000110)2       D. (2042)16

13. 设栈S的初始状态为空，元素a, b, c, d, e 依次入栈，以下出栈序列不可能出现的有（    ）。

A. a, b, c, e, d             B. b, c, a, e, d

C. a, e, c, b, d             D. d, c, e, b, a

14. 已知 6 个结点的二叉树的先根遍历是 1 2 3 4 5 6（数字为结点的编号，以下同），后根遍历是

3 2 5 6 4 1，则该二叉树的可能的中根遍历是（       ）

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

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

15. 在下列各数据库系统软件中，以关系型数据库为主体结构的是（    ）。

A. ACCESS                B. SQL Server

C. Oracle                D. Foxpro

16.在下列各软件中，属于 NOIP 竞赛（复赛）推荐使用的语言环境有（        ）。

A. gcc/g++               B. Turbo Pascal

C. Turbo C               D. free pascal

17. 以下断电之后将不能保存数据的有（      ）。

A. 硬盘      B. ROM       C. 显存       D. RAM

18. 在下列关于计算机语言的说法中，正确的有（       ）。

A. Pascal和C都是编译执行的高级语言

B. 高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上

C. C++是历史上的第一个支持面向对象的计算机语言

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

19. 在下列关于计算机算法的说法中，正确的有（       ）。由OIFans.cn收集

A. 一个正确的算法至少要有一个输入

B. 算法的改进，在很大程度上推动了计算机科学与技术的进步

C. 判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间

D. 目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法

20. 在下列关于青少年信息学竞赛的说法中，你赞成的是（        ）（本题不回答为0分，答题一律满分）。

A. 举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学 与技术人才奠定良好的基础

B. 如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了

C. 准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力

D. 为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有 严谨求实的作风，既要努力奋进，又要胜不骄败不馁

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

1．将 2006 个人分成若干不相交的子集，每个子集至少有 3 个人，并且：

（1）在每个子集中，没有人认识该子集的所有人。

（2）同一子集的任何 3 个人中，至少有 2 个人互不认识。

（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。 则满足上述条件的子集最多能有                                        个？

2．将边长为 n 的正三角形每边 n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形， 我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最 下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同 一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是  n=5 时一条通路的例 子）。设 n=10，则该正三角形的不同的通路的总数为_          __。

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

1. #include <iostream.h>

void main()

{int i,u[4],v[4],x,y=10;

for(i=0;i<=3;i++)

cin >>u[i]; v[0]=(u[0]+u[1]+u[2]+u[3])/7; v[1]=u[0]/((u[1]-u[2])/u[3]); v[2]=u[0]*u[1]/u[2]*u[3]; v[3]=v[0]*v[1];

x=(v[0]+v[1]+2)-u[(v[3]+3)%4];

if(x>10)

y+= (v[2]*100-v[3])/(u[u[0]%3]*5);

else

y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5);

cout <<x<<","<<y<<endl;

} //本例中，给定的输入数据可以避免分母为 0 或下标越界。 输入：9 3 9 4

输出：              

2.#include <iostream.h>

void main()

{int i,j,m[]={2,3,5,7,13};

long t;

for (i=0;i<=4;i++)

{t=1;

for(j=1;j<m[i];j++)     t*=2;

cout <<(t*2-1)*t<<"     ";

}

cout <<endl;

}由OIFans.cn收集

输出:_____                 

3. #include "iostream.h"

#define N  7

int fun1(char s[],char a,int n)

{int j;

j=n;

while(a<s[j] && j>0) j--;

return j;

}

int fun2(char s[],char a,int n)

{int j;

j=1;

while(a>s[j] && j<=n) j++;

return j;

}

void main()

{char s[N+1];

int k,p; for(k=1;k<=N;k++) s[k]='A'+2*k+1; p=fun1(s,'M',N);

cout <<p+fun2(s,'M',N)<<endl;

}

输出：            

4. #include <iostream.h>

#include <iomanip.h>

void digit(long n,long m)

{if(m>0)

cout <<setw(2)<<n%10;

if(m>1)

digit(n/10,m/10);

cout <<setw(2)<<n%10;

}

void main()

{long x,x2;

cout <<"Input a number:"<<endl;

cin >>x;

x2=1;

while(x2<x)  x2*=10;

x2/=10; digit(x,x2); cout <<endl;

}

输入：9734526

输出：                               

五．完善程序  (前 5 空，每空 2 分，后 6 空，每空 3 分，共 28 分)

1．（选排列）下面程序的功能是利用递归方法生成从 1 到 n(n<10)的 n 个数中取 k(1<=k<=n)个数的 全部可能的排列（不一定按升序输出）。例如，当 n=3，k=2 时，应该输出（每行输出 5 个排列）：由OIFans.cn收集

12 13  21  23 32

31

程序：

#include <iostream.h>

#include <iomanip.h>

int n,k,a[10];

long count=0;

void perm2(int j)

{int i,p,t;

if(   ①   )

{for(i=k;i<=n;i++)

{count++;

t=a[k]; a[k]=a[i]; a[i]=t;

for(   ②   )

cout<<setw(1)<<a[p];

cout <<"  "; t=a[k];a[k]=a[i];a[i]=t; if(count%5==0) cout <<endl;

}

return;

}

for(i=j;i<=n;i++)

{t=a[j];a[j]=a[i];a[i]=t;

③   ;

t=a[j];    ④   ;

}

}

void main()

{int i;

cout <<"nEntry n,k (k<=n)n"<<endl;

cin>>n>>k;

for(i=1;i<=n;i++)  a[i]=i;

⑤   ;

cout <<endl;

}

2．（TSP 问题的交叉算子）TSP 问题(Traveling Salesman Problem)描述如下：给定 n 个城 市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环 路，每个城市恰好经过一次，求使总代价达到最小的一条环路。

遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法 之一是 1 到 n 这 n 个数字的一个排列，每个数字为一个城市的编号。例如当 n=5 时，“3 4 2 1 5” 表示该方案实施的路线为 3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两 个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：

(1)选定中间一段作为互换段，该段的起止下标为 t1，t2，随机生成 t1，t2 后，互换两段。

(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：

(2.1) 将两个互换段中，共同的数字标记为 0，表示已处理完。

(2.2) 将两个互换段中其余数字标记为 1，按顺序将互换段外重复的数字进行替换。 例如：n=12，两个个体分别是：

a1: 1 3 5 4  * 2  6 7  9  * 10 12 8 11

a2: 3 2 1 12 * 6 7 10 11 * 8  5  4  9

t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从 1 开始，互换后有：

a1: 1 3 5 4  * 6 7 10 11  * 10 12 8 11

a2: 3 2 1 12 * 2 6  7  9  *  8  5  4  9

然后，将数字 6,7 对应的项标记为 0，星号内数字 2,9,10,11 对应的项标记为 1，并且按顺序对 应关系为:10<->2，11<->9。于是，将 a1[9]=10 替换为 a1[9]=2，将 a2[2]=2 替换为 a2[2]=10， 类似再做第 2 组替换。这样处理后，就得到了两个新个体：

a1: 1  3 5  4      6 7 10 11     2 12  8  9

a2: 3 10 1 12  2 6  7        9   8  5  4  11

（3）输出两个新个体的编码。 程序：

#include <iostream.h>

#include <stdlib.h>

#define N 20

int a1[N],a2[N],kz1[N],kz2[N],n;

int rand1(int k)

{int t=0;

while(t<2|| t>k) t=(int)((double)rand()/RAND_MAX*k); return t;

}

void read1(int a[],int m)

{读入数组元素 a[1]至 a[m]，a[0]=0，略。}由OIFans.cn收集

void wrt1(int a[],int m)

{输出数组元素 a[1]至 a[m]，略。}

void cross(int a1[], int a2[],int t1, int t2, int n)

{int i,j,t,kj;

for(i=t1; i<=t2; i++)

{t=a1[i];    ①    ；

} for(i=1;i<=n;i++) if(i<t1 || i>t2)

kz1[i]=kz2[i]=-1;

else

②   ;

for(i=t1;i<=t2;i++) for(j=t1;j<=t2;j++) if(a1[i]==a2[j])

{   ③   ;   break;

}

for(i=t1; i<=t2; i++)

if(kz1[i]==1)

{for(j=t1;j<=t2;j++)

if(kz2[j]==1)

{kj=j; break;

} for(j=1;j<=n;j++) if(  ④  )

{a1[j]=a2[kj];break;

}

for(j=1;j<=n;j++)

if(   ⑤   )

{a2[j]=a1[i]; break;

}

kz1[i]=kz2[kj]=0;

}

}

void main()

{int k,t1,t2;

cout <<"input (n>5):"<<endl;  cin>>n;

cout <<"input array 1 ("<<n<<" numbers):"<<endl;  read1(a1,n); cout <<"input array 2 ("<<n<<" numbers):"<<endl;  read1(a2,n); t1=rand1(n-1);

do

{t2=rand1(n-1);

}while(t1==t2);

if(t1>t2)

{k=t1; t1=t2; t2=k;

}

⑥   ;

wrt1(a1,n);  wrt1(a2,n);

}