2020考研真题：河北建筑工程学院2020考研807计算机专业基础综合-A卷考试真题

（注意：所有答案必须写在答题纸上，做在试卷或草稿纸上无效）

重要提示：专业考试为1+1(3选1)模式，共150分，其中数据结构(试卷一)90分为必做题。计算机组成原理(试卷二)60 分、计算机网络(试卷三)60分、计算机操作系统(试卷四)60分，考生任选其中一个科目作答。在以下选做的科目前的方框内打勾。并在答题纸上注明所选做的试卷。

计算机组成原理

计算机网络

计算机操作系统

试卷一：数据结构（必做）

单选题(在每小题的四个备选答案中选出一个正确答案，每小题2分，共20分)

1

．

下面叙述正确的是（ ）。

A．

算法的执行效率与数据的存储结构无关

B．

算法的空间复杂度是指算法程序中指令(或语句)的条数

C．

算法的有穷性是指算法必须能在执行有限个步骤之后终止

D．

以上三种描述都不对

2．

下面哪一种情况不利于发挥堆排序的优势（ ）。

A．

待排序的数据量很大

B．

待排序的数据量小

C．

待排序的数据中有的数值很大

D．

待排序的数据相同率高

3．

栈和队列都是（ ）。

A．

顺序存储的线性结构

B．

链式存储的非线性结构

C．

限制存取点的非线性结构

D．

限制存取点的线性结构

4．

用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是（ ）。

A． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80

C． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40

5．

一个栈的输入序列为

1

,

2

,

3

,

...

,

n

，

若输出序列的第一个元素为

n，

输出第

i(1<=i<=n)

个元素是（ ）。

A．

不确定

B． i C． n-i D． n-i+1

6．

向一个栈顶指针为

hs

的链栈中插入一个

*s

结点时，应执行的操作为（ ）。

A． hs->next=s； B． s->next=hs； hs=s；

C． s->next=hs->next； hs->next=s； D． s->next=hs；hs=hs->next；

7．

若以

{4,5,6,3,8}

作为叶子结点的权值构造哈夫曼树，则带权路径长度是（ ）。

A． 55 B． 68 C． 59 D． 28

8．

对包含

N

个元素的哈希表进行查找，平均查找长度为（ ）。

A．

为

O(log

2

N)

B．

为

O

(

N

)

C．

不直接依赖于

N D．

上述三者都不是

9．

已知序列

(34,76,45,18,26,54,92,65)

，按照逐点插入法建立一棵二叉排序树,该二叉排序树的深度是（ ）。

A． 3 B． 4 C． 5 D． 6

10．

如果采用直接选择排序法来排序一个长度为

5，

且已按相反顺序排序的数组

，

共需的比较次数是

（ ）。

A． 1 B． 15 C． 8 D． 10

填空题(每空2分，共20分)

11

． 高度为k，且有

①

个结点的二叉树称为

②

二叉树。

12

． 对于一个图G的遍历,通常有两种方法，它们分别是

③

和

④

。

13

． 线性表的顺序存储结构是一种

⑤

存取的存储结构。线性表的链式存储结构是一种

⑥

存取的存储结构。

14

． a+b*(c-d)-e/f的后缀式为

⑦

。

15

． 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6，依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队序列为e2,e4,e3,e6,e5,e1，则栈容量至少应该是

⑧

。

16

． 设森林F对应的二叉树为A，它有n个结点，A的根为q，q的左子树结点个数为m，森林F中第一棵树的结点个数是

⑨

。

17

． 在一棵AVL树(高度平衡的二叉搜索树)中，每个结点的左子树高度与右子树高度之差的绝对值不超过

⑩

。

解答题(每题6分，共30分)

18

． 已知结点的中序序列和后序序列分别为：ABCEFGHD和ABFHGEDC，画出此二叉树，并且写出它的前序序列。

19

． 简述以下算法的功能

Status A ( LinkedList L )　//　L是无表头结点的单链表

{ if ( L && L->next　)

{ Q=L ;

L=L->next ;

P=L ;

while ( P->next ) P=P->next ;

P->next=Q ;

Q->next=NULL ;

}

return OK ;

}

以上算法的功能为：

20

． 有一组随机数25,84,21,47,15,27,68,35,20，现在采用某一种排序算法对它们进行排序，具体过程如下：

(1) 25 84 21 47 15 27 68 35 20

(2) 20 15 21 25 47 27 68 35 84

(3) 15 20 21 25 35 27 47 68 84

(4) 15 20 21 25 27 35 47 68 84

请问，根据以上情况判断所用的排序方法是什么?

21

． 已知有向图如图1所示，请写出该图所有的拓扑排序。

图1 有向图

22

．

有一份电文中共使用

6

个字符:

a,b,c,d,e,f

，

它们的出现频率依次为

6,5,4,3,2,1

，

请构造一棵哈夫曼树,并计算其带权路径长度

。

算法设计(每题10分，共20分)

23

． 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列，请写出算法。

24

． 已知一个数据值为整数的线性表，欲以表中第一个数据元素为参考点，将该表划分为左右两部分，使其参考点左边的每个数据元素值均小于等于参考点的值，而参考点右边的每个数据元素值均大于参考点的值。若不考虑空间复杂度，利用异地处理方式，设计一个求解该问题的有效算法。

试卷二：计算机组成原理（选做）

五、单选题（在每小题的四个备选答案中选出一个正确答案，每小题2分，共20分）

25

.

在集中式总线仲裁中

，（ ）

方式对电路故障最敏感。

A.

链式查询 B.

计数器定时查询 C.

独立请求 D.

分布式查询

26. 程序控制类指令的功能是（ ）。

A

.

进行算术运算和逻辑运算? B

.

进行主存与

CPU

之间的数据传送?

C

.

进行

CPU

和

I

/

O

设备之间的数据传送? D

.

改变程序执行顺序?

27.

某计算机字长是16位

，

它的存储容量是64KB

，

按字编址

，

它

的

寻址范围是

（ ）

。

A.

64K 　　

B.

32KB　　

C.

32K 　　

D.

16KB

28.

指令系统中采用不同寻址方式的目的主要是

（ ）

。

A.

实现存储程序和程序控制

B.

可以直接访问外存

C.

缩短指令长度，扩大寻址空间，提高编程灵活性　

D.

提供扩展操作码的可能并降低指令译码难度

29.

寄存器间接寻址方式中，操作数处在

（ ）中

。

A.

通用寄存器　　

B.

主存单元　　　　　

C.

程序计数器　　　D.

堆栈

30. 浮点数的表示范围和精度取决于（ ）。

A

.

阶码的位数和尾数的机器数形式

B

.

阶码的机器数形式和尾数的位数

C

.

阶码的位数和尾数的位数

D

.

阶码的机器数形式和尾数的机器数形式

31. 中断向量可提供（ ）。

A

.

被选中设备的地址

B

.

传送数据的起始地址

C

.

中断服务程序入口地址

D

.

主程序的断点地址

32. 计算机操作的最小时间单位是（ ）。

A

.

时钟周期

B

.

指令周期

C

.

CPU周期

D.

中断周期

33. 设某数x的真值为-

0.1010

，

在计算机中该数表示为

1

.0110

，

则该数所用的编码为

（ ）。

A

.

原码

B

.

补码

C

.

反码

D.

移码

34. 在主存和CPU之间增加Cache存储器的目的是（ ）。

A

.

增加内存容量

B

.

提高内存可靠性

C

.

解决CPU和主存之间的速度匹配问题

D

.

增加内存容量，同时加快存取速度

六、填空题（每空2分，共20分）

35．在异步

串行传输系统中

，若

字符格式为

：1位起始位、8位数据位、1位奇偶校验位和1位终止位。假设波特率为1

200bps

，

则此时的比特率是

。

36．假设Cache的工作速度是主存的5倍，且Cache访存命中率为9

8

%，

则采用Cache后

，

存储器性能提高了

倍。

37．系统总线按传输信息的不同分为地址总线、

总线

和

总线三大类。

38．条件转移、无条件转移、跳转、过程调用与返回、陷阱指令都属

类指令，这类指令在指令格式中所表示的地址不是

的地址，而是

的地址。

39．

RISC

的中文含义是

。

40．

设机器数字长为8位（其中1位为符号位），对于整数，当其是补码时，所能表示的十进制的范围是

至

。

七、综合应用题（第一小题8分，第二小题12分）

41.

假设主存容量为512K×

16位

，Cache容量为

4096

×

16位

，块长为4个16位的字，访存地址为字地址。

（1）在全相联映射方式下，设计主存的地址格式。（2分）

（2）在直接映射方式下，设计主存的地址格式。（3分）

（3）在二路组相联映射方式下，设计主存的地址格式。（3分）

42.

设某机有四个中断源A、B、C、D，其硬件排队优先次序为A，B，C，D，现要求将中断处理次序改为D，A，C，B。

（1）写出每个中断源对应的屏蔽字。?（4分）

（2）按下图时间轴给出的四个中断源的请求时刻，画出CPU执行程序的轨迹。设每个中断源的中断服务程序时间均为20s。?（8分）

试卷三：计算机网络（选做）

五、单项选择题：（每小题

2

分，共

20

分）

25．在OSI参考模型中，直接为

表示

层提供服务的是

（ ）

A.

会话

层

B. 传输层

C. 应用层

D. 网络层

2

6．在物理层接口特性中，用于

指明某条线上出现的某一电压的意义的是（ ）

A.

机械特性

B.

功能特性

C.

过程特性

D.

电气特性

27．网络协议主要要素为（

）

A

．数据格式、编码、信号电平　

B.

数据格式、控制信息、速度匹配

C.

编码、控制信息、同步　　　

D.

语法、语义、同步

28

. HDLC

协议对

1

111 1100 0111 1110 组帧后对应的比特串为

（ ）

A. 111110100 01111111 0

B. 111110100 01111101 01111110

C. 11111010 00111110 10

D. 111110100 01111110 01111101

29

. 数据链路层采用选择重传协议传输数据，发送方已发送了0~3号数据帧，现已收到0、1号帧的确认， 2号帧超时，则此时需要重传的帧数是（ ）

A.

1

B.

2

C.

3

D.

4

3

0

.

下列

交换方式中最适合实时性通信场合的

是

（ ）

A．

虚电路方式

B．

电路交换方式

C．数据

报

方式

D

．

各种方法一样

3

1

.

C类IP地址，每个网络可有（ ）台主机。

A

.

127

B

.

512

C

.

254

D

.

1024

3

2

. 在RIP协议中，

到某个

网络的距离为16，其意义是（ ）

A

.

存在循环路由

B

.

该网络为

直接

连接网络

C

.

到达该网络要经过15

次

转发

D

.

该网络不可达

3

3．

下

面

有4

个

字网掩码，

推荐

使用的

是

（ ）

A

.

127.192.0.0

B

.

255.128.0.0

C

.

176.0.0.0

D

.

96.0.0.0

3

4．主机甲与主机乙之间已建立一个TCP连接，双方持续有数据传输，且数据无差错与丢失。若甲收到1个来自乙的TCP段，该段的序号为191

9

、确认序号为204

8

、有效载荷为100字节，则甲立即发送给乙的TCP段的序号和确认序号分别是

（ ）

A. 204

8

、201

8

B. 204

8

、201

9

C. 2047、201

8

D. 2047、201

9

六、填空题（每空1分，共10分）

35. 计算机网络的基本功能是

和信息传递。

36.

技术是广域网技术的基础。

37.

Web浏览器向侦听标准端口的 Web服务器发出请求之后，在服务器响应的 TCP 报头中，源端口号是

。

38.

某通信链路的数据传输速率为1200bps，采用

8

相位调制，该链路的波特率

是

波特。

39. TCP/IP 模型由低到高分别为

层、网际层 、

层和应用层。

40. WWW上的每一个网页都有一个独立的地址，这些地址称为

。

41.

将IP地址转换为物理地址的协议是

。

42.

以太网端到端的往返时延2

τ

称为

，又称为碰撞窗口。以太网取 51.2u争用期的长度，并规定凡长度小于

字节的帧都是无效帧。

七、简答题（每小题5分，共10分）

43.

网络适配器的作用是什么?网络适配器工作在哪一层?

44.

TCP 和 UDP 的主要区别

是什么？

八、综合应用题（每小题

10

分，共

20

分）

