信息技术竞赛测试题及答案

信息技术竞赛测试题及答案1.单选题（每题2分，共20分）1.1在IPv6地址2001:0db8:0000:0000:0000:ff00:0042:8329中，使用零压缩法可简写为A.2001:db8::ff00:42:8329B.2001:db8:0:0:ff:42:8329C.2001:db8::ff:9D.2001:db8:::ff00:42:8329答案：A解析：IPv6零压缩只能出现一次“::”，且必须省略连续的全0段。A项正确省略了中间5个0段。1.2某二叉树后序遍历为DABFC，中序遍历为ADBFC，则其先序遍历为A.CABDFB.CBADFC.ABDFCD.CBAFD答案：B解析：后序最后访问根，可知根为C；中序中C右侧无节点，故右子树空；左子树中序ADBF，后序DABF，递归可得先序CBADF。1.3在Linux中，将文件描述符3重定向到标准错误，应使用A.3>&2B.2>&3C.3<&2D.2<&3答案：A解析：>&表示复制描述符，3>&2把fd3指向fd2的当前目标，即标准错误。1.4若某时序数据库采用LSM-Tree，以下哪项操作最耗时A.顺序写MemTableB.磁盘flushC.合并SSTableD.布隆过滤器查询答案：C解析：合并SSTable需多路归并并清理过期数据，磁盘I/O与CPU开销最大。1.5在Python3中，表达式`[1,2]*3`的结果是A.[3,6]B.[1,2,1,2,1,2]C.[1,2,3]D.报错答案：B解析：列表乘号表示重复拼接，而非元素相乘。1.6使用Kruskal算法求最小生成树时，判断环需借助A.栈B.队列C.并查集D.拓扑排序答案：C解析：并查集可在近似O(α)时间内判断两顶点是否连通。1.7在HTTPS握手阶段，服务器发送的Certificate消息主要携带A.对称密钥B.证书链C.会话票据D.椭圆曲线参数答案：B解析：Certificate用于向客户端出示公钥证书链。1.8若CPU缓存行大小64B，数组元素double占8B，则步长为多少时最可能发生伪共享A.4B.8C.16D.32答案：B解析：同一缓存行可容纳8个double，若多线程以步长8访问相邻元素，则位于同一行。1.9SQL标准中，可重复读隔离级别下，不会出现A.脏读B.不可重复读C.幻读D.丢失更新答案：A解析：可重复读禁止脏读与不可重复读，但幻读仍可能出现。1.10在Git中，命令`gitreset--softHEAD~3`会A.丢弃最近3次提交且工作区回退B.保留工作区与暂存区，仅移动HEADC.删除最近3次提交记录且暂存区清空D.生成新分支答案：B解析：--soft仅移动HEAD指针，不改变索引与工作目录。2.多选题（每题3分，共15分，多选少选均不得分）2.1以下哪些HTTP头部可用来实现客户端缓存A.ETagB.Last-ModifiedC.ExpiresD.Set-Cookie答案：ABC解析：ETag与Last-Modified用于条件请求，Expires指定过期时间，Set-Cookie与会话相关。2.2关于RAID5，描述正确的有A.允许单盘故障B.写入需计算校验C.容量利用率(n-1)/nD.最少需4块盘答案：ABC解析：RAID5最少3块盘即可。2.3以下哪些属于稳定排序算法A.归并排序B.堆排序C.冒泡排序D.计数排序答案：ACD解析：堆排序不稳定。2.4在C语言中，关于`volatile`关键字，正确的有A.禁止编译器优化该变量B.保证原子性C.适用于访问硬件寄存器D.与并发安全无关答案：ACD解析：volatile不保证原子性，需配合锁或原子操作。2.5以下哪些设计模式可降低系统耦合A.观察者B.工厂方法C.单例D.适配器答案：ABD解析：单例主要控制实例数量，不直接降低耦合。3.填空题（每空2分，共20分）3.1若某无向图有n个顶点、e条边，使用邻接矩阵存储，空间复杂度为________。答案：O(n²)3.2在TCP首部中，用于流量控制的字段是________。答案：WindowSize3.3若某系统采用二级页表，页大小4KB，地址宽度48位，则页内偏移占________位。答案：123.4在MySQL8.0中，默认的认证插件为________。答案：caching_sha2_password3.5若某算法时间复杂度为T(n)=4T(n/2)+O(n²)，根据主定理，其复杂度为________。答案：O(n²logn)3.6在RSA加密中，若公钥指数e=3，则私钥指数d需满足3d≡1mod________。答案：φ(n)3.7在CSS中，选择器`.item:nth-child(2n+1)`匹配第________个子元素。答案：奇数3.8若某SSD的擦除单位大小为256KB，写入单位4KB，则写入放大系数最小理论值为________。答案：643.9在Python中，使用`with`语句管理资源时，对象需实现________方法。答案：`__enter__`与`__exit__`3.10在机器学习中，F1分数是精确率与召回率的________平均。答案：调和4.程序阅读题（每题5分，共15分）4.1阅读以下C++代码，写出输出结果：```cppinclude<iostream>template<intN>structFact{staticconstintval=N*Fact<N-1>::val;};template<>structFact<0>{staticconstintval=1;};intmain(){std::cout<<Fact<5>::val<<std::endl;}```答案：120解析：编译期递归计算阶乘，5!=120。4.2阅读以下Python代码，写出输出结果：```pythondeffoo(x=[]):x.append(1)returnxprint(foo(),foo(),sep='-')```答案：[1]-[1,1]解析：默认参数在函数定义时求值，列表x为可变对象，状态持续。4.3阅读以下SQL语句，写出查询结果（仅写出数字）：表T结构(idint,valint)，数据：(1,10),(2,20),(3,30)```sqlSELECTSUM(val)FILTER(WHEREid<=2)FROMT;```答案：30解析：PostgreSQL支持FILTER子句，仅对id≤2的行求和。5.编程填空题（每空3分，共15分）5.1补全快速排序的partition函数，使数组升序：```cppintpartition(inta[],intl,intr){intpivot=a[r],i=l;for(intj=l;j<r;++j){if(a[j]<pivot){std::swap(a[i],a[j]);________;}}std::swap(a[i],a[r]);returni;}```答案：`++i`5.2补全Python生成器，实现斐波那契无限序列：```pythondeffib():a,b=0,1whileTrue:yieldaa,b=b,________```答案：`a+b`5.3补全Java代码，使用双重检查锁定实现线程安全单例：```javaclassSingleton{privatestaticvolatileSingletoninst;privateSingleton(){}staticSingletonget(){if(inst==null){synchronized(Singleton.class){if(______)inst=newSingleton();}}returninst;}}```答案：`inst==null`5.4补全Go代码，实现并发安全计数器：```gotypeCounterstruct{musync.Mutexnint64}func(c*Counter)Inc(){c.mu.________c.n++c.mu.________}```答案：`Lock()`、`Unlock()`5.5补全SQL，将表user中name字段重复行保留id最大者：```sqlDELETEFROMuserWHEREidNOTIN(SELECT________FROMuserGROUPBYname);```答案：`MAX(id)`6.算法设计题（共30分）6.1（10分）给定长度为n的整数数组，求最长严格递增子序列长度。n≤10⁵，元素范围[-10⁹,10⁹]。要求：写出核心算法思路、伪代码、时间复杂度。答案：思路：使用patiencesorting优化，维护tails数组，tails[i]记录长度为i+1的LIS最小末尾。伪代码：```tails=[]forxinarr:idx=lower_bound(tails,x)#首个≥x的位置ifidx==len(tails):tails.append(x)else:tails[idx]=xreturnlen(tails)```时间复杂度：O(nlogn)6.2（10分）设计分布式限流器，支持每秒百万级请求，多节点共享配额。要求：说明数据结构与一致性方案，给出伪代码。答案：采用令牌桶+Redis+Lua脚本。结构：key格式`bucket:{api}`，字段`tokens`剩余令牌数，`last_refill`上次填充时间。Lua脚本原子执行：```localrate=tonumber(ARGV[1])localburst=tonumber(ARGV[2])localnow=tonumber(ARGV[3])localkey=KEYS[1]localbucket=redis.call('HMGET',key,'tokens','last')localtokens=tonumber(bucket[1])orburstlocallast=tonumber(bucket[2])ornowlocaldelta=math.min((nowlast)*rate,bursttokens)tokens=tokens+deltalocalallowed=tokens>=1ifallowedthentokens=tokens1endredis.call('HMSET',key,'tokens',tokens,'last',now)returnallowed```一致性：Redis单线程执行Lua，保证原子性；多节点共享配额。6.3（10分）给定10亿个URL，每个64B，内存限制1GB，去重并统计出现次数前100的URL。要求：给出外部排序+哈希+堆的完整流程，计算I/O次数。答案：步骤：1.顺序读取文件，按hash(url)%2000分桶写入2000个临时文件，每文件约50MB，内存占用<500MB。2.对每个小文件，使用哈希表去重并统计频次，写入<(url,count)>有序中间文件。3.多路归并中间文件，同时维护100大小的小顶堆，保留全局Top100。I/O：分桶阶段：读10GB，写10GB归并阶段：读10GB，写0（仅输出Top100）总I/O≈30GB，机械盘约5分钟。7.系统综合题（共20分）7.1（10分）某微服务集群高峰期出现“部分接口超时但CPU利用率低”现象，给出排查清单与工具。答案：清单：1.网络延迟：tcpdump+Wireshark抓包，查看RTT与重传。2.连接池耗尽：监控连接池active/idle，使用netstat-ant|grepESTABLISHED。3.线程池饥饿：jstack查看WAITING线程，Arthasthread命令。4.GC停顿：jstat–gc查看FullGC次数与时间，GC日志分析。5.数据库慢查询：开启slow_query_log，pt-query-digest分析。6.锁竞争：MySQL的performance_schema或Redis的SLOWLOG。7.磁盘I/O：iostat-x1查看%util与await。8.容器限流：检查Kubernetes的CPUthrottle，cat/sys/fs/cgroup/…/cpu.stat。7.2（10分）设计一个可水平扩展的IM消息系统，支持单聊、群聊、已读回执，日活1亿，峰值QPS500万。要求：画出核心架构图，说明消息可靠投递、顺序、存储选型。答案：架构：接入层：多地域WebSocket集群，基于Netty，无状态，支持水平扩展。路由层：一致性哈希按uid分片，维护用户→网关映射，使用RedisCluster存储在线状态。消息队列：Kafka分区按会话id