初赛模拟试题(一)

NOIP20100 初赛模拟试题 一 普及普及 Pascal 语言语言 二小时完成二小时完成 全部试题答案均要求写在答卷纸上 写在试卷纸上一律无效全部试题答案均要求写在答卷纸上 写在试卷纸上一律无效 一 一 单项选择题单项选择题 共 共 10 题 每题题 每题 1 5 分 共计分 共计 15 分 每题有且仅有一个正确答案 分 每题有且仅有一个正确答案 1 建立了计算机最主要的结构原理的人是 A 图灵 B 比尔 盖茨 C 冯 诺伊曼 D 克拉拉 丹 E 哥德尔 2 设 a b c 是三个布尔型 boolean 的变量 则表达式 a b b c c a a a b b 的值 A 始终为 true B 始终为 false C 当且仅当 c 为 true 时为 false D 当且仅当 a 与 b 均为 true 时为 true E 依赖于 a b c 三者的值 3 设 a b 为两个浮点 float 型变量 下面的表达式中最有可能为真的是 A a b B a a 2 a b b b a b a b C a b a b b b a a 1 它的叶结点数目为 A nk 1 B nk 1 C k 1 n 1 D k 1 n 1 6 表达式 a b c d 的后缀表达式是 A abcd B abc d C abc d D abcd 7 最优前缀编码 也称 Huffman 编码 这种编码组合的特点是对于较频繁使用的元素给 与较短的唯一编码 以提高通讯的效率 下面编码组合哪一组不是合法的前缀编码 A 00 01 10 11 B 0 1 00 11 C 0 10 110 111 D 1 01 000 001 8 快速排序平均情况和最坏情况下的算法时间复杂度分别为 A 平均情况 O nlog2n 最坏情况 O n2 B 平均情况 O n 最坏情况 O n2 C 平均情况 O n 最坏情况 O nlog2n D 平均情况 O log2n 最坏情况 O n2 9 佳佳在网上购买了一个空间 建设了一个网站 那么 他向网站上上传网页时最有可能 采用的网络协议是 A HTTP B TCP C POP3 D FTP E BT 10 一个音乐爱好者收藏有 100 首 MP3 格式的音乐 这些音乐的编码率都是 192Kbps 平 均每首音乐的时长为 3min 他要通过网络将这些音乐传送给另一个人 假设网络速度恒定 为 512KB s 则他传送这些音乐大概需要 A 72s B 843s C 112 5min D 3h48min16s E 超过 24 小时 二二 不定项选择题不定项选择题 共共 10 题题 每题每题 1 5 分分 共计共计 15 分 每题正确答案的个数不少于分 每题正确答案的个数不少于 1 多选或少选均不得分 多选或少选均不得分 1 7f 16 10010101 2 的运算结果等于 A 114 16 B 276 10 C 100010100 2 D 11d 16 E 731 8 2 设 a b c 是三个布尔 boolean 型变量 若表达式 a b c 为 true 则下列表达式 一定为 true 的是 A a b c a B b a a c c b C a b c D b a a b E 以上皆错 3 下面的前序遍历结果不可能是由一棵排序二叉树产生的有 A 1 2 3 4 5 6 7 8 B 1 4 3 6 7 8 5 2 C 8 7 6 5 4 3 2 1 D 6 7 8 5 4 3 2 1 E 以上皆错 4 设想这样一种数据结构 它有 PUSH 和 POP 两个操作 其中 PUSH 操作就是将一个元 素加入到这个数据结构中 而当第 k 次调用 POP 元素时 保证这个数据结构中有元素 选择其中的一个元素返回并删除 若 k 是奇数 选择的是元素中的最大值 若 k 是偶数 选择的是元素中的最小值 如果调用 PUSH 操作放入数据结构中的元素依次是 1 2 3 4 5 6 则下列序列中可能通过适当的 POP 操作产生的有 A 1 2 3 4 5 6 B 1 2 3 4 6 5 C 6 1 5 2 4 3 D 2 1 6 3 5 4 E 3 1 4 2 6 5 5 下面的软件必须在联网状态下才能正常使用的有 A BitTorrent B Mozilla Firefox C Red Hat Linux D MSN Messenger E WinZip 6 若 3 个顶点的无权图 G 的邻接矩阵用数组存储为 0 1 1 1 0 1 0 1 0 假定在具体存储中顶点依次为 v1 v2 v3 关于该图 下面的说法哪些是正确的 A 该图是有向图 B 该图是强连通的 C 该图所有顶点的入度之和减所有顶点的出度之和等于 1 D 从 v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的 7 下面的硬件接口中既不可以连接声卡 又不可以连接鼠标的通讯设备或外设接口有 A PCI B USB C BlueTooth D 红外 E 以上皆错 8 散列表的地址区间为 0 10 散列函数为 H K K mod 11 采用开地址法的线性探查法处 理冲突 并将关键字序列 26 25 72 38 8 18 59 存储到散列表中 这些元素存入 散列表的顺序并不确定 假定之前散列表为空 则元素 59 存放在散列表中的可能地址 有 A 5 B 7 C 9 D 10 9 排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变 下列哪些排 序算法是稳定的 A 插入排序 B 基数排序 C 归并排序 D 冒泡排序 10 在参加 NOI 系列竞赛过程中 下面哪些行为是被严格禁止的 A 携带书写工具 手表和不具有通讯功能的电子词典进入赛场 B 在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数 C 通过互联网搜索取得解题思路 D 在提交的程序中启动多个进程以提高程序的执行效率 三 问题求解 共三 问题求解 共 2 题 每空题 每空 5 分 共计分 共计 10 分 分 1 有五个工人 A B C D E 需要做工作一 二 三 四 五 下表显示了每个人 做每项工作所要花费的最短时间 则完成所有 5 项工作所需要的最短时间是 说明 不同的工作可以由不同的人同时做 但同一个工作只能由 一个人来完成 ABCDE 一75864 二43546 三58673 四67345 五43653 2 某个国家的钱币面值有 1 7 72 73共计四种 如果要用现金付清 10015 元的货物 假设买卖双方各种钱币的数量无限且允许找零 那么交易过程中至少需要流通 张钱 币 四 阅读程序写结果 共四 阅读程序写结果 共 4 题 每题题 每题 8 分 共计分 共计 32 分 分 1 program t1 var a real i j t n ans longint begin readln n for i 1 to n do begin readln a t for j 1 to t do ans ans xor trunc a j end writeln ans end 读入 3 1 6 3 2 6 1 1 0 2 输出 2 program t2 var a array 0 9 of longint n i j x longint begin a 0 1 for i 1 to 9 do a i a i 1 i read x while x 0 do begin if x 0 then write N else begin for i 9 downto 0 do if a i x then x x a i if x 0 then write Y else write N end read x end end 读入 10 30 729 5048 1 输出 3 program t3 const n 200 var si pr set of 2 n x j m integer begin readln m si 2 m pr x 2 repeat while not x in si do x succ x pr pr x j x while j m do begin si si j j j x end until si j 0 for x m downto 2 do if x in pr then begin write x 5 inc j if j mod 10 0 then writeln end writeln end 输入 50 输出 4 program t4 var a array 1 9 1 9 of string st x string i j n m integer begin repeat writeln please input a string length 10 readln st n length st until n b then g gcd a b else a a div g b b div g a a mod b work a b end 2 题目描述 在一个果园里 多多已经将所有的果子打了下来 而且按果子的不同种类分 成了不同的堆 多多决定把所有的果子合成一堆 每一次合并 多多可以把两堆果子合并到一起 消耗的体力等于两堆果子的重量之和 可以看出 所有的果子经过 n 1 次合并之后 就只剩下一堆了 多多在合并果子时总共消 耗的体力等于每次合并所耗体力之和 因为还要花大力气把这些果子搬回家 所以多多在合并果子时要尽可能地节省体力 假定 每个果子重量都为 1 并且已知果子的种类数和每种果子的数目 你的任务是设计出合并 的次序方案 使多多耗费的体力最少 并输出这个最小的体力耗费值 例如有 3 种果子 数目依次为 1 2 9 可以先将 1 2 堆合并 新堆数目为 3 耗费体 力为 3 接着 将新堆与原先的第三堆合并 又得到新的堆 数目为 12 耗费体力为 12 所以多多总共耗费体力 3 12 15 可以证明 15 为最小的体力耗费值 输入 输入包括两行 第一行是一个整数 n 1 n 10000 表示果子的种类数 第二 行包含 n 个整数 用空格分隔 第 i 个整数 ai 1 ai 20000 是第 i 种果子的数目 输出 输出包括一行 这一行只包含一个整数 也就是最小的体力耗费值 输入数据保 证这个值小于 2 31 program fill2 var s1 s2 array 0 15000 of longint s1low s1hi s2low s2hi integer r l s x i min1 min2 longint function peeksmall longint begin min1 1000000000 min2 1000000000 if s1lows1hi then min1 s1 s1low if s2lows2hi then min2 s2 s2low if then begin peeksmall s1 s1low inc s1low end else begin peeksmall s2 s2low inc s2low end end procedure swap l integer r integer var tmp longint begin tmp s1 r s1 r s1 l s1 l tmp end procedure sort low integer hi integer var l longint begin if low hi then else x s1 low hi div 2 swap low l low r hi while l r