CCF笔试试题及详细答案分析

CCF笔试试题及详细答案分析考试时间：______分钟总分：______分姓名：______一、请编写一个函数，实现判断一个给定的非负整数`n`是否是2的幂。如果是，返回`True`；否则，返回`False`。要求在不使用除法、位移运算符的情况下完成。二、给定一个由小写字母组成的字符串`s`。请编写一个函数，找到字符串中第一个只出现一次的字符，并返回它的索引。如果不存在这样的字符，返回`-1`。三、请编写一个函数，实现将一个非空的整数链表反转。链表节点定义如下：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next```函数应返回反转后的链表的头节点。四、假设你正在使用一个栈来模拟一个简单的文本编辑器的撤销操作。栈中存储的是每次编辑操作前文本的状态（可以用字符串表示）。每次用户输入一个字符，就将其压入栈；如果用户按下撤销键（假设用字符'u'表示），则弹出栈顶元素（模拟撤销上一步操作，栈顶元素是上一步操作前的状态），并恢复到该状态。请编写一个函数，处理一系列由字符组成的操作序列（操作序列以空格分隔），并返回最终文本的状态以及执行过程中栈的最大深度。函数输入为一个字符串`ops`，表示操作序列，例如`"abcudu"`。函数输出为一个元组`(final_text,max_stack_depth)`。五、给定一个包含`m`行`n`列的整数矩阵`matrix`，以及一个目标值`target`。请编写一个函数，判断`target`是否存在于该矩阵中。该矩阵按照每行从左到右、每列从上到下递增的顺序排列。六、请编写一个函数，计算一个正整数`n`的阶乘`n!`的值。要求使用递归方法实现。七、请编写一个函数，接受两个正整数`m`和`n`，返回它们的最小公倍数（LeastCommonMultiple,LCM）。你可以假设`m`和`n`都大于0。八、请实现一个简单的字符串压缩算法。输入一个由字母和数字组成的非空字符串`s`，将连续的相同字符视作一个组，返回压缩后的字符串。如果压缩后的字符串不比原字符串短，则返回原字符串。例如，`"aabcccaaa"`压缩后为`"a2b1c3a3"`。九、请编写一个函数，实现删除排序数组中的重复项。给定一个排序数组`nums`，你需要在原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的长度。函数还需要返回删除后的数组（可以通过修改输入数组或返回新数组实现，但需明确说明）。例如，输入`nums=[0,0,1,1,1,2,2,3,3,4]`，函数应返回长度`5`，且`nums`的前`5`个元素为`[0,1,2,3,4]`。试卷答案一、```pythondefis_power_of_two(n):ifn==0:returnFalsewhilen>1:ifn%2!=0:returnFalsen//=2returnTrue#解析：通过循环不断除以2，判断是否能整除。如果是2的幂，最终会变为1。0不是2的幂。```二、```pythondeffirst_unique_char(s):count={}forcharins:ifcharincount:count[char]+=1else:count[char]=1forindex,charinenumerate(s):ifcount[char]==1:returnindexreturn-1#解析：使用字典统计每个字符的出现次数，然后遍历字符串，返回第一个出现次数为1的字符的索引。```三、```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev#解析：使用三个指针prev,current,next_node，逐个节点反转链表方向。```四、```pythondefprocess_editor_operations(ops):stack=[]max_depth=0current_text=[]ops_list=ops.split()foropinops_list:ifop!='u':stack.append(''.join(current_text))current_text.append(op)max_depth=max(max_depth,len(stack))else:ifstack:current_text=list(stack.pop())final_text=''.join(current_text)return(final_text,max_depth)#解析：使用栈模拟撤销操作。遇到字符则压栈并添加到当前文本，遇到'u'则弹栈恢复当前文本，同时记录栈的最大深度。```五、```pythondefsearch_matrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalsem,n=len(matrix),len(matrix[0])row,col=0,n-1whilerow<mandcol>=0:ifmatrix[row][col]==target:returnTrueelifmatrix[row][col]>target:col-=1else:row+=1returnFalse#解析：从矩阵右上角开始查找。如果当前元素等于目标，返回True。大于目标则向左移动，小于目标则向下移动。```六、```pythondeffactorial(n):ifn==0orn==1:return1returnn*factorial(n-1)#解析：递归实现阶乘，基本情况是0!和1!都等于1，递归步骤是n!=n*(n-1)!。```七、```pythondefgcd(a,b):whileb:a,b=b,a%breturnadeflcm(m,n):returnm*n//gcd(m,n)#解析：先计算最大公约数(GCD)，然后利用公式LCM(m,n)=(m*n)/GCD(m,n)计算最小公倍数。```八、```pythondefcompress_string(s):ifnots:returnscompressed=[]count=1foriinrange(1,len(s)):ifs[i]==s[i-1]:count+=1else:compressed.append(s[i-1])ifcount>1:compressed.append(str(count))count=1compressed.append(s[-1])ifcount>1:compressed.append(str(count))return''.join(compressed)iflen(compressed)<len(s)elses#解析：遍历字符串，统计连续相同字符的个数。每组字符后添加字符本身，如果计数大于1则添加计数。最后比较压缩后长度与原长度。```九、```pythondefremove_duplicates(nums):ifnotnums: