2021考研真题：河北建筑工程学院2021考研学硕 808计算机专业基础综合考试真题

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

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

计算机组成原理

计算机网络

计算机操作系统

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

一、单选题（20分，每题2分）

1. 从逻辑上可以把数据结构分为（

）两大类。

A.

动态结构、静态结构

B.

顺序结构、链式结构

C

.

线性结构、非线性结构

D

.

初等结构、构造型结构

2

.

数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称为（

）。

A.

存储结构

B.逻辑结构

C

.

顺序存储结构

D

.

链式存储结构

3

.

下列时间复杂度中最坏的是（

）。

A.

O(

1) B.

O(n) C.

O

(log

2

n) D.

O

(n

2

)

4

.

设有一个顺序栈S，元素A

,B,C,D,E,F,

依次进栈，如果6个元素出栈的顺序是B

,D,C,F,E,A

，则栈的容量至少应是（

）。

A.

3

B.

4

C.

5

D.

6

5

.

在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（

）。

A.

p

->next=s;s->next=p->next; B. s->next=p->next;p->next=s;

C. p->next=s;p->next=s->next; D. p->next=s->next;p->next=s;

6

.

设数组data[m]作为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）。

A．front=front+1 B．front=(front+1)%(m-1)

C．front=(front-1)%m D．front=(front+1)%m

7

.

树最适合用来表示（

）。

A.

有序数据元素

B.

元素之间具有分支层次关系的数据

C.

无序数据元素

D.

元素之间无联系的数据

8

.

下面结论中不正确的是（

）。

A．关键路径是

AOE网中

从源点到汇点的最长路径

B．按广度优先搜索遍历图时，与始点相邻的结点先于不与始点相邻的结点访问。

C．在拓扑序列中，任意两个相继结点Vi和

Vj

都存在从V

i

到

Vj

的路径。

D．图的邻接多重表中，表中结点的数目是图中边的条数。

9

.

设一组记录的关键字序列为{

46,

79,56,38,40,84

}，

则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（

）。

A.

{

40,38,46,56,79,84} B.

{

40,38,46,79,56,84}

C.

{38,

40,46,56,79,84} D.

{

40,38,46,84,56,79}

1

0.

二叉排序树的查找效率与二叉树的（

）有关，在（

）时其查找效率最低。

A.

高度，呈单枝树

B.

结点的多少，结点太多

C.

树型，完全二叉树

D.

树型，呈单枝树

二、填空题（20分，每空2分）

11.

(1)

是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

12. 已知一棵完全二叉树的结点总数为90个，则最后一层的结点数为

(2)

。

13. 设有一棵二叉树，其先序遍历序列为ABCDEFG，中序遍历序列为CBAEDFG，则该二叉树的后序遍历序列是

(3)

。

14.

有31条边的无向连通图，至少有

(4)

个顶点，至多有

(5)

个顶点。

15.

已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为35的元素时，查找成功的比较次数为

(6)

。

16.在一个图中，所有顶点的度数之和等于所有边数的

(7)

倍。

17.

顺序查找、折半查找和分块查找，都属于

(8)

查找。

18.

对于给定的键值序列{ 12,13,11,18,60,15,7,40,25,100 }，用筛选法建堆，必须从哪个键值开始？

(9)

。

19.

(10)

存储是一种将关键字转换为存储地址的。

三、解答题（30分）

20

