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

《NOIP2013提高组C++试题-.doc》由会员分享，可在线阅读，更多相关《NOIP2013提高组C++试题-.doc（12页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、|第 十九 届 全国青 少 年信 息 学奥林 匹 克联 赛 初赛提高组 C+语言试 题竞赛时间 ： 2013 年 10 月 13 日 14:3016:30选 手注 意： 试题纸 共 有 12 页， 答题 纸 共有 2 页， 满 分 100 分。 请在答 题纸 上作 答， 写在 试题 纸 上 的一律 无效 。 不得使 用任 何电 子设 备（ 如计算 器、 手机 、电 子词 典等） 或查 阅任 何书 籍资 料。一 、单 项选择 题（ 共 15 题 ，每 题 1.5 分 ，共计 22.5 分； 每题 有且仅 有一 个正确 选 项）1. 一个 32 位 整型 变量 占用 （ ） 个字 节。A. 4 B

2、. 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 年， （ ）将 热力 学 中的熵 引入 信息 通信 领域 ，

3、标志 着信 息论 研究 的开 端 。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 条边 的连 通图 。若 要使它 不再 是连 通 图，至

4、少要 删去 其中 的 （ ）条 边。|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. 冒泡排 序

5、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. 源程序

6、 保存 在指 定文 件夹 以外的 位置C. 输出文 件的 文件 名错 误D. 只提交 了可 执行 文件 ，未 提交源 程序三 、问 题求解 （共 2 题， 每 题 5 分， 共计 10 分 ；每 题全部 答对 得 5 分 ， 没 有部 分 分）1. 某系统 自称 使用 了一 种防 窃听的 方式 验证 用户 密码 。 密码 是 n 个数 s1, s2, , sn， 均为 0或 1。 该 系统 每次 随机 生 成 n 个 数 a1, a2, , an， 均 为 0 或 1， 请 用户 回答( s1a1 + s2a2 + + snan)除 以 2 的 余数 。 如 果 多次的 回答 总是 正确 ，

7、即 认为 掌 握密 码。 该系 统认 为， 即 使 问答的 过程 被泄 露， 也无 助于破 解密 码 因 为用 户并没 有直 接发 送密 码。然而， 事与 愿违 。例 如， 当 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 号 荷叶 上

8、时， 下一 时 刻将等 概 率地随 机跳 到 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; cinstr;int n = str.size();bool isPlalindrome = true;fo

9、r (int i = 0; i using namespace std;int main()int a, b, u, v, i, num;cinabuv;num = 0;for (i = a; i using namespace std;int main()const int SIZE = 100;int heightSIZE, numSIZE, n, ans;cinn;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 = nu

10、mi;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 nmp;for (i = 1; i xy;axy = 1;ans = 0;for (i = 1; i = (2) ; j-) /（2 分 ）aj = aj - 1;(3) = temp; /（2 分 ）事实上 ，还 有一 种更 好的 算法， 时间 复杂 度 为 O(n)、空间 复杂 度 为 O(

11、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 在当 前 子序列 中出 现的 次数cinn;for (i = 1; i ai;i = 1;j = 1;/i, j 分别表示 当前 子序 列的首 尾， 并保 证其 中至 多有两 个不 同整 数while (j = n) cur1 = ai;