建站宝盒免费下载,天津省网站制作厂家,扬州网站建设电话,网站seo关键字排序算法 前缀/后缀表达式 二进制补码、反码 最短路 图片/音频/视频文件格式 前序/中序/后序遍历 以比较作为基本运算#xff0c;在 N 个数中找最小数的最少运算次数为#xff08; #xff09;。 A. NNN B. N−1N-1N−1 C. N2N^2N2 D. logNlogNlogN 正确答案#xff1a; B …排序算法 前缀/后缀表达式 二进制补码、反码 最短路 图片/音频/视频文件格式 前序/中序/后序遍历 以比较作为基本运算在 N 个数中找最小数的最少运算次数为 。 A. NNN B. N−1N-1N−1 C. N2N^2N2 D. logNlogNlogN 正确答案 B 设 A 和 B 是两个长为 n 的有序数组现在需要将 A 和 B 合并成一个排好序的 数组请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做 次比较。 A. n2n^2n2 B. nlognnlognnlogn C. 2n2n2n D. 2n−12n-12n−1 正确答案D 某计算机的 CPU 和内存之间的地址总线宽度是 32 位bit这台计算机最多可以使用( )的内存。 正确答案 4GB 解析 地址总线宽度为32位,一次可以发送的一个数据是32位的则寻址的单元最大就是32位数据的最大值就是2的32次方。 232B222KB212MB22GB4GB2^{32}B2^{22}KB2^{12}MB2^2GB4GB232B222KB212MB22GB4GB 有 7 个一模一样的苹果放到 3 个一样的盘子中一共有 种放法。 正确答案8 将 7 个名额分给 4 个不同的班级允许有的班级没有名额有 种不 同的分配方案。 正确答案120 解析 排列组合 N个球放入M个盒子问题 总结 球盒子都可以分成不能区分和能区分还能分成是否能有空箱子所以一共是8种情况。 1.球同盒不同无空箱 Cn−1m−1C_{n-1}^{m-1}Cn−1m−1,nm 0,nm 使用插板法n个球中间有n-1个间隙现在要分成m个盒子而且不能有空箱子所以只要在n-1个间隙选出m-1个间隙即可 2.球同盒不同允许空箱 Cnm−1m−1C_{nm-1}^{m-1}Cnm−1m−1 我们在第1类情况下继续讨论我们可以先假设m个盒子里都放好了1个球所以说白了就是现在有mn个相同的球要放入m个不同的箱子没有空箱。也就是第1种情况 3.球不同盒相同无空箱 第二类斯特林数dp[n][m]dp[n][m]dp[n][m] dp[n][m]m×dp[n−1][m]dp[n−1][m−1]dp[n][m]m \times dp[n-1][m]dp[n-1][m-1]dp[n][m]m×dp[n−1][m]dp[n−1][m−1],1mn dp[k][k]1dp[k][k]1dp[k][k]1,k0 dp[k][0]0dp[k][0]0dp[k][0]0,k1 0,nm 这种情况就是第二类斯特林数我们来理解一下这个转移方程。 对于第n个球如果前面的n-1个球已经放在了m个箱子里那么现在第n个球放在哪个箱子都是可以的所以m×dp[n−1][m]m \times dp[n-1][m]m×dp[n−1][m]; 如果前n-1个球已经放在了m-1个箱子里那么现在第n个球必须要新开一个箱子来存放所以dp[n−1][m−1]dp[n-1][m-1]dp[n−1][m−1] 其他的都没法转移过来 4.球不同盒相同允许空箱 答案是∑i0mdp[n][i]\sum_{i0}^mdp[n][i]∑i0mdp[n][i] dp[n][m]dp[n][m]dp[n][m]为情况3的第二类斯特林数 这种情况就是在第3种情况的前提下去枚举使用的箱子的个数 5.球不同盒不同无空箱 dp[n][m]×fac[m]dp[n][m] \times fac[m]dp[n][m]×fac[m] dp[n][m]为情况3的第二类斯特林数,fac[m]为m的阶乘 因为球是不同的所以dp[n][m]得到的盒子相同的情况只要再给盒子定义顺序就等于现在的答案了 6.球不同盒不同允许空箱 mnm^nmn 每个球都有m种选择所以就等于mnm^nmn 7.球同盒同允许空箱 dp[n][m]dp[n][m−1]dp[n−m][m]dp[n][m]dp[n][m-1]dp[n-m][m]dp[n][m]dp[n][m−1]dp[n−m][m], nm dp[n][m]dp[n][m−1]dp[n][m]dp[n][m-1]dp[n][m]dp[n][m−1], nm 边界dp[k][1]1,dp[1][k]1,dp[0][k]1dp[k][1]1,dp[1][k]1,dp[0][k]1dp[k][1]1,dp[1][k]1,dp[0][k]1 现在有n个球和m个箱子我可以选择在所有箱子里面都放上1个球也可以不选择这个操作。 如果选择了这个操作那么就从dp[n−m][m]dp[n-m][m]dp[n−m][m]转移过来 如果没有选择这个操作那么就从dp[n][m−1]dp[n][m-1]dp[n][m−1]转移过来 8.球同盒同无空箱 dp[n−m][m]dp[n-m][m]dp[n−m][m], dp[][]dp[][]dp[][]同第7种情况,nm 0, nm 因为要求无空箱我们先在每个箱子里面放1个球然后还剩下n-m个球了,再根据情况7答案就出来了 由四个不同的点构成的简单无向连通图的个数是 。 正确答案38 解析 最多可加n∗(n−1)2\frac{n*(n-1)}{2}2n∗(n−1) 条边,最少可加n−1n-1n−1条边 个数即为C63−4C64C65C6638C_{6}^{3}-4C_{6}^{4}C_{6}^{5}C_{6}^{6}38C63−4C64C65C6638 为什么减4呢因为在6条边中选3条边会有4种不连通的情况 即3条边连了3个点构成一个环剩下的一个点被孤立显然此种情况不能成立 以下属于无线通信技术的有 。 A. 蓝牙 B. WiFi C. GPRS D. 以太网 正确答案ABC 可以将单个计算机接入到计算机网络中的网络接入通讯设备有 。 A. 网卡 B. 光驱 C. 鼠标 D. 显卡 正确答案A 解析 网卡是一块被设计用来允许计算机在计算机网络上进行通讯的计算机硬件。 光驱是电脑用来读写光碟内容的机器。 显卡将电脑的数字信息转成模拟信号让显示器显示出来。 一个 1×8 的方格图形不可旋转用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色且不允许两个黑格相邻共有_________种填涂方案。 正确答案55 解析 法一 设DP状态为F[i][0/1]F[i][0/1]F[i][0/1] 分别表示取到第 i 个格当前格是白/黑的方案数 最后答案为F[n][0]F[n][1]F[n][0] F[n][1]F[n][0]F[n][1] 转移 F[i][0]F[i−1][0]F[i−1][1]F[i][1]F[i−1][0]F[i][0] F[i-1][0] F[i-1][1]F[i][1] F[i-1][0]F[i][0]F[i−1][0]F[i−1][1]F[i][1]F[i−1][0] 法二 设DP状态为F[i]F[i]F[i] 分别表示取到第 i 个格的方案数 若当前格是白色的前一格颜色任意F[n]F[n−1]F[n]F[n-1]F[n]F[n−1] 若当前格是黑色的前一格是白色的F[n]F[n−2]F[n]F[n-2]F[n]F[n−2] 所以F[n]F[n−1]F[n−2]F[n]F[n-1]F[n-2]F[n]F[n−1]F[n−2]。这是一个斐波那契数列。 从2020年开始NOIP 竞赛将不再支持 Pascal 语言。 补充 到2020年除NOIP以外的赛事不再支持Pascalc 到2022年NOIP也不再支持PascalNOI赛事仅支持c 若 f[0] 0, f[1] 1, f[n 1] (f[n] f[n - 1]) / 2则随着 i 的增大f[i]将接近于( )。 A. 1/2 B. 2/3 C. (√5 − 1)/2 D. 1 正确答案 B 解析 令g[n]f[n]−f[n−1],n1,2,...令 g[n] f[n] - f[n-1], n1,2,...令g[n]f[n]−f[n−1],n1,2,... f[n1]×2f[n]f[n−1]f[n1]\times2f[n]f[n-1]f[n1]×2f[n]f[n−1] f[n1]−f[n]f[n−1]−f[n1]f[n1]-f[n]f[n-1]-f[n1]f[n1]−f[n]f[n−1]−f[n1] f[n1]−f[n]f[n−1]−(f[n]f[n−1])/2f[n1]-f[n]f[n-1]-(f[n]f[n-1])/2f[n1]−f[n]f[n−1]−(f[n]f[n−1])/2 f[n1]−f[n]−(f[n]−f[n−1])/2f[n1] - f[n] -(f[n] - f[n-1])/2f[n1]−f[n]−(f[n]−f[n−1])/2 即g[n1]−g[n]/2即 g[n1] -g[n]/2即g[n1]−g[n]/2 g[1]1g[1] 1g[1]1 故g[n](−2)1−n故 g[n] (-2)^{1-n}故g[n](−2)1−n g[n]g[n−1]...g[1]f[n]−f[0](−2)1−n...12/3×(1−(−2)−n)g[n] g[n-1] ... g[1] f[n] - f[0] (-2)^{1-n} ... 1 2/3 \times (1 - (-2)^{-n})g[n]g[n−1]...g[1]f[n]−f[0](−2)1−n...12/3×(1−(−2)−n) f[n]→2/3f[n] \rightarrow 2/3f[n]→2/3 小明要去南美洲旅游一共乘坐三趟航班才能到达目的地其中第 1 个航班 准点的概率是 0.9第 2 个航班准点的概率为 0.8, 第 3 个航班准点的概率为 0.9。如果存在第 i 个i1,2航班晚点第 i1 个航班准点则小明将赶不 上第 i1 个航班旅行失败除了这种情况其他情况下旅行都能成功。请 问小明此次旅行成功的概率是 。 A. 0.5 B. 0.648 C. 0.72 D. 0.74 正确答案D 解析 第一班晚点第二班准点的概率为0.1×0.80.080.1\times0.80.080.1×0.80.08不必考虑第三班第二班晚点第三班准点的概率为0.2×0.90.180.2\times0.90.180.2×0.90.18不必考虑第一班加起来为不能成功的概率即0.080.180.260.080.180.260.080.180.26用1减去这个概率即为答案即1−0.260.741-0.260.741−0.260.74 欢乐喷球儿童游乐场有个游戏叫“欢乐喷球”正方形场地中心能不断喷出彩色乒乓球以场地中心为圆心还有一 个圆形轨道轨道上有一列小火车在匀速运动火车有六节车厢。 假设乒乓球等概率落到正方形场地的每个地点包括火车车厢。小朋友玩这个游戏时只能坐在同一个火车车厢里可以在自己的车厢里捡落在该车厢内的所有乒乓球每个人每次游戏有三分钟时间则一个小朋友独自玩一次游戏期望可以得到 个乒乓球。假设乒乓球喷出的速度为 2 个/秒每节车厢的面积是整个场地面积的 1/20。 A. 60 B. 108 C. 18 D. 20 正确答案C 解析 一共有2 * 60 * 3360个球 360 / 2018个 以下是面向对象的高级语言的有 。 A. 汇编语言 B. C C. Fortran D. Java 正确答案BD 下列属于解释执行的程序设计语言是 A. C B. C C. Pascal D. Python 正确答案D 以下和计算机领域密切相关的奖项有 。 A. 奥斯卡奖 B. 图灵奖 C. 诺贝尔奖 D. 王选奖 正确答案BD 中国计算机学会于 年创办全国青少年计算机程序设计竞赛。 A. 1983 B. 1984 C. 1985 D. 1986 正确答案 B 如右图所示共有 13 个格子。对任何一个格子进行一 次操作会使得它自己以及与它上下左右相邻的格子中 的数字改变由 1 变 0或由 0 变 1。现在要使得所 有的格子中的数字都变为 0至少需要_________次操作。 正确答案3 如下图所示A 到 B 是连通的。假设删除一条细的边的代价是 1删除一条粗的边的代价是 2要让 A、B 不连通最小代价是(________)2 分最小代价的不同方案数是(_______)3 分。只要有一条删除的边不同就 是不同的方案 正确答案4 9 在一条长度为 1 的线段上随机取两个点则以这两个点为端点的线段的期望长度是 。 A. 1 / 2 B. 1 / 3 C. 2 / 3 D. 3 / 5 正确答案 B 解析 我们先考虑固定一个端点的情况如果左端点固定在了最左边那么答案为1/2既然左端点更大那么肯定答案会小于1/2因此只能是B 正解 法一 从0L任选一点x,0到x的线段长度期望为 ∫0LxL(12L2−1202)/L12L\frac{\int_0^Lx}{L}(\frac{1}{2}L^2-\frac{1}{2}0^2)/L\frac{1}{2}LL∫0Lx(21L2−2102)/L21L 于是从01任选一点x然后再选一点y与x的构成线段的期望长度为 [∫01(1−x1×1−x2x1×x2)]/1[\int_0^1(\frac{1−x}{1}\times\frac{1−x}{2}\frac{x}{1}\times\frac{x}{2})]/1[∫01(11−x×21−x1x×2x)]/1 ∫01(x2−x12)\int_0^1(x^2-x\frac{1}{2})∫01(x2−x21) (13×13−12×1212×1)−(0)(\frac{1}{3}\times1^3-\frac{1}{2}\times1^2\frac{1}{2}\times1)−(0)(31×13−21×1221×1)−(0) 13\frac{1}{3}31 法二 ps.这篇博客是有点问题的ansans/2ans/21/21/2/2应该是除以4 关于Catalan 数 Cn (2n)! / (n 1)! / n下列说法中错误的是 。 A. Cn 表示有n 1 个结点的不同形态的二叉树的个数。 B. Cn 表示含n 对括号的合法括号序列的个数。 C. Cn 表示长度为n 的入栈序列对应的合法出栈序列个数。 D. Cn 表示通过连接顶点而将n 2 边的凸多边形分成三角形的方法个数。 正确答案 A 解析卡特兰数详解 假设一台抽奖机中有红、蓝两色的球任意时刻按下抽奖按钮都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖假如他们的策略均为抽中蓝球则继续抽球抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里最终大箱子里的红球与蓝球的比例接近于 。 A. 1 : 2 B. 2 : 1 C. 1 : 3 D. 1 : 1 正确答案 D 解析 红球每个人都会抽一个。 蓝球设每个人抽S个 n趋于正无穷。 S021122223...n−12nS\frac {0}{2^1}\frac{1}{2^2}\frac{2}{2^3}...\frac{n-1}{2^n}S210221232...2nn−1 S2022123224...n−22nn−12n1\frac{S}{2}\frac {0}{2^2}\frac{1}{2^3}\frac{2}{2^4}...\frac{n-2}{2^n}\frac{n-1}{2^{n1}}2S220231242...2nn−22n1n−1 相减得到 S2122123124...12n−n−12n1\frac{S}{2}\frac{1}{2^2}\frac{1}{2^3}\frac{1}{2^4}...\frac{1}{2^n}-\frac{n-1}{2^{n1}}2S221231241...2n1−2n1n−1 S1S1S1 所以比例是1:1。 为了统计一个非负整数的二进制形式中 1 的个数代码如下 int CountBit(int x) { int ret 0; while (x) { ret; ___________; } return ret; } 则空格内要填入的语句是 。 A. x 1 B. x x - 1 C. x | x 1 D. x 1 正确答案 B 解析 每执行一次x x(x-1)会将x用二进制表示时最右边的一个1变为0 NOIP 初赛中选手可以带入考场的有 。 A. 笔 B. 橡皮 C. 手机关机 D. 草稿纸 正确答案 AB 2-3 树是一种特殊的树它满足两个条件 每个内部结点有两个或三个子结点 所有的叶结点到根的路径长度相同。 如果一棵2-3 树有10 个叶结点那么它可能有 个非叶结点。 A. 5 B. 6 C. 7 D. 8 正确答案 CD 解析 把10个叶结点分成几堆每堆有2或3个点同一个堆的点有相同的父亲 10222222233 对应5218或4217个非叶结点 下列关于图灵奖的说法中正确的有 。 A. 图灵奖是由电气和电子工程师协会IEEE设立的。 B. 目前获得该奖项的华人学者只有姚期智教授一人。 C. 其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵。 D. 它是计算机界最负盛名、最崇高的一个奖项有“计算机界的诺贝尔奖”之称。 正确答案 BCD 方程 a*b (a or b) * (a and b)在 a, b 都取 [0, 31] 中的整数时共有_____组解。*表示乘法or 表示按位或运算and 表示按位与运算 正确答案 454 解析 蒙一下当 (a or b)max(a,b) (a and b)min(a,b) 时等式成立此时二进制下一个数是另一个数的子集 ans2×(∑i05C5i×25−i)−25454ans2\times(\sum_{i0}^5 C_5^i\times2^{5-i})-2^5454ans2×(∑i05C5i×25−i)−25454 即枚举小的数有多少个1算出方案再减去重复的即两个数相同的情况。 设变量x为float型且已赋值则以下语句中能将x中的数值保留到小数点后两位并将第三位四舍五入的是 A. x (x * 1000. 5)/100. 0; B. x(int) (x * 1000. 5)/100. 0; C. x(x/1000. 5* 100. 0; D. xx*1000. 5/100. 0; 正确答案 B 解析运算符优先级 若某算法的计算时间表示为递推关系式 T(N) 2T(N / 2) N log N T(1) 1 则该算法的时间复杂度为 。 A. O(N)O(N)O(N) B. O(NlogN)O(N \log N)O(NlogN) C. O(Nlog2N)O(N \log^2 N)O(Nlog2N) D. O(N2)O(N^2)O(N2) 正确答案 C 解析T(N)2T(N/2)NlogNT(N)2T(N/2)NlogNT(N)2T(N/2)NlogN T(N)NT(N/2)N/2logN\frac{T(N)}{N}\frac{T(N/2)}{N/2}logNNT(N)N/2T(N/2)logN 时间复杂度为O(Nlog2N)O(Nlog^2N)O(Nlog2N) 在 Linux 系统终端中用于列出当前目录下所含的文件和子目录的命令为 。 A. ls B. cd C. cp D. all 正确答案A
