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

自考责任编辑：彭雅倩 2020-03-30

一、1.单项选择题

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

0.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是(     )。
  void fun(int n){
  int i，k；
  for(i=1；i<=n；i十十)
  for(j=1；j<=n；j十十){
  k=1：
  while(k<=n)k=5*k：
  }
}

A.O(n²log₂n)
B.O(nlog₅n)
C.O(n²log₅n)
D.O(n³)

1.利用栈求表达式的值时，设立运算数栈OPND。假设OPND只有两个存储单元，在下列表达式中，不发生溢出的是( )。

A.A—B*(C—D)
B.(A—B)*C—D
C.(A—B*C)—D
D.(A—B)*(C—D)

2.已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。

A.dacb
B.cadb
C.dbca
D.以上答案都不对

3.一个具有1025个结点的二叉树的高h为( )。

A.11
B.10
C.11至1025之间
D.10至1024之间

4.以下关于二叉排序树的说法正确的是( )。 I在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。 Ⅱ每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。 Ⅲ在二叉排序树中，新插入的关键字总是处于最底层。 Ⅳ在二叉排序树中，新结点总是作为叶子结点来插入的。 V二叉排序树的查找效率和二叉排序树的高度有关。

A.I、Ⅱ、Ⅳ、V
B.Ⅱ、Ⅲ、Ⅳ
C. I、Ⅲ、V
D. I、Ⅳ、V

5.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1．．n，1．．n]，且压缩存储在B[1．．k]，则k的值至少为( )。

A.n(n+1)／2
B.n²／2
C.(n—1)(n+1)／2
D.n(n—1)／2

6.下面关于图的存储的叙述中，正确的是( )。

A.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
B.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

7.用递归算法实现n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )

A.n
B.「n/2」
C.「㏒2 n」
D.「㏒2 n」+1

8.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。

A.一定都是同义词
B.一定都不是同义词
C.不一定都是同义词
D.都相同

9.如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是( )。

A.归并排序
B.希尔排序
C.快速排序
D.基数排序

10.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：
  (1)25，84，21，47，15，27，68，35，20
  (2)20，1 5，21，25，47，27，68，35，84
  (3)1 5，20，21，25，35，27，47，68，84
  (4)1 5，20，21，25，27，35，47，68，84
  则采用的排序方法是(     )。

A.选择排序
B.希尔排序
C.二路归并排序
D.快速排序

11.下图中计算机硬件系统基本组成部件①、②、③、④和⑤的名称是( )。

A.①控制器、②运算器、③存储器、④输入设备、⑤输出设备
B.①运算器、②控制器、③存储器、④输入设备、⑤输出设备
C.①运算器、②存储器、③控制器、④输入设备、⑤输出设备
D.①运算器、②控制器、③存储器、④输出设备、⑤输入设备

12.一7的八位二进制反码表示为( )。

A.00000111
B.10000111
C.11111000
D.11111001

13.设数据码字为1001001 1，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。

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

14.如果X为负数，则已知[X]_补求[一X]_补的方法是( )。

A.[X]_补各值保持不变
B.[X]_补符号位变反，其他各位不变
C.[X]_补除符号位外，各位变反，末位加1
D.[X]_补连同符号位一起各位变反，末位加1

15.下面是有关DRAM和SRAM存储器芯片的叙述：
  I DRAM芯片的集成度比SRAM高
  Ⅱ DRAM芯片的成本比SRAM高
  Ⅲ DRAM芯片的速度比SRAM快
  Ⅳ DRAM芯片工作时需要刷新，SRAM芯片工作时不需要刷新
  通常情况下，错误的是(     )。

A.I和Ⅱ
B.Ⅱ和Ⅲ
C.Ⅲ和Ⅳ
D.I和Ⅳ

16.若想对某个寄存器中的某几位清零，可以使用的一条指令是( )。

A.AND
B.OR
C.NOT
D.XOR

17.设指令由取指、分析、执行3个子部件完成，每个子部件的工作周期均为⊿t，采用常规标量流水线处理机。若连续执行10条指令，则共需时间是( )。

