2026年高校计算机科学与技术专业期末考试试卷编程题

2026年高校计算机科学与技术专业期末考试试卷编程题考试时间：______分钟总分：______分姓名：______一、编写一个函数`voidreverseString(char*s)`，该函数接收一个字符串`s`作为参数，原地反转字符串中的字符顺序。假设字符串以空字符`'\0'`结尾，且字符串长度不超过1000个字符。请展示你的代码实现。二、假设你正在使用C++语言实现一个简单的栈（Stack）数据结构，栈中元素为整数。请完成以下任务：1.定义一个名为`SimpleStack`的类，使用`std::vector<int>`作为内部存储结构。2.在该类中实现以下成员函数：*`SimpleStack()`：构造函数，初始化空栈。*`boolisEmpty()const`：判断栈是否为空，若为空返回`true`，否则返回`false`。*`voidpush(intelement)`：将一个整数`element`压入栈顶。*`intpop()`：移除栈顶元素，并返回其值。如果栈为空，则抛出一个`std::runtime_error`异常。*`inttop()const`：返回栈顶元素的值，但不移除它。如果栈为空，则抛出一个`std::runtime_error`异常。*`size_tsize()const`：返回栈中元素的数量。三、编写一个函数`intcountPaths(intn)`，该函数计算在一个`nxn`的二维网格中，从左上角(0,0)走到右下角(n-1,n-1)的不同路径数量。行走规则是只能从左向右或从上向下移动。请展示你的代码实现。假设`n`是一个正整数且`n<=20`。四、给定一个整数数组`nums`和一个整数`target`，编写一个函数`vector<int>twoSum(vector<int>&nums,inttarget)`，找出数组中和为`target`的两个数的索引，并将它们作为数组返回。假设每个输入都有且仅有一个解，且不能重复使用同一个元素。请展示你的代码实现。例如，给定`nums=[2,7,11,15]`,`target=9`，函数应返回`[0,1]`，因为`nums[0]+nums[1]==2+7=9`。五、设计一个算法，将一个给定的非空二叉搜索树（BST）转换成一个排序的循环双向链表。要求不能创建任何新的节点，只调整树中节点的指针。转换后的双向链表应该保持二叉搜索树中中序遍历的顺序。具体来说，链表中的第一个节点为原始二叉搜索树中的最小值节点，最后一个节点为原始二叉搜索树中的最大值节点，且最后一个节点的`right`指针应指向第一个节点，第一个节点的`left`指针应指向最后一个节点，形成一个循环链表。请展示你的代码实现。你需要返回转换后的双向链表中的任意节点即可。六、编写一个函数`boolisValidParentheses(strings)`，判断一个字符串`s`是否为有效的括号字符串。字符串中的括号类型包括`'{'`,`'['`,`']'`,`'}'`，`'('`,`')'`。一个有效的括号字符串必须满足：1.左括号必须与相同类型的右括号匹配。2.括号必须以正确的顺序闭合。3.每个右括号都有一个对应的相同类型的左括号。请展示你的代码实现。例如，`"()"`和`"(())"`是有效的，而`")("`和`"(()"`是无效的。试卷答案一、```cppvoidreverseString(char*s){if(s==nullptr)return;intlength=0;//首先计算字符串长度while(s[length]!='\0'){length++;}//使用两个指针，一个在开头，一个在末尾char*left=s;char*right=s+length-1;//交换两个指针所指向的字符，并向中间移动while(left<right){chartemp=*left;*left=*right;*right=temp;left++;right--;}}```解析：反转字符串的核心思想是使用两个指针，一个从字符串开头向后移动，另一个从字符串末尾向前移动，交换两个指针所指向的字符，直到两个指针相遇或交叉。首先需要确定字符串的长度，然后进行字符的交换操作。二、```cpp#include<vector>#include<stdexcept>classSimpleStack{private:std::vector<int>data;public:SimpleStack(){}//构造函数boolisEmpty()const{//判断栈是否为空returndata.empty();}voidpush(intelement){//压入栈顶data.push_back(element);}intpop(){//移除栈顶元素并返回if(isEmpty()){throwstd::runtime_error("Stackisempty");}inttopElement=data.back();data.pop_back();returntopElement;}inttop()const{//返回栈顶元素但不移除if(isEmpty()){throwstd::runtime_error("Stackisempty");}returndata.back();}size_tsize()const{//返回栈中元素数量returndata.size();}};```解析：使用`std::vector<int>`作为内部存储结构，可以方便地实现栈的操作。`isEmpty`函数通过检查`vector`是否为空来判断栈是否为空。`push`函数将元素添加到`vector`的末尾。`pop`函数移除`vector`的最后一个元素并返回它，如果栈为空则抛出异常。`top`函数返回`vector`的最后一个元素但不移除它，如果栈为空则抛出异常。`size`函数返回`vector`的大小，即栈中元素的数量。三、```cpp#include<vector>intcountPaths(intn){if(n<=0)return0;std::vector<std::vector<int>>dp(n,std::vector<int>(n,0));//初始化边界条件for(inti=0;i<n;++i){dp[0][i]=1;dp[i][0]=1;}//动态规划填充表格for(inti=1;i<n;++i){for(intj=1;j<n;++j){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}returndp[n-1][n-1];}```解析：这是一个典型的动态规划问题。定义`dp[i][j]`为到达位置`(i,j)`的路径数量。初始条件是第一行和第一列的路径数量为1，因为只能从左或从上到达。对于其他位置，到达`(i,j)`的路径数量等于从`(i-1,j)`到达和从`(i,j-1)`到达的路径数量之和。最终`dp[n-1][n-1]`就是到达右下角的路径数量。四、```cpp#include<vector>#include<unordered_map>vector<int>twoSum(vector<int>&nums,inttarget){std::unordered_map<int,int>numMap;//将数字和它的索引存入哈希表for(inti=0;i<nums.size();++i){numMap[nums[i]]=i;}//遍历数组，查找target-num是否在哈希表中for(inti=0;i<nums.size();++i){intcomplement=target-nums[i];if(numMap.find(complement)!=numMap.end()&&numMap[complement]!=i){return{i,numMap[complement]};}}return{};//如果没有找到，返回空数组}```解析：使用哈希表（`unordered_map`）来存储数组中的数字及其索引。首先遍历数组，将每个数字及其索引存入哈希表。然后再次遍历数组，对于每个数字`nums[i]`，计算`complement=target-nums[i]`，检查`complement`是否在哈希表中且其索引不等于`i`。如果在，则返回`[i,numMap[complement]]`。如果遍历完数组没有找到，则返回空数组。五、```cpp//定义二叉树节点structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};//定义双向链表节点structListNode{intval;ListNode*prev;ListNode*next;ListNode(intx):val(x),prev(nullptr),next(nullptr){}};TreeNode*convertBSTToLinkedList(TreeNode*root){if(!root)returnnullptr;ListNode*head=nullptr;ListNode*prev=nullptr;//递归中序遍历std::function<void(TreeNode*)>inorder=[&](TreeNode*node){if(!node)return;inorder(node->left);ListNode*newNode=newListNode(node->val);if(!prev){head=newNode;}else{newNode->prev=prev;prev->next=newNode;}prev=newNode;inorder(node->right);};inorder(root);//使链表成为循环链表if(head){head->prev=prev;prev->next=head;}returnhead;}```解析：将二叉搜索树转换为排序的循环双向链表，可以利用中序遍历的特性。中序遍历二叉搜索树会按照升序访问所有节点。我们定义两个指针`head`和`prev`，`head`用来记录链表的头节点，`prev`用来记录当前遍历到的链表节点。在遍历过程中，为每个访问到的树节点创建一个新的链表节点，并调整`prev`和`newNode`的`next`和`prev`指针，形成双向链表。最后，将链表的头尾节点连接起来，形成循环链表。六、```cppboolisValidParentheses(strings){