北京邮电大学2016年计算机学科基础综合考试真题803

北京邮电大学

2016年硕士研究生入学考试试题 考试科目：计算机学科基础综合

请考生注意：①所有答案（包括选择题和填空题）一律写

在答题纸上，否则不计成绩。

②不允许考生使用计算器。

一、单项选择题（每小题2分，共80分） 1.以下与数据的存储结构无关的术语是

A.循环队列

B.线索树

C.栈

D.数组

2.若双栈共享空间S[0.n-1]，初始时topl=-1、top2=n，则判栈满为真的条件是

A.topl==top2

B.topl-top2=1

C.topl+top2=n

D.top2-topl=1

3.若用带头结点的单循环链表表示非空队列，队列只设一个指针Q，则插入新元素结点P的操作语句序列是

A.P->next=Q->next；Q->next=P；Q=P B.Q->next=P；P>next=Q->next；Q=P C.P->next=Q->next->next；Q=P D.p->next=Q->next；Q=P 4.模式串\"abaabcac”的 nextval数组值是

A.01122312

B.01021302

C.00011201

D.01011201

5.数组A[0..7][0..9]中，每个元素占用3个存储单元，起始存储地址是1000，则数组元素A[5][3]的存储地址是

A.1126

B.1141

C.1156

D.1159

6.在一棵具有20个关键字的3阶B树中，含关键字的结点个数至少是 A.10

B.11

C.12

D.13

7.关键路径是AOE网络中

1 / 9

考试科目：计算机学科基础综合考试803

A.从源点到汇点的最长路径 C.从源点到汇点的最短路径

B.最长回路 D.最短回路

8.具有n个顶点的强连通图，边数最少是

A.2n

B.n+l

C.n

D.n-1

9.下述顺序存储结构排序算法中，关键字比较次数与元素初始排列次序无关的是 A.快速排序

B.堆排序

C.直接插入排序

D.简单选择排序

10.若一组待排记录的关键字为（46，79，38，40，84），利用堆排序建立的初始堆为

A.（38，40，46，79，84） C.（84，79，38，46，40）

B.（84，79，46，40，38） D.（38，40，84，79，46）

11.在关键字随机分布的情况下，用二又排序树方法进行查找，下列方法中与其平均查找长度数量级相当的是 A.顺序查找

B.折半查找

C.分块查找

D.均不正确

12.冯诺依曼计算机的特点是

I.采用二进制

Ⅱ.存储程序 Ⅳ.数据流驱动方式

Ⅲ.控制流驱动方式 A.仅I、Ⅱ

B.仅I、Ⅱ、Ⅲ

D.I、Ⅱ、Ⅲ、Ⅳ

C.仅I、Ⅱ、Ⅳ

13.某8位计算机的存储器按字节编址，如果某字节类型变量对应的存储器单元的值为10000010，那么我们可得出如下结论

A.无法得出结论 C.值为130

B.这是一个补码

D.这是一个负数

14.下列关于IEEE7浮点数格式的叙述中，正确的是

A.尾数和阶码均用原码表示 B.尾数用补码表示、阶码用原码表示

2 / 9

考试科目：计算机学科基础综合考试803

C.只能表示规格化数

D.可以表示规格化数和非规格化数

15.一个八体低位交叉存储器，每个存储体的容量为256M*位，若每个体的存储周期为80ns，那么该存储器能提供的最大带宽是

A.426.67MB/s

B.800MB/S

C.213.33MB/S

D.400MB/S

16.一个八路组相联 Cache共有块，主存共有8192块，每块个字节，那么主存地址的标记x、组号y、和z块内地址分别是

A.x=4，y=3，z=6 C.x=10，y=3，z=6

B.x=1，y=6，z=6 D.x=7，y=6，z=6

17.在某计算机系统中，已知A为累加器，SP为堆栈指示器，Me为Sp指示的栈顶单元，如果进栈操作的顺序是（A）→Ms9，（SP）H1→5P，那么出栈操作的顺序应为

A.（Msp）→A，（SP）-1→SP C.（SP）-1→SP，（Msp）→A

B.（Msp）→A，（SP）+1→sP D.（SP）+1-SP，（Msp）→A

18.在一个具有四级流水线的浮点加法器中，假设四个阶段的时间分别是T1=60ms

、T2=50ns、T3=90ns、T4=80ns，则加法器流水线的时钟周期至少为X；如果采用同样的逻辑电路，但不是流水线方式，则浮点加法所需的时间为Y。那么X和Y是

A.X=70ns，Y=280ns C.X=90ns，Y=280ns

B.X=50ns，Y=90ns D.X=50ms，Y-280ns

19.下列关于PCI总线特性的表述中，不正确的是

A.系统中可以有多条PCI总线 B.能实现即插即用

C.PCI总线采用隐含的集中式总线仲裁方式 D.PCI总线是一个与处理器相关的高速外围总线

20.已知某支持突发（猝发）传输模式的同步总线的时钟频率为200MHz，宽度为32位，地址和数据线复用，每个时钟周期传输一个地址或数据，如果一次“存储器读”总线事物传输用的时间为25ns，则本次传输的有效数据位数是

