《noip()第二十全国青少信息学奥林匹克联赛初赛试题及答案(提高组pascal).doc》由会员分享，可在线阅读，更多相关《noip()第二十全国青少信息学奥林匹克联赛初赛试题及答案(提高组pascal).doc（8页珍藏版）》请在三一办公上搜索。
1、第二十届全国青少年信息学奥林匹克联赛初赛提高组Pascal语言试题竞赛时间:2014年10月12日14:3016:30选手注意: 试题纸共有10页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。 不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料。一、单项选择题(共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项)1.以下哪个是面向对象的高级语言()。A. 汇编语言B. C+C. FORTRAND. Basic2.1TB代表的字节数量是()。A. 2的10次方B. 2的20次方C. 2的30次方D. 2的40次方3. 二进制数00100
2、100和00010101的和是()。A. 00101000B. 001010100C. 01000101D. 001110014. TCP协议属于哪一层协议()。A. 应用层B. 传输层C. 网络层D. 数据链路层5. 下列几个32位IP地址中，书写错误的是().A. 162.105.130.27B. 192.168.0.1C. 256.256.129.1D. 10.0.0.16. 在无向图中，所有顶点的度数之和是边数的()倍。A. 0.5B. 1C. 2D. 47. 对长度为n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为()。A. n/2B. (n+1)/
3、2C. (n-1)/2D. n/48. 编译器的主要功能是()。A. 将一种高级语言翻译成另一种高级语言B. 将源程序翻译成指令C. 将低级语言翻译成高级语言D. 将源程序重新组合9. 二进制数111.101所对应的十进制数是()。A. 5.625B. 5.5C 6.125D. 7.62510. 若有变量var a:integer；x，y:real；，且a:=7，x:=2.5，y:=4.7，则表达式x + a mod 3 * trunc(x + y) mod 2 div 4的值大约是()。A.2.500000B.2.750000C.3.500000D.0.00000011. 有以下结构体说明和
4、变量定义，如图所示，指针p、q、r分别指向一个链表中的三个连续结点。data nextdata nextdata nexttype ptr=node;pqr node=record data:integer; next:ptr; end;var p,q,r:ptr;现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是()。A. q.next:=r.next; p.next:=r; r.next:=q;B. p.next:=r; q.next:=r.next; r.next:=q;C. q.next:=r.next; r.next:=q; p.next:=r;D. r.
5、next:=q; q.next:=r.next; p.next:=r;12. 同时查找2n个数中的最大值和最小值，最少比较次数为()。A. 3(n-2)/2B. 4n-2C. 3n-2D. 2n-213. 设G是有6个结点的完全图要得到一棵生成树，需要从G中删去()条边。A. 6B. 9C. 10D. 1514. 以下时间复杂度不是O(n2)的排序方法是()。A. 插入排序B. 归并排序C. 冒泡排序D. 选择排序15. 以下程序段实现了找第二小元素的算法。输入是n个不等的数构成的数组S，输出S中第二小的数SecondMin。在最坏情况下，该算法需要做()次比较。if S1S2 then be
6、gin FirstMin:=S1; SecondMin:=S2; endelse begin FirstMin:=S2; SecondMin:=S1; end;for i:=3 to n dO if SiSecondMin then if Sidictindj+1 then begin tmp:=indj; indj:=indj+1; indj+1:=tmp; end; for i:=1 to n do rankindi:=i; for i:=1 to n do write(ranki, ); writeln; end.输入:7aaaababbbaaaaaacccaa输出:_4. const
7、SIZE=100; var alive:array1.SIZE of integer; n, m, num, i, j:integer; function next(num:integer):integer; begin repeat inc(num); if numn then num:=1; until alivenum0; exit(num); end; begin read(n, m); for i:=1 to n do alivei:=1; num:=1; for i:=1 to n do begin for j:=1 to m-1 do num:=next(num); write(
8、num, ); alivenum:=0; if in then num:=next(num); end; writeln; end.输入:11 3输出:_五、完善程序(每题14分，共计28分)1. (双栈模拟数组)只使用两个栈结构stack1和stack2，模拟对数组的随机读取。作为栈结构，stack1和stack2只能访问栈顶(最后一个有效元素)。栈顶指针top1和top2均指向栈顶元素的下一个位置。输入第一行包含两个整数，分别是数组长度n和访问次数m，中间用单个空格隔开。第二行包含n个整数，依次给出数组各项(数组下标从0到n-1)。第三行包含m个整数，需要访问的数组F标。对于每次访问，输出
9、对应的数组元素。(前两空每空2.5分，其余每空3分，共14分) const SIZE=100; var stack1, stack2:array0.SIZEof integer; top1, top2:integer; n, m, i, j:integer; procedure clearStack(); var i:integer; begin for i:=top1 to SIZE do stack1i:=0; for i:=top2 to SIZE do stack2i:=0; end; begin read(n,m); for i:=0 to n-1 do read(stack1i);
10、 top1:=_; top2:=_; for j:=0 to m-1 do begin read(i); while (itop11)do begin dec(top2); _; inc(top1); end; clearStack(); writeln(stack1_); end;end.2. (最大子矩阵和)给出m行n列的整数矩阵，求最大的子矩阵和(子矩阵不能为空)。输入第一行包含两个整数m和n，即矩阵的行数和列数。之后m行，每行n个整数，描述整个矩阵。程序最终输出最大的子矩阵和。(第一空2分，其余3分，共14分) const SIZE=100; var matrix:array1.SIZ
11、E,1.SIZE of integer; rowsum:array1.SIZE,0.SIZE of integer; /rowsumI,j记录前i行前j个数的和 m, n, i, j, first, last, area, ans:integer; begin read(m,n); for i:=1 to m do for j:=1 to n do read(matrixi,j); ans:=matrix_; for i:=1 to m do _; for i:=1 to m do for j:=1 to n do rowsumi,j:=_; for first:=1 to n do for last:=first to n do begin _; for i:=1 to m do begin area:=area + _; if (areaans) then ans:=area; if (area0) then area:=0; end; end; writeln(ans); end.
