这是我的第一篇博客有不对之处请提出。题解一、单项选择题共 15 题每题2分共计30分每题有且仅有一个正确选项1. 在C中下面哪个关键字用于声明一个变量其值不能被修改 BA. unsigned B. const C. static D. mutable分析明显这考察的是基础操作“常量”。const才是C中def常量的正确操作。因此选B。2八进制数12345670和07654321的和为D 。A. 22222221 B. 21111111 C. 22111111 D. 22222211分析有些人想到的是把他们都转为十进制计算。这有点复杂其实可以直接用竖式计算逢8进1。竖式过程1234567007654321__________?????211算到这里就可以得出答案了D。3. 阅读下述代码请问修改data的value成员以存储3.14正确的方式是 A。union Data { int num; float value; char symbol; }; union Data data;A. data.value 3.14; B. value.data 3.14; C.>struct Node { int data; Node* next; };现在有一个指向链表头部的指针Node* head。如果想要在链表中插入一个新节点其 成员data的值为42并使新节点成为链表的第一个节点下面哪个操作是正确的A A. Node* newNode new Node; newNode-data 42; newNode-next head; head newNode;B. Node* newNode new Node; head-data 42; newNode-next head; head newNode;C. Node* newNode new Node; newNode-data 42; head-next newNode;D. Node* newNode new Node; newNode-data 42; newNode-next head;分析链表操作题。还是基础数据结构操作不过要记得链表的特点断一个后面全丢了。所以要细心一些。要在链表的头部插入一个新节点并使其成为第一个节点我们需要完成以下三个关键步骤分配内存并创建一个新节点。将新节点的data赋值为 42。将新节点的next指针指向当前的头节点head然后将头指针head更新为指向这个新节点。先分析A。赋值没问题。指针没丢掉。头部修改了。故此选A。5. 根节点的高度为1一棵拥有2023个节点的三叉树高度至少为 C。A. 6 B. 7 C. 8 D. 9分析手模呀。题目已知根节点的高度为1这意味着第 1 层最多有 301301 个节点第 2 层最多有 313313 个节点第 3 层最多有 329329 个节点一直算算到8时抵达上限选C。6. 小明在某一天中依次有七个空闲时间段他想要选出至少一个空闲时间段来练习唱歌但 他希望任意两个练习的时间段之间都有至少两个空闲的时间段让他休息。则小明一共有 B 种选择时间段的方案。A. 31 B. 18 C. 21 D. 33分析这题是经典排列组合题。由于范围很小7所以可以直接硬算。1. 选 1 个时间段随便选哪个都行。方案数 72. 选 2 个时间段如果第1个选1第2个可以选 4, 5, 6, 7 4种如果第1个选2第2个可以选 5, 6, 7 3种如果第1个选3第2个可以选 6, 7 2种如果第1个选4第2个可以选 7 1种如果第1个选 5, 6, 7后面不够放第2个了。方案数 4 3 2 1 103. 选 3 个时间段实际上只有一种方案。所以选择B(107118)。7. 以下关于高精度运算的说法错误的是 C。A. 高精度计算主要是用来处理大整数或需要保留多位小数的运算。B. 大整数除以小整数的处理的步骤可以是将被除数和除数对齐从左到右逐位尝试将 除数乘以某个数通过减法得到新的被除数并累加商。C. 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关。D. 高精度加法运算的关键在于逐位相加并处理进位。分析咋一看都对实际上仔细一点可以发现C有点问题。比如372* 23———和1000* 1———我们自己算一下发现第一个更慢一些。但第二个最大的位数比第一个大。这是常识问题很明显C是答案。8. 后缀表达式“6 2 3 - 3 8 2 / * 2 ^ 3 ”对应的中缀表达式是 AA. ((6- (2 3)) * (3 8 / 2)) ^ 2 3B. 6- 2 3 * 3 8 / 2 ^ 2 3C. (6- (2 3)) * ((3 8 / 2) ^ 2) 3D. 6- ((2 3) * (3 8 / 2)) ^ 2 3分析这是前中后缀表达式问题。中缀表达式就是实际算式。把每一个符号往前移。1先把往前找第一个空得出(23)。2把-往前移得出6-拼接起来就是6-(23)。3把/往前移得出8/2。4把往前移得出(38/2)。5把*往前移把两个前面算好的表达式拼接得出((6- (2 3)) * (3 8 / 2))。6把^往前移得出((6- (2 3)) * (3 8 / 2)) ^ 2。此时已经得出结论选择A。9. 数1010102进制和1668进制的和为 D。A. 10110000base-2B. 236base-8C. 158base-10D. A0base-16分析基础进制转换问题问题101010和166相加得到16010进制。A不对。B算出结果158排除。C看一眼排除。只剩D了。10.假设有一组字符{a,b,c,d,e,f}对应的频率分别为5%、9%、12%、13%、16%、45%。请 问以下哪个选项是字符a,b,c,d,e,f分别对应的一组哈夫曼编码A A. 1111, 1110, 101, 100, 110, 0B. 1010, 1001, 1000, 011, 010, 00C. 000, 001, 010, 011, 10, 11D. 1010, 1011, 110, 111, 00, 01分析哈夫曼树作图题。把每一个频率最小的相加成为新值再一个一个网上组成树只剩一个时停下。算了一下过程规则一个值到根的长度就是它的编码的长度。f对应的45%到根的距离是1。所以长度为1只有A的0符合标准。选A。11.给定一棵二叉树其前序遍历结果为ABDECFG中序遍历结果为DEBACFG。请问这棵 树的正确后序遍历结果是什么AA. EDBGFCAB. EDBGCFAC. DEBGFCAD. DBEGFCA分析前中后序遍历问题。前序根左右中序左根右后序左右根根据规则得出树的根是ABDE为右侧CFG为左侧。左子树的中序遍历为D E B对应的前序遍历为B D E前序的第一个字母B是左子树的根节点。在中序D E B中B的左边是D E右边为空。说明B只有左子树没有右子树。继续看B的左子树中序D E前序D E根节点是D。在中序D E中D的右边是E说明D只有右子树E。右子树的中序遍历为C F G对应的前序遍历为C F G前序的第一个字母C是右子树的根节点。在中序C F G中C的左边为空右边是F G。说明C只有右子树没有左子树。继续看C的右子树中序F G前序F G根节点是F。在中序F G中F的右边是G说明F只有右子树G。然后继续推导。所以A/ \B C/ \D F/ \E G后序遍历的顺序是左子树 - 右子树 - 根节点。左子树B-D-E的后序先左后右再根即E - D - B右子树C-F-G的后序先左后右再根即G - F - C最后访问根节点A将它们拼接起来最终的后序遍历结果为E D B G F C A。OK选择A。12.考虑一个有向无环图该图包含4条有向边(1,2), (1,3), (2,4)和(3,4)。以下哪 选项是这个有向无环图的一个有效的拓扑排序 BA. 4, 2, 3, 1B. 1, 2, 3, 4C. 1, 2, 4, 3D. 2, 1, 3, 4分析拓扑排序题。会规则就简单。每次取入度为0的点重复。先1然后取2或3最后4。所以只能是1234或 1324只有B符合。13.在计算机中以下哪个选项描述的数据存储容量最小BA.字节byte B.比特bit C.字word D.千字节kilobyte分析这题拉完了。常识没办法解释。知道bit最小即可。14.一个班级有10个男生和12个女生。如果要选出一个3人的小组并且小组中必须至少包 含1个女生那么有多少种可能的组合AA.1420B.1770C.1540D.2200分析组合题。用逆向思维。第一步计算从全班任意选出3人的总组合数班级总人数 10男生 12女生 22人。从22人中任选3人的组合数为C(22,3)22×21×203×2×11540C(22,3)3×2×122×21×20​1540 种。第二步计算不满足条件的组合数就是全是男生的组合题目要求“至少包含1个女生”那么它的反面就是“一个女生都没有全是男生”。从10个男生中任选3人的组合数为C(10,3)10×9×83×2×1120C(10,3)3×2×110×9×8​120 种。第三步相减得出最终结果至少包含1个女生的组合数 总组合数 - 全是男生的组合数1540−12014201540−1201420 种。因此可能的组合共有1420种。15.以下哪个不是操作系统DA.Linux B.Windows C.Android D.HTML分析这题要是不会真没办法了。HTML是编程语言。选D。二、阅读程序程序输入不超过数组或字符串定义的范围判断题正确填√错误填×除特 殊说明外判断题1.5分选择题3分共计40分1#include iostream #include cmath using namespace std; double f(double a,double b, double c) { double s (a b c) / 2; return sqrt(s * (s-a) * (s-b) * (s-c)); } int main() { cout.flags(ios::fixed); cout.precision(4); int a, b, c; cin a b c; cout f(a, b, c) endl; return 0; }分析看一眼代码发现其核心行为是输入三个数并且使用海伦公式来得出解。16.2分当输入为“2 2 2”时输出为“1.7321”。T当然对算一下得出结论。17.2分将第7行中的“(s-b) * (s-c)”改为“(s-c) * (s-b)”不会影响 程序运行的结果。T乘法交换律18.2分程序总是输出四位小数。T这就要看基本功了前面那个对cout的操作就是设置4位输出19.当输入为“3 4 5”时输出为A。A. “6.0000” B. “12.0000” C. “24.0000” D. “30.0000”一道计算题这里就不写怎么算得了。20.当输入为“5 12 13”时输出为B。 A. “24.0000” B. “30.0000” C. “60.0000” D. “120.0000”一道计算题。。。2#include iostream #include vector #include algorithm using namespace std; int f(string x, stringy) { int m x.size(); int n y.size(); vectorvectorintv(m1, vectorint(n1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (x[i-1] y[j-1]){ v[i][j] v[i-1][j-1] 1; } else { v[i][j] max(v[i-1][j],v[i][j-1]); } } } return v[m][n]; } bool g(string x, string y) { if (x.size() ! y.size()) { return false; } return f(x x, y) y.size();; } int main() { string x, y; cin x y; cout g(x, y) endl; return 0; }分析这段代码的核心行为是判断y是否为x的最长公共子串。根据图中数据得出结论分析出g的功能是判断x与y是否等长不等则判断y是否为x的最长公共子串。f函数则是通过dp实现最长公共子序列算法计算字符串x和y的最长公共子序列的长度。接下来看题目21.f 函数的返回值小于等于min(n,m)。T f函数计算的是字符串x和y的最长公共子序列的长度。子序列是从原字符串中删除一些字符也可以不删除后得到的序列因此它的长度不可能超过原字符串中较短的那个的长度。所以他的长度必然小于等于min(m, n)。该说法正确。22.f 函数的返回值等于两个输入字符串的最长公共子串的长度。F f返回的是子序列不是字串。23.当输入两个完全相同的字符串时g函数的返回值总是true。 T当x和y完全相同时y一定是xx的子串因此它们的最长公共子序列长度等于y的长度f(xx, y) y.size()成立返回true。24.将第19行中的“v[m][n]”替换为“v[n][m]”那么该程序 D。A. 行为不变 B. 只会改变输出 C. 一定非正常退出 D. 可能非正常退出有可能侥幸没超出边界因此不一定100% RE。25.当输入为“csp-j p-jcs”时输出为B 。A. “0” B. “1” C. “T” D.“F”不可能打印一个字符串排除后两个。p-jcs确实是csp-jcsp-j的子串选B。26.当输入为“csppsc spsccp”时输出为D 。A. “T” B. “F” C.0 D.1spsccp是csppscssppsc的子串。选D。3#include iostream #include cmath using namespace std; int solve1(int n) { return n * n; } int solve2(int n) { int sum 0; for (int i 1; i sqrt(n); i) { if (n % i 0) { if (n/i i) { sum i*i; } else { sum i*i (n/i)*(n/i); } } } return sum; } int main() { int n; cin n; cout solve2(solve1(n)) solve1(solve2(n)) endl; return 0; }分析solve1返回其平方solve2通过一个函数确定其所有因子的平方和。27.如果输入的n为正整数solve2函数的作用是计算n所有的因子的平方和。T阅读代码发现其逻辑确实是这样。28.第13-14行的作用是避免n的平方根因子i或n/i进入第16行而被计算两次。T是的这样可以避免else用来防止多计算。29.如果输入的n为质数solve2(n)的返回值为n*n1。T当输入的n为质数时质数的正因子只有两个1和n本身。当i 1时n%10成立。因为n是质数n1所以n/1!1。进入else分支sum 1*1 (n/1)*(n/1)即sum 1 n*n。当i从2遍历到sqrt(n)时因为n是质数没有其他因子所以n % i ! 0不会执行任何加操作。故答案选择T。30.如果输入的n为质数p的平方那么solve2(n)的返回值为D题目已知输入的n为质数p的平方即n p^2。我们来找出n p^2的所有正因子因为p是质数所以p^2的正因子只有三个1、p和p^2。循环条件为i sqrt(n)即i sqrt(p^2)也就是i p。然后通过模拟循环得出结论选择D。31.当输入为正整数时第一项减去第二项的差值一定D。A.大于0 B.大于等于0且不一定大于0 C.小于0 D.小于等于0且不一定小于0前两个分析发现不会是正数。第一项等于n^2的所有正因子的平方和。因此第二项等于n的所有正因子的平方和 的平方。因为n是正整数它至少有一个因子1所以因子平方和S 1^2 1。对于任何大于等于 1 的实数S都有S^2 S。这说明第二项 第一项。差值 第一项 - 第二项。因为 第一项 第二项所以 差值 0。因此选D。32.当输入为“5”时输出为C。A. “651 625” B. “650 729” C. “651 676” D. “652 625”直接计算得出结论。三、完善程序单选题每小题 3 分共计30分 1寻找被移除的元素问题原有长度为n1、公差为1的等差升序数列将数列输入 到程序的数组时移除了一个元素导致长度为n的升序数组可能不再连续除非被移除的是第 一个或最后一个元素。需要在数组不连续时找出被移除的元素。 试补全程序。#include iostream #include vector using namespace std; int find_missing(vectorint nums) { int left 0, right nums.size()- 1; while (left right) { int mid left (right- left) / 2; if (nums[mid] mid ①) { ②; } else { ③; } } return ④; } int main() { int n; cin n; vectorint nums(n); for (int i 0; i n; i) cin nums[i]; int missing_number find_missing(nums); if (missing_number ⑤) { cout Sequence is consecutive endl; } else { cout Missing number is missing_number endl; } return 0; }分析经典二分题。33.①处应填A A. 1 B. nums[0] C. right D.leftmid是中点nums[mid]就是nums的mid位置这两个比较。如果缺失了一个数字那么在缺失数字之后的所有元素其值都会比它的索引大1。所以要加1。34.②处应填AA. left mid 1 B. right mid-1 C. right mid D. left mid扩大二分边界直接选择A。35.③处应填CA. left mid 1 B. right mid-1 C. right mid D. left mid缩小二分边界直接选择C。36.④处应填AA. left nums[0] B. right nums[0] C. mid nums[0] D. right 1left是边界答案因此选择AB理论上也可以但是有可能出现误差。37.⑤处应填BA. nums[0]n B. nums[0]n-1 C. nums[0]n1 D. nums[n-1]A. nums[0]n这是数组连续时下一个应该出现的数字。B. nums[0]n-1这是数组连续时最后一个元素的值也就是nums[n-1]。C. nums[0]n1这是数组连续时下下一个应该出现的数字。D. nums[n-1]这是数组连续时最后一个元素的值。故此选择B。2编辑距离给定两个字符串每次操作可以选择删除Delete、插入Insert、替换Replace 一个字符求将第一个字符串转换为第二个字符串所需要的最少操作次数。 试补全动态规划算法。#include iostream #include string #include vector using namespace std; int min(int x, inty, int z) { return min(min(x, y),z); } int edit_dist_dp(string str1, string str2) { int m str1.length(); int n str2.length(); vectorvectorintdp(m 1, vectorint(n 1)); for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0) dp[i][j] ①; else if (j 0) dp[i][j] ②; else if (③) dp[i][j] ④; else dp[i][j] 1 min(dp[i][j-1], dp[i-1][j],⑤); } } return dp[m][n]; } int main() { string str1, str2; cin str1 str2; cout Minimum numberof operations: edit_dist_dp(str1,str2) endl; return 0; }分析min被修改为判断3个数的最小值而edit_dist_dp是dp核心。根据题意分析dp[i][j]为把字符串str1的前i个字符变成字符串str2的前j个字符所需要的最少操作次数。38.①处应填AA. j B. i C. m D. n我们的代码执行到i0才会出现这个情况。代表我们要把str1的前0个字符串空串变为str2的前j个字符串所需要的操作次数。因为空所以要加上j次。39.②处应填BA. j B. i C. m D. nj0的特殊情况。代表我们要把str1的前i个字符串变为str2的前0个字符串所需要的操作次数。减少i次因此是i。40.③处应填AA. str1[i-1] str2[j-1]B. str1[i] str2[j]C. str1[i-1] ! str2[j-1]D. str1[i] ! str2[j]这次要求我们找特殊情况。而且它没有给出后面的修改。我们看看后面和前面全是修改有没有可能当前因为相同不用修改所以我们选则A相同的情况。41.④处应填BA. dp[i-1][j-1] 1 B. dp[i-1][j-1] C. dp[i-1][j] D. dp[i][j-1]前面我们得知这是相同情况。代表我们要把str1的前i个字符串变为str2的前j个字符串所需要的操作次数。我们不需要修改增加A是错的。dp[i-1][j-1]代表我们要把str1的前i-1个字符串变为str2的前j-1个字符串所需要的操作次数。这就是直接不修改了。选择B。42.⑤处应填CA. dp[i][j] 1 B. dp[i-1][j-1] 1 C. dp[i-1][j-1] D. dp[i][j]最后就是i和j都正常的一般情况了。前面dp[i-1][j]dp[i][j-1]。不就是求删除Delete、插入Insert、替换Replace的最小值吗所以我们选择C凑齐3种情况。完成。