编程复赛常考试题与答案

编程复赛常考试题与答案整理考试时间：______分钟总分：______分姓名：______一、选择题1.在计算机中，数据的最小存储单位是（），数据的可读最小单位是（）。A.字节B.字C.位D.字长2.关于算法的时间复杂度，下列说法正确的是（）。A.算法执行时间等于算法中所有语句执行时间之和B.算法执行时间与输入规模无关C.算法执行时间与具体计算机的硬件环境有关D.算法执行时间等于算法中所有语句频度之和3.下列数据结构中，不属于线性结构的是（）。A.线性表B.栈C.队列D.二叉树4.在C++中，`std::vector<int>vec;vec.push_back(1);vec.pop_back();`执行后，`vec.size()`的值为（）。A.0B.1C.2D.35.下列排序算法中，时间复杂度为O(nlogn)且是稳定排序的是（）。A.快速排序B.堆排序C.归并排序D.希尔排序6.关于递归算法，下列说法正确的是（）。A.递归算法一定比非递归算法效率高B.递归算法一定比非递归算法更容易理解C.递归算法必须包含终止条件，否则会导致栈溢出D.递归算法不能处理大规模数据7.给定一个有序数组`intarr[]={1,3,5,7,9};`，要查找元素`4`，使用二分查找法，第一次比较的中间元素下标是（）。A.0B.1C.2D.38.在图论中，一个有向图有5个顶点，任意两个顶点之间都有边相连，则该图的边数最多为（）。A.5B.10C.20D.259.下列关于`const`关键字的说法，正确的是（）。A.`constint*p`表示指针p指向的值不能改变B.`int*constp`表示指针p指向的地址不能改变C.`constint*constp`表示指针p指向的地址和值都不能改变D.以上说法都不完全正确10.下列代码段输出结果是（）。```cppinta=10;int*p1=&a;int*p2=p1;*p2=20;cout<<a<<endl;```A.10B.20C.0D.1020二、多选题1.下列关于栈和队列的描述中，正确的是（）。A.栈是先进后出（LIFO）B.队列是先进先出（FIFO）C.栈和队列都是线性表D.栈和队列都可以用链表实现2.下列排序算法中，在平均情况下时间复杂度为O(n^2)的有（）。A.冒泡排序B.选择排序C.插入排序D.归并排序3.关于动态规划，下列说法正确的是（）。A.动态规划通常用于解决多阶段决策问题B.动态规划需要保存每个子问题的解以避免重复计算C.动态规划一定能比递归效率高D.动态规划的关键在于状态转移方程的建立4.在C++STL中，`std::set`和`std::map`的底层实现通常是基于（）。A.数组B.链表C.红黑树D.哈希表5.关于位运算，下列说法正确的是（）。A.`a&b`表示按位与B.`a|b`表示按位或C.`a^b`表示按位异或D.`~a`表示对a取反6.下列关于输入输出流（I/O）的描述，正确的是（）。A.`cin`是标准输入流B.`cout`是标准输出流C.`scanf`和`printf`比`cin`和`cout`速度通常更快D.使用`endl`比`"\n"`刷新缓冲区的效率更高7.下列关于文件操作的描述，正确的是（）。A.打开文件需要包含`<fstream>`头文件B.使用`ifstream`进行读操作，使用`ofstream`进行写操作C.`fstream`可以同时进行读写操作D.关闭文件操作`close()`是必须的，否则可能导致数据丢失8.在搜索算法（如DFS/BFS）中，关于剪枝（Pruning）的说法正确的是（）。A.剪枝可以提高搜索效率B.剪枝可以剔除所有无效的搜索路径C.深度优先搜索（DFS）中常用的剪枝方法有最优性剪枝和可行性剪枝D.广度优先搜索（BFS）通常不需要剪枝三、填空题1.在C++中，`std::vector`是一种动态数组，要访问容器中第`i`个元素，可以使用`vec.at(i)`或`vec[i]`，但前者在越界时会抛出异常，后者则会产生未定义行为。2.递归函数必须包含终止条件，否则会导致栈溢出错误。3.对于一个包含n个元素的数组，其前缀和公式为`sum[i]=sum[i-1]+arr[i]`，其中`sum[0]`通常定义为`arr[0]`或`0`，具体取决于题目定义。4.在图论中，若一个图有`n`个顶点，且任意两个顶点之间都有边相连，则该图的边数为`n*(n-1)/2`（无向图）或`n*(n-1)`（有向图）。5.全排列问题通常使用回溯法解决，回溯法通常包含两个步骤：递归进入下一层和递归返回上一层。四、编程实现题1.【贪心算法】区间调度问题题目描述：有若干个活动，每个活动都有一个开始时间`start_i`和结束时间`end_i`。如果两个活动的开始时间`start_i`和结束时间`end_j`满足`start_i>=end_j`，则活动i可以在活动j结束后开始。请编写程序，计算出最多能安排多少个互不冲突的活动。输入格式：第一行输入一个整数n(1≤n≤100)，表示活动的数量。输出格式：输出一个整数，表示最多能安排的活动数量。2.【动态规划】最长公共子序列（LCS）题目描述：给定两个字符串A和B，求这两个字符串的最长公共子序列的长度。子序列是指不改变原字符串中字符的相对顺序，删除一部分字符后得到的新序列。输入格式：第一行输入字符串A。第二行输入字符串B。字符串长度均不超过100。输出格式：输出一个整数，表示最长公共子序列的长度。3.【搜索与剪枝】全排列输出题目描述：给定一个不重复的整数数组`nums`，返回该数组所有可能的全排列（按任意顺序返回即可）。要求：使用回溯法或深度优先搜索（DFS）实现，不得使用STL的`next_permutation`函数。输入格式：第一行输入整数n(1≤n≤8)。第二行输入n个整数`nums[i]`。输出格式：输出所有可能的全排列，每行一个排列，元素之间用空格隔开。注意：不要有多余的空格或换行符。4.【图论】最短路径（BFS）题目描述：在一个无权图中（边权均为1），从起点`S`到终点`T`，求最短路径的长度。如果有多条最短路径，输出任意一条即可。图的顶点编号为0到N-1，共N个顶点。输入格式：第一行输入两个整数N和M，分别表示顶点数和边数。第二行输入起点S和终点T。输出格式：输出一个整数，表示最短路径的长度。如果起点和终点不连通，输出-1。5.【数据结构】单调栈应用题目描述：给定一个整数数组`heights`，其中`heights[i]`代表第`i`标柱子的高度。柱子间有一个宽度为1，现要从这些柱子中选出几根柱子，使其组成的矩形面积最大。矩形必须由柱子连成，且不能跨越柱子间的空隙。输入格式：第一行输入整数n(1≤n≤10^5)。第二行输入n个整数`heights[i]`。输出格式：输出一个整数，表示最大矩形面积。试卷答案一、选择题1.C,B解析：在计算机中，数据的最小存储单位是位（bit），它是二进制位的最小单位；数据的可读最小单位通常指字符（Character），一个字符由若干个字节组成。2.D解析：算法的时间复杂度通常用算法中基本操作执行的次数来度量，即算法中所有语句频度之和。算法的执行时间受硬件环境（如CPU速度、编译器效率）影响，因此与具体计算机硬件环境有关；算法执行时间与输入规模有关，与硬件无关。3.D解析：栈、队列、线性表都是线性结构，而二叉树是非线性结构（树形结构），每个节点最多有两个子节点。4.A解析：`push_back`向容器末尾添加一个元素，容器大小加1；`pop_back`移除容器末尾的元素，容器大小减1。初始大小为0，操作后大小为0。5.C解析：归并排序的时间复杂度为O(nlogn)，且它是稳定的排序算法。快速排序和堆排序的时间复杂度也是O(nlogn)，但它们是不稳定的排序算法。希尔排序是对插入排序的改进，平均时间复杂度在O(n^2)到O(nlogn)之间。6.C解析：递归算法必须包含终止条件（基准情况），否则递归调用会无限进行，最终导致栈溢出。递归算法不一定比非递归算法效率高，且不一定更容易理解。7.C解析：数组下标从0开始，长度为5。中间元素下标为`(0+4)/2=2`，对应的值为5。比较发现5>4，所以去右边查找。8.B解析：对于n个顶点的无向完全图，每两个顶点之间都有且只有一条边，边数为`n*(n-1)/2`。本题n=5，计算结果为`5*4/2=10`。9.A,B,C解析：这三者都是C++中合法的常量指针声明。*`constint*p`：指针p指向的值不能改变（const修饰的是int）。*`int*constp`：指针p本身的指向地址不能改变（const修饰的是指针）。*`constint*constp`：指针p指向的值和地址都不能改变。通常在考试中，如果这三个选项都正确，应全选。10.B解析：`p1`指向`a`，`p2`被赋值为`p1`，所以`p1`和`p2`指向同一个地址。`*p2=20`修改的是`a`的值，因此`a`输出为20。二、多选题1.A,B,C,D解析：栈是先进后出（LIFO），队列是先进先出（FIFO），它们都是线性表。栈和队列都可以使用链表（单向链表或双向链表）来实现。2.A,B,C解析：冒泡排序、选择排序、插入排序的平均时间复杂度都是O(n^2)。归并排序、快速排序、堆排序的平均时间复杂度是O(nlogn)。3.A,B,D解析：动态规划用于解决多阶段决策问题，需要保存子问题解以避免重复计算，关键在于状态转移方程。C选项错误，因为递归实现的动态规划如果包含大量重叠子问题，效率可能低于优化的递归或非递归解法。4.C解析：C++STL中的`std::set`和`std::map`是基于红黑树（一种自平衡二叉搜索树）实现的，能够保证查找、插入、删除的时间复杂度为O(logn)。5.A,B,C,D解析：这些都是位运算的基本操作。*`&`：按位与*`|`：按位或*`^`：按位异或*`~`：按位取反6.A,B,C解析：`cin`和`cout`是C++标准输入输出流。`scanf`和`printf`是C语言风格，通常比流操作更快（因为没有缓冲区类型转换的开销）。D选项错误，`endl`会强制刷新缓冲区，这比直接输出`"\n"`要慢，且`"\n"`只换行不刷新缓冲区。7.A,B,C解析：文件操作需要包含`<fstream>`头文件。`ifstream`用于读，`ofstream`用于写，`fstream`可用于读写。虽然操作系统会在进程结束时自动关闭文件，但在编程规范中，显式调用`close()`是良好的习惯以释放资源。8.A,B,C解析：剪枝可以去除不必要的搜索路径从而提高效率。深度优先搜索（DFS）常用可行性剪枝（剪掉无法到达终点的路径）和最优性剪枝（剪掉已经不是最优的路径）。广度优先搜索（BFS）是逐层搜索，通常不需要剪枝（除非有明显的对称性或重复状态），因为它本身就是为了找最短路径。三、填空题1.`vec[i]`解析：`vec.at(i)`在越界时会抛出异常（如`std::out_of_range`），而`vec[i]`在越界时行为是未定义的（UB），这可能导致程序崩溃或读取非法内存。2.基准情况解析：递归必须有终止条件（BaseCase），否则递归调用会一直进行，直到堆栈空间耗尽。3.`arr[0]`解析：前缀和通常定义为`sum[0]=arr[0]`，或者在某些定义中`sum[0]=0`，但公式`sum[i]=sum[i-1]+arr[i]`要求`sum[0]`为`arr[0]`才能使公式对i=1成立（即`sum[1]=sum[0]+arr[1]`）。4.`n*(n-1)/2`解析：n个顶点的无向完全图，每个顶点与其他n-1个顶点相连，总度数为n*(n-1)。因为无向图中每条边贡献2个度数，所以边数为`n*(n-1)/2`。5.回溯解析：回溯法本质是深度优先搜索（DFS）的一种，其核心思想是“探索与回溯”，即在探索过程中遇到不满足条件时，撤销上一步的选择（回溯）并尝试其他路径。四、编程实现题1.【贪心算法】区间调度问题*解析思路：这是一个经典的贪心问题。最优策略是“尽可能多地安排活动”。为了保证剩余时间最多，我们应该优先选择结束时间最早的活动。具体步骤如下：1.按照活动的结束时间对数组进行升序排序。2.初始化计数器`count=1`，选取第一个活动的结束时间作为当前结束时间`current_end`。3.遍历剩余活动，如果当前活动的开始时间`start_i>=current_end`，则安排该活动，更新`count`和`current_end`。*答案核心代码：```cppsort(v.begin(),v.end(),[](vector<int>a,vector<int>b){returna[1]<b[1];});intcount=1,current_end=v[0][1];for(inti=1;i<n;i++){if(v[i][0]>=current_end){count++;current_end=v[i][1];}}cout<<count;```2.【动态规划】最长公共子序列（LCS）*解析思路：LCS是动态规划的典型应用。1.定义状态：`dp[i][j]`表示字符串A的前i个字符和字符串B的前j个字符的最长公共子序列长度。2.状态转移方程：*如果`A[i-1]==B[j-1]`，则`dp[i][j]=dp[i-1][j-1]+1`。*如果`A[i-1]!=B[j-1]`，则`dp[i][j]=max(dp[i-1][j],dp[i][j-1])`。3.初始化：`dp[i][0]=0`和`dp[0][j]=0`。*答案核心代码：```cppintdp[105][105]={0};for(inti=1;i<=A.size();i++){for(intj=1;j<=B.size();j++){if(A[i-1]==B[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[A.size()][B.size()];```3.【搜索与剪枝】全排列输出*解析思路：使用深度优先搜索（DFS）配合访问标记数组。1.定义一个`used[]`数组记录当前数字是否被使用。2.递归函数`dfs(pos)`：*`pos`表示当前要填第几个位置。*如果`pos==n`，说明已经排好，输出当前路径。*遍历所有数字，如果未被使用，则标记为已用，加入当前路径，递归`dfs(pos+1)`，回溯时取消标记。*答案核心代码：```cppvector<int>path;boolused[10]={false};voiddfs(intpos){if(path.size()==n){for(intx:path)cout<<x<<"";cout<<endl;return;}for(inti=0;i<n;i++){if(!used[i]){used[i]=true;path.push_back(nums[i]);dfs(pos+1);path.pop_back();used[i]=false;}}}```4.【图论】最短路径（BFS）*解析思路：在无权图中，最短路径问题可以使用广度优先搜索（BFS）解决。BFS天然具有“分层遍历”的特性，第一次到达终点时，经过的步数即为最短距离。1.使用队列存储节点，使用`dist[]`数组记录起点到各节点的距离，初始化为-1。2.将起点入队，`dist[S]=0`。3.循环处理队列：取出队首元素`u`，遍历`u`的所有邻居`v`。4.如果`dist[v]==-1`（未访问过），则`dist[v]=dist[u]+1`，并将`v`入队。5.当队列为空或`dist[T]!=-1`时停止。*答案核心代码：```cppqueue<int>q;intdist[N]={0};q.push(S);dist[S]=0;while(!q.empty()){intu=q.front();q.pop();if(u==T)break;for(intv:adj[u]){if(dist[v]==-1){dist[v]=dist[u]+1;q.push(v);}}}cout<<dist[T];```5.【数据结构】单