3 / 9

考试科目：计算机学科基础综合考试803

A.32位 B.128位 C.160位 D.256位

21.下列说法中，不正确的是

A.统一编制方式下CPU需要设置专门的输入输出指令访问端口 B.数据端口和状态端口都称为I/O端口

C.输入端口和输出端口可以使用同一个I/O端口地址 D.输入端口只能输入数据或读入状态 22.下列关于DMA的叙述中，正确的是

A.DMA请求和中断请求同时发生时，中断请求先得到响应

B.在DMA读操作中，数据经过的路径是内存→数据总线→CPU→数据总线→外设

C.DMA的周期窃取需要等当前指令周期结束后才能启动 D.DMA方式下数据传送由硬件完成 23.目前，个人电脑中使用的主流桌面操作系统是

A.Windows，Mac OS，Linux B.Windows，Linux，Android C.Windows，Linux，ios D.Windows，Unix，ios

24.进程从运行状态转为就绪状态的条件是

A.进程被调度程序选中 C.等待某一个事件

B.时间片用完 D.等待的事件发生

25.下述关于进程、线程的陈述中，正确的是

1.进程控制块PCB记录了进程运行状态、使用资源等信息 Ⅱ.进程I/O操作结束后，进程执行状态从等待阻塞态变为运行态 Ⅲ.单处理器系统中，基于共享内存的进程间通信是在用户模式下实现 IV.在支持多线程的系统中，操作系统以线程为单位分配内存、文件等资源，以

4 / 9

考试科目：计算机学科基础综合考试803

进程为单位进行CPU调度

A.I，Ⅱ，Ⅲ，IV C.I，Ⅲ

B. I，Ⅱ，Ⅲ D. Ⅱ，IV

26.在单处理器系统中，5个进程同时被创建，CPU调度程序采用某种调度策略安排这些进程的并发执行。假设这5个进程的单独占用CPU时的执行时间分别为2.4，6，8，10。当这5个并发进程全部执行完毕后，它们的最小平均等待时间是

A.2

B.6

C.8

D.10

27.在一个采用分页内存管理的系统中，物理内存空间大小为232字节，逻辑地址空间由211个页面组成，页面大小为1024字节，采用页表进行逻辑地址到物理地址的变换。在物理地址中，用于定义页框（帧）号的位数为 A.22

B.10

C.32

D.11

28.在I/O设备管理中，引入缓冲机制的目的是

A.减少了硬盘空间 B.增加了内存空间 C.减少了内存空间

D.改善CPU和/O设备之间速度不匹配

29.在下述死锁问题处理机制中，采用银行家算法的是

A.死锁预防 C.死锁检测

B.死锁避免 D.死锁恢复

30.假设文件系统采用位图管理磁盘自由空间，磁盘自由空间大小为4096磁盘块，每个磁盘块大小为1024字节，位图需要占用的字节数是

A.4096

B.1024

C.512

D.128

31.下述CPU调度算法中，适合硬实时系统的是

A.时间片轮转法 C.最短作业优先

B.先来先服务

D.基于优先级的抢占式调度

32.磁盘调度算法中，先来先服务磁盘调度算法（FCFS）是

5 / 9

考试科目：计算机学科基础综合考试803

A.按照访问请求的次序，即按照访问请求发出的次序依次读写各个磁盘块 B.优先为距离磁头当前所在位置最近磁道（柱面）的访问请求服务 C.按照访问请求，随机读写各个磁盘块 D.基本思想与电梯的原理类似，又称电梯算法 33.UDP协议属于七层参考模型中的

A.会话层

B.传输层

C.数据链路层

D.互联网层

34.在一条带宽为4kHz的信道上发送二进制信号。若该信道的信噪比（S/N）为1023，则可达到的最大传输速率为

A.4k bps

B.8k bps

C.40kbps

D.80k bps

35.若信道有噪音，数据链路层采用下列成帧方法不能正常工作的是

A.字符计数法 C.比特填充法

B.字符填充法 D.物理层编码违例法

36.下列关于链路状态路由选择协议的描述中，错误的是

A.相邻路由器需定期交换路由表 B.采用Flooding技术更新链路状态信息 C.区域内各路由器的拓扑结构数据库一致 D.具有快速收敛的优点

37.一主机的IP地址为172.20.72.24，子网掩码为255.255.192.0，当该主机在子网内发送广播数据报时，IP数据报中的目的地址为

A.172.20.72255 C.172.20..255 38.IPv6地址的长度为

A.32比特

B.比特

C.128比特

D.160比特

B.172.20.255.255 D.172.20.127.255

39.TCP协议中慢启动算法解决的是

A.两军问题

B.半开连接问题

6 / 9

考试科目：计算机学科基础综合考试803

C.拥塞控制问题 D.可靠传输问题

40.用于域名解析的协议是

A.ARP

B.DHCP

C.ICMP

D.DNS

二、综合应用题（共70分）

41.（8分）已知某二叉树的先序、中序和后序遍历如下，其中一部分未标出，试填写空格处的内容，并画出该二叉树。

