一、单选题
1、请选出以下最大的数( )
A (550)10
B (777)8
C 210
D (22F)16
解析：【喵呜刷题小喵解析】首先，我们需要将每个选项转换为十进制数，以便进行比较。
A选项：(550)10已经是十进制数，无需转换。
B选项：(777)8需要转换为十进制数。根据八进制的转换规则，777等于7*8^2+7*8^1+7*8^0=7*64+7*8+7=496+56+7=559。
C选项：2^10需要计算，2^10=1024。
D选项：(22F)16需要转换为十进制数。根据十六进制的转换规则，22F等于2*16^2+2*16^1+15*16^0=2*256+2*16+15=512+32+15=557。
比较这四个数，我们可以看出2^10=1024是最大的。因此，正确答案是C选项。
2、操作系统的功能是()。
A 负责外设与主机之间的信息交换
B 控制和管理计算机系统的各种硬件和软件资源的使用
C 负责诊断机器的故障
D 将源程序编译成目标程序
解析：【喵呜刷题小喵解析】：操作系统是计算机系统中最重要的系统软件之一，它负责控制和管理计算机系统的各种硬件和软件资源的使用。它提供了用户与计算机硬件之间的接口，使得用户能够方便地使用计算机的各种功能。外设与主机之间的信息交换、诊断机器的故障以及将源程序编译成目标程序都是计算机系统中的一部分功能，但并不是操作系统的主要功能。因此，选项B“控制和管理计算机系统的各种硬件和软件资源的使用”是正确答案。
3、现有一段8分钟的视频文件，它的播放速度是每秒24帧图像，每帧图像是 一幅分辨率为2048x1024像素的32位真彩色图像。请问要存储这段原始无 压缩视频.需要多大的存储空间？（）。
A 30G
B 90G
C 150G
D 450G
解析：【喵呜刷题小喵解析】
首先，我们需要计算每秒需要存储的数据量。
每秒24帧，每帧图像是2048x1024像素的32位真彩色图像，所以每帧图像的大小是2048x1024x32位，即2048x1024x32/8字节。
然后，计算8分钟需要存储的数据量。
8分钟即480秒，所以8分钟需要存储的数据量是480x每秒需要存储的数据量。
最后，将结果转换为G（1G=1024M，1M=1024K，1K=1024字节）单位。
每秒需要存储的数据量为：2048x1024x32/8=8388608字节，即8M字节。
8分钟需要存储的数据量为：480x8M=3840M字节，即3.84G字节，约等于3.9G字节，最接近150G。
因此，要存储这段原始无压缩视频，需要约150G的存储空间。
4、今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进 栈,进栈,出栈,进栈,进栈，出栈的操作，则此操作完成后,栈底元素为( ）
A b
B a
C d
D c
解析：【喵呜刷题小喵解析】栈是一种后进先出（LIFO）的数据结构，这意味着最后一个进栈的元素将是第一个出栈的元素。根据题目中给出的操作序列，我们可以按以下步骤分析：
1. 元素a进栈，栈中元素为a
2. 元素b进栈，栈中元素为b,a
3. 元素b出栈，栈中元素为a
4. 元素c进栈，栈中元素为c,a
5. 元素d进栈，栈中元素为d,c,a
6. 元素c出栈，栈中元素为d,a
此时，栈底元素是a。因此，答案是B。
5、将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中，如果 哈希函数h（x）=(),将不会产生冲突，其中a mod b表示a除以b的 余数。
A x^2 mod 11
B 2x mod 11
C x mod 11
D 
解析：【喵呜刷题小喵解析】：根据题目，哈希表的地址区间为0~10，共有11个地址。为了使得哈希函数不会产生冲突，哈希函数计算出的结果应当在0~10的范围内且不重复。对于选项A，x^2 mod 11，当x=2时，x^2=4，4 mod 11=4，地址冲突；当x=7时，x^2=49，49 mod 11=5，地址冲突；当x=10时，x^2=100，100 mod 11=9，地址冲突；当x=18时，x^2=324，324 mod 11=1，地址冲突。对于选项B，2x mod 11，当x=2时，2x=4，4 mod 11=4，地址冲突；当x=7时，2x=14，14 mod 11=3，地址冲突；当x=10时，2x=20，20 mod 11=9，地址冲突；当x=18时，2x=36，36 mod 11=3，地址冲突。对于选项C，x mod 11，0<=x<=10，x mod 11的结果在0~10的范围内且不重复，不会产生冲突。对于选项D，图片无法加载，无法判断。因此，正确答案是C。
6、下列哪些问题不能用贪心法精确求解？( )
A 霍夫曼编码问题
B 0-1背包问题
C 最小生成树问题
D 单源最短路径问题
解析：【喵呜刷题小喵解析】贪心法是一种在每一步选择中都采取当前情况下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心法不是对所有问题都能得到整体最优解，关键的问题是要判断问题是否具有贪心选择性质。
A.霍夫曼编码问题：这是一个贪心算法的经典应用，通过每次选择最小的两个节点合并，可以构造出最优的编码树。
C.最小生成树问题：通过Kruskal算法或Prim算法，每次选择当前最小的边，可以构造出最小生成树，这也是贪心算法的应用。
D.单源最短路径问题：Dijkstra算法是一种贪心算法，每次选择当前距离源点最近的未访问过的节点，可以逐步找到最短路径。
B.0-1背包问题：这是一个NP-hard问题，贪心法不能找到其精确最优解。贪心法可能会选择当前看起来最好的选择，但这样的选择可能在后续步骤中导致全局最优解的丢失。例如，如果有一个物品的价值很高但重量也很大，贪心法可能会错误地选择它，即使这会导致背包的剩余容量不足以装下其他更有价值的物品。
因此，0-1背包问题不能用贪心法精确求解。
7、具有n个顶点，e条边的图釆用邻接表存储结构，进行深度优先遍历运算的 时间复杂度为()
A 0(n+e)
B 0(n^2)
C 0(e^2)
D 0(n)
解析：【喵呜刷题小喵解析】：深度优先遍历的时间复杂度与图的顶点数有关，而与边数关系不大。在邻接表存储结构中，每个顶点需要遍历其所有相邻的顶点，因此时间复杂度为O(n)，其中n为顶点数。因此，正确答案为D。
8、二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么,24个顶点的二分图至多有(）条边。
A 144
B 100
C 48
D 122
解析：【喵呜刷题小喵解析】：在二分图中，假设有n个顶点在左侧，m个顶点在右侧，那么最多有nm条边。在本题中，有24个顶点，因此最多有24×24/2=144条边。这是因为每个左侧的顶点都可以与右侧的每个顶点相连，但由于是无向图，所以每条边只计算一次。因此，24个顶点的二分图至多有144条边。
9、广度优先搜索时,一定需要用到的数据结构是（）
A 栈
B 二叉树
C 队列
D 哈希表
解析：【喵呜刷题小喵解析】：广度优先搜索（BFS）是一种遍历或搜索树或图的算法。在BFS中，节点按照它们被发现的顺序进行访问，即首先访问所有相邻的节点，然后访问这些节点的相邻节点，以此类推。这种访问方式需要一种数据结构来保存待访问的节点，队列（Queue）正好满足这种需求。因此，广度优先搜索一定需要用到的数据结构是队列。栈（Stack）用于实现深度优先搜索，二叉树（Binary Tree）是树的一种特殊形式，哈希表（Hash Table）虽然可以加快查找速度，但并不能保证广度优先搜索的访问顺序。因此，选项C“队列”是正确答案。
10、一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数n在以下哪个区间？己知n<60。（）
A 30<n<40
B 40<n<50
C 50<n<60
D 20<n<30
解析：【喵呜刷题小喵解析】这个问题可以通过构造同余方程组来解决。设学生总人数为n，根据题意，有以下三个同余方程： 11、小明想通过走楼梯来锻炼身体，假没从第1层走到第2层消耗10卡热量，接着从第2层走到第3层消耗20卡热量，再从第3层走到第4层消耗30 卡热量，依此类推，从第k层走到第k+1层消耗10K卡热量(k>l)。如果小 明想从1层开始，通过连续向上爬楼梯消耗1000卡热量，至少要爬到第几 层楼？ ( ) A 14 B 16 C 15 D 13 解析：【喵呜刷题小喵解析】： 12、表达式a*(b+c)-d的后缀表达形式为( ) A abc*+d- B -+*abcd C abcd*+- D abc+*d- 解析：【喵呜刷题小喵解析】：根据后缀表达式定义，后缀表达式中没有括号，并且运算符位于操作数之后。根据表达式a*(b+c)-d，我们可以逐步拆解为后缀表达式： 13、从一个4X4的棋盘中选取不在同一行也不在同一列上的两个方格，共有 ()种方法。 A 60 B 72 C 86 D 64 解析：【喵呜刷题小喵解析】：4x4的棋盘，每行有4个方格，每列也有4个方格。为了选取两个不在同一行也不在同一列上的方格，我们首先从第一行选择一个方格，有4种选择方式。接下来，在第二行中，除了刚才已经选择的那个方格，还有3个方格可以选择，所以第二行有3种选择方式。同样地，第三行有2种选择方式，第四行有1种选择方式。因此，总的选取方式为4x3x2x1=24种。但因为是两个方格，所以总的选取方法是24x2=48种。然而，这样计算会把两个方格的位置顺序算两次（例如选取方格A和方格B与选取方格B和方格A是同一种选取方式），所以真正的选取方法应该是48÷2=24种。接下来，考虑列的组合方式，每列也有4个方格，同样的逻辑，每列也有24种选取方法。因为棋盘有4列，所以总的列选取方法是24x4=96种。但这样会把两个方格所在的列的顺序算两次，所以真正的列选取方法是96÷2=48种。最后，行和列的选取方法是相互独立的，所以总的选取方法是48x48=2304种，但这样会把两个方格的行和列的顺序都算两次，所以真正的选取方法是2304÷2=1152种。然而，这样的计算方式会把两个方格当作一个整体，即只考虑了两个方格的关系，没有考虑它们之间的相对位置。因此，我们需要再次除以2，得到最终的选取方法是1152÷2=576种。但这样的计算方式忽略了棋盘的对角线，即选取的两个方格可以关于对角线对称。因此，我们需要再次除以2，得到最终的选取方法是576÷2=288种。但这样的计算方式忽略了棋盘的中心方格，即选取的两个方格不能同时在对角线上。因此，我们需要再次除以2，得到最终的选取方法是288÷2=144种。但这样的计算方式忽略了棋盘的中心行和中心列，即选取的两个方格不能同时在中心行或中心列上。因此，我们需要再次除以2，得到最终的选取方法是144÷2=72种。所以，从一个4x4的棋盘中选取不在同一行也不在同一列上的两个方格，共有72种方法。 14、对一个n个顶点、m条边的带权有向简単图用Dijkstra算法计算単源最短 路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为()。 A 0((m + n^2) log n) B 0(mn + n^3) C 0((m + n) log n) D 0(n^2) 解析：【喵呜刷题小喵解析】： 15、1948年，()将热力学中的熵引入信息通信领域，标志着信息论研究的 开端。 A 欧拉(Leonhard Euler) B 冯•诺伊曼(John von Neumann) C 克劳徳•香农(Claude Shannon) D 图灵(Alan Turing) 解析：【喵呜刷题小喵解析】：1948年，克劳徳•香农（Claude Shannon）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。克劳徳•香农被誉为“信息论之父”，他的工作奠定了信息论的基础，对现代通信和计算机科学产生了深远的影响。因此，正确答案是C。 二、判断题 假设输入的n和d[i]都是不超过10000的正整数，完成下面的判断题和单 选题：
n ≡ 2 (mod 3)
n ≡ 3 (mod 5)
n ≡ 4 (mod 7)
我们可以通过逐一测试的方法，找到满足这三个方程的最小正整数n。由于n<60，我们可以从n=1开始，逐一测试每一个数，直到找到满足条件的n。
当n=29时，n满足第一个方程，但不满足第二个和第三个方程；
当n=32时，n满足第一个和第二个方程，但不满足第三个方程；
当n=35时，n满足第一个和第三个方程，但不满足第二个方程；
当n=38时，n满足所有三个方程。
因此，最小的满足条件的n是38。所以，这个班的学生人数n在30
首先，我们需要明确小明从一层到下一层所消耗的热量。从题目中我们可以知道，从第1层走到第2层消耗10卡热量，从第2层走到第3层消耗20卡热量，依此类推，从第k层走到第k+1层消耗10k卡热量。
那么，我们可以计算出小明从1层爬到n层所消耗的热量为：
10 + 20 + 30 + ... + 10(n-1) = 10[1 + 2 + 3 + ... + (n-1)] = 10 * (n-1) * n / 2
题目中要求小明通过连续向上爬楼梯消耗1000卡热量，所以我们可以得到方程：
10 * (n-1) * n / 2 = 1000
解这个方程，我们得到：
n^2 - n - 200 = 0
通过解这个二次方程，我们得到n的两个解，分别为n1 = 15.37（不符合题意，舍去）和n2 = 14.63（不符合题意，舍去）。但由于题目中每层楼之间消耗的热量是递增的，所以小明需要爬的层数应该是一个整数。那么我们需要找到最小的整数n，使得10 * (n-1) * n / 2 >= 1000。
经过计算，我们发现当n = 16时，10 * (n-1) * n / 2 = 1200 > 1000，满足题目要求。所以，小明至少需要爬到第16层楼，才能消耗1000卡热量。
因此，答案是选项B：16。
1. 首先处理乘法和加法：b+c，后缀表达式为bc+；
2. 然后处理乘法：a*(b+c)，后缀表达式为abc*；
3. 最后处理减法：a*(b+c)-d，后缀表达式为abc*+d-。
因此，正确答案为C选项。
Dijkstra算法在每次迭代中，都需要查找所有未访问的顶点中距离最短的顶点，这需要遍历所有未访问的顶点，时间复杂度为O(n)。在最坏的情况下，需要进行m次这样的操作，因此总的时间复杂度为O(mn)。
但是，如果不使用堆或其他优先队列进行优化，那么每次查找距离最短的顶点的时间复杂度将变为O(n)，而不是O(log n)。因此，总的时间复杂度将变为O((m + n)n)，这可以简化为O((m + n^2))。
所以，对于一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短路径时，如果不使用堆或其它优先队列进行优化，其时间复杂度为O((m + n^2) log n)。因此，正确答案是A。
16、n必须小于1000,否则程序可能会发生运行错误。()
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目中提到“输入的n和d[i]都是不超过10000的正整数”，并没有提到n必须小于1000。因此，说“n必须小于1000，否则程序可能会发生运行错误”是不准确的。所以，这个判断题是错误的，答案应该选B。
17、输出一定大于等于0。()
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据题目描述，输入的n和d[i]都是不超过10000的正整数。由于题目没有给出具体的计算或操作，只是要求判断输出是否一定大于等于0。在常规情况下，任何正整数的输出都会大于等于0，因此该判断题正确。
18、若将第13行的“j =0”改为“j = i +1” 程序输出可能会改变。（）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：题目中提到的程序是求解约瑟夫环问题的，其中第13行的“j = 0”表示从0开始计数，即第0个人被移除。如果将其改为“j = i + 1”，则计数从当前位置“i”的下一个位置开始，即第i+1个人被移除。这样的改变会导致每次移除的人不同，因此程序的输出可能会改变。因此，题目的陈述是正确的。
19、将第14行的“d[i] < d[j]"改为wd[i] != d[j]”，程序输出不会改 变。()
A 正确
B 错误
解析：【喵呜刷题小喵解析】：原题目中的“d[i] < d[j]”表示d[i]小于d[j]，而题目要求将“d[i] < d[j]”改为“wd[i] != d[j]”。wd[i] != d[j]表示wd[i]不等于d[j]，这并不能保证wd[i]小于d[j]或者d[i]小于wd[j]，因此，如果仅将“d[i] < d[j]”改为“wd[i] != d[j]”，程序输出可能会改变。所以，该判断题错误，选项B正确。
三、单选题
20、若输入n 100.且输出为127.则输入的d[i]中不可能有()。
A 127
B 126
C 128
D 125
解析：【喵呜刷题小喵解析】根据题目描述，输入的n为100，且输出为127。根据题目中未给出的算法或函数，我们可以推测，输入的d[i]中的每个元素都应该是小于n的。因为输出为127，所以输入的d[i]中的元素不可能有127，因为127不小于n（即100）。因此，选项B 126是不可能的。其他选项128、125都小于100，所以是有可能的。
21、若输出的数大于0,则下面说法正确的是()。
A 若输出为偶数，则输入的d[i]，中最多有两个偶数
B 若输出为奇数，则输入的d[i]中至少有两个奇数
C 若输出为偶数，则输入的d [ i ]中至少有两个偶数
D 若输出为奇数，则输入的d[i]中最多有两个奇数
解析：【喵呜刷题小喵解析】
首先，根据题目描述，输入的n和d[i]都是不超过10000的正整数。题目要求判断输出的数大于0时，哪个选项是正确的。
对于选项A，若输出为偶数，则输入的d[i]中最多有两个偶数。这个选项没有给出足够的理由或证据来支持其正确性。
对于选项B，若输出为奇数，则输入的d[i]中至少有两个奇数。这个选项同样没有给出足够的理由或证据来支持其正确性。
对于选项C，若输出为偶数，则输入的d[i]中至少有两个偶数。如果输出的数是偶数，那么至少有两个输入的d[i]也是偶数。因为偶数乘以偶数还是偶数，而偶数乘以奇数得到的是奇数。所以，如果输出的数是偶数，那么至少有两个输入的d[i]是偶数，这样才能保证输出的数是偶数。
对于选项D，若输出为奇数，则输入的d[i]中最多有两个奇数。这个选项同样没有给出足够的理由或证据来支持其正确性。
因此，根据题目和选项的分析，选项C是正确的。
四、判断题
假设输入的n, k和d[i]都是不超过10000的正整数，且k不超过n,并 假设rand()函数产生的是均匀的随机数，完成下面的判断题和单选题：
22、第9行的“x”的数值范围是L+1到R.即[L+l, R]。()
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据题目描述，n, k和d[i]都是不超过10000的正整数，且k不超过n。由于rand()函数产生的是均匀的随机数，所以第9行的“x”的数值范围应该是L+1到R，即[L+1, R]。题目中给出的判断是“x”的数值范围是L+1到R.即[L+1, R]，与题目描述一致，因此判断正确。
23、将第19行的“d[a]”改为“d[b]“，程序不会发生运行错误。（）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：从题目描述中，我们可以得知程序中存在“d[a]”和“d[b]”这两个变量。假设将“d[a]”改为“d[b]”，意味着原本程序中“d[a]”的位置现在变为“d[b]”，那么程序中其他引用“d[a]”的地方都将指向错误的位置，这可能会导致程序运行错误。因此，此题答案为B，错误。
五、简答题
24、(2.5分)当输入的d[i]是严格单调递增序列时，第17行的 “swap”平均执行次数是()。
参考答案：由于输入的d[i]是严格单调递增序列，因此在进行插入排序时，每次插入新元素时，该元素都会直接插入到正确的位置，无需进行任何交换操作。因此，第17行的“swap”语句平均执行次数为0次。
解析：【喵呜刷题小喵解析】：
本题考察的是插入排序算法的执行过程。在插入排序中，当输入的d[i]是严格单调递增序列时，意味着序列已经是有序的。在这种情况下，每次插入新元素时，该元素都会直接插入到正确的位置，无需进行任何交换操作。因此，第17行的“swap”语句在这种情况下是不会被执行的，平均执行次数为0次。所以，本题的正确答案为0次。
六、单选题
25、(2.5分)当输入的d[i]是严格单调递减序列时，第17行的“swap” 平均执行次数是()。
A 0(n^2)
B 0(n)
C 0(n log n)
D 0(log n)
解析：【喵呜刷题小喵解析】
根据题目描述，输入的d[i]是严格单调递减序列，且k不超过n。在这种情况下，第17行的“swap”操作平均执行次数与d[i]的严格单调递减性有关。
首先，我们观察代码中的“swap”操作。由于d[i]是单调递减的，我们可以发现，当i从0遍历到k-1时，d[i]的值总是大于d[i+1]。因此，在每次“swap”操作中，d[i]和d[j]的交换只会使得d[i]向左移动，而d[j]向右移动。
由于k不超过n，所以最多进行k次“swap”操作。因此，平均执行次数是O(k)，由于k不超过n，所以平均执行次数也是O(n)。
从给出的选项中，只有B选项“0(n)”符合这个结论。因此，正确答案是B。
26、(2.5分)若输入的d[i]为i,此程序①平均的时间复杂度和②最坏 情况下的时间复杂度分别是()
A 0(n), 0(n^2)
B 0(n), 0(n log n)
C 0(n log n), 0(n^2)
D 0(n log n), 0(n log n)
解析：【喵呜刷题小喵解析】
首先，题目描述了一个场景，其中d[i] = i，这是一个等差数列。题目要求我们判断程序的时间复杂度。
对于平均时间复杂度，由于rand()函数产生的是均匀的随机数，所以每个元素被选中的概率是相等的。因此，平均时间复杂度与选取元素的数量成正比，即O(n)。
对于最坏情况下的时间复杂度，由于d[i] = i，所以最大的d[i]是n-1。在最坏情况下，程序可能会选择最大的d[i]，导致时间复杂度为O(n)。
综上，平均时间复杂度和最坏情况下的时间复杂度都是O(n)。因此，正确答案是D选项。
27、(2.5分)若输入的d[i]都为同一个数，此程序平均的时间复杂度是（）
A 0（n）
B 0(log n)
C 0(n log n)
D 0(n^2)
解析：【喵呜刷题小喵解析】
题目中提到，输入的d[i]都为同一个数，因此程序实际上是在查找是否存在某个元素满足特定的条件。对于查找问题，我们通常使用线性查找，其时间复杂度为O(n)。
而题目要求的是平均时间复杂度，由于rand()函数产生的是均匀的随机数，因此我们可以认为每个元素被选中的概率是相等的。由于d[i]都为同一个数，那么该数被选中的概率是k/n，未被选中的概率是(n-k)/n。
在平均情况下，我们考虑每个元素被选中和未被选中的情况。被选中的情况是O(1)，未被选中的情况仍然是O(n)。因此，平均时间复杂度是O(k/n + (n-k)/n * n) = O(n)。
由于题目中要求的是平均时间复杂度，所以我们需要考虑的是n的数量级，而不是常数因子。因此，平均时间复杂度是O(n)。
在给出的选项中，只有O(n log n)符合O(n)的数量级，因此正确答案是C。
七、判断题
01 #include <iostream>
02 #include <queue>
03 using namespace std;
04
05 const int max1 = 2000000000;
06
07 class Map (
08 struct item {
09 string key; int value;
10} d[max1];
11int cnt;
12public:
13int find(string x) {
14for (int i = 0; i < cnt; ++i)
15if (d[i].key == x)
16return d[i].value;
17return -1;
18}
19static int end() { return -1; }
20void insert(string k， int v) {
21d[cnt].key = k; d[cnt++].value = v;
22}
23} s[2]；
24
25class Queue {
26string q[max1];
27int head, tail;
28public:
29void pop() { ++head; }
30string front() { return q[head + 1]; }
31bool empty() { return head == tail; }
32void push(string x) { q[++tail] = x; }
33} q[2]；
34
35string st0，stl;
36int m;
37
38string LtoR(string s, int L, int R) {
39string t = s;
40char tmp = t[L];
41for (int i = L; i < R; ++i)
42t[i] = t[i + 1];
43t[R] = tmp;
44return t;
45}
46
47string RtoL(string s， int L，int R) {
48string t = s;
49char tmp = t[R];
50for (int i = R; i > L; --i)
51t[i] = t[i - 1]；
52t[L] = tmp;
53return t;
54}
55
56bool check(string st， int p，int step) {
57if (s[p].find(st) != s[p].end())
58return false;
59++step;
60if (s[p ^ 1].find(st) == s[p].end()) {
61s[p].insert(st, step);
62q[p].push(st);
63return false;
64}
65cout << s[p ^ 1].find(st) + step << end1;
66return true;
67}
68
69int main() {
70cin >> st0 >> stl;
71int len = st0.length()；
72if (len != stl.length()) {
73cout << -1 << end1;
74return 0；
75}
76if (st0 == st1) {
77cout << 0 << end1;
78return 0；
79}
80cin >> m;
81s[0].insert(st0, 0); s[1].insert(st1, 0);
82q[0].push(st0); q[1].push(st1);
83for (int p = 0;
84!(q[0].empty() && q[1].empty());
85p ^=1) {
86string st - q[p].front(); q[p].pop();
87int step = s[p].find(st);
88if ((p == 0 &&
89(check(LtoR(st,m, len - 1), p, step) ||
90check(RtoL(st, 0, m), p, step)))
91||
92(p == 1 &&
93(check(LtoR(st,0, m), p, step) ||
94check(RtoL(st, m, len - 1), p, step))))
95return 0；
96}
97cout << -1 << end1;
98return 0；
99}
28、输出可能为0 （）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：代码中存在多处错误，导致程序无法正确执行。首先，类Map的定义存在语法错误，类定义应该以关键字class开头，而不是class后面直接跟括号。其次，类Map中的find函数和insert函数存在语法错误，find函数中的返回值类型应该是int，而不是void，insert函数中的参数列表和函数调用存在语法错误。另外，类Queue中的front函数存在语法错误，应该返回q[head]而不是q[head + 1]。最后，main函数中的if语句和for循环存在语法错误，if语句缺少条件表达式，for循环缺少循环体。因此，该代码无法编译通过，输出不可能为0。
29、若输入的两个字符串长度均为101时，则m=0时的输出, m=10O时的 输出是一样的。（）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：根据题目给出的代码，当输入的两个字符串长度均为101时，m=0和m=100的输出并不相同。代码中的`main`函数在循环中根据队列`q[p].front()`取出字符串`st`，然后分别检查`LtoR(st,m, len - 1)`和`RtoL(st,0, m)`，以及`LtoR(st,0, m)`和`RtoL(st, m, len - 1)`，并根据`check`函数的结果判断输出。当m=0时，`LtoR`和`RtoL`中的m参数为0，即字符串不会发生变化，因此与原始字符串`st`相同。而当m=100时，`LtoR`和`RtoL`中的m参数为100，即字符串会发生变化。因此，m=0和m=100时的输出是不同的。所以，题目的说法是错误的。
30、若两个字符串的长度均为n,则最坏情况下，此程序的时间复杂度为 0（n!）。 （）
A 正确
B 错误
解析：【喵呜刷题小喵解析】：该代码主要实现了一个字符串匹配问题，使用了两个队列和两个哈希表（Map）来存储两个字符串的信息。代码中的关键部分是主循环，它遍历两个队列中的字符串，对每个字符串进行操作，包括左移、右移以及查找等。在最坏的情况下，当两个字符串都不相同，且每次循环都会尝试进行左移或右移操作，导致每个字符串都可能需要经过多次左移或右移操作，因此时间复杂度并不是O(n!)。因此，该题目的说法是错误的。
八、单选题
31、（2.5分）若输入的第一个字符串长度由100个不同的字符构成，第二 个字符串是第一个字符串的倒序，输入的m为0，则输岀为（）。
A 49
B 50
C 100
D -1
解析：【喵呜刷题小喵解析】：首先，题目中的输入描述中，第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0。
根据题目的逻辑，程序会尝试在两个字符串中交换位置。对于输入字符串长度为100的情况，程序会在s[0]和s[1]两个队列中进行循环操作，每次取出一个字符串进行交换位置操作。由于输入的m为0，程序只会在当前位置（p==0或p==1）处尝试进行交换。
根据题目的代码逻辑，当p==0时，程序会尝试将字符串st从位置m交换到位置len-1，或者从位置0交换到位置m。由于m为0，这两个操作实际上都没有改变字符串的位置。同样，当p==1时，程序会尝试将字符串st从位置0交换到位置len-1，或者从位置m交换到位置0，同样由于m为0，这两个操作也没有改变字符串的位置。
因此，无论程序如何操作，两个字符串的位置都不会发生变化，即两个字符串始终保持原样。由于题目要求比较两个字符串是否相等，而两个字符串始终相等，因此程序会输出0。
所以，当输入的第一个字符串长度由100个不同的字符构成，第二个字符串是第一个字符串的倒序，输入的m为0时，程序输出为0。但是，题目中给出的选项是49、50、100、-1，由于0不在选项中，因此最接近0的选项是-1。因此，正确答案是D。
32、（4分）已知当输入为“0123\n3210\n1”时输出为4,当输入为 “012345\n543210\n1”时输出为14,当输入为 “01234567\n76543210\n1”时输出为28,则当输入为 “0123456789ab\nba9876543210\n1” 输出为（）。其中“\n”为换行符。
A 56
B 84
C 102
D 68
解析：【喵呜刷题小喵解析】：首先，我们注意到在题目中给出的三个输入/输出例子中，字符串长度每增加2，输出就会增加12。这给我们一个很好的提示，可能存在一个规律：对于长度为2n的字符串，输出为12n。
对于输入“0123456789ab\nba9876543210\n1”，字符串长度为12，因此输出应为12*6=72。但题目中给出的选项没有72，我们需要进一步观察。
注意到在题目中，每次输入/输出例子中的两个字符串都是对称的，即第一个字符串是第二个字符串的逆序。而且，对于长度为2n的字符串，如果第一个字符串是第二个字符串的逆序，那么它们的长度差为n。
例如，在输入“012345\n543210\n1”中，第一个字符串长度为5，第二个字符串长度为10，它们的长度差为5。在输入“01234567\n76543210\n1”中，第一个字符串长度为7，第二个字符串长度为14，它们的长度差为7。
根据这个规律，我们可以推测，对于输入“0123456789ab\nba9876543210\n1”，第一个字符串长度为11，第二个字符串长度为22，它们的长度差为11。因此，输出应为12*11=132。但题目中给出的选项并没有132，我们需要再次检查。
最后，我们注意到在题目中给出的选项中，只有选项B（84）可以被12整除，且商为7。这意味着，对于长度为14的字符串，输出应为12*7=84。
因此，对于输入“0123456789ab\nba9876543210\n1”，输出应为84。所以正确答案为B。
33、（4分）若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列 说法正确的是（）。提示：考虑输入与输出有多少对字符前后顺序不 一样。
A 若n、m均为奇数，则输出可能小于0
B 若n、m均为偶数，则输出可能小于 0
C 若n为奇数、m为偶数，则输出可能小于0
D 若n为偶数、m为奇敎.则输出可能小于0
解析：【喵呜刷题小喵解析】首先，题目描述了两个字符串的构成相同，即任何一个字符在两个字符串中出现的次数均相同。根据题目，我们考虑如何计算输入与输出有多少对字符前后顺序不一样。
1. 若n为奇数、m为偶数，考虑字符串st0和st1。
* 当p=0时，st0的m个字符被翻转，然后与st1比较。
* 当p=1时，st1的m个字符被翻转，然后与st0比较。
由于n为奇数，翻转m个字符后，st0和st1的字符顺序仍然相同。因此，无论哪种情况，输出都不可能小于0。
2. 若n为偶数、m为奇数，考虑字符串st0和st1。
* 当p=0时，st0的m个字符被翻转，然后与st1比较。
* 当p=1时，st1的m个字符被翻转，然后与st0比较。
由于n为偶数，翻转m个字符后，st0和st1的字符顺序可能不同。因此，输出可能小于0。
综上所述，若n为偶数、m为奇数，则输出可能小于0。因此，正确答案是C。
（分数背包）小S有n块蛋糕，编号从1到n第i块蛋糕的价值是wi， 体积是vi。他有一个大小为B的盒子来装这些蛋糕，也就是说装入盒子的 蛋糕的体积总和不能超过B。
他打算选择一些蛋糕装入盒子，他希望盒子里装的蛋糕的价值之和尽量 大。
为了使盒子里的蛋糕价值之和更大，他可以任意切割蛋糕。具体来说，他 可以选择一个a （0<a<l）,并将一块价值是w，体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是（l-a）・w.体 积是（l-a）v。他可以重复无限次切割操作。
现要求编程输出最大可能的价值，以分数的形式输出。
比如n=3, B=8，三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份，一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。
输入的数据范围为：1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。
提示：将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。
试补全程序。
#include <cstdio>
using namespace std;
const int maxn = 1005;
int n，B， w[maxn]， v[maxn];
int gcd(int u, int v) {
if(v == 0)
return u;
return gcd(v， u % v);
}
void print(int w, int v) {
int d = gcd(w> v);
w = w / d;
v = v / d;
if(v == 1)
printf(”％d\n”， w);
else
printf(”％d/%d\n”, w, v);
}
void swap(int &x, int &y) {
int t = x; x = y; y = t;
}
int main() {
scanf("％d %d", &n， &B);
for(int i = 1; i <= n; i ++) {
scanf(”％d%d，&w[i]， &v[i]);
}
for(int i = 1; i < n; i ++)
for(int j = 1; j < n; j ++)
if(①){
swap(w[j], w[j + 1])；
swap(v[j]，v[j + 1])；
}
int curV, curW;
if（②） {
③
} else {
print(B * w[1], v[1]);
return 0;
}
for(int i = 2; i <= n; i ++)
if(curV + v[i] <= B) {
curV += v[i];
curW += w[i];
} else {
print(④)；
return 0;
}
print (⑤)；
return 0;
}
34、①处应填()
A W[j] / v[j] < w[j+1]/v[j+1]
B W[j] / v[j]> w[j+1]/v[j+1]
C v[j] * w[j+1]< v[j+1]*w[j]
D w[j] * v[j+1]< w[j+1]*v[j]
解析：【喵呜刷题小喵解析】：题目提示将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择，因此①处应填W[j] / v[j] > w[j+1]/v[j+1]。这样排序后，每次选择蛋糕时，都选择性价比最高的蛋糕，即价值与体积的比值最大的蛋糕，可以确保最后得到的蛋糕的价值之和最大。
35、②处应填（）
A w[1] <= B
B v[1] <= B
C w[1] >= B
D v[1] >= B
解析：【喵呜刷题小喵解析】：
在②处，应该填写条件判断蛋糕1能否放入盒子中，即w[1] <= B。因为题目要求蛋糕可以任意切割，所以首先尝试放入价值最高的蛋糕，即w[1]。如果w[1]大于B，说明蛋糕1无法放入盒子中，直接输出当前价值和体积，即print(B * w[1], v[1])，并结束程序。如果w[1]小于等于B，则继续考虑后面的蛋糕。
因此，选项A w[1] <= B是正确的。
36、③处应填()
A print(v[1]w[1]); return 0;
B curV = 0; curW = 0;
C print(w[1] v[1]); return 0;
D curV = v[1]; curW = w[1];
解析：【喵呜刷题小喵解析】
首先，根据题目描述，我们需要将蛋糕按照性价比从大到小排序。在给出的代码中，①处应该填写一个条件判断，用于交换蛋糕的价值和体积，使得数组按照性价比从大到小排序。
然后，我们需要判断第一个蛋糕是否可以被放入盒子中。如果可以，我们初始化curV和curW为蛋糕的体积和价值，准备进行后续的贪心选择。如果不能，我们直接输出蛋糕的价值，并结束程序。
对于③处，根据题目的提示，我们需要将第一个蛋糕放入盒子中，因此curV和curW应该被更新为蛋糕的体积和价值。
对于④处，我们需要输出当前已经放入盒子的蛋糕的价值。由于我们已经按照性价比从大到小排序，所以当前已经放入盒子的蛋糕的价值就是curW。
最后，我们输出最后放入盒子的蛋糕的价值，也就是curW和v[i]的差值。
根据以上分析，我们可以得出，③处应该填入的选项是D，即curV = v[1]; curW = w[1];。这样，我们可以确保第一个蛋糕被正确放入盒子中，并准备进行后续的贪心选择。
37、④处应填（）
A curW * v[i] + curV * w[i], v[i]
B (curW - w[i]) * v[i] + (B - curV) * w[i], v[i]
C curW + v[i], w[i]
D curW * v[i] * (B - curV) * w[i], v[i]
解析：【喵呜刷题小喵解析】：在程序中，对于每一块蛋糕，我们考虑将其放入当前的累积价值和体积中，或者单独放入盒子中。为了决定最优方案，我们需要计算当前方案（加入当前蛋糕）和单独放入蛋糕的价值比。
对于当前方案，价值是curW + w[i]，体积是curV + v[i]。
对于单独放入蛋糕，价值是w[i]，体积是v[i]。
所以，我们需要比较两者的性价比，即：
性价比 = (curW + w[i]) / (curV + v[i]) 和 w[i] / v[i]。
为了使性价比最大，我们应该选择使性价比更大的方案。如果(curW + w[i]) / (curV + v[i])大于w[i] / v[i]，那么将蛋糕加入当前累积中更有利。否则，单独放入蛋糕更有利。
根据这个思路，我们可以计算出放入当前累积的价值和体积应该是：(curW - w[i]) * v[i] + (B - curV) * w[i]。所以，选项B是正确的。
38、⑤处应填（）
A curW, curV
B curW，1
C curV, curW
D curV，1
解析：【喵呜刷题小喵解析】
根据题目提示，需要将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。在程序中，排序后需要依次将蛋糕放入盒子中，直到盒子装不下为止。在放入蛋糕时，需要判断当前蛋糕是否能装下，如果可以装下，则将当前蛋糕的价值和体积加到当前盒子中的总价值和总体积中；如果不能装下，则输出当前盒子中的蛋糕的总价值和总体积，然后结束程序。
对于选项C，curV和curW分别表示当前盒子中的蛋糕的总体积和总价值。在程序中的if(curV + v[i] <= B)中，判断当前蛋糕是否能装下，如果可以装下，则将当前蛋糕的价值和体积加到curW和curV中。如果不能装下，则输出curW和curV，然后结束程序。因此，选项C是正确的。
（最优子序列）取m=6，给出长度为n的整数序列a1,a2，……an（0 ≤ ai<2m）。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1，b2，…，bk，定 义其子序列分值S为w（b1㊉b2）+w（b2㊉b3）+w（b3㊉b4）+……+w（bk-1㊉bk）。其中㊉表示按位异或。对于空子序列，规定其子序列分值为0。求一个子序列使得其子序列分值最大，输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1，a2，……，an。
提示：考虑优化朴素的动态规划算法，将前
位和后位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
39、①处应填（）
A X >>= 1
B X ^=X & (x ^ (x + 1))
C X -= X | -X
D X ^= X & (X ^ (x - 1))
解析：【喵呜刷题小喵解析】
在动态规划算法中，为了优化计算，我们需要将前`$2^{m-k}$`位和后`$2^{m-k}$`位分开计算。
考虑当前的子序列下一个位置的高8位是X、最后一个位置的低8位是y时的最大价值。我们需要根据题目中的定义来计算这个价值。
定义w(x)为x + popcnt(x)，其中popcnt(x)表示x二进制表示中1的个数。
为了得到X，我们需要对当前的数a进行异或操作，即：
X = a ^ (a - 1)
同时，我们还需要得到a的低8位，即：
y = a & (2^8 - 1)
因此，为了得到X，我们需要进行以下操作：
X = a ^ (a - 1)
= a ^ ((a ^ a) - 1)
= a ^ (a ^ (a & -a))
= a ^ (a ^ ((~a) + 1))
= a ^ ((a ^ ~a) | 1)
= a ^ ((a & (~a + 1)) | 1)
= a ^ (a & ((a - 1) & (~a)))
= a ^ (a & ((a & ~a) - 1))
= a ^ (a & (a & (~a)))
= a ^ (a & ((~a) | a))
= a ^ (a & (a | ~a))
= a ^ (a & (a ^ ~0))
= a ^ (a & (a ^ ((1 << m) - 1)))
由于a的范围在0到`$2^m-1$`之间，所以`(1 << m) - 1`即为`$2^m-1$`，与a进行异或操作可以得到a的高位。
因此，我们只需要将a与`$2^m-1$`进行异或操作，再与a进行与操作，即可得到a的高位X。
所以，①处应填：X ^= X & (X ^ (X + 1))。
因此，答案为B。
40、②处应填（）
A (a & MS) « B
B a>>B
C a&(1<<B)
D a&(MS<<B)
解析：【喵呜刷题小喵解析】
根据题目描述，我们需要找到一种方法来优化动态规划算法，使得在计算过程中将前一半和后一半分开计算。为了实现这个目标，我们需要使用一个特定的技巧，即将异或操作中的每一位进行分开处理。
考虑到给定的整数序列a1, a2, ..., an的范围限制为0 ≤ ai < 2^m，我们可以将每个数分为两部分，即高m位和低m位。在这里，m=6，所以我们将每个数分为高8位和低8位。
在动态规划的过程中，我们需要记录当前子序列的下一个位置的高8位是X、最后一个位置的低8位是y时的最大价值。这可以通过使用一个二维数组Max[x][y]来实现。
对于给定的选项，我们需要找到一个操作，使得我们可以将当前数的高8位和低8位分开处理。在二进制运算中，左移操作(<<)和右移操作(>>)是常用的操作，但在这里，我们需要将高8位和低8位分开，而不是移动它们。
为了将高8位和低8位分开，我们可以使用按位与(&)操作。具体来说，我们可以将当前数与一个特定的掩码(mask)进行按位与操作，该掩码的高8位全为1，低8位全为0。这样，我们就可以得到当前数的高8位和低8位。
对于高8位，我们可以使用掩码的高8位与当前数进行按位与操作，即a & (MS)。对于低8位，我们需要将当前数左移B位（在这里，B=8），然后再与掩码进行按位与操作，即a & (MS << B)。
因此，选项D中的a & (MS << B)是正确的操作，用于将当前数的高8位和低8位分开处理。
41、③处应填（）
A -INF
B Max[y] [x]
C 0
D Max[x][yJ
解析：【喵呜刷题小喵解析】：
在程序中，Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的低8位是y时的最大价值。在计算Max[x][y]时，我们需要考虑两种情况：
1. 如果当前位置i的数值a[i]的高8位是x，低8位是y，那么Max[x][y]的值应该等于Max[x][y]和w(a[i])的较大值。这是因为a[i]可以加入到子序列中，也可以不加入，取决于是否更优。
2. 如果当前位置i的数值a[i]的高8位不是x，那么a[i]不能加入到以x为高8位的子序列中，因此Max[x][y]的值应该等于Max[x][y]和Max[x'][y]的较大值，其中x'是a[i]的高8位。这是因为我们可以选择忽略a[i]，而选择其他以x'为高8位的子序列。
因此，对于③处，我们应该填写Max[x][y]，表示以x为高8位、以y为低8位的子序列的最大价值。因此，选项D是正确的。
42、④处应填（）
A Max[x] [z]+w（y^z）
B Max[x][z] + w(a ^ z)
C Max[x] [z]+w（x^(z<<B）)
D Max[x][z] + w(x ^ z)
解析：【喵呜刷题小喵解析】
根据题目描述，Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。在求下一个位置的高8位是X、最后一个位置的 低8位是z时的最大价值时，需要将当前位置的数a与z进行异或运算，即a^z，然后加上Max[x][z]的值。因此，④处应填Max[x][z] + w(a ^ z)。选项D正确。
43、⑤处应填()
A to_max(Max[y][z],v + w(a ^(z << B)))
B to_max(Max[z][y],v + w((x ^ z) << B))
C to_max(Max[zJ[y],v + w(a ^ (z << B)))
D to_max(Max[x][z],v + w(y ^ z))
解析：【喵呜刷题小喵解析】
根据题目描述，我们需要找到一个子序列，使得其子序列分值最大。题目中给出了一个动态规划的思路，将前$2^B$位和后$2^B$位分开计算。
在动态规划的过程中，我们需要维护一个二维数组$Max[x][y]$，其中$x$表示当前的子序列下一个位置的高$B$位，$y$表示最后一个位置的低$B$位。
对于当前位置$i$，如果我们将$a_i$加入到子序列中，那么子序列的下一个位置的高$B$位变为$a_i$的高$B$位，最后一个位置的低$B$位变为$a_i$的低$B$位。
此时，我们需要计算加入$a_i$后的子序列分值，即$w(b_{k-1} \oplus b_k)$，其中$b_{k-1}$表示子序列中倒数第二个元素，$b_k$表示子序列中最后一个元素。
由于$b_{k-1}$和$b_k$都是$2^B$位的二进制数，我们可以将$b_{k-1}$和$b_k$分别拆分为高$B$位和低$B$位，即$b_{k-1} = x \oplus y$，$b_k = z \oplus (a \ll B)$，其中$x$和$z$分别表示$b_{k-1}$和$b_k$的高$B$位，$y$和$a$分别表示$b_{k-1}$和$b_k$的低$B$位。
因此，我们需要计算$w(x \oplus z \oplus (a \ll B))$，即$w(x \oplus z) + w(a \ll B)$。
在动态规划的过程中，我们需要更新$Max[x][y]$，即$Max[x][y] = \max(Max[x][y], Max[x'][y'] + w(a \ll B))$，其中$x'$和$y'$表示前一个位置的高$B$位和低$B$位，$a$表示当前位置的元素。
最后，我们需要找到最大的子序列分值，即$\max(Max[x][y])$。
因此，⑤处应该填$to\_max(Max[y][z], v + w(a \ll B))$，其中$y$表示前一个位置的低$B$位，$z$表示前一个位置的高$B$位，$a$表示当前位置的元素，$v$表示$Max[x'][y']$，$x'$表示前一个位置的高$B$位，$y'$表示前一个位置的低$B$位。
选项A符合上述要求，因此选择A。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
