北京经纬信息技术有限公司校招笔试题带答案

北京经纬信息技术有限公司校招笔试题带答案一、计算机基础（选择题，每题3分，共15分）1.以下数据结构中，适合用作缓存（需频繁插入、删除和随机访问）的是？A.链表B.数组C.哈希表D.二叉树答案：C解析：哈希表通过哈希函数将键映射到存储位置，插入、删除和随机访问的平均时间复杂度均为O(1)，适合缓存场景。链表和数组的随机访问效率较低，二叉树的操作复杂度不稳定。2.操作系统中，进程的状态不包括？A.运行态B.就绪态C.阻塞态D.等待态答案：D解析：进程的基本状态包括运行态（正在CPU执行）、就绪态（等待CPU调度）、阻塞态（等待I/O或资源）。“等待态”通常是阻塞态的别称，题目中D为干扰项。3.TCP三次握手过程中，第二次握手发送的标识位是？A.SYNB.ACKC.SYN+ACKD.FIN答案：C解析：第一次握手客户端发送SYN=1（请求连接）；第二次握手服务器回复SYN=1（确认连接请求）和ACK=1（确认客户端的SYN）；第三次握手客户端发送ACK=1（确认服务器的SYN），完成连接建立。4.以下排序算法中，时间复杂度稳定为O(nlogn)的是？A.快速排序B.冒泡排序C.归并排序D.选择排序答案：C解析：归并排序的时间复杂度不依赖数据分布，始终为O(nlogn)。快速排序在最坏情况下（如已排序数组）时间复杂度退化为O(n²)；冒泡排序和选择排序的平均时间复杂度为O(n²)。5.关于二叉树遍历，前序序列为ABC，后序序列为CBA，可能的中序序列是？A.ACBB.BACC.ABCD.CBA答案：B解析：前序遍历顺序为根左右，后序遍历为左右根。前序首元素A是根节点，后序末元素A也是根节点。前序中A之后是B，说明B是左子树的根；后序中A之前是CB，说明B的左子树是C。因此中序遍历顺序为左根右，即BAC。二、算法与编程（共40分）1.编写Python函数，输入一个单链表头节点，反转该链表，并返回反转后的头节点。要求时间复杂度O(n)，空间复杂度O(1)。（10分）答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.next保存下一个节点current.next=prev反转指针prev=current前指针后移current=next_node当前指针后移returnprev```解析：通过迭代法逐个反转节点指针。维护前一个节点（prev）和当前节点（current），每次将当前节点的next指向prev，逐步后移prev和current，最终prev即为反转后的头节点。2.给定一个整数数组nums和整数k，找出数组中和至少为k的最短非空子数组的长度。若不存在这样的子数组，返回-1。（15分）示例：nums=[2,-1,3],k=4，输出2（子数组[3,-1,2]和为4？不，正确示例应为nums=[1,2,3,-4,5],k=6，输出3（子数组[1,2,3]和为6，长度3）。答案：```pythondefshortest_subarray(nums,k:int)->int:n=len(nums)prefix=[0](n+1)foriinrange(n):prefix[i+1]=prefix[i]+nums[i]fromcollectionsimportdequeq=deque()res=float('inf')foriinrange(n+1):维护队列递增，确保可以用队首计算最小长度whileqandprefix[i]prefix[q[0]]>=k:res=min(res,iq.popleft())移除队列中比当前前缀和大的元素，保持单调递增whileqandprefix[i]<=prefix[q[-1]]:q.pop()q.append(i)returnresifres!=float('inf')else-1```解析：使用前缀和+双端队列优化。前缀和数组prefix[i]表示前i个元素的和。双端队列q保存递增的前缀和索引，对于每个i，若存在j∈q使得prefix[i]-prefix[j]≥k，则i-j为可能的子数组长度。通过维护队列的单调性，确保每次只需检查队首元素，时间复杂度O(n)。3.某铁路调度系统中，列车从A站到B站的路径由多个区间组成，每个区间有长度（公里）和限速（公里/小时）。列车在区间内必须按该区间限速行驶，区间之间切换时速度可立即调整。设计算法计算列车从A到B的最短行驶时间。（15分）示例：输入[(100,50),(200,100)]，输出4小时（100/50+200/100=2+2）。答案：```pythondefcalculate_min_time(intervals)->float:total_time=0.0forlength,speedinintervals:ifspeed<=0:raiseValueError("限速不能为0或负数")total_time+=length/speedreturntotal_time```解析：列车在每个区间内的行驶时间为长度除以限速，总时间为各区间时间之和。由于区间切换不耗时，且必须按区间限速行驶，因此总时间即为各区间时间的累加。三、数据库（共20分）1.简述数据库索引的作用及常见类型，说明聚集索引和非聚集索引的区别。（10分）答案：索引是数据库中优化查询效率的数据结构，通过快速定位记录位置减少全表扫描。常见类型包括B树索引（最常用，支持范围查询）、哈希索引（适合等值查询）、全文索引（用于文本搜索）等。聚集索引决定了表中数据的物理存储顺序，一个表只能有一个聚集索引（通常基于主键）；非聚集索引的逻辑顺序与物理存储顺序无关，一个表可创建多个非聚集索引。聚集索引查询时直接定位数据页，效率更高；非聚集索引需通过索引找到数据行的位置（如行指针或聚集索引键），可能需要二次查询。2.某铁路票务系统数据库有订单表orders（order_idINT主键，user_idINT，train_idVARCHAR(20)，order_timeDATETIME，statusTINYINT）。写出SQL查询：2023年10月期间，每个用户下单的高铁（train_id以'G'开头）订单数量，按数量降序排列，只显示数量≥5的用户。（10分）答案：```sqlSELECTuser_id,COUNT()ASorder_countFROMordersWHEREorder_timeBETWEEN'2023-10-0100:00:00'AND'2023-10-3123:59:59'ANDtrain_idLIKE'G%'-高铁车次以G开头ANDstatus=1-假设status=1表示有效订单（根据实际业务补充）GROUPBYuser_idHAVINGorder_count>=5ORDERBYorder_countDESC;```解析：通过WHERE子句过滤时间范围和高铁车次，GROUPBY按用户分组统计订单数，HAVING筛选数量≥5的用户，ORDERBY按数量降序排列。四、逻辑与行业知识（共25分）1.逻辑推理：某车站3个检票口，A口每分钟通过4人，B口5人，C口3人。8:00同时开放，8:10A口故障停用，8:15B口故障停用，8:20所有乘客检票完毕。乘客到达速率：8:00-8:10每分钟20人，8:10-8:15每分钟15人，8:15-8:20每分钟10人。问8:00时已有多少人等待检票？（10分）答案：设8:00时已有x人。8:00-8:10（10分钟）：到达20×10=200人，检票(4+5+3)×10=120人，剩余x+200-120=x+80。8:10-8:15（5分钟）：A停用，到达15×5=75人，检票(5+3)×5=40人，剩余x+80+75-40=x+115。8:15-8:20（5分钟）：B停用，到达10×5=50人，检票3×5=15人，剩余x+115+50-15=x+150。8:20时剩余0，故x+150=0→x=-150。注：负数表示系统在8:00前已提前处理了150人（或题目数据假设）。2.行业知识：简述铁路CTCS（中国列车运行控制系统）的等级划分及核心特点。（10分）答案：CTCS分为0-4级：CTCS-0：通用机车信号+监控装置，适用于普速铁路（≤160km/h）。CTCS-1：点式信息传输（应答器），实现地-车信息交互，适用于160-200km/h线路。CTCS-2：轨道电路+应答器+列控中心，控车精度提升，适用于200-250km/h客专。CTCS-3：GSM-R无线通信（车-地双向）+轨道电路，支持300-350km/h高铁，