其中TP、TB、DOS、D11、D31都是子目录名。 设当前命令提示符为 A:\TB> ,请写出完成如下操作的DOS命令: ①在DOS运行中,没有执行过PATH命令,现要用DOS子目录中FORMAT命令,对插入在B驱动器(5.25英寸高密)中的360KB软盘进行格式化工作,请写出相应的操作命令。 ② 交换F2.TXT与F3.DOC两个文件的内容,要求使用的命令不得超过三条; 2.请用等号或不等号联接表示下列不同进位制数值的大小。 例如: (3)10 < (4)4 = (100)2 < (A)16 其中圆括号外右下角的下标,表示圆括号内数的进位制。 (98.375)10 (142.3)8 (58.5)16 (1011000.0101)2 3.阅读程序,写出程序段运行后数组元素 a1 , a2 , …, a11 中的值。 a[1]:=1; a[2]:=1; k:=1; repeat a[k+2]:=1; for i:=k+1 downto 2 do a[i]:=a[i]+a[i-1]; k:=k+1; until k>=10; 4. 已知: ack(m,n) 函数的计算公式如下: n+1 m=0 ack (m , n) = ack (m-1 , 1) n=0 ack (m-1 , ack ( m , n-1) ) m≠0 且 n≠0 请计算: ack ( 1 , 3 )、ack ( 2 , 4 )、ack ( 3 , 3 )、ack ( 3 , 4 ) 的值 5. 有N×N个数据组成如下方阵: 并已知:AIJ = AJI 现将A11,A12,…,A1N,A22,A23,…,A2N,A33,A34,…,A3N,…,ANN 存储在一维数组A[1],A[2],…,A[ N (N+1) / 2 ]中。 试问:任给I , J 怎样求出K来,使得A[ K]的值正好是AIJ,请写出由I , J计算K的表达式。 6. 已知: A1 , A2 , … , A81 共有81个数,其中只有一个数比其他数大,要用最少的比较运算次数,把这个值大的数找出来(假设两个数比较一次能决定出大于、小于或等于这三种情况)请将以下算法补充完整。 第一步: s1=A1 + A2 + … + A27 s2=A28 + A29 + … + A54 第一次比较 ( s1 , s2 ): s1 > s2 取K = 0 s1 < s2 取K = 27 s1 = s2 取K = 54 第二步: s1=AK+1 + AK+2 + … + AK+9 s2=AK+10 + AK+11 + … + AK+18 第二次比较 ( s1 , s2 ): s1 > s2 取K = ① s1 < s2 取K = ② s1 = s2 取K = ③ 第三步: s1=AK+1 + AK+2 + AK+3 s2=AK+4 + AK+5 + AK+6 第三次比较 ( s1 , s2 ): s1 > s2 取K = ④ s1 < s2 取K = ⑤ s1 = s2 取K = ⑥ 第四步: s1=AK+1 s2=AK+2 第四次比较 ( s1 , s2 ): s1 > s2 ⑦ 为最大数 s1 < s2 ⑧ 为最大数 s1 = s2 ⑨ 为最大数 7. 下面是一个利用完全二叉树特性,用顺序表来存储的一棵二叉树,结点数据为字符型(结点层次号从小到大,同一层从左到右顺序存储,#表示空结点,@表示存储数据结束)。现要求画出对应该存储结构的二叉树示意图。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C # # D E # # # # # G F @ 二、根据题目要求,补充完善以下程序: 1.[ [题 目]: 积木游戏:设有n个小木块排成一排,如下图: □ □ □ …… …… □ 游戏开始时,每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种(约定: 0表示红色,1表示黄色,2表示蓝色)。要求通过翻看与交换方式对小木块重新排列(翻看的规则为每个小木块只能看一次),最终成为下面的形状: □ □ □ …… □ □ □ □ …… □ □ □ □ …… □ 红 蓝 黄 即相同颜色的木块排列在一起,设计一个翻看与交换的方案,使得用最少的交换次数实现上面的要求。 [算法描述]:翻看小木块时,可以从两端进行。例如,设中间状态如下: □ □ □…… □ □ □…… □ □ □…… □ □ □…… □ 红 未翻过 蓝 黄 此时,可以从两个方向看,即从a或b处开始: 1.若看a则有三种可能性: 为红色,则不用交换 为蓝色,交换一次,即a与b交换 为黄色,交换两次,即c与b交换一次,然后a与c再交换一次 此时,平均交换次数为1 2.若看b也有三种可能性: 为蓝色,则不用交换 为红色,交换一次,即b与a交换 为黄色,交换一次,即b与c交换 此时,平均交换次数为2/3 由此可见,从b处翻看直到游戏结束,次数最少符合题目要求。 [程 序]: program exp1 (input , output); const n = 20; var i , tem , r , b , y : integer; a : array [ 1 . . n ] of 0 . . 2; begin for i := 1 to n do read (a[ i ]); r := 1; ① ; y := n; while ② do if ③ then begin tem := a[ r ]; a[ r ]:= a[ b ]; a[ b ] := tem; r := r + 1 end else if ④ then begin tem := a[ b ]; a[ b ] := a[ y ]; a[ y ]:= tem; ⑤ ; ⑥ ; end else b := b - 1; for i := 1 to n do write ( a[ i ] : 3 ) end. 2.[题 目]: 四色问题。设有下列形状的图形:有8个区域,其编号为1,2,…,n。 (n = 8) 图形中各区域的相邻关系用上边的邻接矩阵表示:1——相邻,0——不相邻。 [程序要求]:将上面图形的每一个部分涂上红(1),黄(2),蓝(3),绿(4)四种颜色之一,要求相邻的部分不同色。 [算法描述]:用数组 r : array [ 1 .. n , 1 .. n ] of 0 .. 1 ; 表示邻接矩阵 s : array [ 1 .. n ] of integer ; 表示涂的元素。 采用回溯的方法,首先给第一个图形涂上红色(1),然后在下面的图形中依次涂上其它颜色,当有矛盾时回溯解决。 [程 序]: const n = 8; var i , j , k : integer; r : array [ 1 .. n , 1 .. n ] of 0 .. 1; s : array [ 1 .. n ] of integer; begin for i := 1 to n do begin for j:=1 to n do read ( r [ i , j ]); readln; end; ① ; i := 2; j := 1; while i < = n do begin while ( j < =4 ) and (i < = n) do begin k := 1; while ② do k := k + 1; if k < i then ③ else begin ④ ; i := i + 1; j := 1; end; end; if j > 4 then begin i := i - 1; ⑤ end; end; for i := 1 to n do writeln ( i , ‘→’ , s[ i ]) end. 3.[问 题]: 多项式加法运算:一个仅含有x的多项式可以用下列的方式表示: (系数,指数), (系数,指数),……,(0,0) 。其中 (0 , 0) 作为结束标志。 例如: P ( x ) = 4x6– 3x3 + 2x2–1 可表示为:(4 , 6),(-3 , 3),(2 , 2),(-1 , 0),(0 , 0) Q ( x ) = x4–x +1 可表示为:(1 , 4),(-1 , 1),(1 , 0),(0 , 0) 当用上面的方式给出2个多项式之后,程序对这两个多项式进行加法运算,结果也用上面的方式给出。 例如:上面的 P( x ) 和 Q ( x ) 相加的结果为: 4x6 + x4– 3x3 + 2x2–x 表示结果为: (4 , 6),(1 , 4),(-3 , 3),(2 , 2),(-1 , 1),(0 , 0) [算法描述]:多项式可用数组 p : array [ 1 .. n , 1 .. 2 ] of integer 表示。 分别以p1表示p,p2表示q,p3表示结果。处理的过程为将p赋值到p3,然后逐项检查q,当发现有相同的方次时,进行系数相加;当发现没有相同方次时,插入到p3中去。 [程 序]: var x , y , i , i1 , j , j1 , j2 : integer; p1 , p2 , p3 : array [ 1 .. 20 , 1 .. 2 ] of integer; begin j1:= 0; write ( ‘ Input P (x) =’); read ( x , y ); while (x <>0) or (y<>0) do begin j1:= j1+1; p1 [ j1, 1 ]:= x; p1 [ j1, 2 ]:= y; read ( x , y ) ; end; j1:= j1+1; p1[ j1 , 1 ]:= 0; p1[ j1 , 2 ] := 0; write (‘ Input Q ( x ) = ’ ); read (x , y); j2 := 0; while (x <>0) or (y<>0) do begin j2 := j2+1; p2[ j2 , 1 ] :=x; p2[ j2 , 2 ]:= y; read (x , y); end; j2 := j2+1; p2[ j2 , 1 ] := 0; p2[ j2 , 2 ]:= 0; for i := 1 to j1 do begin p3[ i , 1 ] := p1[ i , 1 ]; p3[ i , 2 ] := p1[ i , 2 ] end; i := 1; while ① do begin if ② then begin for j := j1 downto 1 do begin p3 [ j+1 , 1 ] := p3 [ j , 1 ]; p3 [ j+1 , 2 ] := p3 [ j , 2 ] end p3 [ i , 1]:= p2[ i , 1]; p3[ i , 2 ]:= p2[ i , 2 ]; j1:= j1+1 end else begin i1:=1; while p2[ i , 2 ] < p3[ i1 , 2 ] do ③ ; if p2[ i , 2 ] = p3[ i1 , 2 ] then p3[ i1 , 2 ] := ④ else begin for j := j1 downto i1 do begin p3[ j+1 , 1 ]:= p3[ j , 1 ]; p3[ j+1 , 2 ]:= p3[ j , 2 ] end; p3[ i1 , 1 ]:= p[ i , 1 ]; p3[ i1 , 2 ]:= p3[ i , 2 ]; ⑤ ; end; end; {if} i := i + 1; end; {while} for j := 1 to j1-2 do write ( ‘ ( ’ , p3[ j , 1 ] , ‘ , ’ , p3[ j , 2 ] , ‘ ) ,’ ); writeln ( ‘ ( ’ , p3[ j+1 , 1 ], ‘ , ’ , p3[ j+1 , 2 ], ‘ )’ ); end. R O O T A11 A12 A13 …… A1N A21 A22 A23 …… A2N A31 A32 A33 …… A3N …… …… AN1 AN2 AN3 …… ANN a b c 8 7 6 5 2 3 4 1 1 2 3 4 5 6 7 8 1 0 1 0 0 0 0 1 1 2 1 0 1 0 0 1 1 0 3 0 1 0 1 0 1 0 0 4 0 0 1 0 1 1 0 0 5 0 0 0 1 0 1 0 0 6 0 1 1 1 1 0 1 0 7 1 1 0 0 0 1 0 1 8 1 0 0 0 0 0 1 0 2-2第二届全国青少年信息学(计算机)奥林匹克竞赛 分区联赛初赛(高中组)答案 一、基础知识部分 (共39分) (1) ① A:\TB> CD.. { 2 % } A:\ CD DOS A:\DOS > FORMAT B:/s/4 (/s是将磁盘格式成系统盘,/4表示进行低密度格式化) ② A:\TB> COPY A:\TP\D11\F2.TXT A:\DOS\D31\HH.DOC {3 % } A:\TB> COPY A:\D0S\D31\F3.DOC A:\TP\D11\F2.TXT A:\TB> REN A:\DOS\D31\HH.DOC F3.DOC (2) (98.375)10 = (142.3)8 > (58.5)16 > (1011000.0101)2 {3 % } (3) {6 % } a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 1 9 36 84 126 126 84 36 9 1 1 (4) ack ( 1 , 3 ) =5 ack ( 2 , 4 ) =11 {4 % } ack ( 3 , 3 ) =61 ack ( 3 , 4 ) =125 (5) K = I (I-1)/2+J {5 % } (6) ① K ② K+9 ③ K+18 ④ K ⑤ K+3 ⑥ K+6 ⑦ AK+1 ⑧ AK+2 ⑨ AK+3 {9 % } (7)二叉树示意图: {7% } 二、根据题目要求,补充完善以下伪代码程序 ( 共61分) (1) { 3+4+3+3+4+4 =21% } ① b:=n ② b>=r ③ a[b]=0 ④ a[b]=1 ⑤ b:=b-1 ⑥ y:=y-1 (2) { 4+4+4+4+4 =20% } ① s[1]:=1 ② (kr[i,k]<>j) 或 ( kj)or( r[i,k]<>1)) ③ j:=j+1; ④ s[i]:=j ⑤ j:=s[i]+1 (3){ 4+4+4+4+4 =20% } ① p2[i,1]<>0 ② p2[i,2]>p3[1,2] ③ i1:=i1+1 ④ p3[i1,1]+p2[i,1] ⑤ j1:=j1+1 E D G F C A B ― 2 ―第十五届全国青少年信息学奥林匹克联赛初赛试题 ( 提高组 Pascal语言 二小时完成 ) ● ● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 单项选择题 (共10题,每题1.5分,共计15分。每题有且仅有一个正确答案。) 1、关于图灵机下面的说法哪个是正确的: A) 图灵机是世界上最早的电子计算机。 B) 由于大量使用磁带操作,图灵机运行速度很慢。 C) 图灵机只是一个理论上的计算模型。 D) 图灵机是英国人图灵发明的,在二战中为破译德军的密码发挥了重要作用。 2、关于BIOS下面的说法哪个是正确的: A) BIOS是计算机基本输入输出系统软件的简称。 B) BIOS里包含了键盘、鼠标、声卡、图形界面显器等常用输入输出设备的驱动程序。 C) BIOS一般由操作系统厂商来开发完成。 D) BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。 3、已知大写字母A的ASCII编码为65(十进制),则大写字母J的 十六进制 ASCII编码为: A) 48 B) 49 C) 50 D) 以上都不是 4、在字长为16位的系统环境下,一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是: A) 19 B) -19 C) 18 D) -18 5、一个包含n个分支结点(非叶结点)的非空满k叉树,k>=1,它的叶结点数目为: A) nk + 1 B) nk-1 C) (k+1)n-1 D. (k-1)n+1 6. 表达式a (b+c)-d的后缀表达式是: A) abcd +- B) abc+ d- C) abc +d- D) -+ abcd 7、最优前缀编码,也称Huffman编码。这种编码组合的特点是对于较频繁使用的元素给与较短的唯一编码,以提高通讯的效率。下面编码组合哪一组不是合法的前缀编码。 A)(00,01,10,11) B)(0,1,00,11) C)(0,10,110,111) D)(1,01,000,001) 8、快速排序平均情况和最坏情况下的算法时间复杂度分别为: A) 平均情况 O(nlog2n),最坏情况O(n2) B) 平均情况 O(n), 最坏情况O(n2) C) 平均情况 O(n), 最坏情况O(nlog2n) D) 平均情况 O(log2n), 最坏情况O(n2) 9、左图给出了一个加权无向图,从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为:A) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V5 10、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源,请问全国信息学奥林匹克官方网站的网址是: A) http://www./ B) http://www.noi.org/ C) http://www./ D) http://www./ 二. 不定项选择题 (共10题,每题1.5分,共计15分。每题正确答案的个数不少于1。多选或少选均不得分)。 1、关于CPU下面哪些说法是正确的: A) CPU全称为中央处理器(或中央处理单元)。 B) CPU能直接运行机器语言。 C) CPU最早是由Intel公司发明的。 D) 同样主频下,32位的CPU比16位的CPU运行速度快一倍。 2、关于计算机内存下面的说法哪些是正确的: A) 随机存储器(RAM)的意思是当程序运行时,每次具体分配给程序的内存位置是随机而不确定的。 B) 一般的个人计算机在同一时刻只能存/取一个特定的内存单元。 C) 计算机内存严格说来包括主存(memory)、高速缓存(cache)和寄存器(register)三个部分。 D) 1MB内存通常是指1024 1024字节大小的内存。 3、关于操作系统下面说法哪些是正确的: A. 多任务操作系统专用于多核心或多个CPU架构的计算机系统的管理。 B. 在操作系统的管理下,一个完整的程序在运行过程中可以被部分存放在内存中。 C. 分时系统让多个用户可以共享一台主机的运算能力,为保证每个用户都得到及时的响应通常会采用时间片轮转调度的策略。 D. 为了方便上层应用程序的开发,操作系统都是免费开源的。 4、关于计算机网络,下面的说法哪些是正确的: A) 网络协议之所以有很多层主要是由于新技术需要兼容过去老的实现方案。 B) 新一代互联网使用的IPv6标准是IPv5标准的升级与补充。 C) TCP/IP是互联网的基础协议簇,包含有TCP和IP等网络与传输层的通讯协议。 D) 互联网上每一台入网主机通常都需要使用一个唯一的IP地址,否则就必须注册一个固定的域名来标明其地址。 5、关于HTML下面哪些说法是正确的: A) HTML全称超文本标记语言,实现了文本、图形、声音乃至视频信息的统一编码。 B) HTML不单包含有网页内容信息的描述,同时也包含对网页格式信息的定义。 C) 网页上的超链接只能指向外部的网络资源,本网站网页间的联系通过设置标签来实现。 D) 点击网页上的超链接从本质上就是按照该链接所隐含的统一资源定位符(URL)请求网络资源或网络服务。 6、若3个顶点的无权图G的邻接矩阵用数组存储为{{0,1,1},{1,0,1},{0,1,0}},假定在具体存储中顶点依次为: v1,v2,v3 关于该图,下面的说法哪些是正确的: A) 该图是有向图。 B) 该图是强连通的。 C) 该图所有顶点的入度之和减所有顶点的出度之和等于1。 D) 从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。 7、在带尾指针(链表指针clist指向尾结点)的非空循环单链表中每个结点都以next字段的指针指向下一个节点。假定其中已经有2个以上的结点。下面哪些说法是正确的: A) 如果p指向一个待插入的新结点,在头部插入一个元素的语句序列为: p^.next:= clist^.next; clist^.next:= p; B) 如果p指向一个待插入的新结点,在尾部插入一个元素的语句序列为: p^.next:= clist; clist^.next:= p; C) 在头部删除一个结点的语句序列为: p:= clist^.next; clist^.next:= clist^.next^.next; dispose(p); D) 在尾部删除一个结点的语句序列为。 p:= clist; clist:= clist ^.next; dispose(p); 8、散列表的地址区间为0-10,散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突,并将关键字序列26,25,72,38,8,18,59存储到散列表中,这些元素存入散列表的顺序并不确定。假定之前散列表为空,则元素59存放在散列表中的可能地址有: A) 5 B) 7 C) 9 D) 10 9、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变,下列哪些排序算法是稳定的: A) 插入排序 B) 基数排序 C) 归并排序 D) 冒泡排序 10、在参加NOI系列竞赛过程中,下面哪些行为是被严格禁止的: A) 携带书写工具,手表和不具有通讯功能的电子词典进入赛场。 B) 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。 C) 通过互联网搜索取得解题思路。 D) 在提交的程序中启动多个进程以提高程序的执行效率。 三.问题求解(共2题,每空5分,共计10分) 1.拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若 ∈E(G),则u在线性序列中出现在v之前,这样的线性序列成为拓扑序列。如下的有向无环图,对其顶点做拓扑排序,则所有可能的拓扑序列的个数为 。 2.某个国家的钱币面值有1, 7, 72, 73共计四种,如果要用现金付清10015元的货物,假设买卖双方各种钱币的数量无限且允许找零,那么交易过程中至少需要流通 张钱币。 四.阅读程序写结果(共4题,每题8分,共计32分) 1. var a, b: integer; function work(a, b: integer): integer; begin if a mod b <> 0 then work := work(b, a mod b) else work := b; end; begin read(a, b); writeln(work(a, b)); end. 输入:123 321 输出:_________ 2. var a, b: array[0..3] of integer; i, j, tmp: integer; begin for i := 0 to 3 do read(b[i]); for i := 0 to 3 do begin a[i] := 0; for j := 0 to i do begin inc(a[i], b[j]); inc(b[a[i] mod 4], a[j]); end; end; tmp := 1; for i := 0 to 3 do begin a[i] := a[i] mod 10; b[i] := b[i] mod 10; tmp := tmp (a[i] + b[i]); end; writeln(tmp); end. 输入:2 3 5 7 输出:_______________ 3. const y = 2009; maxn = 50; var n, i, j, s: longint; c: array[0..maxn, 0..maxn] of longint; begin s := 0; read(n); c[0, 0] := 1; for i := 1 to n do begin c[i, 0] := 1; for j := 1 to i - 1 do c[i, j] := c[i-1, j-1] + c[i-1, j]; c[i, i] := 1; end; for i := 0 to n do s := (s + c[n, i]) mod y; write(s); end. 输入:17 输出: 4. var n, m, i, j, k, p: integer; a, b: array[0..100] of integer; begin read(n, m); a[0] := n; i := 0; p := 0; k := 0; repeat for j := 0 to i - 1 do if a[i] = a[j] then begin p := 1; k := j; break; end; if p <> 0 then break; b[i] := a[i] div m; a[i+1] := (a[i] mod m) 10; inc(i); until a[i] = 0; write(b[0], '.'); for j := 1 to k - 1 do write(b[j]); if p <> 0 then write('('); for j := k to i - 1 do write(b[j]); if p <> 0 then write(')'); writeln; end. 输入:5 13 输出:_________ 五.完善程序 (前5空,每空2分,后6空,每空3分,共28分) 1.(最大连续子段和)给出一个数列(元素个数不多于100),数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列,使得这个子数列中包含的所有元素之和最大,在和最大的前提下还要求该子数列包含的元素个数最多,并输出这个最大和以及该连续子数列中元素的个数。例如数列为4,-5,3,2,4时,输出9和3;数列为1 2 3 -5 0 7 8时,输出16和7。 var a: array[1..100] of integer; n, i, ans, len, tmp, beg: integer; begin read(n); for i := 1 to n do read(a[i]); tmp := 0; ans := 0; len := 0; beg := ① ; for i := 1 to n do begin if tmp + a[i] > ans then begin ans := tmp + a[i]; len := i - beg; end else if ( ② ) and (i - beg > len) then len := i - beg; if tmp + a[i] ③ then begin beg := ④ ; tmp := 0; end else ⑤ ; end; writeln(ans, ' ', len); end. 2. (寻找等差数列) 有一些长度相等的等差数列(数列中每个数都为0~59的整数),设长度均为L,将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数,问原先,L最大可能为多大?先读入一个数n(1<=n<=60),再读入n个数,代表打乱后的数。输出等差数列最大可能长度L。 var hash: array[0..60] of integer; n, x, ans, maxnum, i: integer; function work(now: integer): boolean; var ok: boolean; first, second, delta, i: integer; begin while (( ① ) and (hash[now]=0)) do inc(now); if now > maxnum then begin work := true; exit; end; first := now; for second := first to maxnum do if hash[second] > 0 then begin delta := ② ; if first + delta ③ > maxnum then break; if delta = 0 then ok := ( ④ ) else begin ok := true; for i := 0 to ans - 1 do ok := ⑤ and (hash[first+delta i]>0); end; if ok then begin for i := 0 to ans - 1 do dec(hash[first+delta i]); if work(first) then begin work := true; exit; end; for i := 0 to ans - 1 do inc(hash[first+delta i]); end; end; work := false; end; begin fillchar(hash, sizeof(hash), 0); read(n); maxnum := 0; for i := 1 to n do begin read(x); inc(hash[x]); if x > maxnum then maxnum := x; end; for ans := n downto 1 do if (n mod ans = 0) and ⑥ then begin writeln(ans); break; end; end. 3 2 1 5 4 7 6 8 997 全国分区联赛 高中组(初赛) 第三届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题(高中组) ( Pascal 语言 竞赛用时:2小时) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一.基础部份: 〈1〉WPS 是属于 类软件; FOXBASE 是属于 类软件。 用FOXBASE的命令: CREATE GZB,在磁盘中生成的是 文件。 〈2〉在MS DOS的根目录中,有如下文件: TIME.EXE
TIME.BAT 试问:C: \ > TIME〈回车〉 执行的是什么命令? 〈3〉已知 ASCII码表中的大写字母后有6个其他字符, 接着便是小写字母。现已知:A字母的ASCII码为 (41)16 {表示十六进制数41},试写出如下字母用十进制表示的ASCII码: G-→( )10 b -→( )10 t -→( )10 〈4〉 设数组A [ 10..100 , 20..100 ] 以行优先的方式顺序存储,每个元素占4个字节,且已知A [ 10 , 20 ] 的地址为1000,则A [ 50 , 90 ] 的地址是 。 〈5〉一个汉字的机内码目前通常用二个字节来表示:第一个字节是区位码的区号加 (160)10; 第二个字节是区位码的位码加 (160)10 。 已知:汉字“却”的区位码是4020,试写出机内码两个字节的二进制的代码: □□□□□□□□,□□□□□□□□ 〈6〉下图中用点表示城市,点与点之间的联线表示城市间的道路: 试问:① 能否找出一条从A城市出发,经过图中所有道路一次后又回到 出发点的通路来? ② 能否从A出发,找出去每个城市且只去一次的通路来? 若能,则写出通路,否则说明理由。 〈7〉为了便于处理表达式,常常将普通表达式(称为中缀表示)转换为前缀 {运算符在前,如X/Y写为 / XY} 和后缀 {运算符在后,如X / Y写为X Y / } 的表达形式。 在这样的表示中可以不用括号即可确定求值的顺序,如: (P+Q)*(R-S)→ *+PQ-RS 或→ RQ+RS-* ① 试将下面的表达式改写成前缀与后缀的表示形式: 〈a〉A+B*C/ D 〈b〉A-C*D+B∧E ② 试将下面的前缀表示还原成中缀的表示形式,同时写出后缀表示: +△A*B△C {前缀式中△表示一元运算符取负号,如△A表示 (-A)} 〈8〉一个将角编了号的正三角形可以进行如下二种运动: < a > 沿过顶点1的高h翻转180°,我们将这个运动用字母a来表示: < b > 沿过三角形的外心,垂直于三角形所在平面的有向轴L (注意:三角形翻转时L轴也随着翻转的),按右手法则旋转120°(右手法则是指用右手大拇指指向L轴的方向,由其余四指决定旋转方向的法则),我们将这样的运动用字母b来表示: 如果将a,b作为运算对象,并将两个运动连续进行看作一种运算(这里不妨也称为乘法),则对图一的三角形而言,aa的结果便成为: 若将运动前后的三角形状态简称为元素,那么三角形状态就可与运动的表达式关联起来。据此,请回答如下问题: ① 从图一的三角形的原始状态出发,可以运动出多少种不同状态的三角形,试写出最简单的运算表达式(借助于a , b与乘法运算); ② 这样定义的乘法运算是否符合交换律与结合律? ③ 如果将从三角形的某种状态运动回到原始状态称之为该元素的逆元素,例如: ∴ bb的逆元素为b,可表示为 (bb) –1 =b 试求: (1) a -1 = (2) (ab)-1 = (3) ((aa) a)-1 = (4) b -1 = 二.根据题意,补充完善以下程序: 1.[问题描述]:一个正整数(非素数)可以表示成它的因子(1与其本身除外)的乘积。 例如: 12有因子2 , 2 , 3 , 4 , 6,所以可表示为: 12 =2 2 3 = 4 3 =2 6 给出任一个正整数N,求出它所有的因子乘积的表达式(交换律得出的不同式子算同一种)。 [算法说明]:读入一个整数N,首先求出它的所有的因子以及每个因子可能的次数。 例如:整数48: 因子: 2 3 4 6 8 12 16 24 次数: 4 1 2 1 1 1 1 1 将上面的结果存入数组 A : ARRAY [ 0 .. 20 , 1 .. 2 ]中,其中: A[ i , 1 ]表示因子; A[ i , 2 ]表示次数。 然后用简单回溯的方法求出所有可能的表示: 数组B[ 0 .. 20 ]记录取数情况; C : ARRAY [ 0 .. 20 ]工作单元。 [程序清单]: program exp4 ( input , output ); var a : array [ 0..20 , 1..2 ] of integer; c , b : array [ 0..20] of integer; n , m , i , j , s , k , L : integer; Begin readln (n); for i := 1 to 20 do a [ i , 1 ]:= 0; ① ; a [ 0 , 2 ]:=1; j:=0; for i := 2 to n-1 do begin s := 0; m := n; while ( m < > 0) and ( m mod i = 0 ) do begin m := m div i; ② ; end; if ③ then begin j := j + 1; ④ ; a [ j , 2 ] := ⑤ ; end end; for i := 0 to j do b [ j ] := 0; while b[ 0 ] = 0 do begin k := j; while ⑥ do k := k -1; b [ k ]:= b [ k ] + 1; for L:= ⑦ do b [ L ]:= 0; s := 1; for i := 1 to j do if b [ i ] < > 0 then for L := 1 to b [ i ] do ⑧ ; if s = n then begin for i := 1 to j do c [ i ]:= b [ i ]; write ( ‘(’ ); m := 1; for i :=1 to j do while ( c [ i ] > 0 ) and ( m < > n ) do begin m := m a [ i , 1 ]; if m = n then write ( a [ i , 1 ] ) else begin write ( a [ i , 1 ] , ‘ ’ ); c [ i ] := c [ i ] – 1; end; end; writeln ( ‘)’ ); end end; End. 2.[问题描述]:给出一个凸多边形,可以取得若干个内接三角形,同时约定内接三角形必须有一条边(仅能有一条边)与凸多边形的边相重合,例如:下面的5边形中,可能有的内接三角形有5种: 问题: 当依次给出凸多边形的每个顶点的2个坐标之后,找出一个面积最大的内接三角形,输出该三角形的面积与三个顶点的坐标。 [算法说明]:凸多边形的每个顶点用一对坐标(x , y)表示; 用数组p:array [1..n] of point; 存储输入的顶点坐标; 同时编制一个由三角形的三个顶点计算其面积的函数SEA。 [程序清单]: program exp5 ( input , output ); const n = 6; type point =record x , y : real; end; var p : array [ 1 .. 2 n ] of point; i , j : integer; q1 , q2 , q3 : point; smax : real; function sea ( p1, p2 , p3 : point ) : real; var s1 , s2 , s3 , s4 : real; begin s1:= sqrt ( (p1.x - p2.x) (p1.x - p2.x) + (p1.y - p2.y) (p1.y - p2.y) ); s2:= sqrt ( (p1.x – p3.x) (p1.x – p3.x) + (p1.y – p3.y) (p1.y – p3.y) ); s3:= sqrt ( (p2.x – p3.x) (p2.x – p3.x) + (p2.y – p3.y) (p2.y – p3.y) ); p4:= ① ; sea:= sqrt ( p4 (p4 – s1) (p4 - s2) (p4 - s3) ); end; Begin for i:=1 to n do readln ( p[ i ].x , p[ i ].y ); smax:=0; for i:=1 to n-1 do ② for i:=1 to n do for ③ do if ④ then begin smax := sea (p[ i ] , p[ i+1] , p[ j ]); q1:= p[ i ]; q2:= ⑤ ; q2:= p[ j ] end; writeln ( smax , q1.x , q1.y , q2.x , q2.y , q3.x , q3.y ) End. 3.[问题描述]:拼图形:边长为1的正方形面积为1,从边长为1的正方形出发可以用2个边长为1的正方形拼成面积为2的长方形: 同时约定: 1.边长对应相等的长方形被认为是相同的;(所有左边的两个面积为2的长方形只看作一个长方形); 2.长度相等的边才能拼接,且两个边必须重合; 从面积为2的长方形出发,用2个面积为2的长方形可拼出面积为4的长方形(包括正方形),拼法如下: 同样再从面积为4的长方形(包括正方形)出发,可以拼成面积为8的长方形,拼法如下: 可以按上面的方法继续拼下去。 问题:输入一个数N,输出面积不超过N的所有可能拼法。例如:当N=20时,输出: (1 , 1),(2 , 1),(4 , 2),(8 , 2),(16 , 3)即面积为1的拼法1种,面积为2的拼法1种,面积为4的拼法2种,面积为8的拼法2种,面积为16的拼法3种。 [算法说明]:矩形可以用三个数x , y , s来表示,其中x , y 表示边长,s表示面积,并用数组G[ 1..100 , 1..3 ] 表示图形。 拼接过程为: 有二种拼法: 当给出n之后,可能拼接的次数为r满足:2 r≤N<2r+1 (不包括面积为1的拼法); 用数组b[1..100]记录各种面积可能出现的拼法。 [程序清单]: program exp8 ( input , output ); type g = record x , y , z : integer end; var g1 : array [ 1..100 ] of g; i , j , n , s1 , jj , j1 , j2 , i1 : integer; b : array [ 1..100 ] of integer; gw : g; function eq (gk : g) : boolean; var jeq : integer; p : boolean; begin p:= true; jeq:=1; while ( p and ( jeq < = j ) ) do if ( ( gk.x = g1[ jeq ].x ) and ( gk.y = g1[ jeq ].y ) ) or ( ( gk.x = g1[ jeq ].y ) and (gk.y = g1[ jeq ].x ) ) then p:=false else jeq:= jeq +1; eq:=p end; Begin readln (n); s1:=1; jj := 1; while ① do begin ② ; jj := jj + 1 end; ③ ; j1:= 1; j := 1; g1[ j ].x := 1; g1[ j ].y := 1; g1[ j ].z := 1; for i :=2 to jj do begin j2 := j; for i1:=j1 to j2 do begin gw.x := g1[i1].x 2; gw.y := g1[i1].y; gw.z := g1[i1].z 2; if ④ then begin j:= j + 1; g1[ j ]:= gw end; gw.x := g1[ i1].x; ⑤ ; if eq (gw) then begin j := j + 1; ⑥ ; end; end; j1 := j2 + 1 end; for i:=1 to n do b[ i ] := 0; for i:=1 to j do ⑦ ; for i:=1 to n do if ⑧ then write ( ‘(’ , i , ‘ ,’ , b[i] , ‘ )’ ); End. A D C B E F a 3 1 2 h 2 1 3 h 2 1 3 h L 1 2 3 h L b 3 1 2 1 2 3 bb 3 1 2 2 3 1 3 1 2 b bb △ACD , △BDE , △CEA , △DAB , △EBC B A C E D y x x y y y x x 或 ·2·2001 全国分区联赛 高中组(初赛) 第七届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题 (提高组PASCAL语言 二小时完成) ●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●● 一. 选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分,多选无分,共30分) 1、中央处理器CPU能访问的最大存储器容量取决于( ) A) 地址总线
C) 可擦除可编程只读 D)高速缓冲 7、若我们说一个微机的CPU是用的PII300,此处的300确切指的是( ) A) CPU的主时钟频率
B) CPU产品的系列号 C) 每秒执行300百万条指令
D) 此种CPU允许最大内存容量 8、Email邮件本质上是一个( ) A) 文件
B) 电报
C) 电话
D) 传真 9、2KB的内存能存储( )个汉字的机内码 A) 1024
B) 516 C) 2048
D) 218 10、以下对Windows的叙述中,正确的是( ) A) 从软盘上删除的文件和文件夹,不送到回收站 B) 在同一个文件夹中,可以创建两个同类、同名的文件 C) 删除了某个应用程序的快捷方式,将删除该应用程序对应的文件 D) 不能打开两个写字板应用程序 11、运算式(2047)10 - (3FF)16+ (2000)8的结果是( ) A) (2048)10
B) (2049)10
C) (3746)8
D) (1AF7)16 12、TCP/IP协议共有( )层协议 A) 3
B) 4
C) 5
D) 6 13、若已知一个栈的入栈顺序是1,2,3,…,n,其输出序列为P1,P2,P3,…,Pn,若P1是n,则Pi是( ) A) i
B) n-1
C) n-i+1
D) 不确定 14、计算机病毒是( ) A) 通过计算机传播的危害人体健康的一种病毒 B) 人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合 C) 一种由于计算机元器件老化而产生的对生态环境有害的物质 D) 利用计算机的海量高速运算能力而研制出来的用于疾病预防的新型病毒 15、下面关于算法的错误说法是( ) A) 算法必须有输出
B) 算法必须在计算机上用某种语言实现 C) 算法不一定有输入 D) 算法必须在有限步执行后能结束 16、[ x ]补码=10011000,其原码为( ) A) 011001111
B) 11101000
C) 11100110
D) 01100101 17、以下哪一个不是栈的基本运算( ) A) 删除栈顶元素 B) 删除栈底的元素 C) 判断栈是否为空 D) 将栈置为空栈 18、在顺序表(2,5,7,10,14,15,18,23,35,41,52)中,用二分法查找12,所需的关键码比较的次数为( ) A) 2
B) 3
C) 4
D) 5 19、一棵二叉树的高度为h,所有结点的度为0,或为2,则此树最少有( )个结点 A) 2h-1
B) 2h-1
C) 2h+1
D) h+1 20、无向图G=(V,E),其中V={ a , b , c , d , e , f } E={ (a , b) , (a , e) , (a , c) , (b , e) , (c , f) , (f , d) , (e , d) }? 对该图进行深度优先遍历,得到的顶点序列正确的是( ) ? A) a,b,e,c,d,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,b,e,d,f,c 二.问题求解(5+7,共12分) 1、已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为:CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为: 2、平面上有三条平行直线,每条直线上分别有7,5,6个点,且不同直线上三个点都不在同一条直线上。问用这些点为顶点,能组成多少个不同四边形? 三.阅读程序,并写出正确的运行结果(4 + 7 + 8 + 9,共28分) 1. PROGRAM GAO7_1:
VAR P,Q,S,T:INTEGER; BEGIN READLN(P); FOR Q:=P+1 TO 2 P DO
BEGIN T:=0; S:=(P Q) MOD (Q-P); IF S=0 THEN BEGIN T:=P+Q+ (P Q) DIV (Q-P); WRITE(T:4); END; END; END. 输入:12 输出: 3. PROGRAM GAO7_3;
VAR I,J,H,M,N,K:INTEGER;
B?:ARRAY[1..10] OF INTEGER; BEGIN READLN(N); FOR I:=1 TO 10 DO BEGIN M :=N; J:=11; WHILE M > 0 DO BEGIN J:=J-1; B[J]:=M MOD 10; M:=M DIV 10 ? END; FOR H:=J TO 10 DO? N:=N+B[H]; END;
WRITELN(N); END. 输入1234 输出: 4. PROGRAM GAO7_4;
VAR X,Y1,Y2,Y3:INTEGER; BEGIN READLN(X); Y1:=0; Y2:=1; Y3:=1; WHILE Y2<=X DO BEGIN Y1:=Y1+1; Y3:=Y3+2; Y2:=Y2+Y3
⑤ :=D; DK[ I+1 , 2 ]:=L; SP:=SP+1; END; FOR I:=1 TO SP-1 DO WRITELN(DK[ I , 1 ] : 4,DK[ I , 2 ] : 4); READLN; END. 2、求关键路径 ? 设有一个工程网络如下图表示(无环路的有向图): ? 其中,顶点表示活动,①表示工程开始,⑤表示工程结束(可变,用N表示),边上的数字表示活动延续的时间。 ? ? ? 如上图中,活动①开始5天后活动②才能开始工作,而活动③则要等①、②完成之后才能开始,即最早也要7天后才能工作。 在工程网络中,延续时间最长的路径称为关键路径。 上图中的关键路径为: ①—②—③—④—⑤共18天完成。 关键路径的算法如下: 1. 数据结构:
R[1..N,1..N] OF INTEGER; 表示活动的延续时间,若无连线,则用-1表示; ? EET[1..N] 表示活动最早可以开始的时间 ? ET[1..N] 表示活动最迟应该开始的时间 ???? 关键路径通过点J,具有如下的性质: EET[ J ] = ET[ J ] 2. 约定: ? 结点的排列已经过拓扑排序,即序号前面的结点会影响序号后面结点的活动。 程序清单: PROGRAM GAO7_6; VAR I,J,N,MAX,MIN,W,X,Y:INTEGER; R:ARRAY [1..20,1..20] OF INTEGER; EET,ET:ARRAY [1..20] OF INTEGER; BEGIN READLN (N) FOR I:=1 TO N DO
END; EET[1]:=0;{认为工程从0天开始} FOR I:=2 TO N DO BEGIN MAX:=0; FOR J:=1 TO N DO IF R[J,I]<>-1 THEN IF ②
THEN MAX:=R[J,I]+EET[J]; EET[I]:=MAX; END;
③
FOR I:=N-1 DOWNTO 1 DO BEGIN MIN:=10000; FOR J:=1 TO N DO IF R[ I , J ]<> -1 THEN IF ④ THEN MIN:=ET[J] - R[ I , J ]; ET[I]:=MIN; END; WRITELN(EET[N]); FOR I:=1 TO N-1 DO IF ⑤ THEN WRITE (I,'→'); WRITE (N); READLN END. ·2·第十八届全国青少年信息学奥林匹克联赛初赛 提高组 Pascal语言试题 竞赛时间:2012年10月13日14:30~16:30 选手注意 试题纸共有15页,答题纸共有2页,满分100分。请在答题纸上作答,写在试题纸上 的一律无效 ●不得使用任何电子设备(如计算器、手机、电子词典等)或查阅任何书籍资料 单项选择题(共10题,每题1.5分,共计15分;每题有且仅有一个正确选 项) 1.目前计算机芯片(集成电路)制造的主要原料是(),它是一种可以在沙子中提炼 出的物质 A.硅 B.铜 2.()是主要用于显示网页服务器或者文件系统的HTML文件内容,并让用户与这些 文件交互的一种软件。 A.资源管理器B.浏览器 C.电子邮件 D.编译器 3.目前个人电脑的()市场占有率最靠前的厂商包括 Intel, AMD等公司 A.显示器 B. CPU C.内存 D.鼠标 4.无论是TCPP模型还是OSI模型,都可以视为网络的分层模型,每个网络协议都会被 某一层中。如果用现实生活中的例子来比喻这些“层”,以下最恰当的是()。 A.中国公司的经理与斯洛伐克公司的经理交互商业文件 第4层 中国公司经理 斯洛伐克公司经理 第3层 中国公司经理秘书 斯洛伐克公司经理秘书 第2层 中国公司翻译 斯洛伐克公司翻译 第1层 中国邮递 斯洛伐克邮递员 CCF NOIP2012初赛 提高组 Pascal1 B.军队发布命令 第4层 司令 第3层 军长1 军长2 第2层 师长1 师长2 师长3 师长4 第1层团长1团长2团长3团长4团长5团长6团长7团长8 C.国际会议中,每个人都与他国地位对等的人直接进行会谈 第4层 英国女王 瑞典国王 第3层 英国首相 瑞典首相 第2层 英国外交大臣 瑞典外交大臣 第1层 英国驻瑞典大使 瑞典驻英国大使 D.体育比赛中,每一级比赛的优胜者晋级上一级比赛 第4层 奥运会 第3层 全运会 第2层 省运会 第1层 市运会 5.如果不在快速排序中引入随机化,有可能导致的后果是() A.数组访问越界 B.陷入死循环 C.排序结果错误 D.排序时间退化为平方级 6.1946年诞生于美国宾夕法尼亚大学的ENAC属于()计算机。 A.电子管 B.晶体管 C.集成电路 D.超大规模集成电路 7.在程序运行过程中,如果递归调用的层数过多,会因为()引发错误。 A.系统分配的找空间溢出 B.系统分配的堆空间溢出 CCF NOIP2012初赛 是高组 Pascal299 全国分区联赛 高中组(初赛) 第五届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题(高中组) ( Pascal 语言 竞赛用时:2小时) ●● 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一. 选择一个正确答案代码(A/B/C/D),填入每题的括号内 (每题1.5分,多选无分,共30分) 1. 微机内存储器的地址是按( )编址的。 A. 二进制位 B. 字长 C. 字节 D. 微处理器的型号 2. 下列诸因素中,对微机工作影响最小的是( ) A. 尘土 B. 噪声 C. 温度 D. 湿度 3. 在24 24点阵的字库中,汉字“一”与“编”的字模占用字节数分别是( ) A. 32,32 B. 32,72 C. 72,72 D. 72,32 4. 将DOS系统盘插入A驱动器启动机器,随后使用一批应用软件,在此过程中,DOS系统盘( ) A. 必须始终插入在A驱动器中 B. 不必再用 C. 可能有时要插入A驱动器中 D. 可能有时要插入B驱动中 5. 以下DOS命令中,有可能在磁盘上建立子目录的是( ). A. type B. dir C. xcopy D.cd 6. 在config.sys文件中,装入特定的可安装设备驱动程序的命令是( ). A. buffer B. files C. driver D. device 7. 计算机能直接执行的指令包括两部分,它们是( ). A. 源操作数与目标操作数 B.操作码与操作数 C. ASCII码与汉字代码 D.数字与字符 8. 在微机中,通用寄存器的位数是( ). A. 8位 B. 16位 C. 计算机字长 D. 32位 9. 在计算机中,ASCII码是( )位二进制代码 A. 8 B. 7 C. 12 D. 16 10. 计算机的软件系统通常分为( ) A. 系统软件与应用软件 B. 高级软件与一般软件 C. 军用软件与民用软件 D. 管理软件与控制软件 11. 执行DOS命令:C>ATTRIB A: . 的功能是( ) A. 查看A盘上所有文件属性 B. 查看A盘上当前目录中所有文件属性 C. 查看A盘上所有系统文件属性 D. 删去A盘上所有隐含文件的属性 12. 执件下列DOS命令,效果等价的是( )组. A. copy . for 与 copy . for con B. copy A: . B: 与 xcopy A: . B: C. copy fole1.txt + file2.txt 与 copy flle2.txt + file1.txt D. xcopy A: . B: /S 与 diskcopy A: B: 13. 已知小写字母‘m’的十六进制的ASCll码值是6D,则小写字母‘c’的十六进制的ASCII码值是( ) A. 98 B. 62 C. 99 D. 63 14. 计算机中的数有浮点数与定点数两种,其中用浮点数表示的数,通常由( )这两部分组成。 A. 指数与基数 B. 尾数与小数 C. 阶码与尾数 D. 整数与小数 15. 下列文件名中,属于DOS中的保留设备名的为( ) A. AUX B. COM C. CON 1 D. PRN 1 16. 启动计算机引导DOS是将操作系统( ) A. 从磁盘调入中央处理器 B. 从内存储器调入高速缓冲存储器 C. 从软盘调入硬盘 D. 从系统盘调入内存储器 17. 十进制算术表达式:3 512 + 7 64 + 4 8 + 5 的运算结果,用二进制表示为( ). A. 10111100101 B. 11111100101 C. 11110100101 D. 11111101101 l8. 组成‘教授’(jiao shou)‘副教授’(fu jiao shou)与‘讲师’(jiang shi)这三个词的汉字,在GB2312-80字符集中都是一级汉字.对这三个词排序的结果是( ). A. 教授,副教授,讲师 B. 副教授,教授,讲师 C. 讲师,副教授,教授 D. 副教授,讲师,教授 19. 不同的计算机,其指令系统也不同,这主要取决于( ). A. 所用的操作系统 B. 系统的总体结构 C. 所用的CPU D. 所用的程序设计语言 20. 对具有隐含属性(H)的当前目录下的文件 ab. txt,能成功执行的 DOS命令是() A. TYPE ab.txt B. COPY ab. txt xy. txt C. DIR ab.txt D. REN ab. txt xy. txt 二.回答问题: (共10分) 将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。 例如:当n=1时,L1=2,进一步考虑,用n条折成角的直线(角度任意),放在平面上,能确定的最大区域数目Zn是多少?例如:当n=1时,Z1=2 (如图所示) 当给出n后,请写出以下的表达式: Ln= Zn= 三.阅读程序,并写出程序的正确运行结果: (每题15分,共30分) 1. program exgp1; var i , j , k : integer; a : array [0..100] of integer; Begin for i:=0 to 100 do a[i]:=i; for k:=5 downto 2 do begin
for i:=1 to 100 do if(i mod k)=0 then a[i]:=0;
for i:=1 to 99 do
for j:=1 to 100-i do if a[j]>a[j+1] then begin
a[j]:=a[j]+a[j+1];
a[j+1]:=a[j]-a[j+1];
a[j]:=a[j]-a[j+1];
end; end; j:=1; while (a[j]=0) and (j<100) do j:=j+1; for i:=j to 100 do a[0]:=a[0]+a[i]; writeln(a[0]); End 本题的运行结果是:
2. 设数组A[1],A[2],…A[N],已存入了数据,调入不同的排序程序,则数据比较的次数将会不同,试计算出分别调用下列不同的排序过程的比较运算的次数。 其中SWAP(I,J)表示A[ I ]与A[ J ]进行交换。 (1) PROCEDURE SORT1(N:INTEGER);