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

2019 年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题

一、单项选择题：1~40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项符合试题要求。

1. 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是

x=0 ； while ( n>= ( x+l ) * ( x+l )) ；x=x+l

1/22)O( n)B. O( nD. C. A. O( log n)O( n)

BT 若将一棵树 T 转化为对应的二又树，则下列对 BT 的遍历中，其遍历序列与T 的后根遍历序列相同的2. 是

A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历 115 个结点，则 n 的值是对 n 个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有3. A. 56B. 57C. 58D. 60

中，删除某结点T 形成之后形成平衡二又树v T树 ) T插入，再将 w 在任意一棵非空平衡二又树( AVL4.221

与 T 的叙述中，正确的是 T T 。下列关于平衡二又树331 I. 若 v 是 T 的叶结点，则 T 与 T 可能不相同311

的叶结点，则T 与 T 一定不相同 T不是Ⅱ .若 v 311 T 与 T一定相31 的叶结点，则同 T若 v 不是Ⅲ .1 D. 仅 I、Ⅱ I、ⅢA. 仅IB. 仅IIC. 仅

网表示一项包含个活动的工程。活动下图所示的 AOE 8 d5. 的最早开始时间和最迟开始时间分别是

A.3和7B.12和12C. 12和 14 D.15和15 用有向无环图描述表达式 ( x+y ) *(( x+y ) /x) ，需要的顶点个数6.至少是 A.5B.6C.8D.9

7. 选择一个排序算法时， 除算法的时空效率外， 下列因素中，还需要考虑的是 算法的稳定性Ⅲ .数据的规模Ⅱ .数据的存储方式I. 数据的初始状态V. 、Ⅱ、Ⅲ、ⅣIIVD. 仅Ⅲ仅 I、Ⅱ仅Ⅱ、Ⅲ、 )，采用线性探查H( key) =key%7 现有长度为 11 8.且初始为空的散列表HT ，散列函数是 线性探测

