【考研类试卷】考研计算机学科专业基础综合-25及答案解析.doc

《【考研类试卷】考研计算机学科专业基础综合-25及答案解析.doc》由会员分享，可在线阅读，更多相关《【考研类试卷】考研计算机学科专业基础综合-25及答案解析.doc（31页珍藏版）》请在麦多课文档分享上搜索。

1、考研计算机学科专业基础综合-25 及答案解析(总分：73.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。（分数：2.00）A.B.C.D.2.利用栈求表达式的值时，设立运算数栈 OPND。假设 OPND 只有两个存储单元，在下列表达式中，不发生溢出的是( )。AAB*(CD) B(AB)*CDC(AB*C)D D(AB)*(CD)（分数：2.00）A.B.C.D.3.已知输入序列为 abcd，经过输出受限的双端队列后，能得到的输出序列是( )。Adacb BcadbCdbca D以上答案都不对

2、（分数：2.00）A.B.C.D.4.一个具有 1025 个结点的二叉树的高度为( )。A11 B10C11 至 1025 之间 D10 至 1024 之间（分数：2.00）A.B.C.D.5.以下关于二叉排序树的说法正确的是( )。在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二又排序树在二叉排序树中，新插入的关键字总是处于最底层在二叉排序树中，新结点总是作为叶子结点来插入的二叉排序树的查找效率和二叉排序树的高度有关A、 B、 C、 D、（分数：2.00）A.B.C.D.6.简单无向图的邻接矩阵是对称

3、的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为A1n，1n，且压缩存储在 B1k，则 k 的值至少为( )。An(n+1)/2 Bn 2/2C(n-1)(n+1)/2 Dn(n-1)/2（分数：2.00）A.B.C.D.7.若无向图 G=(V，E)中含 8 个顶点，为保证图 G 在任何情况下都是连通的，则需要的边数最少是( )。A7 B21 C22 D28（分数：2.00）A.B.C.D.8.用递归算法实现 n 个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为( )。（分数：2.00）A.B.C.D.9.在采用线性探测法处理冲突所构成的散列表上进行

4、查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。A一定都是同义词 B一定都不是同义词C不一定都是同义词 D都相同（分数：2.00）A.B.C.D.10.如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是( )。A归并排序 B希尔排序 C快速排序 D基数排序（分数：2.00）A.B.C.D.11.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84(3)15

5、，20，21，25，35，27，47，68，84(4)15，20，21，25，27，35，47，68，84则采用的排序方法是( )。A选择排序 B希尔排序 C二路归并排序 D快速排序（分数：2.00）A.B.C.D.12.下图中计算机硬件系统基本组成部件、和的名称是( )。（分数：2.00）A.B.C.D.13.15 的八位二进制反码表示为( )。A00001111 B10001111 C11110000 D11110001（分数：2.00）A.B.C.D.14.设数据码字为 10010011，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。A2 B3 C4 D5（分

6、数：2.00）A.B.C.D.15.如果 X 为负数，则已知X 补 求-X 补 的方法是( )。AX 补 各值保持不变BX 补 符号位变反，其他各位不变CX 补 除符号位外，各位变反，末位加 1DX 补 连同符号位一起，各位变反，末位加 1（分数：2.00）A.B.C.D.16.下面是有关 DRAM 和 SRAM 存储器芯片的叙述：DRAM 芯片的集成度比 SRAM 高DRAM 芯片的成本比 SRAM 高DRAM 芯片的速度比 SRAM 快DRAM 芯片工作时需要刷新，SRAM 芯片工作时不需要刷新通常情况下，错误的是( )。A和 B和 C和 D和（分数：2.00）A.B.C.D.17.若想对

7、某个寄存器中的某几位清零，可以使用的一条指令是( )。AAND BOR CNOT DXOR（分数：2.00）A.B.C.D.18.设指令由取指、分析、执行 3 个子部件完成，每个子部件的工作周期均为t，采用常规标量流水线处理机。若连续执行 10 条指令，则共需时间是( )。A8t B10 t C12t D14t（分数：2.00）A.B.C.D.19.某计算机的指令系统中共有 101 条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。A101 B102 C103 D104（分数：2.00）A.B.C.D.20.某总线有 104 根信号线，其中数据总线(DB)32 根，

8、若总线工作频率为 33MHz，则其理论最大传输率是( )。A33 MB/s B64MB/s C132 MB/s D164 MB/s（分数：2.00）A.B.C.D.21.RGB8:8:8 表示一帧彩色图像的颜色数是( )。A2 3 B2 8 C2 24 D2 512（分数：2.00）A.B.C.D.22.关于程序中断方式和 DMA 方式的叙述中错误的是( )。若同时接到 DMA 请求和中断请求，CPU 优先响应 DMA 请求程序中断需要保护现场，DMA 方式不需要保护现场程序中断方式的中断请求是为了报告 CPU 数据的传输结束，而 DMA 方式的中断请求完全是为了传送数据中断方式和 DMA 方

9、式中，快速 I/O 设备更适合采用中断方式传递数据A、 B、 C、 D、（分数：2.00）A.B.C.D.23.构造操作系统的主要结构模式是( )。整体式结构 层次式结构 微内核结构(客户/服务器) 对称式结构A和 B和 C、和 D、和（分数：2.00）A.B.C.D.24.有 2 个优先级相同的并发进程 P1 和 P2，它们的执行过程如下图所示，x、y 和 z 是共享变量。假设，当前信号量 s1=0，s2=0，已知 z=2，进程运行结束后，则 x、y 和 z 的可能值分别是( )。（分数：2.00）A.B.C.D.25.一个支持并发的操作系统在运行过程中，调度模块会不断地选择新进程运行。在非

10、抢先式操作系统中，下面不是引起操作系统重新选择新进程的直接原因是( )。A分配的时间片用完 B运行着的进程要等待某一信号到来C正在运行的进程出错 D有新进程进入就绪队列（分数：2.00）A.B.C.D.26.一个正在访问临界资源的进程由于申请等待 IO 操作而被中断时，它是( )。A可以允许其它进程进入与该进程相关的临界区B不允许其它进程进入任何临界区C可以允许其它进程抢占处理机，但不得进入该进程的临界区D不允许任何进程抢占处理机（分数：2.00）A.B.C.D.27.在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是( )。A存取控制列表 B用户

11、权限保护 C程序状态保护 D界地址保护（分数：2.00）A.B.C.D.28.某简单分页式存储管理中，地址空间分页为每页 1KB，对应相应的物理块。设主存总容量为 256KB，描述主存分配情况的位示图如下所示(0 表示未分配，1 表示已分配)，起始页号 位示网0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 116 1 0 1 1 1 0 0 0 0 0 1 1 1 0 0 032 1 1 1 1 1 1 1 1 1 1 1 1 1此时，操作系统创建了一个新进程，大小为 2.5KB，按首先分配低址空间的策略，那么，分配给该进程的页面的页号分别是( )。A17、21 和 22 B2

12、1、22 和 23 C23、24 和 25 D29、30 和 31（分数：2.00）A.B.C.D.29.分页式虚拟存储管理系统中，页面的大小与可能产生的缺页中断次数是( )。A成正比 B成反比 C无关系 D固定值（分数：2.00）A.B.C.D.30.某一个磁盘共有 16 个盘面，每个盘面上从外到内共有 30000 个磁道(或称 30000 个柱面)，每个磁道有250 个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号(磁头号)、磁道号和扇区号均从 0 开始编号，那么，盘块号 1002578 对应的盘面号、磁道号和扇区号是( )。A1，2500，78 B10，250，78 C2，250，

13、161 D0，4010，78（分数：2.00）A.B.C.D.31.现代操作系统中，文件系统都有效地解决了重名问题，允许不同的文件可以有相同的文件名。那么，实现该功能的主要方法是( )。A重名翻译机构 B建立索引表C建立指针 D建立树形目录结构（分数：2.00）A.B.C.D.32.设备管理中，能够用空间换取时间的技术是( )。ASPOOLing 技术 B虚拟存储技术 C覆盖与交换技术 D通道技术（分数：2.00）A.B.C.D.33.关于 OSI 参考模型和 TCP/IP 模型在网络层提供的服务，正确的说法是( )。AOSI 模型在网络层仅提供面向连接服务BTCP/IP 模型在网络层提供无连

14、接服务COSI 模型在网络层仅提供无连接服务DTCP/IP 模型在网络层提供无连接和面向连接服务（分数：2.00）A.B.C.D.34.光纤分为单模光纤和多模光纤，这两种光纤的区别是( )。A单模光纤的数据速率比多模光纤低 B多模光纤比单模光纤传输距离更远C单模光纤比多模光纤的价格更便宜 D多模光纤比单模光纤的纤芯直径粗（分数：2.00）A.B.C.D.35.使用 HDLC 时，位串 011111110111110 进行位填充后的位模式是( )。A011101110101110110 B0111101110111110C0111111101111100 D01111101101111100（分

15、数：2.00）A.B.C.D.36.在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过一段时间，发送窗口的后沿的变化情况可能是( )。原地不动 向前移动 向后移动A、 B、 C、 D都有可能（分数：2.00）A.B.C.D.37.CRC 校验是目前常用的检错方式。如果采用的多项式为 G(X)=x4+x2+x+1，那么对于要传的信息串1010001 的 CRC 校验码是( )。A1011 B1101 C1110 D1100（分数：2.00）A.B.C.D.38.关于因特网中的主机和路由器，以下说法正确的是( )。主机通常需要实现 TCP 协议 路由器必须实现 TCP 协议主机必

16、须实现 IP 协议 路由器必须实现 IP 协议A、和 B、和 C、和 D、和（分数：2.00）A.B.C.D.39.下面包含在 TcP 头中而不包含在 UDP 头中的信息是( )。A目标端口号 B序号 C源端口号 D校验号（分数：2.00）A.B.C.D.40.DNS 服务器在名称解析过程中正确的查询顺序是( )。A本地缓存记录区域记录转发域名服务器根域名服务器B区域记录本地缓存记录转发域名服务器根域名服务器C本地缓存记录区域记录根域名服务器转发域名服务器D区域记录本地缓存记录根域名服务器转发域名服务器（分数：2.00）A.B.C.D.二、综合应用题(总题数：7，分数：-7.00)41.现有一

17、个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，em)；i=1；while(所剩边数=顶点数)从图中删去 ei；若图不再连通，则恢复 ei；i=i+1：请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举例说明。（分数：-1.00）_42.设有带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。设计在时间和空间上都尽可能高效的算法，将 L 改造成 L=(a1，a 3，a n,a4，a 2)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。(

18、3)说明你所设计算法的时间复杂度和空间复杂度。（分数：-1.00）_43.下图是某存储芯片的引脚图，请回答：(1)这个存储芯片的类型(是 RAM 还是 ROM)?这个存储芯片的容量?(2)若地址线增加一根，存储芯片的容量将变为多少?(3)这个芯片是否需要刷新?为什么?刷新和重写有什么区别?(4)如果需要刷新，请指出芯片刷新一遍需要的时间(设存取周期为 0.5s)及你准备选择的刷新方式，需说明理由。（分数：-1.00）_44.磁盘机由 6 个盘片组成，其中专设 1 个盘面为伺服面，其他的盘面作为记录数据的盘面。盘存储区域内直径为 6.1cm，外直径为 12.9cm，道密度为 22TPM，位密度为

