NOIP2013初赛提高组Pascal试题-及答案~.doc

|第 十九 届 全国青 少 年信 息 学奥林 匹 克联 赛 初赛提高组 Pascal 语言试题竞赛时间 ： 2013 年 10 月 13 日 14:3016:30选 手注 意： 试题纸 共 有 12 页， 答题 纸 共有 2 页， 满 分 100 分。 请在答 题纸 上作 答， 写在 试题 纸 上 的一律 无效 。 不得使 用任 何电 子设 备（ 如计算 器、 手机 、电 子词 典等） 或查 阅任 何书 籍资 料。一 、单 项选择 题（ 共 15 题 ，每 题 1.5 分 ，共计 22.5 分； 每题 有且仅 有一 个正确 选 项）1. 一个 32 位 整型 变量 占用 （ ） 个字 节。A. 4 B. 8 C. 32 D. 1282. 二进制 数 11.01 在十 进制 下是（ ）。A. 3.25 B. 4.125 C. 6.25 D. 11.1253. 下面的 故事 与（ ）算 法 有着异 曲同 工之 妙。从前有 座山 ， 山里 有座 庙 ， 庙 里有 个老 和尚 在给 小 和尚讲 故事 ： 从前 有座 山， 山 里有座 庙 ， 庙 里有 个老 和 尚在给 小和 尚讲 故事 ： 从前有 座山 ， 山里 有座 庙 ， 庙 里有 个 老和尚 给 小 和尚 讲故 事. .A. 枚举 B. 递归 C. 贪心 D. 分治4. 1948 年， （ ）将 热力 学 中的熵 引入 信息 通信 领域 ，标志 着信 息论 研究 的开 端 。A. 冯·诺 伊曼 （ John von Neumann） B. 图灵（ Alan Turing）C. 欧拉（L eonhard Euler） D. 克劳德 ·香 农（ Claude Shannon）5. 已知一 棵二 叉树 有 2013 个 节点， 则其 中至 多有 （ ）个节 点 有 2 个 子节 点。A. 1006 B. 1007 C. 1023 D. 10246. 在一个 无向 图中 ， 如 果任 意两点 之间 都存 在路 径相 连， 则 称其 为连 通 图。右 图是 一个 有 5 个顶 点、8 条边 的连 通图 。若 要使它 不再 是连 通 图，至 少要 删去 其中 的 （ ）条 边。|A. 2 B. 3 C. 4 D. 57. 斐波那 契数 列的 定义 如下 ： F1 = 1, F2 = 1, Fn = Fn 1 + Fn 2 (n 3)。 如 果用 下面 的函数 计 算斐波 那契 数列 的 第 n 项 ，则其 时间 复杂 度为 （ ）。funtion F(n : longint) : longint;beginif n 100 do beginsum := sum + i;inc(i);end;C. i := 1;repeatsum := sum + i;inc(i);until i > 100;D. i := 1;repeatsum := sum + i;inc(i);until i strn-i+1) thenisPlalindrome := false;end;if (isPlalindrome) then writeln('Yes')elsewriteln('No');end.输入：a bceecba输出： 2. vara, b, u, v, i, num : integer;beginreadln(a, b, u, v);num := 0;for i := a to b do beginif (i mod u = 0) or (i mod v = 0) then inc(num);|end;writeln(num);end.输入：1 1000 10 15输出： 3. const SIZE = 100;varn, ans, i, j : integer;height, num : array1.SIZE of integer;begin read(n);for i := 1 to n do beginread(heighti);numi := 1;for j := 1 to i-1 do beginif (heightj = numi) thennumi := numj+1;end;end;ans := 0;for i := 1 to n do beginif (numi > ans) thenans := numi;end;writeln(ans);end.输入：83 2 5 11 12 7 4 10输出： |4. const SIZE = 100;varn, m, p, count, ans, x, y, i, j : integer;a : array1.SIZE, 1.SIZE of integer;procedure colour(x, y : integer);begin inc(count); axy := 1;if (x > 1) and (ax-1y = 0) then colour(x-1, y);if (y > 1) and (axy-1 = 0) thencolour(x, y-1);if (x < n) and (ax+1y = 0) then colour(x+1, y);if (y < m) and (axy+1 = 0) thencolour(x, y+1);end;beginfillchar(a, sizeof(a), 0);readln(n, m, p); for i := 1 to p do beginread(x, y);axy := 1;end;ans := 0;for i := 1 to n dofor j := 1 to m doif aij = 0 then begincount := 0;colour(i, j);if (ans < count) then ans := count;|end;writeln(ans);end.输入：6 5 91 42 32 43 24 14 34 55 46 4输出： 五 、完 善程序 （第 1 题 15 分， 第 2 题 13 分， 共计 28 分）1. （序列重排）全 局数 组变 量 a 定 义如 下：const int SIZE = 100;int aSIZE, n;它记录 着一 个长 度 为 n 的 序列 a1, a2, , an。现在需 要一 个函 数， 以整 数 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);vari, j : longint;b : array1.SIZE of longint;beginfor i := 1 to p dob (1) := ai; /（2 分 ）for i := p + 1 to n do bi - p := ai;|for i := 1 to n doai := bi;end;我们也 可以 用时 间换 空间 ，使用 时间 复杂 度 为 O(n2)、空 间 复 杂 度 为 O(1)的算 法：procedure swap2(p : longint);vari, j, temp : longint;beginfor i := p + 1 to n do begintemp := ai;for j := i downto (4) do /（2 分 ）aj := aj - 1;(5) := temp; /（2 分 ）end;end;事实上 ，还 有一 种更 好的 算法， 时间 复杂 度 为 O(n)、空间 复杂 度 为 O(1)：procedure swap3(p : longint);varstart1, end1, start2, end2, i, j, temp : longint;beginstart1 := 1;end1 := p;start2 := p + 1;end2 := n; while true do begini := start1;j := start2;while (i <= end1) and (j <= end2) do begintemp := ai;ai := aj;|aj := temp; inc(i); inc(j);end;if i <= end1 then start1 := ielse if (4) then /（3 分 ）beginstart1 := (5) ; /（3 分 ） end1 := (6) ; /（3 分 ） start2 := j;end elsebreak;end;end;2. （两元序列） 试 求一 个整 数序列 中， 最长 的仅 包含 两个不 同整 数的 连续 子序 列。 如 有 多 个子序 列并 列最 长， 输出 任意一 个即 可。 例如 ，序 列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中 ， 有两段 满足 条件 的最 长子 序列， 长度 均 为 7， 分别 用下划 线和 上划 线标 出。program two;const SIZE = 100;varn, i, j, cur1, cur2, count1, count2, ans_length, ans_start, ans_end : longint;/cur1, cur2 分别 表示当 前子 序列 中的 两个 不同整 数/count1, count2 分别表 示 cur1, cur2 在 当前子 序列 中出 现的 次数a : array1.SIZE of longint;begin readln(n);for i := 1 to n do read(ai);i := 1;