K3知识点

提示：文章

前言

前期疑问：
本文目标：

---

K3知识点

2024年12月2日17:25:30

一、顺序队列和链式队列

题目

关于队列的说法正确的有
A、队列又叫先进先出表
B、队列是一种线性表
C、无法判断队列是否为空
D、顺序队列和链式队列是不同的两种存储方式
正确答案：ABD

疑问：

顺序队列和链式队列是两种存储方式吗？

**顺序队列和链式队列确实是两种不同的存储方式。**‌‌

顺序队列采用固定的存储空间，在读访问时非常简单，对内部元素的访问也很方便。然而，由于顺序队列的存储空间是提前设定的，当元素数量超过预设容量时，就会出现溢出现象。为了解决这个问题，顺序队列可以采用循环队列的结构，通过将队尾指针循环使用来扩展存储空间。

链式队列则通过动态申请空间来满足队列长度的大幅变动，避免了溢出问题。链式队列的存储空间是动态分配的，可以根据需要随时扩展，但访问队列内部元素不如顺序队列方便。

顺序队列和链式队列的定义和特性

• ‌顺序队列‌：使用一组地址连续的存储单元存放队列中的元素。队头指针指示当前的队首元素，队尾指针指示当前的队尾元素。顺序队列的存储空间是提前设定的，可能会出现溢出问题，可以通过循环使用队尾指针来解决。
• ‌链式队列‌：采用链式存储结构，通过动态申请空间来满足队列长度的大幅变动。链式队列的存储空间是动态分配的，避免了溢出问题，但访问队列内部元素不如顺序队列方便。

实际应用场景

• ‌顺序队列‌：适用于元素数量相对固定且读操作频繁的场景，如固定大小的缓冲区。
• ‌链式队列‌：适用于元素数量频繁变动的场景，如网络通信中的数据包处理。

顺序表

顺序表和顺序队列一样吗？

顺序表和顺序队列在定义和用途上有显著区别。

顺序表是一种线性表的存储结构，它使用一组地址连续的存储单位来依次存储线性表中的数据元素，使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点包括动态分配空间、支持随机访问和顺序访问，逻辑顺序与物理顺序一致，每个元素都有唯一的位置，可以通过索引直接访问‌12。

顺序队列则是队列的顺序存储结构，实际上是一种运算受限的顺序表。它使用一个向量空间来存放当前队列中的元素，通过设置两个指针（front和rear）分别指示队头元素和队尾元素在向量空间中的位置。顺序队列遵循先进先出的规则，适用于需要按顺序处理元素的场景‌

题目

以下哪个说法是正确的(A B D)
A、顺序表按下表查找的时间复杂度为O(1)
B、顺序表存储空间连续，即允许元素的随机访问
C、顺序表在使用时，长度可随意变动
D、顺序表插入变动的时间复杂度为O(n)

链式队列

源于题目：

1、 关于单向、双向链表，下列说法正确的是（多选）： ABCD

A. 用单向链表作为栈的存储形式，栈操作的时间复杂度可以达到O（1）

B. 用带尾指针的单向链表作为队列的存储形式，队列操作的时间复杂度可以达到O（1）

C. 用双向链表作为队列的存储形式，队列操作的时间复杂度可以达到O（1）

D. 用双向循环链表作为队列的存储形式，队列操作的时间复杂度可以达到O（1）

上面这个题目里的关键词对我来说都是陌生的。。。。。

查找关于A选项"单向链表作为栈的存储形式"这句话的意思，找到了下面的文章，列举的数据类型比较多：

【数据结构】第 1~10 章：思维导图与重点汇总

二、AVL树

这个知识点没有看懂，参考文档：AVL树详解

