每日一题

4.1 时间复杂度

错题：

4.2 时间复杂度

错题：

4.3 链表

错题：

2
- 注意特殊条件

4.4 链表

错题：

2
- -1表示指向NULL，-2表示空表项

4.5 栈

错题：

无
卡塔兰数的计算确实只与入栈序列的长度有关，而不关心入栈序列的具体内容或元素的顺序。这是因为卡塔兰数计算的是栈操作的合法性约束，而栈操作的合法性取决于元素的相对入栈顺序和出栈顺序，而非具体的元素值。因此，对于任何长度为 nnn 的入栈序列，合法的出栈序列的个数始终是固定的，由卡塔兰数给出。

4.6 队列和栈

错题：

4.7 队列和栈

错题：

4.8 队列

错题：

4.9 中缀表达式和后缀表达式

错题：

无
中缀转后缀，左优先
中缀转前缀，左优先（王道上的是错的）

4.10 后缀表达式和二叉树的层序遍历

错题：

4.11 数组的压缩存储

错题：

4.12 kmp算法

错题：

4.13 kmp算法

错题：

4.14 二叉树

错题：

4.15 二叉树

错题：

1
- 有n个结点的二叉树，可能的层高为完全二叉树的层高m~连成一条即n的层高，可能的数量为n-m+1

4.16 二叉树

错题：

4.17 二叉树

错题：

4.18 二叉树

错题：

4.19 二叉树

错题：

4.20 二叉树

错题：

4.21 二叉树

错题：

1
- 注意卡特兰数的适用

4.22 哈夫曼树和指令集

错题：

4.23 并查集和加法器

错题：

1
- 注意区分根节点的编号和根节点数组存储的值
2
- 功能部件指具体的实现硬件，如加法器本身

4.24 图和计算机系统概述

错题：

4.25 图和计算机系统概述

错题：

1
- 如果两个点可以互相到达，则属于同一个强连通分量

4.26 图和数据的运算

错题

无
- 记住这个加法器的图，减法的情况下，两端是减数和被减数的补码，sub控制进位+1

4.27 图和数据的运算

错题

4.28 图和数据的表示

错题

4.29 图和数据的表示

错题：

4.30 图和数据的运算

错题：

2
- 能用表示范围判断就用表示范围判断
- 不好转真值的时候才用标志位判断

5.1 图和数据的运算

错题：

5.2 图和数据的表示

错题：

5.3 图的存储和浮点数的表示

错题

5.4 图的存储和数据的运算

错题

5.5 图和数据的运算

错题：

5.6 图和浮点数的表示

错题：

5.7 图和浮点数的运算

错题：

1
- dijkstra算法的流程、操作与prim算法的都很相似，都基于贪心策略。区别在于：
  - 目的不同
    - dijkstra算法的目的是构建单源点的最短路径
    - prim算法的目的是构建最小生成树
  - 算法思路略有不同
    - prim算法从一个点开始，每次选择权值最小的边，将其连接到已构建的生成树上，直至所有顶点都已加入
    - 而dijkstra算法每次找出道远点距离最近且未归入集合的点，并把它归入集合，同时以这个点为基础更新从源点到其他顶点的距离。
  - 适用的图不同
    - prim算法只能适用于带权无向图
    - dijkstra算法可以用于带权有向图或者无向图

5.8 图和浮点数的表示

错题：

5.9 图和浮点数的表示

错题：

2
- float里面有些二进制组合表示特殊状态不表示具体的数，因此比int少

5.10 图和浮点数的表示

错题：

1
- 上下三角矩阵是指主对角线上下，不包括斜对角线
2
- 非规格化浮点数在超出规格化的范围后，非规格化数仍然能参加运算而不是直接当成0处理

5.11 图和数据类型转换

错题：

5.12 图和浮点数的计算与表示

错题：

2
- 对阶

5.13 图和边界对齐

错题：

5.14 图和数据类型转换

错题：

2
- 短数向长数转换，只需要记住无符号数和有符号数扩展的规则，边长后的数据类型只决定解释机器数的规则

5.15 图和数据的存储

错题：

5.16 查找和浮点数的表示

错题：

5.17 二叉树和存储系统

错题：

1
- 二分查找判定树有两种情况
  - 每个分支节点要么左右子树结点总数相等，要么左子树比右子树结点总数多一个
  - 每个分支节点要么左右子树结点总数相等，要么左子树比右子树结点数少一个

5.18 排序和存储系统

错题：

5.19 排序和存储系统

错题：

5.20 排序和存储系统

错题：

1
- 给出的是查找顺序而不是二叉排序树的存储
2
- 当cache命中的时候，直接从cache中读取送到cpu，不需要进行主存和cpu之间的数据交换
- 而当cache确实的时候，需要从主存中读取数据送入cpu并且写入cache
- 题目考察的就是cache缺失后cpu和主存进行交换所需要的时间。

5.21 平衡二叉树和存储系统

错题：

