1、计算机专业（基础综合）-试卷 92 及答案解析(总分：118.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_2.假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。void funint n) int i，j，k； for (i；l； i=n； i+) while (kn)（分数：2.00）A.O(n 2 109 2 n)B.O(nlo9 5 n)C.O(n 2 109 5 n)D.O(n 3 )3.以下说法正确的是( )。带头结点的循环
2、双链表 L 为空的条件是：LpriOF=L&Lnext=L线性表的插入和删除总是伴随着大量数据的移动只有删除静态链表的尾结点才不需要移动元素若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续（分数：2.00）A.仅B.仅、C.仅、D.、和4.循环队列用数组 A0m 一 1存放其元素值，已知其头尾指针分别是 front 和 rear（且队尾指针 rear指向队尾元素的下一个元素），则当前队列中的元素个数是( )。（分数：2.00）A.(rearfront+m)mB.(rearfront+l)mC.rearfront1D.rearfront5.下列关于二叉树的叙述中正确的是( )。对
3、于任何一棵二叉树，叶子结点数都是度为 2 的结点数加1二叉树的左右子树不可以任意地交换二叉树只适合使用链式结构存储，不可能用顺序结构存储结点按层序编号的二叉树，第 i 个结点的左孩子（假设存在）的编号为 2i（分数：2.00）A.仅、B.仅C.仅、D.仅、6.若二叉树是由森林变换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点有( )。（分数：2.00）A.n 一 1B.nC.n+1D.n+27.根据使用频率为 5 个字符设计的赫夫曼编码不可能是( )。（分数：2.00）A.000，001，010，011，1B.0000，0001，001，01，1C.000，001，01，10，
4、11D.00，100，101，110，1118.在具有 n 个顶点的图 G 中，若最小生成树不唯一，则( )。G 的边数一定大于 n1.G 的权值最小的边一定有多条G 的最小生成树代价不一定相等（分数：2.00）A.仅B.仅、C.仅、D.仅9.图 11 中强连通分量的个数为( )。 （分数：2.00）A.2B.3C.4D.510.在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是( )。（分数：2.00）A.28，36，18，46，35B.18，36，28，46，35C.46，28，18，36，35D.46，36，18，28，3511.排序趟数与序列的原始状态无关的排序方
5、法是( )。直接插入排序简单选择排序冒泡排序基数排序（分数：2.00）A.仅、B.仅、C.仅、D.仅、12.下列关于外部排序说法正确的是( )。（分数：2.00）A.内存与外设交换信息的时间只是外部排序总时间的一小部分B.外部排序就是在外存上进行排序，无需内存参与C.败者树是一棵完全二叉树D.置换选择排序得到的初始归并段长度一定相等13.图 12 中计算机硬件系统基本组成部件、和的名称分别是( )。 （分数：2.00）A.控制器、运算器、存储器、输入设备、输出设备B.运算器、控制器、存储器、输入设备、输出设备C.运算器、存储器、控制器、输入设备、输出设备D.运算器、控制器、存储器、输出设备、输
6、入设备14.已知小写英文字母“a”的 ASC码值为 61H，现字母“g”被存放在某个存储单元中，若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是( )。（分数：2.00）A.167HB.E6HC.67HD.E7H15.页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB，地址变换过程如图 13 所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数物理地址 a 应为( )。（分数：2.00）A.33220B.8644C.4548D.250016.下列关于 ROM 和 RAM 的说法中，正确的是( )。CDROM 与 EPROM 都采用随机
7、存储方式SRAM 读后不需要刷新，而 DRAM 读后需要刷新Cache 可以由 ROM 或者 RAM 组成（分数：2.00）A.、和B.仅和C.仅D.仅17.下列关于 Flash 存储器的说法正确的是( )。（分数：2.00）A.Flash 存储器属于易失性存储器B.Flash 存储器不具备写功能C.Flash 存储器是不可擦除的存储器D.Flash 存储器同时具有 ROM 和 RAM 的功能18.某机器采用 16 位单字长指令，采用定长操作码，地址码为 5 位，现己定义 60 条二地址指令，那么单地址指令最多有( )条。（分数：2.00）A.4B.32C.128D.25619.在一条无条件跳
8、转指令的指令周期内，程序计数器(PC)的值被修改了( )次。（注：指令均为单字长指令，且按字寻址）（分数：2.00）A.1B.2C.3D.不能确定20.当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断请求的是( )。外部事件. Cache浮点运算下溢浮点运算上溢（分数：2.00）A.仅、B.仅、C.仅、D.仅、21.假定一个高速缓存(M1)和存储器(M2)的层次结构有以下性能。M1:16KB，存取时间为 50ns； M2:1MB，存取时间为 400ns。高速缓存块为 8B，组大小为 256 个字，采用组相联映射，高速缓存命中率 h=095 时的有效存储器存取时间是( )
9、。（分数：2.00）A.50nsB.60nsC.70nsD.80ns22.下面关于 PCI 总线的基描述中，错误的有( )。PCI 总线是一个与处理器性能相关的高速外围总线PCI 总线可对传输信息进行奇偶校验. PCI 设备一定是主设备系统中允许有多条 PCI 总线（分数：2.00）A.仅、B.仅、C.仅和D.仅、23.下列说法正确的是( )。（分数：2.00）A.在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的B.计算机的外围设备就是指输入和输出设备C.中断隐指令属于程序控制型指令D.在中断服务程序中，恢复现场之前需要关中断24.操作系统必须提供的功能是( )。（分
10、数：2.00）A.GUIB.为进程提供系统调用命令C.处理中断D.编译源程序25.以下服务中，能发挥多线程系统的特长的是( )。利用线程并发地执行矩阵乘法运算. Web 服务器利用线程请求 HTTP 服务.键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作（分数：2.00）A.、B.、C.、D.、26.现在有 3 个同时到达的作业 Jl、J2 和 J3，它们的执行时间分别为 T1、T2 和 T3，且 T1T2T3。如果该系统中有两个 CPU，各自按照单道方式运行且采用短作业优先算法，则平 均周转时
11、间是( )。（分数：2.00）A.(T1+T2+T3)/3B.(2T1+T2+T3)/3C.(T1+2T2+T3)/3D.(2T1+T2+T3)/3 或(T1+2T2+T3)/327.对计数型信号量 S 执行 V 操作后，下列选项错误的是( )。当 S.value0 时，唤醒一个阻塞队列进程只有当 S.value0 时，唤醒一个阻塞队列进程当 S.value0 时，唤醒一个就绪队列进程只有当 S.value0 时，唤醒一个就绪队列进程（分数：2.00）A.、B.、C.、D.、28.设有 8 页的逻辑空间，每页有 1024B，它们被映射到 32 块的物理存储区中。那么逻 辑地址的有效位是( )物
12、理地址至少是( )位。（分数：2.00）A.10，12B.10，15C.13，15D.13，1229.某虚拟存储器的用户编程空间共 32 个页面，每页 1KB，主存为 16KB。假定某时刻用户页表中已调入主存的页面的虚页号和物理页号对照表为表 11，则与表 12 十六进制虚地址对应的物理地址为( )。（分数：2.00）A.1E5C，2A5CB.1E5C，缺页中断C.125C，2A5CD.125C，缺页中断30.假定有一个请求分页存储管理系统，测得系统各相关设备的利用率如下：CPU 利用率为 10，磁盘交换区为 997，其他 I/O 设备为 5。试问：下面措施中将可能改进 CPU 利用率的是(
13、)。增大内存的容量增大磁盘交换区的容量减少多道程序的道数增加多道程序的道数 V使用更快速的磁盘交换区使用更快速的 CPU（分数：2.00）A.、B.、C.、D.、31.下面关于文件系统的说法正确的是( )。（分数：2.00）A.文件系统负责文件存储空间的管理，但不能实现文件名到物理地址的转换B.在多级目录结构中，对文件的访问是通过路径名和用户目录名进行的C.文件可以被划分成大小相等的若干物理块，且物理块大小也可以任意指定D.逻辑记录是对文件进行存取操作的基本单位32.一个交叉存放信息的磁盘，信息存放方式如图 14 所示。每个磁道有 8 个扇区，每个扇区 512B，旋转速度为 3000 转/分。
14、假定磁头已在读取信息的磁道上，0 扇区转到磁头下需要 1/2 转，且设备对应的控制器不能同时进行输入/输出，在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2，问依次读取一个磁道上所有的扇区的数据到内存平均传输速度为( )。 （分数：2.00）A.571KB/sB.671KB/sC.771KB/sD.871KB/s33.假设 T 是从磁盘输入一块数据到缓冲区需要的时间，C 是 CPU 对一块数据进行处理的时间，而 M 是将一块数据从缓冲区传送到用户区的时间。当一用户进程要按顺序访问的方式处理大量数据时，请问在单缓冲和双缓冲的情况下，系统对一块数据的处理时间分别是( )。（分数：2
15、.00）A.max(T，C)+M，max(T，M+C)B.max(T，M+C)，max(T，C)+MC.max(T，M)+C，max(T，M+C)D.max(T，M+C)，max(T，M)+C34.计算机网络可分为通信子网和资源子网，下列属于通信子网的是( )。网桥交换机计算机软件路由器（分数：2.00）A.、B.、C.、D.、35.已知循环冗余码生成多项式 G(x)=x 5 +x 4 +x+1，若信息位为 10101100，则冗余码是( )。（分数：2.00）A.1101B.1100C.1101D.110036.若子网掩码为 25525500，则下列( )IP 与其他地址不在同一网络中？（分
16、数：2.00）A.1722515200B.172251615C.1722525200D.17235161537.在 IPv6 协议中，一个数据流可以由( )进行标识。（分数：2.00）A.源地址、目的地址和流名称B.源地址、目的地址和流标号C.源地址、端口号和流标号D.MAC 地址、端口号和流名称38.使用 CIDR 技术把 4 个网络 10010000/18、100100640/18、10010012 80/18、1001001920/18 汇聚成一个超网，得到的地址是( )。（分数：2.00）A.10010000/16B.10010000/18C.1001001280/18D.100100
17、640/1839.一个有 50 个路由器的网络，采用基于距离一向量的路由选择算法，路由表的每个表项长度为 6B，每个路由器都有 3 个邻接路由器，每秒与每个邻接路由器交换 1 次路由表，则每条链路上由于路由器更新路由信息而耗费的带宽为( )。（分数：2.00）A.2400bit/sB.3600bit/sC.4800bit/sD.6000bit/s40.设某 TCP 的拥塞窗口的慢启动门限值初始为 8(单位为报文段，且最大报文段长度为 1KB)，当拥塞窗口上升到 12 时，网络会发生超时。按照以上给出的条件，第 12 次传输时，拥塞窗口的大小为( )。（分数：2.00）A.5B.6C.7D.84
18、1.关于 FTP 的工作过程，下面说法错误的是( )。（分数：2.00）A.每次数据传输结束后，FTP 服务器同时释放 21 和 20 端口B.FTP 的数据连接是非持久的C.FTP 的文件传输需要两条 TCP 连接D.FTP 协议可以在不同类型的操作系统之间传送文件二、综合应用题(总题数：8，分数：36.00)42.综合应用题 41-47 小题。_有一结点的关键字序列 F= 129，72，180，105，147，96，45，69，散列函数为：H (k) =k mod 11，其中 k 为关键字，散列地址空间为 010。要求：（分数：6.00）(1).画出相应的散列表。当发生冲突时，以线性探测法
19、解决。该散列表的装填因子是多少？计算在等概率情况下，查找成功和查找不成功时的平均查找长度 ASL。（分数：2.00）_(2).画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功时的平均查找长度 ASL（只将与关键字的比较次数计算在内即可）。（分数：2.00）_(3).试按各关键字在序列 F 中的次序将它们依次插入一棵初始为空的平衡二叉排序树中，画出每一步插入后平衡二叉排序树的形态。若做了某种旋转，请注明旋转的类型。（分数：2.00）_试设计一个算法，判断一个有向无环图 G 中是否存在这样的顶点，该顶点到其他任意顶点都有一条有向路径。有向图 G 以邻接表的形
20、式存储。（分数：6.00）(1).给出算法的基本设计思想以及结点和邻接表的定义。（分数：2.00）_(2).根据设计思想，采用 C、C+语言描述算法，关键之处给出注释。（分数：2.00）_(3).说明你所设计算法的时间复杂度。（分数：2.00）_有以下两段 C 语言程序代码：int funl(unsigned short si) int fun2 (unsigned short sireturn . (s1*256) ； return ( (short) s1*256) /256) ；请回答下列问题：（分数：6.00）(1).假设计算机硬件不提供直接乘除运算功能，如何实现上述函数的功能？函数
21、funl 和 fun2 得到的结果各有什么特征？（分数：2.00）_(2).根据以上程序填写表 44（要求机器数用十六进制表示）。 （分数：2.00）_(3).表中的哪些数据异常？并分析“异常”产生的原因。（分数：2.00）_以下是计算两个向量点积的程序段：float dotproduct (float x L83 f float y 8 )float sum=0.0；int i；for (i=0；i8；1+)sum+=x i *y i) ；return sum；试回答以下问题：（分数：8.00）(1).访问数组 x 和 y 时的时间局部性和空间局部性各如何？能否推断出命中率的高低？（分数：2
22、.00）_(2).假定该段程序运行的计算机的数据 Cache 采用直接映射方式，其容量为 32B，每个主存块大小为16B。假定编译程序将变量 sum 和 i 分配给寄存器，数组 x 存放在 00000040H 开始的 32B 的连续存储区中，数组 y 则紧跟在 x 后进行存放。试计算该程序数据访问的命中率，要求说明每次访问的 Cache 命中情况。（分数：2.00）_(3).将上述(2)中的数据 Cache 改用 2路组相联映射方式，块大小改为 8B，其他条件不变，则该程序数据访问的命中率是多少?（分数：2.00）_(4).在上述(2)中条件不变的情况下，如果将数组 x 定义为 float12
23、，则数据访问的命中率又是多少？（分数：2.00）_43.某系统有 R1、R2 和 R3 共三种资源，在 T0 时刻，P1、P2、P3 和 P4 这四个一组合作进程，执行顺序如图 44 所示。请用 PV 操作实现进程中的同步操作。 （分数：2.00）_某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有 10 项，其中前 8 项是直接索引项，第 9 项是一次间接索引项，第 10 项是二次间接索引项，假定物理块的大小是 2KB，每个索引项占用 4 个字节，试问：（分数：4.00）(1).该文件系统中最大的文件可以达到多大？（分数：2.00）_(2).假定一个文件的实际大小是 128M
24、B，该文件实际占用磁盘空间多大（包括间接索引块，不计索引表所占空间）?（分数：2.00）_假定站点 A 和 B 在同一个 10Mbit/s 以太网的网段上，这两个站点之间的传播时延为 225 比特时间。现假定 A 开始发送一帧，并且在 A 发送结束之前 B 也发送一帧。如果 A 发送的是以太网所允许的最短的帧，试问：（分数：4.00）(1).A 在检测到和 B 发生碰撞之前能否把自己的数据发送完毕？如果 A 在发送完毕之前并没有检测到碰撞，那么能否肯定 A 所发送的帧不会和 B 发送的帧发生碰撞？（提示：在计算时应当考虑到每一个以太网帧在发送到信道上时，在 MAC 帧前面还要增加 7 个字节的
25、前同步码和 1 个字节的帧定界符）（分数：2.00）_(2).在(1)中的站点 A 和 B 在 t=0 时同时发送了数据帧。当 t=225 比特时间，A 和 B 同时检测到发生了碰撞，并且在 t=225+48=273 比特时间完成了干扰信号的发送。A 和 B 在 CSMA/CD 算法中选择不同的 r 值退避。假定 A 和 B 选择的随机数分别是 0 和 1。试问：A 和 B 各在什么时间开始重传其数据帧？A 重传的数据帧在什么时间到达 B?A 重传的数据会不会和 B 重传的数据再次发送碰撞？B 会不会在预定的重传时间停止发送数据？（分数：2.00）_计算机专业（基础综合）-试卷 92 答案解析
26、(总分：118.00，做题时间：90 分钟)一、单项选择题(总题数：41，分数：82.00)1.单项选择题 1-40 小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数：2.00）_解析：2.假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。void funint n) int i，j，k； for (i；l； i=n； i+) while (kn)（分数：2.00）A.O(n 2 109 2 n)B.O(nlo9 5 n)C.O(n 2 109 5 n) D.O(n 3 )解析：解析：首先抓基本运算语句，即 k=5*k；设其执行时间为 T(n)。对于
27、j 每循环一次，该语句的执行次数为 m，有 5 m n，即 m109sn。所以， T(n)= i=1 n j=1 n m=m i=1 n j=1 n =mn 2 = n 2 log 5 n=O(n 2 log 5 n)3.以下说法正确的是( )。带头结点的循环双链表 L 为空的条件是：LpriOF=L&Lnext=L线性表的插入和删除总是伴随着大量数据的移动只有删除静态链表的尾结点才不需要移动元素若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续（分数：2.00）A.仅 B.仅、C.仅、D.、和解析：解析：循环双链表为空时头结点如图 16 所示。4.循环队列用数组 A0m 一 1
28、存放其元素值，已知其头尾指针分别是 front 和 rear（且队尾指针 rear指向队尾元素的下一个元素），则当前队列中的元素个数是( )。（分数：2.00）A.(rearfront+m)m B.(rearfront+l)mC.rearfront1D.rearfront解析：解析：因为是循环队列，所以应该分为 rearfront 和 rearfront 两种情况来讨论。 (1)当rearfront 时，队列中元素个数为 rearfront=(rearfront+m)m 因为 0rearfrontm，所以rearfront+m 与 m 取余后结果还是 rearfront。 (2)当 rearf
29、ront 时，队列中元素个数为 m(frontrear)=rear front+m=(rear front+m)m 因为 Orearfront+nm，所以 rearfront+m与 m 取余后结果还是 rearfront+m。 综合(1)、(2)可知，A 选项正确。 知识点总结：循环队列的两大状态和两大操作以及三大重点提醒。 (1)两大状态（数学式子表示） 1)队空状态：q.reaF=q.front。 2)队满状态：(q.rear+1) MAX=q.front。 (2)两大，操作 1)元素 x 进队操作（移动队尾指针）。 q.reaF(q.rear+1)MAX； q.dataq.rear=x；
30、 2)元素 x 出队操作（移动队头指针）。 q.front=(qu.front+1)MAX； x=q.dataq.front；5.下列关于二叉树的叙述中正确的是( )。对于任何一棵二叉树，叶子结点数都是度为 2 的结点数加1二叉树的左右子树不可以任意地交换二叉树只适合使用链式结构存储，不可能用顺序结构存储结点按层序编号的二叉树，第 i 个结点的左孩子（假设存在）的编号为 2i（分数：2.00）A.仅、B.仅 C.仅、D.仅、解析：解析：:的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目的时候一定要先想到这种特殊情况，所以错误。 :二叉树的左右子树是有顺序的，不能随意交换，所以正确
31、。 :般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用顺序结构存储，所以错误。 ：该结论只对完全二叉树才成立，所以错误。 综上所述，只有正确。6.若二叉树是由森林变换而来的，若森林中有 n 个非终端结点，则二叉树中无右孩子的结点有( )。（分数：2.00）A.n 一 1B.nC.n+1 D.n+2解析：解析：由于森林中每一个非终端结点（根结点除外）的所有儿子在转换成二叉树之后，只有一个儿子的右孩子为空，根结点中本身有一个在转化成二叉树后右孩子为空，如图 17 所示，所以共有 n+1 个。7.根据使用频率为 5 个字符设计的赫夫曼编码不可能是( )。（分数：2.00）A.0
32、00，001，010，011，1B.0000，0001，001，01，1C.000，001，01，10，11D.00，100，101，110，111 解析：解析：赫夫曼树中只有度为 0 或 2 的结点，由 D 选项可以画出对应的二叉树，如图 18 所示。8.在具有 n 个顶点的图 G 中，若最小生成树不唯一，则( )。G 的边数一定大于 n1.G 的权值最小的边一定有多条G 的最小生成树代价不一定相等（分数：2.00）A.仅 B.仅、C.仅、D.仅解析：解析：最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一定相等，故错误；既然最小生成树不唯一，并且最小生成树的边都
33、为 n 一 1 条，说明图 G 的边数一定会大于 n1，故正确；最小生成树不唯一，和 G 的权值最小的边的条数没有任何关系，故错误。9.图 11 中强连通分量的个数为( )。 （分数：2.00）A.2B.3C.4 D.5解析：解析：在有向图 G 中，如果两个顶点 v i 、v j 间有一条从 v i 到 v j 的有向路径，同时还有一条从 v j 到 v i 的有向路径，则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向图的极大强连通子图，称为强连通分量。本题中可以看出 v2、v3、v4 同属于一个连通分量，另外 v1、v5、v6 各自属于一个强连通分量，所
34、以共有 4 个强连通分量。10.在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是( )。（分数：2.00）A.28，36，18，46，35B.18，36，28，46，35C.46，28，18，36，35D.46，36，18，28，35 解析：解析：可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线如图 19 所示。 11.排序趟数与序列的原始状态无关的排序方法是( )。直接插入排序简单选择排序冒泡排序基数排序（分数：2.00）A.仅、B.仅、 C.仅、D.仅、解析：解析：直接插入排序：每趟排序都是插入一个元素，所以排序
35、趟数固定为 n1（n 为元素数）。 简单选择排序：每趟排序都是选出一个最小（或最大）的元素，所以排序趟数固定为 n1（n 为元素数）。交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。 基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为 d（d 为组成元素的关键字位数）。 综上所述，、都是无关的，所以选 B。12.下列关于外部排序说法正确的是( )。（分数：2.00）A.内存与外设交换信息的时间只是外部排序总时间的一小部分B.外部排序就是在外存上进行排序，无需内存参与C.败者树是一棵完全二叉树 D.置换选择排序得到的初始归并段长度一定相等解析：解析：A:影响外部排序
36、时间的主要因素就是内存与外设交换信息的总次数，所以 A 错误。 B:外部排序也是在内存上进行排序，只不过需要分为多步而已，所以 B 错误。 C:从败者树的构建方式可知，败者树是一棵完全二叉树，所以 C 正确。 补充知识点：败者树和堆有什么区别？ 解析：外部排序中败者树和堆排序的区别在于： (1)败者树是在双亲结点中记下刚进行完的这场比赛的败者，而让胜者去参加更加高一层的比赛，便可得到一棵败者树。而堆排序可看作一种胜者树，即双亲结点表示其左右孩子中的胜者。(2)在败者树中，参加比较的 n 个关键字全部为叶子结点，双亲即为其左、右子女的败者，败者树中结点总数为 2n1，加上冠军结点恰好为 2n。而
37、堆是由 n 个关键字组成的完全二叉树，每个关键字作为树中一个结点，根是 n 个关键字中的胜者，树中结点总数为 n。 D:使用置换一选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的过程也可以得到答案，所以 D 错误。 外部排序的基本过程： 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段： (1)建立用于外部排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内排序方法对各段进行排序。经过排序的段叫作初始归并段。当它们生成后就被写到外存中。 (2)按归并树模式，把(1)生成的初始归并段加以归并，一趟趟扩大归并段和减少归并段数，直到最后归并成一个大归并段
38、为止。 例如：设有一个包含 4500 个记录的输入文件，现用一台其内存至多可容纳 750 个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳 250 个记录，这样全部记录可存储在 4500/250=18 个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中可用于排序的存储区域能容纳 750 个记录，所以内存中恰好能存 3 个块的记录。在外排序一开始，把 1 8 块记录每 3 块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到 6 个初始归并段。然后一趟一趟进行归并排序，如图 110 所示。13.图 12 中计算机硬件系统基本组成部件、
39、和的名称分别是( )。 （分数：2.00）A.控制器、运算器、存储器、输入设备、输出设备B.运算器、控制器、存储器、输入设备、输出设备 C.运算器、存储器、控制器、输入设备、输出设备D.运算器、控制器、存储器、输出设备、输入设备解析：解析：图中实线框为 CPU，而 CPU 包含五大部件中的运算器和控制器，排除 C 选项。控制器为计算机提供工作统一的时钟及其发出各种控制命令来协调计算机的各部件自动地工作，所以控制器应该与其他四大部件相连，可得为运算器，为控制器。最后，根据数据的流向可以判断，为输入设备，为输出设备。剩下为存储器。14.已知小写英文字母“a”的 ASC码值为 61H，现字母“g”被
40、存放在某个存储单元中，若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是( )。（分数：2.00）A.167HB.E6HC.67HD.E7H 解析：解析：由于“a”的 ASC码值为 61H，而“g”是第 7 个字母，所以可以得到“g”的 ASC码值应为 61H +6=67H=1100111B。现在“g”的 ASC码值中有 5 个“1”，按照偶校验的规则，应该在最高位上添加一个 l，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进制数为 E7H (1110 0111)。15.页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB，地址变换过程
41、如图 13 所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数物理地址 a 应为( )。（分数：2.00）A.33220 B.8644C.4548D.2500解析：解析：本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统管理中一逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为 4KB，逻辑地址 8644 除以 4096，取整为 2，取余为 452。页号为 2，查页表得物理块号为 8。因此，a 的有效地址为 84096+452=33220。16.下列关于 ROM 和 RAM 的说法中，正确的是( )。CDROM 与 EPROM 都采用随机存储方式SRAM 读后不需要刷新，而 DRAM 读后需要刷新Cache 可以由 ROM 或者 RAM 组成（分数：2.00）A.、和B.仅和C.仅D.仅 解析：解析：对于选项：首先，ROM 和 RAM 都是采用随机存取方式。由于 EPROM 属于 ROM，故采用随机存取方式。而 CDROM 属于光盘，为非随机存储，故错误。 对于选项：SRAM 采用双稳态触发器来记忆信息，因此不需要刷新；而 DRAM 采用电容存储电荷的原理来存储信息，只能维持很短的时间，因此需要刷新，故正确。 对于选项：Cache 需要有信息的输入和输出，而 ROM 只可读，不可输入，
