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

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

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

□计算机组成原理 □计算机网络 □计算机操作系统

试卷一

：数据结构（必做

）

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

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的(

)和运算等的学科

。

A.

结构

B.

关系

C.

运算

D.

算法

2.

若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用

(

)

存储方式最节省时间。

A. 顺序表

B. 单链表

C. 双链表

D. 单循环链表

3. 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为( )

。

A.

front=front->next;

B.

s->next=rear;rear=s;

C.

rear->next=s;rear=s;

D.

s->next=front;front=s;

4. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是( )

。

A.

a在b的右方

B.

a在b的左方

C.

a是b的祖先

D.

a是b的子孙

5. 假定在一棵二叉树中，度为2的结点数为15，度为1的结点数为30，则叶子结点数为( )

个

。

A.

15

B.

16

C.

17

D.

47

6. 在一个包含n个顶点的有向图中，如果所有顶点的出度之和为s，则所有顶点的入度之和为( )。

A. n B. s

C. 2n D. s-1

7. 下列关于图遍历的说法不正确的是( )

。

A.

连通图的深度优先搜索是一个递归过程

B.

图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C.

非连通图不能用深度优先搜索法

D.

图的遍历要求每一顶点仅被访问一次

8. 对一棵二叉排序树按( )遍历，可得到结点值从小到大的排列序列

。

A.

先序

B.

中序

C.

后序

D.

层次

9. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是( )

。

A.

顺序查找

B.

折半查找

C.

哈希查找

D.

分块查找

10. 若需要在O(

nlog

2

n

)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是(

)

。

A.

快速排序

B.

堆排序

C.

归并排序

D.

直接插入排序

二、填空题(每个空2分，共20分)

12.设单链表的结点结构为(data ,next)。已知指针p指向单链表中的结点，q指向新

结点，欲将q插入到p结点之后，则需要执行的语句：

②

。

13.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为：

③

。

14. 采用二叉链表作为二叉树的存储结构，则具有n

个结点的二叉树有

④

个空链域。

15. 在赫夫曼树中，结点的度数可能取值是：

⑤

。

16. 若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的

⑥

。

17. 判定一个有向图是否存在回路，可以利用

⑦

。

18. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时，

⑧

次比较后查找成功

。

19. 具有相同函数值的关键字对哈希函数来说称为

⑨

。

20. 直接插入排序在关键字正序有序的情况下，其排序时间复杂度为

⑩

。

三、解答题(共30分)

21.

已知栈的基本操作函数

：

int InitStack(SqStack *S); //

构造空栈

int StackEmpty(SqStack *S);//

判断栈空

int Push(SqStack *S,ElemType e);//入栈

int Pop(SqStack *S,ElemType *e);//出栈

函数conversion实现十进制数转换为八进制数，请将函数补充完整。

void conversion(){

InitStack(S);

scanf(

“

%d

”

,&N);

while(N){

（1）

;

N=N/8;

}

while(

（2）

){

Pop(S,&e);

printf(

“

%d

”

,e);

}

}//conversion

22.根据字母集合{e,m,o,r,y}中每个字母在电文中出现的频度所构建的赫夫曼编码为：

e: 00

m: 01

o: 11

r: 101

y: 100

回答下列问题：

