2018年考研408计算机统考真题在线评测（附答案）

第41题

给定一个含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。

（2）

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;
return i+1;//返回结果
}

（3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。

第42题

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

请回答下列问题。

（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用。

（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。

（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

答：

（1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动Prim算法或Kruskal算法作图。注意本题最小生成树有两种构造，如下图所示。

方案的总费用为16。

（2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用Prim算法（或kruskal算法）。

（3）TTL=5，即IP分组的生存时间（最大传递距离）为5，方案1中TL和BJ的距离过远，TTL=5不足以让IP分组从H1传送到H2，因此H2不能收到IP分组。而方案2中TL和BJ邻近，H2可以收到IP分组。

第43题

假定计算机的主频为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%。

第44题

某计算机采用页式虚拟存储管理方式，按字节编址。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组号是多少？

答：（1）物理地址由实页号和页内地址拼接，因此其位数为16+12 = 28；或直接可得20+3+5 = 28。

（2）TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB中每项都有一个比较器，没有映射规则，只要空闲就行。TLB采用静态存储器SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。

（3）图中可以看到，Cache中每组有两行，故采用 2 路组相联映射方式。因为是2路组相联并采用LRU替换算法，所以每行（或每组）需要1位LRU位；因为采用回写策略，所以每行有1位修改位（脏位），根据脏位判断数据是否被更新，如果脏位为1则需要写回内存。28 位物理地址中Tag字段占20位，组索引字段占3位，块内偏移地址占5位，故Cache共有23 = 8组，每组2行，每行有25 = 32B；故Cache总容量为8×2×(20+1+1+1+32×8) = 4464位 = 558字节。

Cache中有效位用来指出所在Cache行中的信息是否有效。

（4）虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找TLB表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号008CH恰好在TLB表中对应实页号 0040H（有效位为1，说明存在），虚拟地址的后3位为页内地址040H，则对应的物理地址是 0040040H。物理地址为0040040H，其中高20位00400H为标志字段，低5位00000B为块内偏移量，中间3位010B为组号2，因此将00400H与Cache中的第2组两行中的标志字段同时比较，可以看出，虽然有一个Cache行中的标志字段与00400H相等，但对应的有效位为0，而另一Cache行的标志字段与00400H不相等，故访问Cache不命中。

因为物理地址的低12位与虚拟地址低12位相同，即为0010 0110 0000B。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此虚拟地址0007 C260H所在的主存映射到Cache组号为3。

第45题

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

（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？

（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。

（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？

答：

（1）由图可知，地址总长度为32位，高20位为虚页号，低12位为页内地址。且虚页号高10位为页目录号，低10位为页号。展开成二进制则表示为：0000 0001 1000 0000 0110 0000 0000 1000 B

故十六进制表示为0180 6008H。

（2）PDBR为页目录基址地址寄存器（Page-Directory Base Register），其存储页目录表物理内存基地址。进程切换时，PDBR的内容会变化；同一进程的线程切换时，PDBR的内容不会变化。每个进程的地址空间、页目录和PDBR的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新PDBR。同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。

（3）改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。

第46题

某文件系统采用索引节点存放文件的属性和地址信息，簇大小为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的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。

第47题

某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销告部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。

请回答下列问题。

（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？

（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？

答：

（1）广播地址是网络地址中主机号全1的地址（主机号全0的地址，代表网络本身）。销售部和技术部均分配了192.168.1.0/24的IP地址空间，IP地址的前24位为子网的网络号。于是在后8位中划分部门的子网，选择前1位作为部门子网的网络号。令销售部子网的网络号为0，技术部子网的网络号为1，则技术部子网的完整地址为 192.168.1.128；令销售部子网的主机号全1，可以得到该部门的广播地址为192.168.1.127。每个主机仅分配一个IP地址，计算目前还可以分配的主机数，用技术部可以分配的主机数，减去已分配的主机数，技术部总共可以分配计算机主机数为27-2 = 126（减去全0和全1的主机号）。已经分配了208-129+1 = 80个，此外还有1个IP地址分配给了路由器的端口(192.168.1.254)，因此还可以分配126-80-1=45台。

（2）判断分片的大小，需要考虑各个网段的MTU，而且注意分片的数据长度必须是8B的整数倍。由题可知，在技术部子网内，MTU = 800B，IP分组头部长20B，最大IP分片封装数据的字节数为⌊(800-20)/8⌋×8 = 776。至少需要的分片数为⌈(1500-20)/776⌉ = 2。第1个分片的偏移量0；第2个分片的偏移量为 776/8 = 97。