2018年408计算机学科专业基础真题

一、单项选择题（第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求）

1、若栈S1中保存整数，栈S2中保存运算符，函数F()依次执行下述各步操作：

（1）从S1中依次弹出两个操作数a和b；

（2）从S2中弹出一个运算符op；

（3）执行相应的运算bopa；

（4）将运算结果压入S1中。

假定S1中的操作数依次是5，8，3，2（2在栈顶），S2中的运算符依次是*，-，+（+在栈顶）。调用3次F（）后，S1栈顶保存的值是（  ）。

A.-15

B.15

C.-20

D.20

2、现有队列Q与栈S，初始时Q中的元素依次是1，2，3，4，5，6(1在队头)，S为空。若仅允许下列3种操作：① 出队并输出出队元素；② 出队并将出队元素入栈；③ 出栈并输出出栈元素，则不能得到的输出序列是（  ）。

A.1，2，5，6，4，3

B.2，3，4，5，6，1

C.3，4，5，6，1，2

D.6，5，4，3，2，1

3、设有一个12×12的对称矩阵M，将其上三角部分的元素mi,j(1<=i<=j<=12)按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是（  ）。

A.50

B.51

C.55

D.66

4、设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是（  ）。

A.2k-1

B.2k

C.k2

D.2k-1

5、已知字符集{a，b，c，d，e，f}，若各字符出现的次数分别为6，3，8，2，10，4，则对应字符集中各字符的哈夫曼编码可能是（  ）。

A.00，1011，01，1010，11，100

B.00，100，110，000，0010，01

C.10，1011，11，0011，00，010

D.0011，10，11，0010，01，000

6、已知二叉排序树如下图所示，元素之间应满足的大小关系是（  ）。

A.x1<x2<x5

B.x1<x4<x5

C.x3<x5<x4

D.x4<x3<x5

7、下列选项中，不是如下有向图的拓扑序列的是（  ）。

A.1，5，2，3，6，4

B.5，1，2，6，3，4

C.5，1，2，3，6，4

D.5，2，1，6，3，4

8、高度为5的3阶B树含有的关键字个数至少是（  ）。

A.15

B.31

C.62

D.242

9、现有长度为7、初始为空的散列表HT，散列函数H(k)=k%7，用线性探测再散列法解决冲突。将关键字22，43，15依次插入到HT后，查找成功的平均查找长度是（  ）。

A.1、5

B.1、6

C.2

D.3

10、对初始数据序列（8，3，9，11，2，1，4，7，5，10，6）进行希尔排序。若第一趟排序结果为（1，3，7，5，2，6，4，9，11，10，8），第二趟排序结果为（1，2，6，4，3，7，5，8，11，10，9），则两趟排序采用的增量（间隔）依次是（  ）。

A.3，1

B.3，2

C.5，2

D.5，3

11、在将数据序列（6，1，5，9，8，4，7）建成大根堆时，正确的序列变化过程是（  ）。

A.6，1，7，9，8，4，5→6，9，7，1，8，4，5→9，6，7，1，8，4，5→9，8，7，1，6，4，5

B.6，9，5，1，8，4，7→6，9，7，1，8，4，5→9，6，7，1，8，4，5→9，8，7，1，6，4，5

C.6，9，5，1，8，4，7→9，6，5，1，8，4，7→9，6，7，1，8，4，5→9，8，7，1，6，4，5

D.6，1，7，9，8，4，5→7，1，6，9，8，4，5→7，9，6，1，8，4，5→9，7，6，1，8，4，5→9，8，6，1，7，4，5

12、冯·诺依曼结构计算机中数据采用二进制编码表示，其主要原因是（  ）。

Ⅰ.二进制的运算规则简单

Ⅱ.制造两个稳态的物理器件较容易

Ⅲ.便于用逻辑门电路实现算术运算

A.仅Ⅰ、Ⅱ

B.仅Ⅰ、Ⅲ

C.仅Ⅱ、Ⅲ

D.Ⅰ、Ⅱ和Ⅲ

13、假定带符号整数采用补码表示，若int型变量x和y的机器数分别是FFFF FFDFH和0000 0041H，则x、y的值以及x-y的机器数分别是（  ）。

A.x=-65，y=41，x-y的机器数溢出

B.x=-33，y=65，x-y的机器数为FFFFFF9DH

C.x=-33，y=65，x-y的机器数为FFFFFF9EH

D.x=-65，y=41，x-y的机器数为FFFFFF96H

14、IEEE754单精度浮点格式表示的数中，最小的规格化正数是（  ）。

