第十五届全国青少年信息学奥林匹克联赛试题及答案C语言

NOIP2009 第 十 五 届 全 国 青 少 年 信 息 学 奥 林 匹 克联 赛 初 赛 试 题 及 答 案 全 部 试 题 答 案 均 要 求 写 在 答 卷 纸 上 ， 写 在 试 卷 纸 上 一 律 无 效 一 .单 项 选 择 题 （ 共 10题 ， 每 题 1.5分 ， 共 计 15分 ， 每 题 有 且 仅 有 一 个 正 确 答 案 。 ）1、 关 于 图 灵 机 下 面 的 说 法 哪 个 是 正 确 的 ：A） 图 灵 机 是 世 界 上 最 早 的 电 子 计 算 机 。 B） 由 于 大 量 使 用 磁 带 操 作 ， 图 灵 机 运 行 速 度 很 慢 。 C） 图 灵 机 只 是 一 个 理 论 上 的 计 算 模 型 。D） 图 灵 机 是 英 国 人 图 灵 发 明 的 ， 在 二 战 中 为 破 译 德 军 的 密 码 发 挥 了 重 要 作 用 。2、 关 于 BIOS下 面 的 说 法 哪 个 是 正 确 的 ：A） BIOS是 计 算 机 基 本 输 入 输 出 系 统 软 件 的 简 称 。B） BIOS里 包 含 了 键 盘 、 鼠 标 、 声 卡 、 图 形 界 面 显 器 等 常 用 输 入 输 出 设 备 的 驱 动 程 序 。C） BIOS一 般 由 操 作 系 统 厂 商 来 开 发 完 成 。 D） BIOS能 提 供 各 种 文 件 拷 贝 、 复 制 、 删 除 以 及 目 录 维 护 等 文 件 管 理 功 能 。3、 已 知 大 写 字 母 A的 ASCII 编 码 为 65（ 十 进 制 ） ， 则 大 写 字 母 J的 十 六 进 制 ASCII编 码 为 ：A） 48 B） 49 C） 50 D） 以 上 都 不 是4、 在 字 长 为 16位 的 系 统 环 境 下 ， 一 个 16位 带 符 号 整 数 的 二 进 制 补 码 为 1111111111101101。 其 对 应 的 十进 制 整 数 应 该 是 ：A） 19 B） -19 C） 18 D） -18 5、 一 个 包 含 n个 分 支 结 点 （ 非 叶 结 点 ） 的 非 空 满 k叉 树 ， k=1， 它 的 叶 结 点 数 目 为 ：A） nk+1 B） nk-1 C） (k+1)n-1 D） (k-1)n+16、 表 达 式 a*(b+c)-d的 后 缀 表 达 式 是 ：A） abcd*+- B） abc+*d- C） abc*+d- D） -+*abcd7、 最 优 前 缀 编 码 ， 也 称 Huffman编 码 。 这 种 编 码 组 合 的 特 点 是 对 于 较 频 繁 使 用 的 元 素 给 与 较 短 的 唯 一 编码 ， 以 提 高 通 讯 的 效 率 。 下 面 编 码 组 合 哪 一 组 不 是 合 法 的 前 缀 编 码 ： A） （ 00， 01， 10， 11） B） （ 0， 1， 00， 11） C） （ 0， 10， 110， 111） D） （ 1， 01， 000， 001）8、 快 速 排 序 平 均 情 况 和 最 坏 情 况 下 的 算 法 时 间 复 杂 度 分 别 为 ：A） 平 均 情 况 O(nlog(2,n)， 最 坏 情 况 O(n2) B） 平 均 情 况 O(n)， 最 坏 情 况 O(n2)C） 平 均 情 况 O(n)， 最 坏 情 况 O(nlog(2,n) D） 平 均 情 况 O(log(2,n)， 最 坏 情 况 O(n2)9、 左 图 给 出 了 一 个 加 权 无 向 图 ， 从 顶 点 V0开 始 用 prim算 法 求 最 小 生 成 树 。 则 依 次 加 入 最 小 生 成 树 的 顶点 集 合 的 顶 点 序 列 为 ： A） V0， V1， V2， V3， V5， V4 B） V0， V1， V5， V4， V3， V3C） V1， V2， V3， V0， V5， V4 D） V1， V2， V3， V0， V4， V510、 全 国 信 息 学 奥 林 匹 克 的 官 方 网 站 为 参 与 信 息 学 竞 赛 的 老 师 同 学 们 提 供 相 关 的 信 息 和 资 源 ， 请 问 全 国 信息 学 奥 林 匹 克 官 方 网 站 的 网 址 是 ：A） / B） /C） / D） /二 .不 定 项 选 择 题 （ 共 10题 ， 每 题 1.5分 ， 共 计 15分 ， 每 题 正 确 答 案 的 个 数 不 少 于 1。 多 选 或 少 选 不 得 分 1、 关 于 CPU下 面 哪 些 说 法 是 正 确 的 ：A） CPU全 称 为 中 央 处 理 器 （ 或 中 央 处 理 单 元 ） 。 B） CPU能 直 接 运 行 机 器 语 言 。C） CPU最 早 是 由 Intel公 司 发 明 的 。 D） 同 样 主 频 下 ， 32位 的 CPU比 16位 的 CPU运 行 速 度 快 一 倍2、 关 于 计 算 机 内 存 下 面 的 说 法 哪 些 是 正 确 的 ：A） 随 机 存 储 器 （ RAM） 的 意 思 是 当 程 序 运 行 时 ， 每 次 具 体 分 配 给 程 序 的 内 存 位 置 是 随 机 而 不 确 定 的 。B） 一 般 的 个 人 计 算 机 在 同 一 时 刻 只 能 存 /取 一 个 特 定 的 内 存 单 元 。 C） 计 算 机 内 存 严 格 来 说 包 括 主 存 （ memory） 、 高 速 缓 存 （ cache） 和 寄 存 器 （ register） 三 个 部 分 。 D） 1MB内 存 通 常 是 指 1024*1024字 节 大 小 的 内 存 。3、 关 于 操 作 系 统 下 面 说 法 哪 些 是 正 确 的 ：A.多 任 务 操 作 系 统 专 用 于 多 核 心 或 多 个 CPU架 构 的 计 算 机 系 统 的 管 理 。B.在 操 作 系 统 的 管 理 下 ， 一 个 完 整 的 程 序 在 运 行 过 程 中 可 以 被 部 分 存 放 在 内 存 中 。C.分 时 系 统 让 多 个 用 户 可 以 共 享 一 台 主 机 的 运 算 能 力 ， 为 保 证 每 个 用 户 都 得 到 及 时 的 响 应 通 常 会 采 用 时 间片 轮 转 调 度 的 策 略 。 D.为 了 方 便 上 层 应 用 程 序 的 开 发 ， 操 作 系 统 都 是 免 费 开 源 的 。 4、 关 于 计 算 机 网 络 ， 下 面 的 说 法 哪 些 是 正 确 的 ：A） 网 络 协 议 之 所 以 有 很 多 层 主 要 是 由 于 新 技 术 需 要 兼 容 过 去 老 的 实 现 方 案 。B） 新 一 代 互 联 网 使 用 的 IPv6标 准 是 IPv5标 准 的 升 级 与 补 充 。C） TCP/IP是 互 联 网 的 基 础 协 议 簇 ， 包 含 有 TCP 和 IP等 网 络 与 传 输 层 的 通 讯 协 议 。D） 互 联 网 上 每 一 台 入 网 主 机 通 常 都 需 要 使 用 一 个 唯 一 的 IP地 址 ， 否 则 就 必 须 注 册 一 个 固 定 的 域 名 来 标 明其 地 址 。 5、 关 于 HTML下 面 哪 些 说 法 是 正 确 的 ：A） HTML全 称 超 文 本 标 记 语 言 ， 实 现 了 文 本 、 图 形 、 声 音 、 乃 至 视 频 信 息 的 统 一 编 码 。B） HTML不 单 包 含 有 网 页 内 容 信 息 的 描 述 ， 同 时 也 包 含 对 网 页 格 式 信 息 的 定 义 。C） 网 页 上 的 超 链 接 只 能 指 向 外 部 的 网 络 资 源 ， 本 网 站 网 页 间 的 联 系 通 过 设 置 标 签 来 实 现 。D） 点 击 网 页 上 的 超 链 接 从 本 质 上 就 是 按 照 该 链 接 所 隐 含 的 统 一 资 源 定 位 符 （ URL） 请 求 网 络 资 源 或 者 网络 服 务 。 6、 若 3个 顶 点 的 无 权 图 G的 邻 接 矩 阵 用 数 组 存 储 为 0， 1， 11， 0， 10， 1， 0， 假 定 在 具 体 存 储 中顶 点 依 次 为 ： v1， v2， v3 关 于 该 图 ， 下 面 的 说 法 哪 些 是 正 确 的 ：A） 该 图 是 有 向 图 。 B） 该 图 是 强 联 通 的 。C） 该 图 所 有 顶 点 的 入 度 之 和 减 所 有 顶 点 的 出 度 之 和 等 于 1。D） 从 v1开 始 的 深 度 优 先 遍 历 所 经 过 的 顶 点 序 列 与 广 度 优 先 的 顶 点 序 列 是 相 同 的 。7、 在 带 尾 指 针 （ 链 表 指 针 clist指 向 尾 结 点 ） 的 非 空 循 环 单 链 表 中 每 个 结 点 都 以 next字 段 的 指 针 指 向 下 一 个 节 点 。 假 定 其 中 已 经 有 了 2个 以 上 的 结 点 。 下 面 哪 些 说 法 是 正 确 的 ： A） 如 果 p指 向 一 个 待 插 入 的 新 结 点 ， 在 头 部 插 入 一 个 元 素 的 语 句 序 列 为 ： p.next:=clist.next;clist.next:=p;B） 如 果 p指 向 一 个 待 插 入 的 新 结 点 ， 在 尾 部 插 入 一 个 元 素 的 语 句 序 列 为 ： p.next:=clist;clist.next:=p;C） 在 头 部 删 除 一 个 结 点 的 语 句 序 列 为 ： p:=clist.next;clist.next:=clist.next.next;dispose(p);D） 在 尾 部 删 除 一 个 结 点 的 语 句 序 列 为 ： p:=clist;clist:=clist.next;dispose(p);8、 散 列 表 的 地 址 区 间 为 0-10， 散 列 函 数 为 H(K)=K mod 11。 采 用 开 地 址 法 的 线 性 探 查 法 处 理 冲 突 ， 并 将关 键 字 序 列 26， 25， 72， 38， 8， 18， 59存 储 到 散 列 表 中 ， 这 些 元 素 存 入 散 列 表 的 顺 序 并 不 确 定 。 假 定 之 前 散 列 表 为 空 ， 则 元 素 59存 放 在 散 列 表 中 的 可 能 地 址 有 ：A） 5 B） 7 C） 9 D） 109、 排 序 算 法 是 稳 定 的 意 思 是 关 键 码 相 同 的 记 录 排 序 前 后 相 对 位 置 不 发 生 改 变 ， 下 列 哪 些 排 序 算 法 是 稳 定 的 ：A） 插 入 排 序 B） 基 数 排 序 C） 归 并 排 序 D） 冒 泡 排 序10、 在 参 加 NOI系 列 竞 赛 过 程 中 ， 下 面 哪 些 行 为 是 被 严 格 禁 止 的 ：A） 携 带 书 写 工 具 ， 手 表 和 不 具 有 通 讯 功 能 的 电 子 词 典 进 入 赛 场 。 B） 在 联 机 测 试 中 通 过 手 工 计 算 出 可 能 的 答 案 并 在 程 序 里 直 接 输 出 答 案 来 获 取 分 数 。C） 通 过 互 联 网 搜 索 取 得 解 题 思 路 。 D） 在 提 交 的 程 序 中 启 动 多 个 进 程 以 提 高 程 序 的 执 行 效 率 。三 .问 题 求 解 （ 共 2题 ， 每 空 5分 ， 共 计 10分 ）1.拓 扑 排 序 是 指 将 有 向 无 环 图 G中 的 所 有 顶 点 排 成 一 个 线 性 序 列 ， 使 得 图 中 任 意 一 对 顶 点 u和 v， 若 E(G)， 则 u在 线 性 序 列 中 出 现 在 v之 前 ， 这 样 的 线 性 序 列 成 为 拓 扑 序 列 。 如 下 的 有 向 无 环 图 ， 对 其 顶点 做 拓 扑 排 序 ， 则 所 有 可 能 的 拓 扑 序 列 的 个 数 为 _。 2、 某 个 国 家 的 钱 币 面 值 有 1， 7， 72， 73共 计 四 种 ， 如 果 要 用 现 金 付 清 10015元 的 货 物 ， 假 设 买 卖双 方 各 种 钱 币 的 数 量 无 限 且 允 许 找 零 ， 那 么 交 易 过 程 中 至 少 需 要 流 通 _张 钱 币 。四 .阅 读 程 序 写 结 果 （ 共 4题 ， 每 题 8分 ， 共 计 32分 ）1 #includeinta,b;intwork(inta,intb)if(a%b)returnwork(b,a%b); returnb;intmain()scanf(“%d%d“,printf(“%dn“,work(a,b);return0;输 入 ：123321输 出 ： _2 #includeintmain() inta4,b4;inti,j,tmp;for(i=0;i#definemaxn50constinty=2009;intmain()intn,cmaxnmaxn,i,j,s=0;scanf(“%d“,c00=1;for(i=1;iintmain()intn,m,i,j,p,k;inta100,b100;scanf(“%d%d“, a0=n;i=0;p=0;k=0;dofor(j=0;jinta101;intn,i,ans,len,tmp,beg,end;intmain()scanf(“%d“,for(i=1;ians)ans=tmp+ai;len=i-beg;elseif(if(tmp+ai)beg=;tmp=0;else ;printf(“%d%dn“,ans,len);return0;2.(寻 找 等 差 数 列)有 一 些 长 度 相 等 的 等 差 数 列 （ 数 列 中 每 个 数 都 为059的 整 数 ） ， 设 长 度 均 为L， 将 等 差 数 列 中 的 所 有 数 打 乱 顺 序 放 在 一 起 。 现 在 给 你 这 些 打 乱 后 的 数 ， 问 原 先 ，L最 大 可 能 为 多 大 ？ 先 读 入 一 个 数n（1inthash60;intn,x,ans,maxnum;intwork(intnow)intfirst,second,delta,i;intok;while(if(nowmaxnum) return1;first=now;for(second=first;secondmaxnum)break;if(delta=0)ok=();elseok=1;for(i=0;imaxnum)maxnum