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

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

1、考研计算机学科专业基础综合-35 及答案解析(总分：148.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 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;AO(n 2log2n) BO(nlog 5n) CO(n 2log5n) DO(n 3)（分数：2.00）A.B.C.D.2.利用栈求表达式的值时，设立运算数栈 OPND。假设 OPND只有两个存储单元，在下列表达式中，不发生溢出的是_

2、。AA-B*(C-D) B(A-B)*C-DC(A-B*C)-D D(A-B)*(C-D)（分数：2.00）A.B.C.D.3.输入受限的双端队列是指元素只能从队列的一端输入，但可从队列的两端输出。若有 8，1，4，2 依次进入输入受限的双端队列，则得不到的输出序列是_。A2814 B1482 C4218 D2148（分数：2.00）A.B.C.D.4.一个具有 1025个结点的二叉树的高度为_。A11 B10C11 至 1025之间 D10 至 1024之间（分数：2.00）A.B.C.D.5.以下关于二叉排序树的说法正确的是_。 在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子

3、关键字小 每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树 在二叉排序树中，新插入的关键字总是处于最底层 在二叉排序树中，新结点总是作为叶子结点来插入的 二叉排序树的查找效率和二叉排序树的高度有关A、 B、 C、 D、（分数：2.00）A.B.C.D.6.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 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个顶点，为保证图

4、G在任何情况下都是连通的，则需要的边数最少是_。A7 B21 C22 D28（分数：2.00）A.B.C.D.8.用递归算法实现 n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为_。（分数：2.00）A.B.C.D.9.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值_。A一定都是同义词 B一定都不是同义词C不一定都是同义词 D都相同（分数：2.00）A.B.C.D.10.如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是_。A归并排序 B希尔排序 C快速排序 D基数排

5、序（分数：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，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.若存储周期 100ns，每次读出一个字节，则该存储器的数据传输率为_。A3210 6b/s B810

6、 6b/sC80Mb/s D8010 6b/s（分数：2.00）A.B.C.D.13.假定采用 IEEE754单精度浮点数格式表示一个数为 45100000H，则该数的值是_。A(+1.125) 10210 B(+1.125) 10211C(+0.125) 10211 D(+0.125) 10210（分数：2.00）A.B.C.D.14.字长相同的两种浮点数，第一种阶码位数多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是 2，则有_。A它们表示的数的范围与精度相同 B第一种数的范围大，精度低C第二种数的范围大，精度高 D第一种数的范围大，精度高（分数：2.00）A.B.C.D.15.

7、以下关于校验码的叙述中，正确的是_。 校验码的码距必须大于 2 校验码的码距越大检错纠错能力越强 增加奇偶校验位的位数可以提高奇偶校验的正确性 采用奇偶校验可检测出一位数据错误的位置并加以纠正 采用海明校验可检测出一位数据错误的位置并加以纠正 循环冗余校验码是通过除法运算来建立数据和校验位之间的约定关系的A、 B、 C、 D、（分数：2.00）A.B.C.D.16.若内存地址区间为 4000H43FFH，每个存贮单元可存储 16位二进制数，该内存区域用 4片存储器芯片构成，则构成该内存所用的存储器芯片的容量是_。A51216bit B2568bit C25616bit D10248bit（分数

8、：2.00）A.B.C.D.17.数据寻址和指令寻址的不同点在于_。A前者决定操作数地址，后者决定程序转移地址B前者决定程序转移地址，后者决定操作数地址C前者是短指令，后者是长指令D前者是长指令，后者是短指令（分数：2.00）A.B.C.D.18.流水计算机中，下列语句发生的数据相关类型是_。ADD R1，R2，R3；(R2)+(R3)R1ADD R4，R1，R5；(R1)+(R5)R4A写后读 B读后写 C写后写 D读后读（分数：2.00）A.B.C.D.19.下列有关控制器的说法正确的是_。A无论是组合逻辑控制器和时序逻辑控制器，都需要有程序计数器B微程序控制器不需要程序计数器，只要有微程

9、序计数器C都可以不需要程序计数器D以上都不对（分数：2.00）A.B.C.D.20.下面是关于目前流行的 PC机主板的叙述： 主板上通常包含微处理器插座(或插槽)和芯片组 主板上通常包含 ROM BIOS和存储器(内存条)插座 主板上通常包含 PCI和 AGP总线插槽 主板上通常包含 IDE连接器其中正确的是_。A仅 B仅和 C仅、和 D、和（分数：2.00）A.B.C.D.21.采用页式内存管理某虚拟存储器，使用 LRU页面替换算法，假定内存容量为 4个页面，且开始时是空的，考虑下面的页面访问地址流(每次访问在一个时间单位内完成)为1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，

10、1，7，1，3，7，则页面命中次数是_。A24 B14 C16 D6（分数：2.00）A.B.C.D.22.外部设备打印机适合于连接的通道是_。A数组多路通道 B字节多路通道C选择通道 D任意一种通道（分数：2.00）A.B.C.D.23.用户程序在用户态下使用陷入指令而引起的中断是_。A故障中断 B外部中断 C不可屏蔽中断 D访管中断（分数：2.00）A.B.C.D.24.下列所示关系中，不是信号量能实现的功能是_。A进程同步 B进程互斥C执行的前趋关系 D进程的并发执行（分数：2.00）A.B.C.D.25.下面是一个并发进程的程序代码，正确的说法是_。semaphore x1=x2=y=

11、1;int c1=c2=0;cobeginprocedure P1 procedure P2P(x1); P(x2);if(+c1=1)P(y); if(+c2=1)P(y);V(x1); V(x2);computer(A); computer(B);P(x1); P(x2);if(-c1=0)V(y); if(-c2=0)V(y);V(x1); V(x2);end endcoendA进程不会死锁，也不会饥饿 B进程不会死锁，但是会饥饿C进程会死锁，但是不会饥饿 D进程会死锁，也会饥饿（分数：2.00）A.B.C.D.26.在操作系统中，进程 A与进程 B共享变量 S1，进程 A与进程 C共享

12、变量 S2，则进程 B和进程 C之间是_。A必须互斥 B必须同步 C同步或互斥 D无关系（分数：2.00）A.B.C.D.27.操作系统中为实现多道程序并发，对内存管理可以有多种方式，其中内存利用率最高的是_。A静态分区管理 B动态分区管理 C分页管理 D分段管理（分数：2.00）A.B.C.D.28.在一个请求页式的虚拟存储系统中，每个页面的大小分为 4096字节。如下某个程序需要将数组赋值，假设，执行代码已经驻留内存，而数据页面尚未分配，数组按先行后列存放。请计算，其缺页中断次数是_。int a10241024;int i, j;i=0;for(j=0; j1023; j+)aij=j;A

13、2 B1 C1024 D512（分数：2.00）A.B.C.D.29.在页式存储管理系统中选择页面的大小，需要考虑的因素是_。 页面大的好处是页表较小 页面小的好处是可以减少由内碎片引起的内存浪费 通常，影响磁盘访问时间的主要因素不在于页面的大小，所以使用时可优先考虑较大的页面A和 B和 C和 D和和（分数：2.00）A.B.C.D.30.操作系统中，采用了多种技术改善磁盘输入输出的访问速度，下列不能提高磁盘访问速度的是_。A加快盘片转速 B运用磁臂调度算法C采用通道技术 D添加磁盘缓冲（分数：2.00）A.B.C.D.31.有一个文件含有 10000个文件块，若将其顺序结构存放，则对文件块顺

14、序查找的平均时间为 5000个。若按索引顺序文件的结构存放，每个索引为 100个文件块，则顺序查找次数是_。A500 B100 C50 D10（分数：2.00）A.B.C.D.32.计算机系统中，不需要处理机干预，能够在内存中(包括映射的内存)快速搬运数据的控制器是_。A通道控制器 BDMA 控制器 C中断控制器 D时钟控制器（分数：2.00）A.B.C.D.33.在协议数据单元中，控制信息所不包括的内容是_。A地址 B查错码 C数据 D协议控制（分数：2.00）A.B.C.D.34.通过改变载波信号的相位值来表示数字信号 1、0 的方法是_。AASK BFSK CPSK DPPP（分数：2.

15、00）A.B.C.D.35.假设一个 NAT服务器其公网地址为 205.56.79.35，并且有如下表的表项，那么当一个 IP地址为192.168.32.56端口为 21分组进入公网的时候，转换后的端口号和源 IP地址是_。表转换端口 原 IP地址 原端口2056 192.168.32.56 212057 192.168.32.56 201892 192.168.48.26 802256 192.168.55.10680A205.56.79.35:2056 B192.168.32.56:2056C205.56.79.35:1892 D205.56.79.35:2256（分数：2.00）A.B.

16、C.D.36.IPv6协议数据单元由一个固定头部和若干个扩展头部以及上层协议提供的负载组成，其中用于标识松散源路由功能的扩展头是_。A目标头部 B路由选择头部C分段头部 D安全封装负荷头部（分数：2.00）A.B.C.D.37.现有一个长度为 3000B的 IP数据报，其 IP头部的长度为 20B，该 IP数据报如在最大帧长度为 1518B的以太网中进行传输，那么为了正确传输，最后一个 IP数据分片的数据大小是_。A20B B30B C40B D50B（分数：2.00）A.B.C.D.38.传输层用于标识不同的应用的是_。A物理地址 B端口号 CIP 地址 D逻辑地址（分数：2.00）A.B.

17、C.D.39.如下图所示一台路由器连接 3个以太网，假设主机 C上要发送一个 IP分组，使得主机 D和主机 E都会接收它，而子网 3和子网 4上的主机都不会接收它，那么该 IP分组的目标 IP地址是_。（分数：2.00）A.B.C.D.40.DNS作为一种分布式系统，所基于的网络应用模式是_。AC/S 模式 BB/S 模式 CP2P 模式 D以上均不正确（分数：2.00）A.B.C.D.二、综合应用题(总题数：7，分数：68.00)41.现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(e1，e2，en)；i=1;while(所剩边数=顶点数)从图中删去 ei

18、;若图不再连通，则恢复 ei;i=i+1;请问上述方法能否求得原图的最小生成树?若该方法可行，请证明之；否则请举例说明。（分数：10.00）_设有带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。设计在时间和空间上都尽可能高效的算法，将 L改造成 L=(a1，a 3，a n，a 4，a 2)。要求：（分数：12.00）(1).给出算法的基本设计思想。（分数：4.00）_(2).根据设计思想，采用 C或 C+或 Java语言描述算法，关键之处给出注释。（分数：4.00）_(3).说明你所设计算法的时间复杂度和空间复杂度。（分数：4.00）_设某计算机有变址寻址、间接寻址

19、和相对寻址等寻址方式，设当前指令的地址码部分为。01AH，正在执行的指令所在地址为 1F05H，变址寄存器中的内容为 23A0H。（分数：12.00）(1).当执行取数指令时，如为变址寻址方式，则取出的数为多少?（分数：4.00）_(2).如为间接寻址，取出的数为多少?（分数：4.00）_(3).当执行转移指令时，转移地址为多少?已知存储器的部分地址及相应内容，见下表。表地址 内容001AH1F05H1F1FH23A0H23BAH23A0H2400H2500H2600H1748H（分数：4.00）_42.四位运算器框图如下图所示，ALU 为算术逻辑单元，A 和 B为三选一多路开关，预先已通过多

20、路开关 A的 SW门向寄存器 R1，R2 送入数据如下：R1=0101，R2=1010。寄存器 BR输出端接四个发光二极管进行显示。其运算过程依次如下：（分数：7.00）_43.考虑有三个吸烟者进程和一个经销商进程的系统中，每个吸烟者连续不断地制作烟卷并将其做好的烟卷消费掉(即吸烟)。制烟和吸烟过程需要烟草、烟纸和火柴三种原料。这三个吸烟者自己分别掌握有烟草、烟纸和火柴中的一种。经销商能源源不断地提供上述三种原料，每次经销商会提供上述三种原料中的任意两种，当某个吸烟者发现经销商提供的原料恰好是自己所需的时候，该吸烟者会取走那两种原料，与他自己拥有的原料一起，开始制烟和吸烟。经销商发现原料被取走

21、了就会继续提供任意两种原料，如此反复。试设计一个使经销商和吸烟者同步的算法，并用 C语言编写程序。（分数：7.00）_某一个计算机系统采用虚拟页式存储管理方式，当前在处理机上执行的某一个进程的页表如下表所列，所有的数字均为十进制，每一项的起始编号是 0，并且所有的地址均按字节计址，每页的大小为 1024字节。表逻辑页号 存在位 引用位 修改位 页框号0 1 1 0 91 1 1 1 32 0 0 0 3 1 0 0 14 0 0 0 5 1 0 1 5（分数：8.00）(1).将下列逻辑地址转换为物理地址，并说明理由。0793，1197，2099，3320，4188，5332（分数：4.00）

22、_(2).假设程序要访问第 2页，页面置换算法为改进的 Clock算法，请问该淘汰哪页?页表如何修改?上述地址的转换结果是否改变?变成多少?（分数：4.00）_如果下表所列是路由器 R1的路由表，仔细分析各个表项的特点，并回答如下问题。表掩码 目的地址 下一跳 接口 标志255.255.192.0 145.23.129.7 m0255.255.255.224202，14.17.193 m10.0.0.0 0.0.0.0 130.56.12.4m2 G（分数：12.00）(1).给出 m0和 m1所在的网络号，以及可连接的最大主机数目。（分数：4.00）_(2).给出接口 m0，m1 和 m2的

23、合理的 IP地址(注要求取最小的地址)。（分数：4.00）_(3).试给出网络的拓扑。（分数：4.00）_考研计算机学科专业基础综合-35 答案解析(总分：148.00，做题时间：90 分钟)一、单项选择题(总题数：40，分数：80.00)1.设 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;AO(n 2log2n) BO(nlog 5n) CO(n 2log5n) DO(n 3)（分数：2.00）A.B.C. D.解析：解

24、析 基本运算语句是 k=5*k，设其执行时间为 T(n)。对于 j每循环一次，该语句的执行次数为 m，有：5 mn，即 mlog 5n。所以：2.利用栈求表达式的值时，设立运算数栈 OPND。假设 OPND只有两个存储单元，在下列表达式中，不发生溢出的是_。AA-B*(C-D) B(A-B)*C-DC(A-B*C)-D D(A-B)*(C-D)（分数：2.00）A.B. C.D.解析：解析 利用栈求表达式的值时，将中缀表达式转换成后缀表达式以及进行后缀表达式求值这两步操作可以一起进行，需要设立运算符栈 OPTR和运算数栈 OPND两个栈。例如求选项 A的表达式 A-B*(C-D)的过程如表 1

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

26、(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 求值时，运算数栈 OPND的大小分别至少为 3、3。因此本题答案为 B。3.输入受限的双端队列是指元素只能从队列的一端输入，但可从队列的两端输出。若有 8，1，4，2 依次进入输入受限的双端队列，则得不到的输出序列是_。A2814 B1482 C4218 D2148（分数：2.00）A.B.C.

27、D. 解析：解析 设 e1端可输入可输出，e2 端仅能输出；且设某元素 x从 e1端进队为 xc1进 ，从 e1端出队为 xc1出 ，从 e2端出队为 xc2出 ，则各选项出队情况如下表所列。表 8，1，4，2 进队/出队情况分析预期输出 进队/出队过程实际输出2814 8e1进 ，1 e2进 ，4 e2进 ，2 e1进 ，2 e1出 ，8 e1出 ，1 e1出 ，4 e1出 28141482 8e1进 ，1 e1进 ，1 e1进 ，4 e1进 ，4 e1进 ，8 e1出 ，2 e1进 ，2 e1出 14824218 8e1进 ，1 e1进 ，4 e1进 ，4 e1出 ，2 e1进 ，2 e1

28、出 ，1 e1出 ，8 e1出 42182148 8e1进 ，1 e1进 ，4 e1进 ?将使 4先于 1输出；4 e2进 ?将使 8先于 4输出 不可能4.一个具有 1025个结点的二叉树的高度为_。A11 B10C11 至 1025之间 D10 至 1024之间（分数：2.00）A.B.C. D.解析：解析 一棵二叉树每层只有 1个结点，则具有 1025个结点的二叉树的最大高度为 1025。一个具有 1025个结点的完全二叉树的高度为 11。这一个具有 1025个结点的二叉树的高 h为 11至 1025之间。5.以下关于二叉排序树的说法正确的是_。 在二叉排序树中，每个结点的关键字都比左孩

29、子关键字大，比右孩子关键字小 每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树 在二叉排序树中，新插入的关键字总是处于最底层 在二叉排序树中，新结点总是作为叶子结点来插入的 二叉排序树的查找效率和二叉排序树的高度有关A、 B、 C、 D、（分数：2.00）A.B.C.D. 解析：解析 对于二叉排序树，左子树上所有记录的关键字均小于根记录的关键字，右子树上所有记录的关键字均大于根记录的关键字。而不是仅仅与左、右孩子的关键字进行比较。在二叉排序树中，新插入的关键字总是作为叶子结点来插入的，但是叶子结点不一定总是处于最底层。对于每一棵特定的二叉排序树，均可按照平均查找

30、长度的定义来求它的 ASL值，显然，由值相同的 n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和 log2n成正比。6.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图 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. 解析：解析 简单无向图的邻接矩阵是对称的，且对角线元素均是 0，故压缩存储只需存储下三角或是上三角(均不包括对角

31、线)即可。故有(上三角形式)：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个结点构成完全连通子图 G1，需 n(n-1)/2=7(7-1)/2=21条边，然后再添加一条边将第 8个结点与G1连接起来，共需 22条边。本题非常容易错误地选择选项 A，主要原因是对“

32、保证图 G在任何情况下都是连通的”的理解，分析选项A，在图 G中，具有 8个顶点 7条边并不能保证其一定是连通图，即有 n-1条边的图不一定是连通图。分析选项 D，图 G有 8个顶点 28条边，那么图 G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。8.用递归算法实现 n个不同元素的有序序列的折半查找，采用一个递归工作栈时，该栈的最小容量应为_。（分数：2.00）A.B.C.D. 解析：解析 根据折半查找的过程，由于需要栈结构实现递归算法，栈的容量应该保证能存放查找失败时所有未完成运行的算法的活动记录。第一次调用该算法时，栈中加入了一条查找记

33、录，表示待查有序表中元素的个数为 n；第二次调用时，无论是在前半区还是后半区查找，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n/2；第三次调用时，栈中又加入了一条查找记录，所确定的查找区间中的元素最多为 n/4；依次类推，当所确定的查找区间中的元素为 0时，递归调用该算法的次数为 次，查找结束。折半查找法在查找成功时和给定值进行比较的关键字个数至多是 ；在查找不成功时和给定值进行比较的关键字个数最多也不超过9.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值_。A一定都是同义词 B一定都不是同义词C不一定都是同义词

34、 D都相同（分数：2.00）A.B.C. D.解析：解析 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。10.如果将中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中最快的是_。A归并排序 B希尔排序 C快速排序 D基数排序（分数：2.00）A.B.C.D. 解析：解析 按照所有中国人的生日(月、日)排序，一方面待排序记录个数 n是非常大的，另一方面关键字所含的排序码为 2，且一个排序码基数为 12，另一个为 31，都是较小的常数值，采用基数排序可以在 O(n)内完成排序过程。11.用某种排序方法对线性表(25，84，21，47，15，27，68，35，

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.00）A.B.C.D. 解析：解析 本题主要考查各种排序的手工排序过程。选择排序在每趟结束后可以确定一个元素的最终位置，而题中第一趟结束后最小关键字并未出现在第一个位置；归并排序会在第一趟结束后，形成若干个部分有序的子序列，并且长度递增，直到

36、最后的一个有序的完整序列；希尔排序也是形成部分有序的序列；快速排序以某个元素为界将大于它和小于它的关键字划分为两个子序列，再将该元素放在中间。观察题中的元素排序过程，可知是快速排序。12.若存储周期 100ns，每次读出一个字节，则该存储器的数据传输率为_。A3210 6b/s B810 6b/sC80Mb/s D8010 6b/s（分数：2.00）A.B.C.D. 解析：解析 由于存储周期 100ns，每次读出一个字节，则数据传输率=8/(10010 -9)=80106位/秒。选项 C的错误在于存在误差，1M=10241024。主存的数据传输率表示每秒从主存进出信息的最大数量，单位为字/秒或

37、字节/秒。13.假定采用 IEEE754单精度浮点数格式表示一个数为 45100000H，则该数的值是_。A(+1.125) 10210 B(+1.125) 10211C(+0.125) 10211 D(+0.125) 10210（分数：2.00）A.B. C.D.解析：解析 45100000H=0100 0101 0001 0000 0000 0000 0000 0000，符号位=0，阶码=10001010，尾数=00100000000000000000000。阶码真值=10001010-1111111=1011B=11。因为隐含了尾数最高数位，尾数为 1.001，所以其真值为(+1.125

38、) 10211。选项 C和 D没有考虑隐含尾数最高数位的问题。14.字长相同的两种浮点数，第一种阶码位数多，尾数位数少，第二种阶码位数少，尾数位数多，阶的底数都是 2，则有_。A它们表示的数的范围与精度相同 B第一种数的范围大，精度低C第二种数的范围大，精度高 D第一种数的范围大，精度高（分数：2.00）A.B. C.D.解析：解析 字长相同的两种浮点数，阶码位数较多表示的数范围越大，尾数越多表示的精度越高。所谓精度是指一个数所含有效数值位的位数，机器字长越长精度就越高。对于字长相同的浮点数来说，阶码位数多，就意味着尾数位数少，数的表示范围增大正是以降低精度为代价的。15.以下关于校验码的叙述

39、中，正确的是_。 校验码的码距必须大于 2 校验码的码距越大检错纠错能力越强 增加奇偶校验位的位数可以提高奇偶校验的正确性 采用奇偶校验可检测出一位数据错误的位置并加以纠正 采用海明校验可检测出一位数据错误的位置并加以纠正 循环冗余校验码是通过除法运算来建立数据和校验位之间的约定关系的A、 B、 C、 D、（分数：2.00）A.B.C.D. 解析：解析 码距大于等于 2的数据校验码，开始具有检错的能力。码距越大，检、纠错能力就越强；奇偶校验码的码距等于 2，可以检测出一位错误(或奇数位错误)，但不能确定出错的位置，也不能检测出偶数位错误；海明码的码距大于 2，不仅可以发现错误，还能指出错误的位

40、置，为自动纠错提供了依据；循环冗余校验码则通过除法运算来建立数据和校验位之间的约定关系。数据校验码是指那些能够发现错误或能够自动纠正错误的数据编码，又称之为“检错纠错编码”。任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数，被称为数据校验码的码距。具有检、纠错能力的数据校验码的实现原理是：在编码中，除去合法的码字外，再加进一些非法的码字，当某个合法码字出现错误时，就变成为非法码字。合理地安排非法码字的数量和编码规则，就能达到纠错的目的。16.若内存地址区间为 4000H43FFH，每个存贮单元可存储 16位二进制数，该内存区域用 4片存储器芯片构成，则构成该内存所用的存储器芯

41、片的容量是_。A51216bit B2568bit C25616bit D10248bit（分数：2.00）A.B.C. D.解析：解析 43FF-4000+1=400，即内存区域为 1K个单元，总容量为 1K16。现有 4片存储芯片构成，则芯片容量为 25616bit。根据总容量和芯片数，由于17.数据寻址和指令寻址的不同点在于_。A前者决定操作数地址，后者决定程序转移地址B前者决定程序转移地址，后者决定操作数地址C前者是短指令，后者是长指令D前者是长指令，后者是短指令（分数：2.00）A. B.C.D.解析：解析 数据寻址寻找的是操作数的地址，指令寻址寻找的是下条指令的地址，它决定于程序转

42、移地址。寻址可以分为指令寻址和数据寻址。寻找下一条将要执行的指令地址称为指令寻址，寻找操作数的地址称为数据寻址。指令寻址比较简单，它又可以细分为顺序寻址和跳跃寻址。而数据寻址方式种类较多，其最终目的都是寻找所需要的操作数。数据寻址和指令寻址只与寻找的地址类型有关，而与指令的长度无关。18.流水计算机中，下列语句发生的数据相关类型是_。ADD R1，R2，R3；(R2)+(R3)R1ADD R4，R1，R5；(R1)+(R5)R4A写后读 B读后写 C写后写 D读后读（分数：2.00）A. B.C.D.解析：解析 数据相关包括写后读相关(RAW)、写后写相关(WAW)、读后写相关(WAR)。在这

43、两条指令中，都对 R1进行操作，其中前面对 R1写操作，后面对 R1读操作，因此发生写后读相关。流水线中的相关是指相邻或相近的两条指令因存在某种关联，后一条指令不能按照原指定的时钟周期运行，使流水线断流。指令流水线的相关性包括结构相关、数据相关、控制相关。结构相关也称资源相关，是指由于多条指令在同一时刻争用同一资源而形成的冲突。数据相关是指后续指令要使用前面指令的操作结果，而这一结果尚未产生或者未送到指定的位置，从而造成后续指令无法运行的局面。控制相关又称为指令相关，主要是由转移指令引起的，在遇到条件转移指令时，存在着是顺序执行还是转移执行两种可能，需要依据条件的判断结果来选择其一。数据相关又可分为 RAW(写后读)、WAR(读后写)和 WAW(写后写)3 种类型。例如有 i和 j两条指令，i 指令在前，j 指令在后，则 3种不同类型的数据相关的含义为：R