1、计算机专业（基础综合）-试卷 95 及答案解析(总分：114.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.下列叙述中，正确的是( )。非空循环单链表 head 的尾结点 p 满足 pnext=head带头结点的循环单链表的头指针为 head，如果 headnextnextnext=head 成立，则该单链表的长度为 3静态链表中的指针表示的是下一个元素在数组中的位置将长度为 n 的单链表链接在长度为 m 的单链表之后的算法时间复杂度为 O(1)（分数
2、：2.00）A.仅、B.、C.仅、D.仅、3.利用栈求表达式的值时，设立运算数栈 S。假设栈 S 只有两个存储单元，在下列表达式中，不发生溢出的是( )。（分数：2.00）A.AB*(CD)B.(AB)*CDC.(AB*C)DD.(AB)*(CD)4.设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B 口中，A11存放到 B1中（假定不用 O 下标），那么 Bk存放的元素的行号是( )。（分数：2.00）A.(k+1)/3B.(k+1)/3C.(k+2)/3D.(k+2)/35.已知一棵 5 阶 B树有 53 个关键字并且每个结点的关键字都达到最少状
3、态，则它的深度是( )。（分数：2.00）A.3B.4C.5D.66.下列说法中，正确的是( )。 具有 10 个叶子结点的二叉树中有 9 个度为 2 的结点 设高度为 5的二叉树上只有度为 0 和度为 2 的结点，则该二叉树中所包含的结点数至少为 9 . 棵完全二叉树上有 1 001 个结点，则可知叶子结点的个数为 501 个 高度为 h 的完全二叉树最少有 2 h 个结点（分数：2.00）A.仅、B.仅、C.仅、D.仅、7.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为一 1，右孩子的平衡因子为 O，则为使其平衡，应做( )型调整。（分
4、数：2.00）A.LLB.RRC.RLD.LR8.下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指图中与该顶点连通的顶点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 nl 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分量（分数：2.00）A.仅、B.仅、C.仅D.、9.下列关于强连通图的说法中，正确的是( )。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边.完全有向图一定是强连通图（分数：2.00）A.仅、B.仅、C.仅、D.、10.假设初始为空的散列表的地址空间为(010)，散列函数为 H (key)
5、 =key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、48，则最后一个关键字值 48 的插入位置是( )。（分数：2.00）A.4B.5C.6D.811.设待排序元素序列所有元素的排序码都相等，则下列排序方法中排序速度最慢的是( )。（分数：2.00）A.直接插入排序B.起泡排序C.简单选择排序D.基数排序12.假设有 5 个初始归并段，每个归并段有 20 个记录，采用 5 路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过( )。（分数：2.00）A.20B.300C.396D.50013.下列说法中，错误的是( )。设浮点数的基数为 4
6、，尾数用原码表示，则 0.000 010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（分数：2.00）A.仅、B.仅、C.仅、D.、和14.下列关于定点数原码一位乘法的描述中，错误的是( )。符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位在原码一位乘算法过程中，所有的移位均是算术移位操作假设两个 n 位数进行原码一位乘，部分积至少需要使用 n 位寄存器（分数：2.00）A.仅、B.仅、C.仅、D.、15.某容量为 256MB 的存储器由若干 16Mx8bitDRAM 芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是(
7、 )。（分数：2.00）A.20B.24C.32D.3616.现有64K2bit 的存储器芯片，欲设计具有同样存储容量的存储器，有( )种方法可以合理地安排地址线和数据线引脚的数目，且使两者之和最小。（分数：2.00）A.2B.3C.4D.517.某计算机有 30 个通用寄存器，采用 32 位定长指令字，操作码字段（不含寻址方式）为 8 位，Add 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Add 指令中偏移量的取值范围是( )。（分数：2.00）A.40964095B.20482047C.10231024D.30
8、71307218.与本指令的地址有关的寻址方式是( )。（分数：2.00）A.寄存器寻址B.直接寻址C.相对寻址D.间接寻址19.假定执行最复杂的指令需要完成 6 个子功能，分别由对应的功能部件 AF 来完成，每个功能部件所花的时间分别为 80ns、40ns、50ns、70ns、20ns、30ns，流水线寄存器延时为 20ns，现把最后两个功能部件 E 和 F 合并，以产生一个五段流水线。该五段流水线的时钟周期至少是( )。（分数：2.00）A.70nsB.80nsC.90nsD.100ns20.在微程序控制器中，执行指令微程序的首条微指令地址是由( )得到的。（分数：2.00）A.程序计数器
9、 PCB.前条微指令C.uPC+1D.指令操作码映射21.指令流水线中出现数据相关时流水线将受阻，( )可解决数据相关问题。（分数：2.00）A.增加硬件资源B.采用旁路电路技术C.采用分支预测技术D.AC 都可以22.在计数器定时查询方式下，若每次计数从n/2开始，则( )。（分数：2.00）A.设备号小的优先级高B.每个设备使用总线的机会相等C.设备号大的优先级高D.以上说法都不正确23.以下 4 个步骤在通道过程中的正确顺序是( )。组织 I/O 操作向 CPU 发出中断请求编制通道程序启动 I/O 通道（分数：2.00）A.B.C.D.24.下列关于批处理技术和多道程序设计技术说法中，
10、正确的是( )。批处理系统的最主要缺点是不能并发执行所谓多道程序设计，是指每一个时刻有若干个进程在执行引入多道程序设计的前提条件之一是系统具有中断功能，采用多道程序设计的系统中，系统的程序道数越多，系统的效率越高（分数：2.00）A.仅、B.仅、C.仅D.仅、25.假设系统中所有进程是同时到达，则最不利于短作业的进程调度算法是( )。（分数：2.00）A.FCFSB.SPFC.RRD.高响应比优先26.Pi()Lock（m_mutex）； /含义为获取互斥信号量 a=new int100； /开辟一个大小为 100 的整型数组空间，/并用全局指针变量 a 保存空间地址 UnLock (m_mu
11、tex)；free (a)； /释放数组空间，且 a的值不改变有多个优先级相同的进程 Pi。试问下列同时运行多个进程 Pi，可能会出现的错误是( )。（分数：2.00）A.内存泄露B.内存越界访问C.内存泄露和内存越界访问D.无27.生产者进程和消费者进程代码如下。生产者进程有一个局部变量 nextProduced，以存储新产生的新项：while (1)/*produce an item in nextProduced*/while(in+1) BUFFER SIZE=out)； /*do nothing*/buffer in=nextProduced；in=(in+l) BUFFER SIZ
12、E；.消费者进程有一个局部变量nextConsumed，以存储所要使用的项：while (1)while (in=out)； /*do nothing*/nextConsumed=buffer out；out= (out+1) BUFFER SIZE；/*consume the item in nextConsumed*/当 in=out 和(in+l)BUFFER_SIZE=out 条件成立的时候，缓冲区中 item 数目各是( )。（分数：2.00）A.0，BUFFER_SIZEB.0，BUFFER_SIZE1C.BUFFER_SIZE1，0D.BUFFER_SIZE，028.某操作系统采
13、用可变分区分配存储管理方法，操作系统占用低地址部分的 126KB。用户区大小为386KB，且用户区始址为 126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址的方案，且初始时用户区的 386KB 空间空闲，对下述申请序列：作业 1 申请 80KB，作业 2 申请 56KB，作业 3 申请120KB，作业 1 完成并释放空间，作业 3 完成并释放空间，作业 4 申请 156KB，作业 5 申请 80KB。如果用首次适应算法处理上述序列，最后的空闲分区的首地址为( )。（分数：2.00）A.126B.432C.256D.22029.在分页式系统中，分页由( )实现。（分数：2.00）
14、A.程序员B.编译器C.系统调用D.系统30.在页式虚拟管理系统中，假定驻留集为 m 个页帧（初始所有页帧均为空），在长为 p 的引用串中具有n 个不同页号(nm)，对于 FIFO、LRU 两种页面替换算法，其缺页中断的次数的范围分别为( )。（分数：2.00）A.m，p和n，pB.m，n和n，pC.n，p和m，nD.n，p和n，p31.设有一个记录式文件，采用链接分配方式，逻辑记录的固定长度为 100B，记录类型是英文文本（例如：WelcOmE to TiaNqin!），在磁盘上存储时采用成组分解技术。盘块长度为 512B。如果该文件的目录项已经读入内存，用户现在需要规范第 22 个逻辑记录
15、中的大小写格式，该操作共需启动硬盘的次数为( )。（分数：2.00）A.1B.2C.5D.632.考虑一个有如下参数的磁盘： （分数：2.00）A.4msB.8msC.13msD.17ms33.下列关于设备驱动程序的叙述中，正确的是( )。与设备相关的中断处理过程是由设备驱动程序完成的由于驱动程序与 I/O 设备（硬件）紧密相关，故必须全部用汇编语言书写磁盘的调度程序是在设备驱动程序中运行的一个计算机系统配置了 2 台同类绘图机和 3 台同类打印机，为了正确驱动这些设备，系统应该提供 5 个设备驱动程序（分数：2.00）A.仅、B.仅、C.仅、D.、34.透明网桥的 MAC 地址表要记录的信息
16、有( )。目的站 MAC 地址源站 MAC 地址端口号帧到达时间.帧转发标记（分数：2.00）A.仅、B.仅、C.仅、D.仅、35.下列说法中，错误的是( )。假设帧序号有 3 位，采用连续 ARQ 协议，发送窗口的最大值为4对于窗口大小为 n 的滑动窗口，最多可以有 n 帧已发送但没有确认在后退 N 帧协议中，如果发送窗口的大小是 16，那么至少需要 4 位的序列号才能保证协议不出错（分数：2.00）A.仅、B.仅C.仅、D.、36.假设某网络最远的两个站点长度为 10km，数据传输率为 10Mbit/s 的 CSMA/CS 以太网，信号传播速度为 200m/s。那么该网络的最小帧长为( )
17、。（分数：2.00）A.20bitB.200bitC.100bitD.1000bit37.图 61 是网络地址转换 NAT 的一个实例，根据图 61 中的信息，标号为的方格中的内容应为( )。（分数：2.00）A.S=135.2.1.1，80 D=202.0.1.1，5001B.S=135.2.1.1，80 D=192.168.1.1，3342C.S=202.0.1.1，5001 D=135.2.1.1，80D.S=192.168.1.1，3342 D=135.2.1.1，8038.对于 193100600 网络，若子网掩码设置成 255255255192，则每个子网最多可接入( )台主机。（
18、分数：2.00）A.256B.254C.62D.3039.在 IP 分组的传输过程中，以下 IP 分组首部中的字段保持不变的是( )。总长度头部检验和生存时间源 IP 地址（分数：2.00）A.仅、B.仅C.仅、D.仅、40.有一个 TCP 连接，当其拥塞窗口为 64 个分组大小时超时。假设网络的 RTT 是固定的 3s，不考虑比特开销，即分组不丢失，则系统在超时后处于慢启动阶段的时间是( )。（分数：2.00）A.12sB.15sC.18sD.21s41.某网络允许的最大报文段的长度为 128B，序号用 8bit 表示，报文段在网络中的寿命为 30s，则每一条TCP 连接所能达到的最高数据率
19、为( )。（分数：2.00）A.46kbit/sB.189kbit/sC.87kbit/sD.256kbit/s二、综合应用题(总题数：8，分数：32.00)42.综合应用题 41-47 小题。_求解下面有向图的有关问题。 （分数：6.00）(1).判断此有向图是否有强连通分量？若有，请画出。（分数：2.00）_(2).画出此图的十字链表存储结构。（分数：2.00）_(3).简述基于图的深度优先搜索策略，并判别一个以邻接表存储的有向图是否存在顶点 Vi 到顶点 Vj 的路径的基本步骤。（分数：2.00）_假设有一带头结点的循环双链表表示的线性表 L=(a 1 ，a 2 ，aa n1 ，a n
20、)。设计在时间和空间上都尽可能高效的算法，将线性表 L 改造成 L=(a 1 ，a 3 ，a n ，a 4 ，a 2 )。要求：（分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度与空间复杂度。（分数：2.00）_假设某计算机所有指令都可用两个总线周期完成，一个总线周期用来取指令，另一个总线周期用来存取数据。假定总线宽度为 8 位，每个总线周期为 250ns，因而每条指令的执行时间为 500ns，若该计算机中配置的磁盘每个磁道有 16
21、个 512 字节的扇区，磁盘旋转一圈的时间是 8192ms。请回答下列问题：（分数：6.00）(1).在磁盘不工作时，主存频带空闲百分比是多少？（分数：2.00）_(2).若采用周期挪用法进行 DMA 传送，则该计算机执行指令的速度由于 DMA 传送而降低了多少？（分数：2.00）_(3).若采用周期挪用法进行 DMA 传送，总线宽度为 16 位，则该计算机执行指令的速度由于 DMA 传送而降低了多少？（分数：2.00）_某微程序计算机具有 12 条微指令 V1V12，每条微指令所包含的微命令信号如表 82 所示。 （分数：6.00）(1).采用“不译法”与“分段直接编码法”混合设计此机微指令
22、的操作控制字段格式，并为每个微命令分配编码；（分数：2.00）_(2).采用“增量”与“下址字段”相结合的方式设计此机微指令的顺序控制字段格式，若要使微程序可在整个控存空间实现转移，则该微指令的顺序控制字段可直接表示出多少个转移条件。（分数：2.00）_(3).画出此机微指令的完整格式图，并标出每个具体字段所需的二进制位数。（分数：2.00）_43.给出一个单车道的简易桥，如图 84 所示。 （分数：2.00）_设正在处理器上执行一个进程的页表如表 83 所示。表中的虚页号和物理块号是十进制数，起始页号（块号）均为 0。所有的地址均是存储器字节地址。页的大小为 1024B。若发生缺页中断，使用
23、 LRU 页面置换算法将缺页调入再进行地址变换，页表中访问字段记录本页最近已有多长时间未被访问。 （分数：4.00）(1).详述在设有快表的请求分页存储器管理系统中，一个虚地址转换成物理内存地址的过程。（分数：2.00）_(2).根据给出的某进程的页表，系统给该进程分配的最大内存物理块数为 3，进程先后使用下面两个虚地址访问内存，其对应的物理内存地址分别是多少？请详述整个地址变换过程，并参照给出的页表，画出每次操作后的页表。（注：访问字段表示的是该页最近已有多长时间未被访问）a) 4475（写操作）b）1197（读操作）（分数：2.00）_44.设有 4 台主机 A、B、C 和 D 都处在同一
24、物理网络中，它们的 IP 地址分别为19215528112、19215528120、19215528135 和 19215528202，子网掩码都是255255255224请回答：(1)该网络的 4 台主机中哪些可以直接通信？哪些需要通过设置路由器才能通信？请画出网络连接示意图，并注明各个主机的子网地址和主机地址。(2)若要加入第 5 台主机 E，使它能与主机 D 直接通信，则其 IP 地址的范围是多少？(3)若不改变主机 A 的物理位置，而将其 IP 改为19215528168，则它的直接广播地址和本地广播地址各是多少？若使用本地广播地址发送信息，请问哪些主机能够收到？(4)若要使该网络中的
25、 4 台主机都能够直接通信，可采取什么办法？（分数：2.00）_计算机专业（基础综合）-试卷 95 答案解析(总分：114.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下列叙述中，正确的是( )。非空循环单链表 head 的尾结点 p 满足 pnext=head带头结点的循环单链表的头指针为 head，如果 headnextnextnext=head 成立，则该单链表的长度为 3静态链表中的指针表示的是下一个元素在数组中的位置将长度为 n 的单
26、链表链接在长度为 m 的单链表之后的算法时间复杂度为 O(1)（分数：2.00）A.仅、B.、C.仅、 D.仅、解析：解析：非空循环单链表的尾结点指针应该指向链表头，即 pnext=head，故 I 正确。 : head 指向头结点，headnext 就指向第一个结点。既然 headnextnextnext=head，说明此循环链表共有 3 个结点（包含头结点），而单链表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存储线性表的元素，故不能算为单链表结点，故此单链表的长度为 2，故错误。 ：静态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的位置，即数组下标，故正
27、确。 ：将链表连接起来只需 O(1)的操作，但找到具有 m 个结点链表的尾结点需遍历该链表，所以时间复杂度应该为 O(m)，故错误。3.利用栈求表达式的值时，设立运算数栈 S。假设栈 S 只有两个存储单元，在下列表达式中，不发生溢出的是( )。（分数：2.00）A.AB*(CD)B.(AB)*CD C.(AB*C)DD.(AB)*(CD)解析：解析：利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一例。例如，求 2(53)+6/2 的过程如表 62 所示。4.设有一个 n 阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B 口中，A11存放到 B1中（假
28、定不用 O 下标），那么 Bk存放的元素的行号是( )。（分数：2.00）A.(k+1)/3B.(k+1)/3 C.(k+2)/3D.(k+2)/3解析：解析：这种题目最好采用特殊值法，推导过程可能比较繁琐，见表 63。5.已知一棵 5 阶 B树有 53 个关键字并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4 C.5D.6解析：解析：根据 B树定义，m 阶 B树除根结点之外，所有非终端结点至少有m/2=3 个子树，即至少有 2 个关键字。那么在每个结点的关键字最少的情况下，根结点关键字个数为 1，其他的结点关键字个数都为 2。又第一层有 1 个结点，第二
29、层有 2 个结点，第三层有 23 个结点，第四层有 233 个结点。即：11+22+232+2332=53，根结点加非终端刚好四层，叶子结点那一层不算，故树的深度为 4。6.下列说法中，正确的是( )。 具有 10 个叶子结点的二叉树中有 9 个度为 2 的结点 设高度为 5的二叉树上只有度为 0 和度为 2 的结点，则该二叉树中所包含的结点数至少为 9 . 棵完全二叉树上有 1 001 个结点，则可知叶子结点的个数为 501 个 高度为 h 的完全二叉树最少有 2 h 个结点（分数：2.00）A.仅、B.仅、C.仅、D.仅、 解析：解析：二叉树叶子结点的个数比度为 2 的结点的个数多 1，故
30、 I 正确。 总结：这个性质在选择题中常有体现（见下面的补充例题），并且需要灵活运用。比如题目可能问，二叉树中总的结点数为n，则树中空指针的个数是多少？我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加 1，即 n+1 个。 这个性质还可以扩展，即在一棵度为 m 的树中，度为 1 的结点数为 n 1 ，度为 2 的结点数为 n2度为 m 的结点数为 n m ，则叶子结点数 n 0 =1+n 2 +2n 3 +(m1)n m 。推导过程如下： 总结点=n 0 +n 1 +n 2 +n 3 +n m ， 总分支数=1n 1 +2n
31、2 +mn m （度为 m 的结点引出 m 条分支） 总分支数=总结点数一 1 将式和式代入式并化简得 n 0 =1+n 2 +2n 3 +(m1)n m 补充例题：在一棵二叉树中度为 0 的结点个数为 k，度为 1 的结点个数为 m，则该二叉树采用二叉链存储结构时，有( )个指针指向孩子结点。 Ak Bm C2k+m2 D2k+m C.本题考查树的链式存储结构。 首先，由二叉树的性质可知，n 0 =n 2 +1（多次用到，考生一定要记住！），得到 n 2 =k1。其次，二叉树的结点总数 n=n 0 +n 1 +n 2 =2k+m1。求指向孩子结点的指针个数其实就是求该二叉树的分支数，而分支数
32、就是等于总结数一 1，所以答案为 2k+m2，故选 C 选项。 ：最少结点的情况应该是除根结点层只有 1 个结点外，其余 4 层都有 2 个结点，因此结点总数为 2(51) +1=9。如图 64 所示，故正确。 7.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为一 1，右孩子的平衡因子为 O，则为使其平衡，应做( )型调整。（分数：2.00）A.LLB.RRC.RLD.LR 解析：解析：既然最低不平衡结点是 A，则以 A 为根的子树不平衡的情况有 4 种，如图 65 所示。8.下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指
33、图中与该顶点连通的顶点数在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 nl 条边无向图的邻接矩阵是对称矩阵具有 n 个顶点的无向图，最多有 n 个连通分量（分数：2.00）A.仅、B.仅、 C.仅D.、解析：解析：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数（这样就会扩大范围，如图 66 所示），故错误。 9.下列关于强连通图的说法中，正确的是( )。n 个顶点构成的强连通图至少有 n 条边强连通图是任何顶点到其他所有顶点都有边.完全有向图一定是强连通图（分数：2.00）A.仅、B.仅、C.仅、 D.、解析：解析：强连通
34、图是相对于有向图而言的，即在有向图 G 中，任何两个顶点都存在路径。所以最少的情况应该是 n 个顶点构成一个首尾相连的环，共有 n 条边，故 I 正确。 :这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。有向图中顶点 A 和 B 之间存在边，不能说明 A 和 B 是互相连通的，所以说正确的表述应该是强连通图是任何顶点到其他所有顶点都有路径，故错误。 ：完全有向图肯定是任何顶点到其他所有顶点都有路径，故正确。10.假设初始为空的散列表的地址空间为(010)，散列函数为 H (key) =key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、
35、48，则最后一个关键字值 48 的插入位置是( )。（分数：2.00）A.4B.5C.6 D.8解析：解析：首先通过散列函数 H(key) =key mod 11 的计算得知，37、95、27、14 分别插入到散列表中的 4、7、5、3 的位置。而 48 mod 11=4，但是此时 4 已经有元素了，根据线性探测再散列法处理冲突的原则，依次探测位置 4 的下一个地址，直到此地址为空，发现 6 为空则插入，故选 C 选项。 补充：如果此题改为使用平方探测法，则又应该选择哪一个选项？ 解析：平方探测法的原理是设发生冲突的地址为d，则平方探测法的探测序列为 d+12，d_12，d+22，d_22，。
36、位置 4 不空时，下一个探测的位置应该为5，发现又不空，则下一个探测的位置应该是 3，发现又不空。接着再探测位置 8，发现为空，将元素插入，故选 D 选项。 平方探测法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。11.设待排序元素序列所有元素的排序码都相等，则下列排序方法中排序速度最慢的是( )。（分数：2.00）A.直接插入排序B.起泡排序C.简单选择排序 D.基数排序解析：解析：当所有待排序元素的排序码都相等时，直接插入排序的排序码比较次数为 n1，元素移动次数为 0；起泡排序的排序码比较次数为 n1，元素移动个数为 0
37、；简单选择排序的排序码比较次数为n(n1)/2，元素移动次数为 0；基数排序采用静态链表存储待排序元素，用于分配的桶亦采用链式队列，排序码比较次数为 nd（d 是排序码位数），元素移动次数为 0，故排序速度最慢的是简单选择排序。12.假设有 5 个初始归并段，每个归并段有 20 个记录，采用 5 路平衡归并排序，若采用败者树的方法，总的排序码比较次数不超过( )。（分数：2.00）A.20B.300 C.396D.500解析：解析：假设采用 k 路平衡归并排序算法，则败者树的高度为log 2 k+1。在每次调整后，找下一个具有最小排序码记录时，最多做log 2 次排序码比较。由题意可知，总共有
38、 100 个记录，所以总的比较次数不超过 100log 2 5=300。 注意：采用败者树进行 k 路平衡归并的外部排序算法，其总的归并效率与 k 无关。13.下列说法中，错误的是( )。设浮点数的基数为 4，尾数用原码表示，则 0.000 010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（分数：2.00）A.仅、B.仅、C.仅、 D.、和解析：解析：对于原码表示的基值为 4 的小数，规格化的形式是小数点后 2 位不全为 0，故 I 错误。 最笨的解题思路：基数 r=4，由于 1/r|M|1，即尾数的十进制绝对值在 0.251 之间
39、。而(0.000 010) 2 =0.031 25，故不是规格化数。 ：浮点数的溢出并不是由尾数来判断的，而是规格化后阶码超出所能表示的范围时，才表示溢出，故错误。 :在浮点数的运算过程中，尾数如果出现 01.XXXX 和10.XXXX，则需要进行右规，并且只需进行一次右规尾数就会变成规格化数，但是左规操作可能不止一次，故正确。14.下列关于定点数原码一位乘法的描述中，错误的是( )。符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位在原码一位乘算法过程中，所有的移位均是算术移位操作假设两个 n 位数进行原码一位乘，部分积至少需要使用 n 位寄存器（分数：2.00）A.仅、B.仅、C.
40、仅、D.、 解析：解析：在原码一位乘算法过程中，符号位是不参加运算的，结果的符号位是被乘数的符号位和乘数的符号位异或的结果，故错误。 :在原码一位乘算法过程中，由于参与操作的数是真值的绝对值，所以没有正负可言，故在原码一位乘法中运算过程中所有的移位均是逻辑移位操作，即在高位添加 0，故错误。 ：由于在部分积相加中，可能导致两个小数相加大于 1，所以部分积至少需要使用 n+1 位寄存器，故错误。15.某容量为 256MB 的存储器由若干 16Mx8bitDRAM 芯片构成，该 DRAM 芯片的地址引脚和数据引脚总数是( )。（分数：2.00）A.20 B.24C.32D.36解析：解析：很多不了
41、解 DRAM 引脚结构的同学很可能会得出 24+8=32 的结果，其实这是不正确的，在高分笔记当中讲过半导体存储芯片的译码驱动方式，其中介绍了重合法，将存储单元分成行和列，然后分别通过行地址线和列地址线来确定行列地址从而确定一个单元，这里 DRAM 采用引脚复用，将行地址线和列地址线合用作一组，只不过在译码时，需要发送两次地址信号（相当于一次行地址，一次列地址），从而减少了 DRAM 的引脚总数，便于设计 DRAM；因此这里地址空间是 16M，需要 24 个地址位来标识，分为两次发送，则地址引脚数为 12，故地址引脚和数据引脚总数为 12+8=20。 【总结】DRAM 芯片采用引脚复用，且行列
42、地址位数一致。16.现有64K2bit 的存储器芯片，欲设计具有同样存储容量的存储器，有( )种方法可以合理地安排地址线和数据线引脚的数目，且使两者之和最小。（分数：2.00）A.2 B.3C.4D.5解析：解析：不妨设地址线和数据线的数目分别为 x 和 y。 只需要满足 2 x y=64K2，所以就有如下方案： 当 y=1 时，x=17； 当 y=2 时，x=16； 当 y=4 时，x=15； 当 y=8 时，x=14； 后面的就不要计算了，肯定比前面的引脚数目多。从以上分析可以出看，当数据线分别为 1 或 2 时，地址线和数据线引脚的数目之和为 18，达到最小，并且有两种解答。17.某计算机有 30 个通用寄存器，采用 32 位定
