2025年北京航空航天大学计算机科学与技术（空天计算）专业入学考试试题

2025年北京航空航天大学计算机科学与技术（空天计算）专业入学考试试题考试时间：______分钟总分：______分姓名：______一、请简述数据结构中“平衡”的含义，并说明以AVL树或红黑树为代表的平衡二叉搜索树在处理大规模有序数据时相比普通二叉搜索树有哪些优势。二、在一个嵌入式实时系统中，假设系统共有5个实时任务T1,T2,T3,T4,T5，它们的优先级分别为P1>P2>P3>P4>P5，且优先级高的任务总是抢占优先级低的任务执行。当前时刻任务T1和T2正在运行，T1的剩余执行时间为10ms，T2的剩余执行时间为5ms。若此时高优先级任务T3请求运行，请画出在优先级调度策略下，从T3请求运行到T1、T2执行完毕的时间段内的任务切换示意图（用任务名和运行时间段表示），并计算在此期间T3的最大可能执行时间。三、计算机内存系统通常采用多级Cache（如L1,L2,L3Cache）结构。请解释多级Cache的设计目标，并说明当CPU访问一个未命中L1Cache但命中的L2Cache的数据时，数据最终如何被加载到L1Cache中（请描述涉及的关键部件和基本流程）。四、简述TCP协议中用于保证数据传输可靠性的主要机制，并解释这三个机制是如何协同工作的。在卫星通信等存在显著传输延迟和潜在丢包的网络环境中，这些机制可能会遇到哪些挑战？五、在处理航天任务产生的海量、多源异构数据时，数据库系统可能面临哪些特有的挑战？请列举至少三种挑战，并分别说明一种可能的应对策略。六、考虑一个需要同时处理多个传感器数据的航天器系统，这些数据具有不同的实时性要求（例如，某些数据需要秒级处理，而另一些则需要毫秒级处理）。请简述如何设计该系统的软件架构（或任务调度策略），以满足不同数据的实时处理需求，并说明需要考虑的关键因素。七、请解释“指令流水线（InstructionPipeline）”的基本原理，并说明它在提高CPU运算速度方面的作用。简述流水线执行过程中可能出现的“数据冒险”、“结构冒险”和“控制冒险”这三种主要风险，并分别提出一种常用的处理方法。八、什么是“实时操作系统（RTOS）”？它与通用操作系统（如Linux、Windows）在设计和目标上有哪些主要区别？请结合航天器任务调度的实际需求，说明RTOS在支持航天任务执行方面的重要作用。九、请描述信息安全领域中“对称加密”和“非对称加密”两种基本加密方式的工作原理，并简要说明它们各自的主要应用场景。在保障航天指挥控制系统信息安全方面，这两种加密方式可能如何协同使用？十、假设你需要设计一个用于模拟卫星轨道计算的程序。请说明在设计该程序时，除了需要考虑的数学模型（如开普勒定律）之外，还需要考虑哪些与计算机科学/技术相关的因素，并简要阐述这些因素的重要性。试卷答案一、平衡的含义是指树在任意节点处，其左子树和右子树的深度之差（平衡因子）的绝对值不超过1。这确保了树的高度大致为log(n)，从而使得在平衡二叉搜索树中插入、删除和查找元素的操作时间复杂度均可达到O(logn)。相比普通二叉搜索树，平衡二叉搜索树能够避免因树形倾斜导致的操作效率急剧下降（最坏情况为O(n)），在处理大规模有序数据时能保持较高的性能和稳定性。二、任务切换示意图如下：```[0-5ms]:T2(运行)[5-10ms]:T1(运行)[10ms]:T3请求运行->T3等待[10-15ms]:T1(运行)[15ms]:T2请求运行->T2等待[15-20ms]:T1(运行)[20ms]:T1执行完毕->T3抢占运行[20-...ms]:T3(运行)```在此时间段内，T3的最大可能执行时间为20ms。计算过程：T1和T2分别在0-10ms和5-10ms运行完毕，T3在10ms请求运行并等待。此后T1继续运行10ms（15ms时完毕），T3再次抢占运行。因此，T3最早在T1执行完毕时（20ms）开始运行，若无其他更高优先级任务干扰，其最大可能执行时间即从20ms开始持续。三、多级Cache的设计目标是提高内存访问速度，降低CPU缓存未命中的平均等待时间，同时平衡成本和容量。当CPU访问未命中L1Cache但命中L2Cache的数据时，流程如下：CPU向L2Cache发出请求；L2Cache查找数据，若命中则直接将数据通过内部总线传送给CPU；若L2Cache未命中（虽然本题假设L2命中），则L2Cache会向下一级Cache（如L3）或主内存（RAM）发起请求；数据从L3或RAM被加载到L2Cache中，同时L2Cache将该数据传送给CPU。在此过程中，涉及的关键部件包括CPU缓存控制器、L1/L2/L3Cache存储单元、内部总线、可能还有内存控制器。基本流程是：CPU发起请求->L1/L2查找->若未命中则向下一级查找/主内存读取->数据逐级回填至L1。四、TCP协议保证数据传输可靠性的主要机制有三：1）序列号与确认应答（ACK）：发送方为每个TCP段编号，接收方对收到的每个段发送ACK确认，确认号指明期望接收的下一个序列号。2）超时重传：发送方在发送段后启动计时器，若超时未收到ACK，则假定段丢失并重传。接收方不发送重复的ACK。3）数据校验：TCP头部包含校验和字段，用于检测数据在传输过程中是否发生错误。这三个机制协同工作：发送方通过序列号确保数据按序到达且无丢失，通过ACK和重传确保数据最终可靠到达，通过校验和确保数据完整性。在卫星通信环境中，显著的传输延迟（高RTT）会导致重传延迟增大，窗口大小受限影响吞吐量；潜在的高丢包率会增加重传次数，进一步恶化性能；ACK的频繁发送也可能占用过多带宽。五、处理航天海量、多源异构数据的数据库系统挑战及策略：1.挑战：数据量巨大（海量）->数据存储、I/O压力大。策略：采用分布式数据库架构、列式存储引擎、大规模并行处理（MPP）技术。2.挑战：数据来源多样（多源异构）->数据格式不统一，集成难度大。策略：使用数据湖或数据仓库技术，结合ETL（抽取、转换、加载）过程进行数据清洗和标准化，支持半结构化和非结构化数据。3.挑战：实时性要求高->需要快速处理和响应传感器数据。策略：引入流处理引擎（如Kafka,Flink），构建实时数据索引，优化查询性能，可能采用内存数据库。4.挑战：数据类型复杂->包括数值、文本、图像、时序等，处理方式各异。策略：采用多模态数据库或支持混合数据类型的数据库（如NoSQL数据库），进行数据分区和分片。六、设计满足不同实时性要求的航天器系统软件架构，可考虑以下策略：1.分层/分区架构：将系统功能按实时性需求划分为不同层级或区域，高实时性任务（如姿态控制）运行在独立的实时内核或高优先级分区，非实时任务（如科学数据处理）运行在后台。2.优先级调度：采用实时操作系统（RTOS）或带优先级调度的机制，确保高优先级任务能够及时获得CPU时间。3.独立任务设计：为关键传感器数据处理或控制任务设计独立的、资源隔离的任务模块。4.资源预留：为高实时性任务预留必要的CPU时间片、内存带宽和处理能力。需要考虑的关键因素包括任务优先级定义、任务间通信与同步机制、CPU和内存资源限制、任务调度算法的公平性与效率、系统容错能力等。七、指令流水线的基本原理是将CPU的指令执行过程分解为多个阶段（如取指IF、译码ID、执行EX、访存MEM、写回WB），并行地处理多条指令的不同阶段。这提高了CPU的吞吐率（单位时间内完成的指令数），但并未提高单条指令的执行速度，且引入了流水线冲突（数据冒险、结构冒险、控制冒险）问题。数据冒险是指后一条指令需要使用前一条指令尚未计算完成的结果；结构冒险是指硬件资源冲突，如只有一个内存端口；控制冒险是指由于分支指令不确定是否执行以及执行哪个目标地址，导致后续指令送入流水线后可能需要被冲刷（flush）。常用的处理方法：数据冒险有数据前递（Forwarding）、指令暂停（Stalling/Bubble）；结构冒险通过增加硬件资源或采用二级流水线；控制冒险有分支预测（BranchPrediction）、延迟分支（DelayedBranch）、分支目标缓冲（BTB）。八、实时操作系统（RTOS）是为实时应用设计的操作系统，其关键特征是能够保证在确定或可预测的时间限制内对外部事件做出响应（满足实时性要求）。它与通用操作系统的主要区别在于：1）调度策略：强调确定性和优先级，常用抢占式、速率单调（RMS）等实时调度算法，而非通用操作系统的多任务共享和公平性考虑。2）内核开销：尽可能小，以保证任务切换快速、响应及时。3）中断处理：快速响应中断，并有明确的优先级规则。4）资源管理：提供任务间同步互斥机制（如信号量、互斥锁），保证资源访问的确定性。RTOS在支持航天任务执行方面至关重要，因为航天任务（如轨道修正、姿态控制、测控指令响应）通常具有严格的截止时间要求，RTOS的确定性保证了任务能够按时完成，是航天器可靠运行的基础。九、对称加密（SecretKeyCryptography）使用同一个密钥进行数据的加密和解密。工作原理：发送方用密钥E(key,data)加密明文data得到密文，接收方用相同的密钥D(key,cipher-text)解密密文得到明文。优点是计算效率高，速度快。主要应用场景：大量数据加密（如文件传输、数据库存储）、需要快速加密解密的场景。非对称加密（PublicKeyCryptography）使用一对密钥：公钥（可公开分发）和私钥（秘密保存）。工作原理：用公钥E(public_key,data)加密数据，只能用对应的私钥D(private_key,cipher-text)解密；反之，用私钥E(private_key,data)签名，只能用对应的公钥D(public_key,signature)验证。优点是解决了密钥分发问题，可用于数字签名和身份认证。主要应用场景：安全信道建立（SSL/TLS）、数字签名、身份认证。在保障航天指挥控制系统信息安全方面，可协同使用：用对称密钥加密传输的大量指令或数据，以提高效率；用非对称密钥（如公钥）加密对称密钥本身，或用于数字签名指令来源的真实性、完整性，确保指令未被篡改且来自授权源。十、设计模拟卫星轨道计算程序时，除数学模型（开普勒定律、牛顿引力定律等）外，还需考虑以下计算机科学/技术相关因素：1）数值方法：轨道计算常涉及复杂的微分方程求解（如运行轨道摄动），需要选择合适的数值积分方法（如龙格-库塔法、蛙跳法）以保证计算精度和效率。2）数据结构：如何有效存储和管理星历数据、卫星状态矢量、大气模型参数等。3）算法效率与精度平衡：计算过程中需要在计算精度和