2025年数据与计算考试题及答案

2025年数据与计算考试题及答案一、单项选择题（每题2分，共20分）1.已知某算法的时间复杂度函数为T(n)=2n²+3nlog₂n+5n+7，其渐进时间复杂度为（）。A.O(n²)B.O(nlogn)C.O(n)D.O(n³)2.关系数据库中，若一个关系模式R的所有非主属性都完全函数依赖于任意一个候选码，则R至少满足（）。A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.BC范式（BCNF）3.在Hadoop生态中，负责资源管理和任务调度的核心组件是（）。A.HDFSB.MapReduceC.YARND.HBase4.对于长度为n的有序数组，使用二分查找的平均时间复杂度为（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n²)5.分布式系统中，CAP理论指的是（）三者无法同时满足。A.一致性、可用性、分区容错性B.一致性、原子性、持久性C.可扩展性、可用性、容错性D.完整性、原子性、分区容错性6.某哈希表采用链地址法处理冲突，哈希函数为H(key)=keymod7。若依次插入键值对(15,A)、(22,B)、(30,C)、(9,D)，则哈希表中索引为1的链表长度为（）。A.1B.2C.3D.47.以下不属于NoSQL数据库特点的是（）。A.支持ACID特性B.灵活的模式设计C.水平扩展能力D.非关系型数据模型8.若某二叉树的前序遍历序列为ABDCE，中序遍历序列为BADCE，则其后序遍历序列为（）。A.BDECAB.BDAECC.BEDCAD.BDCEA9.在Spark中，RDD（弹性分布式数据集）的主要特性是（）。A.不可变、可分区、支持持久化B.可变、全局共享、实时计算C.内存存储、不可分区、单节点处理D.实时更新、高一致性、低延迟10.对于事务的隔离级别，“读未提交”会导致的主要问题是（）。A.脏读B.不可重复读C.幻读D.丢失更新二、填空题（每空2分，共20分）1.数据结构中，栈的基本操作包括入栈、出栈和__________。2.关系代数中，投影操作的符号是__________（用希腊字母表示）。3.HBase的表由行键、列族、时间戳和__________组成。4.快速排序的平均时间复杂度为__________，最坏时间复杂度为__________。5.分布式系统中，Paxos算法用于解决__________问题。6.机器学习中，监督学习与无监督学习的主要区别在于是否有__________。7.数据库索引分为聚簇索引和__________索引，其中__________索引会改变数据的物理存储顺序。8.在MapReduce编程模型中，Map阶段输出的键值对会经过__________过程，按键分组后传递给Reduce阶段。三、简答题（每题8分，共40分）1.简述B树与B+树的主要区别，并说明B+树在数据库索引中的优势。2.什么是数据库的事务？简述事务的ACID特性及其含义。3.对比HDFS（Hadoop分布式文件系统）与传统文件系统的差异，说明HDFS适合处理的场景。4.解释机器学习中的过拟合现象，并列举至少3种缓解过拟合的方法。5.简述分布式计算中“数据局部性”原则的含义，以及SparkRDD如何利用该原则优化计算效率。四、计算题（每题10分，共30分）1.对数组[5,3,8,1,6,2,7,4]进行快速排序（选择首元素为枢轴），写出每一趟排序后的数组状态，并计算总的比较次数（仅统计元素间的直接比较）。2.某关系数据库中有如下关系模式：学生（学号Sno，姓名Sname，年龄Sage，所在系Sdept）课程（课程号Cno，课程名Cname，学分Credit）选课（Sno，Cno，成绩Grade）用关系代数表达式表示以下查询：（1）查询选修了课程号为“C01”且成绩高于85分的学生的学号和姓名；（2）查询所有年龄小于20岁且所在系为“计算机系”的学生的姓名和所选课程的课程名。3.假设某分布式系统中有5个节点，采用Paxos算法达成共识。当前提案编号为n=10，值为v=X。节点A（提议者）向节点B、C、D、E（接受者）发送Prepare请求，其中节点B、C、D响应了Promise（n=10，最大已接受编号为9，值为Y），节点E未响应。此时节点A需要如何处理？若后续节点B、C、D接受了编号为10、值为X的提案，节点E在恢复后应如何同步状态？五、综合题（20分）某电商平台需构建用户行为分析系统，要求实时采集用户浏览、点击、加购、下单等行为数据（日均数据量约500TB），支持秒级查询“最近1小时各商品分类的点击量”和离线分析“用户购买路径转化漏斗”。请设计系统架构，说明关键组件及各组件的作用，并分析需要考虑的性能优化点。答案一、单项选择题1.A2.B3.C4.C5.A6.B7.A8.A9.A10.A二、填空题1.取栈顶元素（或查看栈顶）2.π3.单元格值（或值）4.O(nlogn)、O(n²)5.分布式一致性6.标签（或目标变量）7.非聚簇（或辅助）、聚簇8.洗牌（Shuffle）三、简答题1.主要区别：B树的每个节点存储键和值，所有节点均可能存储数据；B+树的内部节点仅存储键，数据仅存储在叶子节点，且叶子节点通过指针连接成有序链表。优势：B+树的叶子节点包含所有数据并有序，适合范围查询（可通过链表顺序扫描）；内部节点无数据存储，可容纳更多键，减少I/O次数；更适合数据库索引的频繁查询场景。2.事务是数据库中不可分割的最小操作单元。ACID特性：原子性（Atomicity），事务内操作要么全做要么全不做；一致性（Consistency），事务执行前后数据库状态保持一致；隔离性（Isolation），事务间执行互不干扰；持久性（Durability），事务提交后修改永久保存。3.差异：HDFS是分布式文件系统，支持海量数据存储，采用主从架构（NameNode+DataNode），文件分块存储（默认128MB），适合一次写入多次读取；传统文件系统（如NTFS、EXT4）是单机或局域网文件系统，存储容量较小，支持频繁修改。适合场景：海量数据的批量处理（如日志分析、大数据计算），不适合小文件或频繁随机读写。4.过拟合指模型在训练数据上表现良好，但在新数据上泛化能力差。缓解方法：增加训练数据量；正则化（L1/L2正则）；早停（EarlyStopping）；特征选择（减少冗余特征）；使用更简单的模型（降低模型复杂度）。5.数据局部性原则指计算应尽可能靠近数据存储位置，以减少数据传输开销。SparkRDD通过分区（Partition）将数据分布在集群各节点，计算任务（Task）被发送到数据所在节点执行（本地化调度）；RDD的持久化（Cache/Persist）可将常用数据缓存到内存或磁盘，避免重复计算；血缘（Lineage）机制记录数据提供路径，故障时仅需重算相关分区，减少数据传输。四、计算题1.快速排序过程（首元素5为枢轴）：第一趟：分区后数组为[3,1,2,4,5,6,7,8]，比较次数：7次（5与3、8、1、6、2、7、4比较）。第二趟：左子数组[3,1,2,4]（枢轴3），分区后[1,2,3,4]，比较次数：3次（3与1、2、4比较）；右子数组[6,7,8]（枢轴6），分区后[6,7,8]，比较次数：2次（6与7、8比较）。第三趟：左子数组[1,2]（枢轴1），分区后[1,2]，比较次数：1次（1与2比较）；右子数组无。总比较次数：7+3+2+1=13次。2.（1）πSno,Sname(σCno='C01'∧Grade>85(选课⋈学生))（2）πSname,Cname(σSage<20∧Sdept='计算机系'(学生⋈选课⋈课程))3.节点A收到B、C、D的Promise响应（最大已接受编号9<10），因此可以提出编号10的提案，值为X（若响应中存在已接受的值，需选择最大编号对应的值，此处无冲突，故保持X）。节点A向B、C、D发送Accept请求，若多数（≥3）接受，则提案通过。节点E恢复后，需通过Learn阶段获取已达成共识的提案（n=10，v=X），更新自身状态。五、综合题系统架构设计：1.数据采集层：使用Flume或KafkaConnect实时采集用户行为数据，通过Kafka消息队列缓冲（解决生产与消费速率不匹配问题，支持高吞吐量）。2.实时处理层：采用SparkStreaming或Flink处理实时数据，按商品分类聚合最近1小时点击量，结果写入Redis（内存数据库，支持秒级查询）。3.离线存储层：Kafka数据同步至HDFS（长期存储）和HBase（列式存储，支持快速随机访问）；使用Hive构建数据仓库，存储清洗后的结构化数据。4.离线分析层：通过Spark或MapReduce处理Hive数据，计算用户购买路径转化漏斗，结果存储至MySQL或ClickHouse（支持复杂查询）。5.查询服务层：提供API接口，实时查询调用Redis数据，离线分析结果通过可视化工具（如T