如果想过csp-j的初赛本卷应在60左右满分 100 分。请在答题纸上作答写在试题纸上的一律无效。不得使用任何电子设备如计算器、手机、电子词典等或查阅任何书籍资料。一、 单项选择题共 15 题 每题 2 分 共计 30 分; 每题有且有一个正确选项)1. 有一个 int 类型的变量 a以下表达式得到的结果和 a/2 一致是 ( )。A. a 1B. a 1C. a | 1D. a ^ 1答案解析:正确答案 B。右移操作能实现求变量的一半。2. 以下叙述正确的是 ( )。A. 在一个程序中允许使用任意数量的#include 命令行B. 在包含文件中不得再包含其他文件C. #include 命令行不能出现在程序文件的中间D. 虽然包含文件被修改了包含该文件的源程序也可以不重新进行编译和连接答案解析:正确答案 A。预处理中文件包含的概念包含文件中可以包含其他文件 B 选项错误#include 可以出现在程序文件的中间 C 选项错误包含文件被修改了包含该文件的源程序必须重新进行编译和连接。3. 有 2 名老师和 4 名获奖学生排成一排拍照如果老师不能站在队伍两端则有( )种排队方式。A. 288B. 256C. 216D. 312答案解析:正确答案 A。先排列4个学生一共有A4 4种排列方式先让其中一个老师站在已有的队伍中间有三个空位3 种站法。再让另一个老师站在 4 个空位中的一个有 4 种所以一共有 24*3*4288 种站法。4. 将 6 相同的书分给 3 个人每个人至少有一本一共有( )种分法。A. 6B. 10C. 3D. 12答案解析:正确答案 B。每个人必须分一本所以一个人手里先拿走一本剩下 3 本书分给三个人有三种分法3、0、0,2、1、0,1、1、1其中 3、0、0 有 3 种情况2、1、0 有3*2*16 种1、1、1 只有 1 种加起来一共有 10 种。5. 下列说法不正确的是 ( )。A. RAM 是与中央处理器直接交换数据的内部存储器可以随时读写而且速度很快B. CPU 的主要功能是解释计算机指令以及处理计算机软件中的数据C. ROM 只要存储了就无法被修改或删除数据不会因为电源关闭而消失D. Cache 的访问速度一般比 RAM 的访问速度慢答案解析:正确答案 D。Cache 的访问速度一般比 RAM(随机存储器)快。6. 下面的四种排序其排序的稳定性与其他选项中的排序不同的是?( )A. 插入排序B. 冒泡排序C. 归并排序D. 快速排序正确答案D选择排序、快速排序、希尔排序、堆排序是不稳定的排序算法冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。故 D 对A、B、C 错。知识点排序算法稳定性7. 下列选项中的排序算法空间复杂度最高的是?( )A. 归并排序B. 快速排序C. 选择排序D. 插入排序正确答案A知识点复杂度8. 下列选项中能用二分法进行查找的是?( )A. 数组B. 二叉链表C. 单链表D. 双链表答案解析正确答案A能够进行二分查找的条件1 顺序存储2 有序数组满足这两个条件故 A 对B、C、D 错。知识点二分9. 有一个图的邻接表如下图从顶点 a 出发的话那么广度优先遍历的结果是?( )A. abdcBacdbCabcdDadbc正确答案C给定邻接表从顶点 a 出发直接读取邻接表第一行a b c da b c d 为顶点全集。知识点图的广搜10. 有五个叶结点权值依次 27,10,18,5,25将这 5 个叶结点构成哈夫曼树为的话则带权路径长度是( )。A. 85B. 185C. 215D. 300正确答案C哈夫曼树构成过程1 将 5 个结点放入集合 T{27,10,18,5,25}2 从 T 中取出没有双亲且权值最小的两个结点进行合并成新的一棵树并将新树 t1 插入到集合中并将左右子树从集合中删除3 重复 2 操作直到集合 T 中只剩下一棵树注意通常权值小的是左子树大的右子树左小右大如果两个结点的权值相等先出现的结点为左子树新生成的结点按照生成顺序排在所有叶结点的后面27,10,18,5,255 和 10 合并成 15将 15 放入集合 T 中{27,15,18,25}15 和 18 合并成 33将 33 放入集合 T 中{27,33,25}此时将 25 和 27 合并成 52将 52 放入集合 T 中{33,55}目前情况树的带权路径长度为根节点到叶结点的路径长度*叶结点的权值对每个叶节点的和。计算路径长度5*310*315*218*225*227*2215知识点贪心哈夫曼树11. 以下有关线性结构和非线性结构说法正确的是( )。A. 线性结构与非线性结构针对的是数据的物理结构。B. 栈、队列、链表和集合结构都属于线性结构。C. 像树和图这种元素与元素之间是多对多关系的结构都属于非线性结构。D. 线性结构要求每个元素最多只有一个直接前驱和直接后继。正确答案D解析线性结构与非线性结构针对的是数据的逻辑结构主要用来描述数据与数据之间关系栈、队列和链表属于线性结构集合结构属于非线性结构树和图属于非线性结构树中元素是一对多的关系图是多对多的关系线性结构要求每个元素最多只有一个直接前驱和直接后继非线性结构每个元素可以有不止一个直接前驱和直接后继。所以 D 选项正确。12. 已知表达式的前缀表达式为- * / - / * 4 6 12 2 2 2 4 1其后缀表达式为( )。A. 4 6 * 12 / 2 2 - 2 4 * 1 - /B. 4 6 * 12 2 2 - / 2 / 4 * 1 -C. 4 6 * 12 / 2 2 2 / 4 * - 1 -D. 4 6 * 12 / 2 2 - 2 / 4 * 1 -正确答案D解析前缀表达式为中缀表达式按计算顺序加上小括号之后把运算符放到相应小括号前面再把小括号删除得到的该前缀表达式对应的中缀表达式为(4*6/122-2)/2*4-1中缀转后缀表达式为按计算顺序加上小括号之后把运算符放到相应小括号后面再把小括号删除转后缀表达式为 4 6 * 12 / 2 2 - 2 / 4 * 1 -所以 D 选项正确。13. 若使用数组模拟普通队列且 front 表示队首元素位置rear 表示队尾元素的下一个位置以下哪一个选项可以获取队列中的元素个数( )。A. rearB. rear - front - 1C. rear - front 1D. rear - front正确答案D解析在普通队列中所有元素的范围为 front ~ rear - 1元素个数为 rear- 1 - front 1 rear - front。14. 已知二叉树后序序列为 HDAEIGKFBC中序序列为 DHAECBGIFK则先序序列为( )。A. CEADHBFKIGB. CEADHBFGIKC. CBFGIKEADHD. CBFKGIEADH正确答案B解析根据后序序列最后一个元素可以确定出根结点为 C在中序中可以找到左子树节点为 DHAE右子树节点为 BGIFK对于左右子树根据左右子树的后序和中序序列可以确定左右子树的节点分布从而得到整棵二叉树根据画出的二叉树可以得到先序序列为 CEADHBFGIK所以 B 选项正确。15. 存在一个连通图其边集为 E{(A,B),(A,C),(A,D),(C,D),(D,E)}若只删除 1 个点 v使得该连通图变成非连通图则可选取的 v 的个数为( )。A. 1B. 2C. 3D. 4正确答案B解析根据边集可画出该连通图为:由图可知删除 A 点或 D 点后图会变成一个非连通图所以 B 选项正确。二、阅读程序 (程序输入不超过数组或字符串定义的范围判断题正确填√错误填 x; 除特殊说明外判断题 1.5 分选择题 3 分共计 40 分)(1)01 #include iostream 02 #include cmath 03 using namespace std; 04 long long m,n,ans; 05 int z(int n,int m){ 06 return n%m ? z(m,n%m) : m; 07 } 08 09 int main() { 10 cin m n; 11 n * m; 12 for(long long i 1;i sqrt(n);i){ 13 if(n%i0 z(i,n/i)m) ans 1; 14 } 15 coutans; 16 return 0; 17 }假设输入的所有数都为不超过 1000 的正整数完成下面的判断题和单选题判断题16. 当输入为“3 60”时输出为“3”。( )17. 将第 12 行的 for 循环的大括号去掉代码也能正常运行。( )18. (2 分) 把第 12 行 for 循环的条件改为“in”得到的结果是原有结果的两倍。( )单选题19. 当输入为“2 60”时输出为( )。A. “2” B. “3” C. “4” D. “5”20. 当输入为“12 3”时输出为( )。A. “2” B. “1” C. “0” D. “3”答案16. × 17. √ 18. × 19. C 20. C解析16 题运行的结果是错误的得到的结果为 2在 i 等于 3 和 12 的时候满足。17 题是正确的循环内只有一条语句可以不使用大括号。18 题错误当输入的 m和 n 相等时更改条件的结果是一致的。19 题选择选项 C。n 的值为 120 在 i 的值为 2610 时满足情况。20 题选择选项 C。i 循环的范围是从 1 到 6其中不会出现最大公约数为 12 的数字最大公约数不可能比其中一个数字大(2)#include iostream 02 #include vector 03 using namespace std; 04 vectorstring split(string s, char c) { 05 vectorstring res {}; 06 int i 0; 07 for (int j 0; j s.length(); j) { 08 if (s[j] c) { 09 string temp s.substr(i, j - i); 10 res.push_back(temp); 11 i j 1; 12 } 13 } 14 res.push_back(s.substr(i, s.length() - i)); 15 return res; 16 } 17 bool isvalid(string s) { 18 vectorstring v split(s, .); 19 if (v.size() ! 4) 20 return false; 21 for (int i 0; i v.size(); i) { 22 string cur v[i]; 23 int len cur.length(); 24 if (len 0 || len 3) 25 return false; 26 if (cur[0] 0 len ! 1) 27 return false; 28 for (int j 0; j len; j) { 29 if ((cur[j] 0 cur[j] 9) || (cur[j] a cur[j] f) || (cur[j] A cur[j] F)) 30 continue; 31 else 32 return false; 33 } 34 if (stoi(cur) 0 || stoi(cur) 255) 35 return false; 36 } 37 return true; 38 } 39 string strp; 40 int main() { 41 while (cin strp strp ! endl) { 42 bool res isvalid(strp); 43 cout res ? Yes : No; 44 cout endl; 45 } 46 return 0; 47 }判断题21. 将第 7 行代码的 s.length() 修改成 s.sizeof()不影响程序的正确执行。( )22. 去掉 14 行代码程序无法正确运行结果。( )23. 将 26 行代码 len ! 1 替换成 len 1,程序无法运行出正确的结果。 ( )。单选题24. 当输入 192.168.31.010程序的输出结果是( )。A. Yes B. No C. 1 D. 025. 当输入 192.256.1.18程序的输出结果是( )。A. Yes B. No C. 1 D. 026. 当输入175.18.254.10192..168.8123.a.88.09255.0.00.2510.0.0.0endl程序的输出结果是( )。A. 1 0 0 1 1 B. 1 1 0 0 1 C. 1 0 0 0 1 D. 0 0 0 1 1答案21. × 22. √ 23. × 24. D 25. D 26. C解析21 错误s.length()是获取字符串的长度sizeof()函数是用来计算所占的字节数22 正确该行代码是将输入的 ip 地址字符串的最后一组数字截取出来存储到res 中如果删除该行代码就少 ip 地址的最后一组23 错误判断 IP 地址的每一组中的 0 的个数如果第一个是 0保证不能存在多个 0比如 00只需保证长度大于 1 就可以24 分析程序该程序实现的功能是检测输入的 ip 地址是否合法的重点isvalid 函数用来检测各种满足正确 ip 地址的条件1 ip 地址有四组数字组成2 每个字串字串长度为 0、或者大于 3不合法3 非 0 字串是有前置 0不合法4 字串中包含除数字外的字符不合法5 输入的 ip 字符串长度越界不合法192.168.31.010 中的第四组不满足条件 3正确的应该是 01在代码 43行使用三目运算进行结果的输出它的优先级低于会直接输出 res 的值bool类型的 res 会自动升级为 int 类型的 0答案是 D。25 解析同上192.256.1.18 中的第二组数字 256 超过了最大值限制 255不合法输出 0答案选 D26 175.18.254.10 合法 1192..168.8 不合法 不够四组123.a.88.09 不合法 第二组含有字母255.0.00.251 不合法 第三组有前置 00.0.0.0 合法输出结果是 1 0 0 0 1答案选 C(3)01 #include iostream 02 #include set 03 #include vector 04 using namespace std; 05 int n, k, v[21]; 06 setint st; 07 08 void f(int num, int sum, int idx){ 09 if(num k){ 10 st.insert(sum); 11 return; 12 } 13 for(int i idx; i n; i){ 14 f(num 1, sum v[i], i 1); 15 } 16 } 17 int main(){ 18 cin n k; 19 for(int i 0; i n; i){ 20 cin v[i]; 21 } 22 f(0, 0, 0); 23 cout st.size(); 24 return 0; 25 }判断题27. 该程序是从 n 个整数中任选 k 个整数输出选法的数量。( )28. 如果将第 13 行的 idx 修改为 0程序结果不变。( )29. 如果将第 11 行删除程序结果不变。( )单选题30. 当输入为 3 2 1 2 2 时输出为( )。A. 1 B. 2 C. 3 D. 431. 当输入为 5 3 1 2 4 6 7 时第 14 行的执行次数为( )。A. 10 B. 15 C. 20 D. 2532. 当输入为 5 4 1 2 1 5 2 时输出为( )。A. 1 B. 2 C. 3 D. 4答案27. × 28. × 29. √ 30. B 31. D 32. C解析该程序为从输入的 n 个整数中任选 k 个整数进行相加求和使用 set 存储和去重后输出所有可能的不同和出现的次数。27.该程序使用 set 去重了所以输出的是不同和出现的次数所以错误。28.idx 修改为 0 之后k 个位置选数时每个位置都从所有数中选所以会出现同一数字使用多次所以结果可能会变所以错误。29.将 11 行的 return 删除后不影响 k 个数选完后统计结果所以对结果没有影响所以正确。30.输入为 3 2 1 2 23 个数选 2 个求和求不同和出现次数不同和为 123、224总共 2 个所以 B 选项正确。31.输入为 5 3 1 2 4 6 75 个数选 3 个第 1 个位置会放 1 2 4 6 7 各一次第 1 个位置 1第 2 个位置 2 4 6 7 各一次第 2 个位置 2第 3 个位置 4 6 7 各一次按照此规律推导第 14 行的递归调用总执行次数为 25 次。32.输入为 5 4 1 2 1 5 25 个数选 4 个不同的和的个数为 12159、12126、125210 这 3 个所以 C 选项正确。三、完善程序单选题每小题 3 分共计 30 分(1)区间查找问题给你一个遵循递增原则的序列和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。试补全程序。33. ①处填写的代码为( )A. start B. end C. last D. mid34. ②处填写的代码为( )A. startend B. start!endC. start end D. startmiddle35. ③处填写的代码为( )A. start B. end C. last D. mid36. ④处填写的代码为( )A. serchright(a,target,1)B. serchleft(a,n,target)C. serchleft(a,n,1)D. serchleft(a,target,n)37. ⑤处填写的代码为( )A. %d,%d,l,rB. [%d,%d],l,rC. [%d,%d],r,lD. %d,%d,l-1,r1解析答案33. A 34. C 35. C 36. D 37. B题目描述数组是有序的然后要求找等于 target 的第一个位置和等于 target 的最后一个位置。找等于 target 的一个位置可以等价于求 target 的第一个位置找等于 target 的最后一个位置可以等价于求 target1 的第一个位置 - 1因为问题的难点就变成了如何快速找到大于等于 target 的第一个元素位置。假设数组还有没有被标记成红色或蓝色的数组左端点为 left, 数组右端点为right.分成两次去分别查找第一次出现的位置 first 及最后出现的位置 last。查找左端点时如果中点元素等于 target 则可以说明[left, mid]的元素仍会出现目标值 target, 那么将 right 重新指向[left, mid]的右端点即 right mid - 1只要 left right, 就一直指向上述操作。在每次出现目标时记录对应位置循环结束后第一次和最后一次出现的位置分别记录在 first 和 last 当中(2)cc 冒险问题cc 在进行一次森林大冒险冒险的路程是一条曲折幽暗的森林之路在第 i 个位置上会发生一件事情用(ti, xi)表示。若 ti 1则表示这里有一个 xi的神奇魔力的蘑菇。cc 可以选择捡起放自己的背包里也可以选择不捡起若 ti 2则表示这里有一个 xi可怕的怪兽需要用一个 xi魔力的蘑菇才能打败它。你需要求出在 cc 能打败所有怪兽的情况下每个时刻手中的蘑菇数的最大值最小是多少。若不能打败所有怪兽输出-1。试补全程序38. ①处应该填( )A. st[x[i]].push_back(i) B. st[x[i]].push(i)C. st[x[i]].push_front(i) D. st[x[i]].push_top(i)39. ②处应该填( )A. cout -1;return 0; B. cout-1C. return 0; D. return 0;cout-140. ③处应该填( )A. st[x[i]].pop_top() B. st[x[i]].pop_front()C. st[x[i]].pop_back() D. st[x[i]].pop()41. ④处应该填( )A. break B. maxn max(maxn, cnt)C. t[i]1 D. cntmaxn42. ⑤处应该填( )A. cnt-- B. cnt C. t[i]1 D. t[i]0答案38. B 39. A 40. D 41. B 42. A解析可以发现一个蘑菇无论什么时候拿被使用掉的时间都是不会变的所以如果我们想让一个蘑菇在背包里待得时间尽可能的短就要让它尽可能的被晚拿起来于是我们就可以想到使用栈存下每一瓶同类的蘑菇分别出现的时间此时每遇到一只怪物那么它对应的栈顶就是最晚出现的蘑菇使用该蘑菇并打上标记。如果栈空则说明蘑菇不够cc 就完了。最后统计每时每刻背包容量最大值输出即可。38.B 考察 stl 中栈的存储方式应该 push()方法。39.A st[x[i]].size() 0 代表蘑菇不够的时候根据题目要求要输出-1同时需要结束程序运行 return 0;40.D flag[st[x[i]].top()] 1;阅读程序这段代码告诉我们打上标记记为使用该蘑菇那么就要给这个蘑菇出栈蘑菇被用掉了stl 中 stack 出栈的操作是pop()方法。41.B flag[i] 0 是表示背包里多进一个蘑菇我们要将 cnt 计数加一同时根据题目要求来更新 maxn 的值42.A t[i] 2 表示用掉一个蘑菇那应该让 cnt 计数减去 1 2026 csp-j 模拟卷
如果想过csp-j的初赛本卷应在60左右满分 100 分。请在答题纸上作答写在试题纸上的一律无效。不得使用任何电子设备如计算器、手机、电子词典等或查阅任何书籍资料。一、 单项选择题共 15 题 每题 2 分 共计 30 分; 每题有且有一个正确选项)1. 有一个 int 类型的变量 a以下表达式得到的结果和 a/2 一致是 ( )。A. a 1B. a 1C. a | 1D. a ^ 1答案解析:正确答案 B。右移操作能实现求变量的一半。2. 以下叙述正确的是 ( )。A. 在一个程序中允许使用任意数量的#include 命令行B. 在包含文件中不得再包含其他文件C. #include 命令行不能出现在程序文件的中间D. 虽然包含文件被修改了包含该文件的源程序也可以不重新进行编译和连接答案解析:正确答案 A。预处理中文件包含的概念包含文件中可以包含其他文件 B 选项错误#include 可以出现在程序文件的中间 C 选项错误包含文件被修改了包含该文件的源程序必须重新进行编译和连接。3. 有 2 名老师和 4 名获奖学生排成一排拍照如果老师不能站在队伍两端则有( )种排队方式。A. 288B. 256C. 216D. 312答案解析:正确答案 A。先排列4个学生一共有A4 4种排列方式先让其中一个老师站在已有的队伍中间有三个空位3 种站法。再让另一个老师站在 4 个空位中的一个有 4 种所以一共有 24*3*4288 种站法。4. 将 6 相同的书分给 3 个人每个人至少有一本一共有( )种分法。A. 6B. 10C. 3D. 12答案解析:正确答案 B。每个人必须分一本所以一个人手里先拿走一本剩下 3 本书分给三个人有三种分法3、0、0,2、1、0,1、1、1其中 3、0、0 有 3 种情况2、1、0 有3*2*16 种1、1、1 只有 1 种加起来一共有 10 种。5. 下列说法不正确的是 ( )。A. RAM 是与中央处理器直接交换数据的内部存储器可以随时读写而且速度很快B. CPU 的主要功能是解释计算机指令以及处理计算机软件中的数据C. ROM 只要存储了就无法被修改或删除数据不会因为电源关闭而消失D. Cache 的访问速度一般比 RAM 的访问速度慢答案解析:正确答案 D。Cache 的访问速度一般比 RAM(随机存储器)快。6. 下面的四种排序其排序的稳定性与其他选项中的排序不同的是?( )A. 插入排序B. 冒泡排序C. 归并排序D. 快速排序正确答案D选择排序、快速排序、希尔排序、堆排序是不稳定的排序算法冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。故 D 对A、B、C 错。知识点排序算法稳定性7. 下列选项中的排序算法空间复杂度最高的是?( )A. 归并排序B. 快速排序C. 选择排序D. 插入排序正确答案A知识点复杂度8. 下列选项中能用二分法进行查找的是?( )A. 数组B. 二叉链表C. 单链表D. 双链表答案解析正确答案A能够进行二分查找的条件1 顺序存储2 有序数组满足这两个条件故 A 对B、C、D 错。知识点二分9. 有一个图的邻接表如下图从顶点 a 出发的话那么广度优先遍历的结果是?( )A. abdcBacdbCabcdDadbc正确答案C给定邻接表从顶点 a 出发直接读取邻接表第一行a b c da b c d 为顶点全集。知识点图的广搜10. 有五个叶结点权值依次 27,10,18,5,25将这 5 个叶结点构成哈夫曼树为的话则带权路径长度是( )。A. 85B. 185C. 215D. 300正确答案C哈夫曼树构成过程1 将 5 个结点放入集合 T{27,10,18,5,25}2 从 T 中取出没有双亲且权值最小的两个结点进行合并成新的一棵树并将新树 t1 插入到集合中并将左右子树从集合中删除3 重复 2 操作直到集合 T 中只剩下一棵树注意通常权值小的是左子树大的右子树左小右大如果两个结点的权值相等先出现的结点为左子树新生成的结点按照生成顺序排在所有叶结点的后面27,10,18,5,255 和 10 合并成 15将 15 放入集合 T 中{27,15,18,25}15 和 18 合并成 33将 33 放入集合 T 中{27,33,25}此时将 25 和 27 合并成 52将 52 放入集合 T 中{33,55}目前情况树的带权路径长度为根节点到叶结点的路径长度*叶结点的权值对每个叶节点的和。计算路径长度5*310*315*218*225*227*2215知识点贪心哈夫曼树11. 以下有关线性结构和非线性结构说法正确的是( )。A. 线性结构与非线性结构针对的是数据的物理结构。B. 栈、队列、链表和集合结构都属于线性结构。C. 像树和图这种元素与元素之间是多对多关系的结构都属于非线性结构。D. 线性结构要求每个元素最多只有一个直接前驱和直接后继。正确答案D解析线性结构与非线性结构针对的是数据的逻辑结构主要用来描述数据与数据之间关系栈、队列和链表属于线性结构集合结构属于非线性结构树和图属于非线性结构树中元素是一对多的关系图是多对多的关系线性结构要求每个元素最多只有一个直接前驱和直接后继非线性结构每个元素可以有不止一个直接前驱和直接后继。所以 D 选项正确。12. 已知表达式的前缀表达式为- * / - / * 4 6 12 2 2 2 4 1其后缀表达式为( )。A. 4 6 * 12 / 2 2 - 2 4 * 1 - /B. 4 6 * 12 2 2 - / 2 / 4 * 1 -C. 4 6 * 12 / 2 2 2 / 4 * - 1 -D. 4 6 * 12 / 2 2 - 2 / 4 * 1 -正确答案D解析前缀表达式为中缀表达式按计算顺序加上小括号之后把运算符放到相应小括号前面再把小括号删除得到的该前缀表达式对应的中缀表达式为(4*6/122-2)/2*4-1中缀转后缀表达式为按计算顺序加上小括号之后把运算符放到相应小括号后面再把小括号删除转后缀表达式为 4 6 * 12 / 2 2 - 2 / 4 * 1 -所以 D 选项正确。13. 若使用数组模拟普通队列且 front 表示队首元素位置rear 表示队尾元素的下一个位置以下哪一个选项可以获取队列中的元素个数( )。A. rearB. rear - front - 1C. rear - front 1D. rear - front正确答案D解析在普通队列中所有元素的范围为 front ~ rear - 1元素个数为 rear- 1 - front 1 rear - front。14. 已知二叉树后序序列为 HDAEIGKFBC中序序列为 DHAECBGIFK则先序序列为( )。A. CEADHBFKIGB. CEADHBFGIKC. CBFGIKEADHD. CBFKGIEADH正确答案B解析根据后序序列最后一个元素可以确定出根结点为 C在中序中可以找到左子树节点为 DHAE右子树节点为 BGIFK对于左右子树根据左右子树的后序和中序序列可以确定左右子树的节点分布从而得到整棵二叉树根据画出的二叉树可以得到先序序列为 CEADHBFGIK所以 B 选项正确。15. 存在一个连通图其边集为 E{(A,B),(A,C),(A,D),(C,D),(D,E)}若只删除 1 个点 v使得该连通图变成非连通图则可选取的 v 的个数为( )。A. 1B. 2C. 3D. 4正确答案B解析根据边集可画出该连通图为:由图可知删除 A 点或 D 点后图会变成一个非连通图所以 B 选项正确。二、阅读程序 (程序输入不超过数组或字符串定义的范围判断题正确填√错误填 x; 除特殊说明外判断题 1.5 分选择题 3 分共计 40 分)(1)01 #include iostream 02 #include cmath 03 using namespace std; 04 long long m,n,ans; 05 int z(int n,int m){ 06 return n%m ? z(m,n%m) : m; 07 } 08 09 int main() { 10 cin m n; 11 n * m; 12 for(long long i 1;i sqrt(n);i){ 13 if(n%i0 z(i,n/i)m) ans 1; 14 } 15 coutans; 16 return 0; 17 }假设输入的所有数都为不超过 1000 的正整数完成下面的判断题和单选题判断题16. 当输入为“3 60”时输出为“3”。( )17. 将第 12 行的 for 循环的大括号去掉代码也能正常运行。( )18. (2 分) 把第 12 行 for 循环的条件改为“in”得到的结果是原有结果的两倍。( )单选题19. 当输入为“2 60”时输出为( )。A. “2” B. “3” C. “4” D. “5”20. 当输入为“12 3”时输出为( )。A. “2” B. “1” C. “0” D. “3”答案16. × 17. √ 18. × 19. C 20. C解析16 题运行的结果是错误的得到的结果为 2在 i 等于 3 和 12 的时候满足。17 题是正确的循环内只有一条语句可以不使用大括号。18 题错误当输入的 m和 n 相等时更改条件的结果是一致的。19 题选择选项 C。n 的值为 120 在 i 的值为 2610 时满足情况。20 题选择选项 C。i 循环的范围是从 1 到 6其中不会出现最大公约数为 12 的数字最大公约数不可能比其中一个数字大(2)#include iostream 02 #include vector 03 using namespace std; 04 vectorstring split(string s, char c) { 05 vectorstring res {}; 06 int i 0; 07 for (int j 0; j s.length(); j) { 08 if (s[j] c) { 09 string temp s.substr(i, j - i); 10 res.push_back(temp); 11 i j 1; 12 } 13 } 14 res.push_back(s.substr(i, s.length() - i)); 15 return res; 16 } 17 bool isvalid(string s) { 18 vectorstring v split(s, .); 19 if (v.size() ! 4) 20 return false; 21 for (int i 0; i v.size(); i) { 22 string cur v[i]; 23 int len cur.length(); 24 if (len 0 || len 3) 25 return false; 26 if (cur[0] 0 len ! 1) 27 return false; 28 for (int j 0; j len; j) { 29 if ((cur[j] 0 cur[j] 9) || (cur[j] a cur[j] f) || (cur[j] A cur[j] F)) 30 continue; 31 else 32 return false; 33 } 34 if (stoi(cur) 0 || stoi(cur) 255) 35 return false; 36 } 37 return true; 38 } 39 string strp; 40 int main() { 41 while (cin strp strp ! endl) { 42 bool res isvalid(strp); 43 cout res ? Yes : No; 44 cout endl; 45 } 46 return 0; 47 }判断题21. 将第 7 行代码的 s.length() 修改成 s.sizeof()不影响程序的正确执行。( )22. 去掉 14 行代码程序无法正确运行结果。( )23. 将 26 行代码 len ! 1 替换成 len 1,程序无法运行出正确的结果。 ( )。单选题24. 当输入 192.168.31.010程序的输出结果是( )。A. Yes B. No C. 1 D. 025. 当输入 192.256.1.18程序的输出结果是( )。A. Yes B. No C. 1 D. 026. 当输入175.18.254.10192..168.8123.a.88.09255.0.00.2510.0.0.0endl程序的输出结果是( )。A. 1 0 0 1 1 B. 1 1 0 0 1 C. 1 0 0 0 1 D. 0 0 0 1 1答案21. × 22. √ 23. × 24. D 25. D 26. C解析21 错误s.length()是获取字符串的长度sizeof()函数是用来计算所占的字节数22 正确该行代码是将输入的 ip 地址字符串的最后一组数字截取出来存储到res 中如果删除该行代码就少 ip 地址的最后一组23 错误判断 IP 地址的每一组中的 0 的个数如果第一个是 0保证不能存在多个 0比如 00只需保证长度大于 1 就可以24 分析程序该程序实现的功能是检测输入的 ip 地址是否合法的重点isvalid 函数用来检测各种满足正确 ip 地址的条件1 ip 地址有四组数字组成2 每个字串字串长度为 0、或者大于 3不合法3 非 0 字串是有前置 0不合法4 字串中包含除数字外的字符不合法5 输入的 ip 字符串长度越界不合法192.168.31.010 中的第四组不满足条件 3正确的应该是 01在代码 43行使用三目运算进行结果的输出它的优先级低于会直接输出 res 的值bool类型的 res 会自动升级为 int 类型的 0答案是 D。25 解析同上192.256.1.18 中的第二组数字 256 超过了最大值限制 255不合法输出 0答案选 D26 175.18.254.10 合法 1192..168.8 不合法 不够四组123.a.88.09 不合法 第二组含有字母255.0.00.251 不合法 第三组有前置 00.0.0.0 合法输出结果是 1 0 0 0 1答案选 C(3)01 #include iostream 02 #include set 03 #include vector 04 using namespace std; 05 int n, k, v[21]; 06 setint st; 07 08 void f(int num, int sum, int idx){ 09 if(num k){ 10 st.insert(sum); 11 return; 12 } 13 for(int i idx; i n; i){ 14 f(num 1, sum v[i], i 1); 15 } 16 } 17 int main(){ 18 cin n k; 19 for(int i 0; i n; i){ 20 cin v[i]; 21 } 22 f(0, 0, 0); 23 cout st.size(); 24 return 0; 25 }判断题27. 该程序是从 n 个整数中任选 k 个整数输出选法的数量。( )28. 如果将第 13 行的 idx 修改为 0程序结果不变。( )29. 如果将第 11 行删除程序结果不变。( )单选题30. 当输入为 3 2 1 2 2 时输出为( )。A. 1 B. 2 C. 3 D. 431. 当输入为 5 3 1 2 4 6 7 时第 14 行的执行次数为( )。A. 10 B. 15 C. 20 D. 2532. 当输入为 5 4 1 2 1 5 2 时输出为( )。A. 1 B. 2 C. 3 D. 4答案27. × 28. × 29. √ 30. B 31. D 32. C解析该程序为从输入的 n 个整数中任选 k 个整数进行相加求和使用 set 存储和去重后输出所有可能的不同和出现的次数。27.该程序使用 set 去重了所以输出的是不同和出现的次数所以错误。28.idx 修改为 0 之后k 个位置选数时每个位置都从所有数中选所以会出现同一数字使用多次所以结果可能会变所以错误。29.将 11 行的 return 删除后不影响 k 个数选完后统计结果所以对结果没有影响所以正确。30.输入为 3 2 1 2 23 个数选 2 个求和求不同和出现次数不同和为 123、224总共 2 个所以 B 选项正确。31.输入为 5 3 1 2 4 6 75 个数选 3 个第 1 个位置会放 1 2 4 6 7 各一次第 1 个位置 1第 2 个位置 2 4 6 7 各一次第 2 个位置 2第 3 个位置 4 6 7 各一次按照此规律推导第 14 行的递归调用总执行次数为 25 次。32.输入为 5 4 1 2 1 5 25 个数选 4 个不同的和的个数为 12159、12126、125210 这 3 个所以 C 选项正确。三、完善程序单选题每小题 3 分共计 30 分(1)区间查找问题给你一个遵循递增原则的序列和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。试补全程序。33. ①处填写的代码为( )A. start B. end C. last D. mid34. ②处填写的代码为( )A. startend B. start!endC. start end D. startmiddle35. ③处填写的代码为( )A. start B. end C. last D. mid36. ④处填写的代码为( )A. serchright(a,target,1)B. serchleft(a,n,target)C. serchleft(a,n,1)D. serchleft(a,target,n)37. ⑤处填写的代码为( )A. %d,%d,l,rB. [%d,%d],l,rC. [%d,%d],r,lD. %d,%d,l-1,r1解析答案33. A 34. C 35. C 36. D 37. B题目描述数组是有序的然后要求找等于 target 的第一个位置和等于 target 的最后一个位置。找等于 target 的一个位置可以等价于求 target 的第一个位置找等于 target 的最后一个位置可以等价于求 target1 的第一个位置 - 1因为问题的难点就变成了如何快速找到大于等于 target 的第一个元素位置。假设数组还有没有被标记成红色或蓝色的数组左端点为 left, 数组右端点为right.分成两次去分别查找第一次出现的位置 first 及最后出现的位置 last。查找左端点时如果中点元素等于 target 则可以说明[left, mid]的元素仍会出现目标值 target, 那么将 right 重新指向[left, mid]的右端点即 right mid - 1只要 left right, 就一直指向上述操作。在每次出现目标时记录对应位置循环结束后第一次和最后一次出现的位置分别记录在 first 和 last 当中(2)cc 冒险问题cc 在进行一次森林大冒险冒险的路程是一条曲折幽暗的森林之路在第 i 个位置上会发生一件事情用(ti, xi)表示。若 ti 1则表示这里有一个 xi的神奇魔力的蘑菇。cc 可以选择捡起放自己的背包里也可以选择不捡起若 ti 2则表示这里有一个 xi可怕的怪兽需要用一个 xi魔力的蘑菇才能打败它。你需要求出在 cc 能打败所有怪兽的情况下每个时刻手中的蘑菇数的最大值最小是多少。若不能打败所有怪兽输出-1。试补全程序38. ①处应该填( )A. st[x[i]].push_back(i) B. st[x[i]].push(i)C. st[x[i]].push_front(i) D. st[x[i]].push_top(i)39. ②处应该填( )A. cout -1;return 0; B. cout-1C. return 0; D. return 0;cout-140. ③处应该填( )A. st[x[i]].pop_top() B. st[x[i]].pop_front()C. st[x[i]].pop_back() D. st[x[i]].pop()41. ④处应该填( )A. break B. maxn max(maxn, cnt)C. t[i]1 D. cntmaxn42. ⑤处应该填( )A. cnt-- B. cnt C. t[i]1 D. t[i]0答案38. B 39. A 40. D 41. B 42. A解析可以发现一个蘑菇无论什么时候拿被使用掉的时间都是不会变的所以如果我们想让一个蘑菇在背包里待得时间尽可能的短就要让它尽可能的被晚拿起来于是我们就可以想到使用栈存下每一瓶同类的蘑菇分别出现的时间此时每遇到一只怪物那么它对应的栈顶就是最晚出现的蘑菇使用该蘑菇并打上标记。如果栈空则说明蘑菇不够cc 就完了。最后统计每时每刻背包容量最大值输出即可。38.B 考察 stl 中栈的存储方式应该 push()方法。39.A st[x[i]].size() 0 代表蘑菇不够的时候根据题目要求要输出-1同时需要结束程序运行 return 0;40.D flag[st[x[i]].top()] 1;阅读程序这段代码告诉我们打上标记记为使用该蘑菇那么就要给这个蘑菇出栈蘑菇被用掉了stl 中 stack 出栈的操作是pop()方法。41.B flag[i] 0 是表示背包里多进一个蘑菇我们要将 cnt 计数加一同时根据题目要求来更新 maxn 的值42.A t[i] 2 表示用掉一个蘑菇那应该让 cnt 计数减去 1