2025年成章信息学测试题及答案

2025年成章信息学测试题及答案选择题1.以下哪种编程语言通常不用于信息学竞赛？A.PythonB.JavaC.C++D.VisualBasic答案：D。分析：信息学竞赛常用Python、Java、C++，VisualBasic不常用。2.下列哪个数据结构适用于实现后进先出（LIFO）的操作？A.队列B.栈C.链表D.树答案：B。分析：栈的特点是后进先出。3.以下哪个排序算法的平均时间复杂度是$O(nlogn)$？A.冒泡排序B.选择排序C.快速排序D.插入排序答案：C。分析：冒泡、选择、插入排序平均时间复杂度是$O(n^2)$，快速排序是$O(nlogn)$。4.若要查找一个有序数组中某个元素的位置，使用哪种算法效率最高？A.顺序查找B.二分查找C.哈希查找D.线性查找答案：B。分析：在有序数组中二分查找效率最高，时间复杂度$O(logn)$。5.以下哪个关键字用于在Python中定义函数？A.funcB.functionC.defD.define答案：C。分析：Python用def定义函数。6.在C++中，以下哪个是正确的输出语句？A.cout<<"Hello";B.print("Hello");C.printf("Hello");D.console.log("Hello");答案：A。分析：B是Python输出方式，C是C语言输出方式，D是JavaScript输出方式。7.一个有向图有5个顶点，若要保证图是强连通图，至少需要多少条边？A.4B.5C.6D.7答案：B。分析：有向强连通图至少n条边（n为顶点数）。8.以下哪种算法可以用于求解最短路径问题？A.深度优先搜索B.广度优先搜索C.Dijkstra算法D.拓扑排序答案：C。分析：Dijkstra算法用于求最短路径，广度优先搜索可求无权图最短路径，但通常说的最短路径算法选Dijkstra。9.在Python中，以下哪个操作符用于取整除？A./B.//C.%D.答案：B。分析：//是取整除，/是普通除法，%是取余，是幂运算。10.以下哪种数据结构适合用于实现优先队列？A.栈B.队列C.堆D.链表答案：C。分析：堆适合实现优先队列。填空题11.在Python中，列表`a=[1,2,3,4,5]`，要获取列表的长度可以使用______函数。答案：len。分析：len函数用于获取列表等序列的长度。12.在C++中，定义常量使用______关键字。答案：const。分析：const用于定义常量。13.二叉树的遍历方式主要有前序遍历、中序遍历和______遍历。答案：后序。分析：二叉树常见遍历方式有前序、中序、后序。14.若一个栈的初始状态为空，依次入栈元素为1,2,3,4，再依次出栈，出栈顺序为______。答案：4,3,2,1。分析：栈后进先出。15.在Python中，字典`d={'a':1,'b':2}`，要获取键'b'对应的值可以使用______操作。答案：d['b']。分析：通过键访问字典的值。16.图的存储方式主要有邻接矩阵和______。答案：邻接表。分析：图常见存储方式是邻接矩阵和邻接表。17.快速排序的基本思想是______。答案：分治法，选择一个基准值，将数组分为两部分，小于基准的放左边，大于基准的放右边，再分别对两部分排序。18.在C++中，动态分配内存使用______运算符。答案：new。分析：new用于动态分配内存。19.若要在Python中引入一个模块，使用______关键字。答案：import。分析：import用于引入模块。20.一个无向图有8个顶点，若要保证图是连通图，至少需要______条边。答案：7。分析：无向连通图至少n1条边（n为顶点数）。简答题21.简述栈和队列的区别。答案：栈是后进先出（LIFO）的数据结构，元素从栈顶入栈和出栈；队列是先进先出（FIFO）的数据结构，元素从队尾入队，从队头出队。应用场景上，栈常用于递归调用、表达式求值等，队列常用于任务调度、广度优先搜索等。22.解释Python中的列表和元组的区别。答案：列表是可变的数据类型，可以进行元素的添加、删除、修改操作；元组是不可变的数据类型，一旦创建，元素不能修改。列表用方括号[]表示，元组用圆括号()表示。23.简述Dijkstra算法的基本步骤。答案：（1）初始化：将起始顶点的距离设为0，其他顶点距离设为无穷大，创建一个集合记录已确定最短距离的顶点。（2）选择：从未确定最短距离的顶点中选择距离最小的顶点。（3）更新：更新该顶点的邻接顶点的距离。（4）重复23步骤，直到所有顶点的最短距离都确定。24.解释C++中的引用和指针的区别。答案：引用是变量的别名，必须在定义时初始化，不能为NULL，使用时无需解引用；指针是存储变量地址的变量，可以不初始化，可指向NULL，使用时需要解引用。25.简述深度优先搜索（DFS）和广度优先搜索（BFS）的区别。答案：DFS是沿着一条路径尽可能深地访问顶点，直到无法继续再回溯，使用栈或递归实现；BFS是逐层访问顶点，使用队列实现。DFS空间复杂度与树的深度有关，BFS空间复杂度与树的宽度有关。编程题26.编写一个Python函数，计算一个整数列表中所有偶数的和。```pythondefsum_of_even(lst):returnsum(iforiinlstifi%2==0)lst=[1,2,3,4,5,6]print(sum_of_even(lst))```答案分析：使用生成器表达式筛选出偶数，再用sum函数求和。27.编写一个C++程序，输入一个整数n，输出n的阶乘。```cppinclude<iostream>usingnamespacestd;intfactorial(intn){if(n==0||n==1){return1;}returnnfactorial(n1);}intmain(){intn;cin>>n;cout<<factorial(n)<<endl;return0;}```答案分析：使用递归函数计算阶乘。28.编写一个Python程序，判断一个字符串是否是回文串。```pythondefis_palindrome(s):returns==s[::1]s="racecar"print(is_palindrome(s))```答案分析：通过字符串反转判断是否相等。29.编写一个C++程序，实现冒泡排序。```cppinclude<iostream>usingnamespacestd;voidbubbleSort(intarr[],intn){for(inti=0;i<n1;i++){for(intj=0;j<ni1;j++){if(arr[j]>arr[j+1]){inttemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}intmain(){intarr[]={64,34,25,12,22,11,90};intn=sizeof(arr)/sizeof(arr[0]);bubbleSort(arr,n);for(inti=0;i<n;i++){cout<<arr[i]<<"";}cout<<endl;return0;}```答案分析：通过多次比较相邻元素并交换实现排序。30.编写一个Python程序，统计一个字符串中每个字符出现的次数。```pythons="hello"char_count={}forcharins:ifcharinchar_count:char_count[char]+=1else:char_count[char]=1print(char_count)```答案分析：使用字典记录字符及其出现次数。综合题31.给定一个整数数组`nums`和一个目标值`target`，找出数组中所有和为`target`的不重复的三元组。```pythondefthreeSum(nums,target):nums.sort()result=[]n=len(nums)foriinrange(n2):ifi>0andnums[i]==nums[i1]:continueleft,right=i+1,n1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal<target:left+=1eliftotal>target:right=1else:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right1]:right=1left+=1right=1returnresultnums=[1,0,1,2,1,4]target=0print(threeSum(nums,target))```答案分析：先排序，固定一个数，再用双指针找另外两个数，同时去重。32.实现一个简单的栈类，包含入栈、出栈、获取栈顶元素和判断栈是否为空的操作。```pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):ifself.is_empty():returnNonereturnself.items.pop()defpeek(self):ifself.is_empty():returnNonereturnself.items[1]defis_empty(self):returnlen(self.items)==0stack=Stack()stack.push(1)stack.push(2)print(stack.pop())print(stack.peek())```答案分析：使用列表实现栈的基本操作。33.给定一个二叉树，实现二叉树的前序遍历。```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorderTraversal(root):result=[]defhelper(node):ifnode:result.append(node.val)helper(node.left)helper(node.right)helper(root)returnresultroot=TreeNode(1)root.right=TreeNode(2)root.right.left=TreeNode(3)print(preorderTraversal(root))```答案分析：使用递归实现前序遍历。34.编写一个C++程序，实现一个简单的链表，包含插入节点和遍历链表的操作。```cppinclude<iostream>usingnamespacestd;structNode{intdata;Nodenext;Node(intval):data(val),next(nullptr){}};classLinkedList{private:Nodehead;public:LinkedList():head(nullptr){}voidinsert(intval){NodenewNode=newNode(val);if(!head){head=newNode;}else{Nodetemp=head;while(temp>next){temp=temp>next;}temp>next=newNode;}}voidtraverse(){Nodetemp=head;while(temp){cout<<temp>data<<"";temp=temp>next;}cout<<endl;}};intmain(){LinkedListlist;list.insert(1);list.insert(2);list.insert(3);list.traverse();return0;}```答案分析：定义节点结构，链表类实现插入和遍历操作。35.给定一个字符串`s`，找出其中最长的回文子串。```pythondeflongestPalindrome(s):iflen(s)<2:returnsstart,max_len=0,0defexpandAroundCenter(left,right):nonlocalstart,max_lenwhileleft>=0andright<len(s)ands[left]==s[right]:ifrightleft+1>max_len:start=leftmax_len=rightleft+1left=1right+=1foriinrange(len(s)):expandAroundCenter(i,i)expandAroundCenter(i,i+1)returns[start:start+max_len]s="babad"print(longestPalindrome(s))```答案分析：以每个字符或两个字符为中心向两边扩展找最长回文子串。算法设计题36.设计一个算法，判断一个图是否是二分图。```pythonfromcollectionsimportdequedefisBipartite(graph):n=len(graph)color=[1]nforiinrange(n):ifcolor[i]==1:queue=deque([i])color[i]=0whilequeue:node=queue.popleft()forneighboringraph[node]:ifcolor[neighbor]==1:color[neighbor]=1color[node]queue.append(neighbor)elifcolor[neighbor]==color[node]:returnFalsereturnTruegraph=[[1,3],[0,2],[1,3],[0,2]]print(isBipartite(graph))```答案分析：使用广度优先搜索，给节点染色，相邻节点颜色不同，若出现相邻节点颜色相同则不是二分图。37.设计一个算法，实现字符串的全排列。```pythondefpermute(s):result=[]defbacktrack(path,used):iflen(path)==len(s):result.append(''.join(path))returnforiinrange(len(s)):ifused[i]:continuepath.append(s[i])used[i]=Truebacktrack(path,used)path.pop()used[i]=Falseused=[False]len(s)backtrack([],used)returnresults="abc"print(permute(s))```答案分析：使用回溯法生成字符串的全排列。38.设计一个算法，找出一个数组中的第k大元素。```pythonimportheapqdeffindKthLargest(nums,k):heap=[]fornuminnums:heapq.heappush(heap,num)iflen(heap)>k:heapq.heappop(heap)returnheapq.heappop(heap)nums=[3,2,1,5,6,4]k=2print(findKthLargest(nums,k))```答案分析：使用最小堆，维护一个大小为k的堆，堆顶即为第k大元素。39.设计一个算法，实现图的拓扑排序。```pythonfromcollectionsimportdefaultdict,dequedeftopologicalSort(graph,numVertices):inDegree=[0]numVerticesfornodeingraph:forneighboringraph[node]:inDegree[neighbor]+=1queue=deque([iforiinrange(numVertices)ifinDegree[i]==0])result=[]whilequeue:node=queue.popleft()result.append(node)forneighboringraph[node]:inDegree[neighbor]=1ifinDegree[neighbor]==0:queue.append(neighbor)iflen(result)==numVertices:returnresultreturn[]graph={0:[1,2],1:[3],2:[3],3:[]}numVertices=4print(topologicalSort(graph,numVertices))```答案分析：计算每个节点的入度，将入度为0的节点加入队列，不断更新入度，直到队列为空。40.设计一个算法，判断一个数是否是快乐数。```pythondefisHappy(n):defget_next(n):total_sum=0whilen>0:digit=n%10total_sum+=digit2n//=10returntotal_sumseen=set()whilen!=1andnnotinseen:seen.add(n)n=get_next(n)returnn==1n=19print(isHappy(n))```答案分析：使用集合记录出现过的数，若出现循环则不是快乐数，若最终为1则是快乐数。逻辑推理题41.有三个盒子，一个盒子里装着苹果，一个盒子里装着橘子，一个盒子里装着苹果和橘子。每个盒子外面都贴有标签，但标签都是错的。你只能从一个盒子里拿出一个水果，如何判断每个盒子里装的是什么？答案：从贴有“苹果和橘子”标签的盒子里拿水果。如果拿出的是苹果，那么这个盒子实际装的是苹果；因为标签都错，所以贴“橘子”标签的盒子装的是苹果和橘子，贴“苹果”标签的盒子装的是橘子。如果拿出的是橘子，那么这个盒子实际装的是橘子；贴“苹果”标签的盒子装的是苹果和橘子，贴“橘子”标签的盒子装的是苹果。42.有五个人站成一排，他们的职业分别是医生、教师、律师、记者、厨师。已知：（1）医生站在教师的左边；（2）律师和记者相邻；（3）厨师在最右边；（4）医生和律师不相邻。请问五个人从左到右的职业顺序是什么？答案：从左到右依次是医生、教师、记者、律师、厨师。根据条件3确定厨师位置，再结合条件1确定医生和教师相对位置，由条件2确定记者和律师相邻，最后根据条件4确定完整顺序。43.有A、B、C、D四个人参加比赛，比赛结果有以下信息：（1）A不是第一名；（2）B不是第一名也不是最后一名；（3）C的名次在B之前；（4）D不是第二名。请问第一名是谁？答案：第一名是C。根据条件1排除A，条件2排除B，再结合条件3可知C在B前，条件4对确定第一名无直接影响，所以第一名是C。44.有三个开关分别控制三个灯泡，你只能进房间一次，如何确定哪个开关控制哪个灯泡？答案：先打开第一个开关，等几分钟后关闭；再打开第二个开关，然后进入房间。亮着的灯泡由第二个开关控制；用手摸一下另外两个不亮的灯泡，发热的由第一个开关控制，剩下的由第三个开关控制。45.有红、黄、蓝三个气球，分别被甲、乙、丙三人拿着。已知：（1）甲拿的不是红气球；（2）乙拿的不是黄气球；（3）丙拿的是蓝气球。请问甲、乙分别拿的什么颜色气球？答案：甲拿黄气球，乙拿红气球。由条件3确定丙拿蓝气球，再根据条件1可知甲拿黄气球，那么乙拿红气球。数据结构应用题46.设计一个数据结构，支持插入、删除和随机获取元素，且时间复杂度均为$O(1)$。```pythonimportrandomclassRandomizedSet:def__init__(self):self.nums=[]self.val_to_index={}definsert(self,val):ifvalinself.val_to_index:returnFalseself.val_to_index[val]=len(self.nums)self.nums.append(val)returnTruedefremove(self,val):ifvaln