1、计算机专业（基础综合）模拟试卷 107及答案解析(总分：124.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.A-B*(C-D)B.(A-B)*C-DC.(A-B*C)-DD.(A-B)*(C-D)4.设有一个 n阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B中，A11存放到 B1中(假定不用 0下标)，那么 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 一棵完全二叉树上有 1001个结点，则可知叶子结点的个数为 501个 高度为 h的完全二叉树最少有 2h个结点（分数：2.00）A.仅、B.仅、C.仅、D.仅、7.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则为使其平衡，应做( )型调整。（分数：2.00）A.LLB.RR
4、C.RLD.LR8.下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指图中与该顶点连通的顶点数在一个具有 n个顶点的无向图中，要连通全部顶点至少需要 n-1条边无向图的邻接矩阵是对称矩阵具有 n个顶点的无向图，最多有 n个连通分量（分数：2.00）A.仅、B.仅、C.仅D.、9.下列关于强连通图的说法中，正确的是( )。n 个顶点构成的强连通图至少有 n条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图（分数：2.00）A.仅、B.仅、C.仅、D.、10.假设初始为空的散列表的地址空间为(010)，散列函数为 H(key)=key mod 11，采用线性探测再散列
5、法处理冲突，若依次插入关键字 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，尾数用原码表示，则 0000010 为规格化数浮点
6、数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（分数：2.00）A.仅、B.仅、C.仅、D.、和14.已知两个正浮点数，N 1 =2 j1 S，N 2 =2 j2 S 2 ，当下列( )成立时，N 1 N 2 。（分数：2.00）A.S 1 S 2B.j 1 j 2C.S 1 并 S 2 均为规格化数，且 j 1 j 2D.S 1 和 S 2 均为规格化数，且 S 1 S 215.某容量为 256MB的存储器由若干 16M8bitDRAM芯片构成，该 DRAM芯片的地址引脚和数据引脚总数是( )。（分数：2.00）A.20B.24C.32D.3616.
7、现有一 64K2bit的存储器芯片，欲设计具有同样存储容量的存储器，有( )种方法可以合理地安排地址线和数据线引脚的数目，且使两者之和最小。（分数：2.00）A.2B.3C.4D.517.某计算机有 30个通用寄存器，采用 32位定长指令字，操作码字段(不含寻址方式)为 8位，Add 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则 Add指令中偏移量的取值范围是( )。（分数：2.00）A.-40964095B.-20482047C.-10231024D.-3071307218.与本指令的地址有关的寻址方式是( )。（分
8、数：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.程序计数器 PCB.前条微指令C.UPC+1D.指令操作码映射21.指令流水
9、线中出现数据相关时流水线将受阻，( )可解决数据相关问题。（分数：2.00）A.增加硬件资源B.采用旁路电路技术C.采用分支预测技术D.AC 都可以22.在计数器定时查询方式下，若每次计数从n2开始，则( )。（分数：2.00）A.设备号小的优先级高B.每个设备使用总线的机会相等C.设备号大的优先级高D.以上说法都不正确23.以下 4个步骤在通道过程中的正确顺序是( )。组织 IO 操作向 CPU发出中断请求编制通道程序启动 IO 通道（分数：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_mutex)； free(a)； 释放数组空间，且 a的值不改变 有多个优先级相同的进程
11、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* bufferin=nextProduced； in=(in+1)BUFFER_SIZE； 消费者进程有一个局部变量nextConsumed，以存储所要使用的项：while(1) w
12、hile(in=out)；*do nothing* nextConsumed=bufferout； out=(out+1)BUFFER SIZE； *consume the item in nextConsumed* 当 in=out和(in+1)BUFFER_SIZE=out 条件成立的时候，缓冲区中 item数目各是( )。（分数：2.00）A.0，BUFFER_SIZEB.0，BUFFER_SIZE-1C.BUFFER_SIZE-1，0D.BUFFER_SIZE，028.某操作系统采用可变分区分配存储管理方法，操作系统占用低地址部分的 126KB。用户区大小为386KB，且用户区始址为
13、126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址的方案，且初始时用户区的 386KB空间空闲，对下述申请序列：作业 1申请 80KB，作业 2申请 56KB，作业 3申请120KB，作业 1完成并释放空间，作业 3完成并释放空间，作业 4申请 156KB，作业 5申请 80KB。如果用首次适应算法处理上述序列，最后的空闲分区的首地址为( )。（分数：2.00）A.126B.432C.256D.22029.在分页式系统中，分页由( )实现。（分数：2.00）A.程序员B.编译器C.系统调用D.系统30.在页式虚拟管理系统中，假定驻留集为 m个页帧(初始所有页帧均为空)，在长为
14、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个逻辑记录中的大小写格式，该操作共需启动硬盘的次数为( )。（分数：2.00）A.1B.2C.5D.632.考虑一个有如下参数的磁盘： （
15、分数：2.00）A.4msB.8msC.13msD.17ms33.如果 IO 所花费的时间比 CPU的处理时间短得多，则缓冲区( )。（分数：2.00）A.最有效B.几乎无效C.均衡D.以上都不是34.透明网桥的 MAC地址表要记录的信息有( )。目的站 MAC地址 源站 MAC地址端口号帧到达时间帧转发标记（分数：2.00）A.仅、B.仅、C.仅、D.仅、35.下列说法中，错误的是( )。假设帧序号有 3位，采用连续 ARQ协议，发送窗口的最大值为4对于窗口大小为 n的滑动窗口，最多可以有 n帧已发送但没有确认在后退 N帧协议中，如果发送窗口的大小是 16，那么至少需要 4位的序列号才能保证
16、协议不出错（分数：2.00）A.仅、B.仅C.仅、D.、36.假设某网络最远的两个站点长度为 10km，数据传输率为 10Mbits 的 CSMACS 以太网，信号传播速度为 200ms。那么该网络的最小帧长为( )。（分数：2.00）A.20bitB.200bitC.100bitD.1000bit37.图 6-1是网络地址转换 NAT的一个实例，根据图 6-1中的信息，标号为的方格中的内容应为( )。（分数：2.00）A.S=135211，80B.S=135211，80 D=202011，5001 D=19216811，3342C.S=202011，5001D.S=19216811，3342
17、 D=135211，80 D=135211，8038.对于 193100600 网络，若子网掩码设置成 255255255192，则每个子网最多可接入( )台主机。（分数：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.18s
18、D.21s41.某网络允许的最大报文段的长度为 128B，序号用 8bit表示，报文段在网络中的寿命为 30s，则每一条TCP连接所能达到的最高数据率为( )。（分数：2.00）A.46kbitsB.189kbitsC.87kbitsD.256kbits二、综合应用题(总题数：9，分数：42.00)42.综合应用题 41-47小题。_设哈希函数为：H(key)=key mod 13，其中 key为关键字，mod 为取模运算，试用关键字序列39，25，15，54，26，24，14，21，37，38构造哈希表。（分数：4.00）(1).用链地址法处理冲突，画出该哈希表的存储结构图，假定每个记录的查
19、找概率相等，计算查找成功时的平均查找长度。（分数：2.00）_(2).设表地址范围为 013，用线性探测再散列法处理冲突，画出该哈希表的存储结构图，假定每个记录的查找概率相等，计算查找成功时的平均查找长度。（分数：2.00）_输入一整数数组5，7，6，9，11，10，8，该整数序列为图 2-2所示的二叉排序树的后序遍历序列。请实现一个时间上尽可能高效率的算法，判断某一输入整数数组是否为某二叉排序树的后序遍历的结果。如果是返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。要求： （分数：6.00）(1).给出算法的基本设计思想。（分数：2.00）_(2).根据设计思想
20、，采用 C、C+或 Java语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度。（分数：2.00）_某字长为 8位的计算机中，带符号整数采用补码表示，x=-68，y=-80，x 和 v分别存放在寄存器 A和 B中，请回答下列问题(最终要求用十六进制表示二进制序列)。（分数：8.00）(1).寄存器 A和 B中的内容分别是什么?（分数：2.00）_(2).若 x和 y相加后的结果存放在寄存器 C中，则寄存器 C中的内容是什么?运算结果是否正确?此时，溢出标志 OF、符号标志 SF和零标志 ZF各是什么?加法器最高位的进位 C n 是什么?（分数：2.00）_
21、(3).若 x和 y相减后的结果存放在寄存器 D中，则寄存器 D中的内容是什么?运算结果是否正确?此时，溢出标志 OF、符号标志 SF和零标志 ZF各是什么?加法器最高位的进位 C n 是什么?（分数：2.00）_(4).若将加法器最高位的进位 Cn作为进位标志 CF，能否直接根据 CF的值对两个带符号整数的大小进行比较?（分数：2.00）_假定一个计算机系统中有 1个 TLB和 1个 L1 Data Cache。该系统按字节编址，虚拟地址 16位，物理地址 12位，页大小为 128B，TLB 为 4路组相连，共有 16个页表项，L1 Data Cache 采用直接映射方式，块大小为 4B，共
22、 16行。在系统运行到某一时刻时，TLB、页表和 L1 Data Cache中的部分内容如图 2-3所示。 （分数：8.00）(1).虚拟地址中哪几位表示虚拟页号?哪几位表示页内偏移量?虚拟页号中哪几位表示 TLB标记?哪几位表示 TLB索引?（分数：2.00）_(2).物理地址中哪几位表示物理页号?哪几位表示页内偏移量?（分数：2.00）_(3).主存(物理)，地址如何划分成标记字段、行索引字段和块内地址字段?（分数：2.00）_(4).CPU从地址 067AH 中取出的值为多少?说明 CPU读取地址 067AH中内容的过程。（分数：2.00）_在单 CPU和两台输入输出设备(11，12)的
23、多道程序设计环境下，同时投入 3个作业 J1、J2 和 J3运行。这 3个作业对 CPU和输入输出设备的使用顺序和时间如下所示。 J1：12(30ms)；CPU(10ms)；11(30ms)；CPU(10ms)；12(20ms) J2：11(20ms)；CPU(20ms)；12(40ms) J3：CPU(30ms)；11(20ms)；CPU(10ms)；11(10ms) 假定 CPU、11、12 都能并行工作，J1 优先级最高，J2 次之，J3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 11和 12。试求：（分数：6.00）(1).3个作业从投入到完成分别需要的时间
24、。（分数：2.00）_(2).从投入到完成的 CPU利用率。（分数：2.00）_(3).IO 设备利用率。（分数：2.00）_下列程序实现了矩阵乘法。int A100150；int B150200；int Ci00200；for(i=0；i100，i+) for(j=0；j200；j+) for(k=0；k150；k+) Cij+=Aik*Bkj； 假设矩阵 A和矩阵 B的初值已经初始化过，矩阵 C初始化为 0，各矩阵均以页为单位连续存放(且假定是行优先存储)。又假定一个整数占用 1个字，代码以及变量 i、j 和 k存放在其他页面里，并且存取变量i、j 和 k时不存在缺页问题。主存初始为空，在
25、请求分页存储管理中，页面淘汰算法为 FIFO。（分数：4.00）(1).作业分配 10个页面，每个页面为 100字，给矩阵 A、B 和 C使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10个页面各属于哪些矩阵?（分数：2.00）_(2).当作业分配两个页面，每个页面为 500字，给矩阵 A、B 和 C使用。问执行上面的程序时，缺页次数是多少?当执行完程序时，留在内存的 10个页面各属于哪些矩阵? (注：c+=c+a*b 的执行顺序为：读 a、读 b、计算 ab、读 c、计算 c+ab、写 c)（分数：2.00）_43.假设主机 1(在图 2-4中网络 1以太网上)是可以
26、运行 IE浏览器的某客户机，主机 4(在图 2-4中网络 3以太网上)为天勤论坛 Web服务器(IP 地址为 202197115)，主机 5(在图 2-4中网络 2的 FDDI主干网上)为天勤论坛 DNS服务器，该 DNS服务器上有天勤论坛 Web站点的域名地址到 IP地址解析。其中，路由器 1以太网端口(a 端口)的 MAC地址是 E3，IP 地址是 202197123，子网掩码是2552552550；路由器 1的 FDDI端口(c 端口)的 MAC地址是 F1，IP 地址是 202197101，子网掩码是 2552552550。路由器 2的以太网端口(b 端口)的 MAC地址是 E4，IP
27、 地址是202197114，子网掩码是 2552552550；路由器 2的 FDDI端口(c 端口)的 MAC地址是 F3，IP地址是 202197102，子网掩码是 2552552550，其他站点的 IP地址和 MAC地址如图 2-4所示。试问： 为了使主机 1能够通过域名访问天勤论坛 Web服务器，主机 1上的 IP地址、子网掩码、默认网关 IP地址、DNS 服务器地址应该如何配置?（分数：2.00）_假设主机 1使用的 1234的 UDP端口与 DNS服务器通信，使用的 1235的 TCP端口与 Web服务器通信，请写出主机 1发给 DNS服务器和 Web服务器的 UDP报文和 TCP报
28、文中的源端口号和目的端口号、IP 报文中的源 IP地址和目的 IP地址以及在 3个物理网络中发送的 MAC帧中的源 MAC地址和目的 MAC地址。（分数：4.00）_(2).从(2)的分析中，得出了什么结论?请阐述。（分数：2.00）_计算机专业（基础综合）模拟试卷 107答案解析(总分：124.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.下列叙述中，正确的是( )。 非空循环单链表 head的尾结点 p满足 pnext=head 带头结点的循环
29、单链表的头指针为 head，如果 headnextnextnext=head 成立，则该单链表的长度为 3 静态链表中的指针表示的是下一个元素在数组中的位置 将长度为 n的单链表链接在长度为 m的单链表之后的算法时间复杂度为 O(1)（分数：2.00）A.仅、B.、C.仅、 D.仅、解析：解析：非空循环单链表的尾结点指针应该指向链表头，即 pnext=head，故正确。 ：head 指向头结点，headnext 就指向第一个结点。既然 headnextnextnext=head，说明此循环链表共有 3个结点(包含头结点)，而单链表中增加头结点仅仅是为了更方便地进行插入和删除操作，它并不存储线性
30、表的元素，故不能算为单链表结点，故此单链表的长度为 2，故错误。 ：静态链表中的指针所存储的不再是链表中的指针域，而是其下一个结点在数组中的位置，即数组下标，故正确。 ：将链表连接起来只需 O(1)的操作，但找到具有 m个结点链表的尾结点需遍历该链表，所以时间复杂度应该为 O(m)，故错误。3.利用栈求表达式的值时，设立运算数栈 S。假设栈 S只有两个存储单元，在下列表达式中，不发生溢出的是( )。（分数：2.00）A.A-B*(C-D)B.(A-B)*C-D C.(A-B*C)-DD.(A-B)*(C-D)解析：解析：利用栈求表达式的值时，需要设立运算符栈和运算数栈，下面仅举一例。例如，求
31、2(5-3)+62 的过程如表 6-2所示。4.设有一个 n阶三对角线矩阵 Ann，现把它的三条对角线上的非零元素按行存放到一个一维数组 B中，A11存放到 B1中(假定不用 0下标)，那么 Bk存放的元素的行号是( )。（分数：2.00）A.(k+1)3B.(k+1)3 C.(k+2)3D.(k+2)3解析：解析：这种题目最好采用特殊值法，推导过程可能比较繁琐，见表 6-3。5.已知一棵 5阶 B-树有 53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是( )。（分数：2.00）A.3B.4 C.5D.6解析：解析：根据 B-树定义，m 阶 B-树除根结点之外，所有非终端结点至少
32、有m2=3 个子树，即至少有 2个关键字。那么在每个结点的关键字最少的情况下，根结点关键字个数为 1，其他的结点关键字个数都为 2。又第一层有 1个结点，第二层有 2个结点，第三层有 23个结点，第四层有 233个结点。即：11+22+232+2332=53，根结点加非终端刚好四层，叶子结点那一层不算，故树的深度为4。6.下列说法中，正确的是( )。 具有 10个叶子结点的二叉树中有 9个度为 2的结点 设高度为 5的二叉树上只有度为 0和度为 2的结点，则该二叉树巾所包含的结点数至少为 9 一棵完全二叉树上有 1001个结点，则可知叶子结点的个数为 501个 高度为 h的完全二叉树最少有 2
33、h个结点（分数：2.00）A.仅、B.仅、C.仅、D.仅、 解析：解析：二叉树叶子结点的个数比度为 2的结点的个数多 1，故 I正确。 总结：这个性质在选择题中常有体现，并且需要灵活运用。比如题目可能问，二叉树中总的结点数为 n，则树中空指针的个数是多少?我们可以将所有的空指针看作叶子结点，则图中原有的所有结点都成了双分支结点。因此可得空指针域的个数为树中所有结点个数加 1，即 n+1个。 这个性质还可以扩展，即在一棵度为 m的树中，度为 1的结点数为 n 1 ，度为 2的结点数为 n 2 度为 m的结点数为 n m ，则叶子结点数 n 0 =1+n 2 +2n 3 +(m-1)n m 。推导
34、过程如下： 总结点=-n 0 +n 1 +n 2 +n 3 +n m 总分支数=1n 1 +2n 2 +mn m (度为 m的结点引出 m条分支) 总分支数=总结点数-1 将式和式代入式并化简得 n 0 =1+n 2 +2n 3 +(m-1)n m ：最少结点的情况应该是除根结点层只有 1个结点外，其余4层都有 2个结点，因此结点总数为 2(5-1)+1=9。如图 6-4所示，故正确。 7.在平衡二叉树中插入一个结点就造成了不平衡，设最低的不平衡结点为 A，并已知 A的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则为使其平衡，应做( )型调整。（分数：2.00）A.LLB.RRC.RLD.
35、LR 解析：解析：既然最低不平衡结点是 A，则以 A为根的子树不平衡的情况有 4种，如图 6-5所示。8.下列关于无向图的说法中，正确的是( )。无向图中某个顶点的度是指图中与该顶点连通的顶点数在一个具有 n个顶点的无向图中，要连通全部顶点至少需要 n-1条边无向图的邻接矩阵是对称矩阵具有 n个顶点的无向图，最多有 n个连通分量（分数：2.00）A.仅、B.仅、 C.仅D.、解析：解析：无向图顶点的度即为一个顶点所引出边的条数，等价于一个顶点所含有的邻接顶点的个数，而不是与该顶点连通的顶点数(这样就会扩大范围，如图 6-6所示)，故错误。 9.下列关于强连通图的说法中，正确的是( )。n 个顶
36、点构成的强连通图至少有 n条边强连通图是任何顶点到其他所有顶点都有边完全有向图一定是强连通图（分数：2.00）A.仅、B.仅、C.仅、 D.、解析：解析：强连通图是相对于有向图而言的，即在有向图 G中，任何两个顶点都存在路径。所以最少的情况应该是 n个顶点构成一个首尾相连的环，共有 n条边，故正确。 ：这个选项不细心的话很容易误选。在有向图中，边和路径是不同的概念。有向图中顶点 A和 B之间存在边，不能说明 A和 B是互相连通的，所以说正确的表述应该是强连通图是任何顶点到其他所有顶点都有路径，故错误。 ：完全有向图肯定是任何顶点到其他所有顶点都有路径，故正确。10.假设初始为空的散列表的地址空
37、间为(010)，散列函数为 H(key)=key mod 11，采用线性探测再散列法处理冲突，若依次插入关键字 37、95、27、14、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选项。11.设待排序元素序列所有元素的排序码都相等，则下列排
38、序方法中排序速度最慢的是( )。（分数：2.00）A.直接插入排序B.起泡排序C.简单选择排序 D.基数排序解析：解析：当所有待排序元素的排序码都相等时，直接插入排序的排序码比较次数为 n-1，元素移动次数为 0；起泡排序的排序码比较次数为 n-1，元素移动个数为 0；简单选择排序的排序码比较次数为 n(n-1)2，元素移动次数为 0；基数排序采用静态链表存储待排序元素，用于分配的桶亦采用链式队列，排序码比较次数为 nd(d是排序码位数)，元素移动次数为 0，故排序速度最慢的是简单选择排序。12.假设有 5个初始归并段，每个归并段有 20个记录，采用 5路平衡归并排序，若采用败者树的方法，总的
39、排序码比较次数不超过( )。（分数：2.00）A.20B.300 C.396D.500解析：解析：假设采用 k路平衡归并排序算法，则败者树的高度为log 2 k+1。在每次调整后，找下一个具有最小排序码记录时，最多做log 2 k次排序码比较。由题意可知，总共有 100个记录，所以总的比较次数不超过 100log 2 5=300。13.下列说法中，错误的是( )。设浮点数的基数为 4，尾数用原码表示，则 0000010 为规格化数浮点数运算中，运算结果超出尾数表示范围则表示溢出任何情况下，浮点数的右规操作最多只会进行一次（分数：2.00）A.仅、B.仅、C.仅、 D.、和解析：解析：对于原码表
40、示的基值为 4的小数，规格化的形式是小数点后 2位不全为 0，故错误。 ：浮点数的溢出并不是由尾数来判断的，而是规格化后阶码超出所能表示的范围时，才表示溢出，故错误。 ：在浮点数的运算过程中，尾数如果出现 01XXXX 和 10XXXX，则需要进行右规，并且只需进行一次右规尾数就会变成规格化数，但是左规操作可能不止一次，故正确。14.已知两个正浮点数，N 1 =2 j1 S，N 2 =2 j2 S 2 ，当下列( )成立时，N 1 N 2 。（分数：2.00）A.S 1 S 2B.j 1 j 2C.S 1 并 S 2 均为规格化数，且 j 1 j 2 D.S 1 和 S 2 均为规格化数，且 S 1 S 2解析：解析：S 1 和 S 2 均为规格化数，12S 1 1，12S 2 1，即 S 1 12S 2 2。 j 1 j 2 ，即 j 1 j 2 +1。N 1 =2 j1 S 1 2 j2+1 S 2 2=2 j2 S 2 =N 2 。15.某容量为 256MB的存储器由若干 16M8bitDRAM芯片构成，该 DRAM芯片的地址引脚和数