1
- 每个分支节点平衡因子为1的时候，高度最大，此时h层的平衡二叉树所需最少结点数应按递推式H(n)=H(n-1)+H(n-2)+1计算。(H1=1,H2=2)

5.22 平衡二叉树和存储系统

错题：

5.23 红黑树和存储系统

错题：

1
- 红黑树的黑高是指从该点（不包含该点）出发到叶子节点的路径上黑色节点的数量

5.24 红黑树和存储系统

错题：

5.25 B树和存储系统

错题：

5.26 B树和存储系统

错题：

1
- 根节点的关键字范围是（1，m-1），非根节点的关键字的范围是（上取整m/2-1，m-1）
2
- 以cache块为单位

5.27 B树和存储系统

错题：

1
- 注意区分两种问法
2
- Cache行数所占位数=log2（Cache容量/Cache块大小）

5.28 B树和存储系统

错题：

无
注意多路选择器和比较器的区别，比较器用来判断标记是否匹配，多路选择器用来输出最后结果

5.29 B树和存储系统

错题：

1
2
- 注意这里的主存命中率是指cache未命中的时候的主存命中率

5.30 B树和存储系统

错题：

1
- 兄弟不够借，和双亲合并是指双亲关键字拉下来

5.31 B树和B+树和存储系统

错题：

6.1 排序和存储系统和操作系统概述

错题：

1
- 二次探查再散列法是指平方探测法
2
- 数据修改的时候cache也跟着改
3
- 作业调度是指从外存到内存，内存调度是指挂起的重新放入内存，进程调度是指分配cpu

6.2 排序和存储系统和操作系统概述

错题：

1
- 探测次数是指用到线性探测法，不是查找失败的次数。

6.3 排序和存储系统和操作系统概述

错题：

1
- 因为是mod 7 ，所以查找失败的映射范围是0~6一共7个数，所以只用探测0~6的映射情况，然后分母为7

6.4 排序和指令系统和操作系统概述

错题：

2
- 给出的PC值是取指之前的
传递参数其实就是压栈保存

6.5 排序和指令系统和操作系统概述

错题：

2
- 实际计算机中栈是往低地址延伸，也就是说当栈顶增加的时候，实际上是内存减少，高地址是栈底，低地址是栈顶

6.6 排序和指令系统和操作系统概述

错题：

6.7 排序和指令系统和操作系统概述

错题：

6.8 排序和指令系统和操作系统概述

错题：

2
- RISC有乘除和浮点数运算指令
- RISC从CISC中选取了使用频率高的简单指令，以及很有用且不复杂的指令
3
- 编写中断服务程序也是操作系统所做

6.9 排序和指令系统和操作系统概述

错题：

1
- 冒泡排序上帝视角排序正确以后机器还需要再进行一轮冒泡排序检查是否排序正确

6.10 排序和CPU和操作系统概述

错题：

1
- 快排会交换位置
2

6.11 排序和指令系统和内存管理

错题：

3
- 进程切换的时候需要保存现场即通用寄存器的值

6.12 排序和CPU和进程线程

错题：

6.13 排序和CPU和进程线程

错题：

6.14 排序和指令流水线和进程线程

错题：

6.15 外部排序和CPU和进程线程

错题：

6.16 排序和指令流水线和进程线程

错题：

3
- 自旋锁是一直请求锁，具有随机性

6.17 外部排序和指令流水线和进程线程

错题：

2
- 普通数据冒险采用旁路转发技术不需要阻塞，而load-use需要阻塞一个时钟周期的根本原因是所需数据产生的阶段不同，使用ALU计算获得结果（所需数据）的在EX阶段可以产生所需数据，而load指令在M阶段从内存中获取所需数据

6.18 外部排序和多处理器的基本概念和进程线程

错题：

1
- 败者树中非叶子节点存储的是失败者的标记（归并段下标），而叶子节点存储的是各个路当前记录的索引值

6.19 外部排序和总线和进程线程

错题：

3
- 注意题目所说的是内核线程

6.20 外部排序和I/O和进程线程

错题：

6.21排序和I/O和进程线程

错题：

6.22 外部排序和终端一场和进程线程

错题：

1
- 败者树为k路归并段内部排序所使用的，用于提高内部排序效率，与I/O次数无关
3
- 每个选项都很精华
- 选项解释说正在访问操作系统内核临界区中不应该被剥夺处理机资源，是因为“取出准备挂到就绪队列”，说明还在处理中，如果挂到就绪队列上了，可能因为优先级引起进程调度程序执行

6.23 时间复杂度和中断异常和进程线程

错题：

3
- 唤醒因为I/O操作被阻塞的进程由中断服务程序完成。
  - 阻塞I/O操作进程由对应的系统调用服务例程完成
  - 将数据从设备控制器的寄存器送往内核缓冲区由中断服务程序完成
  - 将数据从内核缓冲区送往用户缓冲区由系统调用服务程序在唤醒后完成
  - 初始化外设的代码在驱动程序中