A.8⊿t
B.10⊿t
C.12⊿t
D.14 ⊿t

18.某计算机的指令系统中共有1 01条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。

A.101
B.102
C.103
D.104

19.某总线有104根信号线，其中数据总线(DB)32根，若总线工作频率为33 MHz，则其理论最大传输率是( )。

A.33 MB／s
B.64 MB／s
C.132 MB／s
D.164 MB／s

20.RGB8：8：8表示一帧彩色图像的颜色数是( )。

A.2³
B.2⁸
C.2²⁴
D.2⁵¹²

21.关于在I／O设备与主机间交换数据的叙述中，错误的是( )。

A.中断方式下，CPU需要执行程序来实现数据传送任务
B.中断方式和DMA方式下，CPU与I／O设备都可并行工作
C.中断方式和DMA方式中，快速I／O设备更适合采用中断方式传递数据
D.若同时接到DMA请求和中断请求，CPU优先响应DMA请求

22.交互式操作系统中为了能使多个用户同时与系统进行交互，最关键的问题是( )。

A.计算机要有足够快的运行速度
B.能快速进行内外存之间的信息交换
C.系统能够及时接收多个用户的输入
D.一段时间内所有用户的程序都能运行

23.有2个优先级相同的并发进程P1和P2，它们的执行过程如下图所示，x、y和z是共享变量。假设，当前信号量s1=0，s2=0，进程运行结束后，x、y和z的值分别为(     )。
  进程P1  进程P2
  ……   ……
  y：=20；  x：=10；
  y：=y+1； x：=x+1；
  y：=y+1； x：=x+1；
  z：=y+1； P(s1)；
  V(s1)；   x：=x+y；
  P(s2)；   z：=x+z；
  y：=z+y； V(s2)；

A.33，42，22
B.11，42，33
C.33，76，55
D.33，76，33

24.临界区是指并发进程访问共享变量段的( )。

A.管理信息
B.信息存储
C.数据
D.代码程序

25.一个正在访问临界资源的进程由于申请等待10操作而被中断时，它是( )。

A.可以允许其它进程进入与该进程相关的临界区
B.不允许其它进程进入任何临界区
C.可以允许其它进程抢占处理机，但不得进入该进程的临界区
D.不允许任何进程抢占处理机

26.在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是( )。

A.存取控制列表
B.用户权限保护
C.程序状态保护
D.界地址保护

27.段页式存储管理中，某个进程的段表和页表如下图所示，页的大小为4096B，现有逻辑地址(1，8228)，其对应的物理地址是( )。

A.483364
B.409636
C.475172
D.516132

28.分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数是( )。

A.成正比
B.成反比
C.无关系
D.固定值

29.某一个磁盘共有16个盘面，每个盘面上从外到内共有30000个磁道(或称30000个柱面)，每个磁道有250个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号(磁头号)、磁道号和扇区号均从0开始编号，那么，盘块号10025 78对应的盘面号、磁道号和扇区号是( )。

A.1，2500，78
B.10，250，78
C.2，250，1 61
D.0，4010，78

30.现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有相同的文件名。那么，实现该功能的主要方法是( )。

A.重名翻译机构
B.建立索引表
C.建立指针
D.建立树形目录结构

31.设备管理中，设备映射表(DMT)的作用是( )。

A.管理物理设备
B.管理逻辑设备
C.实现输入／输出
D.建立逻辑设备与物理设备的对应关系

32.在OSI参考模型中，实现系统间二进制信息块的正确传输，为上一层提供可靠、无错误的数据信息的协议层是( )。

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

33.光纤分为单模光纤和多模光纤，这两种光纤的区别是( )。

A.单模光纤的数据速率比多模光纤低
B.多模光纤比单模光纤传输距离更远
C.单模光纤比多模光纤的价格更便宜
D.多模光纤比单模光纤的纤芯直径粗

34.使用HDLC时，位串011111110111110进行位填充后的位模式是( )。

A.011101110101110110
B.0111101110111110
C.1.1111110111e+014
D.1.1111011011e+015

