【C++笔试强训】第二十四天 「爱情、让人受尽委屈。」 2024-04-20 06:26 95阅读 0赞 > **?C++笔试强训** > > -------------------- > > * **博客主页：**[一起去看日落吗][Link 1] > * **分享博主的C++刷题日常，大家一起学习** > * **`博主的能力有限，出现错误希望大家不吝赐教`** > * **分享给大家一句我很喜欢的话：夜色难免微凉，前方必有曙光** ?。 > > -------------------- > > ![在这里插入图片描述][047d8ad26e314dc7bc7aa19a6ce9ccb0.jpeg_pic_center] ?? -------------------- ## 选择题 ## ### ?第一题 ### 请指出选择排序，冒泡排序，快速排序的时间复杂度分别是（） A O(n2)、O(n2)、O(n*log2n) B O(n*log2n)、、O(n^2)、O(n*log2n） C O(n)、O(n2)、O(n2) D O(n*log2n)、O(n2)、O(n2) 先进排序都是对数阶，一般排序方法都是n方 ![在这里插入图片描述][2dc53230eebf4d92bf5ca92e9123c15d.png] > **`这道题的答案是A`** -------------------- ### ?第二题 ### 在单链表中，增加头结点的目的是（） A 标识表结点中首结点的位置 B 算法实现上的方便 C 使单链表至少有一个结点 D 说明单链表是线性表的链式存储实现 增加头节点代码会简单些，做其他节点的插入删除两个没区别，如果是第一个节点，不带头节点需要特殊处理 ![请添加图片描述][d85f4d32ecde4fcfa26821a225191447.png] > **`这道题的答案是B`** -------------------- ### ?第三题 ### 下列算法的功能是什么？ /*L是无头节点单链表*/ LinkList Demo(LinkList L){ ListNode *Q,*P; if(L&&L->next){ Q=L; L=L->next; P=L; while(P->next) P=P->next; p->next=Q; } return L; } 根据代码的操作画图，得出结论是让链表变得循环了![请添加图片描述][ea692181ecf543399bcf692ae035b0f6.png] ![请添加图片描述][3e92b71df3d3474eaa96ed1e09a0ec41.png] A 遍历链表 B 链表深拷贝 C 链表反转 D 单链表转变为循环链表 > **`这道题的答案是D`** -------------------- ### ?第四题 ### 表达式3*2^(4+2*2-6\*3)-5求值过程中当扫描到6时,对象栈和运算符栈为(),其中 ^ 为乘幂 A 3,2,4,1,1;( \* ^(+ \* - B 3,2,8;( \* ^ - C 3,2,4,2,2; ( \* ^(- D 3,2,8;\*^(- ![在这里插入图片描述][98721f3037194072ad169f3784b86f4b.png_pic_center] ![请添加图片描述][de61402626e24d5c9ff17e506cd15cf1.png] > **`这道题的答案是D`** -------------------- ### ?第五题 ### 假设以数组A\[60\]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为() A 3 B 37 C 97 D 50 这道题很简单，当前是47，存50个元素，就是47+50-60 = 37 > **`这道题的答案是B`** -------------------- ### ?第六题 ### 一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最多有（） A 112 B 111 C 107 D 109 第六层有九个结点，七层满二叉树的结点个数 2 ^ 7 - 1 = 128 则这棵树的结点 128 - 9 \* 2 = 109 这道题主要考察二叉树的性质 > **`这道题的答案是D`** -------------------- ### ?第七题 ### 有权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（） A 24 B 71 C 48 D 53 ![请添加图片描述][7dacf41f3b114b6dabb8f32af5e97edb.png] ![请添加图片描述][4dda718fd72a4b298e9c4735a58dfa57.png] > **`这道题的答案是B`** -------------------- ### ?第八题 ### 已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，最后的叶子节点为（） A 34 B 21 C 16 D 12 ![请添加图片描述][9efcbe936ff74064a8df8da8c7c89306.png] > **`这道题的答案是C`** -------------------- ### ?第九题 ### 将10个元素散列到100000个单元的哈希表中,则()产生冲突 A 一定会 B 一定不会 C 仍可能会 空间很多，数据很少，哈希最大的特点是空见少数据多，哈希函数是映射函数，保不准数据很特殊，可能还是会映射同一个地址，只不过是产生冲突的可能性减少了，不能保证一定不会产生冲突 > **`这道题的答案是C`** -------------------- ### ?第十题 ### 下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是 （） 。 A 直接插入排序 B 起泡排序 C 基数排序 D 快速排序 ABD正序和反序都不同，基数排序是不需要移动数据和比较数据的，是所有排序里面唯一的，是通过分发和收集对数据的排序 > **`这道题的答案是C`** -------------------- ## 编程题 ## ### ? 第一题 ### 链接：[年终奖][Link 2] ![在这里插入图片描述][3601440426b145c7b8a52ed2273eb1f2.png_pic_center] * 解题思路 本题需要使用动态规划求解。 定义f(i,j)表示从左上角走到坐标(i，j)处能获得的最大奖励。 搜索所有从左上角走到右下角的路径，找到最优路径。 f(i,j)分三种情况： 第一列：f(i, 0) = f(i-1, 0) + board(i, 0) 第一行：f(0,j) = f(0, j - 1) + b(0, j) 其它位置：f(i, j) = max\{f(i-1, j), f(i, j - 1)\} + board(i, j) 最后返回右下角的值。 * 代码演示 class Bonus { public: int getMost(vector<vector<int> > board) { // write code here int row = board.size(); int col = board[0]. size(); vector<vector<int>> allPrice(row,vector<int> (col,0)); allPrice[0][0] = board[0][0]; for(int i = 0;i < row;++i) { for(int j = 0;j < col;++j) { if(i == 0 && j == 0) continue; if(i == 0)//在第一行，只能往右走 allPrice[i][j] = allPrice[i][j-1] + board[i][j]; else if(j == 0)//在第一列，只能往下走 allPrice[i][j] = allPrice[i-1][j] + board[i][j]; else allPrice[i][j] = max(allPrice[i][j-1],allPrice[i-1][j]) + board[i][j]; } } return allPrice[row-1][col-1]; } }; -------------------- ### ? 第二题 ### 链接：[迷宫问题][Link 3] ![请添加图片描述][1da813d732624909bf573e7cda1d9bca.png] ![请添加图片描述][ca69618325a64b3bb21f0d7f270a8ec9.png] * 解题思路 本题可用回溯法求解 具体步骤为： 1. 首先将当前点加入路径，并设置为已走 2. 判断当前点是否为出口，是则输出路径，保存结果；跳转到4 3. 依次判断当前点的上、下、左、右四个点是否可走，如果可走则递归走该点 4. 当前点推出路径，设置为可走 * 代码演示 #include <iostream> #include <vector> using namespace std; int ROW,COL; vector<vector<int>> maze; vector<vector<int>> path_tmp;//临时路径 vector<vector<int>> path_best;//最佳路径 void MazeTrack(int i ,int j) { maze[i][j] = 1;//代表（i，j）已经走过 path_tmp.push_back({ i,j}); //判断是否到达出口 if(i == ROW - 1 && j == COL - 1) { if(path_best.empty() || path_best.size() > path_tmp.size()) path_best = path_tmp; } //向右走 if(j+1 < COL && maze[i][j+1] == 0) MazeTrack(i, j+1); //向左走 if(j-1 >= 0 && maze[i][j-1] == 0) MazeTrack(i, j-1); //向上走 if(i-1 >= 0 && maze[i-1][j] == 0) MazeTrack(i-1,j); //向下走 if(i+1 < ROW && maze[i+1][j] == 0) MazeTrack(i+1, j); maze[i][j] = 0;//回溯，恢复 path_tmp.pop_back(); } int main() { while(cin >> ROW >> COL) { maze = vector<vector<int>>(ROW,vector<int>(COL,0));//开辟迷宫空间 path_tmp.clear(); path_best.clear(); //输入迷宫 for(int i = 0;i < ROW;++i) { for(int j = 0;j < COL;++j) { cin >> maze[i][j]; } } MazeTrack(0,0);//从（0，0）位置开始走 //输出路径 for(int i = 0;i < path_best.size();++i) { cout << "(" << path_best[i][0] << "," << path_best[i][1] << ")" << endl; } } return 0; } -------------------- [Link 1]: https://blog.csdn.net/m0_60338933?type=blog [047d8ad26e314dc7bc7aa19a6ce9ccb0.jpeg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0fbe5260145b4aa9a0c7072686d43a32.jpeg [2dc53230eebf4d92bf5ca92e9123c15d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/576a00be5be84b60a54e7453a65f44f1.png [d85f4d32ecde4fcfa26821a225191447.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/638a53a89ad144d2994ef7e9366c9d4a.png [ea692181ecf543399bcf692ae035b0f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/4b34ac0a94bd497ea5517bf0bfb7af41.png [3e92b71df3d3474eaa96ed1e09a0ec41.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/a3c4d226ab004530902fc69c5fa40b0a.png [98721f3037194072ad169f3784b86f4b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e57b97060dd74e81b047583f409506f2.png [de61402626e24d5c9ff17e506cd15cf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/72f498a61b4f4111bceb68f02e4f6d9f.png [7dacf41f3b114b6dabb8f32af5e97edb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/8788a5c51a594e1eb15da221305163a1.png [4dda718fd72a4b298e9c4735a58dfa57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5748f868b1984ab995cbc7375b6175c0.png [9efcbe936ff74064a8df8da8c7c89306.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/bfdae96ced524a1a9e3a66cd0d480728.png [Link 2]: https://www.nowcoder.com/practice/72a99e28381a407991f2c96d8cb238ab?tpId=49&&tqId=29305&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking [3601440426b145c7b8a52ed2273eb1f2.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/6c1ad0dab12f439986977b7531c386ec.png [Link 3]: https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&&tqId=21266&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking [1da813d732624909bf573e7cda1d9bca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/49f295981bb440859031faca44c125e3.png [ca69618325a64b3bb21f0d7f270a8ec9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/cbbd7692dc224330be2db39f272d493a.png
今天药忘吃喽~
骑猪看日落
梦里梦外;
迷南。
「爱情、让人受尽委屈。」
Bertha 。
超、凢脫俗
还没有评论，来说两句吧...