1、计算机专业（基础综合）模拟试卷 103 及答案解析(总分：122.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.下列说法中，正确的是( )。 假设某有序表的长度为 n，则可以在 1-(n+1)的位置上插入元素 在单链表中，无论是插入还是删除操作，都必须找到其前驱结点 删除双链表的中间某个结点时，只需修改两个指针域 将两个各有 n 和 m 个元素的有序表(递增)归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n-1。（分数：2.00）A.仅、
2、B.、C.仅、D.仅、3.下列关于栈的说法中，正确的是( )。 若进栈顺序为 a、b、c，则通过出栈操作可能得到 5 个a、b、c 的不同排列 链式栈的栈顶指针一定指向栈的链尾 两个栈共享一个向量空间的好处是减少了存取时间（分数：2.00）A.仅B.仅、C.仅D.仅、4.若将 n 阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)21-1中，第一个非零元素 a(1，1)存于 B0中，则存放到 Bk中的非零元素 a(i，j)(1in，1jn)的下标 i、i 与 k的对应关系是( )。（分数：2.00）A.k=i(i+1)2+jB.k=i(i-1)2+j-1C.k-j(j+1)
3、2+iD.k-j(j-1)2+i-15.已知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_BHGJI_（分数：2.00）A.CBEDAHGFIJB.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB6.设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对( )个字符编码。（分数：2.00）A.3B.4C.5D.67.下列说法中，正确的是( )。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n 2 -2e 若
4、邻接表中有奇数个边表结点，则该图一定是有向图 对于采用邻接表存储的图，其深度优先遍历算法类似于二叉树的中序遍历 使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能人于 1（分数：2.00）A.仅、B.仅、C.仅、D.仅、8.下列关于生成树的说法中，正确的是( )。（分数：2.00）A.最小生成树是指权值之和为最小的生成树，且唯一B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度C.Prime 算法和 Kruskual 算法构造的最小生成树一定一样D.Prime 算法适用于求边稠密的图的最小生成树9.下列关于 m 阶 B+树的说法中，正确的是( )。具有 n 个关键字的结点至少
5、含有 n+1 棵子树所有叶子结点包含全部关键字B+树支持随机索引B+树可用于文件的索引结构（分数：2.00）A.仅、B.仅、C.仅、D.仅、10.利用逐点插入建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行( )次元素间的比较。（分数：2.00）A.4B.5C.6D.711.对以下关键字序列用快速排序算法进行排序，速度最慢的是( )。（分数：2.00）A.1，4，7，10，15，24B.2，5，3，20，15，18C.4，5，7，13，10，9D.4，7，8，5，19，1612.在外部排序算法中，最佳归并树主要的作用是( )。
6、（分数：2.00）A.产生初始归并段B.完成归并排序C.对归并排序进行优化D.增大归并路树13.下列关于计算机系统中的概念的说法中，正确的是( )。CPU 中不包括地址译码器CPU 中程序计数器(PC)中存放的是操作数地址CPU 中决定指令执行顺序的是程序计数器在 CPU 中状态寄存器对用户是完全透明的（分数：2.00）A.仅、B.仅、C.仅、D.仅、14.假定采用 IEEE 754 单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（分数：2.00）A.(+1125)2 10B.(+11 25)2 11C.(+0125)2 11D.(+0125)2 1015.一个 8 位
7、的二进制整数，若采用补码表示，且由 3 个“1”和 5 个“0”组成，则最小值为( )。（分数：2.00）A.-127B.-32C.-125D.-316.一台 8 位微机的地址总线为 16 条，其 RAM 存储器容量为 32KB，首地址为 4000H，且地址是连续的，可用的最高地址为( )。（分数：2.00）A.BFFFHB.CFFFHC.DFFFHD.EFFFH17.有效容量为 128KB 的 Cache，每块 16B，8 路组相联。字节地址为 1234567H 的单元调入该 Cache，其Tag 应为( )。（分数：2.00）A.1234HB.2468HC.048DHD.12345H18.
8、在单发射、按序流动的普通流水线中，可能出现下列( )数据相关问题。写后读相关 RAW读后写相关 WAR写后写相关 WAW（分数：2.00）A.仅B.仅、C.仅D.仅、19.在按字节编址的计算机中，一条指令长 16 位，当前分支转移指令(采用相对寻址)地址为 3000，指令地址的偏移量为-5，当执行完此转移指令后，PC 的值为( )。（分数：2.00）A.2996B.2997C.3001D.300220.以下给出的事件中，无须异常处理程序进行中断处理的是( )。（分数：2.00）A.缺页故障B.访问 Cache 缺失C.地址越界D.除数为 021.假定一台计算机的显示存储器用 DRAM 芯片实现
9、，若要求显示分辨率为 16001200，颜色深度为 24 位，帧频为 85Hz，显存总带宽的 50用来刷新屏幕，则需要的显存总带宽至少约为( )。（分数：2.00）A.245MbitsB.979MbitsC.1958MbitsD.7834Mbits22.总线宽度只与下列( )选项有关。控制线根数地址线根数数据线根数（分数：2.00）A.仅B.仅、C.仅D.、23.在主机和外设的信息传送中，( )没有使用程序控制方式。（分数：2.00）A.程序查询方式B.程序中断方式C.DMA 方式D.通道方式24.下列关于操作系统结构说法中，正确的是( )。 当前广泛使用的 Windows XP 操作系统，采
10、用的是分层式 OS 结构 模块化的 OS 结构设计的基本原则是：每一层都仅使用其底层所提供的功能和服务，这样使系统的调试和验证都变得容易 由于微内核结构能有效支持多处理机运行，故非常合适于分布式系统环境 采用微内核结构设计和实现操作系统具有诸多好处，如添加系统服务时，不必修改内核、使系统更高效等（分数：2.00）A.仅、B.仅、C.仅D.仅、25.在有一个 CPU 和两台外设 D1 和 D2，且能够实现抢占式优先级调度算法的多道程序环境中，同时进入优先级由高到低的 P1，P2，P3 的 3 个作业，每个作业的处理程序和使用资源的时间如下：P1：D2(30ms)，CPU(10ms)，D1(30m
11、s)，CPU(10ms)P2D1(20ms)，CPU(20ms)，D2(40ms)P3：PU(30ms)，D1(20ms)假设对于其他辅助操作时间忽略不计，CPU 的利用率是( )。（分数：2.00）A.478B.578C.678D.77826.设有如下两个优先级相同的进程 P1 和 P2。信号量 S1 和 S2 的初值均为 0，试问 P1、P2 并发执行结束后，z 的值可能是( )。 （分数：2.00）A.4、8、11B.4、6C.6、8D.4、827.系统的资源分配图在下列情况中，无法判断是否处于死锁的情况是( )。出现了环路没有环路每种资源只有一个，并出现环路每个进程结点至少有一条请求边
12、（分数：2.00）A.、B.仅、C.仅、D.都能判断28.下列存储管理方式中，会产生内部碎片的是( )。分段虚拟存储管理分页虚拟存储管理段页式分区管理固定式分区管理（分数：2.00）A.仅、B.仅、C.仅D.仅、29.下列程序设计技术和数据结构中，适合虚拟页式存储系统的有( )。堆栈 Hash 函数索引的符号表顺序搜索二分法查找纯代码矢量操作间接寻址矩阵操作（分数：2.00）A.、B.、C.、D.、30.文件系统中设立打开(open)系统调用的主要目的是( )。（分数：2.00）A.把文件从辅存读到内存B.把文件的控制信息从辅存读到内存C.把文件的 FAT 表信息从辅存读到内存D.把磁盘文件系
13、统的控制管理信息从辅存读到内存31.在 PC-DOS 中，某磁盘文件 A 与 B，它们所占用的磁盘空间如下所示。试问 A、B 文件在磁盘上各占( )簇。 （分数：2.00）A.3，3B.4，5C.5，3D.5，432.某磁盘盘组共有 10 个盘面，每个盘面上有 100 个磁道，每个磁道有 32 个扇区，假定物理块的大小为2 个扇区，分配以物理块为单位。若使用位图(bitmap)管理磁盘空间，则位图需要占用的空间大小是( )。（分数：2.00）A.2000BB.12000BC.6000BD.16000B33.关于 SPOOLing 技术的说法，以下正确的是( )。 SPOOLing 系统中不需要
14、独占设备 SPOOLing系统加快了作业完成的速度 当输入设备忙时，SPOOLing 系统中的用户程序暂停执行，待 IO 空闲时再被唤醒执行输出操作 在采用 SPOOLing 技术的系统中，用户的打印结果首先被送到内存固定区域（分数：2.00）A.仅、B.仅C.仅、D.仅、34.如图 7-1 所示的是某 IP 网络连接拓扑结构，共有( )。 （分数：2.00）A.5 个冲突域，1 个广播域B.3 个冲突域，3 个广播域C.4 个冲突域，2 个广播域D.6 个冲突域，2 个广播域35.长度为 1km，数据传输率为 10Mbits 以太网，电信号在网上的传播速度是 200ms。假设以太网数据帧的长
15、度为 256bit，其中包括 64bit 帧头、检验和及其他开销。数据帧发送成功后的第一个时间片保留给接收方，用于发送一个 64bit 的确认帧。假设网络负载非常轻(即不考虑冲突的任何情形)，则该以太网的有效数据传输速率为( )。（分数：2.00）A.421MbitsB.117MbitsC.609MbitsD.519Mbits36.下面技术无法使 10Mbits 的以太网升级到 100Mbits 的是( )。（分数：2.00）A.帧长保持不变，网络跨距增加B.采用帧扩展技术C.传输介质使用高速光纤D.使用以太网交换机，引入全双工流量控制协议37.以下给出的地址中，属于子网 1921681519
16、28 的主机地址是( )。1921681517192168151419216815161921681531（分数：2.00）A.仅B.仅、C.仅、D.、和38.下列关于 ARP 的说法中，错误的是( )。ARP 的请求报文是单播的ARP 的响应报文是单播的如果局域网 A 的主机 1 想和局域网 B 的主机 2 通信，但是主机 1 不知道主机 2 的物理地址，主机 1 通过发送 ARP 报文就可以解决（分数：2.00）A.仅B.仅C.仅、D.仅、39.TCP 中滑动窗口的值设置得太大，对主机的影响是( )。（分数：2.00）A.由于传送的数据过多而使路由器变得拥挤，主机可能丢失分组B.产生过多的
17、 ACKC.由于接收的数据多，而使主机的工作速度加快D.由于接收的数据多，而使主机的工作速度变慢40.A 和 B 建立 TCP 连接，MSS 为 1KB。某时，慢开始门限值为 2KB，A 的拥塞窗口为 4KB，在接下来的一个RTT 内，A 向 B 发送了 4KB 的数据(TCP 的数据部分)，并且得到了 B 的确认，确认报文中的窗口字段的值为 2KB，那么，请问在下一个 RTT 中，A 最多能向 B 发送( )数据。（分数：2.00）A.2KBB.4KBC.5KBD.8KB41.从协议分析的角度来看，WWW 服务的第一步是 WWW 浏览器对 WWW 服务器( )。（分数：2.00）A.请求地址
18、解析B.传输连接建立C.请求域名解析D.会话连接建立二、综合应用题(总题数：8，分数：40.00)42.综合应用题 41-47 小题。_求解下面有向图的有关问题，见图 8-3。 （分数：6.00）(1).判断此有向图是否有强连通分量?若有，请画出。（分数：2.00）_(2).画出此图的十字链表存储结构。（分数：2.00）_(3).简述基于图的深度优先搜索策略，并判别一个以邻接表存储的有向图是否存在顶点 V i 到顶点 V j 的路径的基本步骤。（分数：2.00）_假设有一带头结点的循环双链表表示的线性表 L=(a 1 ，a 2 ，a n-1 ，a n )。 设计在时间和空间上都尽可能高效的算法
19、，将线性表 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 个 512 字节的扇区，磁盘旋转一圈的时
20、间是 8192ms。请回答下列问题：（分数：6.00）(1).在磁盘不工作时，主存频带空闲百分比是多少?（分数：2.00）_(2).若采用周期挪用法进行 DMA 传送，则该计算机执行指令的速度由于 DMA 传送而降低了多少?（分数：2.00）_(3).若采用周期挪用法进行 DMA 传送，总线宽度为 16 位，则该计算机执行指令的速度由于 DMA 传送而降低了多少?（分数：2.00）_下面是一段 MIPS 指令序列：add$t1，$s1，$s0 #R$t1R$s1+R$s0sub$t2，Ss0，$s3 #R$t2R$s0-R$s3add$t1，St1，$t2 #R$t1R$t1+R$t2 假定在
21、一个采用“取指、译码取数、执行、访存、写回”的五段流水线处理器中执行上述指令序列，请回答下列问题：（分数：8.00）(1).以上指令序列中，哪些指令之间发生数据相关?（分数：2.00）_(2).若不采用“转发”技术的话，需要在何处、加入几条 nop 指令能保证这段指令序列的执行避免数据冒险。（分数：2.00）_(3).如果采用“转发”技术，是否可以完全解决数据冒险?若不行，需要在何处，加入几条 nop 指令，才能使这段指令序列的执行避免数据冒险。（分数：2.00）_(4).在 2)和 3)两种情况下，执行上述 3 条指令的 CPl 分别是多少?(保留小数点后一位)（分数：2.00）_43.给出
22、一个单车道的简易桥，如图 8-4 所示。 （分数：2.00）_设正在处理器上执行一个进程的页表如表 8-2 所示。表中的虚页号和物理块号是十进制数，起始页号(块号)均为 0。所有的地址均是存储器字节地址。页的大小为 1024B。若发生缺页中断，使用 LRU 页面置换算法将缺页调入再进行地址变换，页表中访问字段记录本页最近已有多长时间未被访问。 （分数：4.00）(1).详述在设有快表的请求分页存储器管理系统中，一个虚地址转换成物理内存地址的过程。（分数：2.00）_(2).根据给出的某进程的页表，系统给该进程分配的最大内存物理块数为 3，进程先后使用下面两个虚地址访问内存，其对应的物理内存地址
23、分别是多少?请详述整个地址变换过程并参照给出的页表，画出每次操作后的页表。(注：访问字段表示的是该页最近已有多长时间未被访问) a)4475(写操作) b)1197(读操作)（分数：2.00）_设有 4 台主机 A、B、C 和 D 都处在同一物理网络中，它们的 IP 地址分别为19215528112、19215528120、19215528135 和 19215528202，子网掩码都是255255255224，请回答：（分数：8.00）(1).该网络的 4 台主机中哪些可以直接通信?哪些需要通过设置路由器才能通信?请画出网络连接示意图，并注明各个主机的子网地址和主机地址。（分数：2.00）_
24、(2).若要加入第 5 台主机 E，使它能与主机 D 直接通信，则其 TP 地址的范围是多少?（分数：2.00）_(3).若不改变主机 A 的物理位置，而将其 IP 改为 19215528168，则它的直接广播地址和本地广播地址各是多少?若使用本地广播地址发送信息，请问哪些主机能够收到?（分数：2.00）_(4).若要使该网络中的 4 台主机都能够直接通信，可采取什么办法?（分数：2.00）_计算机专业（基础综合）模拟试卷 103 答案解析(总分：122.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一
25、个选项是最符合题目要求的。（分数：2.00）_解析：2.下列说法中，正确的是( )。 假设某有序表的长度为 n，则可以在 1-(n+1)的位置上插入元素 在单链表中，无论是插入还是删除操作，都必须找到其前驱结点 删除双链表的中间某个结点时，只需修改两个指针域 将两个各有 n 和 m 个元素的有序表(递增)归并成一个有序表，仍保持其递增有序，则最少的比较次数是 m+n-1。（分数：2.00）A.仅、B.、C.仅、 D.仅、解析：解析：有序表插入的时候是不能指定位置的，因为这样可能使得插入后的表不再是有序表。正确的插入思想是：先通过元素比较找到插入的位置，再在该位置上插入，故错误。 ：从单链表插入
26、和删除的语句描述中可以看出，无论是插入还是删除操作，都必须找到其前驱结点，故正确。 ：删除双链表中间某个结点时，需要修改前后两个结点的各一个指针域，共计两个指针域，故正确。 ：当一个较短的有序表中所有元素均小于另一个较长的有序表中所有的元素，所需比较次数最少。假如一个有序表为 1、3、4，另一个有序表为 5、6、7、8、12，这样只需比较 3 次即可，故答案应该是 n 和 m 中较小者，即 min(n，m)，故错误。3.下列关于栈的说法中，正确的是( )。 若进栈顺序为 a、b、c，则通过出栈操作可能得到 5 个a、b、c 的不同排列 链式栈的栈顶指针一定指向栈的链尾 两个栈共享一个向量空间的
27、好处是减少了存取时间（分数：2.00）A.仅 B.仅、C.仅D.仅、解析：解析：该选项旨在让考生知道一个公式。对于 n 个不同元素进栈，出栈序列的个数为 可以马上得出，当 n=3 时，出栈序列个数为4.若将 n 阶上三角矩阵 A 按照列优先顺序存放在一维数组 B0，1，n(n+1)21-1中，第一个非零元素 a(1，1)存于 B0中，则存放到 Bk中的非零元素 a(i，j)(1in，1jn)的下标 i、i 与 k的对应关系是( )。（分数：2.00）A.k=i(i+1)2+jB.k=i(i-1)2+j-1C.k-j(j+1)2+iD.k-j(j-1)2+i-1 解析：解析：对于元素 a(i，j
28、)而言，前面有 j-1 列，第 1 列到第 j-1 列的元素个数分别为 1j-1 个，由等差数列求和公式可算得一共有 j(j-1)2 个元素，故 k=j(j-1)2+i-1(注意 B 数组是从 0 开始存元素，因此要减去 1)。5.已知一棵二叉树的先序、中序、后序的部分序列如下，其中有些位置没有给出其值，则原二叉树的中序遍历序列为( )。 先序：A_CDEF_H_J 中序：C_EDA_GFI_ 后序：C_BHGJI_（分数：2.00）A.CBEDAHGFIJ B.CHEDABGFIJC.CBEDAJGFIHD.CJEDAHGFIB解析：解析：对于一棵二叉树(包括子树)，它的遍历序列对应的结构应
29、该是：先序遍历：根左子树右子树，中序遍历：左子树根右子树，后序遍历：左子树右子树根，由题目中给出的先序序列的第一个结点我们找到树的根 A，然后在中序序列中找到 A，并以 A 为分界将中序序列划分为C_EDA_GFI_，所以 C_ED 为左子树，_GFI_为右子树，再对应到后序遍历序列上，这里左子树结点的个数等于中序遍历序列中左子树结点的个数，因此 C_ _B 为左子树，HGJI_为右子树，这样把中序序列和后续序列中的左右子树一对比，则 CBED 为左子树，FGHIJ 为右子树。答案选 A。6.设某赫夫曼树的高度为 5，若已对两个字符编码为 1 和 01，则最多还可以对( )个字符编码。（分数：
30、2.00）A.3B.4 C.5D.6解析：解析：首先，赫夫曼编码遵循的原则为：一个编码不能是任何其他编码的前缀。比如 1 和 10 就不行，因为 1 是 10 的前缀。既然 1 和 01 已经使用了，所以 1 和 01 开头的码字不能再使用。又由于赫夫曼树的高度为 5，故赫夫曼编码的长度不能超过 4，只剩下 0000、0001、0010、0011 等 4 种编码(这种编码方式可得到最多)，故选 B 选项。7.下列说法中，正确的是( )。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，零元素的个数为 n 2 -2e 若邻接表中有奇数个边表结点，则该图一定是有向图 对于采用邻接表存储的图，其深
31、度优先遍历算法类似于二叉树的中序遍历 使用队列实现广度优先遍历算法，则每个顶点进队列的次数可能人于 1（分数：2.00）A.仅、B.仅、C.仅、D.仅、 解析：解析：总结如下： 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 n 2 。 在含有 n 个顶点 e 条边的无向图的邻接矩阵中，非零元素的个数为 2e。 在含有 n 个顶点e 条边的无向图的邻接矩阵中，零元素的个数为 n 2 -2e。 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，非零元素的个数为 e。 在含有 n 个顶点 e 条边的有向图的邻接矩阵中，零元素的个数为 n 2 -e。 根据，故正确。 ：无向图采
32、用邻接表表示时，每条边存储两次，所以其边表结点个数为偶数，故边表结点为奇数只能是有向图，故正确。 ：深度优先遍历算法是先访问一个顶点 v，然后是离开顶点越远越优先访问，即相当于二叉树的先序遍历，故错误。 ：采用广度优先遍历算法遍历一个图时，每个顶点仅遍历一次，所以最多只能进队 1 次，故错误。8.下列关于生成树的说法中，正确的是( )。（分数：2.00）A.最小生成树是指权值之和为最小的生成树，且唯一B.某图的广度优先生成树的高度一定大于等于深度优先生成树的高度C.Prime 算法和 Kruskual 算法构造的最小生成树一定一样D.Prime 算法适用于求边稠密的图的最小生成树 解析：解析：
33、A：最小生成树是指权值之和为最小的生成树，但是不唯一，故 A 选项错误。 B：由广度优先遍历和深度优先遍历算法可知，深度优先算法构造的生成树的树高大于等于广度优先算法构造的生成树的树高，故 B 选项错误。 C：当最小生成树不唯一时，这两种算法构造的最小生成树可能相同，也可能不同，故 C 选项错误。 D：Prime 算法的时间复杂度为 O(n 2 )，适合稠密图；Kruskual 算法的时间复杂度为 O(elog 2 e)，适合稀疏图，故 D 选项正确。9.下列关于 m 阶 B+树的说法中，正确的是( )。具有 n 个关键字的结点至少含有 n+1 棵子树所有叶子结点包含全部关键字B+树支持随机索
34、引B+树可用于文件的索引结构（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：一棵 m 阶 B+树满足下列条件： 每个分支结点至多有 m 棵子树。 根结点或者没有子树，或者至少有两棵子树。 除根结点外，其他每个分支结点至少有m2棵子树。 具有 n 个关键字的结点含有 n 棵子树。 所有叶子结点包含全部关键字及指向相应记录的指针，而且叶子结点按关键字的大小顺序链接。 所有分支结点巾仅包含它的各个子结点中最大关键字及指向子结点的指针。 B+树中，所有非终端结点可以看成是索引部分，故可用于文件的索引结构。 综上所述，可知、正确，、错误，故选 B 选项。10.利用逐点插入建立序列(50，
35、72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，要查找元素 30 要进行( )次元素间的比较。（分数：2.00）A.4B.5 C.6D.7解析：解析：由题可以建立出如图 7-5 所示的一棵二叉排序树。11.对以下关键字序列用快速排序算法进行排序，速度最慢的是( )。（分数：2.00）A.1，4，7，10，15，24 B.2，5，3，20，15，18C.4，5，7，13，10，9D.4，7，8，5，19，16解析：解析：首先需要知道快速排序的一个特性，即元素越无序，快速排序越快；元素越有序，快速排序越慢。但是一般情况下，有序的元素序列比较少，大部分情况都是杂乱无章的一
36、堆数，所以说快速排序是所有排序中性能最好的排序方法。有些同学可能会有疑问，快速排序最差的时间复杂度是 O(n 2 )，而有不少排序算法最坏的时间复杂度是 O(nlog 2 n)，比如堆排序。为什么快速排序的性能是最好的昵?因为快速排序出现最坏性能的情况实在是太少发生了，所以要看综合的性能，不能只看最坏的(记住就好，在此不举例子了)。本题 A 选项是一个有序序列，所以速度肯定最慢。12.在外部排序算法中，最佳归并树主要的作用是( )。（分数：2.00）A.产生初始归并段B.完成归并排序C.对归并排序进行优化 D.增大归并路树解析：解析：A：产生初始归并段的工作应该由置换一选择排序完成，故 A 选
37、项错误。 设输入的关键字满足 k 1 k 2 k n ，缓冲区大小为 m，用置换选择排序方法可产生nm个初始归并段。 B：因为最佳归并树是针对排序之后的初始归并段操作，所以归并排序不可能由最佳归并树完成，故 B 选项错误。C：最佳归并树仿造赫夫曼树的构造过程，以初始归并段的长度为权值，构造具有最小带权路径长度的赫夫曼树，可以有效地减少归并过程中的读写记录数，以加快外部排序的速度，故 C 选项正确。 D：增大归并路数应该是由败者树来完成的，故 D 选项错误。13.下列关于计算机系统中的概念的说法中，正确的是( )。CPU 中不包括地址译码器CPU 中程序计数器(PC)中存放的是操作数地址CPU
38、中决定指令执行顺序的是程序计数器在 CPU 中状态寄存器对用户是完全透明的（分数：2.00）A.仅、 B.仅、C.仅、D.仅、解析：解析：地址译码器是存储器在对地址进行译码时所需要的，CPU 中没有地址译码器，故正确。：CPU 中程序计数器(PC)中存放的是当前欲执行指令的地址，而不是操作数地址，故错误。 ：程序计数器的作用就是决定了指令下一步该执行的顺序，故正确。 ：状态寄存器、通用寄存器、程序计数器(PC)程序员能够操作它们的内容，这样才能实现汇编的编程。但是诸如 IR、MAR、MDR等都是 CPU内部的工作寄存器，程序员就不能改变其内容了，也就是对程序员是完全透明的，故错误。14.假定采
39、用 IEEE 754 单精度浮点数格式表示一个数为 45100000H，则该数的值是( )。（分数：2.00）A.(+1125)2 10B.(+11 25)2 11 C.(+0125)2 11D.(+0125)2 10解析：解析：45100000H 的二进制数为 0100 0101 0001 0000 0000 0000 0000 0000，第 1 位为符号位，表示正数，随后 8 位 1000 1010 为用移码表示的阶码，减去 127 得到十进制数 11，而 IEEE 754 中单精度数在阶码不为 0 时隐含 1，所以尾数为(10010)2=1125。15.一个 8 位的二进制整数，若采用补
40、码表示，且由 3 个“1”和 5 个“0”组成，则最小值为( )。（分数：2.00）A.-127B.-32C.-125 D.-3解析：解析：8 位补码最小时必为负数，所以第一位(符号位)必须为 1。而负数的数值位绝对值越大，则此负数越小。又负数的补码表示的高位 0 相当于原码表示的 1，故当剩下的 2 个“1”在最低位，5 个“0”在数值位的最高位时此负数最小。该负数的补码为 10000011，则原码为 11111101，转换成十进制为-125。16.一台 8 位微机的地址总线为 16 条，其 RAM 存储器容量为 32KB，首地址为 4000H，且地址是连续的，可用的最高地址为( )。（分数
41、：2.00）A.BFFFH B.CFFFHC.DFFFHD.EFFFH解析：解析：32KB 存储空间共占用 15 条地址线，若 32KB 的存储地址起始单元为 0000H，其范围应为00007FFFH，但现在的首地址为 4000H，即首地址后移了，因此最高地址也应该相应后移。故最高地址为 4000H+7FFFH=BFFFH。17.有效容量为 128KB 的 Cache，每块 16B，8 路组相联。字节地址为 1234567H 的单元调入该 Cache，其Tag 应为( )。（分数：2.00）A.1234HB.2468HC.048DH D.12345H解析：解析：因为块的大小为 16B，所以块内地址字段为 4 位；又因为 Cache 容量为 128KB，8 路组相联
