《广东省汕头市金山中学高一信息技术 历年noip初赛试题14》由会员分享，可在线阅读，更多相关《广东省汕头市金山中学高一信息技术 历年noip初赛试题14（8页珍藏版）》请在金锄头文库上搜索。
1、广东省汕头市金山中学高一信息技术 历年NOIP初赛试题14（高中组） Pascal语言 竞赛用时：2小时 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、基础知识部分 （44分）1 已知A盘上的目录和文件组织如下：ROOTTP D11 F1.TXTTB F2.TXTDOS D31 F3.DOC F4.DOC FORMAT.COM其中TP、TB、DOS、D11、D31都是子目录名。设当前命令提示符为 A:TB ，请写出完成如下操作的DOS命令：在DOS运行中，没有执行过PATH命令，现要用DOS子目录中FORMAT命令，对插入在B驱动器（5.25英寸高密）中的360KB软盘进行格式化工
2、作，请写出相应的操作命令。 交换F2.TXT与F3.DOC两个文件的内容，要求使用的命令不得超过三条；2请用等号或不等号联接表示下列不同进位制数值的大小。例如： (3)10 (4)4 (100)2 =10;4 已知： ack(m,n) 函数的计算公式如下：n+1 m=0ack (m , n) = ack (m-1 , 1) n=0ack (m-1 , ack ( m , n-1) ) m0 且 n0请计算： ack ( 1 , 3 )、ack ( 2 , 4 )、ack ( 3 , 3 )、ack ( 3 , 4 ) 的值5 有NN个数据组成如下方阵：A11 A12 A13 A1NA21 A2
3、2 A23 A2NA31 A32 A33 A3N AN1 AN2 AN3 ANN并已知：AIJ = AJI现将A11，A12，A1N，A22，A23，A2N，A33，A34，A3N，ANN 存储在一维数组A1，A2，A N* (N+1) / 2 中。试问：任给I , J 怎样求出K来，使得A K的值正好是AIJ，请写出由I , J计算K的表达式。6 已知： A1 , A2 , , A81 共有81个数，其中只有一个数比其他数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整。第一步： s1=A1 + A2 + + A27
4、s2=A28 + A29 + + A54第一次比较 ( s1 , s2 )：s1 s2 取K = 0s1 s2 取K = s1 s2 取K = s1 s2 为最大数s1 s2 为最大数s1 = s2 为最大数7 下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，表示空结点，表示存储数据结束）。现要求画出对应该存储结构的二叉树示意图。123456789101112131415ABC#DE#GF二、根据题目要求，补充完善以下程序：1 题 目：积木游戏：设有n个小木块排成一排，如下图： 游戏开始时，每个小木块向下的一面涂有红、黄、
5、蓝三种颜色之中的一种（约定： 0表示红色，1表示黄色，2表示蓝色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木块只能看一次），最终成为下面的形状： 红 蓝 黄即相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次数实现上面的要求。算法描述：翻看小木块时，可以从两端进行。例如，设中间状态如下：a b c 红 未翻过 蓝 黄此时，可以从两个方向看，即从a或b处开始：1若看a则有三种可能性：为红色，则不用交换为蓝色，交换一次，即a与b交换为黄色，交换两次，即c与b交换一次，然后a与c再交换一次此时，平均交换次数为12若看b也有三种可能性：为蓝色，则不用交换为红色，
6、交换一次，即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;beginfor i := 1 to n do read (a i ); r := 1; ; y := n;while doif then begintem := a r ; a r := a b ; a b := tem; r := r +
7、1endelse if then begintem := a b ; a b := a y ; a y := tem; ; ;endelse b := b - 1;for i := 1 to n do write ( a i : 3 )end. 2题 目： 四色问题。设有下列形状的图形：有8个区域，其编号为1，2，n。 （n = 8）8765234112345678101000011210100110301010100400101100500010100601111010711000101810000010图形中各区域的相邻关系用上边的邻接矩阵表示：1相邻，0不相邻。程序要求：将上面图形的每一
8、个部分涂上红(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;beginfor i := 1 to
9、n do beginfor j:=1 to n do read ( r i , j ); readln; end; ; i := 2; j := 1; while i = n do beginwhile ( j =4 ) and (i = n) do begink := 1;while do k := k + 1;if k 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 + 2x21 可表示为：(4 , 6)，(-3 , 3)，(2 , 2)，(-1 , 0)，(0 , 0)Q ( x ) = x4x +1 可表示为：(1 , 4)，(-1 , 1)，(1 , 0)，(0 , 0)当用上面的方式给出2个多项式之后，程序对这两个多项式进行加法运算，结果也用上面的方式给出。例如：上面的 P( x ) 和 Q ( x ) 相加的结果为： 4x6 + x4 3x3 + 2x2x表示结果为： (4 , 6)，(1 , 4)，(-3 , 3)，(2 , 2)，(-1 , 1)，(0 , 0