上一节的二叉二叉查找树BST，若按照顺序插入，会退化为一条链。于是需要对树的结构进行调整，使得树的高度在每次插入元素后仍然能保持O(logn)的级别，这样就产生了平衡二叉树。AVL(平衡二叉树）也是一个二叉查找树，查找操作和BST一样。但是AVL的高度为O(logn),查找时间复杂度为O(logn)。

43、AVL树再平衡的方法有
A、单次旋转：向右旋转
B、两次旋转：先向左旋转再向右旋转
C、两次旋转：先向右旋转再向左旋转
D、单次旋转：向左旋转
回答错误，答案为 ABCD

三、红黑树

参考文档：红黑树入门到精通，简单看了下，文字比较多，简单理解就是为了避免二叉树变成链表，实现平衡二叉树，产生了红黑树。具体的下次再研究吧。

四、二叉排序树

二叉排序树又叫二叉搜索树、搜索二叉树、二叉排序树、排序二叉树

源于题目：

对于下列关键字序列，不可能构成某二叉排序树种一条查找路径的序列是（）
A. 92, 20, 91, 34, 88, 35
B. 12, 25, 71, 68, 33, 34
C. 21, 89, 77, 29, 36, 38
D. 95, 22, 91, 24, 94, 71
答案：D

搜索文章，这篇文章有点看懂：二叉搜索树（二叉排序树）

其中关于二叉排序树的特点如下：

二叉排序树的定义和性质
二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），是一种递归定义的数据结构：

• ‌左子树‌：所有节点的值都小于根节点的值。
• ‌右子树‌：所有节点的值都大于根节点的值。
• ‌递归性质‌：左子树和右子树也必须是二叉排序树‌5。

二叉搜索树（BST）和二叉平衡树区别

‌二叉搜索树（BST）和AVL树在结构上有所不同，但都属于二叉树的一种。

定义和特性

• ‌**二叉搜索树（BST）**‌：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。这种结构使得二叉搜索树在查找、插入和删除操作上的时间复杂度为O(logN)，但在最坏情况下会退化为链表，时间复杂度变为O(N)‌12。
• ‌AVL树‌：AVL树是一种自平衡的二叉搜索树，它通过旋转操作来保持树的平衡，确保任何节点的两个子树的高度差不超过1。这使得AVL树的查找、插入和删除操作的时间复杂度仍然为O(logN)，但插入和删除操作需要进行复杂的旋转调整，以维持树的平衡‌

上述题目改天再做的时候突然又有点蒙，按照我最新的理解，二叉排序树的叶子结点应该都比根节点小，左节点都小于右节点。

能构成二叉搜索树的一个条件是，后面的节点值都小于第二个和第三个节点值，否则不能形成二叉搜索树。

写完上面的文字，看了下定义文字，不是二叉排序树的叶子结点应该都比根节点小，而是左子树节点的值小于根节点，右子树节点的值大于根节点

11、红黑树再平衡的方法有（ABE）
A. 单次左旋
B. 单次右旋
C. 两次旋转：先左旋再右旋
D. 两次旋转：先右旋再左旋
E. 改变颜色
答案应该是ABCDE吧
好像又是ABE
红黑树保持平衡的基本三种操作。 1 变色:红变黑 黑变红 2 左旋 3 右旋

五、树的概念

这个章节解决之前一直疑惑的几个概念：1、左子树；2、右子树；3、中序遍历；4、后序遍历；5、中根遍历

依据题目解决问题熟悉知识点

题目1

某二叉树节点的中序遍历为abcdefg，后序遍历为bdcafge，则其左子树中节点数目为()
A.4
B.2
C.5
D.3
A

看到这个题目首先要解决一个问题，就是什么是左子树？

左子树

查了资料，答，

‌左子树‌是指在二叉树中，以当前节点的左孩子为根节点的子树。在二叉树中，每个节点最多有两个子节点，分别称为左子节点和右子节点。左子树就是以当前节点的左孩子为根节点的子树‌

右子树

左子树：以当前节点的左孩子为根节点的子树。
右子树：以当前节点的右孩子为根节点的子树。
关系：两者都是二叉树的组成部分，且互不相交‌

前序遍历、中序遍历，后序遍历

这三个遍历方式都是按照深度优先来遍历的

参考文档：一文讲解前序遍历，中序遍历，后序遍历的遍历过程

至于前序遍历、中序遍历，后序遍历怎么记忆，方法是前中后是对应根，左右是固定左在右前面。所以前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。这样就记住了遍历顺序，但是究竟细节是怎么遍历的呢，下面验证一下

先根遍历、中根遍历

源于题目

4.[多选]关于二叉树（高度和深度的起始值为1），正确的是（）
A.一颗非空二叉树的先根遍历与中根遍历的顺序正好相反，则该二叉树所有节点无右孩子；
B.二叉树中每个节点的两颗子树的高度差等于1；
C.一颗具有n个节点的二叉树，其高度最多为n，最少为log2（n）
D.一颗非空二叉树的先根遍历与中根遍历的顺序正好相同，则该二叉树所有节点无左孩子；
正确答案：AD

先根遍历和先序遍历实际上是同一个概念，只是叫法不同，它们都是指的一种节点遍历算法，即按照“根节点->左子树->右子树”的顺序遍历每个节点，可记做根左右。这种遍历方式一般用于树或者二叉树中。‌

题目

某二叉树节点的中序遍历为abcdefg，后序遍历为bdcafge，则其左子树中节点数目为()
A.4
B.2
C.5
D.3

        E/     \A       G \     /   C   F/   \     B    D 

120 已知一颗二叉树，如果先序遍历的节点顺序是：KDCEFGHB,中序遍历是：CDFEGHKB,则后序遍历结果为
A. CFHGEBDK
B. CDFEGHBK
C. FGHCDEBK D. CFHGEDBK
D

自己梳理的结果如下

      K/     \D       B
/   \      
C    E/   \     F     H /
G

根据后序遍历，左右根的遍历方法，得到答案为CFGHEDBK

上述二叉树后序遍历结果和答案不一样，需要再次修改

左孩子右孩子

‌左孩子和左子树在二叉树中是不同的概念。

在二叉树中，每个节点有两个子节点，分别称为左孩子和右孩子。左孩子是指与节点直接相连的左边的子节点，而左子树是指从该节点出发向左延伸的整棵子树，包括该节点的所有左子孙节点‌。

左孩子和左子树的具体定义和区别

1. ‌左孩子：左孩子是指与某个节点直接相连的左边的子节点。在二叉树中，每个节点最多有两个孩子，左孩子和右孩子‌12。
2. ‌左子树：左子树是指从某个节点出发向左延伸的整棵子树，包括该节点的所有左子孙节点。左子树不仅包含左孩子，还包括左孩子的所有子孙节点‌

基于上述题目，验证答案，先验证A和D。

对于C答案，解释是二叉树高度最高的情况是每一个层只有一个结点，此时高度为N最小的情况是完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1，所以高度是[log2N]+1 到 N。

完全二叉树除了拥有二叉树的基本性质外，还具有以下性质：

1. 具有n个结点的完全二叉树的深度为 [log2n]+1 （注：[ ]表示向下取整）
2. 满二叉树也满足这个条件

用节点数为7的满二叉树验证上述计算高度的公式，验证有效。log2(7)=2.8，向下取整为2，加1为3，树的高度也为3。

题目2

某二叉树节点的中序遍历为abcdefg，后序遍历为bdcafge，则其左子树中节点数目为()
A.4
B.2
C.5
D.3
A

这个题目把我难住了，感觉之前看的前序后序中序知识又废了，就继续查找资料，看到下面这篇文章，【数据结构】—树：中序遍历，按照他的遍历方法才更熟悉一些。

但是上述是中序遍历，至于前序遍历和后序遍历是怎么遍历的，就继续查找，找到这篇文章

精简解析：二叉树的遍历方法及其应用场景，该文章前文的题目，我自己没看答案，自己写了下，答案全对，感觉这时候对遍历就更理解了。

最后还是回到上述的题目中，尝试解决一下。

六、平衡二叉树平衡因子

平衡因子为左子树比右子树的高度差。分为1和0和-1，什么是左子树、什么是右子树？左子树就是以当前节点的左节点为根节点的子树。

明白上面的知识点，下面的题目就好处理一些了。

12、若平衡二叉树的高度为4（只有根节点的二叉树高度为1），且所有非叶节点的平衡因子均为1，则该平衡树的节点总数为
A、4
B、7
C、12
D、20
正确答案B

根据题目画出平衡二叉树的图，根据下面的图可以知道节点总数为7个。

        8/     \3       14/  \    /   2    6  15/     
1        

七、B+树

1. 以下关于B+树的描述，正确的是 O
   A. B+树中，叶子节点之间不能顺序访问
   B. B+树查找的平均时间复杂度为O(logn）
   C. B+树中,中间节点保存了键值和数据
   D. B+树中，叶子节点只保存了数据

D选项，B+ 树非叶子节点上是不存储数据的，仅存储键值

1. 每个非叶子节点都包含了一定数量的子节点，这使得 B+ 树具有更高的数据存储和检索效率。
2. 所有数据都存储在叶子节点上，而非叶子节点只包含索引信息，这有助于减少磁盘 I/O 操作。
3. 叶子节点之间通过指针连接，形成一个有序链表，方便范围查询和顺序访问。
4. B+ 树的平衡性能保证了在数据插入和删除时树的高效性能。

B+ 树是一种高效的数据结构，适用于需要频繁插入、删除和范围查询操作的场景。

这个题目AC为什么不对还有待探究。

六、缓存Cache存储器访问周期计算

K3真题：
假定某计算机存储器中有Cache和主存(Memeory)，主存按字编址。假定Cache容量为4个Cache Line，用直接相联的映射方式，按地址取模的方式映射，采用最近最少使用的（LRU，least Recent Use）替换方法。假定Cache Line的大小为1个字节，cachel的初始时为空，某程序依次访问如下地址：0,8,0,6,8时，则该程序的Cache命中率为（*）
A、60%
B、40%
C、80%
D、0%

4.1 源于题目

假定某处理器使用了L1 Cache和L2 Cache。L1 Cache的命中率为90%，L2 Cache的局部命中率为95%。L1 Cache的访问延迟为10个时钟周期，L2 Cache的访问延迟为100个时钟周期。主存的访问延迟为1000个时钟周期。那么平均存储器(AMAT，Average Memory Access Time)的访问时间为多少个周期？
A、40
B、25
C、30
D、35

这个题目不会，百度查到资料，L1 Cache, L2 Cache读取命中率与时钟周期计算，这个题目看了能懂

按照上述文章计算，machineTime=(10 * 90% ) + 100 * ( (1 - 90%) * 95%) + 1000 * ( 1- 90% - (1 - 90%) * 95% ) = 23.5个

变更：根据下面的开放案例题目，列出新的公式：

计算逻辑表,假设数据总量为1
L1	L2	L3
时间t=10，数据全部穿越L1	t=100*(1-90%)，10%的数据全部穿越L2	t=1000*(1-(1-90%)*95%)，10%的95%在L2中被命中，只有10%的5%到了L3
10	10	1000*0.005=5
总共25个周期

4.2 开放案例题目

某计算机存储器层次中，存储系统由一个Cache和主存组成二级存储系统，假定Cache的存取周期为20ns，命中率为90%，希望采用Cache后的加速比等于5，那么要求主存的存取周期是（B ）ns
A. 175
B. 200
C. 225
D. 250

解释：做为单选题有唯一的正确答案，可以通过解方程的方式进行求解。
加速比为5，意味着使用cache以后的访存时间是不使用cache的访存时间的 1/5，假设不使用 cache 的访问时间为 x，
使用 cache 的访问时间分两种情况讨论，90%的概率命中，所以命中时的访存时间期望值是 0.9 * 20 = 18，
10%的概率不命中，这时要先访问cache，再访问主存，所以访存的期望是 0.1 * (20 + x) = 2 + 0.1x，两者相加为 20 + 0.1x。
不使用 cache 的访存时间是使用 cache 的访存时间的 5 倍，所以x / (20 + 0.1 x) = 5
求解这个方程可得，x = 200，所以B是正确答案。

自己验证：

验证逻辑表
10（假设总量是10）	x（设主存时间为x）
10（加了cache后的总量同样是10）	0.2x（加速比为5，时间缩短了5倍）
得到等式：20*(90%)+20*(1-90%)+20*(1-90%)=0.2x。	【这边有个疑问就是为什么还要加上20*(1-90%)，这边刚才想到应该可以理解为穿越cache的数据应该是全部，由此就涉及到上面的一个题目的计算了】

2.CPU访问存储器数据过程，Cache命中时访问时间为1ns，Cache缺失率为4%，Cache不命中时的访问时间为15ns，则存储器平均访问时间为（D）
当cache命中的情况：t1 = 1ns 出现概率为96%
当cache不命中的情况：t2 = 1ns + 15ns 出现概率为4%
t = t1 * 0.96 + t2 * 0.4 = 1.6
A、1.64ns
B、1.40ns
C、1.44ns
D、1.60ns

4.2 题目2

其他网上题目：存储系统Cache命中率问题——计算机组成原理，上述这个题目的第一个问我知道怎么做，第二个问题跟我想的不一样，【2024年12月20日12:39:46 今天再看一下第二题就是涉及了一个新的公式而已】。

文章提到的第一个题目，408真题：
在Cache和主存构成的两级存储体系中，主存与Cache同时访问，Cacge的存取时间是100ns,主存的存取时间是1000ns,设Cache和主存同时访问，若希望有效（平均）存取时间不超过Cache存取时间的115%，则Cache命中率至少应该为多少？

解：
分析：若Cache命中率为x那么主存命中率即为(1-x)。 即命中Cache了那么就不命中主存了。

假设命中率为x,可得100x+1000(1-x)<=100*(1+15%)

简单计算后得结果：

x >= 59/60

所以，Cache的命中率x至少应该为59/60，或者约为0.9833，即98.33%。

这个题目和上述两个题目的计算方式就不一样了。这个题目没有将数据全部穿越Cache的时间全算上。而是只算了cache命中的90%。我觉得可能是因为这句话【设Cache和主存同时访问】。

这篇文章中的写操作描述的就是我所表述的这种情况吧。同时文中还表述了平均访问时间和访问效率的计算公式。存储系统Cache（知识点+例题）

计算机组成原理求Cache的命中率相关练习题

计算机组成原理Cache例题

b站视频学习：【计组 | Cache】30min带你狠狠拿捏Cache所有知识与题型方法

根据上述b站视频笔记：
三种映射方式：
1、直接映射：要求主存的每一个块只能映射到Cache中的一个固定位置，cpu访问某个特定行即可。
2、全相联映射：允许主存的任何一个块映射到Cache中的任何一个位置。
3、组相联映射：结合了全相联和直接映射的优点。它将Cache分成若干组，每组包含多个块。主存的块可以映射到特定的组中，但组内的块位置是固定的。

地址结构：

直接映射主存地址结构	|标记|cache行号|块内地址|
全相联映射主存地址结构	|标记|块内地址|
组相联映射主存地址	|标记|组号|块内地址|

主存块号即去除块内地址的部分

七、哈希表二次探测及线性探测

二次探测

源于K3题目

哈希表有14个桶，哈希函数为h(key) = key % 11。表中先后插入了数据30、48、66、18、74和96，如果采用二次探测法处理冲突，则新数据31的位置（从0开始计数）是（C 11）

A、10 B、12 C、11 D、9

解析：

H(30) = 8
H(48)=4
H(66)=0
H(18)=7
H(74)=8，冲突	二次探测，H=(H(74) + 1) MOD 14 = 9
H(96)=8，冲突	二次探测，H=(H(96) + 1) MOD 14 = 9，冲突	H=(H(96) - 1) MOD 14 = 7，冲突；H=(H(96) + 4) MOD 14 = 12
H(31)=9，冲突	二次探测，H=(H(31) + 1) MOD 14 = 10

在hash表中的存储情况如下

0	1	2	3	4	5	6	7	8	9	10	11	12	13
66				48			18	30	74	31		90

正确答案C，应该是表达的位置吧。10号索引对应11号位置。

网上题目1

21.设哈希表长为14哈希函数是H(key)=key%11,表中已有数据的关键字为15,38.61.84共四个,现要将关键字为49的结点加刭表中,用二次探测再散列法解决冲突,则放入的位置是：9

题目链接：设哈希表长为14，哈希函数为h(key)=key%11。表中

解析：

线性探测

题目

34、有一系列整数7、30、11、18、9，采用的散列函数为 H(Key）=（key＊3）% 7，将这些数据按序散列到表长为10的哈希表中存储(位置从0开始计算)。若采用线性探测法解决冲突，则以下说法正确的是（BCD）？

A、18插在第6个位置

B、11插在第5个位置

C、9插在第8个位置

D、7插在第0个位置

这个题目11和18发生冲突，11的位置为H(11)=(11*3)%7=5; H(18)=(18*3)%7=5。这个时候只需要放在第6个位置就行了。如果第6个位置有值，会放在第7个位置就了。

网上题目2

关于散列表的题目

真题3

有一系列整数7、30、11、18、9，采用的散列函数为 H(Key）=（key＊3）% 7，将这些数据按序散列到表长为10的哈希表中存储(位置从0开始计算)。若采用线性探测法解决冲突，则以下说法正确的是（ABD）？

A.9插在第8个位置
B.11插在第5个位置
C.18插在第6个位置
D.7插在第0个位置

有一系列整数31，18，67，56，45，40，采用散列函数为H(key)=key % 7，将这些数据散列表长为7的哈希表中存储，若采用线性探测法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度可能为：D

A. 1.33
B. 1.5
C. 2
D. 2.17
链表法解决冲突 A （1+1+2+1+2+1）/ 6 =1.33 链表只有取余相同才会冲突

八、加密算法

源于题目：

用户口令在不需要还原的情形下，使用以下哪种算法比较适合存储？
A、SHA512
B、SHA1
C、PBKDF2
D、RSA
回答错误，答案为 C

参考文档:存储用户密码应该使用什么加密算法？比较合适

九、开源协议

1. BSD类如Apache/BSD/MIT等 典型软件：Tomcat,OpenSSL 触发代码开源义务前提条件：无 开源要求和范围：无 规避开源方式：不涉及
2. MPL类如：MPL/EPL等 典型软件：FireFox,Eclipse 触发代码开源义务前提条件：产品集成使用该软件，并对外分发或销售产品对该软件进行了修改 开源要求和范围：若无修改，则无需开源；若对其进行了修改，需将修改的部分开源 规避开源方式：使用时不做任何修改
3. GPL类: LGPL 典型软件：Hibernate，glibc 触发代码开源义务前提条件：产品集成使用该软件，并对外分发或销售 开源要求和范围：软件本身须开源。具有传染性，与其静态链接部分的代码也必须以LGPL许可开源；动态链接则不被传染。 规避开源方式：动态链接使用，仅开源其软件本身即可，产品代码可免受传染。
4. GPL类: GPL 典型软件：Busybox，linux kernel 触发代码开源义务前提条件：产品集成使用该软件，并对外分发或销售 开源要求和范围：软件本身须开源。 具有传染性，与其有链接关系的代码都必须以GPL许可对外开源，即与该软件在同一进程中运行的代码都必须开源 规避开源方式：进程隔离，独立于产品进程运行，仅开源其软件本身即可，产品代码可免受传染
5. GPL类: AGPL相当于给GPL加了（Add）一个补丁，变成AGPL 典型软件：Berkeley_DB 触发代码开源义务前提条件：产品集成使用该软件 开源要求和范围：在GPL上增加了一条限制：即便不对外分发，只要在网络服务器上使用AGPL软件提供网络服务，就需要履行相关开源义务。例如： Berkeley_DB，即使没有“分发”动作，通过WEB形式为用户提供服务，也要履行对外开源义务。 规避开源方式：同GPL
6. GPL类: SSPL 典型软件：MongoDB 触发代码开源义务前提条件：产品将该软件做为服务或利用该软件的能力向公司外的第三方提供服务 开源要求和范围：软件本身须开源。 具有传染性，使用开源软件相关的服务组件也要开源。相对AGPL，任何试图将开源软件作为服务加以利用的组件，都必须开放用于提供此类服务的软件的源代码。 规避开源方式：谨慎使用！ 对于使用SSPL协议软件，向第三方提供服务会导致软件包整体开源。只能向公司内部人员开放。

十、密码学

源于题目

基于《密码算法应用规范》，Hash长度扩展攻击可以用下面哪些方法进行防护
A、HMAC-SHA2-256
B、RSA-SHA2-256
C、AES-GCM
D、HMAC-MD5
回答错误，答案为 ACD

导致hash扩展攻击的根源是采用MAC = H(key ∥ message)的方式生成MAC。 HMAC算法采用H(key ∥ H(key ∥ message))的方式获得MAC，消除了这个问题。因此C、D都对。 参见https://en.wikipedia.org/wiki/HMAC

而AES-GCM算法在计算MAC时，每一个密文分组都参与了MAC计算。攻击者在不知道密钥时，应该无法运算出扩展消息的MAC值。

基于《密码算法应用规范》,Hash长度扩展攻击可以用下面哪些方法进行防护

根据《密码算法应用规范》中提到的Hash长度扩展攻击（Hash length extension attack），这是一种基于HMAC（散列消息认证码）的攻击，它允许攻击者在不知道密钥的情况下修改消息的哈希值。

为了防护这种攻击，可以采用以下方法：

1. 使用安全的哈希算法，如SHA-256或SHA-512。
2. 使用密钥派生函数（如HKDF）来生成密钥。
3. 使用库函数，如HMAC，它们通常内置了对抗长度扩展攻击的保护机制。
4. 监测日志或网络流量，如果发现异常，应立即更换密钥。

以下是一个使用Python的HMAC示例代码，它应用了安全的哈希算法和密钥派生方法来防护Hash长度扩展攻击：

---

总结

未完待续