2009

题目5：

完全二叉树的第六层有8个叶结点，根据完全二叉树的性质可得，叶结点只可能出现在最低层和次底层，也就是倒数第二层。问该结点个数最多是多少个，直接得出叶结点出现在次高层，一共6+1=7层，1-5层一共有2^5-1=31个，第六层应有32个，8个无孩子，第七层还有(32-8)\times 2=48个 一共31+32+48=111个

题目6：

树、森林转化为二叉树：森林先单独转换，后将森林的每个树的根节点连起来。

题目10：

根据数据元素序列，判断A选项，最大的两个或最小的两个元素没有冒泡到它的位置上，排除A。选择排序，也不符合。进行二路归并排序后应该是4，4，1的子表且表内有序。综上，只符合原始序列为11、12、13、7、8、9、23、4、5，第一趟插入11，第二趟插入12后的结果。

题目14：

每个主存块32B，按字节编址，那么一个主存块就有32个存储单元，主存129号应该位于\lfloor\frac{129}{4}\rfloor​=4号主存块，根据映射关系，一共16/2=8组，其对应组号应为 4 mod 8=4

题目17：

题目27：

段号为8位，总共地址长度位32位，最大可用32-8=24位为段长。即2^{24}B。

题目31：

由图可知，删除F1，即删除user1，user3仍然在使用F1.删除后不影响软链接（复制的原有的count值），F2的值仍为1， F3的值变为2-1=1。user1、2、3分别指F1F2F3。

题目36：

以太网交换机属于数据链路层的设备，数据链路层的帧依据目的物理地址进行转发。

题目37：

采用CSMA/CD协议，为了能够及时检测到碰撞，数据的传输时间要大于争用期，即往返传播时延。设数据帧长为t，两个站点的距离为x,\frac{t-800}{1\times10^9}\ge2\times\frac{x-m}{2\times10^8} 即m\le80m​。所以两个站点之间的距离至少要减少80m。

题目46：

访问页面4KB，占12位，根据虚地址得出一共16位，页号占4位。高四位为页号

1.访问2362H，页号为2，首先访问TLB为空，然后访问页表，再访问页框号拼接成的主存地址，一共10+100+100=210ns。

2.访问1565H，页号为1，缺页，首先访问TLB为空，访问页表缺页，缺页处理，调入。访问TLB命中，然后访问主存。一共10ns+100ns+100000000ns+10ns+100ns=100000220ns。（缺页处理完后从TLB开始访问，此时已经调入）。

3.访问25A5H，访问TLB命中，访问主存，一共10ns+100ns=110ns。

根据最近最少使用置换算法，将0号页面置换出来，拼接后的物理地址为101565H。

题目47：

1.划分为两个子网，用一位主机号作为子网号，剩下7位，其中全0位本地网络地址，全1为广播地址，每个子网一共有 2^7-2=126个>120个。局域网1为：202.118.1.1~202.118.1.126。局域网2为：202.118.1.129-202.118.254。

2.

如果对于互联网中的路由，如果没有确切的目的网络地址，则使用默认路由，将目的地址在已知网络之外的分组依据默认路由转发。

3.