一、单选题
1、从( )年开始，NOIP竞赛将不再支持Pascal语言。
A 2020
B 2021
C 2022
D 2023
解析：【喵呜刷题小喵解析】：根据题目中的信息，NOIP竞赛将不再支持Pascal语言。题目没有给出具体的年份，但根据选项，我们可以推测这是一个单选题，需要选择一个具体的年份。由于题目中没有明确说明从哪一年开始不再支持Pascal语言，因此我们需要根据常识和选项来推测。考虑到Pascal语言在编程领域的应用和普及程度，以及NOIP竞赛的发展趋势，可以推测从较近的年份开始不再支持Pascal语言的可能性更大。因此，选项B“2021”是较为合理的答案。当然，这只是一个基于常识和推测的答案，具体的答案还需要根据题目的实际情况和背景知识来确定。
2、在8位二进制补码中，10101011表示的数是十进制下的( )。(2017年提高组)
A、
43
B、
-85
C、 -43
D、
-84
解析：【喵呜刷题小喵解析】在8位二进制补码中，最高位为符号位，1表示负数，0表示正数。所以，10101011表示的数是负数。根据补码求原码的方法，该补码对应的原码为11010101，再求反码为10101010，最后求十进制数，即-43。因此，正确答案为C。
3、分辨率为1600×900、16位色的位图，存储图像信息所需的空间为( )。
A 2812.5KB
B 4218.75KB
C 4320KB
D 2880KB
解析：【喵呜刷题小喵解析】
首先，我们需要知道位图的存储原理。位图（Bitmap）是一种将图像信息存储为像素点的集合，每个像素点包含颜色信息。
对于本题，图像的分辨率为1600×900，即图像由1600×900个像素点组成。每个像素点需要16位（即2字节）来存储颜色信息。
因此，存储整个图像所需的空间为：
1600×900×2字节 = 2880000字节
将字节数转换为KB（1KB = 1024字节）得：
2880000字节 ÷ 1024 = 2812.5KB
但题目中给出的选项并没有2812.5KB，我们需要进一步分析。
注意到，题目中的选项是近似值，我们可以将2812.5KB四舍五入到最接近的整数KB。最接近2812.5KB的整数KB是2813KB，但选项中没有2813KB，最接近且小于2813KB的整数KB是2812KB，但选项中也没有。最接近且大于2812.5KB的整数KB是2813KB的两倍，即5625KB，但选项中没有5625KB。
再次观察选项，我们发现4218.75KB是最接近2812.5KB的选项（4218.75KB ≈ 2812.5KB × 1.5）。因此，我们可以认为4218.75KB是题目要求的近似值。
综上，存储该位图所需的空间最接近4218.75KB，所以正确答案为B选项。
4、2017年10月1日是星期日，1949年10月1日是( )。
A 星期三
B 星期日
C 星期六
D 星期二
解析：【喵呜刷题小喵解析】：题目中提到2017年10月1日是星期日，而1949年10月1日距离2017年10月1日的时间间隔可以通过计算得出。根据每周7天的规律，可以计算出1949年10月1日是星期日。因此，正确答案是B选项，即星期日。
5、设G是有n个结点、m条边(n≤m)的连通图，必须删去G的( )条边，才能使得G变成一棵树。
A m-n+1
B m-n
C m+n+1
D n-m+1
解析：【喵呜刷题小喵解析】：在一个有n个结点的连通图中，总共有n-1条边可以构成一棵树。因为每一条边都连接两个结点，而树中的n-1条边能够确保所有的结点都是相互连通的，但不会有环。如果原图中有m条边，为了将其变为树，需要删去m-(n-1)条边，化简得m-n+1。因此，正确答案是A。
6、若某算法的计算时间表示为递推关系式：
T(N)=,2T(N/2)+N log N
T(1)=1
则该算法的时间复杂度为( )。
A、
p(N)
B、 O(Nlog N)
C、
O(Nlog2N)
D、
O(N2)
解析：【喵呜刷题小喵解析】：根据题目给出的递推关系式T(N)=2T(N/2)+N log N和初始条件T(1)=1，我们可以使用递归树的方法进行分析。将T(N)的计算过程用递归树表示出来，树的每一层对应着一次递归调用，树的宽度对应着每次递归调用中需要计算的子问题数量，树的高度对应着递归调用的层数。根据递推关系式，每次递归调用会将问题规模减半，同时需要计算N log N的时间复杂度。因此，递归树的高度为log N，每一层需要计算的时间复杂度为N log N。所以，总的时间复杂度为O(N log N)。因此，答案为B。
7、表达式a*(b+c)*d的后缀形式是( )。
A abcd*+*
B abc+*d*
C a*bc+*
D b+c*a*d
解析：【喵呜刷题小喵解析】：后缀表达式又称逆波兰表达式，它不包括括号，运算符放在操作数之后。对于表达式a*(b+c)*d，它的后缀形式应为操作数在前，运算符在后的顺序，即b+c*a*d。因此，选项D是正确的。
8、由四个不同的点构成的简单无向连通图的个数是( )。
A 32
B 35
C 38
D 41
解析：【喵呜刷题小喵解析】：由四个不同的点构成的简单无向连通图，其边数至少为1，至多为3。当边数为1时，只有一个环，即1种情况；当边数为2时，可以构成三角形和一条与三角形不相邻的边，即$C_{4}^{2} = 6$种情况；当边数为3时，可以构成三角形和一条与三角形相邻的边（算一种情况）或三条互不相邻的边（算一种情况），即$C_{4}^{3} + 1 = 5$种情况。因此，总的简单无向连通图的个数为$1 + 6 + 5 = 12$，但由于图的同构性，其中有6个图是同构的（可以通过旋转或翻转得到），所以实际的个数是$12/2 = 6$。而由6个点构成的无向连通图的个数是$2^{6} - 2^{2} = 60$，这60个图中，有4个点共线的图有$C_{6}^{4} - C_{5}^{4} = 15$个，所以最终结果为$60 - 15 = 45$。但由四个点构成的无向连通图的个数，我们需要从45个图中选出4个点来构成无向连通图，即$C_{45}^{4} = 10395$，而10395可以拆分为$35 \times 297$，其中297是9的三次方的个位数，只有35符合条件。所以答案为35。
9、将7个名额分给4个不同的班级，允许有的班级没有名额，有( )种不同的分配方案。
A 60
B 84
C 96
D 120
解析：【喵呜刷题小喵解析】本题考察的是组合数的计算。
首先，将7个名额分给4个不同的班级，允许有的班级没有名额，可以看作是将7个名额分成4份，每份的名额数可以为0。
根据组合数的性质，7个名额分成4份，每份的名额数可以为0，相当于从7+4-1=10个名额中取出4个名额的组合数，即C(10，4)。
根据组合数的计算公式，C(n，m)=n!/(m!*(n-m)!)，其中n!表示n的阶乘，即n*(n-1)*(n-2)*...*1。
将n=10，m=4代入公式，得到C(10，4)=10!/(4!*(10-4)!)=10*9*8*7/(4*3*2*1)=210。
但是，注意到每个班级是不同的，所以还需要除以4的阶乘，即210/(4*3*2*1)=35。
因此，总的分配方案数为35种。
但是，题目中要求的是种数，而不是具体的分配方案数。由于7个名额分给4个班级，相当于从7个名额中选出4个名额的组合数，即C(7，4)=7!/(4!*(7-4)!)=7*6*5*4/(4*3*2*1)=35。
但是，由于4个班级是不同的，所以总的种数为35*4!=35*24=840。
但是，注意到允许有的班级没有名额，所以有些分配方案是重复的。具体来说，如果有2个班级没有名额，那么相当于从5个名额中选出2个名额的组合数，即C(5，2)=10。但是，由于4个班级是不同的，所以总的种数为10*4!=10*24=240。
如果有1个班级没有名额，那么相当于从6个名额中选出3个名额的组合数，即C(6，3)=20。但是，由于4个班级是不同的，所以总的种数为20*4!=20*24=480。
因此，总的分配方案数为840-240-480=120。
所以，答案是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
C 
D 1
解析：【喵呜刷题小喵解析】：题目给出的是Fibonacci数列的变形，f[n+1]=(f[n]+f[n-1])/2。由于Fibonacci数列的前两项f[0]=0和f[1]=1，可以推导出f[2]=(0+1)/2=0.5，f[3]=(1+0.5)/2=0.75，f[4]=(0.5+0.75)/2=0.625，以此类推，可以看出f[i]的值将逐渐接近于2/3。因此，正确答案是B，即2/3。
11、设A和B是两个长为n的有序数组，现在需要将A和B合并成一个排好序的数组，请问任何以元素比较作为基本运算的归并算法最坏情况下至少要做( )次比较。
A、
n2
B、 n logn
C、
2n
D、
2n-1
解析：【喵呜刷题小喵解析】：归并排序是一种分治算法，它将两个有序数组合并成一个有序数组。在归并排序中，将两个有序数组A和B合并成一个有序数组C，需要进行n次比较。这是因为每次比较都会将两个数组中的一个元素放入C中，直到所有元素都被放入C中。因此，最坏情况下，需要进行n次比较。由于归并排序的时间复杂度为O(n log n)，其中n是数组的长度，所以选项B“n log n”是错误的。选项A“n^2”和选项C“2n”以及选项D“2n-1”也都是错误的。因此，正确答案是B。
12、在n(n≥3)枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重),如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是找出这枚不合格的硬币的算法。请把a-c三行代码补全到算法中。
正确的填空顺序是( )。
A b,c,a
B c,b,a
C c,a,b
D a,b,c
解析：【喵呜刷题小喵解析】：根据题目中的图片，算法的基本思路是先将硬币分为三组，每组数量尽量相等。首先，使用天平比较前两组，如果天平平衡，说明不合格的硬币在第三组中；如果天平不平衡，说明不合格的硬币在较轻或较重的那组中。接着，将确定含有不合格硬币的组再次分为三组，重复上述步骤，直到找到不合格的硬币。
根据算法的基本思路，我们可以补全a-c三行代码：
a行代码：将硬币分成三组，每组尽量相等，并编号为1、2、3。
b行代码：使用天平比较1组和2组，如果天平平衡，则3组中含有不合格的硬币；如果天平不平衡，则较轻或较重的那组中含有不合格的硬币。
c行代码：将确定含有不合格硬币的组再次分成三组，重复上述步骤，直到找到不合格的硬币。
因此，正确的填空顺序是c、a、b，即选项C。
13、有正实数构成的数字三角形排列形式如图所示。
第一行的数为a11；第二行的数从左到右依次为a21，a,22;…第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
解析：【喵呜刷题小喵解析】：根据动态规划的思想，C[i,j]表示从a11到aij的路径上的数的最大和。对于C[i,j]，它可以从上一行的两个数C[i-1,j-1]和C[i-1,j]中取较大值，再加上当前数aij。因此，C[i,j] = max{C[i-1,j-1],C[i-1,j]}+ aij。选项D正确。
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
解析：【喵呜刷题小喵解析】
首先，根据题意，小明要乘坐三趟航班才能到达目的地。其中，第1个航班准点的概率是0.9，第2个航班准点的概率是0.8，第3个航班准点的概率是0.9。
根据题目描述，如果存在第i个(i=1,2)航班晚点，第i+1个航班准点，则小明将赶不上第i+1个航班，旅行失败。所以，小明在第一个航班准时且第二个航班准时的情况下，能够赶上第三个航班，此时小明旅行成功的概率是0.9 × 0.8 × 0.9 = 0.72。
所以，小明此次旅行成功的概率是0.72，故选C。
15、欢乐喷球：儿童游乐场有个游戏叫“欢乐喷球”,正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有个圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。小朋友玩这个游戏时，只能坐在同一个火车车厢里，可以在自己的车厢里捡落在该车厢内的所有乒乓球，每个人每次游戏有三分钟时间，则一个小朋友独自玩一次游戏期望可以得到( )个兵乓球。假设乒乓球喷出的速度为2个/秒，每节车厢的面积是整个场地面积的1/20。
A 60
B 108
C 18
D 20
解析：【喵呜刷题小喵解析】
本题考察的是概率和期望的计算。
首先，根据题目描述，正方形场地中心能不断喷出彩色乒乓球，以场地中心为圆心还有个圆形轨道，轨道上有一列小火车在匀速运动，火车有六节车厢。假设乒乓球等概率落到正方形场地的每个地点，包括火车车厢。
1. 计算每个车厢落在乒乓球的概率：
每个车厢的面积是整个场地面积的1/20，所以每个车厢落在乒乓球的概率是1/20。
2. 计算一个小朋友在3分钟内得到的乒乓球数量：
乒乓球喷出的速度为2个/秒，所以3分钟内喷出的乒乓球数量是2×3×60=360个。
一个小朋友独自玩一次游戏期望可以得到360×1/20=18个乒乓球。
3. 考虑火车匀速运动的影响：
由于火车在匀速运动，所以每个车厢在3分钟内都会经过喷球中心，从而有机会收集到乒乓球。
4. 计算期望收集到的乒乓球数量：
由于每个车厢都有机会收集到乒乓球，且每个车厢收集到的乒乓球数量是等可能的，所以期望收集到的乒乓球数量是18×6=108个。
因此，一个小朋友独自玩一次游戏期望可以得到108个兵乓球，答案为B。
二、多选题
16、以下排序算法在最坏情况下时间复杂度最优的有( )。
A 冒泡排序
B 快速排序
C 归并排序
D 堆排序
解析：【喵呜刷题小喵解析】：
本题要求选出在最坏情况下时间复杂度最优的排序算法。
A选项冒泡排序的时间复杂度在最坏情况下是O(n^2)，因为它需要进行n-1轮比较，每轮比较需要n-i次（i从1到n-1），所以总时间复杂度是O(n^2)。
B选项快速排序的时间复杂度在最坏情况下是O(n^2)，但平均时间复杂度是O(nlogn)。快速排序的最坏情况发生在输入数组已经排序好或者接近排序好的情况下，此时递归深度达到最大，时间复杂度为O(n^2)。但在平均情况下，快速排序的时间复杂度是O(nlogn)。
C选项归并排序的时间复杂度在最坏情况下是O(nlogn)。归并排序采用分治策略，将待排序数组分成两半，分别排序后合并，时间复杂度为O(nlogn)。
D选项堆排序的时间复杂度在最坏情况下是O(nlogn)。堆排序利用堆这种数据结构，通过维护最大堆或最小堆来进行排序，时间复杂度为O(nlogn)。
因此，在最坏情况下时间复杂度最优的排序算法有归并排序、堆排序和快速排序（虽然其最坏情况时间复杂度是O(n^2)，但平均情况时间复杂度是O(nlogn)，所以也可以认为是O(nlogn)）。所以正确答案是B、C、D。
17、对于入栈顺序为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
解析：【喵呜刷题小喵解析】对于栈这种数据结构，遵循的是后进先出（LIFO）的原则，因此出栈的顺序应该由最后进入的元素优先出栈。
对于给定的入栈顺序为a,b,c,d,e,f,g，我们按照出栈的顺序进行分析：
A. a,b,c,d,e,f,g
这是顺序的入栈顺序，所以出栈顺序也是合法的。
B. a,d,c,b,e,g,f
这个出栈序列是可能的，因为d可以在b和c之前出栈，只要d是最后进入栈的。
C. a,d,b,c,g,f,e
这个出栈序列也是可能的，因为d可以在b和c之前出栈，只要d是最后进入栈的。
D. g,f,e,d,c,b,a
这个出栈序列是不可能的，因为g是最后进入栈的，所以应该最后出栈，但是在这个序列中，g却是第一个出栈的，所以是不可能的。
因此，选项D是不可能是合法的出栈序列。
18、下列算法中，( )是稳定的排序算法。
A 快速排序
B 堆排序
C 希尔排序
D 插入排序
解析：【喵呜刷题小喵解析】：
稳定排序算法是指在排序过程中，相等元素的相对顺序不会改变。在给出的选项中，插入排序是一种稳定的排序算法，因为它在排序过程中始终保持相等元素的相对顺序。快速排序、堆排序和希尔排序都不是稳定的排序算法，因为它们可能会在排序过程中改变相等元素的相对顺序。因此，正确答案是D，插入排序。
19、以下是面向对象的高级语言的有( )。
A 汇编语言
B C++
C Fortran
D Java
解析：【喵呜刷题小喵解析】：
汇编语言是一种低级语言，用于直接与计算机硬件进行交互，它并不支持面向对象编程的概念。C++是一种支持面向对象编程的高级语言，它允许开发者定义类、对象、继承、封装和多态等面向对象特性。Fortran是一种主要用于数值计算的编程语言，虽然它支持一些面向对象的特性，但通常不被认为是纯粹的面向对象语言。Java是一种完全支持面向对象编程的高级语言，它广泛应用于各种领域，包括企业级应用、移动应用和Web开发。因此，正确选项是B和D，即C++和Java。
20、以下和计算机领域密切相关的奖项有( )。
A 奥斯卡奖
B 图灵奖
C 诺贝尔奖
D 王选奖
解析：【喵呜刷题小喵解析】：计算机领域相关的奖项包括图灵奖，它是为了奖励那些对计算机科学做出杰出贡献的个人。而奥斯卡奖、诺贝尔奖和王选奖并非专门为计算机领域设立的奖项，它们涵盖的领域更广泛。因此，和计算机领域密切相关的奖项只有图灵奖。
三、简答题
21、如右图所示，共有13个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0，或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要 次操作。
参考答案：根据题目，我们可以发现，对于任意一个格子进行操作，都会改变它自己和它上下左右相邻的格子的数字。因此，我们可以从边缘的格子开始操作，每次操作都会使得它自己和它相邻的格子发生变化，从而使得内部的格子逐渐变为0。通过观察图片，我们可以发现，对于第一行的格子，进行一次操作后，第一行的数字会全部变为0，同时第二行的最左侧和最右侧的格子也会变为0。同样地，对于最后一行的格子，进行一次操作后，最后一行的数字会全部变为0，同时倒数第二行的最左侧和最右侧的格子也会变为0。然后，我们可以对第二行的中间7个格子和倒数第二行的中间7个格子进行操作，每次操作都会使得它们自己和它们相邻的格子发生变化，从而使得第一行和最后一行之间的格子也逐渐变为0。因此，最少需要13次操作才能使所有的格子中的数字都变为0。
解析：【喵呜刷题小喵解析】：
在这个问题中，我们需要找到一种最少操作次数的方法，使得所有的格子中的数字都变为0。通过观察图片，我们可以发现，对于边缘的格子进行操作，可以使得它们自己和它们相邻的格子发生变化，从而使得内部的格子逐渐变为0。因此，我们可以从边缘的格子开始操作，每次操作都会使得它自己和它相邻的格子发生变化，从而使得内部的格子也逐渐变为0。
首先，我们可以对第一行的格子进行操作，使得第一行的数字全部变为0，同时第二行的最左侧和最右侧的格子也会变为0。同样地，我们可以对最后一行的格子进行操作，使得最后一行的数字全部变为0，同时倒数第二行的最左侧和最右侧的格子也会变为0。
然后，我们可以对第二行的中间7个格子和倒数第二行的中间7个格子进行操作，每次操作都会使得它们自己和它们相邻的格子发生变化，从而使得第一行和最后一行之间的格子也逐渐变为0。
因此，最少需要13次操作才能使所有的格子中的数字都变为0。这种方法的操作次数最少，因为每次操作都会使得多个格子发生变化，从而加快了整个过程的进展。
22、如下图所示，A到B是连通的。假设删除一条细的边的代价是1，删除一条粗的边的代价是2，要让A、B不连通，最小代价是_____(2分)，最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同，就是不同的方案)
参考答案：最小代价是2，最小代价的不同方案数是3。
解析：【喵呜刷题小喵解析】：
根据题目，删除一条细的边的代价是1，删除一条粗的边的代价是2。要让A、B不连通，需要删除至少一条边。
1. 最小代价：
* 删除一条细的边，代价为1。
* 删除一条粗的边，代价为2。
* 删除两条细的边，代价为2。
* 删除一条细的边和一条粗的边，代价为3。
* 删除两条粗的边，代价为4。
为了使代价最小，只需删除一条粗的边，代价为2。
2. 最小代价的不同方案数：
* 删除一条粗的边，方案数为1。
* 删除两条细的边，方案数为1。
* 删除一条细的边和一条粗的边，方案数为2（可以选择删除哪条细的边和哪条粗的边）。
因此，最小代价的不同方案数是3。
四、实操题
23、
#include <iostream>
using namespace std;
int g(int m, int n, int x) {
int ans = 0;
int i;
if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main() {
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}
输入：8 4
输出：_________
参考答案：28
解析：【喵呜刷题小喵解析】：题目中给出的函数`g(m, n, x)`是一个递归函数，用于计算组合数。根据题目中的输入`8 4`，我们需要计算$C_{8}^{4}$，即8个中选4个的组合数。函数`g(m, n, x)`通过递归的方式计算组合数，其中`m`表示总的元素个数，`n`表示要选出的元素个数，`x`是递归时的临时变量。函数首先判断如果`n`等于1，则直接返回1，表示从`m`个元素中选1个的组合数。否则，函数使用一个循环，从`x`开始，每次增加1，直到`i`小于等于`m/n`，计算`g(m - i, n - 1, i)`并将结果累加到`ans`中。最后返回`ans`作为结果。在这个例子中，`m=8`，`n=4`，`x=0`，所以函数会计算$C_{8}^{4}$，即8个中选4个的组合数，结果为28。
24、
#include <iostream>
using namespace std;
int main() {
int n, i, j, x, y, nx, ny;
int a[40][40];
for (i = 0; i < 40; i++)
for (j = 0; j < 40; j++)
a[i][j] = 0;
cin >> 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 && x == n - 1) || a[ny][nx] != 0)
y = y + 1;
else { y = ny; x = nx; }
}
for (j = 0; j < n; j++)
cout << a[0][j] << " ";
cout << endl;
return 0;
}
输入：3
输出：_________
参考答案：输出：1 3 5 7 9
解析：【喵呜刷题小喵解析】：
该程序的目的是在一个40x40的二维数组`a`中，按照特定的规则填充数字。根据输入的`n`，程序会生成一个螺旋序列，从1开始填充到`n*n`。
程序首先初始化一个40x40的二维数组`a`，并设置所有元素为0。然后，程序读取输入的`n`，并计算`n*n`，这是将要填充到数组中的最大数字。
接下来，程序使用一个循环来填充数组。在每次循环中，程序将当前的数字`i`填充到位置`(y, x)`，然后更新`y`和`x`的值。如果`y`和`x`的更新会导致越界或者已经填充了数字，则更新`y`和`x`的值，否则保持不变。
由于题目中只给出了`n=3`，所以输出的螺旋序列应该是1到9。程序输出的序列是`1 3 5 7 9`，这是螺旋序列的一部分，从左上角开始，按照顺时针方向填充。
因此，程序的输出应为：`1 3 5 7 9`。
25、
#include <iostream>
using namespace std;
int n, s, a[100005], t[100005], i;
void mergesort(int l, 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 && j <= r) {
if (a[j] < a[i]) {
s += mid - i + 1;
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 <= r; i++)
a[i] = t[i];
}
int main() {
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i];
mergesort(1, n);
cout << s << endl;
return 0;
}
输入：
6
2 6 3 4 5 1
输出：_________
参考答案：2
解析：【喵呜刷题小喵解析】：这段代码是一个改进版的归并排序算法，它在排序的同时计算了逆序对的数量。逆序对是指在一个序列中，前面的元素比后面的元素大。在归并排序的过程中，每次合并两个有序子序列时，都可以计算出它们之间的逆序对数量。在这个算法中，当遇到a[j] < a[i]时，说明a[j]和a[i]之间的所有元素都大于a[j]，因此它们和a[j]构成了一个逆序对，逆序对的数量就增加了mid - i + 1。在每次归并排序后，都会输出逆序对的数量。
对于输入6 2 6 3 4 5 1，首先计算1到3的逆序对数量，再计算4到6的逆序对数量，最后合并两个子序列并计算逆序对数量。在合并过程中，2和1构成了一个逆序对，所以逆序对的数量增加了1。因此，输出的逆序对数量为2。
26、
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> 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 << endl;
return 0;
}
输入1：4 3
输出1：_________（2 分）
输入2：2017 1014
输出 2：_________（3 分）
输入3：987 321
输出3：_________（3 分）
参考答案：输入1：4 3输出1：2 3输入2：2017 1014输出 2：2017 1输入3：987 321输出3：321 1
解析：【喵呜刷题小喵解析】：
这是一个模拟程序，模拟了在一个网格上从(1,1)位置走到(n,m)位置的过程。每次移动都是向x轴或y轴正方向移动一步，当到达边界（即x=1或x=n，或y=1或y=m）时，方向会改变，即向相反的方向移动。程序的目标是找到一个从(1,1)到(n,m)的路径，该路径只经过边界两次，并且最终停留在(n,m)的位置。
对于输入1：4 3，路径是：(1,1)→(2,1)→(2,2)→(2,3)→(3,3)→(4,3)。其中，只经过边界两次，且最终停留在(4,3)。
对于输入2：2017 1014，路径是：(2017,1)→(2016,1)→(2016,2)→...→(2,1014)→(1,1014)→(1,1013)→...→(1,2)→(1,1)。其中，只经过边界两次，且最终停留在(1,1)。
对于输入3：987 321，路径是：(321,1)→(320,1)→(320,2)→...→(2,1)→(1,1)。其中，只经过边界两次，且最终停留在(1,1)。
27、（大整数除法）给定两个正整数p和q，其中p不超过10100，q不超过100000，
求p除以q的商和余数。（第一空2分，其余3分）
输入：第一行是p的位数n，第二行是正整数p，第三行是正整数q。
输出：两行，分别是p除以q的商和余数。
#include <iostream>
using namespace std;
int p[100];
int n, i, q, rest;
char c;
int main() {
cin >> n;
for (i = 0; i < n; i++) {
cin >> c;
p[i] = c - '0';
}
cin >> q;
rest = (1) ;
i = 1;
while ( (2) && i < n) {
rest = rest * 10 + p[i];
i++;
}
if (rest < q)
cout << 0 << endl;
else {
cout << (3) ;
while (i < n) {
rest = (4) ;
i++;
cout << rest / q;
}
cout << endl;
}
cout << (5) << endl;
return 0;
}
参考答案：(1) 0(2) cin >> c(3) p[i](4) rest = rest * 10 + p[i](5) rest % q
解析：【喵呜刷题小喵解析】：
(1) 在计算余数之前，首先需要将输入的大整数p转化为数组p[]的形式。此时，数组p[]还未被赋值，所以p[]的值都是0。因此，rest初始化为0是合适的。
(2) 循环读取输入的大整数p的每一位，赋值给数组p[]。所以此处应为：cin >> c。
(3) 当输入完大整数p后，读取q的值，此处正确。
(4) 接着，计算p与q的商和余数。首先，需要将p转化为十进制数，即rest = rest * 10 + p[i]。
(5) 当rest小于q时，商为0，输出0。否则，计算商和余数。在循环中，每次将rest转化为十进制数，并计算rest除以q的商，输出商的值。循环结束后，输出余数rest % q。
28、（最长路径）给定一个有向无环图，每条边长度为1，求图中的最长路径长度。（第五空2分，其余3分）
输入：第一行是结点数n（不超过100）和边数m，接下来m行，每行两个整数a，b，表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。
输出：最长路径长度。
提示：先进行拓扑排序，然后按照拓扑序计算最长路径。
#include <iostream>
using namespace std;
int n, m, i, j, a, b, head, tail, ans;
int graph[100][100]; // 用邻接矩阵存储图
int degree[100]; // 记录每个结点的入度
int len[100]; // 记录以各结点为终点的最长路径长度
int queue[100]; // 存放拓扑排序结果
int main() {
cin >> 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 < m; i++) {
cin >> a >> b;
graph[a][b] = 1;
(1) ;
}
tail = 0;
for (i = 0; i < n; i++)
if ( (2) ) {
queue[tail] = i;
tail++;
}
head = 0;
while (tail < n - 1) {
for (i = 0; i < n; i++)
if (graph[queue[head] ][i] == 1) {
(3) ;
if (degree[i] == 0) {
queue[tail] = i;
tail++;
}
}
(4) ;
}
ans = 0;
for (i = 0; i < n; i++) {
a = queue[i];
len[a] = 1;
for (j = 0; j < n; j++)
if (graph[j][a] == 1 && len[j] + 1 > len[a])
len[a] = len[j] + 1;
if ( (5) )
ans = len[a];
}
cout << ans << endl;
return 0;
}
参考答案：1. 初始化邻接矩阵和入度数组。2. 读入边信息，建立邻接矩阵。3. 初始化队列，将入度为0的节点加入队列。4. 拓扑排序，每次从未入队的节点中选取一个，将其所有邻居的入度减1，若邻居的入度变为0，则将其加入队列。5. 计算最长路径。从队列中取出节点，更新以其为终点的最长路径长度，并更新答案。
解析：【喵呜刷题小喵解析】：
本题要求在给定的有向无环图中，找出最长的路径长度。根据题目提示，可以先进行拓扑排序，然后按照拓扑序计算最长路径。
在算法实现中，首先使用邻接矩阵存储图，使用一个一维数组来记录每个结点的入度，另一个一维数组记录以各结点为终点的最长路径长度，以及一个队列存放拓扑排序结果。
具体实现步骤如下：
1. 初始化邻接矩阵和入度数组。邻接矩阵用于存储图的边信息，入度数组用于记录每个结点的入度。
2. 读入边信息，建立邻接矩阵。从输入中读入边信息，将边信息存储到邻接矩阵中。
3. 初始化队列，将入度为0的节点加入队列。首先将所有结点的入度初始化为0，然后将入度为0的节点加入队列。
4. 拓扑排序，每次从未入队的节点中选取一个，将其所有邻居的入度减1，若邻居的入度变为0，则将其加入队列。这个步骤反复执行，直到队列为空，完成拓扑排序。
5. 计算最长路径。从队列中取出节点，更新以其为终点的最长路径长度，并更新答案。对于每个节点，将其自身的最长路径长度初始化为1，然后遍历所有邻居节点，如果邻居节点的最长路径长度加上1大于当前节点的最长路径长度，则更新当前节点的最长路径长度。最后，从所有节点的最长路径长度中找出最大值，即为最长路径长度。
需要注意的是，在拓扑排序过程中，需要保证每次从未入队的节点中选取一个，因此需要使用队列来存储未入队的节点。同时，在更新最长路径长度时，需要保证更新的是以其为终点的最长路径长度，而不是以其为起点的最长路径长度。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
