【C++笔试强训】第二十天 超、凢脫俗 2024-04-20 06:24 83阅读 0赞 > **?C++笔试强训** > > -------------------- > > * **博客主页：**[一起去看日落吗][Link 1] > * **分享博主的C++刷题日常，大家一起学习** > * **`博主的能力有限，出现错误希望大家不吝赐教`** > * **分享给大家一句我很喜欢的话：夜色难免微凉，前方必有曙光** ?。 > > -------------------- > > ![在这里插入图片描述][047d8ad26e314dc7bc7aa19a6ce9ccb0.jpeg_pic_center] ?? -------------------- ## 选择题 ## ### ?第一题 ### 对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（）。 A O(n) O(n) B O(n) O(1) C O(1) O(n) D O(1) O(1) 线性表可以直接通过下标访问，和元素的多少没有关系，所以访问时间复杂度为O1 增加结点需要看节点个数，所以是On > **`这道题的答案是C`** -------------------- ### ?第二题 ### 在下列链表中不能从当前结点出发访问到其余各结点的是（） A 双向链表 B 单循环链表 C 单链表 D 双向循环链表 单链表只可以往后走，如果指针从中间开始，则不能访问前面的节点 ![请添加图片描述][ae6e9ff3e87e4cc7a6dad766e65f8a52.png] > **`这道题的答案是C`** -------------------- ### ?第三题 ### 完成在双向循环链表结点 p 之后插入 s 的操作是（） A p->next=s;s->prior=p;p->next->prior=s;s->next=p->next B p->next->prior=s;p->next=s;s->prior=p;s->next=p->next C s->prior=p;s->next=p->next;p->next=s;p->next->prior=s D s->prior=p;s->next=p->next;p->next->prior=s;p->next=s 数据结构画图是关键 修改指针的时候，需要先把插入节点的前后连起来 每个人的插入顺序可能不一样，所以我们可以根据选项看题目 ![请添加图片描述][92816c92da7f468aa6d2b568d2d89926.png] > **`这道题的答案是D`** -------------------- ### ?第四题 ### 栈是一种智能在某一端插入和删除的特殊线性表，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，若6元素为A、B、C、D、E、F出栈顺序为B、D、C、F、E、A，则S栈的最小容量为（）。 A 3 B 4 C 5 D 6 这种题目也是画出图就可以知道结果了 ![请添加图片描述][bb7a39c8d36d4fb39665b2501ab68cb9.png] > **`这道题的答案是A`** -------------------- ### ?第五题 ### 现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为（）(假设队头不存放数据) A (rear - front + N) % N + 1 B (rear - front + N) % N C (rear - front) % (N + 1) D (rear - front + N) % (N - 1) 队头不存放数据代表多一个空间不使用，数据结构一定要多画图，假设有8个空间，最多可以存储7个数据，举例子按公式算就可以了，并不需要过多思考，找反例就可以 ![请添加图片描述][f11871ac7d6b4402abc5c75580652b3d.png] > **`这道题的答案是B`** -------------------- ### ?第六题 ### 下述结论中,正确的是()①只有一个结点的二叉树的度为0;②二叉树的度为2;③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树 A ①②③ B ②③④ C ②④ D ①④ 二叉树的度是所有节点中度最大的一个，只有一个节点所以度为0，所以1⃣️正确，二叉树的度可以是0 1 2 ，所以2⃣️错误，二叉树如果摆法不相同，是有序数，则两棵树不同，所以3⃣️错，完全二叉树本身是按照满二叉树的方式建立的，所以4⃣️正确 > **`这道题的答案是D`** -------------------- ### ?第七题 ### 若将关键字1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是（ ） A 0 B 1 C 2 D 3 只要把图画出来，所有的数据结构问题都可以迎刃而解 ![请添加图片描述][959202329b934c30a199125de4480171.png] > **`这道题的答案是D`** -------------------- ### ?第八题 ### 初始序列为1 8 6 2 5 4 7 3一组数采用堆排序，当建堆（小根堆）完毕时，堆所对应的二叉树中序遍历序列为（） A 8 3 2 5 1 6 4 7 B 3 2 8 5 1 4 6 7 C 3 8 2 5 1 6 7 4 D 8 2 3 5 1 4 7 6 这道题是考察建堆![请添加图片描述][4e86ac67650f4015bf77fdd0ae5c2dcd.png] > **`这道题的答案是A`** -------------------- ### ?第九题 ### 解决散列法中出现冲突问题常采用的方法是（） A 数字分析法、除余法、平方取中法 B 数字分析法、除余法、线性探测法 C 数字分析法、线性探测法、多重散列法 D 线性探测法、多重散列法、链地址法 数字分析的不是常用的方法，除余法不是解决冲突，是映射发生 线性探测法、多重散列法、链地址法才是常用的方法 > **`这道题的答案是D`** -------------------- ### ?第十题 ### 下列选项中，不可能是快速排序第2趟排序结果的是 （） A 2,3,5,4,6,7,9 B 2,7,5,6,4,3,9 C 3,2,5,4,7,6,9 D 4,2,3,5,7,6,9 快速排序是找到一个关键值，然后左边小于他，右边大于他，然后继续递归排序 所以C是不可以的 ![请添加图片描述][0ffc1f6b18e345faae122c5a4ffc97f3.png] > **`这道题的答案是C`** -------------------- ## 编程题 ## ### ?第一题 ### 链接：[字符串反转][Link 2] ![请添加图片描述][85aa79af104042c79f84c84e30bf9108.png] * 解题思路 字符串反转，需要交换首尾字符，设置首尾两个位置start，end，每次交换首尾字符，然后start++, end–，直到start，end相遇，反转完成。 或者直接调用库函数里面的交换 * 代码也是 #include <iostream> #include <string> #include <algorithm> using namespace std; //方法一 void strReverse_1(string &s) { int start = 0; int end = s.size() - 1; while(start < end) { char tmp = s[start]; s[start] = s[end]; s[end] = tmp; start++; end--; } } //方法二 void strReverse_2(string &s) { reverse(s.begin(),s.end()); } int main() { string s; while(cin >> s) { //strReverse_1(s); strReverse_2(s); cout << s << endl; } return 0; } -------------------- ### ?第二题 ### 链接：[公共子串计算][Link 3] ![请添加图片描述][bc5e4b9dbfac4ae6bbe3657cb88a0e46.png] * 解题思路 求最大公共子串，使用递推实现 假设 x(i): 字符串第i个字符 y(j): 字符串第j个字符 dp\[i\]\[j\]: 以x(i),y(j)结尾的最大子串长度 比如：x: “abcde” y:“bcdae” dp\[2\]\[1\]: 以x(2),y(1)结尾的最大子串长度 即：x遍历到"abc", y遍历到"bc", 都以字符’c’结尾时最大公共子串为"bc" 故：当计算dp\[i\]\[j\]时，首先看x(i),y(j)的值： （1）: x(i) == y(j) 当前两个字符串结尾的字符相等，dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + 1 即个它的长度加1 （2）: x(i) != y(j) 当前两个字符串结尾的字符不相等，说明没有以这连个字符结尾的公共子串 即dp\[i\]\[j\] = 0 （3）: dp\[0\]\[j\] 和 dp\[i\]\[0\]表示以某个子串的第一个字符结尾，最大长度为1 如果x(0) = = y(j) 或者 x(i) == y(0), 则长度为1，否则为0 当dp中的 所有元素计算完之后，从中找打最大的值输出 * 代码演示： #include <iostream> #include <string> #include <vector> using namespace std; int getMax(const string &s1,const string &s2) { int len1 = s1.size(); int len2 = s2.size(); vector<vector<int>> msc(len1,vector<int>(len2,0)); int max_len = 0; for(int i = 0;i < len1;i++) { for(int j = 0;j < len2;++j) { if(s2[j] == s1[i]) { if(i >= 1 && j >= 1) msc[i][j] = msc[i-1][j-1] + 1; else msc[i][j] = 1; if(msc[i][j] > max_len) max_len = msc[i][j]; } } } return max_len; } int main() { string s1,s2; while(cin >> s1 >> s2) { int max_len = getMax(s1,s2); cout << max_len << 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/1df74580726a414fbaf3ee13eecac670.jpeg [ae6e9ff3e87e4cc7a6dad766e65f8a52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0175afb46628480aae867f65f8104a87.png [92816c92da7f468aa6d2b568d2d89926.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/9d18d7f2076b400ba06f4103b3176ff5.png [bb7a39c8d36d4fb39665b2501ab68cb9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0a2d7fa703c046218ca4c6f36a89abc2.png [f11871ac7d6b4402abc5c75580652b3d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/f9868c0f7f23462ebfe107e76d330624.png [959202329b934c30a199125de4480171.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5cd75b141d4b48ca8924f24735652105.png [4e86ac67650f4015bf77fdd0ae5c2dcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/485bf3e1a78c4d6db388e47f49cd6284.png [0ffc1f6b18e345faae122c5a4ffc97f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/318f0f22ec774ad08450db40cd9a55ac.png [Link 2]: https://www.nowcoder.com/practice/e45e078701ab4e4cb49393ae30f1bb04?tpId=37&&tqId=21235&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking [85aa79af104042c79f84c84e30bf9108.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/7b73654c22134973bb36009104f216f1.png [Link 3]: https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b?tpId=37&&tqId=21298&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking [bc5e4b9dbfac4ae6bbe3657cb88a0e46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/80b68b230c284286999b53fbcc02bf0d.png
今天药忘吃喽~
骑猪看日落
梦里梦外;
迷南。
「爱情、让人受尽委屈。」
Bertha 。
超、凢脫俗
还没有评论，来说两句吧...