2026年高校计算机科学与技术专业编程能力测试卷详解

2026年高校计算机科学与技术专业编程能力测试卷详解考试时间：______分钟总分：______分姓名：______一、选择题（每题2分，共20分）1.下列哪个不是Java语言的基本数据类型？A.intB.floatC.booleanD.StringE.char2.在C++中，用于动态分配内存的运算符是？A.=B.*C.newD.deleteE.sizeof3.下列关于数组描述错误的是？A.数组是索引的集合B.数组的大小在创建后通常不可变C.数组的索引通常从0开始D.数组可以存储不同类型的数据E.数组是一种线性数据结构4.设有链表节点定义`structNode{intdata;Node*next;}`，在指向头节点的指针p下，删除p所指节点的直接后继节点的正确操作是？（假设直接后继存在且其指针为q）A.p->next=q->next;deleteq;B.q=p->next;p->next=q->next;deleteq;C.p->next=p->next->next;deletep->next;D.q=p;p=p->next;deletep;E.p->next=deletep->next;5.下列排序算法中，平均时间复杂度最低的是？A.冒泡排序B.选择排序C.插入排序D.快速排序E.堆排序6.在二叉搜索树中，任意节点的左子树中的所有节点的值均小于该节点的值，右子树中的所有节点的值均大于该节点的值。这个描述？A.仅在完全二叉树中成立B.仅在平衡二叉树中成立C.总是成立D.有时成立E.总是成立，但根节点没有父节点7.下列关于递归的说法错误的是？A.递归需要有递归出口B.递归函数调用自身C.递归可以提高代码的可读性D.递归会消耗更多的内存（栈空间）E.每次递归调用都会创建新的变量副本8.设有函数`voidswap(int&a,int&b)`，其中`&`表示引用。调用`swap(x,y);`会导致变量x和y的值？A.仍然保持原值B.互相交换C.x的值变为y的值，y保持不变D.x的值不变，y变为x的原值E.可能交换，也可能不交换，取决于编译器9.下列关于面向对象编程（OOP）原则的说法错误的是？A.封装：隐藏对象内部细节，仅暴露必要的接口B.继承：实现代码复用，建立类之间的层级关系C.多态：允许不同类的对象对同一消息做出不同响应D.抽象：关注对象的本质特征，忽略非本质细节E.对象间必须通过消息传递进行交互10.当我们需要频繁地在数据集合中查找元素，且插入和删除操作相对较少时，比较适合使用的数据结构是？A.数组B.链表C.哈希表D.树E.栈二、填空题（每空2分，共20分）1.在Python中，用于表示元组的符号是________。2.C++中，`#include<iostream>`头文件主要用于包含输入输出流库，其中`cout`是指向________的对象。3.在队列中，插入元素的操作称为________，删除元素的操作称为________。4.堆排序是一种基于________的排序算法，它可以将数组调整为最大堆或最小堆。5.在二叉树中，某个节点的子节点称为该节点的________，该节点称为其子节点的________。6.算法的________效率是指算法执行所需要的基本运算次数，而________效率是指算法执行所需占用存储空间的大小。7.在面向对象中，通过`extends`关键字实现的是________关系，通过`implements`关键字实现的是________关系（以Java或类似语言为例）。8.所谓递归函数，是指在其函数体内部________调用自身的函数。9.哈希表通过计算键值（Key）来直接确定数据存储位置，其主要的冲突解决方法有________和________。10.代码的________指的是代码的清晰易懂程度，良好的代码规范有助于提高代码的________。三、编程题（共30分）1.（10分）编写一个函数，接收一个整数数组`arr`和一个目标整数`target`，返回一个布尔值，表示数组中是否存在至少两个不同的索引`i`和`j`，使得`arr[i]+arr[j]==target`。要求：不得使用额外的数组或集合存储元素，尽量优化时间复杂度。函数签名如下（以C++为例）：```cppboolhasTargetSum(intarr[],intsize,inttarget);```请在下方给出该函数的完整实现。2.（10分）编写一个函数，接收一个字符串`s`，返回该字符串中每个字符出现的次数。返回值应为`std::map<char,int>`（C++）或`dict[str,int]`（Python），其中键是字符，值是该字符在字符串中出现的次数。函数签名如下（以C++为例）：```cppstd::map<char,int>countCharacters(conststd::string&s);```请在下方给出该函数的完整实现。3.（10分）假设我们使用单链表实现栈（后进先出-LIFO）。节点定义如下（以C++为例）：```cppstructListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};```请编写`push`和`pop`操作的实现。`push(val)`将元素val压入栈顶，`pop()`返回并移除栈顶元素。如果栈为空，`pop()`应返回一个错误标识（例如-1）。函数签名如下：```cppclassLinkedListStack{public:ListNode*top;LinkedListStack():top(nullptr){}voidpush(intval);intpop();};```请在下方给出`push`和`pop`函数的完整实现。四、阅读与完善题（共30分）阅读以下C++代码段，该代码旨在实现一个简单的二分查找算法，用于在一个已按非降序排列的整数数组`arr`中查找目标值`target`。数组的大小由`size`参数给出。如果找到目标值，函数返回其索引；如果未找到，函数返回-1。```cpp#include<vector>intbinarySearch(conststd::vector<int>&arr,intsize,inttarget){intleft=0;intright=size-1;while(left<=right){//代码缺失处1//在此处计算中间位置mid的值//--intmid=...;//请补充计算mid的表达式if(arr[mid]==target){returnmid;//找到目标值，返回索引}elseif(arr[mid]<target){//代码缺失处2//在此处更新左边界left的值//--left=...;//请补充更新left的表达式}else{//arr[mid]>target//代码缺失处3//在此处更新右边界right的值//--right=...;//请补充更新right的表达式}}return-1;//未找到目标值}```请补充代码缺失处1、2、3的具体内容，以完善该二分查找算法。试卷答案一、选择题1.D2.C3.D4.B5.E6.C7.E8.B9.E10.C二、填空题1.()2.ostream3.入队(Enqueue),出队(Dequeue)4.二叉堆(BinaryHeap)5.子节点(Child),父节点(Parent)6.时间(Time),空间(Space)7.继承(Inheritance),实现(Implementation)8.自身(itself)9.开放地址法(OpenAddressing),链地址法(SeparateChaining)10.可读性(Readability),可维护性(Maintainability)三、编程题1.代码实现（C++示例）：```cppboolhasTargetSum(intarr[],intsize,inttarget){if(size<2)returnfalse;//至少需要两个元素intleft=0;intright=size-1;while(left<right){intcurrentSum=arr[left]+arr[right];if(currentSum==target){returntrue;}elseif(currentSum<target){left++;//需要更大的和，移动左指针}else{right--;//需要更小的和，移动右指针}}returnfalse;}```解析思路：*目标：在无额外存储的情况下，判断数组中是否存在两个不同的索引`i`和`j`使得`arr[i]+arr[j]==target`。*策略：利用双指针技术。首先对数组进行排序（虽然题目未要求排序，但此方法通常隐含数组有序或可以接受排序，若数组无序则需先排序）。初始化两个指针，一个指向数组的起始位置（`left`），另一个指向末尾位置（`right`）。*迭代：计算`arr[left]+arr[right]`的和。*如果和等于`target`，则找到一对解，返回`true`。*如果和小于`target`，为了增大和，需要移动`left`指针向右（`left++`）。*如果和大于`target`，为了减小和，需要移动`right`指针向左（`right--`）。*结束：如果两个指针相遇(`left>=right`)仍未找到满足条件的数对，则返回`false`。*注意：题目要求“不得使用额外的数组或集合存储元素”，双指针方法只使用常数额外空间，符合要求。时间复杂度主要由排序决定（如果需要），或假设数组已排序，则为O(n)。2.代码实现（C++示例）：```cpp#include<map>#include<string>std::map<char,int>countCharacters(conststd::string&s){std::map<char,int>charCount;for(charc:s){charCount[c]++;}returncharCount;}```解析思路：*目标：统计字符串中每个字符出现的次数。*策略：使用哈希表（在C++中为`std::map`或`std::unordered_map`，Python中为`dict`）。`std::map`内部通常实现为红黑树，`std::unordered_map`实现为哈希表。`std::unordered_map`通常提供更快的平均查找速度。此处使用`std::map`示例。遍历字符串中的每个字符，将其作为键（Key）在哈希表中查找。*如果键已存在，则将其对应的值（计数）加一。*如果键不存在，则将其插入哈希表，并将计数初始化为1。*实现：使用基于范围的for循环(`for(charc:s)`)来迭代字符串中的每个字符。对每个字符`c`，使用`charCount[c]++`来更新其计数。*返回：遍历完成后，返回包含字符及其对应计数的`std::map`对象。3.代码实现（C++示例）：```cppstructListNode{intval;ListNode*next;ListNode(intx):val(x),next(nullptr){}};classLinkedListStack{public:ListNode*top;LinkedListStack():top(nullptr){}voidpush(intval){ListNode*newNode=newListNode(val);newNode->next=top;top=newNode;}intpop(){if(top==nullptr){return-1;//栈为空，返回错误标识}ListNode*temp=top;intpoppedValue=temp->val;top=top->next;deletetemp;returnpoppedValue;}};```解析思路：*目标：使用单链表实现栈的基本操作`push`和`pop`。*栈特性：后进先出(LIFO)。链表适合实现栈，因为链表的头部（头节点）是插入和删除操作的便捷位置。*`push(val)`操作：*创建一个新节点`newNode`，其值为`val`，其`next`指针初始为`nullptr`。*将新节点插入到链表头部，使其成为新的栈顶。即，将`newNode->next`指向当前的栈顶`top`。*更新栈顶指针`top`指向`newNode`。*`pop()`操作：*检查栈是否为空（`top==nullptr`）。如果为空，则无法弹出元素，返回错误标识（如`-1`）。*如果不为空，获取当前栈顶节点的值`poppedValue`。*保存`top`节点的下一个节点（即原栈顶的下一个元素，成为新的栈顶）。*释放原栈顶节点的内存（`deletetemp`）。*更新栈顶指针`top`指向新的栈顶节点。*返回弹出的值`poppedValue`。四、阅读与完善题代码完善：```cppintbinarySearch(conststd::vector<int>&arr,intsize,inttarget){intleft=0;intright=size-1;while(left<=right){//代码缺失处1//在此处计算中间位置mid的值//--intmid=left+(right-left)/2;//防止(left+right)可能的溢出if(arr[mid]==target){returnmid;//找到目标值，返回索引}elseif(arr[mid]<target){//代码缺失处2//在此处更新左边界