选择题15题每题2分继续来写csp-j初赛的有关内容。分析文件型病毒基本都是通过感染可执行文件来运行的因为感染文本文件无法自动运行。但是“可执行文件”范围太广大多都是exe和com文件。故此选择D。分析常识问题选C即可。分析内存地址是内存中每个存储单元对应的编号每一个内存地址唯一对应一块内存存储单元这是它最核心、最重要的特点。选择B。分析还是常识问题通过名字或者看看我们的电脑就知道了选C。分析最早的计算机是ENIAC,被用于军事领域的复杂计算旨在满足美国军方在炮弹弹道计算方面的需求选择A。分析这也是常识问题不过学过asm的小伙伴应该都知道寄存器比如rspecx是暂时存放数据的单元速度比内存快得多。选D。分析首先要明白没有管理软件、自由软件这些东西软件只分两大类系统软件OS和应用软件你下载的一切软件。只有A符合选择A。分析第一代是晶体管计算机没有“软件”这个东西第二代是电子管计算机还是只能显示没有系统。软件和系统是第三代才有的。选择C。分析计算机浮点数的标准构成 浮点数格式N M * r^E。阶码E决定数值范围尾数M决定数值精度 基数r一般为 2是约定好的不需要存储。这种也是常识问题不做太多拓展选C。分析题干描述的是原码表示法1 字节 8 位最高位是符号位符号位0正数符号位1负数剩余 7 位存放数值。正数最大值01111111 127负数最小值11111111 -127注意原码存在正 000000000和负 010000000两种编码没有额外编码表示 - 128。因此取值范围\(\boldsymbol{-127 \leqslant A \leqslant 127}\)。选择A。分析A数据结构不分“A优于B”看特定场景使用。queue的操作是先进先出。stack的操作是先进后出确实二维数组实际上就是“数组里面有数组”。所以选择D。分析分析过程原始序列\(25,84,21,47,15,27,68,35,20\)第 (2) 趟\(20,15,21,\boldsymbol{25},47,27,68,35,84\)可以看到基准元素 25 已经固定在最终正确位置左边全部≤25右边全部≥25这是快速排序一趟划分的典型特征。快速排序为追求效率使用分治算法实现。选择D。分析复习一下前中后序遍历的规则。前序根左右中序左根右后序左右根先推一下发现根是S没有右子树。然后每个顺推得出树为然后我们再后序推导。后序遍历左→右→根W → U → V → T → S → WUVTS对应选项 A。选择A。分析A这种存储方式某些情况下插入删除效率很低链表的最后一个节点的指针是NULL。n 个结点的二叉排序树最坏形态为单侧链表此时最大检索长度等于 \(\boldsymbol{n}\)\(\log_2n\) 是平衡二叉树的理想查找长度所以我们选择D。分析把每一个号往前移动即可。A过程发现其结果与答案不一样B格式错误C过程我们发现符合答案所以我们应选择C。阅读程序题分析递归算法的经典汉诺塔问题。16题错。n 0时会一直减少n变为负数不会停下来。17题错。根为一个然后接下来每个分为两个直到1。以n 3时举例我们可以发现最终输出了123次即7行不是2^n8行。18题对限制条件是n0。由于n是个int数大于0代表最小等于1而我们修改1为 1就是完全一样的。19题对只有n是1才会进入分支证明n是1所以n与1是一样的。20题D前面计算过这个的执行次数是2^n-1。时间复杂度不计算常数项所以2^n-1实际上就是2^n。21题B前面说过n0时是死循环排除A。那最小的只有B了所以选择B。分析程序功能计算 \(\boldsymbol{\dfrac{1}{2^n}}\)输出小数形式。推导\(\dfrac{1}{2^n}\dfrac{5^n}{10^n}\)\(10^n\) 等价小数点向左移动 n 位。num[]大整数存 \(5^n\)a1记录 \(5^n\) 的位数。输出格式0.后面总共打印n 位 如果 \(5^n\) 的位数 \(a1n\)先补 \((n-a1)\) 个前导 0再输出 \(5^n\) 的数字。22题错程序都有输出0.所以当然是个小数。23题错仔细看一下会发现被初始化为a1了。24题对因为每次都进行了%10操作实际上就是个位数所以是对的。25题对在特殊情况下会出现0.。。。0的情况。26题B两层循环所以是n^2。27题B\(\dfrac1{2^3}\dfrac180.125\)\(5^3125\)a13n3 不需要补 0输出0.125。分析这是一段二分答案“跳石头”代码。原题大意在起点和终点之间有 N 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走 M 块岩石不能移走起点和终点的岩石。输出最短跳跃距离的最大值。28题错有可能最优答案就是0。 当f11二分下界直接从 1 开始永远不会检查dis0此时会丢失答案 0输出发生改变。所以结果不一定不变。29题对因为只有达成此条件才会退出循环。30题错check(mid)1代表 mid 可行代码执行ansmid; f1mid1要尝试去找比 mid 更大的可行解。最终 ans 可以大于当前 mid。31题C这是二分算法会降低复杂度所以AB排除。check()函数里面一层循环时间\(O(n)\)。二分的范围\([0,l]\)二分执行次数是\(\boldsymbol{\log l}\)次。32题Bcheck 函数验证check(4)last0a[1]2\(2-024\)要删掉count1a[2]11\(11-011\ge4\)保留last11a[3]14\(14‑1134\)删掉count2a[4]17\(17‑116\ge4\)保留last17a[5]21\(21‑174\ge4\)保留last21a[6]25\(25‑214\ge4\)保留count2 ≤ m24 可行。check(5)last02‑025 →删 count111‑011≥5 →last1114‑1135 →删 count217‑116≥5 →last1721‑1745 →删 count3count3 m25 不可行。最大可行距离就是 4。程序填空题分析dijkstra最短路算法用于计算非负最短路。33题C顶点到自己的路径权重为 0因此选 C。34题A初始化邻接矩阵两个不同顶点之间暂时没有通路距离初始化为极大值因此选 A。35题A填写路径之间的权值。36题B打擂台比较的思想更新最小值。37题C依然是比较更新思想他拿什么比较就填什么。分析dp[]数组含义dp[j]代表背包容量为j时可以装下的最大价值。这道题实现的是dp完全背包问题即每个选项可选任意次的背包问题。38题A初始化为0。39题A第一个0是占位用的实际上只有5个物品下标1-5。所以是5。40题C完全背包物品可无限取用需要从小到大正向遍历背包容量5510。41题D完全背包状态转移公式\(dp[j]\max(dp[j],\;dp[j-w[i]]v[i])\) 含义比较「不拿当前物品」和「拿一次当前物品」两种情况取价值较大值因此选 D。42题Bdp的结果都是存在dp数组的最后一个位置这里最大下标是10。