19、 6000bpm，平均寻道时间为 10ms，磁盘转速为 7200RPM。假定 =3，试计算：(1)数据盘面数和柱面数。(2)盘组容量是多少字节?(3)数据传输率是多少字节/秒?(4)从任一磁道读取 80000 个字节数据的平均存取时间是多少?(5)假定系统配备上述磁盘机 15 台，每个磁道分为 64 个扇区，试为该磁盘系统设计一个地址方案。（分数：-1.00）_45.有 n 个生产者进程向 1 个有限的缓冲区不断地发送消息，这些消息通过缓冲区分发到 m 个消费者，缓冲区的大小只可以存放 1 条消息。生产者和消费者的工作遵循如下规则：(1)生产者和消费者对缓冲区的访问互斥；(2)对每 1 条放入

20、缓冲区的消息，所有消费者都必须接收 1 次；(3)缓冲区满时，生产者必须阻塞，缓冲区空时，消费者阻塞。请用信号量和 P、V 操作组织正确的发送和接收。用类 c 语言进行描述。（分数：-1.00）_46.并发使得处理机的利用率得到提高，其主要原因是处理机与 IO 可以同时为多个进程服务，也即处理机与 IO 设备真正地并行。但是处理机的利用率提高并不是简单地将二个进程的处理机利用率相加，而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发，调度算法采用时间片轮转，时间片很小可以不计，忽略系统的开销，请分析以下问题：假设每个进程的处理机的利用率为 u1=20%。(1)进程并发时，处理机