A.1.0X2-126

B.1.0X2-127

C.1.0X2-128

D.1.0X2-149

15、某32位计算机按字节编址，采用小端（Little Endian）方式。若语令“int i=0”对应指令的机器代码为“C745FC00000000”，则语句“int i=-64”对应指令的机器代码是（  ）。

A.C7 45 FC C0 FF FF FF

B.C7 45 FC 0C FF FF FF

C.C7 45 FC FF FF FF C0

D.C7 45 FC FF FF FF 0C

16、整数x的机器数为11011000，分别对x进行逻辑右移1位和算术右移1位操作，得到的机器数各是（  ）。

A.1110 1100、1110 1100

B.0110 1100、1110 1100

C.1110 1100、0110 1100

D.0110 1100、0110 1100

17、假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为保证其地址引脚数最少，并尽量减少刷新开销，则r、c的取值分别是（  ）。

A.2048、1

B.64、32

C.32、64

D.1、2048

18、按字节编址的计算机中，某double型数组A的首地址为2000H，使用变址寻址和循环结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是（  ）。

A.25

B.32

C.64

D.100

19、减法指令“sub R1,R2,R3”的功能为“(R1)-(R2)→R3"，该指令执行后将生成进位/借位标志CF和溢出标志OF。若(R1)=FFFFFFFFH，(R2)=FFFFFFF0H，则该减法指令执行后，CF与OF分别为（  ）。

A.CF=0，OF=0

B.CF=1，OF=0

C.CF=0，0F=1

D.CF=1，OF=1

20、若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A~E实现，各功能部件所需时间分别为80ps、50ps、50ps、70ps和50ps，采用流水线方式执行指令，流水段寄存器延时为20ps，则CPU时钟周期至少为（  ）。

A.60ps

B.70ps

C.80ps

D.100ps

21、下列选项中，可提高同步总线数据传输率的是（  ）。

Ⅰ.增加总线宽度

Ⅱ.提高总线工作频率

Ⅲ.支持突发传输

Ⅳ.采用地址/数据线复用

A.仅Ⅰ、Ⅱ

B.仅Ⅰ、Ⅱ、Ⅲ

C.仅Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ和Ⅳ

22、下列关于外部I/O中断的叙述中，正确的是（  ）。

A.中断控制器按所接收中断请求的先后次序进行中断优先级排队

B.CPU响应中断时，通过执行中断隐指令完成通用寄存器的保护

C.CPU只有在处于中断允许状态时，才能响应外部设备的中断请求

D.有中断请求时，CPU立即暂停当前指令执行，转去执行中断服务程序

23、下列关于多任务操作系统的叙述中，正确的是（  ）。

Ⅰ、具有并发和并行的特点

Ⅱ、需要实现对共享资源的保护

Ⅲ、需要运行在多CPU的硬件平台上

A.仅Ⅰ

B.仅Ⅱ

C.仅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

24、某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μs。在T时刻就绪队列中有3个进程P1、P2和P3，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。

若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，则系统的平均周转时间为（  ）。

A.54μs

B.73μs

C.74μs

D.75μs

25、属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下。

在所有可能的指令执行序列中，使x的值为2的序列个数是（  ）。

A.1

B.2

C.3

D.4

26、假设系统中有4个同类资源，进程P1、P2和P3需要的资源数分别为4、3和1，P1、P2和P3已申请到的资源数分别为2、1和0，则执行安全性检测算法的结果是（  ）。

A.不存在安全序列，系统处于不安全状态

B.存在多个安全序列，系统处于安全状态

C.存在唯一安全序列P3、P1、P2，系统处于安全状态

D.存在唯一安全序列P3、P2、P1，系统处于安全状态

27、下列选项中，可能导致当前进程P阻塞的事件是（  ）。

Ⅰ、进程P申请临界资源

Ⅱ、进程P从磁盘读取数据

Ⅲ、系统将CPU分配给高优先权的进程

A.仅Ⅰ

B.仅Ⅱ

C.仅Ⅰ、Ⅱ

D.Ⅰ、Ⅱ、Ⅲ

28、若x是管程内的条件变量，则当进程执行x、wait()时所做的工作是（  ）。

A.实现对变量x的互斥访问

B.唤醒一个在x上阻塞的进程

C.根据x的值判断该进程是否进入阻塞状态

D.阻塞该进程，并将之插入x的阻塞队列中

29、当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是（  ）。

Ⅰ、内核中时钟变量的值

Ⅱ、当前进程占用CPU的值

Ⅲ、当前进程在时间片内剩余执行时间

