2023复试——机试随笔【c++】【考研】

**2023复试——机试随笔**

**前言**

作为一名即将毕业的研究生，我深感幸运能够参加2023年的复试。机试是整个复试过程中的一项重要环节，考察了我们的编程能力和对算法的理解。在这篇随笔中，我将分享我在机试中的体验和所学到的经验。

**一、题目类型**

今年的机试共有四道题，其中三道是基础题，一个是综合题。基础题主要考察了我们对数据结构、算法和计算机网络等基本知识的掌握。综合题则要求我们将这些知识应用到实际问题中去。

**二、题目内容**

### 基础题一：链表反转题目描述：给定一个单向链表，要求实现链表反转。

cpp// Node结构定义struct ListNode {
 int val;
 ListNode* next;
};

// 链表反转函数ListNode* reverseList(ListNode* head) {
 if (head == nullptr || head->next == nullptr) return head;

 ListNode* newHead = nullptr;
 while (head != nullptr) {
 //保存当前节点的下一个节点 ListNode* nextNode = head->next;
 // 将当前节点设置为新链表的头结点 head->next = newHead;
 newHead = head;

 // 移动到下一个节点 head = nextNode;
 }

 return newHead;
}

cpp// 滑动窗口函数vector<int> slidingWindow(vector<int>& nums, int k) {
 vector<int> result;
 for (int i =0; i <= nums.size() - k; i++) {
 // 初始化窗口内元素的和 int sum =0;

 // 遍历窗口内的元素 for (int j = i; j < i + k; j++) {
 sum += nums[j];
 }

 result.push_back(sum);
 }

 return result;
}

cpp// Node结构定义struct TreeNode {
 int val;
 TreeNode* left;
 TreeNode* right;
};

// 中序遍历函数void inorderTraversal(TreeNode* root, vector<int>& result) {
 if (root == nullptr) return;

 // 遍历左子树 inorderTraversal(root->left, result);

 // 访问当前节点 result.push_back(root->val);

 // 遍历右子树 inorderTraversal(root->right, result);
}

cpp// 动态规划函数int longestIncreasingSubsequence(vector<int>& nums) {
 if (nums.empty()) return0;

 vector<int> dp(nums.size(),1);
 for (int i =1; i < nums.size(); i++) {
 for (int j =0; j < i; j++) {
 // 如果当前元素大于前面一个元素，则更新dp[i]
 if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] +1);
 }
 }

 return *max_element(dp.begin(), dp.end());
}