NOIP2013提高组C++试题-.doc

|第 十九 届 全国青 少 年信 息 学奥林 匹 克联 赛 初赛提高组 C+语言试 题竞赛时间 ： 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 项 ，则其 时间 复杂 度为 （ ）。int F(int n)if (n 100) sum += i;i+;C. i = 1;do sum += i;i+; while (i 100);2. （ ）的 平均时 间复杂 度 为 O(n log n)，其 中 n 是待 排序的 元素 个数 。A. 快速排 序 B. 插入排 序 C. 冒泡排 序 D. 归并排 序3. 以 A0 作为 起点 ，对 下面 的 无向图 进行 深度优 先遍 历 时（遍 历的 顺序 与顶 点字 母的 下 标 无关） ，最 后一 个遍 历到 的顶点 可能 是（ ）。A. A1 B. A2 C. A3 D. A4|4. （ ）属 于 NP 类问 题 。A. 存在一 个 P 类 问题B. 任何一 个 P 类 问题C. 任何一 个不 属 于 P 类的 问 题D. 任何一 个在 （输 入规 模的 ）指数 时间 内能 够解 决的 问题5. CCF NOIP 复 赛考 试结 束 后，因 （ ） 提出 的申 诉 将不会 被受 理。A. 源程序 文件 名大 小写 错误B. 源程序 保存 在指 定文 件夹 以外的 位置C. 输出文 件的 文件 名错 误D. 只提交 了可 执行 文件 ，未 提交源 程序三 、问 题求解 （共 2 题， 每 题 5 分， 共计 10 分 ；每 题全部 答对 得 5 分 ， 没 有部 分 分）1. 某系统 自称 使用 了一 种防 窃听的 方式 验证 用户 密码 。 密码 是 n 个数 s1, s2, , sn， 均为 0或 1。 该 系统 每次 随机 生 成 n 个 数 a1, a2, , an， 均 为 0 或 1， 请 用户 回答( s1a1 + s2a2 + + snan)除 以 2 的 余数 。 如 果 多次的 回答 总是 正确 ， 即 认为 掌 握密 码。 该系 统认 为， 即 使 问答的 过程 被泄 露， 也无 助于破 解密 码 因 为用 户并没 有直 接发 送密 码。然而， 事与 愿违 。例 如， 当 n = 4 时， 有人 窃听 了以 下 5 次 问答 ：系统生 成 的 n 个 数问答编 号a1 a2 a3 a4掌握密 码的 用户 的回 答1 1 1 0 0 12 0 0 1 1 03 0 1 1 0 04 1 1 1 0 05 1 0 0 0 0就破解 出了 密 码 s1 = ， s2 = ， s3 = ， s4 = 。2. 现有一 只青 蛙， 初始 时在 n 号荷 叶上。 当它 某一 时刻 在 k 号 荷叶 上时， 下一 时 刻将等 概 率地随 机跳 到 1, 2, , k 号 荷叶 之 一上 ， 直至 跳 到 1 号荷叶 为止 。 当 n = 2 时 ， 平均一 共跳 2 次 ； 当 n = 3 时， 平均 一共 跳 2.5 次。 则当 n = 5 时，平 均一 共跳 次。1 2 3 4 5|四 、阅 读程序 写结 果（共 4 题， 每题 8 分， 共计 32 分）1. #include #include using namespace std;int main() string str; cin>>str;int n = str.size();bool isPlalindrome = true;for (int i = 0; i using namespace std;int main()int a, b, u, v, i, num;cin>>a>>b>>u>>v;num = 0;for (i = a; i using namespace std;int main()const int SIZE = 100;int heightSIZE, numSIZE, n, ans;cin>>n;for (int i = 0; i >heighti;numi = 1;for (int j = 0; j = numi)numi = numj+1;ans = 0;for (int i = 0; i ans) ans = numi;cout#include using namespace std;|const int SIZE = 100;int n, m, p, aSIZESIZE, count;void colour(int x, int y)count+;axy = 1;if (x > 1) if (y > 1) if (x >n>>m>>p;for (i = 1; i >x>>y;axy = 1;ans = 0;for (i = 1; i = (2) ; j-) /（2 分 ）aj = aj - 1;(3) = temp; /（2 分 ）事实上 ，还 有一 种更 好的 算法， 时间 复杂 度 为 O(n)、空间 复杂 度 为 O(1)：void swap3(int p)int start1, end1, start2, end2, i, j, temp;start1 = 1;end1 = p;start2 = p + 1;end2 = n;while (true) i = start1; j = start2;while (i using namespace std;int main()const int SIZE = 100;int n, i, j, aSIZE, cur1, cur2, count1, count2, ans_length, ans_start, ans_end;/cur1, cur2 分别表示 当前子 序列 中的 两个 不同 整数/count1, count2 分别表示 cur1, cur2 在当 前 子序列 中出 现的 次数cin>>n;for (i = 1; i >ai;i = 1;j = 1;/i, j 分别表示 当前 子序 列的首 尾， 并保 证其 中至 多有两 个不 同整 数while (j <= n) cur1 = ai;