2018年408统考真题及答案(含综合题解析)

2024年1月22日发(作者：好看的汽车图片大全大图)

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）1.若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：（1）从S1中依次弹出两个操作数a和b；（2）从S2中弹出一个运算符op；（3）执行相应的运算bopa；（4）将运算结果压入S1中。假定S1中的操作数依次是5,8,3,2（2在栈顶），S2中的运算符依次是*,-,+（+在栈顶）。调用3次F()后，S1栈顶保存的值是。A.-15B.15C.-20D.202.现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是。A.1,2,5,6,4,3B.2,3,4,5,6,1C.3,4,5,6,1,2D.6,5,4,3,2,13.设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是。A.50B.51C.55D.664.设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是。A.2k-1B.2kC.k2D.2k-15.已知字符集{a,b,c,d,e,f}，若各字符出现的次数分别为6,3,8,2,10,4，则对应字符集中各字符的哈夫曼编码可能是A.00,1011,01,1010,11,100。B.00,100,110,000,0010,01C.10,1011,11,0011,00,010D.0011,10,11,0010,01,0006.已知二叉排序树如下图所示，元素之间应满足的大小关系是。1

A.x1

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题A.11101100，11101100C.11101100，01101100B.D.01101100，1110，01101100。D.1、204817.假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为保证其地址引脚数最少，并尽量减小刷新开销，则r、c的取值分别是A.2048、1B.64、32C.32、6418.按字节编址的计算机中，某double型数组A的首地址为2000H，使用变址寻址和循环结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是。A.25B.32C.64D.10019.减法指令“subR1,R2,R3”的功能为“(R1)-(R2)→R3”，该指令执行后将生成进位/借位标志CF和溢出标志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，则该减法指令执行后，CF与OF分别为。=0,OF==1,OF==0,OF==1,OF=120.若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各功能部件所需时间分别为80ps、50ps、50ps、70ps和50ps，采用流水线方式执行指令，流水段寄存器延时为20ps，则CPU时钟周期至少为。D.100psA.60psB.70psC.80ps21.下列选项中，可提高同步总线数据传输率的是。I.增加总线宽度III.支持突发传输A.仅I、IIII.提高总线工作频率IV.采用地址/数据线复用B.仅I、II、IIIC.仅III、IV。D.I、II、III和IV22.下列关于外部I/O中断的叙述中，正确的是A.中断控制器按所接收中断请求的先后次序进行中断优先级排队响应中断时，通过执行中断隐指令完成通用寄存器的保护只有在处于中断允许状态时，才能响应外部设备的中断请求D.有中断请求时，CPU立即暂停当前指令执行，转去执行中断服务程序23.下列关于多任务操作系统的叙述，正确的是I.具有并发和并行的特点II.需要实现对共享资源的保护III.需要运行在多CPU的硬件平台上A.仅IB.仅IIC.仅I、IID.I、II、III24.某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1?s。在T时刻就绪队列中有3个进程P1、P2和P3，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。进程P1P2P3等待时间30?s15?s18?s需要的CPU时间12?s24?s36?s优先权103020。若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，系统的平均周转时间为。3

A.54?sB.73?sC.74?sD.75?s25.属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下。thread1movR1,xincR1movx,R1//(x)→R1//(R1)+1→R1//(R1)→xmovR2,xincR2movx,R2thread2//(x)→R2//(R2)+1→R2//(R2)→x在所有可能的指令执行序列中，使x的值为2的序列个数是。A.1B.2C.3D.426.假设系统中有4个同类资源，进程P1,P2和P3需要的资源数分别为4,3和1，P1,P2和。P3已申请到的资源数分别为2,1和0，则执行安全性检测算法的结果是A.不存在安全序列，系统处于不安全状态B.存在多个安全序列，系统处于安全状态C.存在唯一安全序列P3,P1,P2，系统处于安全状态D.存在唯一安全序列P3,P2,P1，系统处于安全状态27.下列选项中，可能导致当前进程P阻塞的事件是I.进程P申请临界资源II.进程P从磁盘读数据III.系统将CPU分配给高优先权的进程A.仅IB.仅IIC.仅I、IID.I、II、III。28.若x是管程内的条件变量，则当进程执行()时所做的工作是A.实现对变量x的互斥访问B.唤醒一个在x上阻塞的进程C.根据x的值判断该进程是否进入阻塞状态D.阻塞该进程，并将之插入x的阻塞队列中29.当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是I.内核中时钟变量的值II.当前进程占用CPU的时间III.当前进程在时间片内的剩余执行时间A.仅I、IIB.仅II、IIIC.仅I、III。D.I、II、III30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法中，不会导致磁臂黏着的是A.先来先服务（FCFS）C.扫描算法（SCAN）I.提前读III.延迟写A.仅I、on方法B.最短寻道时间优先（SSTF）D.循环扫描算法（CSCAN）。II.为文件分配连续的簇IV.采用磁盘高速缓存B.仅II、IIIC.仅I、III、IV。C.信号量方法dSet指令。指令。。31.下列优化方法中，可以提高文件访问速度的是D.I、II、III、IV32.下列同步机制中，可以实现让权等待的是33.下列TCP/IP应用层协议中，可以使用传输层无连接服务的是4

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题34.下列选项中，不属于物理层接口规范定义范畴的是A.接口形状A.发送确认帧C.使用多个MAC地址B.引脚功能C.物理地址。D.信号电平。802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是B.采用二进制指数退避D.交换RTS与CTS帧。36.主机甲采用停-等协议向主机乙发送数据，数据传输速率是3kbps，单向传播延时是200ms，忽略确认帧的传输延时。当信道利用率等于40%时，数据帧的长度为A.240比特B.400比特C.480比特D.800比特37.路由器R通过以太网交换机S1和S2连接两个网络，R的接口、主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址、H2收到的封装P的以太网帧的源MAC地址分别是。A.00-a1-b2-c3-d4-62,00-1a-2b-3c-4d-52B.00-a1-b2-c3-d4-62,00-a1-b2-c3-d4-61C.00-1a-2b-3c-4d-51,00-1a-2b-3c-4d-52D.00-1a-2b-3c-4d-51,00-a1-b2-c3-d4-6138.某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为35.230.32.0/21,将该4条路由聚合后的目的网络地址为35.230.40.0/21,35.230.48.0/21和35.230.56.0/21，A.35.230.0.0/19B.35.230.0.0/20。D.校验和。文本C.35.230.32.0/19D.35.230.32.0/协议实现分用（demultiplexing）时所依据的头部字段是A.源端口号图像B.目的端口号视频C.长度文件40.无须转换即可由SMTP协议直接传输的内容是二、综合应用题（第41～47小题，共70分）41.（13分）给定一个含n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。。42.（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH8个城市，题42图中无向边上的权值表示两个城市间备选光纤的铺设费用。5

