2019年考研408计算机学科专业基础综合真题及答案2019年全国硕⼠研究⽣招⽣考试
计算机科学与技术学科联考
计算机学科专业基础综合试题
⼀、单项选择题：1~40⼩题，每⼩题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. 56
B. 57
C. 58
D. 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. 仅I
B. 仅II
C. 仅I、Ⅱ
D. 仅I、Ⅲ
5.下图所⽰的AOE⽹表⽰⼀项包含8个活动的⼯程。活动d
的最早开始时间和最迟开始时间分别是
B. 12和12
C. 12和14
D. 15和15
6.⽤有向⽆环图描述表达式(x+y)*((x+y)/x)，需要的顶点个
数⾄少是
A. 5
B. 6
C. 8
D. 9
7.选择⼀个排序算法时，除算法的时空效率外，下列因素中，
还需要考虑的是
I.数据的规模Ⅱ.数据的存储⽅式Ⅲ.算法的稳定性V.数据的初始状态
A. 仅Ⅲ
B. 仅I、Ⅱ
C. 仅Ⅱ、Ⅲ、IV
D. I、Ⅱ、Ⅲ、Ⅳ
8.现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采⽤线性探查(线性探测再散列)
法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插⼊到HT后，HT查失败的平均查长度是
A. 4
B. 5.25
C. 6
D. 6.29
9.设主串T=“abaabaabcabaabc”，模式串S=“abaab c”，采⽤KMP算法进⾏模式匹配，到匹配成功时为⽌，在匹配过程中进⾏的单个字符间的⽐较次数是
A. 9
B. 10
C. 12
D. 15
10. 排序过程中，对尚未确定最终位置的所有元素进⾏⼀遍处理称为⼀“趟”。下列序列中，不可能是快速排序第⼆趟结果的是
A. 5，2，16，12，28，60，32，72
B. 2，16，5，28，12，60，32，72
C. 2，12，16，5，28，32，72，60
D. 5，2，12，28，16，32，72，60
11. 设外存上有120个初始归并段，进⾏12路归并时，为实现最佳归并，需要补充的虚段个数是
B. 2
C. 3
D. 4
12. 下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是
A. 程序的功能都通过中央处理器执⾏指令实现
B. 指令和数据都⽤⼆进制表⽰，形式上⽆差别
C. 指令按地址访问，数据都在指令中直接给出
D. 程序执⾏前，指令和数据需预先存放在存储器中
13. 考虑以下C语⾔代码：
unsigned short usi=65535；
short si=usi；
执⾏上述程序段后，si的值是
A. -1
B. -32767
C. -32768
D. -65535
14. 下列关于缺页处理的叙述中，错误的是
A. 缺页是在地址转换时CPU检测到的⼀种异常
B. 缺页处理由操作系统提供的缺页处理程序来完成
C. 缺页处理程序根据页故障地址从外存读⼊所缺失的页
D. 缺页处理完成后回到发⽣缺页的指令的下⼀条指令执⾏
15. 某计算机采⽤⼤端⽅式，按字节编址。某指令中操作数的机器数为1234 FF00H，该操作数采⽤基址寻址
⽅式，形式地址(⽤补码表⽰)为FF12H，基址寄存器内容为F000 0000H，则该操作数的LSB(最低有效字节)所在的地址是
A. F000 FF12H
B. F000 FF15H
C. EFFF FF12H
D. EFFF FF15H
16. 下列有关处理器时钟脉冲信号的叙述中，错误的是
A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频
C. 时钟周期以相邻状态单元间组合逻辑电路的最⼤延迟为基准确定
D. 处理器总是在每来⼀个时钟脉冲信号时就开始执⾏⼀条新的指令
17. 某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采⽤寄存器、寄存器间接寻址⽅式。对于下列
给定部件，该指令在取数及执⾏过程中需要⽤到的是
I.通⽤寄存器组(GPRs)Ⅱ.算术逻辑单元(ALU)
Ⅲ.存储器(Memory)Ⅳ.指令译码器(ID)
A. 仅I、Ⅱ
B. 仅I、Ⅱ、Ⅲ
C. 仅Ⅱ、Ⅲ、IV
D. 仅I、Ⅲ、Ⅳ
18. 在采⽤“取指、译码/取数、执⾏、访存、写回”5段流⽔线的处理器中，执⾏如下指令序列，其中s0、s1、
s2、s3和t2表⽰寄存器编号。
I1：add s2，s1，s0 //R[s2]←R[s1]+R[s0]
I2：load s3，0(t2)//R[s3]←M[R[t2]+0]
I3：add s2，s2 s3 //R[s2]←R[s2]+R[s3]
I4：store s2，0(t2)//M[R[t2]+0]←R[s2]
下列指令对中，不存在数据冒险的是
A. I1和I3
B. I2和I3
C. I2和I4
D. I3和I4
19. 假定⼀台计算机采⽤3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总
线的⼯作频率为1333 MHz、总线宽度为64位，则存储器总线的总带宽⼤约是
A. 10. 66 GB/s
B. 32 GB/s
C. 64 GB/s
D. 96 GB/s
20. 下列关于磁盘存储器的叙述中，错误的是
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. 仅Ⅱ、Ⅲ、IV
D. I、Ⅱ、Ⅲ、IV
23. 下列关于线程的描述中，错误的是
A. 内核级线程的调度由操作系统完成
B. 操作系统为每个⽤户级线程建⽴⼀个线程控制块
C. ⽤户级线程间的切换⽐内核级线程间的切换效率⾼
D. ⽤户级线程可以在不⽀持内核级线程的操作系统上实现
24. 下列选项中，可能将进程唤醒的事件是
I. I/O结束Ⅱ. 某进程退出临界区Ⅲ. 当前进程的时间⽚⽤完
A. 仅I
B. 仅Ⅲ
C. 仅I、Ⅱ
D. I、Ⅱ、Ⅲ
25. 下列关于系统调⽤的叙述中，正确的是
I.在执⾏系统调⽤服务程序的过程中，CPU处于内核态
Ⅱ.操作系统通过提供系统调⽤避免⽤户程序直接访问外设
Ⅲ.不同的操作系统为应⽤程序提供了统⼀的系统调⽤接⼝
IV.系统调⽤是操作系统内核为应⽤程序提供服务的接⼝
A. 仅I、IV
B. 仅II、III
C. 仅I、Ⅱ、IV
D. 仅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 ms