每日一题

4.1 时间复杂度

错题：

• 1
• 2

4.2 时间复杂度

错题：

• 1
• 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 图和数据的运算

错题

• 1

4.28 图和数据的表示

错题

• 无

4.29 图和数据的表示

错题：

• 无

4.30 图和数据的运算

错题：

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

5.1 图和数据的运算

错题：

• 无

5.2 图和数据的表示

错题：

• 无

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

错题

• 无

5.4 图的存储和数据的运算

错题

• 无

5.5 图和数据的运算

错题：

• 无

5.6 图和浮点数的表示

错题：

• 2

5.7 图和浮点数的运算

错题：

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

5.8 图和浮点数的表示

错题：

• 2

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 平衡二叉树和存储系统

错题：

5.22 平衡二叉树和存储系统

错题：