计算机综合408真题与解析

给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。
要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。
解析：
（1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1～n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1～n+1，当A中n个数恰好为1～n时返回n+1。当数组A中出现了小于等于0或大于n的值时，会导致1～n中出现空余位置，返回结果必然在1～n中，因此对于A中出现了小于等于0或大于n的值可以不采取任何操作。经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令B[A[i]-1]=1；否则不进行操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1～n之间。若B[i]全部不为0，返回i+1（跳出循环时i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。 Int findMissMin(int A[],int n) { int i,*B;//标记数组 B=(int*)malloc(sizeof(int)*n);//分配空 memset(B,0,sizeof(int)*n);//赋初值为0 for(i=0;i<n;i++) if(A[i]>0&&A[i]<=n)//若A[i]的值介于1～n，则标记数组B
```
 B[A[i]-1]=1;
```
for(i=0;i<n;i++)//扫描数组B，找到目标值
if(B[i]==0)break;
returni+1;//返回结果
}
（2）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。
假定计算机的主频为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总时间的百分比最大是多少？
解析：
1）程序定时向缓存端口查询数据，由于缓存端口大小有限，必须在传输完端口大小的数据时访问端口，以防止部分数据未被及时读取而丢失。设备A准备32位数据所用的时间为4B/2MB=2μs，所以最多每隔2μs必须查询一次，每秒的查询次数至少是1s/2μs=5×105，每秒CPU用于设备A输入/输出的时间至少为5×105×10×4=2×107个时钟周期，占整个CPU时间的百分比至少是2×107/500M=4%。
2）中断响应和中断处理的时间为400×(1/500M)=0.8μs，这时只需判断设备B准备32位数据要多久，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新，造成丢失。经过计算，设备B准备32位数据所用的时间为4B/40MB=0.1μs，因此设备B不适合采用中断I/O方式。
3）在DMA方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制的。设备B每秒的DMA次数最多为40MB/1000B=40000，CPU用于设备B输入/输出的时间最多为40000×500=2×107个时钟周期，占CPU总时间的百分比最大为2×107/500M=4%。
某文件系统采用索引结点存放文件的属性和地址信息，簇大小为4KB。每个文件索引结点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。
（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可。）
（2）文件系统用1M（1M=220）个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个图像文件？
（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？
解析：
（1）簇大小为4KB，每个地址项长度为4B，故每簇有4KB/4B=1024个地址项。最大文件的物理块数可达8+1×1024+1×10242+1×10243，每个物理块（簇）大小为4KB，故最大文件长度为(8+1×1024+1×10242+1×10243)×4KB=32KB+4MB+4GB+4TB。
（2）文件索引结点总个数为1M×4KB/64B=64M，5600B的文件占2个簇，512M个簇可存放的文件总个数为512M/2=256M。可表示的文件总个数受限于文件索引结点总个数，故能存储64M个大小为5600B的图像文件。
（3）文件F1的大小为6KB<4KB×8=32KB，故获取文件F1的最后一个簇的簇号只需要访问索引结点的直接地址项。文件F2的大小为40KB，4KB×8<40KB<4KB×8+4KB×1024，故获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。

相关推荐

热点推荐

免费获取考研大礼包