2013信息学竞赛初赛模拟试题(二)(pascal)

1、冲刺 NOIP初赛模拟试题与解析（ 提高组 Pascal 语言 二小时完成 ）一、单项选择题 （共 10题，每题 1.5分，共计 15分，每题有且仅有一个正确答案）。1、关于图灵机下面的说法哪个是正确的( )：A)图灵机是世界上最早的电子计算机。B)由于大量使用磁带操作，图灵机运行速度很慢。C)图灵机只是一个理论上的计算模型。D)图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。2、某计算机的硬盘容量是 1T，这里 1T=( )字节.A)1000*1000*1000*1000B)1024*1024*1024C) 1024*1024*1024*1024D)1000*1024*10

2、24*10243、中缀表达式 A-(B+C/D)*E的后缀表达式是( )。A)AB-C+D/E*B) ABC+D/-E*C)ABCD/E*+-D)ABCD/+E*-41.100,1.100的二维数组A,每个元素Ai,j存储时占用两个字节,将 A数组按行优先方式存入从 SA开始的连续存储单元中,则元素 A66,65存储的结束地址是( )。A)SA+13130B)SA+13129C)SA+6565D)SA+65645、计算机辅助教学的简写是( )。A)CAI B)CAMC)CAD D)CAS6、二叉树是重要的数据结构，5个点的不同的二叉树有( )个。A)30 B)40C)42 D)467、(101

3、.101)2=( )10A)5.625 B)5.5C)6.125 D)3.5258 Sa,b,c,d,e,f b,d,c,f,e,a那么栈容量至少应该是( )。A)5 B)4 C)3 D)29、有一棵树 T=(K,R)，其中 K=A,B,C,D,E,F,G,H,I,J,R=r，r=,那么它按后根次序周游得到的结点序列是( )。A)ABEFCGHDIJB)ABCDEFGIJHC)EFBHGCIJDAD)EBFACGHIDJ10、在数据结构中链表是(A)顺序存储的线性表结构B)非顺序存储的线性表结构C)顺序存储的非线性表结构)。D)非顺序存储的非线性表结构 E) 特殊的树结构二、不定项选择题（共

4、10题，每题 1.5分，共计 15分，每题正确答案的个数不少于 1。多选或少选均不得分）。1、在 TCP/IP协议中下列服务属于应用层的是( )。A)WWWB)FTPD)TCPC)SMTP2、下列关于十进制数-100的正确说法是( )。A)原码为 11100100BC)补码为 64HB)反码为 9BHD)补码为 9CH3、若 A=true,B=false,C=true,D=false,以下逻辑运算表达式真的有()。A)(AB)V(CDVA)B)(AB)VC) BC)(BVCVD)VDAD)A(DVC) B4、以下是关于排序的说法正确的是()。A)选择排序、冒泡排序、插入排序是稳定的B)希尔排序

5、、快速排序、堆排序的时间复杂度为 O(nlog2n)C)线形排序、二路归并排序的空间复杂度为 O(n)D)希尔排序、快速排序、堆排序、归并排序是不稳定的5、在带尾指针（链表指针 clist指向尾结点）的非空循环单链表中每个结点都以 next字段的指针指向下一个节点。假定其中已经有了 2个以上的结点。下面哪些说法是正确的()。A)如果 p指向一个待插入的新结点，在头部插入一个元素的语句序列为：p.next:=clist.next;clist.next:=p;B)如果 p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：p.next:=clist;clist.next:=p;C)在头部删除一

6、个结点的语句序列为：p:=clist.next;clist.next:=clist.next.next;dispose(p);D)在尾部删除一个结点的语句序列为：p:=clist;clist:=clist.next;dispose(p);)。6、下列是关于数据结构的说法正确的是(A)栈的插入和删除只能在栈底进行B)线性表的线性存储结构优于链式存储结构C)队列是一个先进先出的线性表D)队列是只能在一端插入，另一端删除的线性表7、以下关于图的正确说法是( )。A)所有顶点的度数之和等于边数的 2倍B)在有向图中顶点的入度之和等于出度之和C)任意一个图一定有偶数个奇点D)任意一个图一定有奇数个偶点8

