计算机专业（基础综合）模拟试卷2

一、1.单项选择题

单项选择题
1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

0.在顺序表中删除一个元素的时间复杂度为(  )。

A.O(1)
B.O(log n)
C.O(n)
D.O(n2)

1.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是(  )。

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

2.设A是一个已有10个元素的栈，栈中依次是A1，A2，…，A10，栈顶是A10；B是一个已有10个元素的循环队列，队列中元素依次为B1，B2，…，B10，队头元素为B1。A、B均采用顺序结构，现要将栈中元素全部移入队列中，需(  )次基本操作才能使得队列中元素与栈中元素交替排列，即B中排列后的元素为B1，A1，B2，．A2，…，B10，A10。(不必考虑存储空间)

A.100
B.1 000
C.50
D.20

3.设高度为H的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为(  )。

A.2*H
B.2*H-1
C.2*H+1
D.H+1

4.设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有(  )个结点。

A.13
B.12
C.26
D.25

5.已知10个数据元素为(54，28，16，34，73，62，95，60，23，43)，按照依次插入结点的方法生成一棵二叉排序树后，查找值为62的结点所需比较的次数为(  )。

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

6.当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于(  )，则必须分裂成两个结点，当向一棵m阶的B-树做删除操作时，若一个结点中的关键字个数等于(  )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

A.m，m／2-2
B.m-1，m／2-1
C.m+1，m／2
D.m／2，m／2+1

7.下面关于Prim算法和Kruskal算法的时间复杂度正确的是(  )。

A.Prim算法的时间复杂度与网中的边数有关，适合于稀疏图
B.Prim算法的时间复杂度与网中的边数无关，适合于稠密图
C.Kruskal算法的时间复杂度与网中的边数有关，适合于稠密图
D.Kruskal算法的时间复杂度与网中的边数无关，适合于稀疏图

8.数据序列F={2，1，4，9，8，10，6，20)只能是下列排序算法中的(  )的两趟排序后的结果。

A.快速排序
B.冒泡排序
C.选择排序
D.插入排序

9.在含有n个关键字的大顶堆中，关键字最小的记录有可能存储在(  )位置上。

A.n／2
B.n／2-1
C.1
D.n／2+2

10.冯.诺依曼机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是(  )。

A.指令操作码的译码结果
B.指令和数据的寻址方式
C.指令周期的不同阶段
D.指令和数据所在的存储单元

11.IEEE754标准浮点数的尾数采用(  )机器数形式。

A.原码
B.补码
C.移码
D.反码

12.字长16位的补码定点小数的表示范围是(  )。

A.0～1-2^-15
B.-(1-2^-15)～1-2^-15
C.-1～1-2^-15
D.-1～1

13.补码定点小数除法中，被除数和除数应满足(  )。

A.0≤｜被除数｜≤｜除数｜
B.0＜｜被除数｜≤｜除数｜
C.0＜｜除数｜≤｜被除数｜
D.0＜｜被除数｜＜｜除数｜

14.某机器采用四体低位交叉存储器，现分别执行下述操作：(1)读取6个连续地址单元中存放的存储字，重复80次；(2)读取8个连续地址单元中存放的存储字，重复60次。则(1)、(2)所花时间之比为( )。

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

15.下列说法中错误的是( )。

A.虚拟存储器的引入主要是为了解决主存容量的问题
B.虚拟存储器通过页表来实现虚实地址的映射
C.虚拟存储器是一个容量很大的逻辑模型，不是任何实际的存储器
D.虚拟存储器完全由硬件实现

16.在指令格式中，采用扩展操作码设计方案的目的是(  )。

A.缩短指令字长
B.增加指令字长
C.保持指令字长不变的基础上增加指令数量
D.保持指令字长不变的基础上扩大指令寻址空间

17.磁盘的平均存取时间是指平均寻道时间和平均等待时间之和。若磁盘的转速提高一倍，则(  )。

A.平均存取时间减半
B.平均寻道时间减半
C.平均等待时间减半
D.以上都正确

18.下列说法正确的是( )。

A.取指周期一定等于机器周期
B.指令字长等于机器字长的前提下，取指周期等于机器周期
C.指令字长等于存储字长的前提下，取指周期等于机器周期
D.取指周期与机器周期没有必然联系

19.下列说法中正确的是(  )。

A.微处理器的程序称为微程序
B.微指令控制器的执行速度比硬布线控制器快
C.存放微程序的控制存储器可用ROM或EPROM来实现
D.在微程序控制器中，微指令使用机器指令来解释执行

20.同步通信比异步通信数据传输率高的原因是(  )。

A.同步通信不需要应答信号
B.同步通信使用公共时钟进行同步
C.同步通信中，通信双方的速度相近
D.以上都包括

21.CPU在中断周期要完成的任务不包括(  )。

A.保护断点
B.关中断
C.保护现场
D.向量地址送PC

22.实时系统中的进程调度，通常采用(  )算法。

A.先来先服务
B.时间片轮转
C.抢占式的优先数高者优先
D.响应比高者优先

23.进程由就绪态转换为运行态是由(  )引起的。

A.中断事件
B.进程状态转换
C.进程调度
D.为程序创建进程

24.以下(  )不是产生死锁的原因。

A.资源共享
B.并发执行的进程数太多
C.系统资源不足
D.进程推荐顺序非法

25.把程序地址空间中使用的逻辑地址变成内存中物理地址称为(  )。

A.加载
B.物理化
C.重定位
D.逻辑化

26.下面关于虚拟存储器的论述中，正确的是(  )。

