[数据结构与算法]2012年-全国计算机-408统考-错题、难点总结

选择题

数据结构部分

1. P190 T2 做对,难点难题，总结
   
   考点：中缀转后缀的机器计算过程

当时这题没有用完整的计算来做，只做到了最多的括号在栈中，就选了
完整的流程如下：

中缀表达式转换后缀表达式过程：
①从左往右扫描中缀表达式，如果遇到操作数，则直接输出到表达式队列中
②如果遇到操作符，则把栈中优先级大于等于当前遇到的操作符的操作符依次弹出，遇到’(’，或者栈为空则停止弹出，再把该当前遇到的操作符入栈
③如果遇到’(‘界限符，则把栈中的运算符依次弹出，直到把’(‘左括号弹出为止。注意的是’)'右括号是不会入栈的，只用作代码的出栈判断符
④处理完所有的字符后，把运算符栈中的运算符依次弹出加入到表达式队列中

类似题目有：

空闲的时候我查了中缀转前缀的机算过程，过于复杂，嗯嗯！

2. P190 T3 做对,这题的结论在2011年真题 T5的时候有说过
   

给出前序和后序序列，虽然不能确定一颗二叉树，那么我们知道存在即是合理，肯定有它存在的意义，从前序和后序序列中，我们可以确定的是每两个点之间的关系–是祖先关系

如：这题中
通过先序序列a的位置和后序序列a的位置可以得出，a是b,c,d,e的祖先
因为后序遍历是最后才访问根的
而在通过其前序遍历的第二个结点e，通过在后序遍历中的e位置可得，e是b,c,d的祖先，那么这题就完成了，因为a,b,c,d,e都已经划分完集合，那么只要e直接和a根节点相连。

总结得到----太阳学长的肯定–善于思考

举一反三系列，对这道题进行加强：这道题的根节点只有一个孩子，我对这道题进行了加强，对根节点再加一个孩子。那么通过前序和后序遍历的序列怎么判断出来3和5是1的孩子，2和7是3的孩子，10是5的孩子呢？
前序序列：1，3，2，7，5，10
后序序列：2，7，3，10，5，1
通过前序序列第一个访问的元素来判断每一颗子树的祖先。
在前序序列中第一个访问的元素是1，那么通过后序遍历序列1的位置可以得到1是2，7，3，10，5的祖先。
在先序序列中第二个访问的元素是3，那么通过后序遍历序列3的位置可以得到3是2，7的祖先。
而因为3的子树已划定了范围了就是后序遍历3之前的序列，那么就在前序序列中跳过这些元素2和7都不是直接和1相连的，而前序序列是先访问根的，访问完3的子树，那么必定会访问1的右子树，且先访问自己的孩子，那么在前序序列中3的子树集合的下一个访问的元素就是根节点1的孩子。因此5就是根节点1的孩子，那么在后序遍历中找5所在的位置，就可以确定以根节点为5的元素集合了，划分时不包括已经划分集合的元素，如2和7已经划分到了3为根节点的子树中了，那么在后序遍历中5是10的祖先了。
到此就可以确定
①1的左右孩子了：1的直接相连的孩子左右孩子为3和5。
②3的孩子为2和7
③5的孩子为10


在划分完集合可以看到在
大集合中{1,3,2,7,5,10}
中集合{3,2,7}、{5,10}
小集合{2}、{7} 、{10} //下一级是上一级的子集，不算子集的根节点
可以看到
①在大集合{1,3,2,7,5,10}中的中集合{3,2,7}、{5,10}在前序和后序的位置是一样的，他们就是兄弟关系
②再来看小集合{2}、{7}在其对于的中集合{3,2,7}中前序和后序的位置是一样的，因此2和7是兄弟关系

这样就印证了一个结论：两个结点(都在同一子树集合中)/两个子集(都在一个更大的子集中)，如果两者的前后关系在前序和后序的顺序相同，那么这两者就是兄弟关系，而如果不同，那么就是父子关系，谁父谁子看先序。

3. P191 T10 做对,老考点了，弄一下
   

考点：通过一趟排序后，确定一个最终位置的算法有哪些！
Ⅰ选择排序：每轮选出一个最小的进行置换到i的位置
Ⅳ堆排序：把已经排序好的元素放在数组尾部，进行下一趟堆排序，前n-i个元素重新建堆
Ⅲ快速排序：每轮必有一个元素被确定。左递归一个，右递归一个
还有一个冒泡排序：把最大/最小的元素冒泡到端点，进行下一轮的排序

计算机组成原理部分

4. P192 T15 做对,主要是堆边界对齐的存储方式弄一下

考点：各种数据类型的字节大小、小端/大端存储方式、数据边界对齐
小端存储方式：低字节数据存低位、高字节数据存高位
大端存储方式：高字节数据存高位、低字节数据存低位，按人类的视角是最合理的
数据边界对齐方式，如果这个变量占x字节，那么它的起始字节也是x的倍数
int -4B ，按 字对齐(4字节)
char -1B，按字节对齐
short -2B，按半字对齐(2字节)
double -8B，按两个字对齐(8字节)
字长为32位=4B，半字为16位=2B
这里的0XC00D，13不能整除2 (必须是short字节大小的整数倍)，每个变量有自己的强迫症，起始地址必须是自己长度的整数倍才行
那么为什么要边界对齐呢？是从计组+操作系统的角度来看是为了一次性取出对应的数据，减少磁盘I/O，或者提高Cache的命中率

5. P192 T16 做对,对闪存弄一下

考点ROM存储器的特点
MROM-(MASK-ROM)掩模式只读存储器—只能由厂商设置，无法更改
PROM-(Programmable-ROM)可编程只读存储器–只能编写一次
?：
EPROM----(Erasable-Programmable-ROM)-可擦除可编程只读存储器
①UVEPROM----(Ultraviolet-Erasable-Programmable-ROM)-紫外线可擦除可编程只读存储器，全部擦除
②E²PROM–(电擦除可编程只读存储器)，只擦除特定的字

Flash Memory：闪存存储器----(应用在SD卡、U盘)
由MOS管组成，密度比RAM高，闪存在存之前需要先擦除然后再写入，因此写的速度要比读的速度慢

SSD----固态硬盘，408新增考点，由Flash芯片组成，可快速擦除重写

6. P192 T17 做对,注意两种不同的映射方式
   

如果按照王道书上的组相联映射方式的话，这些主存地址全都映射到了第0组，那么就只有访问的主存地址间隔不超过2时再次访问才能Cache命中，那么正常来说就只有访问到6的时候，下一次访问6间隔刚好为2，Cache命中，只命中了一次Cache，但是呢！这里采用了不同的映射方式，它采用了连续的存储空间映射到同一组，如这里采用二路组相联映射方式，那么主存地址
0~1 映射到0组
2~3 映射到1组
4~5 映射到0组
6~7 映射到1组
8~9 映射到0组
理解过程即可

7. P192 T19 错题！，已经对总线的内容忘记了

错误原因:只算了传输4个数据所需要的时间40ns，却没有计算传输地址所需要的时间
因为宽度是32bit，所以每次传输时传输32bit，传输32bit所需要的时间为一个时钟周期=10ns，因为采用了突发传输方式，因此其数据存储在连续的存储空间中，因此传输128bit，只需要1个首地址和传输4次数据，共传输了5次，总计50ns。

8. P192 T19 做对，采用的是排除+直接选
   

做题时的思路：
A记得是USB是即插即用的–如U盘-----直接排除了
B、C我直觉看应该是对的。
然后我看了D：就知道D不对了，因为在单片机STM32的时候，串口连接USB就是一位一位的传的，都说了是串行通信，怎么能一次传输2为数据呢？这不就荒谬绝伦的吗？直接选D

USB特性：
热拔插
即插即用
菊花链形式连接众多外设
可扩展好，如一个USB口可以使用一个USB扩展器连接更多的USB设备
传输速率高

操作系统部分

8. P193 T23 做对，要注意’发送’和’执行’的区别
   

①系统调用是可以发送在用户态的，但是执行时在内核态，应用程序只能通过系统调用(广义指令)，(程序接口-一组的系统调用)请求操作系统的服务，而且用户不能直接使用程序接口，只能通过编程代码来调用程序接口
②外部中断，可以发生在用户态，但是外部中断处理是在内核态执行
③进程切换： 进程切换与内核密切相关，因为进程切换需要用到PC程序计数器、通用寄存器等其他寄存器，并将其运行环境保存在进程的PCB中，然后将其PCB移入就绪队列、阻塞队列，根据进程调度算法在就绪队列中选出一个进程进行调度，更新其PCB，恢复其运行环境。
④缺页是可以发生在用户态的，但是缺页处理，需要在内核态执行，因为涉及到了外存、内存的数据交换

9. P193 T26 做对，已经对其流程模糊了
   

考点：I/O系统层次结构
软件肯定是靠近用户的，而且，越靠近用户的东西就越有逻辑
设备独立性性软件：功能是完成逻辑设备名到物理设备名之间的映射(查找逻辑设备表)，并通过物理设备名找到对应的驱动程序。
当时想着设备驱动程序就是用于外设与硬件进行沟通的东西，就是个翻译器。

计算机网络部分

10. P194 T34 做对，老考点了，搞一个

考点：“泄气工程”
①机械特性：物理连接的特性、接口的形状、引线数目、引脚数量
②电气特性：电压范围、传输速率、距离，通常都带有数字与功能特性区分
③功能特性：用文字描述一个电平的意义、接口等含义，无数字，通过文字描述一个功能
④规程特性/过程特性：规程和时序

11. P194 T36 做对，注意一个细节即可

对于使得信道利用率达到最高，就是在一个往返时间内，要尽可能能多发数据帧，尽可能得占用信道，把所有的窗口都用上发生那么信道的利用率是最高的，而为了尽可能的在一个往返的时间内把所有的发生窗口都用上，那么就尽可能地使用数据帧短的如这道题的128B，因为越小的数据，发送完后就可能有更多的时间发送下一个，尽可能的占用信道。

12. P195 T37 错题！总结
    

13. P195 T40 对，但这个是应用层的重点

读之前都是STMP
用户想读的时候再使用POP3读

综合题

数据结构部分

1. P195 T41
   

考点：Huffman+二路归并的思想可以使得在最坏的情况下获得最佳的合并效率-----在DS树的章节中弄过了，不再重复

计算机组成原理部分

2. P196 T43 (有一部分错题)
   

第一问的第三小问：主存带宽至少达到多少才能满足CPU的访问要求----错题
通过第一问的第二小问可得Cache缺失的次数=3x10⁵次，每次Cache缺失之后，都要取访问主存，而Cache与主存之间交换的块大小为16B，因此主存的带宽=16Bx3x10⁵=4.8MB/S
错误原因：我用了32bit来算。。裂开了，现在才发现错得有多离谱，3x10⁵是缺失次数啊！和存储器的总线宽度有什么关系。当时可能想到了总线的带宽。。串了
总线带宽=总线宽度x总线频率

第四问-----错题
通过流水线可以看到，当过了T之后，每经过一个t就完成一个存储体的存取，因此为了使得主存的带宽最大，那么就要在一个存储周期内把全部的体都存取一遍，而一个访问一个存储区的数据大小是32bit=4B，因此最大的带宽=4x4B/50ns=320MB/S,----当流水线流动起来之后每个存储体都能给CPU提供32bit
错误原因：只算了一个存储体的带宽，没有 x4

3. P196 T44 (有一部分错题)
   

这题我挂在了第四问的细节上。哎果然是细节决定成败啊！！！！！

我这里只考虑了I2和I3的关系，却没有考虑I3与I1的关系，I3和I2是没有关系的，只与I1有关系，因为要左移，我这里看错了，因此，I3的ID只需要I1的WB之后即可，所以只需17个时钟周期

操作系统

4. P196 T46 (有一部分错题)
   

第二问的第一小问----错题，二轮的时候做错了，现在还是做错了，该打
这里题目的意思是采用了连续分配+直接索引分配的方式，所以不能只看一个分配方式来算它的单个文件长度了
连续分配：块数占2B=16bit，因此连续分配的块最多=2¹⁶个块
而直接索引结构每个索引项占6B，而只剩下了504B，因此直接索引项的个数=504B/6B=84个
因此总的单个文件最大长度=(2¹⁶ + 84)*1KB=2²⁶B+84KB

计算机网络部分

5. P198 T47 这题在传输层的时候已经弄过了，不再重复
   
   

遇到这种混合层，给出IP地址，先把IP地址转换成16进制(方便找)，用于查表
1）①通过IP分组结构所示，源IP地址在第13字节~16字节，目的IP地址在第17 ~20字节，查表即可
②考到了TCP建立的过程
①SYN=1，seq=x
②SYN=1，seq=y，ACK=1，ack=x+1
③ACK=1，seq=x+1，ack=y+1

2)考点:在TCP建立完成的基础,完成数据传输，可以看出1，2，3用于完成TCP连接的建立过程，而第三次握手的时候已经开始传输数据了
H主机在编号3的发送报文的第5字节~第8字节为seq=0X 84 6b 41 c6
ack=OX e0 59 9f f0(期待主机S发来的报文序号)

而编号5的报文正好是主机S发送给主机H的报文且其seq=OX e0 59 9f f0(响应了主机H)，而ack=seq=0X 84 6b 41 d6（说明主机S已经接收到了0X 84 6b 41 d6之前的报文了，并期待收到下一个的序号报文），那么就能算出主机S接收了0X 84 6b 41 d6 -1 -0X 84 6b 41 c6 +1=0x10=16B
3）送分题：考点：TTL的作用：每次经过一个路由器TTL-1，当TTL=0的时候该报文的生命周期就用完了，就会从链路上消失，并向源主机发送一个ICMP差错报文