◾1.若任一字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数≥2）的不等长编码，每个字符的编码均为二进制的0,1序列，最长为L位，且具有前缀特性。请回答下列问题：
（1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？
（2）基于你所设计的数据结构，简述从0/1串到字符串的译码过程。
（3）简述判定某字符集的不等长编码是否具有前缀特性的过程。
解析：
（1）二叉树或者哈夫曼树。普通的二叉树也可以设计前缀编码，哈夫曼树会使总长最小，是对前者的优化。
（2）将所有的字符信息存储到二叉树的叶子结点上，且约定左分支表示字符0，右分支表示字符1.则可将根节点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。从根节点出发将0/1串沿着分支探查下去，遇到带有信息的叶子结点即为一个字符，然后再从根节点出发，以此类推直至0/1串全部译码为字符串。
（3）只需判定存储有字符信息的节点是否全部为叶子结点即可。若存储有某个字符信息的节点非叶子结点，即有子节点，那么它的0/1编码一定是它孩子节点0/1编码的前缀，违反了前缀特性。

◾2.假定主存地址为32位，按字节编址，指令Cache和数据Cache与主存之间均采用8路组相联映射方式，直写写策略和LRU替换算法，主存块大小为64B，数据区容量各为32KB。开始时Cache均为空，请回答下列问题：
（1）Cache每一行中标记（Tag）、LRU位各占几位？是否有修改位？
（2）有如下C语言程序段：
For（k=0;k<1024;k++)
S[k]=2*s[k];
若数组S及其变量k均为int型，int型数据占4B，变量k分配在寄存器中，数组s在主存中的起始地址为0080 00C0H，则该程序段执行过程中，访问数组S的数据Cache缺失次数为多少？
（3）若CPU最先开始的访问操作是读取主存单元0001 003H中的指令，简要说明从Cache中访问该指令的过程，包括Cache缺失处理过程。
解析：
（1）主存地址为32位，其中6位为块内地址。标记：32-6-6=20位，LRU：3位，直写写策略无修改位。
（2）在该程序的执行过程中，产生一次缺失时会更新Cache中的16块，之后的15次访问均命中Cache，故平均每16次访问Cache就会产生一次缺失，K的范围为1024，即共1024次访问Cache，Cache缺失次数=1024/16=64次。
（3）CPU访指的大致过程：CPU发出读请求时，若访存地址在Cache中命中，就将此地址转换成Cache地址，直接对Cache进行读操作，与主存无关；若Cache不命中，则仍需访问主存，并将此字所在的一块一次性从主存调入Cache，若此时Cache已满，就根据LRU替换算法，用这个块替换Cache中的一块信息。