【C++笔试强训】第二十三天 本是古典 何须时尚 2024-04-20 06:26 81阅读 0赞 > **?C++笔试强训** > > -------------------- > > * **博客主页:**[一起去看日落吗][Link 1] > * **分享博主的C++刷题日常,大家一起学习** > * **`博主的能力有限,出现错误希望大家不吝赐教`** > * **分享给大家一句我很喜欢的话:夜色难免微凉,前方必有曙光** ?。 > > -------------------- > > ![在这里插入图片描述][047d8ad26e314dc7bc7aa19a6ce9ccb0.jpeg_pic_center] ?? -------------------- ## 选择题 ## ### ? 第一题 ### 下面程序段的时间复杂度为() for (int i=0;i<m;i++) for (int j=0;j<n;j++) a[i][j]=i*j; ![请添加图片描述][f02a221249c24de6a8af2214ae406091.png] 这里一看到循环套循环,这一眼就知道是m\*n的,看次数 > **`这道题的答案是C`** -------------------- ### ? 第二题 ### 下列关于线性链表的叙述中,正确的是( ) A 各数据结点的存储空间可以不连续,但它们的存储顺序与逻辑顺序必须一致 B 各数据结点的存储顺序与逻辑顺序可以不一致,但它们的存储空间必须连续 C 进行插入与删除时,不需要移动表中的元素 D 以上说法均不正确 A 存储空间可以不连续,它存储顺序与逻辑顺序就没有必要一致,逻辑顺序是123,而存储的物理顺序可以是213 B 如果储存空间连续这就不是链表了 C 进行插入与删除时,不需要移动表中的元素,只需要改变指针 > **`这道题的答案是C`** -------------------- ### ? 第三题 ### 下列描述的不是链表的优点是( ) A 逻辑上相邻的结点物理上不必邻接 B 插进、删除运算操纵方便,不必移动结点 C 所需存储空间比线性表节省 D 无需事先估计存储空间的大小 A逻辑上相邻的结点物理上不必邻接,这是一大特点 B插进、删除运算操纵方便,不必移动结点,这是链表最大的优点 D无需事先估计存储空间的大小,我们都是动态申请的 C 如果存储123,如果是顺序表只需要3个,而链表则需要多申请指针维护数据 > **`这道题的答案是C`** -------------------- ### ? 第四题 ### 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执行() A h->next=s; B s->next=h; C s->next=h;h->next=s; D s->next=h->next;h->next=s; ![请添加图片描述][01f5309b06164e5e9c16261443d2c127.png] 把图画出来答案就清晰明了了 > **`这道题的答案是D`** -------------------- ### ? 第五题 ### 队列\{a,b,c,d,e\}依次入队,允许在其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的出队序列是() A b, a, c, d, e B d, b, a, c, e C d, b, c, a, e D e, c, b, a, d 注意:允许在其两端进行入队操作,但仅允许在一端进行出队操作 画个图就可以知道结果了,每个结果都尝试一下 > **`这道题的答案是C`** -------------------- ### ? 第六题 ### 若一棵二叉树具有12个度为2的结点,6个度为1的结点,则度为0的结点个数是() A 10 B 11 C 13 D 不确定 n0 = n2 + 1 ;这是二叉树的一个性质 > **`这道题的答案是C`** -------------------- ### ? 第七题 ### 下列各树形结构中,哪些是平衡二叉查找树: ![请添加图片描述][2ebed5b3e6d444308f3c739bfbe76825.png] 平衡二叉树的两个前提,一,他是一棵二叉搜索树,二,平衡因子绝对值不能超过一 A 不是二叉搜索树 B 平衡因子不满足 C 是AVL树 D 不是二叉搜索树 > **`这道题的答案是C`** -------------------- ### ? 第八题 ### 已知关键字序列5,8,12,19,28,20,15,22是最小堆,插入关键字3,调整后得到的最小堆是() A 3,8,12,5,20,15,22,28,19 B 3,5,12,19,20,15,22,8,28 C 3,12,5,8,28,20,15,22,19 D 3,5,12,8,28,20,15,22,19 ![请添加图片描述][1f97e0f6f26c4a4d992b1ba054636d27.png] ![请添加图片描述][7ee75ccb4951469c98c5462608993d0c.png] > **`这道题的答案是D`** -------------------- ### ? 第九题 ### 采用哈希表组织100万条记录,以支持字段A快速查找,则() A 理论上可以在常数时间内找到特定记录 B 所有记录必须存在内存中 C 拉链式哈希曼最坏查找时间复杂度是O(n) D 哈希函数的选择跟A无关 A 不一定,用哈希表组织这么多数据,大概率会出现冲突 B 不一定,数据量太大可能在内存放不下,会采用外部存储 C 最坏的情况是所有数据都要查找一次,所以是On D A如果是整数可以采用其他映射关系,如果是字符串就不能用除留余数法,所以有关系 > **`这道题的答案是C`** -------------------- ### ? 第十题 ### 假设你只有100Mb的内存,需要对1Gb的数据进行排序,最合适的算法是() A 归并排序 B 插入排序 C 快速排序 D 冒泡排序 内存无法装载这么大内存 插入,冒泡,快速都是内部排序,利用归并可以把数据分到不同的文件记录内部数据进行排序 > **`这道题的答案是C`** -------------------- ## 编程题 ## ### ? 第一题 ### 链接:[微信红包][Link 2] ![请添加图片描述][29ed872bfc124100bcfeabf547a638df.png] * 解题思路 本题两种思路,第一种排序思路,如果一个数出现次数超过一半了,排序过后,必然排在中间,则最后遍历整个数组查看是否符合即可。第二种思路可以用map统计每个数字出现的次数,最后判断有没有超过一半的数字。 * 代码演示 class Gift { public: int getValue(vector<int> gifts, int n) { // write code here //方法一:map统计 // map<int,int> count; // int mid = gifts.size()/2; // for(auto &e : gifts) // { // count[e]++; // } // for(auto &e : count) // { // if(e.second >= mid) // return e.first; // } // return 0; //方法二:不停统计求次数 sort(gifts.begin(),gifts.end()); int mid = gifts[n/2]; int count = 0; for(auto &e : gifts) { if(e == mid) count++; } if(count > n/2) return mid; return 0; } }; -------------------- ### ? 第二题 ### 链接:[计算字符串的编辑距离][Link 3] ![请添加图片描述][cc067d7448054b66b952a5142c76b263.png] * 解题思路 本题需要用动态规划解题 状态: 子状态:word1的前1,2,3,…m个字符转换成word2的前1,2,3,…n个字符需要的编辑距离 F(i,j):word1的前i个字符于word2的前j个字符的编辑距离 状态递推: F(i,j) = min \{ F(i-1,j)+1, F(i,j-1) +1, F(i-1,j-1) +(w1\[i\]==w2\[j\]?0:1) \} 上式表示从删除,增加和替换操作中选择一个最小操作数 F(i-1,j): w1\[1,…,i-1\]于w2\[1,…,j\]的编辑距离,删除w1\[i\]的字符—>F(i,j) F(i,j-1): w1\[1,…,i\]于w2\[1,…,j-1\]的编辑距离,增加一个字符—>F(i,j) F(i-1,j-1): w1\[1,…,i-1\]于w2\[1,…,j-1\]的编辑距离,如果w1\[i\]与w2\[j\]相同, 不做任何操作,编辑距离不变,如果w1\[i\]与w2\[j\]不同,替换w1\[i\]的字符为w2\[j\]—>F(i,j) 初始化: 初始化一定要是确定的值,如果这里不加入空串,初始值无法确定 F(i,0) = i :word与空串的编辑距离,删除操作 F(0,i) = i :空串与word的编辑距离,增加操作 返回结果:F(m,n) * 代码演示 #include <iostream> #include <vector> #include <string> using namespace std; int minDistance(const string &s1,const string &s2) { if(s1.empty() || s2.empty()) return max(s1.size(),s2.size()); int len1 = s1.size(); int len2 = s2.size(); vector<vector<int >> f(len1+1,vector<int>(len2+1,0)); //初始化距离 for(int i = 0;i <= len1;i++) f[i][0] = i; for(int j = 0;j <= len2;++j) f[0][j] = j; for(int i = 1;i <= len1;++i) { for(int j = 1;j <= len2 ;++j) { if(s2[j-1] == s1[i-1]) { f[i][j] = min(f[i-1][j],f[i][j-1]) + 1; //由于字符相同,距离不发生变化 f[i][j] = min(f[i-1][j-1],f[i][j]); } else { f[i][j] = min(f[i-1][j],f[i][j-1]) + 1; //由于字符不相同,距离+1 f[i][j] = min(f[i-1][j-1]+1,f[i][j]); } } } return f[len1][len2]; } int main() { string s1,s2; while(cin >> s1 >> s2) { cout << minDistance(s1,s2) << 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/536bff0aee0d4664820b65308be07ef9.jpeg [f02a221249c24de6a8af2214ae406091.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/86c32c1b17b148c89e4857d113c02e35.png [01f5309b06164e5e9c16261443d2c127.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/174b4d9d06ce486ab347d0b8acfc9923.png [2ebed5b3e6d444308f3c739bfbe76825.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/39e7b36daa5d46ef87b944b8a4b991d9.png [1f97e0f6f26c4a4d992b1ba054636d27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/0f2f0455b11a4d81a702da8ccf06ef24.png [7ee75ccb4951469c98c5462608993d0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c1328a4379b94e5ea0673c4130060250.png [Link 2]: https://www.nowcoder.com/practice/fbcf95ed620f42a88be24eb2cd57ec54?tpId=49&&tqId=29311&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking [29ed872bfc124100bcfeabf547a638df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c1ffa38d1b2742ec8c80777daa7cfe04.png [Link 3]: https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&&tqId=21275&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking [cc067d7448054b66b952a5142c76b263.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/e13bef45b64b41cdb96ff5858c8b3db8.png
还没有评论,来说两句吧...