A.仅Ⅰ、Ⅱ

B.仅Ⅱ、Ⅲ

C.仅Ⅰ、Ⅲ

D.Ⅰ、Ⅱ、Ⅲ 

30、系统总是访问磁盘的某个磁道而不响应对其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法中，不会导致磁臂粘着的是（  ）。

A.先来先服务（FCFS）

B.最短寻道时间优先（SSTF）

C.扫描算法（SCAN）

D.循环扫描算法（CSCAN）

31、下列优化方法中，可以提高文件访问速度的是（  ）。

Ⅰ、提前读

Ⅱ、为文件分配连续的簇

Ⅲ、延迟写

Ⅳ、采用磁盘高速缓存

A.仅Ⅰ、Ⅱ

B.仅Ⅱ、Ⅲ

C.仅Ⅰ、Ⅲ、Ⅳ

D.Ⅰ、Ⅱ、Ⅲ、Ⅳ

32、在下列同步机制中，可以实现让权等待的是（  ）。

A.Peterson方法

B.swap指令

C.信号量方法

D.TestAndSet指令

33、下列TCP/IP应用层协议中，可以使用传输层无连接服务的是（  ）。

A.FTP

B.DNS

C.SMTP

D.HTTP

34、下列选项中，不属于物理层接口规范定义范畴的是（  ）。

A.接口形状

B.引脚功能

C.物理地址

D.信号电平

35、IEEE802、11无线局域网的MAC协议CSMA/CA进行信道预约的方法是（  ）。

A.发送确认帧

B.采用二进制指数退避

C.使用多个MAC地址

D.交换RTS与CTS帧

36、主机甲采用停-等协议向主机乙发送数据，数据传输速率是3kbps，单向传播延时是200ms，忽略确认帧的传输延时。当信道利用率等于40%时，数据帧的长度为（  ）。

A.240比特

B.400比特

C.480比特

D.800比特

37、路由器R通过以太网交换机S1和S2连接两个网络，R的接口、主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址、H2收到的封装P的以太网帧的源MAC地址分别是（  ）。

A.00-a1-b2-c3-d4-62，00-1a-2b-3c-4d-52

B.00-a1-b2-c3-d4-62，00-a1-b2-c3-d4-61

C.00-1a-2b-3c-4d-51，00-1a-2b-3c-4d-52

D.00-1a-2b-3c-4d-51，00-a1-b2-c3-d4-61

38、某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为35.230.32.0/21，35.230.40.0/21，35.230.48.0/21和35.230.56.0/21，将该4条路由聚合后的目的网络地址为（  ）。

A.35.230.0.0/19

B.35.230.0.0/20

C.35.230.32.0/19

D.35.230.32.0/20

39、UDP协议实现分用（demultiplexing）时所依据的头部字段是（  ）。

A.源端口号

B.目的端口号

C.长度

D.校验和

40、无需转换即可由SMTP协议直接传输的内容是（  ）。

A.JPEG图像

B.MPEG视频

C.EXE文件

D.ASCII文本

二、综合应用题（第41~47小题，共70分）

41、（13分）给定一个含n（n>=1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组{-5，3，2，3}中未出现的最小正整数是1；数组{1，2，3}中未出现的最小正整数是4。要求：

（1）给出算法的基本设计思想。

（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

（3）说明你所设计算法的时间复杂度和空间复杂度。 

42、（12分）拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题。

（1）仅从铺设费用角度出发，给出所有可能的最经济的光缆铺设方案（用带权图表示），并计算相应方案的总费用。

（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。

（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？

43、（8分）假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MBps和40MBps，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。

（1）若设备A采用定时查询I/O方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入输出的时间占CPU总时间的百分比至少是多少？

（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？

（3）若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分比最大是多少？

44、（15分）某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。

题44图

根据题44图回答下列问题。

（1）主存物理地址占多少位？

（2）TLB采用什么映射方式？TLB用SRAM还是DRAM实现？

（3）Cache采用什么映射方式？若Cache采用LRU替换算法和回写（Write Back）策略，则Cache每行中除数据（Data）、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？

（4）若CPU给出的虚拟地址为0008C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由，若CPU给出的虚拟地址为0007C260H，则该地址所在主存块映射到的Cache组号是多少？

45、（8分）请根据题44图给出的虚拟存储管理方式，回答下列问题。

（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？

（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。

（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？

46、（7分）某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。

（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可）

（2）文件系统用1M（1M=220）个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件？

（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？

47、（7分）某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。

请回答下列问题。

（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？

（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？