45.

某单位分配到一个B类IP地址，其net-id为1

38

.2

28

.0.0.该单位有4000台机器，分布在16个不同地点。请分析：

（1）选用子网掩码为255.255.255.0是否合适？

（2）如果合适试给每一个地点分配一个子网号码，并算出每个主机IP地址的最小值和最大值。

46.

假定网络中的路由器B的路由表有如下的项目（这三列分别表示“目的网络”、“距离”和“下一跳路由器”）

N1

6

A

N2 2

C

N6 8 F

N8 4 E

N9 4 F

现在B收到从C发来的路由信息（这两列分别表示“目的网络”“距离”）：

N2

5

N3 8

N6 4

N8 3

N9 5

请给

出路由器B更新后的路由表（详细说明每一个步骤）。

试卷四：计算机操作系统（选做）

五、单项选择题（每题2分，共20分）

25.

操作系统的（ ）管理部分负责对进程进行调度。

A.

主存储器

B. 控制器

C. 运算器

D. 处理器

26.

用P、V操作管理临界区时，信号量的初值应定义为（ ）。

A.

-

1

B. 0

C. 1

D. 任意值

27.

通过硬件和软件的功能扩充，把原来独占的设备改造成能为若干用户共享的设备，这种设备称为（ ）。

A.

存储设备

B. 系统设备

C. 用户设备

D. 虚拟设备

28.

两个进程并发执行，一个进程要等待另一个进程发来消息，或者建立某个条件后再向前推进，这种制约性被称为进程的（

）。

A.

同步

B. 互斥

C. 调度

D. 执行

29

.

进程和程序的本质区别是（ ）。

A.

存储在内存和外存

B. 顺序和非顺序执行机器指令

C. 分时使用和独占使用计算机资源

D. 动态和静态特征

30

.

页式存储管理时，每读/写一个数据，要访问（

）次主存。

A.

4

B. 3

C. 2

D.1

31. 操作系统提供给程序员的接口是（ ）。

A.

进程

B. 系统调用

C. 库函数

D. B和C

32.

在文件系统中若采用一级目录结构，存在的最主要的一个问题是（

）。

A.

目录表的大小难以确定

B. 磁盘容量大时，文件检索太慢

C. 用户使用不方便

D. “重名”问题，即文件命名冲突

33.

死锁预防是保证系统不进入死锁状态的静态策略，其解决方法是破坏产生死锁的四个必要条件之一。下列方法中哪一个破坏了“循环等待”条件（

）。

A.

银行家算法

B. 一次性分配策略

C. 剥夺资源法

D. 资源有序分配法

34.

相关临界区是指（

）。

A.

一个共享资源

B. 并发进程中涉及相同变量的那些程序段

C. 并发进程中与共享变量有关的程序段

D. 一个独占资源

六、填空题（每空2分，共20分）

35.

现代操作系统中，申请和拥有资源的基本单位是

①

，其引入的根本目的是为了实现程序的并发执行。在此基础上，为了进一步提高系统内程序并发执行的速度，又引入了

②

的概念和机制。

36.

计算机外围设备和内存之间常用的数据传送控制方式有程序直接控制方法、

③

、

④

和通道方式。

37.

为了赋予操作系统某些特权，使得操作系统更加安全可靠地工作。实际操作系统中区分程序执行的两种不同运行状态是

⑤

态和

⑥

态。

38.

设有8页的逻辑空间，每页有1024字节，它们被映射到32块的物理存储区。那么，逻辑地址的有效位是

⑦

位，物理地址至少是

⑧

位。

39. 在页式管理中，页表的作用是实现从

⑨

到

⑩

的地址映射

。

七、综合题（每题10分，共20题）

40.

在采用页式存储管理的系统中，每页2KB，系统地址总线是16位。假定某时刻系统为用户的第0、1、2、3页分配的物理块号分别为2、4、6、8，请确定逻辑地址1301H的物理地址。

41.

在一个请求分页系统中，假如一个作业的页面走向为1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6，当分配给该作业的物理块数M为4时，应用下面的页面替换算法，分别计算在访问过程中所发生的缺页率。

（1）先进先出算法（FIFO）。

（2）最近最久未使用算法（LRU）。