2019年考研408计算机学科专业基础综合真题与答案.pdf

2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项符合试题要求。1.设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是 x=0；while(n=(x+l)*(x+l)x=x+l；A.O(log n)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.604.在任意一棵非空平衡二又树(AVL树)T1 中，删除某结点v 之后形成平衡二又树T 2，再将 w 插入 T2 形成平衡二又树 T 3。下列关于 T 1 与 T3 的叙述中，正确的是I.若 v 是 T 1 的叶结点，则 T1 与 T3 可能不相同.若 v 不是 T1 的叶结点，则T1 与 T 3 一定不相同.若 v 不是 T1 的叶结点，则T1 与 T3一定相同A.仅 IB.仅 IIC.仅 I、D.仅 I、5.下图所示的 AOE 网表示一项包含 8 个活动的工程。活动d的最早开始时间和最迟开始时间分别是A.3 和 7B.12 和 12C.12 和 14 D.15 和 156.用有向无环图描述表达式(x+y)*(x+y)/x)，需要的顶点个数至少是A.5B.6C.8D.97.选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是I.数据的规模.数据的存储方式.算法的稳定性V.数据的初始状态仅仅 I、仅、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.299.设主串 T=“abaabaabcabaabc，模”式串 S=“abaabc”，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是A.9B.10C.12D.1510.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是A.5，2，16，12，28，60，32，72B.2，16，5，28，12，60，32，72C.2，12，16，5，28，32，72，60D.5，2，12，28，16，32，72，6011.设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是A.1B.2C.3D.412.下列关于冯 诺依曼结构计算机基本思想的叙述中，错误的是A.程序的功能都通过中央处理器执行指令实现B.指令和数据都用二进制表示，形式上无差别C.指令按地址访问，数据都在指令中直接给出D.程序执行前，指令和数据需预先存放在存储器中13.考虑以下 C 语言代码：unsigned short usi=65535；short si=usi；执行上述程序段后，si 的值是A.-1B.-32767C.-32768D.-6553514.下列关于缺页处理的叙述中，错误的是A.缺页是在地址转换时 CPU 检测到的一种异常B.缺页处理由操作系统提供的缺页处理程序来完成C.缺页处理程序根据页故障地址从外存读入所缺失的页D.缺页处理完成后回到发生缺页的指令的下一条指令执行15.某计算机采用大端方式，按字节编址。某指令中操作数的机器数为方式，形式地址(用补码表示 )为 FF12H，基址寄存器内容为1234 FF00H，该操作数采用基址寻址F000 0000H，则该操作数的LSB(最低有效字节)所在的地址是A.F000 FF12HB.F000 FF15HC.EFFF FF12HD.EFFF FF15H16.下列有关处理器时钟脉冲信号的叙述中，错误的是A.时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B.时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C.时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D.处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令17.某指令功能为 Rr2 Rr1+MRr0 ，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是I.通用寄存器组 (GPRs).算术逻辑单元 (ALU).存储器(Memory).指令译码器(ID)A.仅 I、B.仅 I、C.仅、IVD.仅 I、18.在采用“取指、译码/取数、执行、访存、写回 ”5 段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3 和 t2 表示寄存器编号。I1：add s2，s1，s0/Rs2 Rs1+Rs0I2：load s3，0(t2)/Rs3 MRt2+0I3：add s2，s2s3/Rs2 Rs2+Rs3I4：store s2，0(t2)/MRt2+0 Rs2下列指令对中，不存在数据冒险的是A.I1 和 I3B.I2 和 I3C.I2 和 I4D.I3 和 I419.假定一台计算机采用 3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333 MHz、总线宽度为64 位，则存储器总线的总带宽大约是A.10.66 GB/sB.32 GB/sC.64 GB/sD.96 GB/s20.下列关于磁盘存储器的叙述中，错误的是A.磁盘的格式化容量比非格式化容量小B.扇区中包含数据、地址和校验等信息C.磁盘存储器的最小读写单位为一个字节D.磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成21.某设备以中断方式与CPU 进行数据交换，CPU 主频为 1 GHz，设备接口中的数据缓冲寄存器为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、IV23.下列关于线程的描述中，错误的是A.内核级线程的调度由操作系统完成B.操作系统为每个用户级线程建立一个线程控制块C.用户级线程间的切换比内核级线程间的切换效率高D.用户级线程可以在不支持内核级线程的操作系统上实现24.下列选项中，可能将进程唤醒的事件是I.I/O 结束.某进程退出临界区仅 I仅.当前进程的时间片用完C.仅 I、D.I、25.下列关于系统调用的叙述中，正确的是.操作系统通过提供系统调用避免用户程序直接访问外设 .不同的操作系统为应用程序提供了统一的系统调用接口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.25 msB.20 msC.15 msD.10 ms28.在分段存储管理系统中，用共享段表描述所有被共享的段。若进程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.630.下列关于死锁的叙述中，正确的是 I.可以通过剥夺进程资源解除死锁II.死锁的预防方法能确保系统不发生死锁III.银行家算法可以判断系统是否处于死锁状态.当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态A.仅 II、B.仅 I、C.仅I、D.仅I、31.某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示页目录号(10 位)页号(10 位)页内偏移(12 位)虚拟地址 2050 1225H 对应的页目录号、页号分别是A.081H、101HB.081H、401HC.201H、101HD.201H、401H32.在下列动态分区分配算法中，最容易产生内存碎片的是A.首次适应算法B.最坏适应算法C.最佳适应算法D.循环首次适应算法33.OSI 参考模型的第 5 层(自下而上)完成的主要功能是A.差错控制B.路由选择C.会话管理D.数据表示转换34.100BaseT 快速以太网使用的导向传输介质是A.双绞线B.单模光纤C.多模光纤D.同轴电缆35.对于滑动窗口协议，如果分组序号采用3 比特编号，发送窗口大小为5，则接收窗口最大是A.2B.3C.4D.536.假设一个采用 CSMA/CD 协议的 100Mbps 局域网，最小帧长是 128 B，则在一个冲突域内两个站点之间的单向传播延时最多是A.2.56 sB.5.12 sC.10.24 sD.20.48 s37.若将 101.200.16.0/20 划分为 5 个子网，则可能的最小子网的可分配IP 地址数是A.126B.254C.510D.102238.某客户通过一个 TCP 连接向服务器发送数据的部分过程如题38 图所示。客户在 t0 时刻第一次收到确认序列号ack_seq=100 的段，并发送序列号 seq=100 的段，但发生丢失。若TCP 支持快速重传，则客户重新发送 seq=100 段的时刻是A.t1B.t2C.t3D.t439.若主机甲主动发起一个与主机乙的TCP 连接，甲、乙选择的初始序列号分别为 2018 和 2046，则第三次握手TCP 段的确认序列号是A.2018B.2019C.2046D.204740.下列关于网络应用模型的叙述中，错误的是A.在 P2P 模型中，结点之间具有对等关系B.在客户/服务器(C/S)模型中，客户与客户之间可以直接通信C.在 C/S 模型中，主动发起通信的是客户，被动通信的是服务器D.在向多用户分发一个文件时，P2P 模型通常比 C/S 模型所需时间短二、综合应用题：4147 小题，共70 分。41.(13 分)设线性表 L=(a1，a2，a，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：typedef struct node int data；struct node*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(n3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m(m1)个碗，每两位哲学家之间有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)21，计算 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)=6 227 020 800，但 f1(13)的返回值为 1 932 053 504，为什么两者不相等？要使f1(13)能返回正确的结果，应如何修改f1 源程序？(5)第 19 行 imul eax,ecx 表示有符号数乘法，乘数为Reax 和 Recx，当乘法器输出的高、低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 为路由器，主机 H1H4 的 IP 地址配置以及R 的各接口 IP 地址配置如图中所示。现有若干台以太网交换机(无 VLAN 功能)和路由器两类网络互连设备可供选择。请回答下列问题：(1)设备 1、设备 2 和设备 3分别应选择什么类型网络设备？(2)设备 1、设备 2 和设备 3中，哪几个设备的接口需要配置IP 地址？并为对应的接口配置正确的IP 地址。(3)为确保主机 H1H4 能够访问 Internet，R 需要提供什么服务？(4)若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题参考答案一、单项选择题1.B2.B3.C4.A5.C6.A7.D8.C9.B10.D11.B12.C13.A14.D15.D16.D17.B18.C19.B20.C21.A22.D23.B24.C25.C26.B27.C28.B29.C30.B31.A32.C33.C34.A35.B36.B37.B38.C39.D40.B42.【答案要点】(1)采用链式存储结构(两段式单向循环链表)，队头指针为 front，队尾指针为rear。(2)初始时，创建只有一个空闲结点的两段式单向循环链表，头指针front 与尾指针 rear 均指向空闲结点。如下图所示。二、综合应用题41.【答案要点】(1)算法的基本设计思想：算法分 3 步完成。第1 步，采用两个指针交替前行，找到单链表的中间结点；第 2 步，将单链表的后半段结点原地逆置；第 3 步，从单链表前后两段中依次各取一个结点，按要求重排。(2)算法实现：(3)算法的时间复杂度：参考答案的时间复杂度为 O(n)。队空的判定条件：front=rear。队满的判定条件：front=rear-next。(3)插入第一个元素后的队列状态：(4)操作的基本过程：43.【答案要点】/信号量semaphore bowl；/用于协调哲学家对碗的使用 semaphore chopsticksn；/用于协调哲学家对筷子的使用for(int i=0；in；i+)chopsticksi.value=1 ；/设置两个哲学家之间筷子的数量bowl.value=min(n-1，m)；/bowl.value n-1，确保不死锁CoBeginwhile(True)/哲学家 i 的程序思考；P(bowl)；/取碗P(chopsticksi)；/取左边筷子P(chopsticks(i+l)MOD n)；/取右边筷子就餐；V(chopsticksi)；V(chopsticks(i+1)MOD n)；V(bowl)；CoEnd44.【答案要点】(1)磁盘容量 =(30010200512/1024)KB=3 105 KB(2)依次访问的簇是 100 260、101 660、110 560、60 005。(3)第 100 530 簇在磁盘上的物理地址由其所在的柱面为使 f1(13)能返可正确结果，可将函数f1 的返回值类型改为 double(或 long long 或 long double 或 float)。(5)若乘积的高33 位为非全0 或非全 l，则 OF=1编译器应该在 imul 指令后加一条“溢出自陷指令”，使得 CPU 自动查询溢出标志 OF，当 OF=1 时调出“溢出异常处理程序”。46.【答案要点】第 1 行指令和第30 行指令的代码在同一页。号、磁头号、扇区号构成因为页大小为 4KB，所以虚拟地址的高20 位为虚拟页其所在的柱面号为?100530/(10200/2)?=100。号。第 1 行指令和第30 行指令的虚拟地址高20 位都是100530%(10 200/2)=530，磁头号为?530/(200/2)?=5。00401H，因此两条指令在同一页中。扇区号为(5302)%200=60。Cache 组数为 64/4=16，因此，主存地址划分中，低6将簇号转换成磁盘物理地址的过程由磁盘驱动程序完位为块内地址、中间4 位为组号 (组索引)、高 22 位为标成。记。读取第 16 行 call 指令时，只可能在指令Cache 第 0组45.【答案要点】中命中。(1)计算 f(l0)需要调用函数 f1 共 10次执行第16 行 call因为页大小为4KB，所以虚拟地址和物理地址的最低指令会递归调用 f1。12 位完全相同，因而call 指令虚拟地址0040 1025H中(2)第 12 行 jle 指令是条件转移指令。第16行 call 指的 025H=0000 0010 0101B=00 0000 100101B为物理地址令、第 20行 jmp 指令、第 30 行 ret 指令一定会使程序跳的低 12 位，故对应Cache 组号为 0。转执行。(3)第16 行 call指令的下一条指令的地址为004047.【答案要点】1025H+5=0040 102AH，故第 17 行指令的虚拟地址是(1)设备1：路由器，设备 2：以太网交换机，设备3：0040 102AH。call 指令采用相对寻址方式，即目标地址以太网交换机 (2)设备 1 的接口需要配置IP 地址；设备 1=(PC)+偏移量，call 指令的目标地址为0040 1000H，所的 IFl、IF2和 IF3接口的 IP 地址分别是：192.168.1.254、以 偏 移 量 =目 标 地 址 -(PC)=00401000H-0040192.168.1.1和 192.168.1.65。102AH=FFFF FFD6H。根据第 16 行 call 指令的偏移量字段为 D6 FF FF FF，可确定 M 采用小端方式。(3)R 需要提供 NAT 服务(4)主机 H4 会接收该数据报。(4)因为 f(13)=6 227 020 800，大于32 位 int 型数据可表示的最大值，因而f1(13)的返回值是一个发生了溢出的结果。