计算机考研真题及参考答案资料下载.pdf
- 文档编号:5981677
- 上传时间:2023-05-05
- 格式:PDF
- 页数:12
- 大小:829.83KB
计算机考研真题及参考答案资料下载.pdf
《计算机考研真题及参考答案资料下载.pdf》由会员分享,可在线阅读,更多相关《计算机考研真题及参考答案资料下载.pdf(12页珍藏版)》请在冰点文库上搜索。
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,100B.00,100,110,000,0010,01C.10,1011,11,0011,00,010D.0011,10,11,0010,01,0006.已知二叉排序树如下图所示,元素之间应满足的大小关系是。
A.x1x2x5B.x1x4x5C.x3x5x4D.x4x3x57.下列选项中,不是如下有向图的拓扑序列的是。
A.1,5,2,3,6,4B.5,1,2,6,3,4C.5,1,2,3,6,4D.5,2,1,6,3,48.高度为5的3阶B树含有的关键字个数至少是。
A.15B.31C.62D.2429.现有长度为7、初始为空的散列表HT,散列函数H(k)=k%7,用线性探测再散列法解决冲突。
将关键字22,43,15依次插人到HT后,查找成功的平均查找长度是。
A.1.5B.1.6C.2D.310.对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。
若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8),第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9),则两趟排序采用的增量(间隔)依次是。
A.3,1B.3,2C.5,2D.5,311.在将数据序列(6,1,5,9,8,4,7)建成大根堆时,正确的序列变化过程是。
A.6,1,7,9,8,4,56,9,7,1,8,4,59,6,7,1,8,4,59,8,7,1,6,4,5B.6,9,5,1,8,4,76,9,7,1,8,4,59,6,7,1,8,4,59,8,7,1,6,4,5C.6,9,5,1,8,4,79,6,5,1,8,4,79,6,7,1,8,4,59,8,7,1,6,4,5D.6,1,7,9,8,4,57,1,6,9,8,4,57,9,6,1,8,4,59,7,6,1,8,4,59,8,6,1,7,4,512.冯诺依曼结构计算机中数据采用二进制编码表示,其主要原因是。
.二进制的运算规则简单.制造两个稳态的物理器件较容易.便于用逻辑门电路实现算术运算A.仅、B.仅、C.仅、D.、和13.假定带符号整数采用补码表示,若int型变量x和y的机器数分别是FFFFFFDFH和00000041H,则x、y的值以及x-y的机器数分别是。
A.x=-65,y=41,x-y的机器数溢出B.x=-33,y=65,x-y的机器数为FFFFFF9DHC.x=-33,y=65,x-y的机器数为FFFFFF9EHD.x=-65,y=41,x-y的机器数为FFFFFF96H14.IEEE754单精度浮点格式表示的数中,最小的规格化正数是。
A.1.02-126B.1.02-127C.1.02-128D.1.02-14915.某32位计算机按字节编址,采用小端(LittleEndian)方式。
若语令“inti=0;
”对应指令的机器代码为“C745FC00000000”,则语句“inti=-64;
”对应指令的机器代码是。
A.C745FCC0FFFFFFB.C745FC0CFFFFFFC.C745FCFFFFFFC0D.C745FCFFFFFF0C16.整数x的机器数为11011000,分别对x进行逻辑右移1位和算术右移1位操作,得到的机器数各是。
A.11101100、11101100B.01101100、11101100C.11101100、01101100D.01101100、0110110017.假定DRAM芯片中存储阵列的行数为r、列数为c,对于一个2K1位的DRAM芯片,为保证其地址引脚数最少,并尽量减少刷新开销,则r、c的取值分别是。
A.2048、1B.64、32C.32、64D.1、204818.按字节编址的计算机中,某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分别为。
A.CF=0,OF=0B.CF=1,OF=0C.CF=0,0F=1D.CF=1,OF=120.若某计算机最复杂指令的执行需要完成5个子功能,分别由功能部件AE实现,各功能部件所需时间分别为80ps、50ps、50ps、70ps和50ps,采用流水线方式执行指令,流水段寄存器延时为20ps,则CPU时钟周期至少为。
A.60psB.70psC.80psD.100ps21.下列选项中,可提高同步总线数据传输率的是。
.增加总线宽度.提高总线工作频率.支持突发传输.采用地址/数据线复用A.仅、B.仅、C.仅、D.、和22.下列关于外部I/O中断的叙述中,正确的是。
A.中断控制器按所接收中断请求的先后次序进行中断优先级排队B.CPU响应中断时,通过执行中断隐指令完成通用寄存器的保护C.CPU只有在处于中断允许状态时,才能响应外部设备的中断请求D.有中断请求时,CPU立即暂停当前指令执行,转去执行中断服务程序23.下列关于多任务操作系统的叙述中,正确的是。
.具有并发和并行的特点.需要实现对共享资源的保护.需要运行在多CPU的硬件平台上A.仅B.仅C.仅、D.、24.某系统采用基于优先权的非抢占式进程调度策略,完成一次进程调度和进程切换的系统时间开销为1s。
在T时刻就绪队列中有3个进程P1、P2和P3,其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。
进程等待时间需要的CPU时间优先权P130s12s10P215s24s30P318s36s20若优先权值大的进程优先获得CPU,从T时刻起系统开始进程调度,则系统的平均周转时间为。
A.54sB.73sC.74sD.75s25.属于同一进程的两个线程thread1和thread2并发执行,共享初值为0的全局变量x。
thread1和thread2实现对全局变量x加1的机器级代码描述如下。
thread1thread2movR1,x/(x)R1incR1/(R1)+1R1movx,R1/(R1)xmovR2,x/(x)R2incR2/(R2)+1R2movx,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阻塞的事件是。
.进程P申请临界资源.进程P从磁盘读数据.系统将CPU分配给高优先权的进程A.仅B.仅C.仅、D.、28.若x是管程内的条件变量,则当进程执行x.wait()时所做的工作是。
A.实现对变量x的互斥访问B.唤醒一个在x上阻塞的进程C.根据x的值判断该进程是否进人阻塞状态D.阻塞该进程,并将之插入x的阻塞队列中29.当定时器产生时钟中断后,由时钟中断服务程序更新的部分内容是。
.内核中时钟变量的值.当前进程占用CPU的时间.当前进程在时间片内的剩余执行时间A.仅、B.仅、C.仅、D.、30.系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求,这种现象称为磁臂黏着。
下列磁盘调度算法中,不会导致磁臂粘着的是。
A.先来先服务(FCFS)B.最短寻道时间优先(SSTF)C.扫描算法(SCAN)D.循环扫描算法(CSCAN)31.下列优化方法中,可以提高文件访问速度的是。
.提前读.为文件分配连续的簇.延迟写.采用磁盘高速缓存A.仅、B.仅、C.仅、D.、32.在下列同步机制中,可以实现让权等待的是。
A.Peterson方法B.swap指令C.信号量方法D.TestAndSet指令33.下列TCP/IP应用层协议中,可以使用传输层无连接服务的是。
A.FTPB.DNSC.SMTPD.HTTP34.下列选项中,不属于物理层接口规范定义范畴的是。
A.接口形状B.引脚功能C.物理地址D.信号电平35.IEEE802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是。
A.发送确认帧B.采用二进制指数退避C.使用多个MAC地址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、35.230.40.0/21、35.230.48.0/21和35.230.56.0/21,将该4条路由聚合后的目的网络地址为。
A.35.230.0.0/19B.35.230.0.0/20C.35.230.32.0/19D.35.230.32.0/2039.UDP协议实现分用(demultiplexing)时所依据的头部字段是。
A.源端口号B.目的端口号C.长度D.校验和40.无需转换即可由SMTP协议直接传输的内容是。
A.JPEG图像B.MPEG视频C.EXE文件D.ASCII文本二、综合应用题:
第4147小题,共70分。
41.(13分)给定一个含n(n1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。
例如,数组-5,3,2,3中未出现的最小正整数是1;
数组1,2,3中未出现的最小正整数是4。
要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C+语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
42.(12分)拟建设一个光通信骨干网络连通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分组?
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图根据题44图回答下列问题。
(1)主存物理地址占多少位?
(2)TLB采用什么映射方式?
TLB用SRAM还是DRAM实现?
(3)Cache采用什么映射方式?
若Cache采用LRU替换算法和回写(WriteBack)策略,则Cache每行中除数据(Data)、Tag和有效位外,还应有哪些附加位?
Cache总容量是多少?
Cache中有效位的作用是什么?
(4)若CPU给出的虚拟地址为0008C040H,则对应的物理地址是多少?
是否在Cache中命中?
说明理由,若CPU给出的虚拟地址为0007C260H,则该地址所在主存块映射到的Cache组号是多少?
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地址,则技术部子网还可以连接多少台主机?
(2)假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组,IP分组的头部长度为20B,路由器在通过接口F1转发该IP分组时进行了分片。
若分片时尽可能分为最大片,则一个最大IP分片封装数据的字节数是多少?
至少需要分为几个分片?
每个分片的片偏移量是多少?
2018年计算机学科专业基础综合试题参考答案一、单项选择题1B2C3A4A5A6C7D8B9C10D11A12D13C14A15A16B17C18B19A20D21B22C23C24D25B26A27C28D29D30A31D32C33B34C35D36D37D38C39B40D二、综合应用题41解析:
1)题目要求算法时间上尽可能高效,因此采用空间换时间的办法。
分配一个用于标记的数组Bn,用来记录A中是否出现了1n中的正整数,B0对应正整数1,Bn-1对应正整数n,初始化B中全部为0。
由于A中含有n个整数,因此可能返回的值是1n+1,当A中n个数恰好为1n时返回n+1。
当数组A中出现了小于等于0或者大于n的值时,会导致1n中出现空余位置,返回结果必然在1n中,因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。
经过以上分析可以得出算法流程:
从A0开始遍历A,若0Ai=n,则令BAi-1=1;
否则不做操作。
对A遍历结束后,开始遍历数组B,若能查找到第一个满足Bi=0的下标i,返回i+1即为结果,此时说明A中未出现的最小正整数在1n之间。
若Bi全部不为0,返回i+1(跳出循环时i=n,i+1等于n+1),此时说明A中未出现的最小正整数是n+1。
intfindMissMin(intA,intn)inti,*B;
/标记数组B=(int*)malloc(sizeof(int)*n);
/分配空间memset(B,0,sizeof(int)*n);
/赋初值为0for(i=0;
i0&
Ai=n)/若Ai的值介于1n,则标记数组BBAi-1=1;
for(i=0;
in;
i+)/扫描数组B,找到目标值if(Bi=0)break;
returni+1;
/返回结果3)时间复杂度:
遍历A一次,遍历B一次,两次循环内操作步骤为O
(1)量级,因此时间复杂度为O(n)。
空间复杂度:
额外分配了Bn,空间复杂度为O(n)。
42解析:
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解析:
1)程序定时向缓存端口查询数据,由于缓存端口大小有限,必须在传输完端口大小的数据时访问端口,以防止部分数据没有被及时读取而丢失。
设备A准备32位数据所用时间为4B/2MB=2us,所以最多每隔2us必须查询一次,每秒的查询次数至少是1s/2us=5105,每秒CPU用于设备A输入/输出的时间至少为5105104=2107个时钟周期,占整个CPU时间的百分比至少是2107/500M=4%。
2)中断响应和中断处理的时间为400(1/500M)=0.8us,这时只需判断设备B准备32位数据要多久,如果准备数据的时间小于中断响应和中断处理的时间,那么数据就会被刷新、造成丢失。
经过计算,设备B准备32位数据所用时间为4B/40MB=0.1us,因此,设备B不适合采用中断I/O方式。
3)在DMA方式中,只有预处理和后处理需要CPU处理,数据的传送过程是由DMA控制。
设备B每秒的DMA次数最多为40MB/1000B=40000,CPU用于设备B输入/输出的时间最多为40000500=2107个时钟周期,占CPU总时间的百分比最多为2107/500M=4%。
44解析:
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总容量为82(20+1+1+1+328)=4464位=558字节。
Cache中有效位用来指出所在Cache行中的信息是否有效。
4)虚拟地址分为两部分:
虚页号、页内地址;
物理地址分为两部分:
实
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 考研 参考答案