.什么是线索二叉树？请简述在中序线索二叉树中查找指定结点的直接前趋和直接后继的基本思想。(5分）

21

.

设散列函数为H(K)= K %13 ，散列表的地址空间为区间[0,15]，开始散列表为空，用线性探测法解决冲突，请画出依次插入键值

19,01,23,14,55,20,84,27,68,11,10,77

后的散列表,并求对该表的平均查找长度ASL。

（6分）

22

.

假定用于通信的电文由字符集{

a,b,c,d,e,f,g,h }

中的8个字母组成，各字母在电文中出现的频率分别为{

5,

25,3,6,10,11,36,4 }

。要求：

（

1）根据各字母的出现频率，构造相应的哈夫曼树；

（

2）计算它的带权路径长度；

（

3）为这8个字母设计Huffman编码。

（本题共9分）

23

.

画出如下图所示图的MST，并分别按照普里姆算法和克鲁斯卡尔算法生成最小生成树中各边的次序写出各条边。

（6分）

注： ① 边的表示方法：（1，2）1 ，表示1和2之间的一条边，权值为1；

② 规定以1为最小生成树的根结点。

24

.

简述以下算法的功能。（4分）

void A(LinkList &L,int n)

{

L=(LinkList)malloc(sizeof(LNode));

r=L;

for(i=1;i<=n;++i)

{

p=(LNode *)malloc(sizeof(LNode));

scanf(p->data);

r->next=p;

r=p;

}

r->next=Null;

}

四、算法设计题（20分）

25

.

已知一个顺序存储的线性表的元素非递减有序排列，给出顺序表存储结构的定义，并编写算法删除表中多余的值相同的元素的高效算法。（8分）

26.

编写先序非递归算法，实现二叉树的左右子树的交换（给出二叉树存储结构的定义，用到其他辅助结构请给出相关函数的说明，关键部分请给出注释）。（12分）

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

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

27

.

计算机只懂机器语言，而人类熟悉高级语言，故人机通信必须借助（

）。

A.

编译程序

B.

编辑程序

C.

连接程序

D.

载入程序

28.

一般8位的微型机系统以16位来表示地址，则该计算机系统有（

）个地址空间。

A

.

256

B

.

65535

C

.

65536

?

D

.

131072

29.

在各种异步通信方式中，

（

）

速度最快。

A.

不互锁

B.

半互锁

C.

全互锁

D.

总互锁

30.

不同的信号共用一组信号线，分时传送，这种总线传输方式是

（

）

传输。

A.

猝发

B.

并行

C.

复用

D.

串行

31.

一个512

KB

的存储器，其地址线和数据线的总和是

（

）

。

A.

17

B.

19

C.

27

　　　D.

28

32.

磁盘转速提高一倍，则

（

）

。

A

.

平均查找时间缩小一半

B

.

其存取速度也提高一倍

C

.

不影响查找时间

D

.

平均查找时间增加一倍

33.

设机器字长为64位，存储容量为128

MB

，若按字编址，它的寻址范围是

（

）

。

A

.

16

MB

B

.

16M

C

.

32

MB

D

.

32

M

34.

设寄存器内容为11111111，若它等于-0，则为

（

）

。

A

.

原码

B

.

补码

C

.

移码

D.

反码

35.

加法器采用先行进位的目的是

（

）

。

A

.

优化加法器的结构

B

.

节省器材

C

.

加速传递进位信号

D.

增强加法器结构

36.

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

（

）

中。

A

.

通用寄存器

B

.

堆栈

C

.

主存单元

D

.

缓存

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

37．

设机器字长为16位，存储器按字节编址，C

PU

读取一条单字长指令后，P

C

值自动加_

_______

。

38．

直接、间接、立即三种寻址方式指令的执行速度，由快至慢的排序是_

_____________

。

39．

某机有四级中断，优先级从高到低为1→2→3→4。若将优先级顺序修改，改后1级中断的屏蔽字为1011，2级中断的屏蔽字为1111，3级中断的屏蔽字为0011，4级中断的屏蔽字为0001，则修改后的优先顺序从高到低为_

_____________

。

40．

计算机操作的最小单位时间是_

____________

周期。

41．

在控制器的控制方式中，机器周期内的时钟周期个数可以不相同，这属于_

_______

控制。

42．

同一高级语言

（可以/不可以）在不同形式的计算机上执行。

4

3．计算机的

_______________

单元和

_______________

单元合称为A

LU

。

4

4．标准的

ASCII

码是

__________

位。

4

5．设寄存器位数为8位，机器数采用补码形式（含1位符号位）。对应于十进制数-27，寄存器内容为_

___________

。

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

46.

假设磁盘采用

DMA

方式与主机交换信息，其传输速率为2

MB/s

，而且D

MA

的预处理需1000个时钟周期，D

MA

完成传送后处理中断需500个时钟周期。如果平均传输的数据长度为4

KB

，试问在硬盘工作时，50

MHz

的处理器需用多少时间比率进行D

MA

辅助操作（预处理和后处理）。

47.

某模型机共有64种操作，操作码位数固定，且具有以下特点：

（1）采用一地址或二地址形式；

（2）有寄存器寻址、直接寻址和相对寻址（位移量为-128～+127）三种寻址方式；

（3）有16个通用寄存器，算术运算和逻辑运算的操作数均在寄存器中，结果也在寄存器中；

（4）取数/存数指令在通用寄存器和存储器之间传送数据；

（5）存储器容量为1

MB

，按字节编址。

要求设计算术逻辑指令、取数/存数指令和相对转移指令的格式，并简述理由。

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

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

2

分，共

20

分）

27．MAC地址通常存储在计算机的（ ）。

A.网卡上

B.内存中

C.高速缓存中

D.硬盘上

2

8．如果子网掩码是 255.255.255.224，那么主机 218.22.50.40所在的驻留子网是（ ）。

A.218.22.50.0 B.218.22.50.224 C.218.22.50.32 D.218.22.50.40

29．某公司申请到一个 C类网络，出于地理位置上的考虑，必须切割成

12

个子网，那么子网掩码可以设置为（ ）。

A.255.255.255.0 B.255.255.255.192 C.255.255.255.224 D.255.255.255.240

30

.

浏览器与 Web服务器之间使用的协议是（ ）。

A.DNS B.SNMP C.HTTP D.SMTP

31

.

转发数据包时，网络层所使用的主要信息依据是（ ）。

A.IP路由表

B.MAC地址表

C.ARP缓存

D.端口列表

32

.

数据链路层传输的 PDU是（ ）。

A.比特流

B.字节

C.数据帧

D.分组

33

.

关于 OSPF协议和 RIP协议，下列说法正确的是（ ）。

A.OSPF协议和 RIP协议都是静态路由

B.OSPF协议属于距离向量型路由协议，RIP协议属于链路状态型路由协议

C.OSPF协议适合在小型的、动态的互联网上使用，而 RIP协议适合在大型的、动态的互联网上使用

D.OSPF协议适合在大型的、动态的互联网上使用，而 RIP协议适合在小型的互联网上使用

34

.

在 Internet上，大学或教育机构类别的域名中一般包括（ ）。

A.edu B.com C.gov D.org

35．下面的 IPv6地址，不符合书写规范是（ ）。

A.12AB:0:0:CD30:: B.FF05::B3 C.::128.10.2.1 D.FE80::12::A2

36．常用的传输介质中，带宽最大、传输信号衰减最小、抗干扰能力最强的是（ ）。

A.同轴电缆

B.光纤

C.双绞线

D.无线电磁波

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

37．波分多路复用技术主要用于

通信。

38．实现封装成帧、透明传输和差错检测功能的层次是

。

3

9．一般来说，网络协议的三要素由

、

和同步三部分组成。。

4

0．DNS服务器的作用是将域名转换成

。

41．计算机网络中， ARP 协议用于完成 IP 地址到

的解析任务。

42．TCP 协议通过三次握手建立连接，通过

次握手释放连接。。

43．IPv6的地址长度是

位二进制位。

44．适配器从网络上收到的发往本站的帧包括：

、 _

和多播帧。

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

45.

常用的局域网的网络拓扑结构有哪些？现在最流行的是哪种结构？

46. 在以太网中，常用的有线通信媒体有哪些？局域网常用的通信媒体是哪种？高速主干网使用哪种通信媒体？

八、综合应用题（每小题

10

分，共

20

分）

47.

现有一个 C 类网段 19

5

.16

2

.

9

0.0，要将其划分为 6 个子网，请问如何指定子网掩码？每个子网的网络地址、可分配的主机地址范围是多少？

48.

假设路由器 X 的路由表有如下左表所示的项目（三列分别表示目的网络、距离、下一跳路由器）：

现在 X 收到从路由器 C 发来的路由信息如上右表所示（两列分别表示目的网络、距离）。

试求出路由器 X 更新后的路由表（请详细说明每一个路由项的由来）。

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

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

27．操作系统的主要功能是管理计算机系统中的（

）。

A．进程 B．作业 C．资源 D．程序和数据

28．按照作业到达的先后次序调度作业，排队等待时间最长的作业被优先调度，这是指（ ）调度算法。

A．先来先服务 B．计算时间短的作业优先

C．响应比高者优先 D．优先级

29．“中断”的概念是指（

）。

A．暂停处理机执行 B．暂停处理机对现行程序的执行

　 C．停止整个系统运行 D．使处理机空转

30．段页式存储管理中的地址格式是（

）地址。

　 A．线性 B．一维 C．二维 D．三维

31．用户程序的逻辑地址可以不连续的存储管理方式是（

）。

　 A．固定分区 　　 B．可变分区 　 C．页式 D．段页

32．逻辑文件的组织形式是由（

）决定的。

A．存储介质特性 B．操作系统的管理方式 C．主存容量 　　 D．用户

33．磁盘是共享设备，每一时刻（

）进程与它交换信息。

A．可有任意多个 B．限定n个 C．至少有一个　 D．最多有一个

34．硬件采用了中断和通道技术，使得（

）。

A．CPU与外设能紧密结合 B．CPU与外设能并行工作

　 C．CPU速度提高 D．外设速度提高

35．作业调度选中一个作业后，按作业控制说明书中第一个作业的要求创建该作业的进程，并使进程的状态为（

）。

A．就绪 B．运行 C．等待 D．收容

36．可重定位内存分区分配的目的为（ ）。

　 A．解决碎片问题 B．便于多作业共享内存

　 C．方便回收空闲区

D．摆脱用户干预

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

37．可变分区存储管理中，分区的长度不是预先固定的，而是按

①

来划分的；分区个数也不是预先确定的，而是由

②

决定的。

38．进程通信根据

③

分为高级通信和低级通信，PV操作属于

④

。

39．进程调度的职责是按给定的

⑤

从

⑥

中选择一个进程，让它占用处理器。

40．把存储介质上连续信息所组成的一个区域称为

⑦

；为管理方便，经常将存储介质的

⑧

称为物理单位。

41．为破坏进程循环等待条件，从而防止死锁，通常采用的方法是把系统中所有资源类进行

⑨

，当任何一个进程申请两个以上资源时，总是要求按对应资源号

⑩

次序申请这些资源。

七、综合题（共2小题，20分）

42．说明进程和程序的区别和联系。（8分）

43．在单道批处理系统中，有四个作业进入系统，进入时间及所需计算时间如下表所示。现忽略作业调度所花时间。当第一个作业进入系统后就可开始调度。（12分）

（1）将分别采用“先来先服务”和“短作业优先”调度算法时，各个作业的开始时间，完成时间，周转时间分别是多少？

（2）采用“先来先服务”调度算法时，平均周转时间为______。采用“短作业优先”调度算法时，平均周转时间为______。