完善程序专项练习.pdf

完善程序专项练习 百度 Pascal 吧公开培训教材 完善程序专项练习  1.  NOIP2013 提高组 （序列重排）全局数组变量 a 定义如下： const int SIZE = 100; var a:array [1..size] of integer; n:integer; 它记录着一个长度为 n 的序列 a[1], a[2], …, a[n]。 现在需要一个函数，以整数 p (1 ≤ p ≤ n)为参数，实现如下功能：将序列 a 的前 p 个数与后 n – p 个数对调，且不改变这 p 个数（或 n – p 个数） 之间的相对位置。例如， 长度为 5 的序列 1, 2, 3, 4, 5，当 p = 2 时重排 结果为 3, 4, 5, 1, 2。 有一种朴素的算法可以实现这一需求，其时间复杂度为 O(n)、空间复杂度为 O (n)： procedure swap1(p : longint); var i, j : longint; b : array[1..SIZE] of longint; begin for i := 1 to p do b[ (1)] := a[i]; for i := p + 1 to n do b[i - p] := a[i]; for i := 1 to n do a[i] := b[i]; end; 我们也可以用时间换空间，使用时间复杂度为 O(n2)、空间复杂度为 O(1)的算 法： procedure swap2(p : longint); var i, j, temp : longint; begin for i := p + 1 to n do begin temp := a[i]; for j := i downto (2)do //（2 分） a[j] := a[j - 1]; 第 1 页，共 10 页 完善程序专项练习 百度 Pascal 吧公开培训教材 (3) := temp; //（2 分） end; end; 事实上，还有一种更好的算法，时间复杂度为 O(n)、空间复杂度为 O(1)： procedure swap3(p : longint); var start1, end1, start2, end2, i, j, temp : longint; begin start1 := 1; end1 := p; start2 := p + 1; end2 := n; while true do begin i := start1; j := start2; while (i = end1) and (j = end2) do begin temp := a[i]; a[i] := a[j]; a[j] := temp; inc(i); inc(j); end; if i = end1 then start1 := i else if (4)then begin start1 := (5) ; end1 := (6) ; start2 := j; end else break; end; end; 第 2 页，共 10 页 完善程序专项练习 百度 Pascal 吧公开培训教材 2.NOIP2013 普及组 （二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有 节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。 输入的第一行包含一个整数 n，表示这棵树有 n 个顶点，编号分别为 1, 2, …, n，其中编号为 1 的为根结点。之后的第 i 行有三个数 value, left_child, rig ht_child，分别表示该节点关键字的值、左子节点的编号、右子节点的编号；如 果不存在左子节点或右子节点，则用 0 代替。输出 1表示这棵树是二叉查找树， 输出 0 则表示不是。 program Bst; const SIZE = 100; c