35.以太网交换机转发数据包时所依据的是( )。

A.IP地址
B.MAC地址
C.LLC地址
D.PORT、地址

36.CRC校验是目前常用的检错方式。如果采用的多项式为G(X)=X⁴+X+1，那么对于要传的信息串1101011011的CRC校验码是( )。

A.1011
B.1101
C.：1110
D.1100

37.关于因特网中的主机和路由器，以下说法正确的是(     )。
  I．主机通常需要实现TCP协议  Ⅱ．路由器必须实现TCP协议
  Ⅲ．主机必须实现IP协议    Ⅳ．路由器必须实现IP协议

A.I、Ⅱ和Ⅲ
B.I、Ⅱ和Ⅳ
C.I、Ⅲ和Ⅳ
D.Ⅱ、Ⅲ和Ⅳ

38.下面包含在TCP头中而不包含在UDP头中的信息是( )。

A.目标端口号
B.序号
C.源端口号
D.校验号

39.DNS服务器在名称解析过程中正确的查询顺序是( )。

A.本地缓存记录→区域记录→转发域名服务器→根域名服务器
B.区域记录→本地缓存记录→转发域名服务器→根域名服务器
C.本地缓存记录→区域记录→根域名服务器→转发域名服务器
D.区域记录→本地缓存记录→根域名服务器→转发域名服务器

二、2.综合应用题

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

0. 已知加权有向图G如下，回答下列问题：

  (1)画出该有向图G的邻接矩阵；
  (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

1. 已知数组A[1……n]的元素类型为整型int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。
  (1)给出算法的基本设计思想；
  (2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释；
  (3)说明你所设计算法的时间复杂度和空间复杂度。

2. 设某计算机有变址寻址、间接寻址和相对寻址等寻址方式，设当前指令的地址码部分为001AH，正在执行的指令所在地址为1F05H，变址寄存器中的内容为23A0H。
  (1)当执行取数指令时，如为变址寻址方式，则取出的数为多少?
  (2)如为间接寻址，取出的数为多少?
  (3)当执行转移指令时，转移地址为多少?
  已知存储器的部分地址及相应内容，见下表。

3. 四位运算器框图如下图所示，ALU为算术逻辑单元，A和B为三选一多路开关，预先已通过多路开关A的SW门向寄存器R₁，R₂送入数据如下：R₁=0101，R₂=1010。寄存器BR输出端接四个发光二极管进行显示。其运算过程依次如下：

  (1)R₁(A)+R₂(B)→BR(显示结果1010)；
  (2)R₂(A)+R₁(B)→BR(显示结果1111)；
  (3)R₁(A)+R₁(B)→BR(显示结果1010)；
  (4)R₂(A)+R₂(B)→BR(显示结果1111)；
  (5)R₂(A)+BR(B)→BR(显示结果1111)；
  (6)R₁(A)+BR(B)→BR(显示结果1010)；
  试分析运算器的故障位置与故障性质(“1”故障还是“0”故障)，说明理由。

4. 在某一个单处理机的系统中，外接了一台打印机，一台输入设备。当前在系统中有二个进程P0、P1已经就绪，进程P0首先获得处理机运行，调度算法为先来先服务，进程P0、P1的运行要求是这样的：P0：计算100ms，打印信息200ms，继续计算1 00ms，打印信息200ms，结束。P1：计算100ms，输入数据150ms，继续计算200ms，结束。
  请用甘特图画出它们的运行轨迹，并说明：
  进程P0、P1在运行时有无等待?若有，请指出时间区间。
  计算处理机的利用率。

5. 某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下所示，所有的数字均为十进制，每一项的起始编号是0，并且所有的地址均按字节计址，每页的大小为1024字节。

  (1)计算下列逻辑地址转换为物理地址，并说明为什么?
  0793，1197，2099，3320，41 88，5332
  (2)假设程序要访问第2页，页面置换算法为改进的Clock算法，请问该淘汰哪页?页表如何修改?上述地址的转换结果是否改变?变成多少?