41.（13分）给定一个含 n（n>1））个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数是1;数组{1，2，3}中未出现的最小正整数是 4。要求∶
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
42.（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、OD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光缆的铺设费用。
请回答下列问题。
（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。
（2）题 42图可采用图的哪一种存储结构?给出求解问题（1）所使用的算法名称。
（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机 H1 直接连接在TL的路由器上，主机 H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组?
1. 已知表头元素为c的单链表在内存中的存储状态如下表所示。
地址|元素|链接地址
1000H |a |1010H
1004H |b |100CH
1008H |c |1000H
100CH |d |NULL
1010H |e |1004H
1014H | |
现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的"链接地址"依次是
A. 1010H,1014H,1004H
B. 1010H, 1004H,1014H
C. 1014H,1010H,1004H
D. 1014H,1004H,1010H
43.（8分）假定计算机的主频为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 总时间的百分比最多是多少?
2.已知一个带有表头结点的双向循环链表L，结点结构为
preV |data |next
，其中，prev和next分别是指向其直接前驱和直接后
继结点的指针。现要删除指针p所指的结点，正确的语句序列是
A.p->next->prev=p->prev; p->prev->next=p->prev; free (p);
B.p->next->prev=p->next; p->prey-> next=p->next; free (p);
C.p->next->prev=p->next; p->prev->next=p->prev; free (p);
D.p->next->prey=p->prey; p->prev->next=p->next; free (p);
44.（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。
根据题 44 图回答下列问题。
（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组号是多少?
3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1~～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1~9，则n至少是
A.2
B.3
C.4
D.5
45.（8分））请根据题44 图给出的虚拟储管理方式，回答下列问题。
（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么?
（2）寄存器 PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址?进程切换时，PDBR 的内容是否会变化?说明理由。同一进程的线程切换时，PDBR 的内容是否会变化?说明理由。
（3）为了支持改进型 CLOCK置换算法，需要在页表项中设置哪些字段?
4.有一个100阶的三对角矩阵M，其元素mij（1≤i<100，1≤j≤100）按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。元素m3030在N中的下标是
A.86
B.87
C.88
D.89
46.（7分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。
（1）该文件系统能支持的最大文件长度是多少? （给出计算表达式即可）
（2）文件系统用1M（1M=220）个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件?
（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和 F2最后一个簇的簇号需要的时间是否相同?为什么?