21、的利用率与并发进程数的关系是什么?(2)假设某一计算机系统拥有 20MB 内存，以等额分区的方式实现了多道程序设计并运行，每个分区为4MB，其中操作系统占一个分区，请问此时处理机的利用率最大为多少?(3)假设为这个系统增加了 16MB 内存，系统有足够的并发度，此时处理机的利用率最大为多少?系统的吞吐量比(2)增加了多少?(4)在(3)的基础上继续增加 16MB 内存，此时处理机的利用率最大为多少?系统的吞吐量比(3)增加了多少?分析此时增加的内存是否合算?说明为什么。（分数：-1.00）_47.假设路由器 R 存在两个接口，接口 R1 连接标准局域网，接口 R2 连接限制最大传输单元(MTU

22、)的局域网，现在一个 IP 数据包从接口 R1 转发到接口 R2，从 R2 链路上截获两个数据包的 IP 报头，如题 47-a 表所示，请回答如下问题：题 47-a 表编号 IP 分组内容(十六进制)1 45 00 00 64 00 1e 20 00 ff 01 18 27 c0 a8 01 01 c0 a8 01 022 45 00 00 58 00 1e 00 1e ff 01 38 15 c0 a8 01 01 c0 a8 01 02(1)接口 R2 的最大传输单元是多少?(2)所传输的 IP 数据包的数据大小是多少?分为了几个 IP 分片?(3)根据截获的 IP 报头，请填充没有截获的

