C.x1>x2且同号
D.x1>x2且异号
涉及考点：
机器中float型数据的比较，十六进制的float型数据比较
15.某容量为256MB的存储器由若干个4M*8倍DRAM芯片构成，则该DRAM芯片的地址引脚与数据引脚的总和
A.19
B.22
C.30
D.36
涉及考点：
存储器的编址
25.下列指令，无法在用户态执行的是
A.trap指令
B.跳转指令
C.压栈指令
D.关中断指令
涉及考点：
指令的执行状态---用户态
33.关于OSI参考模型中，直接为会话层提供服务的是：
A.应用层
B.表示层
C.传输层
D.网络层
涉及考点：
OSI网络模型
40.用浏览器访问某学校主页，不可能用到的协议
A.PPP
B.ARP
C.UDP
D.SMTP
涉及考点：
网络协议
二、综合应用题：
第41～47小题，共70分。
41.二叉树的带权路径长度（WPL）是所有叶结点的带权路径长度之和。
给定二叉树T，采用二叉链表存储，结点结构为[left|weight|right],其中叶节点weight域保存该节点的非负权值。
设root为指向T的根节点指针，请设计算法求T的WPL，要求：
1）写出基本设计思想
2）采用C或C++，给出二叉树节点的数据类型定义
3）结合设计思想，采用C或C++描述算法，关键之处做出标注。
涉及考点：
这道编程题目考察了二叉树的带权路径长度的求法，和往常一样首先要写出设计思想，然后做出数据类型定义，然后就是具体算法的编写
46.文件F由200条记录组成，记录从1开始编号，用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录，请回答下列问题，并说明理由。
1）若文件系统为顺序分配方式，每个存储块存放一条记录，文件F的存储区域前后均有足够空闲的存储空间，则要完成上述操作最少要访问多少存储块？
F的文件控制区内容会有哪些改变？
2）若文件系统为链接分配方式，每个存储块存放的一条记录和一个链接指针，则要完成上述操作最少要访问多少存储块？
若每个存储块大小为1KB，其中4个字节存放指针，则该系统支撑文件的最大长度是多少？
涉及考点：
（1）文件系统的顺序分配方式
（2）文件系统的链接分配方式，以及文件的存储
47.系统中有多个生产者进程和消费者进程，共享用一个可以存1000个产品的缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。
要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量P，V（wait，signed）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值
涉及考点：
典型的生产者消费者模式进程间的互斥和同步
2019考研计算机学科专业基础综合真题及答案
一、单项选择题：
1~40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项符合试题要求。
1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是
x=0；
while（n>=（x+l）*（x+l））
x=x+l；
A.O（logn）B.O（n1/2）C.O（n）D.O（n2）
2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是
A.先序遍历B.中序遍历C.后序遍历D.按层遍历
3.对n个互不相同的符号进行哈夫曼编码。
若生成的哈夫曼树共有115个结点，则n的值是
A.56B.57C.58D.60
4.在任意一棵非空平衡二又树（AVL树）T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。
下列关于T1与T3的叙述中，正确的是
I.若v是T1的叶结点，则T1与T3可能不相同
Ⅱ.若v不是T1的叶结点，则T1与T3一定不相同
Ⅲ.若v不是T1的叶结点，则T1与T3一定相同
A.仅IB.仅IIC.仅I、ⅡD.仅I、Ⅲ
5.下图所示的AOE网表示一项包含8个活动的工程。
活动d的最早开始时间和最迟开始时间分别是
A.3和7B.12和12C.12和14D.15和15
6.用有向无环图描述表达式（x+y）*（（x+y）/x），需要的顶点个数至少是
A.5B.6C.8D.9
7.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是
I.数据的规模Ⅱ.数据的存储方式Ⅲ.算法的稳定性V.数据的初始状态
A.仅ⅢB.仅I、ⅡC.仅Ⅱ、Ⅲ、IVD.I、Ⅱ、Ⅲ、Ⅳ
8.现有长度为11且初始为空的散列表HT，散列函数是H（key）=key%7，采用线性探查（线性探测再散列）法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是
A.4B.5.25C.6D.6.29
9.设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是
A.9B.10C.12D.15
10.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。
下列序列中，不可能是快速排序第二趟结果的是
A.5，2，16，12，28，60，32，72B.2，16，5，28，12，60，32，72
C.2，12，16，5，28，32，72，60D.5，2，12，28，16，32，72，60
11.设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是
A.1B.2C.3D.4
12.下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是
A.程序的功能都通过中央处理器执行指令实现
B.指令和数据都用二进制表示，形式上无差别
C.指令按地址访问，数据都在指令中直接给出
D.程序执行前，指令和数据需预先存放在存储器中
13.考虑以下C语言代码：
unsignedshortusi=65535；
shortsi=usi；
执行上述程序段后，si的值是
A.-1B.-32767C.-32768D.-65535
14.下列关于缺页处理的叙述中，错误的是
A.缺页是在地址转换时CPU检测到的一种异常
B.缺页处理由操作系统提供的缺页处理程序来完成
C.缺页处理程序根据页故障地址从外存读入所缺失的页
D.缺页处理完成后回到发生缺页的指令的下一条指令执行
15.某计算机采用大端方式，按字节编址。
某指令中操作数的机器数为1234FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为FF12H，基址寄存器内容为F0000000H，则该操作数的LSB（最低有效字节）所在的地址是
A.F000FF12HB.F000FF15HC.EFFFFF12HD.EFFFFF15H
16.下列有关处理器时钟脉冲信号的叙述中，错误的是
A.时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
B.时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频
C.时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定
D.处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
17.某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。
对于下列给定部件，该指令在取数及执行过程中需要用到的是
I.通用寄存器组（GPRs）Ⅱ.算术逻辑单元（ALU）
Ⅲ.存储器（Memory）Ⅳ.指令译码器（ID）
A.仅I、ⅡB.仅I、Ⅱ、ⅢC.仅Ⅱ、Ⅲ、IVD.仅I、Ⅲ、Ⅳ
18.在采用“取指、译码/取数、执行、访存、写回”5段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器编号。
I1：
adds2，s1，s0//R[s2]←R[s1]+R[s0]
I2：
loads3，0（t2）//R[s3]←M[R[t2]+0]
I3：
adds2，s2s3//R[s2]←R[s2]+R[s3]
I4：
stores2，0（t2）//M[R[t2]+0]←R[s2]
下列指令对中，不存在数据冒险的是
A.I1和I3B.I2和I3C.I2和I4D.I3和I4
19.假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz、总线宽度为64位，则存储器总线的总带宽大约是
A.10.66GB/sB.32GB/sC.64GB/sD.96GB/s
20.下列关于磁盘存储器的叙述中，错误的是
A.磁盘的格式化容量比非格式化容量小
B.扇区中包含数据、地址和校验等信息
C.磁盘存储器的最小读写单位为一个字节
D.磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成
21.某设备以中断方式与CPU进行数据交换，CPU主频为1GHz，设备接口中的数据缓冲寄存器为32位，设备的数据传输率为50kB/s。
若每次中断开销（包括中断响应和中断处理）为1000个时钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是
A.1.25%B.2.5%C.5%D.12.5%
22.下列关于DMA方式的叙述中，正确的是
I.DMA传送前由设备驱动程序设置传送参数
II.数据传送前由DMA控制器请求总线使用权
Ⅲ.数据传送由DMA控制器直接控制总线完成
IV.DMA传送结束后的处理由中断服务程序完成
A.仅I、ⅡB.仅Ⅰ、Ⅲ、ⅣC.仅Ⅱ、Ⅲ、IVD.I、Ⅱ、Ⅲ、IV
23.下列关于线程的描述中，错误的是
A.内核级线程的调度由操作系统完成
B.操作系统为每个用户级线程建立一个线程控制块
C.用户级线程间的切换比内核级线程间的切换效率高
D.用户级线程可以在不支持内核级线程的操作系统上实现
24.下列选项中，可能将进程唤醒的事件是
I.I/O结束Ⅱ.某进程退出临界区Ⅲ.当前进程的时间片用完
A.仅IB.仅ⅢC.仅I、ⅡD.I、Ⅱ、Ⅲ
25.下列关于系统调用的叙述中，正确的是
I.在执行系统调用服务程序的过程中，CPU处于内核态
Ⅱ.操作系统通过提供系统调用避免用户程序直接访问外设
Ⅲ.不同的操作系统为应用程序提供了统一的系统调用接口
IV.系统调用是操作系统内核为应用程序提供服务的接口
A.仅I、IVB.仅II、IIIC.仅I、Ⅱ、IVD.仅I、Ⅲ、Ⅳ
26.下列选项中，可用于文件系统管理空闲磁盘块的数据结构是
I.位图Ⅱ.索引节点Ⅲ.空闲磁盘块链Ⅳ.文件分配表（FAT）
A.仅I、ⅡB.仅Ⅰ、Ⅲ、ⅣC.仅l、ⅢD.仅Ⅱ、Ⅲ、Ⅳ
27.系统采用二级反馈队列调度算法进行进程调度。
就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2。
若当前Q1、Q2为空，系统依次创建进程Pl、P2后即开始进程调度Pl、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为
A.25msB.20msC.15msD.10ms
28.在分段存储管理系统中，用共享段表描述所有被共享的段。
若进程P1和P2共享段S，下列叙述中，错误的是
A.在物理内存中仅保存一份段S的内容
B.段S在P1和P2中应该具有相同的段号
C.P1和P2共享段S在共享段表中的段表项
D.P1和P2都不再使用段S时才回收段S所占的内存空间
29.某系统采用LRU页置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页号的序列为0，1，2，7，0，5，3，5，0，2，7，6，则进程访问上述页的过程中，产生页置换的总次数是
A.3B.4C.5D.6
30.下列关于死锁的叙述中，正确的是
I.可以通过剥夺进程资源解除死锁
II.死锁的预防方法能确保系统不发生死锁
III.银行家算法可以判断系统是否处于死锁状态
Ⅳ.当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
A.仅II、ⅢB.仅I、Ⅱ、ⅣC.仅I、Ⅱ、ⅢD.仅I、Ⅲ、Ⅳ
31.某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示
页目录号（10位）页号（10位）页内偏移（12位）
虚拟地址20501225H对应的页目录号、页号分别是
A.081H、101HB.081H、401HC.201H、101HD.201H、401H
32.在下列动态分区分配算法中，最容易产生内存碎片的是
A.首次适应算法B.最坏适应算法C.最佳适应算法D.循环首次适应算法
33.OSI参考模型的第5层（自下而上）完成的主要功能是
A.差错控制B.路由选择C.会话管理D.数据表示转换
34.100BaseT快速以太网使用的导向传输介质是
A.双绞线B.单模光纤C.多模光纤D.同轴电缆
35.对于滑动窗口协议，如果分组序号采用3比特编号，发送窗口大小为5，则接收窗口最大是
A.2B.3C.4D.5
36.假设一个采用CSMA/CD协议的100Mbps局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播延时最多是
A.2.56μsB.5.12μsC.10.24μsD.20.48μs
37.若将101.200.16.0/20划分为5个子网，则可能的最小子网的可分配IP地址数是
A.126B.254C.510D.1022
38.某客户通过一个TCP连接向服务器发送数据的部分过程如题38图所示。
客户在t0时刻第一次收到确认序列号ack_seq=100的段，并发送序列号seq=100的段，但发生丢失。
若TCP支持快速重传，则客户重新发送seq=100段的时刻是
A.t1B.t2C.t3D.t4
39.若主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为2018和2046，则第三次握手TCP段的确认序列号是
A.2018B.2019C.2046D.2047
40.下列关于网络应用模型的叙述中，错误的是
A.在P2P模型中，结点之间具有对等关系
B.在客户/服务器（C/S）模型中，客户与客户之间可以直接通信
C.在C/S模型中，主动发起通信的是客户，被动通信的是服务器
D.在向多用户分发一个文件时，P2P模型通常比C/S模型所需时间短
二、综合应用题：
41~47小题，共70分。
41.（13分）设线性表L=（a1，a2，a…，an-2，a-1，a。
）采用带头结点的单链表保存，链表中结点定义如下：
typedefstructnode{
intdata；
structnode*next；
}NODE；
请设计一个空间复杂度为O
（1）且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=（a1，an，a2，an-1，a3，an-2…）。
要求：
（1）给出算法的基本设计思想
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。
42.（10分）请设计一个队列，要求满足：
①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间复杂度始终保持为O
（1）。
请回答下列问题：
（1）该队列应该选择链式存储结构，还是顺序存储结构？
（2）画出队列的初始状态，并给出判断队空和队满的条件
（3）画出第一个元素入队后的队列状态。
（4）给出入队操作和出队操作的基本过程。
43.（8分）有n（n≥3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。
在圆桌中心有m（m≥1）个碗，每两位哲学家之间有1根筷子。
每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。
为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作（wait（）、signal（）操作）描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
44.（7分）某计算机系统中的磁盘有300个柱面，每个柱面有10个磁道，每个磁道有200个扇区，扇区大小为512B。
文件系统的每个簇包含2个扇区。
请回答下列问题：
（1）磁盘的容量是多少？
（2）假设磁头在85号柱面上，此时有4个磁盘访问请求，簇号分别为：
100260、60005、101660和110560。
若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是什么？
（3）第100530簇在磁盘上的物理地址是什么？
将簇号转换成磁盘物理地址的过程是由I/O系统的什么程序完成的？
45.（16分）已知f（n）=n！
=n×（n-l）×（n-2）×…×2×1，计算f（n）的C语言函数fl的源程序（阴影部分）及其在32位计算机M上的部分机器级代码如下：
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机M按字节编址，int型数据占32位。
请回答下列问题：
（1）计算f（10）需要调用函数f1多少次？
执行哪条指令会递归调用f1？
（2）上述代码中，哪条指令是条件转移指令？
哪几条指令一定会使程序跳转执行？
（3）根据第16行call指令，第17行指令的虚拟地址应是多少？
已知第16行call指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？
已知第16行call指令的后4字节为偏移量，M采用大端还是小端方式？
（4）f（13）=6227020800，但f1（13）的返回值为1932053504，为什么两者不相等？
要使f1（13）能返回正确的结果，应如何修改f1源程序？
（5）第19行imuleax,ecx表示有符号数乘法，乘数为R[eax]和R[ecx]，当乘法器输出的高、低32位乘积之间满足什么条件时，溢出标志OF=1？
要使CPU在发生溢出时转异常处理，编译器应在imul指令后加一条什么指令？
46.（7分）对于题45，若计算机M的主存地址为32位，采用分页存储管理方式，页大小为4KB，则第1行push指令和第30行ret指令是否在同一页中（说明理由）？
若指令Cache有64行，采用4路组相联映射方式，主存块大小为64B，则32位主存地址中，哪几位表示块内地址？
哪儿位表示Cache组号？
哪几位表示标记（tag）信息？
读取第16行call指令时，只可能在指令Cache的哪一组中命中（说明理由）？
47.（9分）某网络拓扑如题47图所示，其中R为路由器，主机H1~H4的IP地址配置以及R的各接口IP地址配置如图中所示。
现有若干台以太网交换机（无VLAN功能）和路由器两类网络互连设备可供选择。
请回答下列问题：
（1）设备1、设备2和设备3分别应选择什么类型网络设备？
（2）设备1、设备2和设备3
升级会员 