2026年高校计算机科学与技术2025学年期末单套试卷编程题

2026年高校计算机科学与技术2025学年期末单套试卷编程题考试时间：______分钟总分：______分姓名：______一、选择题1.以下哪个数据结构是先进后出（LIFO）的？A.队列(Queue)B.栈(Stack)C.队列(Dequeue)D.堆(Heap)2.在已排序的数组中查找一个元素，最有效的算法是？A.冒泡排序(BubbleSort)B.插入排序(InsertionSort)C.二分查找(BinarySearch)D.选择排序(SelectionSort)3.下列哪个算法适用于求解图中顶点之间的最短路径问题？A.快速排序(QuickSort)B.冒泡排序(BubbleSort)C.Dijkstra算法(Dijkstra'sAlgorithm)D.冒泡排序(BubbleSort)4.以下哪个不是面向对象编程（OOP）的基本特性？A.封装(Encapsulation)B.继承(Inheritance)C.迭代(Iteration)D.多态(Polymorphism)5.以下哪种数据结构适合用于实现优先队列？A.数组(Array)B.链表(LinkedList)C.堆(Heap)D.栈(Stack)6.计算机程序执行的主要内存单元是？A.寄存器(Registers)B.辅助存储器(SecondaryStorage)C.运算器(ArithmeticLogicUnit-ALU)D.控制器(ControlUnit)7.以下哪个不是算法的时间复杂度表示方法？A.O(1)B.O(n)C.O(n^2)D.O(logn)8.在C++/Java等语言中，`#include<iostream>`或`importjava.util.*;`语句的作用是？A.定义一个类B.声明一个函数C.包含头文件或库，以便使用其中的功能D.分配内存空间9.下列哪个操作是递归函数必须包含的？A.输出结果B.调用自身C.分配内存D.初始化变量10.当我们说一个算法的时间复杂度是O(nlogn)时，意味着什么？A.算法执行时间与输入规模n成正比B.算法执行时间与输入规模n的对数成正比C.算法执行时间增长速度介于n和nlogn之间D.算法执行时间是常数二、多项选择题11.以下哪些属于基本数据类型（以C++/Java为例）？A.intB.charC.StringD.floatE.boolean12.栈的主要操作包括？A.插入(Insert)B.删除(Delete)C.初始化(Initialize)D.访问栈顶元素(Peek)E.排序(Sort)13.以下哪些算法属于分治法策略的典型应用？A.快速排序(QuickSort)B.归并排序(MergeSort)C.冒泡排序(BubbleSort)D.二分查找(BinarySearch)E.堆排序(HeapSort)14.在面向对象编程中，继承的主要优点有？A.提高代码可重用性B.增强代码可维护性C.实现数据隐藏D.提供代码封装E.允许创建类的层次结构15.以下哪些情况可能导致程序运行时错误？A.除以零的操作B.访问数组越界C.使用未初始化的指针D.循环条件永远为真E.变量名拼写错误（编译时错误）三、编程题（一）基础数据结构实现(25分)请用你选择的编程语言（如C++、Java或Python）实现一个单链表（SinglyLinkedList）的类，并包含以下成员函数：1.`__init__`：构造函数，初始化空链表。2.`insert_at_head(data)`：向链表头部插入一个新节点（包含数据`data`）。3.`insert_at_tail(data)`：向链表尾部插入一个新节点（包含数据`data`）。4.`delete_head()`：删除链表头部的节点，并返回被删除节点的数据。如果链表为空，则返回None或提示错误。5.`search(data)`：在链表中查找值为`data`的节点。如果找到，返回True；否则返回False。6.`__str__`或`to_string`：返回一个表示链表内容的字符串，例如`1->2->3->None`。（二）算法设计与实现(25分)请编写一个函数（或方法），实现以下功能：给定一个由正整数组成的非空列表（数组），返回一个新列表，其中包含原始列表中每个元素的平方，但仅保留平方值小于或等于给定阈值`threshold`的元素，并且结果列表按升序排序。*要求:*首先，计算列表中所有元素的平方。*然后，筛选出平方值小于或等于`threshold`的元素。*最后，对筛选后的元素列表进行升序排序。*请设计一个时间复杂度尽可能优化的算法来实现此功能。*你可以选择使用任何合适的数据结构来辅助实现。（三）综合应用题(15分)假设你需要编写一个简单的文本文件统计程序。该程序需要从标准输入（或文件）读取一行或多行文本，统计并输出以下信息：1.文本中的总字符数（不包括空格和标点符号）。2.文本中的总单词数（以空格为分隔符）。3.文本中出现的不同单词的列表，按字母顺序排序。请设计并实现该程序的核心逻辑部分。你可以假设输入文本仅包含英文字符、空格和常见的英文标点符号（如逗号、句号、分号等），并且单词之间由一个或多个空格分隔。你需要明确说明如何处理标点符号（例如，是否计入字符数，是否从单词统计中排除）。试卷答案一、选择题1.B2.C3.C4.C5.C6.A7.A8.C9.B10.C二、多项选择题11.A,B,D,E12.A,B,C,D13.A,B,D,E14.A,B,E15.A,B,C,D三、编程题（一）基础数据结构实现(假设使用Python）```pythonclassNode:def__init__(self,data):self.data=dataself.next=NoneclassSinglyLinkedList:def__init__(self):self.head=Nonedefinsert_at_head(self,data):new_node=Node(data)new_node.next=self.headself.head=new_nodedefinsert_at_tail(self,data):new_node=Node(data)ifself.headisNone:self.head=new_nodereturncurrent=self.headwhilecurrent.nextisnotNone:current=current.nextcurrent.next=new_nodedefdelete_head(self):ifself.headisNone:returnNone#或raiseException("Listisempty")removed_data=self.head.dataself.head=self.head.nextreturnremoved_datadefsearch(self,data):current=self.headwhilecurrentisnotNone:ifcurrent.data==data:returnTruecurrent=current.nextreturnFalsedef__str__(self):elements=[]current=self.headwhilecurrentisnotNone:elements.append(str(current.data))current=current.nextelements.append("None")return"->".join(elements)```解析思路:选择题：考察基本概念。1.栈是LIFO结构。2.二分查找在有序数组中效率最高。3.Dijkstra算法用于求最短路径。4.OOP四大特性是封装、继承、多态、抽象。5.堆结构天然支持优先队列。6.程序执行主要在内存中的寄存器。7.O(1),O(n),O(n^2),O(logn)是常见的时间复杂度表示。8.#include引入头文件，import引入库。9.递归的核心是自我调用。10.O(nlogn)表示增长速度比O(n)快，但比O(n^2)慢。多选题：考察知识点广度。11.C++/Java基本数据类型包括int,char,float,boolean。String是引用类型。12.栈基本操作是Push(Insert)/Pop(Delete)，访问栈顶元素(Peek)。初始化是构造函数做的事情。排序不是栈的标准操作。13.分治法将问题分解为子问题，递归解决，合并结果。快速排序、归并排序、二分查找、堆排序都符合此策略。冒泡排序是迭代法。14.继承优点是代码复用、维护性、层次结构。多态是OOP的另一大特性，与继承紧密相关。数据隐藏是封装的特性。15.除以零、数组越界、未初始化指针使用、死循环都是运行时错误。变量名拼写错误是编译时语法错误。编程题（一）：考察链表实现。需要定义节点类Node和链表类SinglyLinkedList。链表类需要初始化为空（head为None）。insert_at_head需要创建新节点，将其next指向原head，然后head指向新节点。insert_at_tail需要遍历到末尾，然后插入新节点。delete_head需要处理空链表情况，否则将head指向下一个节点并返回删除节点的数据。search需要遍历链表比较数据。__str__需要遍历链表将数据收集起来，格式化为字符串返回。（二）算法设计与实现(假设使用Python）```pythondeffilter_and_sort_squares(arr,threshold):#计算平方并筛选squared_filtered=[x2forxinarrifx2<=threshold]#对结果排序squared_filtered.sort()returnsquared_filtered```解析思路:此题考察算法设计、列表操作和复杂度分析。首先，需要对输入数组的每个元素x计算其平方x2。然后，根据题目要求，需要筛选出所有平方值小于或等于`threshold`的元素。这可以通过列表推导式实现：`[x2forxinarrifx2<=threshold]`。列表推导式内部先计算平方，然后通过`if`条件判断是否小于等于阈值，满足条件的才被包含在结果列表`squared_filtered`中。最后，题目要求结果列表按升序排序。Python列表的`.sort()`方法可以将列表就地排序，时间复杂度为O(nlogn)。因此，整个函数的时间复杂度主要取决于排序步骤，为O(nlogn)，其中n是筛选后剩余元素的数量。如果筛选后元素很少，排序的开销很小。（三）综合应用题(假设使用Python）```pythonimportstringdeftext_stats(text):#去除标点符号，只保留字母和空格，并将文本转为小写translator=str.maketrans('','',string.punctuation)cleaned_text=text.translate(translator).lower()#统计字符数（不包括空格和标点）char_count=sum(1forcincleaned_textifc.isalpha())#统计单词数（以空格分隔）words=cleaned_text.split()word_count=len(words)#统计不同单词并排序unique_words=sorted(set(words))returnchar_count,word_count,uniq