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

2026年高校计算机科学与技术专业期末考试试卷编程题冲刺押题考试时间：______分钟总分：______分姓名：______一、代码填空题1.以下Python代码实现了二分查找算法，请将缺失的部分补充完整。```pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=________ifarr[mid]==target:returnmidelifarr[mid]<target:left=________else:right=________return-1```2.以下C++代码实现了栈的链式存储结构，请将缺失的部分补充完整。```cppstructNode{intdata;Node*next;Node(intx):data(x),next(NULL){}};classStack{private:Node*top;public:Stack():top(NULL){}boolisEmpty(){return________;}voidpush(intx){Node*newNode=newNode(x);newNode->next=________;top=newNode;}intpop(){if(isEmpty()){return-1;}Node*temp=top;intpopped=temp->data;top=top->next;deletetemp;returnpopped;}};```3.以下Java代码实现了队列的链式存储结构，请将缺失的部分补充完整。```javaclassNode{intdata;Nodenext;Node(intx){data=x;next=null;}}classQueue{privateNodefront,rear;publicQueue(){front=rear=null;}booleanisEmpty(){return________;}voidenqueue(intx){NodenewNode=newNode(x);if(rear==null){front=rear=newNode;return;}rear.next=________;rear=newNode;}intdequeue(){if(isEmpty()){return-1;}intpopped=front.data;front=front.next;if(front==null){rear=null;}returnpopped;}}```二、代码阅读题1.阅读以下Python代码，该代码实现了快速排序算法，请解释该代码的工作原理。```pythondefquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)```2.阅读以下C++代码，该代码实现了二叉搜索树的插入操作，请解释该代码的工作原理。```cppstructTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};voidinsertIntoBST(TreeNode*root,intval){if(root==NULL){root=newTreeNode(val);return;}if(val<root->val){if(root->left==NULL){root->left=newTreeNode(val);}else{insertIntoBST(root->left,val);}}else{if(root->right==NULL){root->right=newTreeNode(val);}else{insertIntoBST(root->right,val);}}}```三、算法设计题1.设计一个算法，找出一个无序数组中重复次数最多的元素及其重复次数。例如，在数组`[1,3,2,1,4,1]`中，元素`1`重复次数最多，为`3`次。请用伪代码描述该算法，并分析其时间复杂度。2.设计一个算法，判断一个给定的字符串是否是回文串。例如，字符串`"madam"`是回文串，而字符串`"hello"`不是回文串。请用C++或Java实现该算法，并分析其时间复杂度。四、综合应用题设计一个简单的文本编辑器程序，该程序支持以下操作：*`INSERTs`：在当前光标位置插入字符串`s`。*`DELETEn`：删除`n`个字符。*`LEFTk`：将光标向左移动`k`个位置。*`RIGHTk`：将光标向右移动`k`个位置。程序需要维护一个字符串作为文本内容，以及一个整数表示当前光标的位置。请用Python或Java实现该程序的核心功能，并解释你的实现思路。试卷答案一、代码填空题1.mid=left+(right-left)//2right=mid-1left=mid+12.top==NULLtop3.front==nullrear二、代码阅读题1.该代码实现了快速排序算法。工作原理如下：*选择一个基准元素（pivot），这里选择数组中间的元素。*将数组划分为三个部分：小于基准元素的元素、等于基准元素的元素、大于基准元素的元素。*递归地对小于基准元素和大于基准元素的子数组进行快速排序。*最终将排序好的子数组与等于基准元素的元素连接起来，得到排序好的数组。*时间复杂度：平均情况为O(nlogn)，最坏情况为O(n^2)。2.该代码实现了二叉搜索树的插入操作。工作原理如下：*如果当前节点为空，则创建一个新节点，并将其值设置为val，作为插入节点。*如果当前节点的值小于val，则将val插入到当前节点的左子树中，否则插入到右子树中。*递归地进行插入操作，直到找到合适的插入位置。*时间复杂度：平均情况为O(logn)，最坏情况为O(n)。三、算法设计题1.伪代码：```functionfindMostFrequentElement(arr):countMap=newHashMap()maxCount=0mostFrequentElement=nullfori=0toarr.length-1:ifcountMap.containsKey(arr[i]):countMap[arr[i]]=countMap[arr[i]]+1else:countMap[arr[i]]=1ifcountMap[arr[i]]>maxCount:maxCount=countMap[arr[i]]mostFrequentElement=arr[i]returnmostFrequentElement,maxCount```时间复杂度：O(n)2.C++代码：```cppboolisPalindrome(strings){intleft=0,right=s.length()-1;while(left<right){while(left<right&&!isalnum(s[left]))left++;while(left<right&&!isalnum(s[right]))right--;if(tolower(s[left])!=tolower(s[right]))returnfalse;left++;right--;}returntrue;}```时间复杂度：O(n)四、综合应用题Python代码示例：```pythonclassTextEditor:def__init__(self):self.text=""self.cursor=0definsert(self,s):self.text=self.text[:self.cursor]+s+self.text[self.cursor:]self.cursor+=len(s)defdelete(self,n):ifn>0:self.text=self.text[:self.cursor]+self.text[self.cursor+n:]self.cursor=max(0,self.cursor-n)defleft(self,k):self.cursor=max(0,self.cursor-k)defright(self,k):self.cursor=min(len(self.text),self.cursor+k)defget_text(self):returnself.text#示例用法editor=TextEdit