2025年计算机科学基础概念测试题及答案

2025年计算机科学基础概念测试题及答案一、单项选择题（每题2分，共20分）1.以下关于算法时间复杂度的描述中，正确的是：A.时间复杂度为O(n²)的算法一定比O(nlogn)的算法慢B.同一个算法的时间复杂度与具体输入数据无关C.递归算法的时间复杂度可通过主定理（MasterTheorem）分析D.空间复杂度为O(1)的算法一定不使用任何额外内存2.操作系统中，CFS（完全公平调度）算法的核心调度单位是：A.进程的优先级数值B.进程的虚拟运行时间C.进程的剩余执行时间D.进程的内存占用量3.在TCP/IP协议栈中，QUIC协议主要运行在：A.应用层B.传输层C.网络层D.数据链路层4.数据库系统中，“脏读”现象主要违反了事务的哪一特性？A.原子性（Atomicity）B.一致性（Consistency）C.隔离性（Isolation）D.持久性（Durability）5.编译过程中，语法分析阶段的主要输入是：A.源程序字符流B.词法分析提供的记号流C.中间代码D.目标代码6.计算机组成原理中，基址寻址方式的关键寄存器是：A.指令寄存器（IR）B.基址寄存器（BR）C.程序计数器（PC）D.累加寄存器（AC）7.哈希表中，采用开放定址法处理冲突时，若当前位置被占用，下一个探测位置的计算不包括：A.线性探测（i+1,i+2,…）B.二次探测（i+1²,i-1²,i+2²,…）C.双重哈希（h1(key),h2(key),…）D.链地址法（链表存储冲突元素）8.以下排序算法中，属于稳定排序的是：A.快速排序B.堆排序C.归并排序D.希尔排序9.虚拟内存管理中，页表项的基本组成不包括：A.有效位（ValidBit）B.修改位（DirtyBit）C.访问位（ReferenceBit）D.优先级位（PriorityBit）10.计算机网络中，OSPF协议属于：A.距离向量路由协议B.链路状态路由协议C.路径向量路由协议D.洪泛路由协议二、填空题（每空2分，共20分）1.跳表（SkipList）的平均查找时间复杂度为__________，最坏情况为__________。2.TCP三次握手中，第二次握手的报文中需设置的标志位是__________和__________。3.虚拟内存的理论基础是__________，其核心是利用__________实现小内存运行大程序。4.一棵度为m的B树中，每个节点最多包含__________个关键字，最少包含__________个关键字（根节点除外）。5.数据库索引按存储结构可分为__________索引（如B+树）和__________索引（如哈希索引）。三、简答题（每题8分，共40分）1.比较归并排序与快速排序的核心思想、时间复杂度（最好/最坏/平均）及适用场景。2.简述虚拟内存的作用及其实现的关键技术（至少列出3项）。3.说明TCP拥塞控制的四个阶段及其主要机制。4.解释B+树与B树在数据库索引中的差异，并说明B+树更适合索引的原因。5.描述操作系统中进程与线程的区别（从资源分配、调度、并发性、通信方式四方面展开）。四、计算题（每题10分，共20分）1.某递归算法的时间复杂度满足递推关系式：T(n)=2T(n/2)+nlogn（n≥2），T(1)=1。使用主定理（MasterTheorem）计算其时间复杂度，并写出推导过程。2.给定IP地址192.168.1.0/24，需划分6个子网，每个子网至少支持30台主机。要求：（1）计算子网掩码；（2）列出前3个子网的网络地址和可用主机地址范围。五、综合分析题（20分）设计一个分布式系统的缓存策略，需考虑以下需求：高并发读、数据一致性、缓存失效机制、内存淘汰策略。要求：（1）选择缓存中间件（如Redis）；（2）说明一致性保证的具体方法；（3）设计失效机制（如主动失效与被动失效结合）；（4）选择内存淘汰算法并说明理由；（5）分析可能出现的缓存穿透、击穿问题及解决措施。答案一、单项选择题1.C2.B3.B4.C5.B6.B7.D8.C9.D10.B二、填空题1.O(logn)；O(n)2.SYN；ACK3.局部性原理；外存（磁盘）4.m-1；⌈m/2⌉-1（或m/2向下取整-1）5.聚簇（或顺序）；非聚簇（或哈希）三、简答题1.归并排序核心思想：分治+合并，将数组递归拆分为子数组，排序后合并。时间复杂度：最好/平均/最坏均为O(nlogn)，空间复杂度O(n)，稳定排序，适合外排序。快速排序核心思想：分治+枢轴划分，选择枢轴将数组分为两部分递归排序。时间复杂度：平均O(nlogn)，最坏（已排序或逆序）O(n²)，空间复杂度O(logn)（栈空间），不稳定排序，适合内存排序。适用场景：归并排序适合需要稳定性或外存排序；快速排序适合通用内存排序，平均性能更优。2.虚拟内存作用：扩展物理内存，允许程序使用比物理内存更大的地址空间；隔离进程地址空间，提高安全性；支持多道程序并发。关键技术：页表（映射虚拟地址到物理地址）、页面置换算法（如LRU、FIFO）、请求调页（仅在需要时加载页面）、交换空间（磁盘中存储换出页面）。3.TCP拥塞控制四阶段：（1）慢启动：初始拥塞窗口（cwnd）指数增长（cwnd=1,2,4…），直到达到慢启动阈值（ssthresh）；（2）拥塞避免：cwnd线性增长（每次ACK增加1/cwnd），直到检测到拥塞；（3）快速重传：收到3个重复ACK时，认为丢包，执行快速重传（立即重传丢失报文）；（4）快速恢复：ssthresh设为cwnd/2，cwnd设为ssthresh+3（因收到3个重复ACK），之后线性增长，避免进入慢启动。4.B+树与B树差异：B+树所有关键字存储在叶子节点，非叶子节点仅作索引；B树关键字分布在所有节点。B+树叶子节点通过指针链接成有序链表；B树无此结构。B+树更适合索引的原因：（1）叶子节点存储所有数据，查询效率稳定（必须到叶子节点）；（2）链表结构支持范围查询（如SQL的BETWEEN）；（3）非叶子节点无数据，可存储更多索引项，减少磁盘IO次数。5.进程与线程区别：（1）资源分配：进程是资源分配的基本单位（拥有独立内存、文件等）；线程是调度的基本单位（共享进程资源）。（2）调度：进程切换需切换页表、上下文，开销大；线程切换仅需切换寄存器、栈，开销小。（3）并发性：一个进程内的多线程可并发执行，提高CPU利用率；多进程并发需跨进程通信。（4）通信方式：进程间通过管道、消息队列、共享内存等；线程间通过共享内存直接通信（需同步机制）。四、计算题1.主定理形式：T(n)=aT(n/b)+f(n)，其中a=2，b=2，f(n)=nlogn。计算n^(log_ba)=n^(log_22)=n^1=n。比较f(n)与n^(log_ba)的关系：f(n)=nlogn=nlogn，属于n^(log_ba)log^kn（k=1）。根据主定理情况2，若f(n)=Θ(n^(log_ba)log^kn)（k≥0），则T(n)=Θ(n^(log_ba)log^(k+1)n)。因此，T(n)=Θ(nlog²n)。2.（1）子网划分：需6个子网，2^3=8≥6，故借用3位主机位作为子网位。原掩码/24（255.255.255.0），新掩码为/24+3=/27（255.255.255.224）。每个子网主机位为5位（32-27=5），可用主机数=2^5-2=30（满足需求）。（2）前3个子网：子网1：网络地址192.168.1.0/27，可用主机192.168.1.1~192.168.1.30；子网2：网络地址192.168.1.32/27，可用主机192.168.1.33~192.168.1.62；子网3：网络地址192.168.1.64/27，可用主机192.168.1.65~192.168.1.94。五、综合分析题（1）缓存中间件选择Redis：支持丰富数据结构（如字符串、哈希、列表）、持久化（RDB/AOF）、分布式集群（RedisCluster），适合高并发场景。（2）一致性保证：采用“写数据库+删缓存”策略（先写数据库，成功后删除缓存），避免脏数据。对于强一致性场景，使用分布式锁（如RedLock）保证写操作互斥；或结合消息队列（如Kafka）异步更新缓存，确保最终一致。（3）失效机制：主动失效（设置TTL，如热点数据TTL=5分钟，非热点=30分钟）+被动失效（业务逻辑中检测数据变更时主动删除缓存）。（4）内存淘汰算法：选择LRU（最近最少使用）或其优化版（如Redis的近似LRU）。理由：高并发读场景中，LRU能有效保留最近访问的数据，减少缓存