【C++笔试强训】第二十三天 本是古典 何须时尚 2024-04-20 06:26 62阅读 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
今天药忘吃喽~
骑猪看日落
梦里梦外;
迷南。
「爱情、让人受尽委屈。」
Bertha 。
超、凢脫俗
还没有评论，来说两句吧...