某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。 
（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可） 
（2）文件系统用1M（1M=220）个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件？ 
（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？

请根据图给出的虚拟储管理方式，回答下列问题。

 
（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？ 
（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。 
（3）为了支持改进型 CLOCK置换算法，需要在页表项中设置哪些字段？

某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如图所示。

根据图回答下列问题。  
（1）主存物理地址占多少位？ 
（2）TLB采用什么映射方式？TLB用SRAM还是DRAM实现？ 
（3）Cache采用什么映射方式？若 Cache采用LRU替换算法和回写（Write Back）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？ 
（4）若CPU给出的虚拟地址为0008 C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由，若CPU给出的虚拟地址为0007 C260H，则该地址所在主存块映射到的Cache组号是多少？

假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。 
（1）若设备A采用定时查询I/O方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百分比至少是多少？ 
（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？ 
（3）若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输人/输出的时间占CPU总时间的百分比最多是多少？

拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题。 
（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。 
（2）题图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。  
（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数是1；数组{1，2，3}中未出现的最小正整数是4。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。