先序序列：___ ___C D E ___ G A I ___ K 中序序列：C B ___ ___ F H ___ J K I G 后序序列：___ E F D B ___ J I A ___ H

42.（15分）已知某图的邻接矩阵为A，若从顶点i到顶点j有边，则A[i，j]=1，否则A[i，j]=0。试编写一算法求矩阵A的传递包C：使得若从顶点i到顶点j有一条或多条路径，则C[i，j]=1，否则C[i，j]=0。

typedef int adjmatrix[maxvtxnum][maxvtxnum]; void Change（adjmatrix A，adjmatrix C，int n）

43.（11分）某计算机字长16位，主存地址空间大小为KB，按字节编址，采用双字长指令格式，指令各字段定义如题43图，其中OP为固定长度的操作码字段，Rs和Rd分别表示源寄存器和目的寄存器，它们可以是任一通用寄存器R0~R7，其编号分别为0、1、…7，Ms和Md表示寻址方式，定义见题43表所示，A可表示原操作数地址、目的操作数地址的偏移量或立即数，其中立即数用补码表示。

15 操作码 目的操作数 源操作数 0 OP Md Rd A

题43图 指令格式

Ms Rs 7 / 9

考试科目：计算机学科基础综合考试803

题43表

Ms/Md 寻址方式 000 001 010 011 100 立即寻址 寄存器寻址 寄存器间接寻址 变址寻址 寄存器相对寻址 助记符 A Rn [Rn] [Rn]+ [RntA] 含义 操作数=A 操作数=（Rn） 操作数=（（Rn）） 操作数=（（Rn）），（Rn）+1→Rn 操作数=（（Rn+A）） 注：[X]表示存储器地址X的内容或寄存器X的内容请回答下列问题：

（1）该计算机的指令系统最多可定义多少条指令？

（2）已知ADD、AND和SAR指令操作码分别为0001、0010和0011，则下列指令的

机器码格式多少？

①ADD [R3]，R2； （（R3））+（R2）→（R3） ②AND R5，[R6+1024]；（R5）^（（R6）+1024）→R5 ③SAR R7，2； （R7）算术右移2位→R7

（3）如果寄存器R7的内容为8004H，那么执行指令“SARR7，2”后，R7内容为多少？（用十六进制表示），十进制值又为多少？

44.（12分）某计算机的处理器主频为500MHz，有鼠标、软盘和硬盘三种外设，现采用程序查询方式进行I/O操作，假设一次查询操作（包括转移到查询例行程序、访问设备、返回用户程序）共需要400个时钟周期，为了计算方便，我们进一步假设查询次数足够多，不会有数据丢失，并且设备一直处于繁忙状态。

请回答下列问题，要求给出计算过程。

（1）如果每秒钟鼠标必须查询50次才能保证捕捉到用户所做的移动，问查询鼠标输入的开销（即处理器用于鼠标输入的时间占整个处理器时间的百分比）是多少？

（2）如果软盘的数据传输速率是0.1MB/秒，并且查询一次软盘可传输2个字节，要求传输过程中没有数据丢失，问查询软盘的开销是多少？

8 / 9

考试科目：计算机学科基础综合考试803

（3）如果硬盘的数据传输速率是8MB/秒，并且查询一次硬盘可传输16个字节，要求传输过程中没有数据丢失，问查询硬盘的开销是多少？

（4）从上述计算结果可以看出，外设的传输速率越高，处理器用于输入输出的开销就越大。针对上述三种情况有什么改进措施？

45.（7分）在请求页式内存管理系统中，考虑下面的进程页面引用串，

1，2，3，4，5，3，4，1，2，1，2，3，7，6，2

假定：分配给该进程的可用页框（帧）数目为4，所有页框（帧）的内容初始为空，采用FIFO页面替换算法。

计算进程页面访问过程中发生的缺页次数和缺页率，要求给出计算过程。 46.（8分）一组生产者进程和消费者进程共享一个有限缓冲区，缓冲区容量为N

（N>2，为偶数），最多可容纳N个数据项。生产者进程每次访问缓冲区时，一次性地向缓冲区中写入2个数据项，消费者进程每次从缓冲区内提取1个数据项。任何时刻只允许1个生产者或1个消费者访问缓冲区，初始时缓冲区为空。

定义信号量并用wait、signal操作（即P、V操作）实现生产者、消费者进程对缓冲区的并发访问。要求：

（1）给出信号量的定义和初值，说明信号量的含义 （2）描述生产者、消费者的执行步骤

47.（9分）两台计算机的数据链路层采用滑动窗口机制，用kbps的卫星信道传输长度为1024比特的数据帧，信道的单向传播延迟为256ms。应答帧和数据帧帧头的开销忽略不计。回答下列问题。

（1）计算使用停等协议时信道利用率；

（2）计算使用发送窗口为7时Go-Back-N协议的信道利用率；

（3）为使信道利用率达最大，使用Go-Back-N协议时帧头中序号字段至少为多少比特？

（4）为避免无谓的重传，滑动窗口协议的超时重发计时器至少为多少？

9 / 9