2026年高校计算机科学与技术期末编程题集

2026年高校计算机科学与技术期末编程题集考试时间：______分钟总分：______分姓名：______一、基础编程题1.编写一个函数，接收一个整数数组和一个目标值，返回数组中和为目标值的两个数的索引。假设每个输入都有且只有一个解，且不能使用重复的元素。2.编写代码实现字符串的翻转，不使用内置的字符串翻转函数。3.定义一个`Point`类，包含两个属性`x`和`y`代表二维坐标，以及一个方法`distance`，用于计算该点到原点(0,0)的欧几里得距离。二、数据结构应用题4.编写一个函数，实现双向链表的逆序遍历，并打印每个节点的`data`值。5.假设有一个使用栈实现的计算器，支持整数和基本运算符`+`,`-`,`*`,`/`。请编写代码处理以下输入字符串"3+5*8-2"`，并输出计算结果。假设操作数和运算符之间没有空格。6.使用哈希表（散列表）实现一个简单的词频统计程序，读取输入的文本字符串，统计每个不同单词出现的次数，并按出现次数从高到低打印单词及其频率。忽略大小写和标点符号。三、算法设计与实现题7.编写一个函数，实现快速排序算法（QuickSort），对输入的整数数组进行排序。要求使用递归方式实现，并选择合适的基准元素（pivot）。8.给定一个包含`n`个整数的无序数组，以及一个整数`k`。请设计一个算法，在O(n)时间复杂度内找到数组中第`k`大的元素。不能使用额外的存储空间（或使用O(logn)或O(1)的额外空间）。9.实现二分查找算法（BinarySearch），用于在一个已排序的整数数组中查找给定目标值。如果找到，返回其索引；如果没有找到，返回`-1`。四、综合应用题10.假设我们需要管理一个图书馆的图书信息。图书信息包括：书号（唯一）、书名、作者、出版年份。请设计一个简单的图书管理系统，包含以下功能：a.添加一本新书的信息。b.根据书号查询并打印一本图书的完整信息。c.列出所有图书信息，按出版年份降序排列。d.实现上述功能。可以使用数组、链表、哈希表或树等数据结构来存储图书信息，并根据需要选择合适的数据结构实现各个功能。请描述你选择的数据结构以及实现思路，并编写核心代码段（例如，添加和查询功能的代码）。试卷答案一、基础编程题1.```pythondeftwo_sum(nums,target):num_to_index={}fori,numinenumerate(nums):complement=target-numifcomplementinnum_to_index:return[num_to_index[complement],i]num_to_index[num]=ireturn[]```*解析思路：使用哈希表（字典）存储遍历过程中的数字及其索引。对于每个数字`num`，计算其补数`target-num`。如果补数已经在哈希表中，说明找到了一对和为`target`的数，返回它们的索引。否则，将当前数字及其索引存入哈希表。这种方法时间复杂度为O(n)，空间复杂度也为O(n)。2.```pythondefreverse_string(s):returns[::-1]#或者#chars=list(s)#left,right=0,len(chars)-1#whileleft<right:#chars[left],chars[right]=chars[right],chars[left]#left+=1#right-=1#return''.join(chars)```*解析思路：方法一利用Python切片操作，直接返回原字符串的反转副本。方法二通过将字符串转换为字符列表，然后使用双指针技术（一个从左开始，一个从右开始）交换字符，直到指针相遇，最后将字符列表重新连接成字符串。这两种方法都能在不使用内置翻转函数的情况下实现字符串翻转。3.```pythonimportmathclassPoint:def__init__(self,x,y):self.x=xself.y=ydefdistance(self):returnmath.sqrt(self.x2+self.y2)#示例使用#p=Point(3,4)#print(p.distance())#输出5.0```*解析思路：定义`Point`类，包含初始化方法`__init__`接收`x`和`y`坐标作为属性。定义`distance`方法计算欧几里得距离，即根据点到原点的坐标`(x,y)`使用公式`sqrt(x^2+y^2)`。这里使用了`math.sqrt`函数来计算平方根。二、数据结构应用题4.```python#假设定义了DoublyLinkedList类和Node类defreverse_traverse(head):current=headwhilecurrent:print(current.data)current=current.next#正向遍历```*解析思路：双向链表的特点是每个节点包含指向前一个节点和后一个节点的指针。要进行逆序遍历，最直接的方法是直接沿着`next`指针遍历整个链表并打印节点值。由于打印操作本身是顺序的，这实现了“逆序”的打印效果（相对于从`head`到`tail`的遍历顺序）。如果需要更严格的“逆序”访问节点（例如按`prev`指针方向），则需要从`tail`节点开始，沿着`prev`指针遍历。5.```pythondefcalculate(s:str)->int:stack=[]num=0sign='+'#初始符号为'+'fori,cinenumerate(s):ifc.isdigit():num=num*10+int(c)if(cnotin'0123456789'andc!='')ori==len(s)-1:ifsign=='+':stack.append(num)elifsign=='-':stack.append(-num)elifsign=='*':stack.append(stack.pop()*num)elifsign=='/':#注意Python3中/是浮点除法，//是整数除法#题目没明确，这里假设是整数除法且整除last=stack.pop()iflast*num<0andlast%num!=0:#处理负数除不尽的情况，根据语言规范可能需要调整stack.append(-(-last//num))#Python3的//在负数时会向负无穷取整，可能需要特殊处理else:stack.append(last//num)#重置num和signnum=0sign=creturnsum(stack)```*解析思路：使用一个栈来处理操作数和中间结果。遍历输入字符串，遇到数字时构建当前数字。遇到运算符或字符串末尾时，根据前一个运算符`sign`决定如何处理当前构建好的数字`num`。如果`sign`是`+`，将`num`压入栈；如果是`-`，将`-num`压入栈；如果是`*`，弹出栈顶元素与`num`相乘后压回；如果是`/`，弹出栈顶元素与`num`相除（注意处理整数除法和符号）后压回。最后将栈中所有元素求和得到结果。忽略空格。6.```pythondefword_frequency(text):fromcollectionsimportdefaultdicttext=text.lower()#转换为小写importstringtext=text.translate(str.maketrans('','',string.punctuation))#去除标点words=text.split()freq=defaultdict(int)forwordinwords:freq[word]+=1#按频率降序排序sorted_freq=sorted(freq.items(),key=lambdaitem:item[1],reverse=True)forword,countinsorted_freq:print(f"{word}:{count}")#示例使用#word_frequency("Hello,world!Thisisatest.Helloworld!")```*解析思路：使用`collections.defaultdict`方便地统计词频。首先将所有文本转换为小写以忽略大小写差异。然后使用`str.translate`方法去除所有标点符号。接着使用`str.split`按空格分割文本得到单词列表。遍历单词列表，对每个单词，将其作为键在字典`freq`中计数。最后，将字典项按值（频率）进行降序排序，并打印每个单词及其频率。三、算法设计与实现题7.```pythondefquick_sort(arr):defpartition(low,high):pivot=arr[high]#选择最后一个元素作为基准i=low-1forjinrange(low,high):ifarr[j]<=pivot:i+=1arr[i],arr[j]=arr[j],arr[i]arr[i+1],arr[high]=arr[high],arr[i+1]returni+1defquick_sort_recursive(low,high):iflow<high:pi=partition(low,high)quick_sort_recursive(low,pi-1)quick_sort_recursive(pi+1,high)quick_sort_recursive(0,len(arr)-1)returnarr#示例使用#print(quick_sort([10,7,8,9,1,5]))```*解析思路：快速排序是分治算法。核心是`partition`函数，它选择一个基准元素（pivot），然后将数组分成两部分：左边的元素都小于等于基准，右边的元素都大于等于基准。`partition`函数返回基准元素的最终位置`pi`。`quick_sort_recursive`函数递归地对基准左右两边的子数组进行快速排序。整个过程不需要额外的存储空间（原地排序），时间复杂度平均为O(nlogn)，最坏为O(n^2)（当基准选择不当时）。8.```pythondeffind_kth_largest(nums,k):defpartition(left,right):pivot=nums[right]i=left-1forjinrange(left,right):ifnums[j]>pivot:#与快速排序相反，这里找的是第k大，所以用>i+=1nums[i],nums[j]=nums[j],nums[i]nums[i+1],nums[right]=nums[right],nums[i+1]returni+1defquick_select(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=partition(left,right)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnquick_select(left,pivot_index-1,k_smallest)else:returnquick_select(pivot_index+1,right,k_smallest)n=len(nums)ifk<1ork>n:return-1#无效的k#找第n-k+1小的元素，它在排序后数组的索引就是n-kreturnquick_select(0,n-1,n-k)#示例使用#nums=[3,2,1,5,6,4]#k=2#print(find_kth_largest(nums,k))#输出5```*解析思路：这是快速选择算法（Quickselect）的变种，用于在O(n)平均时间复杂度内找到第k大的元素。基本思想与快速排序类似，也是基于分治和`partition`操作。目标是找到第`k`大的元素，可以转化为找到排序后数组中第`n-k`小的元素。通过修改`partition`函数的比较方向（这里是`>`而不是`<=`），并调整递归调用和`k`的计算方式，可以在平均O(n)时间内找到目标元素。最坏情况仍为O(n^2)，但通过随机选择基准可以改进。9.```pythondefbinary_search(arr,target):left,right=0,len(arr)-1whileleft<=right:mid=left+(right-left)//2ifarr[mid]==target:returnmidelifarr[mid]<target:left=mid+1else:#arr[mid]>targetright=mid-1return-1#示例使用#arr=[1,2,3,4,5,6,7,8,9]#target=4#print(binary_search(arr,target))#输出3```*解析思路：二分查找算法适用于在已排序的数组中查找元素。核心思想是每次将查找范围缩小一半。初始化两个指针`left`和`right`，分别指向数组的开始和结束。计算中间位置`mid`。比较`arr[mid]`与`target`：*如果`arr[mid]==target`，找到目标，返回`mid`。*如果`arr[mid]<target`，说明目标在`mid`右侧，将`left`移动到`mid+1`。*如果`arr[mid]>target`，说明目标在`mid`左侧，将`right`移动到`mid-1`。如果`left`超过`right`，说明数组中不存在目标元素，返回`-1`。每次比较都将查找区间减半，时间复杂度为O(logn)。四、综合应用题10.```pythonclassBook:def__init__(self,id,title,author,year):self.id=idself.title=titleself.author=authorself.year=yearclassLibrary:def__init__(self):self.books_by_id={}#使用哈希表存储，方便按ID快速查找self.books_by_year=[]#使用列表存储，按年份插入，方便排序defadd_book(self,book):#检查ID是否重复ifbook.idinself.books_by_id:print(f"Error:BookwithID{book.id}alreadyexists.")returnFalseself.books_by_id[book.id]=book#插入到按年份降序排列的列表中#使用二分查找找到正确的插入位置left,right=0,len(self.books_by_year)whileleft<right:mid=(left+right)//2ifself.books_by_year[mid].year<book.year:right=midelse:left=mid+1self.books_by_year.insert(left,book)returnTruedeffind_book_by_id(self,book_id):ifbook_idinself.books_by_id:book=self.books_by_id[book_id]print(f"ID:{book.id},Title:{book.title},Author:{book.author},Year:{book.year}")returnTrueelse:print(f"BookwithID{book_id}notfound.")returnFalsedeflist_books_by_year_desc(self):forbookinself.books_by_year:print(f"ID:{book.id},Title:{book.title},Author:{book.author},Year:{book.year}")#示例