(1)画出对应的赫夫曼树。(约定构造过程中，左边分支编码为

’

0

’

,右边分支编码为

’

1

’

。

(2)当接收到的电文为01000111101100时，根据赫夫曼编码给出对应的译文。

23.已知无向图G包含6个顶点，如下图所示：

V1V3V4V6V2V5465281093712

回答如下问题：

(1) 画出该无向图G的邻接表存储表示。假定每个顶点的单链表中的结点是按顶点序号从小到大(V1序号小于V2，依次类推)的次序链接。

(2) 对于如上的邻接表存储表示，分别写出从顶点V1出发按深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。

深度优先搜索序列：

广度优先搜索序列：

(3) 对于无向图G，给出用Prim算法(从顶点V1开始)构造的最小生成树。

24.

对关键字序列(

22,41,53,46,30,13,01,67

)，设哈希表的地址空间为[

0…10

]，选取哈希函数

H(k)=(k)MOD 11，

用二次探测再散列处理冲突，请回答下列问题：

(

1

) 画出构建出的哈希表。

(

2

) 计算等概率情况下查找成功时的平均查找长度

ASL

。

25.

对关键字序列(14,13,3,16,29,7,21,9,33,10,20)，进行快速排序，以待排序列的最后一个关键字为枢轴，调用分割函数Partition进行划分并使得枢轴就位，请分别写出前3次调用分割函数Partition后的关键字序列。(枢轴请用圆圈圈出)

第一次：

第二次：

第三次：

四、算法设计(共20分)

26．已知线性表中的元素以值递增有序排列，并以单链表作为存储结构。试写一个高效的算法，删除表中所有值大于mink且小于maxk的元素，同时释放被删除结点的空间。(mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同。)

链表定义如下：

typedef struct LNode{

int data;

struct LNode *next;

}LNode, *LinkList;

算法原型为：int Delete_q(LinkList &L, int mink, int maxk);

27.以二叉链表作为存储结构，写一算法：利用二叉树的后序遍历求二叉树的深度。

二叉树结点定义如下：

T

ypedef struct BiTNode{

TElemType data;

S

truct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;

算法原型为： int Depth(BiTree T);

试卷二

：计算机组成原理(选做)

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

28．

浮点数加减法中的对阶是指

（ ）

。

A. 将较小的一个阶码调整到与较大的一个阶码相同

B. 将较大的一个阶码调整到与较小的一个阶码相同

C. 将被加数的阶码调整到与加数的阶码相同

D. 将加数的阶码调整到与被加数的阶码相同

29．

EPROM是指

（ ）

。

A.

读写存储器

B.

电擦除可编程只读存储器

C.

闪速存储器

D.

紫外线擦除可编程只读存储器

30．

设机器字长为32位，存储容量为16MB，若按双字编址，它的寻址范围是

（ ）

。

A. 8MB B. 2M C. 4M D. 2MB

31．

挂接在总线上的多个部件

（ ）

。

A.

只能分时向总线发送数据，并只能分时从总线接收数据

B.

只能分时向总线发送数据，但可同时从总线接收数据

C.

可同时向总线发送数据，并同时从总线接收数据

D.

可同时向总线发送数据，但只能分时从总线接收数据

32．

指令周期是指

（ ）

。

A. CPU从主存取出一条指令的时间

B. CPU执行一条指令的时间

C. CPU从主存取出一条指令加上CPU执行这条指令的时间

D.

时钟周期时间

33．以下四种类型指令中，执行时间最长的是（ ）。

A.

RR型

B.

RS型

C.

SS型

D.

程序控制

34．在原码加减交替除法中，当余数为负时的算法为（ ）。

A.

商1，余数左移一位，加除数

B.

商1，余数左移一位，减除数

C.

商0，余数左移一位，加除数

D.

商0，余数左移一位，减除数

35．零地址运算指令在指令格式中不给出操作数地址，因此它的操作数来自（ ）。

A.

立即数和栈顶

B.

栈顶和次栈顶

C.

暂存器和栈顶

D.

寄存器和内存单元

36．补码10110110代表的是十进制负数（ ）。

A.

-74

B.

-54

C.

-68

D.

-48

37．在机器数（ ）

中

，

零的表现形式是唯一的

。

A.

原码

B.

补码

C.

反码

D.

阶码

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

38．

设某计算机的CPU主频为8MHz，每个机器周期平均含2个时钟周期，每条指令的指令周期平均有2.5个机器周期，该机的平均指令执行速度为

MIPS。若CPU主频不变，但每个机器周期平均含4个时钟周期，每条指令的指令周期平均有5个机器周期，则该机的平均指令执行速度为

MIPS。由此得到的结论为：

。

39．

CPU中的

寄存器用于存放当前欲执行指令的地址，

寄存器用来存放当前正在执行的指令。

40．

中断处理过程可分为中断请求、

、中断响应、

和中断返回5个阶段。

41．

基本的指令格式由两部分组成，分别是

和地址码。

42．

静态随机读写存储器SRAM靠

存储信息。动态随机读写存储器DRAM靠

存储信息。

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

43．

一个组相连映射的Cache由64块组成，每组内包含4块。主存包含4096块，每块由128字组成，访存地址为字地址。试问主存和高速存储器的地址各为几位？画出主存地址格式。

44．

画出主机框图，以存数指令“STA M”（M均为主存地址）为例，在图中按序标出完成该指令（包括取指令阶段）的信息流程（如→①）。假设主存容量为256M*32位，在指令字长、存储字长、机器字长相等的条件下，指出图中各寄存器的位数。

试卷三

：计算机网络(选做)

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

28．关于网络分层结构，下列说法正确的是（ ）。

A．某一层可以使用上一层提供的服务而不需要知道服务是如何实现的

B．层次划分越多，灵活性越好，协议效率也越高

C．由于结构彼此分离，实现和维护更加困难

D．当一层发生变化时，只要接口关系不变，以上或以下的各层均不受影响

29．如果要将两台计算机通过双绞线直接连接，正确的线序是（ ）。

A．1--1、2--2、3--3、4--4、5--5、6--6、7--7、8--8

B．1--2、2--1、3--6、4--4、5--5、6--3、7--7、8--8

C．1--3、2--6、3--1、4--4、5--5、6--2、7--7、8--8

D．两台计算机不能通过双绞线直接连接

30．要在带宽为4kHz的信道上用2秒钟发送80kbit的数据块，按照香农定理，信道的信噪比最小应为多少（ ）。

A．1023 B．200 C．1005 D．600

31．在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200000km/s。若最小数据帧长度减少1000bit，则最远的两个站点之间的距离至少需要（ ）。

A．增加100m B．增加200m

C．减少100m D．减少200m

32．为所给IP地址范围（170.20.64.1到170.20.95.254）确定合适的子网掩码（ ）。

A．255.255.0.0 B．255.255.224.0

C．255.255.128.0 D．255.255.255.128

33．如果ARP表中没有目的IP地址的MAC地址表项，源站如何找到目的MAC地址（ ）。

A．向整个子网发送一个广播请求 B．向全网发送一个广播请求

C．查找路由表 D．以上说法都不对

34．下列关于交换机的叙述中，正确的是（ ）。

A．通过交换机互连的一组工作站构成一个冲突域

B．以太网交换机本质上是一种多端口网桥

C．交换机每个端口所连网络构成一个独立的广播域

D．以太网交换机可实现不同网段的互连

35．位于不同子网中的主机之间进行相互通信，下面说法中正确的是（ ）。

A．源站点可以直接进行ARP广播得到目的站的硬件地址

B．路由器在转发IP数据报时，重新封装目的IP地址和目的IP硬件地址

C．路由器在转发IP数据报时，重新封装源硬件地址和目的硬件地址

D．路由器在转发IP数据报时，重新封装源IP地址和目的IP地址

36．主机甲与乙之间建立一个TCP连接，双方持续有数据传输，且无差错与丢失。若甲收到一个来自于乙的TCP段，该段的序号是1912、确认序号是2058、有效载荷为150字节，则甲立即发送给乙的TCP段的序号和确认分别是（ ）。

A．2058、2061 B．2058、2062 C．2059、2061 D．2059、2062

37．电子邮件应用程序利用POP3协议（ ）。

A．创建邮件 B．加密邮件

C．发送邮件 D．接收邮件

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

38．在计算机网络中数据的交换按交换方式来分类，可以分为电路交换、报文交换和____三种。

39．网络协议的三要素是：语法、____和时序。

40．计算机网络按作用范围进行分类，主要可分为：____、城域网和广域网。

41．从通信的双方信息交互的方式来看，通信可以划分为单向通信、双向交替通信和____。

42．通信系统中，称调制前的电信号为____信号，调制后的信号为调制信号。

43．局域网拓扑结构包括____、环形和总线网。

44．在计算机网络和数据通信中广泛使用的一种检错码为____。

45．802.3以太网最小传送的帧长度为____个字节。

46．一个IPV6地址占____位。

47．WWW采用的是____的工作模式。

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

48．简述CSMA/CD协议的工作过程？

49．简述采用四次握手机制释放TCP连接的四个步骤？

八、综合应用题：（每小题10分，共20分）

50．一个UDP用户数据报的首部的十六进制表示是：E76200350033F10B。请回答下列问题。

（1）源端口号是什么？

（2）目的端口号是什么？

（3）这个用户数据报的总长度是多少？

（4）数据长度是多少？

（5）服务器程序是什么？

51．如下图所示，已知一个局域网NET1的网络地址为211.60.160.16/28，另一个局域网NET2的网络地址为192.168.10.0/24。路由器R1有3个接口：接口E0（IP地址:211.60.160.18）连接到NET1 ；接口L1（IP地址:202.99.10.1）连接到R2的接口L0上；接口L0（IP地址:222.223.100.17）连接到Internet。路由器R2具有NAPT功能，有两个接口：接口E0（IP地址:192.168.10.1）连接到NET2上；接口L0（IP地址:202.99.10.2）连接到路由器R1的接口L1。DNS服务器和Web服务器都连接到局域网NET1上，DNS服务器使用该网段的最后一个可用的IP地址，而Web服务器使用第一个可用的IP地址。DNS服务器为图中的所有节点做域名解析。主机1和主机2连接到局域网NET2中，IP地址分别为192.168.10.2和192.168.10.3。请回答下列问题。

（1）为了使主机1能够以域名访问Web服务器，现在为主机1配置网络参数，请给出这四个网络参数值：IP地址、子网掩码、默认网关IP地址、DNS服务器地址？

（2）假设主机2使用TCP端口号52328访问图中的Web服务器。当Web服务器收到主机2发给它的TCP报文时，所看到的目的端口号、IP数据报中的源IP地址和目的IP地址分别是多少？

（3）假设路由器R2的路由表中有一条到达Internet的默认路由，请给出这条默认路由表项的具体内容（包括目的地址、掩码、下一跳地址）。

试卷四

：计算机操作系统(选做)

五

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

28.

现代操作系统的基本特征是（

）、资源共享

、虚拟性

和

进程

的异步性。

A. 实现分时与实时处理

B.多道程序设计　C.程序的并发执行

D.中断处理

29. 5

个进程共享同一种临界资源，且每个进程需要7个这样的资源就可以运行完毕，系统最少需要

（ ）

个这种资源才不会产生死锁。

A．

28

B．

29

C．

31

D．

35

30.

在一般操作系统中必不可少的调度是

（ ）

。

A．高级调度

B．中级调度

C．作业调度

D．进程调度

31. 下面所示步骤中，（ ）不是创建进程所必需的。

A.

建立一个进程控制块

B.

为进程分配内存

C

.

将进程控制块插入就绪队列 D

.

为进程分配CPU

32.

有

6

个进程共享同一程序段,而每次最多允许

3

个进程进入该程序段,若用P、V操作作同步机制,则记录型信号量S的取值范围为(

)。

A．[

3

,-

3

]

B．[3,-

6

]

C．[

1

,-

5

]

D．[

2

,-

4

]

33.

在可变分区分配方案中，某一作业完成后，系统收回其主存空间并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1的情况是（ ）。

A．无上邻空闲区也无下邻空闲区 B．有上邻空闲区也有下邻空闲区

C．有下邻空闲区但无上邻空闲区 D．有上邻空闲区但无下邻空闲区

34.

段页式管理每取一次数据，要访问（

）次内存。

A.1 B.2 C.3 D.4

35.采用二级目录结构的系统中，文件的目录由（ ）组成。

A.

主文件目录和用户文件目录

B.

用户文件目录和当前目录

C

.

主文件目录和当前目录 D

.

根目录和子目录

36.

下面4个选项中不属于SPOOLing系统特点的是（ ）。

A．提高了内存的利用率 B. 提高了I/O操作的速度

C．将独占设备改造为共享设备 D. 实现了虚拟设备功能

37. 目前，常用的PCB组织方式有两种：（ ）

A. 链接方式和索引方式 B.链接方式和顺序方式

C. 顺序方式和索引方式 D.直接方式和顺序方式

六

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

38.大多数计算机系统将CPU执行状态分为（ ）和（ ）。

39.在操作系统中，（ ）是资源分配、调度运行和管理的最小单位。

40.一个多道批处理系统中只有P1和P2两道作业，P2比P1晚10ms到达，它们的计算和I/O操作顺序如下：

P1：计算60ms；I/O操作80ms；计算10ms

P2：计算120ms；I/O操作40ms；计算20ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是（ ）。

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

42.产生死锁的4个必要条件是（ ）、请求和保持条件、（ ）、循环等待条件。

43.P、V操作是对（ ）进行操作。

44.根据文件的逻辑结构，文件分为（ ）文件和记录式文件。

七

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

45.假设某程序的页面访问序列为:1、2、3、4、5、2、3、1、2、3、4、5、1、2、3、4，若分配给该程序的内存块数是3块，采用FIFO与LRU方式时缺页率分别是多少？若分配给该程序的内存块是4时，采用FIFO方式的缺页率又是多少？与前面内存块数是3块时相比较出现了什么现象？

46.已知一个求值公式(3A+B

2

)/(2A+B)，若A、B已赋值，请画出该公式求值过程的前趋图并用P、V操作实现这些节点间的同步。