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

2026年高校计算机科学与技术2025学年期末单套试卷程序设计考试时间：______分钟总分：______分姓名：______一、选择题1.以下哪个选项不是C/C++语言的基本数据类型？A.intB.floatC.charD.list2.在逻辑运算中，`!(A&&B)`等价于以下哪个表达式？A.A||BB.A&&!BC.!A||!BD.!A&&!B3.下列关于数组的描述，正确的是？A.数组的大小在创建后可以动态改变B.数组既可以存储基本数据类型，也可以存储自定义类型C.数组元素在内存中一定连续存储D.数组访问某个元素的时间复杂度是O(n)4.设有函数声明`voidfun(intarr[],intsize);`，以下对函数`fun`的调用方式中，正确的是？A.`fun({1,2,3},3);`B.`fun(*arr,size);`其中`arr`是指向整型变量的指针，`size`是整型变量C.`fun(&n,1);`其中`n`是整型变量D.`fun(arr,sizeof(arr));`其中`arr`是整型数组5.在下列数据结构中，适合表示先进先出（FIFO）特性的结构是？A.栈(Stack)B.队列(Queue)C.链表(LinkedList)D.树(Tree)6.对长度为n的线性表进行顺序查找，在最坏情况下，比较元素的次数为？A.n/2B.n+1C.nD.log2(n)7.下列哪个排序算法的平均时间复杂度和最坏时间复杂度都是O(n^2)？A.快速排序(QuickSort)B.归并排序(MergeSort)C.堆排序(HeapSort)D.插入排序(InsertionSort)8.在二叉树中，如果一个节点只有左子节点没有右子节点，该节点仍然可以被称为完全二叉树节点吗？A.可以B.不可以C.取决于树的深度D.取决于该节点的父节点9.以下哪个运算符在C/C++中用于计算模（取余）？A.%B./C.*D.&&10.对于面向对象编程（OOP），以下哪个概念描述了将数据和操作数据的方法捆绑在一起？A.封装(Encapsulation)B.继承(Inheritance)C.多态(Polymorphism)D.抽象(Abstraction)二、填空题1.在Java中，用于定义类默认构造函数的关键字是________。2.C/C++语言中，用于动态分配内存（在堆区）的运算符是________。3.若一个节点的度为2，则称该节点为________节点（在二叉树语境下）。4.算法的空间复杂度通常指算法执行过程中临时占用的最大存储空间，其计算通常基于________的数量级。5.在栈的操作中，向栈中添加元素的操作称为________，从栈中移除元素并获取其值的操作称为________。6.若一个算法的时间复杂度是O(nlogn)，其中n表示问题规模，当n增大时，该算法的执行时间随n增长的速率比O(n^2)________（快/慢）。7.在链表结构中，为了快速删除任意位置节点，通常需要保持对其________节点的引用。8.堆排序算法通常利用________（数据结构）来实现最大堆或最小堆的维护。9.在设计类时，将类的属性设置为private主要是为了实现________。10.递归算法通常需要借助________来保存函数调用的状态信息。三、简答题1.简述栈的LIFO（后进先出）特性，并列举至少两个栈在实际应用中的例子。2.什么是递归？请说明递归函数必须满足的三个条件。3.简述面向对象编程（OOP）的四个基本特性（封装、继承、多态、抽象）及其含义。四、代码阅读理解题阅读以下用Python语言编写的代码，回答问题：```pythondefsearch(arr,low,high,target):ifhigh>=low:mid=(low+high)//2#Checkiftheelementispresentatthemidifarr[mid]==target:returnmid#Ifelementissmallerthanmid,thenitcanonlybepresentinleftsubarrayelifarr[mid]>target:returnsearch(arr,low,mid-1,target)#Elsetheelementcanonlybepresentinrightsubarrayelse:returnsearch(arr,mid+1,high,target)else:#Elementisnotpresentinthearrayreturn-1#Exampleusagemy_list=[10,20,30,40,50]target_value=30result=search(my_list,0,len(my_list)-1,target_value)ifresult!=-1:print(f"Elementispresentatindex{result}")else:print("Elementisnotpresentinthelist")```1.该函数`search`实现了什么算法？请说明。2.该算法在什么条件下会终止递归？3.如果`my_list`是升序排列的，当`target_value`为60时，函数返回什么值？为什么？五、代码填空题阅读以下Python代码框架，并根据要求补全代码。```pythondeffind_second_largest(arr):iflen(arr)<2:return"Listshouldhaveatleasttwoelements"#Initializefirstandsecondlargestelementsifarr[0]>arr[1]:first,second=arr[0],arr[1]else:first,second=arr[1],arr[0]#Traversethearraystartingfromthesecondelementforiinrange(2,len(arr)):ifarr[i]>first:#Newlargestelementfound,updatefirstandsecond________#Fillthislineelifarr[i]>secondandarr[i]!=first:#Newsecondlargestfound________#Fillthislinereturnsecondifsecond!=Noneelse"Nosecondlargestelementfound"#Exampleusagenumbers=[12,35,1,10,34,1]second_largest=find_second_largest(numbers)print(f"Thesecondlargestelementis:{second_largest}")```请将上面代码中需要填空的`________`部分替换为正确的Python代码行。六、编程实现题请使用C/C++或Java语言编写一个完整的程序。要求：1.定义一个名为`Node`的结构体（对于C/C++）或类（对于Java），用于表示双向链表的节点。该节点包含两个成员：一个整型数据域`data`，以及两个指向相邻节点的指针域`prev`和`next`（对于C/C++）或`prev`和`next`（对于Java）。2.在程序中，实现一个双向链表类（或包含相关操作的函数/方法）。该类/函数应至少包含以下成员函数/方法：*`add(intvalue)`:在双向链表的末尾添加一个包含指定整数值的新节点。*`display()`:遍历并打印双向链表中的所有节点的数据值，先从头部开始。*`display_reverse()`:遍历并打印双向链表中的所有节点的数据值，先从尾部开始。3.在`main`函数（或主方法）中，创建一个双向链表对象，然后依次向其中添加元素`10,20,30,40,50`。之后，调用`display()`和`display_reverse()`函数分别打印正向和反向的双向链表内容。试卷答案一、选择题1.D2.C3.B4.D5.B6.C7.D8.A9.A10.A二、填空题1.default2.new(或malloc)3.非空4.空间5.push,pop6.快7.前驱8.树形9.封装10.栈三、简答题1.答：栈是一种只允许在一端（栈顶）进行插入和删除操作的数据结构，具有后进先出（LIFO）的特性。应用例子：函数调用栈、表达式求值（中缀转后缀）、浏览器历史记录（后退功能）。2.答：递归是指一个函数直接或间接地调用自身来解决问题。递归函数必须满足三个条件：基准情况（basecase，终止递归的条件）、递归步骤（将问题分解为更小的子问题并递归调用自身）、前进性（每次递归调用都向基准情况靠近）。3.答：*封装：将数据（属性）和操作数据的方法（行为）捆绑在一起，并隐藏对象的内部实现细节，只暴露必要的接口。*继承：允许一个类（子类/派生类）继承另一个类（父类/基类）的属性和方法，实现代码复用和扩展。*多态：指不同类的对象对同一消息（方法调用）可以做出不同的响应。通常通过方法重载（编译时多态）和方法重写（运行时多态）实现。*抽象：指隐藏对象的内部复杂性，只暴露其本质特征和接口。通过抽象类和接口实现。四、代码阅读理解题1.答：该函数实现了二分查找算法。2.答：该算法在`low`大于`high`时终止递归，此时表示搜索区间为空，元素不在数组中。3.答：函数返回`-1`。因为`60`大于数组中的所有元素（`50`是最大值），所以搜索区间会不断缩小至`low>high`，最终函数返回`-1`。五、代码填空题```pythondeffind_second_largest(arr):iflen(arr)<2:return"Listshouldhaveatleasttwoelements"#Initializefirstandsecondlargestelementsifarr[0]>arr[1]:first,second=arr[0],arr[1]else:first,second=arr[1],arr[0]#Traversethearraystartingfromthesecondelementforiinrange(2,len(arr)):ifarr[i]>first:#Newlargestelementfound,updatefirstandsecondfirst,second=arr[i],firstelifarr[i]>secondandarr[i]!=first:#Newsecondlargestfoundsecond=arr[i]returnsecondifsecond!=Noneelse"Nosecondlargestelementfound"#Exampleusagenumbers=[12,35,1,10,34,1]second_largest=find_second_largest(numbers)print(f"Thesecondlargestelementis:{second_largest}")```填空解析：第一个填空：当发现一个新元素比当前最大值`first`还大时，原来的`first`就变成了第二大的值，新的最大值是当前元素`arr[i]`。因此需要更新`first`为`arr[i]`，并将原来的`first`值赋给`second`。第二个填空：当发现一个新元素不等于当前最大值`first`，并且比当前第二大的值`second`还大时，说明找到了新的第二大的值。因此需要将`second`更新为`arr[i]`。六、编程实现题（以下为C++语言示例代码）```cpp#include<iostream>//DefinetheNodestructureforadoublylinkedliststructNode{intdata;Node*prev;Node*next;Node(intval):data(val),prev(nullptr),next(nullptr){}//Constructor};//DefinetheDoublyLinkedListclassclassDoublyLinkedList{public:Node*head;Node*tail;//ConstructorDoublyLinkedList():head(nullptr),tail(nullptr){}//Functiontoaddanodeattheendofthelistvoidadd(intvalue){Node*newNode=newNode(value);if(head==nullptr){head=tail=newNode;}else{tail->next=newNode;newNode->prev=tail;tail=newNode;}}//Functiontodisplaythelistfromheadtotailvoiddisplay(){Node*current=head;while(current!=nullptr){std::cout<<current->data<<"";current=current->next;}std::cout<<std::endl;}//Functiontodisplaythelistfromtailtoheadvoiddisplay_reverse(){Node*current=tail;while(current!=nullptr){std::cout<<current->data<<"";current=current->prev;}std::cout<<std::endl;}//Destructor(optionalbutgoodpractice)~DoublyLinkedList(){Node*current=head;while(current!=nullptr){Node*next=current->next;dele