A.在段式系统中以段为单位管理用户的逻辑空间，以页为单位管理内存的物理空间；有了虚拟存储器才允许用户使用比内存更大的地址空间
B.为了提高请求分页系统中内存的利用率，允许用户使用不同大小的页面
C.为了能让更多的作业同时运行，通常只装入10％～30％的作业即启动运行
D.最佳适应算法是实现虚拟存储器的常用算法

27.在下列文件的物理结构中，(  )不利于文件长度的动态增长。

A.连续结构
B.链接结构
C.索引结构
D.哈希结构

28.设文件F1的当前引用计数值为1，先建立F1的符号链接(软链接)文件F2，再建 F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是(  )。

A.0、1
B.1、1
C.1、2
D.2、1

29.如果I／O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是(  )。

A.程序查询方式
B.中断方式
C.DMA方式
D.无条件存取方式

30.驱动调度算法中，(  )算法可能会随时改变移动臂的运动方向。

A.电梯调度
B.最短寻找时间优先
C.扫描
D.单向扫描

31.某虚存系统有3页初始为空的页框，若采用先进先出的页面淘汰算法，则在下列的页面需求提出时，会产生(  )次缺页中断?设页面走向为：4 3 2 1 4 3 5 4 3 2 1 5~。

A.7
B.8
C.9
D.10

32.传输线上的位流信号同步，应该属于下列OSI的(  )层处理。

A.物理层
B.数据链路层
C.网络层
D.传输层

33.测得一个以太网数据的波特率是40 Mbps，那么其数据率是(  )。

A.10 Mbps
B.20 Mbps
C.40 Mbps
D.80 Mbps

34.数据链路层采用了后退N帧(GBN)协议，发送方已经发送了编号为0～7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是(  )。

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

35.一个C类地址，采用了255．255．255．240作为子网掩码，那么这个C类地址可以划分为(  )个子网。

A.16
B.32
C.64
D.128

36.下列地址中，不属于多播地址的是(  )。

A.225．189．123．43
B.239．14．68．89
C.240．32．22．12
D.224．0．0．255

37.下列的网络协议中，(  )的运输层协议是使用TCP的。

A.TFTP
B.DNS
C.RIP
D.TELNEI、

38.一个FTP的用户，发送了LIS27、命令来获取服务器的文件列表，这时候服务器应该通过( )端口来传输该列表。

A.21
B.20
C.22
D.19

39.UDP的报文头部不包括( )。

A.目的地址
B.报文长度
C.目的UDP端H
D.源UDP端口

二、2.综合应用题

综合应用题
41-47小题，共70分。

0.

1. 给定集合S={0，1，2，3，4)，以及优先关系R={0＜1，1＜4，1＜2，2＜3，
  2＜4，4＜0)。
  (1)R是偏序关系吗?
  (2)证明你的结论。

2. 下图所示为双总线结构机器的数据通路，IR为指令寄存器，PC为程序计数器(具有自增功能)，M为主存(受R／W信号控制)，AR为地址寄存器，DR为数据缓冲寄存器，ALU由加、减控制信号决定完成何种操作，控制信号G控制的是一个门电路。另外，线上标注有小圈表示有控制信号，例中yi表示y寄存器的输入控制信号，R1 o为寄存器R1的输出控制信号，未标字符的线为直通线，不受控制。
  (1)“ADD R2，R0”指令完成(R0)+(R2)→R0的功能操作，画出其指令周期流程图，假设该指令的地址已放入PC中。并列出相应的微操作控制信号序列。
  (2)若将“取指周期”缩短为一个CPU周期，请先画出修改数据通路，后画出指令周期流程图。
  (3)在(2)的基础上，将“执行周期”也缩短为一个CPU周期，先修改运算器数据通路，后画出指令周期流程图。此时加法指令速度比(1)提高几倍?

3. 有两部计算机M1和M2，指令系统相同。它们的操作频率频率分别是400 MHz和200 MHz。指令分成A、B和C三类，在M1上执行分别需4、6和8个周期；在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行，其中A、B和C三类指令依次占30％、50％和20％。请问哪一部机器较快完成，快几倍?

4. 某会议有n个参与者，等大家到齐后会议才能开始，利用P、V原语操作实现会议参与者进程。

5. 完成以下各小题。
 (1)什么是Belady现象?为什么会产生这种现象?
 (2)页面置换算法FIFO为什么会出现Belady现象?简述理由。
 (3)页面置换算法LRU为什么不会出现Belady现象?简述理由。

6. 假定A和B是试图在一个以太网上发送的两个站。每个站都有一个稳定的帧的队列准备发送，A的帧编号是A1，A2和A3等，B的帧编号是B1，B2和B3等。再假定指数后退的基本单元时间是T=51．2微秒。
  现在A和B同时尝试发送1号帧，碰撞，并且刚好分别选择了0×T和1×T的退避时间，也就是说，A赢得了这一次竞争，发送A1，B需要等待。在这次传送结束时，B尝试再发送B1，而A则尝试发送A2。这一轮的首次尝试产生碰撞，此时，A的退避时间从0×T和1×T中选择，而B则从0×T，…，3×T中选择。
  (1)给出A赢得第2次退避竞争的概率。
  (2)假定A已赢得了第2次退避竞争。A在成功发送A2后，接着尝试发送A3。当B再次尝试发送B1时，A和B再次碰撞。给出A赢得这第3次退避竞争的概率。
  (3)给出A赢得所有其余后退竞争的概率的合理下限值。