23、数据报，注意不包含头部校验和。注：IP 分组头结构分别如题 47-b 图所示。（分数：-1.00）_考研计算机学科专业基础综合-25 答案解析(总分：73.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。（分数：2.00）A.B.C. D.解析：解析 基本运算语句是 k=5*k，设其执行时间为 T(n)。对于 j 每循环一次，该语句的执行次数为 m，有：5 mn，即 mlog 5n。所以:2.利用栈求表达式的值时，设立运算数栈 OPND。假设 OPND 只有两个存储单元，在下列表达式中，不发生溢

24、出的是( )。AAB*(CD) B(AB)*CDC(AB*C)D D(AB)*(CD)（分数：2.00）A.B. C.D.解析：解析 利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及进行后缀表达式求值这两步操作可以和在一起进行，需要设立运算符栈 OPTR 和运算数栈 OPND 两个栈。例如求选项 A 的表达式 A-B*(C-D)的过程如下表所示：求 AB*(CD)表达式值的过程当前字符 运算符栈 OPTR运算数栈 OPND说明A A AB AB* * AB( *( ABC *( ABC *( ABCD *( ABCD) * ABT1 执行 C-D 运算，令 T1=C-D AT2 执行 B

25、*T1运算，令T2=B*T1T3 执行 A-T2运算，令 T3=A-T2按照上述过程可知，选项 A 求值时，运算数栈 OPND 的大小至少为 4。例如求选项 B 的表达式(AB)*CD的过程如下表所示： 求(AB)*CD 表达式值的过程当前字符 运算符栈 OPTR运算数栈 OPND说明( (A ( A ( AB ( AB) T1 执行 A-B 运算，令 T1=A-B* * T1C T1C T2 执行 T1*C 运算，令T2=T1*CD T2DT3 执行 T2-D 运算，令 T3=T2-D按照上述过程可知，选项 B 求值时，运算数栈 OPND 的大小至少为 2。类似地，选项 C、D 求值时，运算

26、数栈 OPND 的大小分别至少为 3、3。因此本题答案为 B。3.已知输入序列为 abcd，经过输出受限的双端队列后，能得到的输出序列是( )。Adacb BcadbCdbca D以上答案都不对（分数：2.00）A.B. C.D.解析：解析 输出受限的双端队列是指删除限制在一端进行，而插入允许在两端进行的队列。分析选项 A，输入序列为 abcd，输出序列为 dacb，由输出受限性质可知以 da 开头的结果只有 dabc，选项A 为错误答案。分析选项 B，输入序列为 abcd，输出序列为 cadb，其输入输出顺序为：先在输出端输入 a，然后在非输出端输入 b，这时队列中的序列为 ba，再在输出端

27、输入 c，这时队列中的序列为 bac：；输出 c，再输出 a；再在输出端输入 d，这时队列中的序列为 bd；输出 d，再输出 b。最后得到输出序列为 cadb。分析选项 C，输入序列为 abcd，输出序列为 dbca，由输出受限性质可知以 db 开头的结果只有 dbad，选项C 为错误答案。4.一个具有 1025 个结点的二叉树的高度为( )。A11 B10C11 至 1025 之间 D10 至 1024 之间（分数：2.00）A.B.C. D.解析：解析 一棵二叉树每层只有 1 个结点，则具有 1025 个结点的二叉树的最大高度为 1025。一个具有 1025 个结点的完全二叉树的高度为 1

28、1。这一个具有 1025 个结点的二叉树的高 h 为 11 至 1025 之间。5.以下关于二叉排序树的说法正确的是( )。在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二又排序树在二叉排序树中，新插入的关键字总是处于最底层在二叉排序树中，新结点总是作为叶子结点来插入的二叉排序树的查找效率和二叉排序树的高度有关A、 B、 C、 D、（分数：2.00）A.B.C.D. 解析：解析 对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字；右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右

29、孩子的关键字进行比较。在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和 log2n 成正比。6.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为A1n，1n，且压缩存储在 B1k，则 k 的值至少为( )。An(n+1)/2 Bn 2/2C(n-1)(n+1)

30、/2 Dn(n-1)/2（分数：2.00）A.B.C.D. 解析：解析 简单无向图的邻接矩阵是对称的，且对角线元素均是 0，故压缩存储只需存储下三角或是上三角(均不包括对角线)即可。故有(上三角形式)：k=(n-1)+(n-2)+1+0=n2-(1+2+n)=n(n-1)/2。7.若无向图 G=(V，E)中含 8 个顶点，为保证图 G 在任何情况下都是连通的，则需要的边数最少是( )。A7 B21 C22 D28（分数：2.00）A.B.C. D.解析：解析 本题考查图的基本概念。要保证无向图 G 在任何情况下都是连通的，即任意变动图 G 中的边，G 始终保持连通。首先需要图 G 的任意 7

31、个结点构成完全连通子图 G1，需 n(n-1)/2=7(7-1)/2=21 条边，然后再添加一条边将第 8 个结点与G1连接起来，共需 22 条边。本题非常容易错误地选择选项 A，主要原因是对“保证图 G 在任何情况下都是连通的”的理解，分析选项A，在图 G 中，具有 8 个顶点 7 条边并不能保证其一定是连通图，即有 n-1 条边的图不一定是连通图。分析选项 D，图 G 有 8 个顶点 28 条边，那么图 G 一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。8.用递归算法实现 n 个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最

32、小容量应为( )。（分数：2.00）A.B.C.D. 解析：解析 根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记录，表示待查有序表中元素的个数为 n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n/2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n/4；依次类推，当所确定的查找区间中的元素为 O 时，递归调用该算法的次数为 次，查找结束。归纳总结 折半查找法在查找成功时和给定值进行比较的关键字个数至多是

33、；在查找不成功时和给定值进行比较的关键字个数最多也不超过9.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值( )。A一定都是同义词 B一定都不是同义词C不一定都是同义词 D都相同（分数：2.00）A.B.C. D.解析：解析 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。10.如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是( )。A归并排序 B希尔排序 C快速排序 D基数排序（分数：2.00）A.B.C.D. 解析：解析 按照所有中国人的生日(月、日)排序，一方面待排序记

34、录个数 n 是非常大的，另一方面关键字所含的排序码为 2，且一个排序码基数为 12，另一个为 31，都是较小的常数值，采用基数排序可以在 O(n)内完成排序过程。11.用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84(3)15，20，21，25，35，27，47，68，84(4)15，20，21，25，27，35，47，68，84则采用的排序方法是( )。A选择排序 B希尔排序 C二路归并排序 D快速排序（分数：2

35、.00）A.B.C.D. 解析：解析 本题主要考查各种排序的手工排序过程。选择排序在每趟结束后可以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递增，直到最后的一个有序的完整序列；希尔排序也是形成部分有序的序列；快速排序以某个元素为界将大于它和小于它的关键字划分为两个子序列，再将该元素放在中间。观察题中的元素排序过程，可知是快速排序。12.下图中计算机硬件系统基本组成部件、和的名称是( )。（分数：2.00）A.B. C.D.解析：解析 第 12 题图中所示为冯诺依曼计算机硬件系统的五大基本部件，包括运算

36、器、控制器、存储器、输入设备和输出设备五大基本部件。归纳总结 运算器用来进行各种运算和数据转换；控制器则为计算机的工作提供统一的时钟和各种命令，协调计算机的各部件自动地工作；存储器用来存放程序、数据；输入设备和输出设备用来接收用户提供的外部信息或向用户提供输出信息。解题技巧 图中虚线框内是 CPU 部分，CPU 包括运算器和控制器，据此可排除选项 C；与其他 4 个部件均有联系，可以确定是控制器，据此可排除选项 A；最后根据信息的传送方向可确定为输入设备，为输出设备。13.15 的八位二进制反码表示为( )。A00001111 B10001111 C11110000 D11110001（分数：

37、2.00）A.B.C. D.解析：解析 A 选项为+15，B 选项为-15 的原码，D 选项为-15 的补码。归纳总结 正数的原码、补码和反码的表示形式是相同的，都等于真值本身，而负数的原码、补码和反码各有不同的表示，其中反码表示法是将真值的数值部分按位取反。解题技巧 因为这是一个负数，所以可以首先排除掉选项 A。然后可以看出选项 B、C、D 分别代表-15 的原码、反码和补码。14.设数据码字为 10010011，采用海明码进行校验，若仅考虑纠正一位错，则必须加入的(冗余)位数是( )。A2 B3 C4 D5（分数：2.00）A.B.C. D.解析：解析 如果仅考虑纠正 1 位错的情况，只要

38、满足 2kn+k+1 就可以了(设校验位的位数为 k，信息位的位数为 n)。此题中因为 n=8，所以 k4。如果在纠正 l 位错的同时还要能发现 2 位错，则满足 2k-1n+k+1。归纳总结 海明码实现原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每一个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。15.如果 X 为负数，则已知X 补 求-X 补 的方法是( )。AX 补 各值保持不变BX 补 符号位变反，其他各位不变CX 补 除符号位外，各位变反，末位加

39、 1DX 补 连同符号位一起，各位变反，末位加 1（分数：2.00）A.B.C.D. 解析：解析 -X 补 被称为X 补 的机器负数，由X 补 求-X 补 的过程称为对X 补 变补(求补)，这是做减法运算时必须要完成的操作。归纳总结 不管 X 的真值为正或为负，已知X 补 求-X 补 的方法是：将X 补 连同符号位一起求反，末尾加“1”。X 补 表示的真值如果是正数，则变补后X 补 所表示的真值变为负数；反过来，X 补 表示的真值如果是负数，则变补后一 X补所表示的真值变为正数。解题技巧 此题容易错选选项 C。如果除符号位外，各位变反，末位加 1，得到的是X原而不是-X 补 ，且只有 X 为负

40、数时成立。16.下面是有关 DRAM 和 SRAM 存储器芯片的叙述：DRAM 芯片的集成度比 SRAM 高DRAM 芯片的成本比 SRAM 高DRAM 芯片的速度比 SRAM 快DRAM 芯片工作时需要刷新，SRAM 芯片工作时不需要刷新通常情况下，错误的是( )。A和 B和 C和 D和（分数：2.00）A.B. C.D.解析：解析 DRAM 的集成度高于 SRAM，SRAM 的速度高于 DRAM，可以推出 DRAM 的成本低于 SRAM，SRAM 芯片工作时不需要刷新，DRAM 芯片工作时需要刷新。归纳总结 随机存储器 RAM 又可分为静态 RAM(SRAM)和动态 RAM(DRAM)两种

41、。SRAM 由 6 个 MOS 管组成一个记忆单元，它的存取速度快，但集成度低，功耗也较大；DRAM 由 4 个 MOS 管或单个 MOS 管组成一个记忆单元，它的集成度高，功耗小，但存取速度慢。DRAM 是靠 MOs 电路中的栅极电容来存储信息的，栅极电容上的电荷数目会随着时间推移逐步泄漏，因此每隔一定的时间必须向栅极电容补充一次电荷，这个过程称为“刷新”。解题技巧 这类选择题是由多选题改造而来的单选题，其难度高于普通的单选题。在解题时需要首先判断多段叙述中各自的正确性，然后再在四个选项中挑选正确的选项。17.若想对某个寄存器中的某几位清零，可以使用的一条指令是( )。AAND BOR CN

42、OT DXOR（分数：2.00）A. B.C.D.解析：解析 对某个寄存器中的某几位清零又称为按位清，将此寄存器的内容和一个特定的源操作数做“与”运算，即可得到。归纳总结 一般计算机都具有与、或、非和异或等逻辑运算指令。这类指令在没有设置专门的位操作指令的计算机中常用于对数据字(字节)中某些位(一位或多位)进行操作。如利用“与”指令还可以使目的操作数的某些位置为“0”。只要源操作数的相应位为“0”，其余位为“1”，然后执行“与”指令即可。利用“或”指令可以使目的操作数的某些位置为“1”。只要源操作数的相应位为“1”，其余位为“0”，然后执行“或”指令即可。解题技巧 此题容易错选选项 D，XOR

43、 指令可以实现对整个寄存器的全部位清零的功能，但不能实现对指定的某几位清零的功能。18.设指令由取指、分析、执行 3 个子部件完成，每个子部件的工作周期均为t，采用常规标量流水线处理机。若连续执行 10 条指令，则共需时间是( )。A8t B10 t C12t D14t（分数：2.00）A.B.C. D.解析：解析 具有 3 个功能段的流水线连续执行 10 条指令共需时间=3t+9t=12t。归纳总结 流水线在开始时总要有一段建立时间，结束时又需要有排空的时间，设-m 段流水线的各段经过时间均为t，则需要 T。一 mt 的流水建立时间，之后每隔t 就可流出一条指令，完成 n 个任务共需时间 T

44、mt+(n 一 1)t。19.某计算机的指令系统中共有 101 条不同的指令，采用微程序控制方式时，控制存储器中具有的微程序数目至少是( )。A101 B102 C103 D104（分数：2.00）A.B. C.D.解析：解析 除去 101 条机器指令所对应的 101 个微程序外，至少还有一个取指微程序，所以至少有102 个微程序。归纳总结 通常，一条机器指令对应一个微程序。由于任何一条机器指令的取指令操作都是相同的，因此可以将取指令操作抽出来编成一个独立的微程序，这个微程序只负责将指令从主存中取出送至指令寄存器。此外，也可以编出对应间址周期的微程序和中断周期的微程序。这样，控制存储器中的微程

45、序个数应等于指令系统中的机器指令数再加上对应的取指、间址和中断周期等公用的微程序数。若指令系统中具有n 种机器指令，则控制存储器中的微程序数至少有 n+1 个。20.某总线有 104 根信号线，其中数据总线(DB)32 根，若总线工作频率为 33MHz，则其理论最大传输率是( )。A33 MB/s B64MB/s C132 MB/s D164 MB/s（分数：2.00）A.B.C. D.解析：解析 在总线的 104 根信号线中，数据总线占 32 根，也就是 4 个字节，由于总线工作频率为33MHz，所以理论的最大数据传输率=4B33MHz=132MB/s。归纳总结 总线的最大数据传输率又称总线带宽，即每秒传输的字节数。总线带宽=总线宽度总线频率。21.RGB8:8:8 表示一帧彩色图像的颜色数是( )。A2 3 B2 8 C2 24 D2 512（分数：2.00）A.B.C. D.解析：解析 RGB8:8:8 是指红、绿、蓝 3 种颜色都各有 8 位，总共的颜色深度为 24 位，所以颜色数为224种。归纳总结 颜色深度与颜色数的对应关系是：颜色数=2 颜色深度 。22.关于程序中断方式和 DMA 方式的叙述中错误的是( )。若同时接到 DMA 请求和中断请求，CPU 优先响应 DMA 请求程序