再散列( 查找失败的平均查找 HT 98，20 依次插入到 HT

后，87法解决冲突将关键字序列，40， 30，6， 11，22， 长度是 6C. A. 4B. 5.256.29D.

算法进行模式匹配，到匹配成功时为止，，模”式串 S=“ abaabc9. ”，采用 KMP 设主串 T=“ abaabaabcabaabc 在匹配过程中进行的单个字符间的比较次数是

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 语言代码：

unsigned short usi=65535 ； short si=usi ； 执行上述程序

段后，si 的值是 A. -1B. -32767C. -32768D. -65535 14. 下列关于缺页处理的叙述中，错误的是 A. 缺页是在地址

转换时 CPU 检测到的一种异常 B. 缺页处理由操作系统提供的缺页处理程序来完成 C. 缺页处理程序根据页故障地址从外存读入所缺失的页 D. 缺页处理完成后回到发生缺页的指令的下一条指令执行 1234 FF00H ，该操作数采用基址寻址15.

某计算机采用大端方式，按字节编址。某指令中操作数的机器数为

F000 0000H ，则该操作数的LSB ( 最低有效字方式，形式地址 ( 用补码表示 ) 为 FF12H，基址寄存器内容为 节 ) 所在的

地址是 A. F000 FF12HB. F000 FF15HC. EFFF FF12HD. EFFF

FF15H

16. 下列有关处理器时钟脉冲信号的叙述中，错误的是 A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成 B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频 C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定 D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令

某指令功能为 R[r2] ←R[r1]+M[R[r0]] ，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列17. 给定部件，该指令在取数及执行过程中需要用到的是 I. 通用寄存器组 ( GPRs)Ⅱ .算术逻辑单元 ( ALU ) ( ID )指令译码器 ( Memory )Ⅳ .Ⅲ .存储器

A. 仅 I、ⅡB. 仅 I 、Ⅱ、ⅢC. 仅Ⅱ、Ⅲ、 IVD. 仅 I 、Ⅲ、Ⅳ

在采用 “取指、译码 /取数、执行、访存、写回 ”5段流水线的处理器中，执行如下指令序列，其中s0、 s1、18. 表示寄存器编号。 t2 、 s3 和s2

s0s1，//R[s2] ← R[s1]+R[s0]： add s2，I1 //R[s3] ← M[R[t2]+0]： load s3， 0( t2)I2 s2，← R[s2]+R[s3]： add s2//R[s2] s3I3 R[s2]←， 0( t2)： store s2//M[R[t2]+0]I4 下列指令对中，不存在数据冒险的是 A.I1和I3B.I2和 I3C.I2和I4D.I3和 I4

DDR3-1333 ，即内存条所接插的存储器总假定一台计算机采用 3通道存储器总线，配套的内存条型号为19.

1333 MHz 、总线宽度为 位，则存储器总线的总带宽大约是线的工作频率为

A. 10. 66 GB/sB. 32 GB/sC. GB/sD. 96 GB/s 下列关于磁盘存储器的叙述中，错误的是20. 磁盘的格式化容量比非格式化容量小A. 扇区中包含数据、地址和校验等信息B. 磁盘存储器的最小读写单位为一个字节C. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成D. 位，32 CPU 主频为 1 GHz ，设备接口中的数据缓冲寄存器为21.某设备以中断方式与CPU 进行数据交换， CPU个时钟周期，则为 1000 50kB/s。若每次中断开销 ( 包括中断响应和中断处理 ) 设备的数据传输率为

时间的百分比最多是输出的时间占整个 CPU 用于该设备输入 / 12. 5%5%D. A. 1.25%B. 2.5%C. 方式的叙述中，正确的是22. 下列关于 DMA 传送前由设备驱动程序设置传送参数I. DMA II. 数据传送前由 DMA 控制器请求总线使用权

Ⅲ .数据传送由 DMA 控制器直接控制总线完成 传送结束后的处理由中断服务程序完成IV.DMA IVIV、Ⅱ、Ⅲ、 A. 仅IIB. 、Ⅱ仅Ⅰ、Ⅲ、ⅣD. 仅Ⅱ、Ⅲ、C.

--- -----

23. 下列关于线程的描述中，错误的是 A. 内核级线程的调度由操作系统完成 B. 操作系统为每个用户级线程建立一个线程控制块 C. 用户级线程间的切换比内核级线程间的切换效率高

D. 用户级线程可以在不支持内核级线程的操作系统上实现 24. 下

列选项中，可能将进程唤醒的事件是 结束I. I/O 某进程退出

临界区 Ⅱ .Ⅲ. 当前进程的时间片用完

仅Ⅲ仅IC. 仅 I、ⅡD. I、Ⅱ、Ⅲ 25. 下列关于系统调用的叙述中，正确的是

操作系统通过提供系统调用避免用户程序直接访问外设Ⅱ . 不同的操作系统为应用程序提供了统一的系统调用接口Ⅲ . 系统调用是操作系统内核为应用程序提供服务的接口IV. IVI、Ⅱ、、

Ⅲ、ⅣIIII II、IVB. 仅 、A. 仅 I 仅仅D. C.

26. 下列选项中，可用于文件系统管理空闲磁盘块的数据结构是 I. 位图Ⅱ .索引节点Ⅲ .空闲磁盘块链Ⅳ .文件分配表 ( FAT)

A. 仅 I、ⅡB. 仅Ⅰ、Ⅲ、ⅣC. 仅 l、ⅢD. 仅Ⅱ、Ⅲ、Ⅳ 就绪队列 Q1 采用时间片轮转调度算法，时间片为 10ms；系统采用二级反馈队列调度算法进行进程调度。27.

就绪队列 Q2 采用短进程优先调度算法；系统优先调度Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2

Q1； Q1 中的进程执行一个时间片后，若未结束，则转入Q2 。若当前中的进程；新创建的进程首先进入

Q1、Q2 为空，系统依次创建进程Pl 、P2 后即开始进程调度 Pl、P2 需要的 CPU 时间分别为 30ms 和 20ms， 则进程 P1、 P2 在系统中的平均等待时间为 D. 10 msA. 25 msB. 20 msC. 15 ms

错误P1 和 P2 共享段 S，下列叙述中， 在分段存储管理系统中， 用共享段表描述所有被共享的段。若进程28. 的是

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. 银行家算法可以判断系统是否处于死锁

状态 当系统出现死锁时，必然有两个或两个以上的进程处

于阻塞态Ⅳ . I、Ⅱ、Ⅲ、Ⅲ、ⅣI仅C. B. 仅 I、Ⅱ、Ⅳ A. 仅II 、Ⅲ仅D.

某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示31. )页目录号 ( 10 位)页号 ( 10 位)位( 12 页内偏移

对应的页目录号、页号分别是2050 1225H 虚拟地址

D. 201H 、 401H101H 201H、C. 081H、A. 081H 101HB. 、 401H

在下列动态分区分配算法中，最容易产生内存碎片的是32. D. 首次适应算法B. 最佳适应算法C. 最坏适应算法循环首次适应算法A.

) 完成的主要功能是层参考模型的第 33.OSI 5 ( 自下而上 D. C. 会话管理A. 差错控制数据表示转换B. 路由选择 34. 100BaseT 快速以太网使用的导向传输介质是

同轴电缆D. C. 多模光纤B. A. 双绞线单模光纤 ，则接

收窗口最大是5比特编号，发送窗口大小为3 35.对于滑动窗口协

议，如果分组序号采用 2A. C. 3B. D.

--- -----

36. 假设一个采用 CSMA/CD 协议的 100Mbps 局域网，最小帧长是 128 B ，则在一个冲突域内两个站点之间的单向传播延时最多是

A. 2.56 μsB. 5.12 μsC. 10.24 μsD. 20.48 μs 个子网，则可能的最小子网的可分配划分为 5 200. 16. 0/20 IP 地址数是若将 101.37. 1022510D. B. 2C. A. 126

连接向服务器发送数据的部分过程如题图所TCP 38 某客户通过一个38.

时刻第一次收到确认序列号 的段，并发送ack_seq=100 t示。客户在0

支持快速重传，则客户重TCP 序列号 seq=100 的段，但发生丢失。若

段的时刻是 seq=100 新发送 A. tB. tD. tC. t 31 42

连接，甲、乙选择的初始序列TCP 若主机甲主动发起一个与主机乙的39.

段的确认序列号是，则第三次握手TCP 号分别为 2018 和 2046 A. 2018B. 2019D. 2047C. 2046

下列关于网络应用模型的叙述中，错误的是40. 模型中，结点之间具有对等关系在 P2P A.

模型中，客户与客户之间可以直接通信服务器 ( C/S) B. 在客户 /

模型中，主动发起通信的是客户，被动通信的是服务器在 C/S C. 模型所需时间短模型通常比 C/S D. 在向多用户分发一个文件时， P2P

二、综合应用题：41~47 小题，共 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'= ( a，1 a， a， a， a， a? ) 。 3nn-2n-12 要求： ( 1)给出算法的基本设计思想

( 2)根据设计思想，采用C 或 C++ 语言描述算法，关键之处给出注释。 ( 3)说明你所设计的算法的时间复杂度。

42. ( 10 分 ) 请设计一个队列， 要求满足： ①初始时队列为空； ②入队时， 允许增加队列占用空间； ③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④人队操作和出队操作的时间 复杂度始终保持为 O( 1) 。请回答下列问题：

( 1) 该队列应该选择链式存储结构，还是顺序存储结构？ ( 2) 画出队列的初始状态，并给出判断队空和队满的条件 ( 3) 画出第一个元素入队后的队列状态。 ( 4) 给出入队操作和出队操作的基本过程。

( 8 分 ) 有 n( n≥3)位哲学家围坐在一张圆桌边， 每位哲学家交替地就餐和思考。 在圆桌中心有 m( m≥1)个碗，43. 1 根筷子。每位哲学家必须取到一个碗和两侧的筷子之后，才能就餐，进餐完毕，每两位哲学家之间有

将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信

号量的 P、V 操作 ( wait () 、signal() 操作 ) 描述上述过程中的互斥与同步， 并说明所用信号量及初值的含义。 200 个扇区，扇区大小( 7 分 ) 某计算机系统中的磁盘有300 个柱面，每个柱面有 10 个磁道，每个磁道有44.

为 512B 。文件系统的每个簇包含2 个扇区。请回答下列问题：

磁盘的容量是多少？( 1)

假设磁头在 85号柱面上，此时有 4 个磁盘访问请求， 簇号分别为： 100260、60005、101660 和 110560。( 2) 若采用最短寻道时间优先 ( SSTF) 调度算法，则系统访问簇的先后次序是什么？

I/O 系统的什么程第 100530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由( 3) 序完成的？

--- -----

45.( 16 分) 已知 f( n) =n ！=n×( n-l) ×( n-2) ×? ×2×1，计算 f( n) 的 C 语言函数 fl 的源程序 ( 阴影部分 ) 及其在 32

上的部分机器级代码如下：位计算机 M

其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，

计算机M 按字节编址， int 型数据占 32 位。请回答下列问题：

计算 f( 10) 需要调用函数f1 多少次？执行哪条指令会递归调用f1？( 1)

上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？( 2)

16 行 call 指令采用相对寻址方式，根据第 16 行 call 指令，第 17 行指令的虚拟地址应是多少？已知第( 3)

该指令中的偏移量应是多少( 给出计算过程 ) ？已知第 16 行 call 指令的后 4 字节为偏移量， M 采用大 端还是小端方式？

f1( 13) 能返回正f ( 13) =6 227 020 800 ，但 f1( 13) 的返回值为 1 932 053 504，为什么两者不相等？要使( 4) 确的结果，应如何修改f1 源程序？

R[eax] 和 R[ecx] ，当乘法器输出的高、低32 位乘积第 19 行 imul eax,ecx 表示有符号数乘法，乘数为( 5)

之间满足什么条件时，溢出标志OF=1？要使 CPU 在发生溢出时转异常处理，编译器应在imul 指令 后加一条什么指令？

4KB ，则第 1 行(7 分)对于题45，若计算机 M 的主存地址为32 位，采用分页存储管理方式，页大小为46.

push 指令和第30 行 ret 指令是否在同一页中( 说明理由 ) ？

若指令 Cache 有 行，采用 4 路组相联映射方 式，主存块大小为 B ，则 32 位主存地址中，哪几位表示块内地址？哪儿位表示Cache 组号？哪几位表

示标记 ( tag) 信息？读取第 16行 call 指令时，只可能在指令Cache 的哪一组中命中 ( 说明理由 ) ？

R 的各接口 IP 地址( 9 分 ) 某网络拓扑如题 47 图所示， 其中 R 为路由器， 主机 H1~H4 的 IP 地址配置以及47. ( 无 VLAN 功能 ) 和路由器两类网络互连设备可供选择。配置如图中所示。现有若干台以太网交换机 请回答下列问题：

分别应选择什么类型网络设备？ 2 1、设备和设备 3设备( 1)

IP 和设备 3地址？并为对应的接口配置正确的IP 中，哪几个设备的接口需要配置地 2 设备 1、设备( 2) 址。

为确保主机 H1~H4 能够访问 Internet， R 需要提供什么服务？( 3)

若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？( 4)

--- -----

2019 年全国硕士研究生招生考试 计算机科学与技术学科联考 计算机学科专业基础综合试题参考答

案

42. 一、单项选择题 ，队头指 ) 采用链式存储结 【答案要点】

