《2018年计算机408统考真题解析.pdf》由会员分享，可在线阅读，更多相关《2018年计算机408统考真题解析.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2018年计算机学科专业基础综合试题参考答案一、单项选择题1.9.17.25.33.BCCBB 2.10.18.26.34.CDBAC 3.11.19.27.35.ADDDD AAACD 4.12.20.28.36.ACBDD 5n江泗扛6.14.22.30.38.CACAC 7.15.23.31.39.BBDCD DACDB 8.16.24.32.40.1.解析：第一次调用：从S1中弹出2和3;从S2中弹出；执行3+2=5;将5压入S1中，第一次调用结束后S1中剩余5,8,5(5在栈顶），S2中剩余，（在栈顶）。第二次调用：O从S1中弹出5和8;从S2中弹出；执行8-5=3;将3压入SI中，
2、第二次调用结束后S1中剩余5,3(3在栈顶），S2中剩余。第三次调用：从S1中弹出3和5;从S2中弹出；执行5x3=15;将15压入S1中，第三次调用结束后S1中仅剩余15(栈顶），S2为空。故选B。2.解析：A的操作顺序：。B的操作顺序：CDCDCDCDCD。D的操作顺序：。对千C:首先输出3,说明l和2必须先依次入栈，而此后2肯定比1先输出，因此无法得到1,2的输出顺序。3.解析：数组N的下标从0开始，第一个元素m1,1对应存入n。，矩阵M的第一行有12个元素，第二行有11个，第三行有10个，第四行有9个，第五行有8个，所以m6,6是第12+11+10+9+8+1=51个元素，下标应为50
3、,故选A。4.解析：非叶结点的度均为2,且所有叶结点都位于同一层的完全二叉树就是满二叉树。对千一棵高度为h的满二叉树（空树h=O),其最后一层全部是叶结点，数量为2h-1;总结点数为2h-I。因此当2h-=k时，可以得到2h-I=2k-l。5.解析：构造一棵符合题意的哈夫曼树，如下图所示。由此可知，左子树为o,右子树为1,故答案为A。6.解析：根据二叉排序树的特性：中序遍历(LNR)得到的是一个递增序列。图中二叉排序树的中序遍历序列为Xi,X3,X5,X4,X2,可知X35X407.解析：拓扑 排序每次选取入度为0的结点输出，经观察不难发现拓扑序列前两位一定是1,5或5,1(因为只有1和5的入
4、度均为o,且其他结点都不满足仅有1或仅有5作为前驱）。因此D显然错误。8.解析：m阶B树的基本性质：根结点以外的非叶结点最少 含有m/21-1个关键字，代入m=3得到 每个 非叶结点中 最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。此时其树形与h=5的满二叉树相同，可求得关键字最少为31个。9.解析：根据题意，得到的HT如下：二2 34 5 643 15 ASL成功=(1+2+3)/3=2。10.解析：初始序列：8,3,9,11,2,1,4,7,5,10,6 第一趟：1,3,7,5,2,6,4,9,11,10,8第二趟：I I I I I I I I I I I1,
5、2,6,4,3,7,5,8,11,10,9 I I I I I I I I I I I 第一趟分组：8,1,6;3,4;9,7;11,5;2,.10;间隔为5,排序后组内递增。第二趟分组：1,5,4,10;3,2,9,8;7,6,11;间隔为3,排序后组内递增。故答案选D。11.解析：要熟练掌握建堆、堆的调整方法，从序列末尾开始向前遍历，变换过程如下图所示。6)6)/.)一5气；。三？12.解析：对于I,二进制由千只有0,1 两种数值，运算规则较简单，都是通过ALU部件转换成加法运算。对于 II,二进制只需要高电平和低电平两个状态就可以表示，这样的物理器件很容易制造。对于 III,二进制与逻辑
6、量相吻合。二进制的 0 和1正好与逻辑量的“真”和“假”相对应，因此用二进制数表示二值逻辑显得十分自然，采用逻辑门电路很容易实现运算。13.解析：利用补码转换成原码的规则：负数符号位不变数值位取反加 1;正数补码等于原码。两个机器数对应的原码是x凡,=80000021H,对应的数值是-33,y原=y补=00000041H=65。排除A、D 选项。x-y直接利用补码 减法准则，x补-y补=x补+-yJ补，-y的补码是连同符号位取反加1,最终减法变成加法，得出结果为FFFFFF9EH。14.解析：IEEE754 单精度浮点数的符号位、阶码位、尾数位（省去正数位 1)所占的位数分别是1、8、23 位
7、。最 小正数，数符位取O,移码的取值范围是1254,取1,得阶码值 1一127=-126 Cl27为我们规定的偏置值），尾数取全O,最终推出最小规格化正数为A选项。15.解析：按字节编址，采用小端方式，低位的数据存储在低地址位、高位的数据存储在高地址位，并且按照一个字节相对不变的顺序存储。由题意知机器代码的地址是递减的，存储 0 的位数是后32位，那么我们只需要把-64 的补码按字节存储在其中即可，而-64 表示成 32 位的十六进制数是FFFFFF CO,根据小端方式的特点，高字节存储在低地址，就是CO FF FF FF,故选A。16.解析：逻辑移位：左移和右移空位都补o,并且所有数字参与移
8、动。算术移位：符号位不参与移动，右移空位补符号位，左移空位补0。根据该规则，轻松选出B 选项。17.解析：由题意，首先根据 DRAM采用的是行列 地址线复用技术，我们尽量选用行列差值不要太大的。对于B、C 选项，地址线只需 6 根（取行或列所需地址线的最大值），轻松排除A、D 选项。其次，为了 减小刷新开销，而 DRAM一般是按 行刷新的，所以应选行数值较少的，答案为C。18.解析：根据变址寻址的公式EA=(IX)+A,则(IX)=2100H-2000H=IOOH=256,sizeof(double)=8（双精度浮点数用8 位字节表示），因此数组的下标为256/8=32,答案选B。19.解析：
9、x旷y补=x补+-y压-R2J补=00000010H,很明显Rl 补+-R2 J补的最高位进位和符号位进位都是1(当最高位进位和符号位进位的 值不相同 时才产生溢出），可以判断溢出标志OF为0。同时，减 法操作只需判断借位标志，Rl大于R2,所以借位标志为O,综上选A。20.解析：指令流水线的每个流水段 时间单位为时钟周期，题中指令流水线的指令需要用到AE五个部件，所以每个流水段时间应取：最大部件时间80ps,此外还有寄存器延时为20ps,则CPU时钟周期至少是lOOps。答案选D。21.解析：总线数据传输率总线工作频率x总线带宽（总线宽度/8),所以 I 和II会影响总线数据传输率。采用突发
10、传输方式（也称猝发传输），在一个总线周期内传输存储地址 连续的多个数据字，从而提高了传输效率。采用地址I数据线复用只是减少了线的数量，节省了成本，并不能提高传输率。22.解析：中断优先级由屏蔽字决定，而不是根据请求的先后次序，因此 A错误。中断隐指令完成的淘宝店铺：光速考研工作室工作有：关中断；保存断点；引出中断服务程序，通用寄存器的保护由中断服务程序完成，B错误。中断允许状态即开中断后，才能响应中断请求，C正确。有中断请求时，先要由中断隐指令完成中断前程序的状态保存，D错误。23.解析：多任务操作系统可以 在同一时间内运行 多个应用程序，故I正确。多个任务必须互斥地访问共享资源，为达到这一目
11、标必须对共享资源进行必要的保护，故II正确。现代操作系统都是多任务的（主要特点是并发和并行），并不一定需要运行在多CPU的硬件上，单个CPU也可以满足要求，III错误。综上所述，I、II正确，III错误，故选C。24.解析：由优先权可知，进程的执行顺序为P2-P3-P1oP.2的周转时间：1+15+24=40s P3的周转时间：18+1+24+1+36=80sP1的周转时间：30+1+24+1+36+1+12=105s平均周转时间：(40+80+105)/3=225/3=75s,故选D。25.解析：仔细阅读两个线程代码可知，threadl和thread2均是对x进行加1操作，x初始值为o,若要
12、使得最终X=2,只有先执行threadl 再执行thread2,或先执行thread2再执行threadl,故只有2种可能，选B。26.解析：由题中数据可知，仅剩最后一个同类资源，若将其分给P1或P2,则均无法正常执行；若分给P3,则P3正常执行完成后，释放的这个资源仍无法使P1、P2正常执行，故不存在安全序列，选A。27.解析：进程 等待某资源为可用（不包括处理 机）或等待输入输出完成均会进入阻塞状态，故I、II 正确；III中情况发生时，进程进入就绪状态，故III错误，答案选C。28.解析：“条件变量”是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的“信号量”，都是用于实现进
13、程同步的。需要注意的是，在同一时刻，管程中 只能有一个进程在执行。如果进程A 执行了x.wa识）操作，那么该进程会阻塞，并挂到条件变量 x对应的阻塞队列上。这样，管程的使用权被释放，就可以有另一个进程进入管程。如果进程B执行了x.signal()操作，那么会唤醒x对应的阻塞队列队头进程。在Pascal语言的 管程中，规定只有一个进程要离开管程时才能调用signal()操作。29.解析：时钟中断的 主要工作是处理和时间有关的信息以及决定是否执行调度程序，和时间有关的所有信息，包括系统时间、进程的时间片、延时、使用CPU的时间、各种定时器，故I、II、III均正确，选D。30.解析：当系统总是持续
14、出现某个磁道的访问请求时，均持续满足最短寻道时间优先、扫描算法和循环扫描算法 的访问条件，会一直服务该访问请求。因此，先来先服务按照请求次序进行调度，比较公平，故选A。31.解析：II和IV显然均能提高文件访问速度。对于I,提前读是指在读当前盘块时，将下一个可能要访问的盘块数据读入缓冲区，以便需要时直接从缓冲区中读取，提高了文件的访问速度。对于III,延迟写是先将写数据写入缓冲区，并置上“延迟写”标志，以备不久之后访问，当缓冲区需要再次被分配出去时才将缓冲区数据写入磁盘，减少了访问磁盘的次数，提高了文件的访问速度，III 也正确，答案选D。32.解析：硬件方法实现进程同步不能实现让权等待（见王
15、道单科书），故B、D错误；Pet erson算法满足有限等待但不满足让权等待，故 A 错误；记录型信号量由千引入阻塞机制，消除了不让权等待的情况，故C正确。33.解析：FTP用来传输文件，SMTP用来发送电子邮件，HTTP用来传输网页文件，都对可靠性的要求较高，因此都用传输层有连接的 T CP服务。无连接UDP服务效率更高、开销小，DNS在传输层采用无连接的UDP服务。34.解析：物理 层的接口规范主要分为4种：机械特性、电气特性、功能特性、规程特性。机械特性规定连接所用设备的规格，即 A 所说的接口形状。电气特性规定信号的电压高低、阻抗匹配等，如D所说的信号电平。功能特性规定线路上出现的电平
16、代表什么意义、接口部件的信号线（数据线、控制线、定时线等）的用途，如B 所说的引脚功能。选项C中的物理地址就是 MAC地址，它属于数据链路层的范畴。35.解析：CSMA/CA协议进行信道预约主要使用的是请求发送帧RTS(R equest to Send)和允许发送帧CTS(Clear to Send)。当一台主机想要发送信息时，先向无线站点发送一个RTS帧，说明要传输的数据及相应的时间。当无线站点收到RTS帧之后，会广播一个CTS帧作为对此的响应，既给发送端发送许可，又指示其他主机不要在这个时间内发送数据，从而预约信道，避免碰撞。发送确认帧，主要是保证信息的可靠传输；二进制指数退避法是在CSM
17、A/CD中的一种冲突处理 方法；C选项则与预约信道无关。36.解析：信道利用率传输帧的有效时间传输帧的周期。假设帧的长度为x比特。对于有效时间，应该用帧的大小除以数据传输速率，即x/3kbps。对于帧的传输周期，应包含4个部分：帧在发送端的发送时延、帧从发送端到接收端的单程传播时延、确认帧在接收端的发送时延、确认帧从接收端到发送端的单程传播时延。这 4个时延中，由于题目中说“忽略确认帧的传输延时,因此不计算确认帧的发送时延（注意传输时延和传播时延的区别，传输时延也称发送时延，和传播时延只有一字之差）。所以帧的传输周期由三部分组成：首先是帧在发送端的发送时延x/3kbps,其次是帧从发送端到接收
18、端的单程传播时延200ms,最后是确认帧从接收端到发送端的单程传播时延200ms,三者相加可得其周期应为x/3kbps+400ms。代入信道利用率的公式，求出X=800bit。答案选D。37.解析：在网络的信息传递中，会经常用到两个 地址：MAC地址和I P 地址。其中，MAC地址会随着信息被发往不同的网络而改变，但I P地址当且仅当信息在私人网络中传递时才会改变。分组P在如题图所示的网络中传递时，首先由主机Hl将分组发往路由器R,此时源MAC地址为H1 主机本身的MAC地址，即00-1a-2b-3c-4d-52,目的MAC地址 为路由器R的MAC地址，即 OO-la-2b-3c-4d-51。
19、当路由器R收到分组P后，根据分组P的目的IP地址，得知应 将分组从另一个端口转发出去，于是会给分组P更换新的MAC地址，此时由于从另外的端口转发出去，因此P的新源MAC地址变为负责转发的端口MAC地址，即OO-al-b2-c3-d4-61,目的MAC地址应为主机H2的MAC地址，即OO-al-b2-c3-d4-62。根据分析过程，题 目 所问的MAC地址应为路由器R两个端口的MAC地址，故选D。38.解析：对于此类题目，先分析需要聚合的IP地址。观察发现，题中的4个路由地址，前16位完全相同，不同之处在于第3段的8位中，将这8位展开写成二进制，分别如下：?7 6 5 4 3 2 I。32。I。
20、40。I。I。48。I I。56。I I I。观察发现，4个地址的第3段中，从前向后最多有3位相同，因此这3位是能聚合的最大位 数。将这些相同的位都保留，将第3段 第3位之后的所有位都置o,就得到了聚合后的IP地址 35:230.32.0,其网络前缀为16+3,也即前19 位，故聚合后的网络地址为35.230.32.0/19,答案为C。39.解析：传输层分用的定义是：接收方的传输层剥去报文首部后，能把这些数 据正确交付到目的进程。C和D选项显然不符。端口号是传输层服务访问点TSAP,用来标识主机中的 应 用进程。对于A和B选项，源端口号是在 需要对方回信时选用，不需要时可用全0。目的端口号是在
21、终点交付报文 时使用到，符合题意，故选B。40.解析：电子邮件出现得较早，当时的数据 传输 能力较弱，使用者们往往也不需要传输较大的图片、视频等，因此SMTP具有一些目前 来看较为老旧的性质，例如限制 所有邮件报文的体部分，只能采用7位 ASCII来表示。在如今的传输 过程 中，如果 传输了非文本文件，往往需要将这些多媒体文件重新编码为ASCII再传输。因此无须转换即可传输的是ASCII文本，答案为D。二、综合应用题41.解答：1)题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用千标记的数 组Bn,用来记录A中 是否出现了I-n中的 正整数，BO对应正整数 1,Bn-1对应正
22、整数n,初始化B中 全部 为0。由千A中含有n个整数，因此可能返回的值是l-n+1,当A中 n个数恰好为l-n 时返回 n+l。当数组A中出现了小于等于0或大于n的值时，会导致l-n中出现空余位置，返回结果必然在 l-n中，因此对于A中出现了小于等于0或大于n的值 可以不采取任何操作。经过以上分析可以得出算法流程：从AO开始遍历A,若0 Ai=n,则令BAi-1=1;否则不进行操作。对 A遍历结束后，开始遍历数 组B,若能查找到 第一个满足Bi=0的下标i 返回i+l 即为结果，此时说明A中未出现的最小正整数 在 l-n之间。若Bi全部不为o,返回i+l(跳出循环时 i=n,i+1 等于n+1
23、),此时说明A中未出现的最小正整数是n+l。int findMissMin(int A,int n)int i,*B;./标记数组B=(int*)malloc(sizeof(int)*n);/分配空间memset(B,0,sizebf(int)*n);.,/赋初值为0for(i=O;iO&Ai=n)BAi一l=l;for(i=O;inf if+)if(Bi=O)break;return i+l,;若Ai的值介于1-n,则标记数组BII扫描数组B,找到目标值II返回结果2)时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为0(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了Bn,
24、空间复杂度为O(n)。42.解答：1)为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动Prim算法或Kruskal算法作图。注意本题最小生成树有两种构造，如下图所示。2?2?3 2方案l方案的总费用为16。2)存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用Prim算法（或Kruskal算法）。3)TTL=5,即IP分组的生存时间（最大传递距离）为5,方案1 中TL和BJ的距离过远，TTL=5不足以让IP分组从Hl传送到H2,因此H2不能收到IP分组。而方案2 中TL和BJ邻近，H2可以收到IP分组。43.解答：1)程序定时向缓存端口查询数据，由于缓存端
25、口大小有限，必须在传输完端口大小的数据时访问端口，以防止部分数据未被及时读取而丢失。设备 A准备 32 位数据所用的时间为4B/2MB=2s,所以最多每隔2s必须查询一次，每秒的查询次数至少是ls/2s=5xl05,每秒CPU用于设备A输入输出的时间至少为5xI05xIOx4=2xl07个时钟周期，占整个CPU时间的百分比至少是2x 107/SOOM=4%。2)中断响应和中断处理的时间为400 x(l/500M)=0.8s,这时只需判断设备B准备32位数据要多久，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新，造成丢失。经过计算，设备B准备32位数据所用的时间为4B/40M
26、B=O.ls,因此设备B不适合采用中断1/0方式。3)在DMA 方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制的。设备B 每秒的DMA 次数最多为40MB/IOOOB=40000,CPU用于设备B输入输出的时间最多为40000 x500=2x 107个时钟周期，占CPU总时间的百分比最多为2x107/5QOM=4%。44.解答：1)物理地址由实页号和页内地址拼接，因此其位数为 16+12=28 或直接 可得 20+3+5=28。2)TLB 采用全相联映射，可以把页表内容调入任一块空 TLB 项中，TLB 中每项都有一个比较器，没有映射规则，只要空闲就行。TLB 采用静态
27、存储器 SRAM,读写速度快，但成本高，多用于容量较小的高速缓冲存储器。3)从图 中可以看到，Cache 中每组有两行，故采用 2 路组相联映射方式。因为是 2 路组相联并采用LRU 替换算法，所以每行（或每组）需要 1 位LRU 位；因为采用回写策略，所以每行有1位修改位（脏位），根据脏位判断数据是否被更新，若脏位为1则需要写回内存。28 位物理地址中 Tag 字段占 20 位，组索引字段占 3 位，块内偏移地址占 5 位，故 Cache共有 3=8 组，每组 2 行，每行有 25=32B,故 Cache 总容量为 8x2x(20+1+1+132x8)=4464位=558 字节。Cache
28、中有效位用来指出所在 Cache 行中的信息是否有效。4)虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找 TLB 表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号 008CH 恰好在 TLB 表中对应实页号 0040H(有效位为 1,说明存在），虚拟地址的后 3 位为页内地址 040H,则对应的物理地址是 0040040H。物理地址为 0040040H,其中高 20 位 00400H 为标志字段，低5 位 OOOOOB 为块内偏移量，中间 3 位 010B 为组号 2,因此将 00400H 与
29、Cache 中的第 2 组两行中的标志字段同时比较，可以看出，虽然有一个 Cache 行中的标志字段与 00400H 相等，但对应的有效位为o,而另一Cache行的标志字段与 00400H 不相等，故访问 Cache 不命中。因为物理地址的低 12 位与虚拟地址 低 12 位相同，即为 001001100000B。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此该地址 所在的主存映射到Cache的组号为3。45.解答：1)由图可知，地址总长度为 32 位，高 20 位为虚页号，低 12 位为页内地址，且虚页号高10位为页目录号，低10位为页号。展开成二进制表示
30、为0000 0001 1000 0000 01100000 0000 1000 B I I 11-I 11 I I 页目录号页号页内地址d故十六进制表示为 0180 6008H。2)PDBR 为页目录基址地址寄存器(Page-Directory Base Register),其存储页目录表物理内存基地址。进程切换时，PDBR 的内容会变化；同一进程的线程切换时，PDBR 的内容不会变化。每个进程的地址空间、页目录和PDBR 的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新 PDBR。同一进程中的线程共
31、享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR 的内容也不变。3)改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。46.解答：1)簇大小为 4KB,每个地址项长度为 4B,故每簇有 4KB/4B=1024个地址项。最大文件的物理块 数可达8+lx1024+lx10242+lx10243,每个物理块（簇）大小为4KB,故最大文件长度为(8+x1024+x10242+lxl024扣4KB=32KB+4MB+4GB+4TB。(2)文件索引节点总个数为1Mx4KB/64B=64M,5600B的文件占2个簇，51
32、2M个簇可存放的文件总个数为512M/2,;=256M。可表示的文件总个数受限于文件 索引节点总个数，故能存储64M个大小为5600B的图像文件。(3)文件Fl的大小为6KB 4KBx8=32KB,故获取文件Fl的最后一个簇的簇 号只需要访问索引节点的直接地址项。文件F2的大小为40KB,4KBx8 40KB 4KBx8+4KBx 1024,故获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。47.解答：1)广播地址是网络地址中主机号 全l的地址（主机号全0的地址代表 网络本身）。销售部和技术部均分配了192.168.1.0/24的IP地址空间，IP地址的前24位为子网的网
33、络号。于是在 后8位中划分部门的子网，选择前1位作为部门 子网的网络号。令销售部子网的网络号为o,技术部子网的网络号 为I,则技术部子网的完整地址为192.168.1.128;令销售部子网的主机号全I,可以得到该部门的广播地址为192.168.1.127。每个主机仅分配一个IP地址，计算目前还可以分配的主机数，用技术部可以分配的主机数 减去已分配的主机数，技术部总共可以分配给计算机 的主机数为27-2=126(减去全0和全l的主机号）。已经分配了208-129+I=80个，此外还有1个IP地址 分配给了路由器的端口(192.168.1.254),因此还可以分配 126-80-1=45台。2)判断分片的大小，需要考虑各个网段的MTU,而且注意分片的数据长度必须是8B的整数倍。由题可知，在技术部子网内，MTU=800B,IP分组头部长20B,最大1P分片封装数据的字节数为L(8oo-20)/8x8=776。至少需要的分片 数为(1500-20)/7767=2。第1个分片的偏移量为0;第2个分片的偏移量为776/8=97。