NOIP2017提高组初赛模拟题

1 第二十三届全国青少年信息学奥林匹克联赛初赛 提高组 PASCAL 语言模拟试题 竞赛时间 2017 年 10 月 14 日 14 30 16 30 选手注意 试题纸共有 13 页 答题纸共有 2 页 满分 100 分 请在答题纸上作答 写 在试题纸上的一律无效 不得使用任何电子设备 如计算器 手机 电子词典等 或查阅任何书籍资料 一 单项选择题 共 15 题 每题 1 5 分 共计 22 5 分 每题有且仅有一个正 确 选项 1 1956 年 授予肖克利 William Shockley 巴丁 John Bardeen 和 布拉顿 Walter Brattain 以表彰他们对半导体的研究和晶体管效应的发 现 A 诺贝尔物理学奖 B 约翰 冯 诺依曼奖 C 图灵奖 D 高德纳奖 Donald E Knuth Prize 2 如果开始时计算机处于小写输入状态 现在有一只小老鼠反复按照 CapsLock 字母键 A 字母键 S 和字母键 D 的顺序来回按键 即 CapsLock A S D S A CapsLock A S D S A CapsLock A S D S A 屏幕上输出的第 81 个字符是字母 A S D A 3 二进制数 00101100 和 01010101 异或的结果是 00101000 01111001 01000100 00111000 4 与二进制小数 0 1 相等的八进进制数是 0 8 0 4 0 2 0 1 5 以比较作为基本运算 在 N 个数中找最小数的最少运算次数为 N N 1 N2 log N 6 表达式 a b c d 的后缀表达形式为 abcd abc d abc d abcd 7 一棵二叉树如右图所示 若采用二叉树链表存储该二叉 树 各个结点包括结点的数据 左孩子指针 右孩子指 针 如果没有左孩子或者右孩子 则对应的为空指针 那么该链表中空指针的数目为 A 6 B 7 C 12 14 8 G 是一个非连通简单无向图 共有 28 条边 则该图至少有 个顶点 10 9 8 7 2 9 某计算机的 CPU 和内存之间的地址总线宽度是 32 位 bit 这台计算机 最 多可以使用 的内存 A 2GB B 4GB C 8GB D 16GB 10 无论是 TCP IP 模型还是 OSI 模型 都可以视为网络的分层模型 每个网络协 议都会被归入某一层中 如果用现实生活中的例子来比喻这些 层 以下最恰 当的是 A 中国公司的经理与波兰公司的经理交互商业文件 B 军队发布命令 C 国际会议中 每个人都与他国地位对等的人直接进行会谈 3 D 体育比赛中 每一级比赛的优胜者晋级上一级比赛 11 有 7 个一模一样的苹果 放到 3 个一样的盘子中 一共有 种放法 7 8 21 3 7 12 Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号 下图是他们 之间的关系图 两个人之间有边相连代表这两个人是朋友 没有边相连代表 不是朋友 这个社交网站的规则是 如果某人 A 向他 她 的朋友 B 分享了 某张照片 那么 B 就可以对该照片进行评论 如果 B 评论了该照片 那么他 她 的所有朋友都可以看见这个评论以及被评论的照片 但是不能对该照 4 片进行评论 除非 A 也向他 她 分享了该照片 现在 Lucia 已经上传了 一张照片 但是她不想让 Jacob 看见这张照片 那么她可以向以下朋友 分 享该照片 Dana Michael Eve Dana Eve Monica Michael Eve Jacob Micheal Peter Monica 13 周末小明和爸爸妈妈三个人一起想动手做三道菜 小明负责洗菜 爸爸负责 切 菜 妈妈负责炒菜 假设做每道菜的顺序都是 先洗菜 10 分钟 然后切 菜 10 分钟 最后炒菜 10 分钟 那么做一道菜需要 30 分钟 注意 两道不 同的菜 的相同步骤不可以同时进行 例如第一道菜和第二道的菜不能同时洗 也不能同时切 那么做完三道菜的最短时间需要 分钟 A 90 B 60 C 50 D 40 14 假设某算法的计算时间表示为递推关系式 T n 2T 4n T 1 1 则算法的时间复杂度为 A O n B O C O logn D O n2 n 15 给定含有 n 个不同的数的数组 L 如果 L 中存在 x i 1 i n 使 得 x 1 x2 xi 1 xi 1 xn 则称 L 是单峰的 并称 x i 是 L 的 峰顶 现在已知 L 是单峰的 请把 a c 三行代码补全到算法中使得算法 正确找到 L 的峰顶 a Search k 1 n b Search 1 k 1 c return L k Search 1 n 1 k n 2 2 if L k L k 1 and L k L k 1 3 then 4 else if L k L k 1 and L k L k 1 5 then 6 else 正确的填空顺序是 A c a b B c b a C a b c D b a c 二 不定项选择题 共 5 题 每题 1 5 分 共计 7 5 分 每题有一个或多个 正确 选项 多选或少选均不得分 5 1 以下属于无线通信技术的有 A 蓝牙 B WiFi C GPRS D 以太网 2 可以将单个计算机接入到计算机网络中的网络接入通讯设备有 A 网卡 B 光驱 C 鼠标 D 显卡 3 下列算法中运用分治思想的有 A 快速排序 B 归并排序 C 冒泡排序 D 计数排序 4 下图表示一个果园灌溉系统 有 A B C D 四个阀门 每个阀门可以打开 或 关上 所有管道粗细相同 以下设置阀门的方法中 可以让果树浇上水的 有水 有水 果树 有 A B 打开 其他都关上 B AB 都打开 CD 都关上 C A 打开 其他都关上 D D 打开 其他都关上 5 参加 NOI 比赛 以下能带入考场的有 A 钢笔 B 适量的衣服 C U 盘 D 铅笔 三 问题求解 共 2 题 每题 5 分 共计 10 分 每题全部答对得 5 分 没有 部分分 1 在 1 和 2015 之间 包括 1 和 2015 在内 不能被 4 5 6 三个数任意一个 数整除的数有 个 2 结点数为 5 的不同形态的二叉树一共有 种 结点数为 2 的二 叉树一共有 2 种 一种是根结点和左儿子 另一种是根结点和右儿子 四 阅读程序写结果 共 4 题 每题 8 分 共计 32 分 1 Const SIZE 100 6 var n i sum x integer a array 1 SIZE of integer begin readln n fillchar a sizeof a 0 for i 1 to n do begin read x inc a x end i 0 sum 0 while sum n div 2 1 do begin inc i sum sum a i end writeln i end 输入 11 4 5 6 6 4 3 3 2 3 2 1 输出 2 var n integer procedure f2 x y integer forward procedure f1 x y integer begin if x ans then ans len for i 1 to n do if not visited i and e x i 1 then dfs i len e x i visited x false end begin readln n m for i 1 to n do for j 1 to n do e i j 1 for i 1 to m do begin readln a b c e a b c e b a c end for i 1 to n do visited i false ans 0 for i 1 to n do dfs i 0 writeln ans end 输入 4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60 输出 8 4 const SIZE 10000 LENGTH 10 var sum longint n m i j integer a array 1 SIZE 1 LENGTH of integer function h u v integer integer var ans i integer begin ans 0 for i 1 to n do if a u i a v i then inc ans h ans end begin readln n filichar a sizeof a 0 m 1 repeat i 1 while i n then break inc m a m i 1 for j i 1 to n do a m j a m 1 j until false sum 0 for i 1 to m do for j 1 to m do sum sum h i j writeln sum end 输入 7 输出 五 完善程序 共 2 题 每题 14 分 共计 28 分 1 双子序列最大和 给定一个长度为 n 3 n 1000 的整数序列 要求从 中选出两个连续子序列 使得这两个连续子序列的序列和之和最大 最终只需输出这个 9 最大和 一个连续子序列的序列和为该连续子序列中所有数之和 要求 每个连续子序 列长度至少为 1 且两个连续子序列之间至少间隔 1 个数 第五空 4 分 其余 2 5 分 const MAXN 1000 var n i ans sum longint x array 1 MAXN of longint lmax array 1 MAXN of longint lmax i 为仅含 x i 及 x i 左侧整数的连续子序列的序列和中 最大的序列和 rmax ar ray 1 MAXN of longint rmax i 为仅含 x i 及 x i 右侧整数的连续子序列的序列和中 最大的序列和 begin read n fori 1 to n do read x i lmax 1 x 1 fori 2 to n do if lmax i 1 0 then lmax i x i else lmax i lmax i 1 x i fori 2 to n do if lmax i lmax i 1 then lmax i lmax i 1 1 fori n 1 downto 1 do if rmax i 1 0 then 2 Else 3 fori n 1 downto 1 do if rmax i ans then ans sum end writeln ans end 2 最短路径问题 无向连通图 G 有 n 个结点 依次编号为 1 2 3 n 用邻接 矩阵的形式给出每条边的边长 要求输出以结点 1 为起点出发 到各结点的最短路径长 度 使用 Dijkstra 算法解决该问题 利用 dist 数组记录当前各结点与起点的已找到的 最短路径长度 每次从未扩展的结点中选取 dist 值最小的结点 v 进行扩展 更新与 v 相 邻的结点的 dist 值 不断进行上述操作直至所有结点均被扩展 此时 dist 数据中记录 的值即为各结点与起点的最短路径长度 第五空 2 分 其余 3 分 10 const MAXV 100 var n i j v longint w array 1 MAXV 1 MAXV of longint 邻接矩阵 记录边长 其中 w i j 为连 接结点 i 和结点 j 的无向边长度 若无边则为 1 dist array 1 MAXV of longint used array 1 MAXV of longint 记录结点是否已扩展 0 未扩展 1 已扩展 begin read n for i 1 to n do for j 1 to n do read w i j dist 1 0 for i 2 to n do dist i 1 for i 1 to n do used i 0 while true do begin 1 for i 1 to n do if used i 1 and dist i 1 and v 1 or 2 then 3 if v 1 then break 4 For i 1 to n do if w v i 1 and dist i 1 or 5 then dist i dist v w v i end for i 1 to n do writeln dist i end