题42图请回答下列问题。，（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示）并计算相应方案的总费用。（2）题42图可采用图的哪种存储结构？给出求解问题（1）所使用的算法名称。（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？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总时间的百分比最大是多少？44.（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。根据题44图回答下列问题。（1）主存物理地址占多少位?（2）TLB采用什么映射方式？TLB是用SRAM还是用DRAM实现？（3）Cache采用什么映射方式？若Cache采用LRU替换算法和回写（WriteBack）策略，则Cache每行中除数据（Data）、Tag和有效位，还应有哪些附加位？Cache的总容量是多少？Cache中有效位的作用是什么？（4）若CPU给出的虚拟地址为0008C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由。若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache组号是多少？6

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题题44图45.（8分）请根据题44图给出的虚拟存储管理方式，回答下列问题。（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？46.（7分）某文件系统采用索引结点存放文件的属性和地址信息，簇大小为4KB。每个文件索引结点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可。）（2）文件系统用1M（1M=220）个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个图像文件？（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？47.（7分）某公司的网络如题47图所示。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。请回答下列问题。（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？7

题47图（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？2018年计算机学科专业基础综合试题参考答案一、单项选择题1.9．17．25．33．BCCBB2．10．18．26．34．CDBAC3．11．19．27．35．AAACD4．12．20．28．36．ADDDD5．13．21．29．37．ACBDD6．14．22．30．38．CACAC7．15．23．31．39．DACDB8．16．24．32．40．BBDCD41.解答：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

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题for(i=0;i0&&A[i]<=n)B[A[i]-1]=1;for(i=0;i

比较器，没有映射规则，只要空闲就行。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位相同，即为B。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此该地址所在的主存映射到Cache的组号为3。45.解答：1）由图可知，地址总长度为32位，高20位为虚页号，低12位为页内地址，且虚页号高10位为页目录号，低10位为页号。展开成二进制表示为故十六进制表示为01806008H。2）PDBR为页目录基址地址寄存器（Page-DirectoryBaseRegister），其存储页目录表物理内存基地址。进程切换时，PDBR的内容会变化；同一进程的线程切换时，PDBR的内容不会变化。每个进程的地址空间、页目录和PDBR的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新PDBR。同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。3）改进型CLOCK置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。46.解答：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。可表示的文件总个数受限于文件索引结点总个数，故能10

2018年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题存储64M个大小为5600B的图像文件。（3）文件F1的大小为6KB<4KB×8=32KB，故获取文件F1的最后一个簇的簇号只需要访问索引结点的直接地址项。文件F2的大小为40KB，4KB×8<40KB<4KB×8+4KB×1024，故获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。47.解答：）广播地址是网络地址中主机号全1的地址（主机号全0的地址代表网络本身）1。销售部和技术部均分配了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台。）判断分片的大小，需要考虑各个网段的MTU，而且注意分片的数据长度必须是8B的2整数倍。由题可知，在技术部子网内，MTU=800B，IP分组头部长20B，最大IP分片封装数据的字节数为?(800-20)/8?×8=776。至少需要的分片数为?(1500-20)/776?=2。第1个分片的偏移量为0；第2个分片的偏移量为776/8=97。11