# 考研 408 计算机学科专业基础（一）：数据结构（树与图算法、查找与排序复杂度）与计算机组成原理（IEEE754、Cache映射、流水线、指令系统）

> 全面覆盖408统考《数据结构》（占45分）与《计算机组成原理》（占45分）核心考点：线性表、栈与队列、平衡二叉树/红黑树/B+树、图的最短路径与最小生成树、内部排序与外部排序对比，以及IEEE754浮点数、ALU运算、Cache三种映射与写策略、五段流水线冲突及CPU控制器。

- **Canonical URL:** https://flashcards.world/flashcards/sets/72b50b9d-a1e0-4eaf-a362-3503c62fa962/
- **Markdown URL:** https://flashcards.world/flashcards/sets/72b50b9d-a1e0-4eaf-a362-3503c62fa962.md
- **Level:** basic
- **Languages:** zh → zh
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | 指令系统中的寻址方式：立即寻址、直接寻址、间接寻址、寄存器寻址、基址寻址、变址寻址、相对寻址的核心特点与应用场景是什么？ | 1）立即寻址：地址码字段直接就是操作数补码本身，取指即得操作数，0次访存；2）直接/间接寻址：1次/多次访存；3）基址寻址（EA = (BR)+A）：基址寄存器内容由操作系统管理，程序执行中不变，形式地址A可变，用于多道程序重定位与扩充寻址空间；4）变址寻址（EA = (IX)+A）：变址寄存器内容由用户程序改变，A不变，用于数组遍历与循环；5）相对寻址（EA = (PC)+A）：广泛用于转移指令及编写浮动程序。 |  |  |
| 2 | 若指令流水线有 k 个功能段，各段执行时间均为 Δt，连续执行 n 条无冲突指令的总时间、吞吐率（TP）和加速比（S）公式是什么？ | 流水线执行 n 条指令的总时间 T_k = (k + n - 1)Δt；顺序执行总时间 T_0 = k × n × Δt。流水线实际吞吐率 TP = n / [(k + n - 1)Δt]（当 n→∞ 时最大吞吐率 TP_max = 1/Δt）；流水线加速比 S = T_0 / T_k = (k × n) / (k + n - 1)（当 n→∞ 时理想最大加速比为 k）。 |  |  |
| 3 | 图的邻接矩阵与邻接表存储方式在空间复杂度上有何差异？分别适合什么类型的图？十字链表与邻接多重表分别用于什么图？ | 邻接矩阵空间复杂度为 O(\|V\|²)，适合稠密图，可 O(1) 判断任意两点是否相连；邻接表空间复杂度为有向图 O(\|V\|+\|E\|)、无向图 O(\|V\|+2\|E\|)，适合稀疏图。十字链表是针对【有向图】的链式存储（极易求入度和出度）；邻接多重表是针对【无向图】的链式存储（每条边只用一个结点表示，方便删除边操作）。 |  |  |
| 4 | 哈夫曼树（最优二叉树）的带权路径长度（WPL）如何计算？若度为0的叶结点有 n₀ 个，度为2的分支结点有多少个？ | WPL = ∑(w_i × l_i)，即所有叶结点的权值乘以其到根结点的路径长度之和。由于二元哈夫曼树每次合并两个权值最小的树产生一个新结点，不存在度为1的结点，故度为2的结点数 n₂ = n₀ - 1，总结点数为 2n₀ - 1。 |  |  |
| 5 | 在外部排序中，为减少归并趟数 S = ⌈log_k r⌉，增大归并路数 k 和减少初始归并段个数 r 分别采用什么数据结构实现？ | 1）增大归并路数 k 时，为避免内部归并时每次从 k 个元素中选最小值的比较次数随 k 增大而增加，采用【败者树（Loser Tree）】，使每次选出最小关键字仅需 ⌈log₂k⌉ 次比较；2）减少初始归并段个数 r 时，采用【置换-选择排序（基于最小最大堆）】，可生成平均长度为内存工作区大小 2 倍的初始归并段；3）多路平衡归并中若初始段长度不等，用【最佳归并树（k叉哈夫曼树）】并补充虚段使总 I/O 次数最少。 |  |  |
| 6 | C 语言中 short、int、float、double 之间进行强制类型转换时，哪些转换会导致精度丢失或范围溢出？ | 1）int → float：不会溢出，但 int 有31位有效数值位，而 float 仅有 24 位（1位隐藏位+23位尾数），当 int 有效位超过24位时会发生精度舍入；2）int / float → double：double 尾数有 52+1=53 位且阶码 11 位，能精确表示所有 32 位 int 和 float，既不溢出也不丢精度；3）double → float：可能发生范围溢出（变 ±∞）或尾数截断丢精度；4）float/double → int：向零取整截断小数，超范围时结果未定义（x86中常置为 80000000H）。 |  |  |
| 7 | 408 内部排序算法中，直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、二路归并排序、基数排序的【稳定性】与【最坏时间复杂度】如何对比？ | 【稳定排序（4种）】：直接插入排序（最坏 O(n²)）、冒泡排序（最坏 O(n²)）、二路归并排序（最好/平均/最坏均为 O(n log₂n)）、基数排序（O(d(n+r))）。【不稳定排序（4种，口诀“快些选堆”）】：快速排序（平均 O(n log₂n)，初始有序或逆序时最坏 O(n²)）、希尔排序（取决于增量序列）、简单选择排序（恒为 O(n²)）、堆排序（最好/平均/最坏均为 O(n log₂n)）。 |  |  |
| 8 | 浮点数加减运算的五个基本步骤是什么？在什么阶段可能发生舍入（Rounding）和溢出？ | 五个步骤：1）对阶（小阶向大阶看齐，阶码小的尾数右移，此时右移丢弃低位可能导致精度损失）；2）尾数加减；3）规格化（若结果双符号位为 01 或 10 需右规一次并阶码加1；若最高数值位与符号位相同需左规并阶码减1）；4）舍入（0舍1入法或恒置1法，针对对阶或右规移出的低位）；5）判溢出（由阶码是否上溢/下溢决定，阶码上溢触发异常，下溢按机器零处理）。 |  |  |
| 9 | CISC（复杂指令集计算机）与 RISC（精简指令集计算机）在指令系统设计、寻址方式、寄存器数量和流水线实现上有何核心区别？ | CISC（如 x86）指令数目多、字长不固定、寻址方式复杂、访存指令不受限、多采用微程序控制器，难以高效实现指令流水线；RISC（如 MIPS/ARM/RISC-V）指令数目少且定长、仅 Load/Store 指令可访存、通用寄存器数量多、绝大多数指令单周期完成、采用硬布线控制器，极其有利于指令流水线与超标量优化。 |  |  |
| 10 | 求最短路径的 Dijkstra 算法与 Floyd 算法的时间复杂度各是多少？为什么 Dijkstra 算法不能处理带负权边的图？ | Dijkstra 单源最短路径时间复杂度为 O(\|V\|²)（用优先队列可优化至 O((\|V\|+\|E\|)log\|V\|)）；Floyd 多源最短路径采用动态规划，时间复杂度为 O(\|V\|³)。Dijkstra 基于贪心策略，假设一旦某顶点被并入已确定集合 S，其最短路径长度不再改变；若存在负权边，后续通过负权边绕行可能得到更短路径，从而破坏贪心前提（Floyd 允许负权边但不能有负权回路）。 |  |  |
| 11 | SRAM 与 DRAM 的存储元原理有何不同？为什么 DRAM 需要定期刷新（Refresh），常见的三种刷新方式是什么？ | SRAM 采用双稳态触发器（6晶体管）存储信息，非破坏性读出，速度快、集成度低、无需刷新，常用作 Cache；DRAM 采用栅极电容上的电荷存储信息，破坏性读出（读后需重写），且电容漏电需在 2ms 等刷新周期内按【行】定期刷新，常用作主存。三种刷新方式：集中刷新（存在死区）、分散刷新（无死区但存取周期翻倍且过度刷新）、异步刷新（将刷新周期除以行数分散到各小段时间，死区缩短为一个存取周期）。 |  |  |
| 12 | 硬布线控制器（组合逻辑控制器）与微程序控制器的工作原理、速度及扩充修改灵活性有何不同？ | 硬布线控制器根据指令操作码、节拍信号和状态条件，直接由门电路网络产生微操作控制信号，速度快，但设计复杂且不易修改扩充；微程序控制器将每条机器指令编写为一段存放在控制存储器（CM，只读ROM）中的微程序（由若干微指令组成），每次从 CM 读出微指令产生控制信号，规整且易于修改扩充，但因访问 CM 导致速度较慢。 |  |  |
| 13 | 定点整数的补码加减法中，如何利用“单符号位”和“双符号位（变形补码）”判断溢出（Overflow）？无符号整数加减如何判断溢出？ | 1）有符号补码单符号位：当最高有效位进位 C_{n-1} 与符号位进位 C_n 不同时发生溢出，即 OF = C_n ⊕ C_{n-1}；2）双符号位（变形补码）：结果双符号位 S_{s1}S_{s2} = 01 表示正溢出（上溢），10 表示负溢出（下溢），00 和 11 表示无溢出；3）无符号整数：利用进位/借位标志 CF 判断，加法时 CF = C_n，减法时 CF = C_n ⊕ 1（SUB=1时最高位进位取反）。 |  |  |
| 14 | IEEE 754 标准中 32 位单精度浮点数（float）的各字段位数、阶码偏置值（Bias）及规格化真值计算公式是什么？ | 32位单精度浮点数由 1位数符 S + 8位阶码 E（移码表示，偏置值 Bias = 127 = 7FH） + 23位尾数 M（原码隐藏最高位1）组成。当 1 ≤ E ≤ 254 时为规格化数，真值 = (-1)^S × (1.M)₂ × 2^(E - 127)；E=0 且 M=0 为机器零；E=0 且 M≠0 为非规格化数，真值 = (-1)^S × (0.M)₂ × 2^(-126)；E=255 且 M=0 为无穷大 ∞；E=255 且 M≠0 为 NaN。 |  |  |
| 15 | 图的广度优先搜索（BFS）与深度优先搜索（DFS）在采用邻接矩阵和邻接表存储时的时间复杂度分别是多少？ | 无论 BFS 还是 DFS，遍历图的过程本质上是对每个顶点和每条边进行访问：采用邻接矩阵存储时，查找每个顶点的邻接点需 O(\|V\|)，总时间复杂度均为 O(\|V\|²)；采用邻接表存储时，访问所有顶点花 O(\|V\|)，扫描所有边花 O(\|E\|)，总时间复杂度均为 O(\|V\| + \|E\|)。 |  |  |
| 16 | 在《计算机组成原理》中，计算机系统的性能指标 CPI、MIPS、MFLOPS 与 CPU 执行时间公式是什么？ | CPU 执行时间 = CPU 时钟周期数 × 时钟周期时间(T) = (指令条数 IC × CPI) / 主频(f)。其中 CPI 为执行一条指令所需的平均时钟周期数；MIPS = 指令条数 / (执行时间 × 10⁶) = f / (CPI × 10⁶)，表示每秒执行多少百万条指令；MFLOPS 表示每秒执行多少百万次浮点运算。 |  |  |
| 17 | Cache 的两种写命中策略（全写法 Write-Through 与回写法 Write-Back）和两种写不命中策略（写分配法与非写分配法）如何配合使用？ | 1）【全写法 + 非写分配法】：写命中时同时写 Cache 和主存（设写缓冲队列减少等待），写不命中时只直接写主存而不调块入 Cache，无需脏位（Dirty bit）；2）【回写法 + 写分配法】：写命中时只修改 Cache 而不立即写主存，仅当该行被替换出时若修改位（脏位=1）才写回主存；写不命中时先把主存块调入 Cache 再修改 Cache，每个 Cache 行必须增设 1 位脏位。 |  |  |
| 18 | 总线仲裁的集中式仲裁（链式查询、计数器定时查询、独立请求）各有何优缺点？总线带宽如何计算？ | 链式查询只需很少几根仲裁线（BS、BR、BG），优先级固定由物理位置决定，对电路故障最敏感；计数器定时查询需 ≈log₂n 根设备地址线，优先级可灵活设定；独立请求方式每个设备有独立的 BR 和 BG 线，响应速度最快但控制线数量为 2n。总线带宽 = 总线工作频率 × 总线宽度（Byte） = (总线时钟频率 / 总线周期含时钟数) × (数据线位数 / 8)。 |  |  |
| 19 | I/O 控制方式中的程序查询、程序中断、DMA（直接存储器访问）与通道控制在数据传输单位、CPU 干预频率及开销上有何区别？ | 1）程序查询：CPU 不断轮询设备状态，CPU 与外设串行工作，开销极大；2）程序中断：外设准备好每个字/字节后向 CPU 发中断请求，CPU 暂停现行程序保护现场并执行中断服务程序传输1个字，适合低速外设；3）DMA 方式：由 DMA 控制器接管总线直接在外设与主存间按块传输，每传输一个字仅【窃取（Cycle Stealing）1个存取周期】而不中断 CPU 现行程序，仅在整个数据块传输开始和结束时触发中断由 CPU 干预。 |  |  |
| 20 | 平衡二叉树（AVL树）在插入新结点导致失衡时，LL、RR、LR、RL 四种失衡类型的旋转调整规则分别是什么？ | 1）LL型（左孩子的左子树插入导致失衡）：对最小不平衡子树的根做一次右单旋；2）RR型（右孩子的右子树插入）：做一次左单旋；3）LR型（左孩子的右子树插入）：先对左孩子做左旋，再对根做右旋（先左后右双旋）；4）RL型（右孩子的左子树插入）：先对右孩子做右旋，再对根做左旋（先右后左双旋）。 |  |  |
| 21 | 在408《数据结构》中，具有 n 个结点的二叉链表中，非空链域和空链域的个数分别是多少？若将其线索化，线索指针的数目是多少？ | 具有 n 个结点的二叉链表共有 2n 个指针域，除了根结点外每个结点有且仅有一个父指针指向它，因此非空链域为 n-1 个，空链域为 n+1 个；线索二叉树正是利用这 n+1 个空链域存放指向前驱或后继的线索指针。 |  |  |
| 22 | 红黑树（Red-Black Tree）必须满足哪五条核心性质（口诀“左根右、根叶黑、不红红、黑路同”）？其相比 AVL 树在工程中的优势是什么？ | 性质：1）每个结点或是红色或是黑色；2）根结点必为黑色；3）所有叶结点（外部空指针NIL）均为黑色；4）不存在两个相邻的红结点（红结点的父与子必为黑）；5）从任一结点到其每个叶结点的所有简单路径包含相同数目的黑结点（黑高相同）。优势：红黑树要求任一结点左右子树高度差不超过2倍，插入和删除时旋转次数远少于AVL树（插入最多2次旋转，删除最多3次旋转）。 |  |  |
| 23 | 快速排序的空间复杂度是多少？在什么情况下空间复杂度最坏？堆排序建初堆与每次调整堆的时间复杂度分别是多少？ | 快速排序需要递归工作栈保存划分边界，平均空间复杂度为 O(log₂n)，当初始序列有序或基本有序导致每次枢轴划分极不均匀时，递归深度为 n，最坏空间复杂度为 O(n)。堆排序是原地排序（空间 O(1)），自底向上调整建初堆的时间复杂度为 O(n)，之后进行 n-1 次取堆顶并向下筛选调整的总时间复杂度为 O(n log₂n)。 |  |  |
| 24 | 最小生成树（MST）的 Prim 算法与 Kruskal 算法的贪心策略、时间复杂度及适用场景有何不同？ | Prim 算法从顶点出发（逐步归并顶点），每次选择距离当前生成树顶点集最近的新顶点加入，时间复杂度为 O(\|V\|²)，与边数无关，适合【边稠密图】；Kruskal 算法从边出发（按权值递增排序并结合并查集判环），时间复杂度为 O(\|E\| log \|E\|)，适合【边稀疏而顶点较多】的图。 |  |  |
| 25 | 五段指令流水线（IF取指、ID译码、EX执行、MEM访存、WB写回）中，哪三种相关（冲突/冒险）会导致流水线阻塞？各自如何解决？ | 1）结构冒险（资源冲突）：多条指令同一时钟周期争用同一功能部件（如共用一个存储器），通过将指令 Cache 与数据 Cache 分离（哈佛结构）或插入气泡解决；2）数据冒险（写后读 RAW 冲突）：后续指令需用到前序指令尚未写回的结果，通过【数据旁路/转发（Forwarding）】技术解决，若前一条是 Load 指令紧跟 ALU 使用（Load-Use冒险），必须硬件阻塞（Stall）1个周期再加转发；3）控制冒险（分支指令引起）：通过分支预测、预取分支目标或延迟槽解决。 |  |  |
| 26 | 在页式虚拟存储器中，TLB（快表）、Page Table（慢表/页表）、Cache 与主存的访问流程及命中组合有哪些可能？ | CPU 给出虚拟地址后，先查 TLB 进行虚实地址转换，若 TLB 未命中再查主存中的页表（慢表）；得到物理地址后再查 Cache，若 Cache 未命中则访问主存。合法组合注意：1）若缺页（Page Fault，页表未命中），则 TLB 和 Cache 必定未命中（因为页面根本不在主存中）；2）只要页面在主存中（页表命中），TLB 命中与否和 Cache 命中与否相互独立，均可发生。 |  |  |
| 27 | 散列表（Hash Table）处理冲突的拉链法与开放定址法（线性探测、平方探测）各有何特点？为什么开放定址法删除元素时不能直接置空？ | 拉链法将同义词存于同一个单链表中，无堆积现象且删除简单；开放定址法中，线性探测（d_i = 1, 2, ...）易产生“一次聚集（同义词与非同义词堆积）”，平方探测（d_i = 1², -1², 2², -2²...）可缓解一次聚集但不能探测到表上所有单元（表长需为 4k+3 型素数）。开放定址法删除元素时若直接置空会截断后续同义词的查找路径，必须打上“逻辑删除标记（墓碑）”。 |  |  |
| 28 | 字符串模式匹配的 KMP 算法相比朴素匹配算法的核心改进是什么？当主串指针 i 与模式串指针 j 失配时，i 和 j 如何移动？ | 朴素匹配失配时主串指针 i 需要回溯，最坏时间复杂度 O(mn)；KMP 算法利用已匹配部分的前缀与后缀的最长公共元素长度构造 next 数组，失配时主串指针 i 【永不回溯】，仅将模式串指针 j 回退至 next[j]（或优化后的 nextval[j]）位置，使总时间复杂度达到线性级 O(m + n)。 |  |  |
| 29 | 主存与 Cache 之间的三种地址映射方式（直接映射、全相联映射、组相联映射）的主存地址字段如何划分？ | 1）直接映射：主存地址划分为【标记 Tag + Cache行号 + 块内地址】，主存第 i 块只能映射到 Cache 第 (i mod C) 行，硬件简单但冲突率高；2）全相联映射：划分为【标记 Tag + 块内地址】，主存块可装入任意空 Cache 行，命中率最高但比较器电路开销大；3）k 路组相联映射：划分为【标记 Tag + Cache组号 + 块内地址】，组间直接映射、组内全相联，兼顾命中率与硬件成本。 |  |  |
| 30 | 在 AOV 网（顶点表示活动的网）中进行拓扑排序的作用是什么？在 AOE 网（边表示活动的网）中如何定义“关键路径”与“关键活动”？ | 拓扑排序用于判断有向图是否存在环及确定工程活动的先后执行序列。在 AOE 网中，从源点到汇点所有路径中具有【最大路径长度】的路径称为关键路径；关键路径上的活动称为关键活动，其最早开始时间等于最迟开始时间（即时间余量 l(i) - e(i) = 0），仅缩短单个关键活动未必能缩短总工期（需同时缩短所有并行关键路径上的关键活动）。 |  |  |
| 31 | 一棵 m 阶 B 树（B-Tree）的非根内部结点关键字个数 k 与子树个数 n 的取值范围是什么？B+ 树与 B 树的三大核心区别是什么？ | m阶B树非根内部结点的子树个数 ⌈m/2⌉ ≤ n ≤ m，关键字个数 ⌈m/2⌉ - 1 ≤ k ≤ m - 1（根结点若非叶则至少2棵子树、1个关键字）。B+树与B树区别：1）B+树中n个关键字对应n棵子树（B树为n+1棵）；2）B+树只有叶结点包含全部关键字及指向记录的指针，非叶结点仅作索引；3）B+树所有叶结点通过双向链表相连，既支持从根开始的随机查找，又支持高效的范围顺序查找。 |  |  |
| 32 | 在微程序控制器中，水平型微指令与垂直型微指令有何区别？微指令的编码方式（直接编码、字段直接编码）如何计算控制字段位数？ | 水平型微指令一次能定义并并行执行多个微命令，微指令字较长但微程序短、执行快；垂直型微指令类似机器指令设置微操作码，字长短但并行度低。在【字段直接编码】中，将互斥的微命令分在同一段内进行译码，并且每个字段必须额外留出 1 个状态表示“不发任何微命令”，因此若某段有 k 个互斥微命令，则需要 ⌈log₂(k + 1)⌉ 位。 |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/72b50b9d-a1e0-4eaf-a362-3503c62fa962/).