构 ( 两段式单向循环链表( 1) 5.C3.C4.A1.B2.B 10.D6.A8.C9.B7.D。 rear针为 front ，队尾指针为

15.D13.A14.D11.B12.C初始时，创建只有一个空闲结点的两段式单向循环( 2) 20.C18.C19.B16.D17.B 均指向空闲结点。如下 rear 链表，头指针front 与尾指针 25.C22.D23.B24.C21.A 图

所示。 30.B26.B29.C27.C28.B 35.B33.C34.A31.A32.C 40.B39.D36.B37.B38.C

。队空的判定条件：front==rear 二、综合应用题 。队满的判定条件：front==rear->next 【答案要点】41. 算法的基本设计思想：( 1) 插入第一个元素后的队列状态：( 3) 步，采用两个指针交替前行，步完成。第3 1 算法分 步，将单链表的后半段结点原 2 找到单链表的中间结点；第 步，从单链表前后两段中依次各取一个结点，地逆置；第 3 按要求重排。 算法实现：( 2) 操作的基本过程：( 4) 【答案要点】43. 信号量// ； //用于协调哲学家对碗的使用semaphore bowl 用于协调哲学家对筷子的使// semaphore chopsticks[n] ； 用 i++ )；for ( int i=0 ； iP( chopsticks[ ( i+l ) MOD n] ) // 算法的时间复杂度：( 3) 就餐； 。O( n) 参的时间复杂度为 ；V( chopsticks[i] ) ；V( chopsticks[ ( i+1 ) MOD n] )

---

-----

为使 f1 ( 13) 能返可正确结果，可将函数

f1 的返回值类；V

( bowl ) }。或 float ) 或 long long 或 long double 型改为 double ( CoEnd( 5) 若乘积的高 33 位为非全 0 或非全 l ，则 OF=1 编译器应该在imul 指令后加一条“溢出自陷指令”，使 【答案要点】44. 得 CPU 自动查询溢出标志 OF ，当 OF=1 时调出 “溢出异常 5 K 10512/1024 ) KB=3×200( 1) 磁盘容量 =( 300×10×× 处理程序 ”。 B 依次访问的簇是( 2) 。110 560101 660 、、

60 005100 260 、 46.【答案要点】 簇在磁盘上的物理地址由其所

在的柱面( 3) 第 100 530 第 1 行指令和第 30 行指令的代码在同一页。 号、磁头号、扇区号构成 因为页大小为 4KB ，所以虚拟地址的高20 位为虚拟页

。×200/2) ?=100 ?100530/( 10其所在的柱面号为 号。第 1 行

指令和第30 行指令的虚拟地址高20 位都是

100530% ( 10 ×200/2 ) =530 ，磁头号为 ?530/ ( 200/2 ) ?=5。00401H ，因此两条指令在同一页中。

扇区号为 ( 530×2) 0=60 。 Cache 组数为 /4=16 ，因此，主存地址划分中，低6 将簇号转换成磁盘物理地址的过程由磁盘驱动程序完 4 位为组号 ( 组索引 ) 、高 22 位为标位为块内地址、中间 成。 记。

读取第 16 行 call 指令时，只可能在指令Cache 第 0组 【答 案要点】45. 中命中。 call16 共 10行( 1) 计算 f( l0 )

需要调用函数 f1 次执行第 ，所以虚拟地址和物理地址的最低4KB 因为页大小为 。 f1指令会递归调用 指令虚拟地址位完全相同，因而12 call 中0040 1025H 指行指令是条件转移指令。第16 call ( 2) 第 12 行 jle 025H=0000 0010 0101B=00 0000 100101B的为物理地址 指令一定会使程序跳 ret 30 令、第 20行 jmp 指令、第行 。的低 12 位，故对应Cache 组号为 0 转执行。

(3)第16 行 call指令的下一条指令的地址为0040 【答案要点】47. 行指令的虚拟地址是，故第1025H+5=0040 102AH 17 ：3设备( 1)1：路由器，设备 2：以太网交换机，设备 指令采用相对寻址方式，即目标地址0040 102AH 。 call 1 ( 2) 设备 1 的接口需要配置地址；设备IP 以太网交换机 ，所 call 指令的目标地址为0040 1000H =( PC) +偏移量，

192.168.1.2接口的、IF2和 IF3 IP 地址分别是：的 IFl 、 -( PC) =00401000H-0040量偏以 移 = 目 址地 标 。和 192.168.1.65 192.168.1.1 指令的偏移量字。根据

第 call 16 行102AH=FFFF FFD6H 服务( 3) R NAT 需要提供 采用小端方式。，可确定段为 D6 FF FF FF M 会接收该数

据报。( 4)主机H4 型数据可因为( 4) f( 13) =6 227 020 800

32 ，大于位 int

的返回值是一个发生了溢出f1 ( 13 ) 表示的最大值，因而 的结果。

专业资料可修改可编 范文范可行性研究报告指导范

---