7、、下列( )是 64位处理器。A)Intel ItaniumB)Intel Pentium IIIC)AMD Athlon64D)IBM Power 59、下列 IP地址中错误的是( )。A)202.300.12.4 B)C)100:128:35:91 D)111-102-35-2110、关于二叉树的正确说法是( )。A)满二叉树一定是完全二叉树B)深度为 h的二叉树最多有 2-1个结点(h=1)，最少有 h个结点hC)对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2的结点总数为 N2，则 N0=N2+1D)在二叉树中，第 i层的结点总数不超过 2 ；i-1三.问题求解（共 2题，每空

8、 5分，共计 10分）1、将 n个不同颜色的球放入 k个无标记的盒子中(n=k，且盒子不允许为空)的方案数为 s(n,k)n=4,k=3时,S(n,k)=6 n=6,k=3时，S(n,k)=_。2、在圆周上有 N个点(N=6)，在任意两个点之间连一条弦，假设任何 3条弦在写出三角形总数的表达式而无需化简）？ N=6 4个三角形从某种意义上说具有一定的代表性。四、阅读程序写结果（共 4题，每题 8分，共计 32分）1.阅读下面一段程序，写出运行结果varm,n,s:longint;procedure p1(n:longint);beginif n0 thenbeginp1(n div 2);s:

9、=(s*2+n mod 2*m)mod 1023;endend;beginreadln(m,n);s:=0;p1(n);writeln(s);end.输入：2010 5871输出：2.阅读下面一段程序，写出运行结果vara:array1.100of longint;i,j,k,m,n,left,right,temp:longint;beginreadln(n,m);for i:=1 to n do read(ai);left:=1;right:=n;while leftright dobegink:=am;i:=left;j:=right;repeatwhile(kai)do i:=i+1;i

10、f(ij;if jm then right:=j;end;write(am);end.输入：14 894 32 40 90 99 80 46 21 69 28 64 73 85 54输出：3.阅读下面一段程序，写出运行结果vars1,s2:string;i,j,k,n:longint;a:array0.2000,0.2000 of longint;function min(w,x,y:longint):longint;var m:longint;beginm:=w;if xm then m:=x;if yn then n:=length(s2);for i:=0 to n dobeginai,

11、0:=k*i;a0,i:=k*i;end;for i:=1 to n dofor j:=1 to n doai,j:=min(ai-1,j+k,ai,j-1+k,ai-1,j-1+abs(ord(s1i)-ord(s2j);writeln(alength(s1),length(s2);end.输入：2noipctsc输出：4. 阅读下面一段程序，写出运行结果const maxn=10000;vari,j,k,n,r,p,g:longint;a:array1.maxnof longint;function gcd(m,n:longint):longint;var r:longint;beginw

12、hile n0 dobeginr:=m mod n;m:=n;n:=r;end;gcd:=mend;beginreadln(n,r);for i:=1 to n-r do ai:=n-i+1;for i:=2 to r dobegink:=i;for j:=1 to n-r doif gcd(k,aj)1 thenbeging:=gcd(k,aj);k:=k div g;aj:=aj div g;if k=1 then break;endend;p:=1;g:=0;for i:=1 to n-r dobeginp:=p*ai;while p mod 5=0 dobeginp:=p div 5;

13、g:=g+1;end;p:=p mod 5end;writeln(g);end.输入：2010 202输出：五、完善程序（前 5空，每空 2分，后 6空，每空 3分，共 28分）1.最大子矩阵：求元素之和最大的子方阵，在m*n(m,n=20)的正整数数字方阵 p*q的子阵(1=p=m,1=qmax thenbegin;p1:=i;q1:=j;end;end;for i:=p1 tobegin dofor j:=q1 to dowrite(ai,j, );writeln;end;end.2.开。任意两个火车站有且只有一条路径，每个火车站最多有 50个和它相连接的火车站。 告诉你每个火车站的利润，问你可以获得的最大利润为多