6.24 数据结构的基本概念和I/O方式和内存管理

错题：

1
- 数据元素是指{1，2，3}{1}这些单个的值，数据对象是多个字段或者数据元素的集合
2
- DMA进行数据传送之前，CPU先执行一段初始化程序，完成对DMA控制器中各参数寄存器的初始值的设定，因此通过软件完成对DMA控制器中各参数寄存器的初始值的设定

6.25 单链表和I/O方式和内存管理

错题：

6.26 平衡二叉树和数据的表示和内存管理

错题：

第一题答案写错，选C，正确
2
- 负数是绝对值越小越大
3
- 页式存储管理中每个进程有一个页表
- 段式存储管理中每个进程都有一个段表
- 段页式存储管理中，每个进程都有一个段表，每个进程的每个段都有一个页表

6.27 图和数据的表示和内存管理

错题：

1
- 生成树的定义是，包含所有顶点的极小连通子图
3

6.28 时间复杂度和数据的表示和内存管理

错题：

1
- 运用递归树

6.29 链表和数据的运算和文件管理

错题：

3
- inode不包含文件名，文件名存储在目录文件的目录项中，每个目录文件将文件名与inode号关联

6.30 链表和浮点数的表示和文件管理

错题：

7.1 图和指令系统和文件管理和计算机网络体系结构

错题：

7.2 图的基本概念和I/O方式和死锁和计算机网络的性能指标

错题：

4
- 负载均衡：允许多路并行转发数据，最大吞吐量为多路带宽之和

7.3 线性表和计算机系统概述和I/O管理和计算机网络体系结构

错题：

7.4 kmp算法和数据的表示和进程和线程和计算机网络体系结构

错题：

1
- 注意回溯
3
- 资源分配图中不存在环路，则系统状态图中不存在环路，即无死锁

7.5 数据结构的基本概念和中央处理器和死锁和计算机网络体系结构

错题：

4
- 同步（或时序）规定了事件发生的顺序

7.6 时间复杂度、CPU的基本结构、内存管理、TCP/IP

错题：

7.7 静态链表、微程序控制器、文件管理、OSI模型

错题：

1
3
- FAT在文件系统挂载的时候就被全部或大部分读入内存，并常驻内存当中，而不是打开单个文件的时候才去读入
4
- 传输媒体（线）不属于网络体系结构
- 网络层参与拥塞控制

7.8 线性表和I/O查询方式和内存地址转换计算和OSI/TCP模型的区别

错题：

7.9 栈和I/O方式和文件存储空间管理和TCP/IP模型

错题：

3
- 空闲链表法分为空闲盘块链和空闲盘区链，空闲盘区链可以把连续的空闲盘块合并成一个区，支持合并

7.10 冒泡排序和计算机软件和页面置换算法和通信基础

错题：

7.11 快速排序算法和RAM和信号量和通信基础

错题：

7.12 队列和补码和目录和通信基础

错题：

2
- 补码的本质是取模，对于补码表示的定点小数，模数是2，对于补码表示的定点小数，模数是2^n+1
3
- 在引入索引节点（inode）的文件系统中，目录项通常包含文件名与该文件名对应的索引节点号。目录本身是一个包含这些目录项的文件。索引节点是存储文件元数据（如文件大小、权限、物理位置等）的数据结构，他们通常集中存放在磁盘的特定区域（索引节点区）。因此，目录是文件名到索引节点号的映射集合，而不是索引节点本身的有序集合。
4
- 信道带宽=信道频率范围上限-信道频率范围下限

7.13 快速排序和CPU和内存映射文件和通信基础

错题：

1
- 以第一个关键字
2
- 硬布线控制器又名组合逻辑控制器

7.14 单链表和主存储器和I/O和CSMA/CA

错题：

7.15 栈和指令周期和文件系统布局和数据链路层

错题：

2
- 时钟上升沿瞬间捕获数据，指的是捕获存储器旧值的数据
3
- 超级块有备份

7.16 栈和电路和虚拟存储器和通信基础

错题：

2
- 多路选择器是一种能够从多个输入信号中选择一个输出的信号转换设备。译码器是一种将二进制编码转换为一组特定输出信号的设备。在寄存器堆中，译码器常常用于地址译码，从而控制对特定寄存器的访问。
  - 执行寄存器写相关指令时（将结果保存在寄存器中），指令中的寄存器编号被送到一个地址译码器进行译码，选中某个寄存器进行写入，读出时（从寄存器中获得计算数据）寄存器编号作为一个控制信号来控制一个多路选择器，选择相应的寄存器读出。
  - 读口（组合逻辑操作）：无需时钟控制，busA和busB分别由RA和RB给出地址。地址RA或RB有效后，经一个“取数时间（AccessTime）”，busA和busB有效
  - 写口（时序逻辑操作）：需要时钟控制。写使能为1的情况下，时钟边沿到来时，busW传来的值开始被写入RW指定的寄存器中。