信息学竞赛真题

一 单项选择题 共 15 题 每题 1 5 分 共计 22 5 分 每题有且仅有一个正确选项 1 从 年开始 NOIP 竞赛将不再支持 Pascal 语言 A 2020 B 2021 C 2022 D 2023 2 在 8 位二进制补码中 10101011 表示的数是十进制下的 A 43 B 85 C 43 D 84 3 分辨率为 1600 x900 16 位色的位图 存储图像信息所需的空间为 A 2812 5KB B 4218 75KB C 4320KB D 2880KB 4 2017 年 10 月 1 日是星期日 1949 年 10 月 1 日是 A 星期三 B 星期日 C 星期六 D 星期二 5 设 G 是有 n 个结点 m 条边 n m 的连通图 必须删去 G 的 条边 才能使得 G 变 成一棵树 A m n 1 B m n C m n 1 D n m 1 6 若某算法的计算时间表示为递推关系式 T N 2T N 2 NlogN T 1 1 则该算法的时间复杂度为 A O N B O NlogN C O N log2N D O N2 7 表达式 a b c d 的后缀形式是 A abcd B abc d C a bc d D b c a d 8 由四个不同的点构成的简单无向连通图的个数是 A 32 B 35 C 38 D 41 9 将 7 个名额分给 4 个不同的班级 允许有的班级没有名额 有 种不同的分配方案 A 60 B 84 C 96 D 120 10 若 f 0 0 f 1 1 f n 1 f n f n 1 2 则随着 i 的增大 f i 将接近与 A 1 2 B 2 3 D 1 11 设 A 和 B 是两个长为 n 的有序数组 现在需要将 A 和 B 合并成一个排好序的数组 请 问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 次比较 A n2 B nlogn C 2n D 2n 1 12 在 n n 3 枚硬币中有一枚质量不合格的硬币 质量过轻或质量过重 如果只有一架天 平可以用来称重且称重的硬币数没有限制 下面是找出这枚不合格的硬币的算法 请把 a c 三行代码补全到算法中 a A XUY b A Z c n A 算法 Coin A n 1 k n 3 2 将 A 中硬币分成 X Y Z 三个集合 使得 X Y k Z n 2k 3 if W X W Y W X W Y 分别为 X 或 Y 的重量 4 then 5 else 6 7 if n 2 then goto 1 8 if n 2 then 任取 A 中 1 枚硬币与拿走硬币比较 若不等 则它不合格 若相等 则 A 中 剩下的硬币不合格 9 if n 1 then A 中硬币不合格 正确的填空顺序是 A b c a B c b a C c a b D a b c 13 在正实数构成的数字三角形排列形式如图所示 第一行的数为 a11 第二行的数从左到 右依次为 a21 a22 第 n 行的数为 an1 an2 ann 从 a11 开始 每一行的数 aij 只有两条 边可以分别通向下一行的两个数 a i 1 j 和 a i 1 j 1 用动态规划算法找出一条从 a11 向下 通到 an1 an2 ann 中某个数的路径 使得该路径上的数之和达到最大 令 C i j 是从 a11 到 aij 的路径上的数的最大和 并且 C i 0 C 0 j 0 则 C i j A max C i 1 j 1 C i 1 j aij B C i 1 j 1 c i 1 j C max C i 1 j 1 C i 1 j 1 D max C i j 1 C i 1 j aij 14 小明要去南美洲旅游 一共乘坐三趟航班才能到达目的地 其中第 1 个航班准点的概 率是 0 9 第 2 个航班准点的概率为 0 8 第 3 个航班准点的概率为 0 9 如果存在第 i 个 i 1 2 航班晚点 第 i 1 个航班准点 则小明将赶不上第 i 1 个航班 旅行失败 除了这 种情况 其他情况下旅行都能成功 请问小明此次旅行成功的概率是 A 0 5 B 0 648 C 0 72 D 0 74 15 欢乐喷球 儿童游乐场有个游戏叫 欢乐喷球 正方形场地中心能不断喷出彩色乒乓 球 以场地中心为圆心还有一个圆轨道 轨道上有一列小火车在匀速运动 火车有六节车 厢 假设乒乓球等概率落到正方形场地的每个地点 包括火车车厢 小朋友玩这个游戏时 只能坐在同一个火车车厢里 可以在自己的车厢里捡落在该车厢内的所有乒乓球 每个人 每次游戏有三分钟时间 则一个小朋友独自玩一次游戏期望可以得到 个乒乓球 假设乒 乓球喷出的速度为 2 个 秒 每节车厢的面积是整个场地面积的 1 20 A 60 B 108 C 18 D 20 二 不定项选择题 共 5 题 每题 1 5 分 共计 7 5 分 每题有一个或多个正确选项 多选 或少选均不得分 1 以下排序算法在最坏情况下时间复杂度最优的有 A 冒泡排序 B 快速排序 C 归并排序 D 堆排序 2 对于入栈顺序为 a b c d e f g 的序列 下列 不可能是合法的出栈序列 A a b c d e f g B a d c b e g f C a d b c g f e D g f e d c b a 3 下列算法中 是稳定的排序算法 A 快速排序 B 堆排序 C 希尔排序 D 插入排序 4 以下是面向对象的高级语言的是 A 汇编语言 B C C Fortan D Java 5 以下和计算机领域密切相关的奖项是 A 奥斯卡奖 B 图灵奖 C 诺贝尔奖 D 王选奖 三 问题求解 共 2 题 每题 5 分 共计 10 分 1 如图所示 共有 13 个格子 对任何一个格子进行一次操作 会使得它自己以及与它上 下左右相邻的格子中的数字改变 由 1 变 0 或由 0 变 1 现在要使得所有的格子中的数 字都变为 0 至少需要 3 次操作 2 如图所示 A 到 B 是连通的 假设删除一条细的边的代价是 1 删除一条粗的边的代价 是 2 要让 A B 不连通 最小代价是 4 2 分 最小代价的不同方案数是 9 3 分 只要有一条删除的边不同 就是不同的方案 四 阅读程序写结果 共 4 题 每题 8 分 共计 32 分 1 include using namespacestd int g int m intn int x int ans 0 int i if n 1 return 1 for i x i m n cout g m n 0 endl return 0 输入 8 4 输出 15 2 include using namespacestd int main int n i j x y nx ny int a 40 40 for i 0 i 40 i for j 0 j n y 0 x n 1 n 2 n 1 for i 1 i n n i a y x i ny y 1 n n nx x 1 n if y 0 else y ny x nx for j 0 j n j cout a 0 j cout endl return 0 输入 3 输出 17 24 1 8 15 3 include using namespacestd int n s a 100005 t 100005 i void mergesort intl int r if l r return int mid l r 2 int p l int i l int j mid 1 mergesort l mid mergesort mid 1 r while i mid t p a j p j else t p a i p i while i mid t p a i p i while j r t p a j p j for i l i n for i 1 i a i mergesort 1 n cout s n m int x 1 int y 1 int dx 1 int dy 1 int cnt 0 while cnt 2 cnt 0 x x dx y y dy if x 1 x n cnt dx dx if y 1 y m cnt dy dy cout x y n for i 0 i c p i c 0 cin q rest p 0 i 1 while rest q i if rest q cout 0 endl else cout rest q while i n rest rest q 10 p i i cout rest q cout endl cout rest q n m for i 0 i n i for j 0 j n j graph i j 0 for i 0 i n i degree i 0 for i 0 i a b graph a b 1 degree b tail 0 for i 0 i n i if degree i 0 queue tail i tail head 0 while tail n 1 for i 0 i n i if graph queue head i 1 degree i if degree i 0 queue tail i tail head ans 0 for i 0 i n i a queue i len a 1 for j 0 j len a len a len j 1 if ans len a ans len a cout ans endl return 0