北邮计算机研究生入学考试(复试)历年上机测试模拟试题及模拟题及答案

北邮计算机研究生入学考试(复试)历年上机测试模拟试题及模拟题及答案题目一：C++类设计与内存管理（自定义字符串类）【问题描述】请设计一个名为`MyString`的类，该类用于管理动态分配的字符数组，模拟标准库中`std::string`的部分功能。该类必须展示对深拷贝、内存管理以及运算符重载的深刻理解。具体要求如下：1.构造与析构：实现默认构造函数、带`constchar*`参数的构造函数以及拷贝构造函数。确保析构函数正确释放内存。2.赋值运算符：重载赋值运算符`=`，以支持对象间的赋值（需处理自赋值情况并释放旧内存）。3.连接运算符：重载`+`运算符，用于连接两个`MyString`对象，返回一个新的`MyString`对象。4.索引访问：重载`[]`运算符，用于访问和修改字符串中的特定字符（需提供`const`版本和`const`版本）。5.比较功能：重载`==`和`<`运算符，用于比较两个字符串的内容。6.输出功能：重载`<<`输出流运算符，以便直接输出`MyString`对象。7.成员函数：实现`length()`函数返回字符串长度，`c_str()`函数返回内部字符指针。请编写完整的类定义及实现代码，并在`main`函数中编写测试代码验证上述所有功能。【输入格式】无标准输入，需在`main`函数中硬编码测试数据。【输出格式】输出测试代码中的运行结果，包括字符串连接结果、比较结果以及特定索引的字符。【参考代码】```cpp#include<iostream>#include<cstring>usingnamespacestd;classMyString{private:char*m_data;size_tm_len;public://1.默认构造函数MyString():m_data(nullptr),m_len(0){m_data=newchar[1];m_data[0]='\0';}//1.带参构造函数MyString(constchar*str){if(str==nullptr){m_data=newchar[1];m_data[0]='\0';m_len=0;}else{m_len=strlen(str);m_data=newchar[m_len+1];strcpy(m_data,str);}}//1.拷贝构造函数(深拷贝)MyString(constMyString&other){m_len=other.m_len;m_data=newchar[m_len+1];strcpy(m_data,other.m_data);}//1.析构函数~MyString(){delete[]m_data;}//2.赋值运算符重载MyString&operator=(constMyString&other){if(this==&other){//检查自赋值return*this;}delete[]m_data;//释放旧内存m_len=other.m_len;m_data=newchar[m_len+1];strcpy(m_data,other.m_data);return*this;}//3.连接运算符重载MyStringoperator+(constMyString&other)const{MyStringtemp;delete[]temp.m_data;//释放默认分配的内存temp.m_len=m_len+other.m_len;temp.m_data=newchar[temp.m_len+1];strcpy(temp.m_data,m_data);strcat(temp.m_data,other.m_data);returntemp;}//4.索引访问运算符(非const版本)char&operator[](size_tindex){if(index>=m_len){staticchardummy='\0';cerr<<"Indexoutofbounds!"<<endl;returndummy;}returnm_data[index];}//4.索引访问运算符(const版本)constchar&operator[](size_tindex)const{if(index>=m_len){staticchardummy='\0';returndummy;}returnm_data[index];}//5.比较运算符==booloperator==(constMyString&other)const{returnstrcmp(m_data,other.m_data)==0;}//5.比较运算符<booloperator<(constMyString&other)const{returnstrcmp(m_data,other.m_data)<0;}//6.输出流运算符重载(友元函数)friendostream&operator<<(ostream&os,constMyString&str);//7.获取长度size_tlength()const{returnm_len;}//7.获取C字符串constchar*c_str()const{returnm_data;}};ostream&operator<<(ostream&os,constMyString&str){os<<str.m_data;returnos;}intmain(){MyStrings1("Hello");MyStrings2("World");MyStrings3;cout<<"s1:"<<s1<<endl;cout<<"s2:"<<s2<<endl;//测试拷贝构造MyStrings4(s1);cout<<"s4(copyofs1):"<<s4<<endl;//测试赋值s3=s1;cout<<"s3(assignedfroms1):"<<s3<<endl;//测试连接MyStrings5=s1+s2;cout<<"s5(s1+s2):"<<s5<<endl;//测试比较cout<<"s1==s3?"<<(s1==s3?"Yes":"No")<<endl;cout<<"s1<s2?"<<(s1<s2?"Yes":"No")<<endl;//测试索引访问cout<<"s5[0]:"<<s5[0]<<endl;s5[0]='h';cout<<"s5aftermodify:"<<s5<<endl;return0;}```【答案与解析】输出结果：```texts1:Hellos2:Worlds4(copyofs1):Hellos3(assignedfroms1):Hellos5(s1+s2):HelloWorlds1==s3?Yess1<s2?Nos5[0]:Hs5aftermodify:helloWorld```核心考点解析：1.内存管理：本题的核心在于`new`和`delete`的配对使用。在构造函数中分配内存，在析构函数中释放。如果忘记释放，会导致内存泄漏；如果重复释放，会导致程序崩溃。2.深拷贝与浅拷贝：拷贝构造函数和赋值运算符必须执行深拷贝。即重新分配内存并复制内容，而不是仅仅复制指针（浅拷贝）。浅拷贝会导致两个对象指向同一块内存，当其中一个对象析构释放内存后，另一个对象会成为“悬空指针”，再次析构时引发DoubleFree错误。3.自赋值检查：在赋值运算符中，`if(this==&other)`是必不可少的。否则，在执行`delete[]m_data`后，源数据也被销毁了，无法完成后续的拷贝。4.RuleofThree：C++中如果定义了析构函数、拷贝构造函数或拷贝赋值运算符中的一个，通常需要定义这三个。本题完整展示了这一法则。5.运算符重载：`[]`运算符需要提供两个版本，分别用于常量对象（只读）和非常量对象（读写）。`+`运算符通常返回一个新对象，不应修改当前对象本身，因此声明为`const`成员函数。`<<`必须重载为友元函数，因为左操作数是`ostream`对象，而不是`MyString`对象。题目二：链表操作（合并k个有序链表）【问题描述】给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，并将其返回。数据结构定义如下：```cppstructListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};```请实现函数`ListNode*mergeKLists(vector<ListNode*>&lists)`。【输入格式】第一行输入一个整数N，表示链表的数量。接下来N行，每行输入若干整数，表示一个链表中的节点值，以-1结尾。【输出格式】输出合并后的链表节点值，以空格分隔。【参考代码】```cpp#include<iostream>#include<vector>#include<queue>usingnamespacestd;structListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};//比较器，用于优先队列（最小堆）structCompare{booloperator()(constListNode*a,constListNode*b){returna->val>b->val;//最小堆}};classSolution{public:ListNode*mergeKLists(vector<ListNode*>&lists){//优先队列，存储各个链表当前的头节点priority_queue<ListNode*,vector<ListNode*>,Compare>min_heap;//将所有链表的非空头节点加入堆for(ListNode*head:lists){if(head!=nullptr){min_heap.push(head);}}//创建虚拟头节点简化操作ListNodedummy(0);ListNode*tail=&dummy;while(!min_heap.empty()){//取出最小节点ListNode*curr=min_heap.top();min_heap.pop();//连接到结果链表tail->next=curr;tail=tail->next;//如果该节点后面还有节点，将其加入堆if(curr->next!=nullptr){min_heap.push(curr->next);}}returndummy.next;}};//辅助函数：创建链表ListNode*createList(){intval;ListNodedummy(0);ListNode*tail=&dummy;while(cin>>val&&val!=-1){tail->next=newListNode(val);tail=tail->next;}returndummy.next;}//辅助函数：打印链表voidprintList(ListNode*head){while(head!=nullptr){cout<<head->val<<(head->next?"":"");head=head->next;}cout<<endl;}intmain(){intN;if(!(cin>>N))return0;vector<ListNode*>lists;for(inti=0;i<N;++i){lists.push_back(createList());}Solutionsol;ListNode*merged=sol.mergeKLists(lists);printList(merged);//释放内存（实际考试中视情况而定，此处略）return0;}```【答案与解析】输入示例：```text3145-1134-126-1```输出示例：```text11234456```核心考点解析：1.算法选择：合并k个有序链表是经典问题。方法一：逐一合并。利用合并两个有序链表的函数，循环合并。时间复杂度为O(kN)，其中方法二：分治法。将k个列表两两配对合并，递归进行。时间复杂度O(方法三：优先队列（最小堆）。这是最直观且常用的方法。2.优先队列实现：维护一个大小为k的最小堆。初始时将k个链表的头节点放入堆。每次弹出堆顶元素（当前最小值），接到结果链表末尾。将弹出元素的下一个节点（如果存在）推入堆。堆的操作时间复杂度为O(logk3.细节处理：使用虚拟头节点`dummy`可以避免处理结果链表为空或初始化头节点的繁琐逻辑。注意`priority_queue`默认是最大堆，需要自定义比较器`Compare`实现最小堆。空指针检查：输入链表可能为空。题目三：二叉树算法（二叉树的锯齿形层序遍历）【问题描述】给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。数据结构定义：```cppstructTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};```例如：二叉树`[3,9,20,null,null,15,7]`,```3/\920/\157```锯齿形层序遍历结果为：```text[[3],[20,9],[15,7]]```请实现函数`vector<vector<int>>zigzagLevelOrder(TreeNode*root)`。【输入格式】输入一行表示二叉树的层序遍历序列，空节点用`null`表示，节点间用空格分隔。例如：`3920nullnull157`。【输出格式】输出每一层的节点值，每一行一层。如果该层是从右向左遍历，则逆序输出。【参考代码】```cpp#include<iostream>#include<vector>#include<queue>#include<algorithm>#include<sstream>usingnamespacestd;structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};classSolution{public:vector<vector<int>>zigzagLevelOrder(TreeNode*root){vector<vector<int>>result;if(root==nullptr)returnresult;queue<TreeNode*>q;q.push(root);boolleftToRight=true;//标记遍历方向while(!q.empty()){intsize=q.size();vector<int>level(size);//预分配空间for(inti=0;i<size;++i){TreeNode*node=q.front();q.pop();//根据方向决定索引位置intindex=leftToRight?i:(size-1-i);level[index]=node->val;if(node->left)q.push(node->left);if(node->right)q.push(node->right);}result.push_back(level);leftToRight=!leftToRight;//切换方向}returnresult;}};//反序列化二叉树TreeNode*deserialize(stringdata){if(data.empty())returnnullptr;stringstreamss(data);stringtoken;vector<TreeNode*>nodes;while(ss>>token){if(token=="null"){nodes.push_back(nullptr);}else{nodes.push_back(newTreeNode(stoi(token)));}}if(nodes.empty()||nodes[0]==nullptr)returnnullptr;queue<TreeNode*>q;q.push(nodes[0]);intindex=1;while(!q.empty()&&index<nodes.size()){TreeNode*curr=q.front();q.pop();if(index<nodes.size()){curr->left=nodes[index++];if(curr->left)q.push(curr->left);}if(index<nodes.size()){curr->right=nodes[index++];if(curr->right)q.push(curr->right);}}returnnodes[0];}intmain(){stringline;getline(cin,line);TreeNode*root=deserialize(line);Solutionsol;vector<vector<int>>res=sol.zigzagLevelOrder(root);for(constauto&level:res){for(intval:level){cout<<val<<"";}cout<<endl;}return0;}```【答案与解析】输入示例：```text3920nullnull157```输出示例：```text3209157```核心考点解析：1.层序遍历（BFS）：使用队列（Queue）是实现层序遍历的标准方法。关键在于如何区分每一层。2.分层技巧：在`while`循环内部，首先获取当前队列的大小`size`。这个`size`就是当前层的节点数。然后执行一个`for`循环`size`次，这样就能保证每次`while`迭代处理完一整层。3.锯齿形控制：引入一个布尔标志`leftToRight`。如果为`true`，则按正常顺序`0,1,2...`填充数组。如果为`false`，则按逆序索引`size-1,size-2...`填充数组。优化：不使用`std::reverse`函数，而是在写入数据时直接计算索引，这样可以将时间复杂度从O(N·4.二叉树重建：题目中包含了一个辅助函数`deserialize`，用于根据输入字符串构建二叉树。这也是上机考试的常见需求，即能够处理输入输出逻辑。构建逻辑同样利用了队列，按层序连接父子节点。题目四：动态规划（最长公共子序列LCS及其路径还原）【问题描述】给定两个字符串`text1`和`text2`，返回这两个字符串的最长公共子序列的长度。如果一个字符串是另一个字符串的子序列，则意味着该字符串是在不改变字符相对顺序的情况下，通过删除某些字符（也可以不删除任何字符）从另一个字符串派生出来的。进阶要求：请输出最长公共子序列的具体内容，而不仅仅是长度。【输入格式】输入两行，分别为两个字符串`text1`和`text2`。字符串仅包含小写字母。【输出格式】第一行输出最长公共子序列的长度。第二行输出最长公共子序列（如果有多个，输出任意一个即可）。【参考代码】```cpp#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespacestd;classSolution{public:stringlongestCommonSubsequence(stringtext1,stringtext2){intm=text1.size();intn=text2.size();//dp[i][j]表示text1[0...i-1]和text2[0...j-1]的LCS长度//多开一行一列方便处理空串情况vector<vector<int>>dp(m+1,vector<int>(n+1,0));//填充DP表for(inti=1;i<=m;++i){for(intj=1;j<=n;++j){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}//还原路径stringlcs="";inti=m,j=n;while(i>0&&j>0){if(text1[i-1]==text2[j-1]){//当前字符匹配，属于LCSlcs.push_back(text1[i-1]);i--;j--;}elseif(dp[i-1][j]>dp[i][j-1]){//上方值大，说明来源于上方i--;}else{//左方值大（或相等），说明来源于左方j--;}}//因为是从后往前拼接，需要反转reverse(lcs.begin(),lcs.end());returnlcs;}};intmain(){stringtext1,text2;getline(cin,text1);getline(cin,text2);Solutionsol;stringresult=sol.longestCommonSubsequence(text1,text2);cout<<result.length()<<endl;cout<<result<<endl;return0;}```【答案与解析】输入示例：```textabcdeace```输出示例：```text3ace```核心考点解析：1.动态规划状态定义：dp[i][2.状态转移方程：如果A[i−如果A[i−3.路径还原：从dp如果当前字符相等，则该字符一定是LCS的一部分，加入结果串，并向左上方移动。如果不等，则比较dp[i最后需要将结果字符串反转，因为回溯是从后向前构建的。4.复杂度分析：时间复杂度：O(M×N)空间复杂度：O(M×题目五：搜索与回溯（数独求解）【问题描述】编写一个程序，通过填充空单元格来解决数独问题。一个数独的解法需遵循如下规则：1.数字`1-9`在每一行只能出现一次。2.数字`1-9`在每一列只能出现一次。3.数字`1-9`在每一个以粗实线分隔的`3x3`宫内只能出现一次。4.空单元格用`'.'`表示。数独部分是已填好的，你需要填充剩余的空格。【输入格式】输入9行，每行9个字符，表示数独盘面。【输出格式】输出解决后的数独盘面，共9行。【参考代码】```cpp#include<iostream>#include<vector>usingnamespacestd;classSolution{private:boolrow[9][10];//row[i][num]表示第i行是否有数字numboolcol[9][10];//col[j][num]表示第j列是否有数字numboolbox[9][10];//box[k][num]表示第k个3x3宫是否有数字numvector<vector<char>>board;boolvalid=false;public:voidsolveSudoku(vector<vector<char>>&board){this->board=board;memset(row,0,sizeof(row));memset(col,0,sizeof(col));memset(box,0,sizeof(box));//初始化状态数组for(inti=0;i<9;++i){for(intj=0;j<9;++j){if(board[i][j]!='.'){intnum=board[i][j]-'0';fillNum(i,j,num,true);}}}dfs(0,0);board=this->board;}private://放置或移除数字voidfillNum(inti,intj,intnum,boolstate){row[i][num]=state;col[j][num]=state;box[getBoxIndex(i,j)][num]=state;}//获取3x3宫的索引intgetBoxIndex(inti,intj){return(i/3)*3+(j/3);}voiddfs(inti,intj){if(i==9){valid=true;//找到解return;}//计算下一个坐标intnextI=(j==8)?i+1:i;intnextJ=(j==8)?0:j+1;if(board[i][j]!='.'){dfs(nextI,nextJ);}else{//尝试填入1-9for(intnum=1;num<=9;++num){if(!row[i][num]&&!col[j][num]&&!box[getBoxIndex(i,j)][num]){fillNum(i,j,num,true);board[i][j]=num+'0';dfs(nextI,nextJ);if(valid)return;//剪枝，找到解后立即返回//回溯fillNum(i,j,num,false);board[i][j]='.';}}}}};intmain(){vector<vector<char>>board(9,vector<char>(9));for(inti=0;i<9;++i){for(intj=0;j<9;++j){cin>>board[i][j];}}Solutionsol;sol.solveSudoku(board);for(inti=0;i<9;++i){for(intj=0;j<9;++j){cout<<board[i][j]<<(j==8?"":"");}cout<<endl;}return0;}```【答案与解析】输入示例：```text53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79```(注：输入时字符间空格仅为方便阅读，代码支持连续输入或空格输入，这里用空格分隔)输出示例：```text534678912672195348198342567859761423426853791713924856961537284287419635345286179```核心考点解析：1.回溯算法：这是解决约束满足问题（如数独、八皇后、排列组合）的标准范式。基本思想是：尝试在当前位置放置一个合法的数字->递归进入下一位置->如果递归返回失败，则撤销当前操作（回溯），尝试下一个数字。2.状态记录与剪枝：直接检查行、列、宫是否包含某数字会非常耗时（O(使用三个二维数组`row[9][10]`,`col[9][10]`,`box[9][10]`来记录数字的使用情况。这样检查一个数字是否合法的时间复杂度降为O(`box`的索引计算：`boxIndex=(r/3)*3+(c/3)`，这能将9x9的盘面映射到9个3x3的区域。3.递归终止条件：当行号`i`达到9时，说明所有格子都已填完且合法，设置`valid`标志为true。4.优化：一旦找到解，立即通过`if(valid)return;`在所有递归栈中快速返回，避免不必要的计算，因为标准数独通常只有一个解。题目六：综合应用（哈希表与设计-LRU缓存机制）【问题描述】运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。实现`LRUCache`类：`LRUCache(intcapacity)`以正整数作为容量`capacity`初始化LRU缓存`intget(intkey)`如果关键字`key`存在于缓存中，则返回关键字的值，否则返回-1。`voidput(intkey,intvalue)`如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的值留出空间。进阶：你是否可以在O(【输入格式】第一行输入容量C。第二行输入操作数量N。接下来N行，每行格式为`getkey`或`putkeyvalue`。【输出格式】对于每个`get`操作，输出返回的值。【参考代码】```cpp#include<iostream>#include<unordered_map>usingnamespacestd;//双向链表节点structDLinkedNode{intkey,value;DLinkedNode*prev;DLinkedNode*next;DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}DLinkedNode(int_key,int_value):key(_key),value(_value),prev(nullptr),next(nullptr){}};classLRUCache{private:unordered_map<int,DLinkedNode*>cache;DLinkedNode*head;DLinkedNode*tail;intsize;intcapacity;voidaddToHead(DLinkedNode*node){node->prev=head;node->next=head->next;head->next->prev=node;head->next=node;}voidremoveNode(DLinkedNode*node){node->prev->next=node->next;node->next->prev=node->prev;}voidmoveToHead(DLinkedNode*node){removeNode(node);addToHead(node);}DLinkedNode*removeTail(){DLinkedNode*node=tail->prev;removeNode(node);returnnode;}public:LRUCache(int_capacity):capacity(_capacity),size(