1、计算机专业（基础综合）模拟试卷 66 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为( )。Void fun(int n)int i，j，k；for(i=1，iprior=L&L-next=L线性表的插入和删除总是伴随着大量数据的移动 只有删除静态链表的尾结点才不需要移动元素若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续（A）仅（B）仅 、（C）仅 、（D）、和3 循环队列用数组 A0，m-1存放其元素值，已知其头尾指针分别是
2、front 和rear(且队尾指针 rear 指向队尾元素的下一个元素 )，则当前队列中的元素个数是 ( )。（A）(rear-front+m)m（B） (rearfront+1)m（C） rearfront 一 1（D）rearfront4 下列关于二叉树的叙述中正确的是( )。对于任何一棵二叉树，叶子结点数都是度为 2 的结点数加 l二叉树的左右子树不可以任意地交换二叉树只适合使用链式结构存储，不可能用顺序结构存储结点按层序编号的二叉树，第 i 个结点的左孩子 (假设存在)的编号为 2i（A）仅、（B）仅 （C）仅 、（D）仅、5 已知一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因
3、子均为 0，则该树共有结点总数为( ) 。（A）2 k-1-1（B） 2k-1+1（C） 2k1（D）2 k+16 根据使用频率为 5 个字符设计的赫夫曼编码不可能是( )。（A）000，001，010，011，1（B） 0000，0001，001，01，1（C） 000，001，01，10，11（D）00，100，101，110，1117 在具有 n 个顶点的图 G 中，若最小生成树不唯一，则 ( )。G 的边数一定大于 n1 G 的权值最小的边一定有多条 G 的最小生成树代价不一定相等（A）仅（B）仅 、（C）仅 、（D）仅8 以下哪些方法可以判断出一个有向图是否有环( )。深度优先遍历
4、求最短路径 拓扑排序 求关键路径（A）仅、（B）仅 、（C）仅 、（D）、和9 在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是( )。（A）28，36，18，46，35（B） 18，36，28，46，35（C） 46，28，18，36，35（D）46，36，18，28，3510 排序趟数与序列的原始状态无关的排序方法是( )。直接插入排序 简单选择排序 冒泡排序 基数排序（A）仅、（B）仅 、（C）仅 、（D）仅、11 下列关于外部排序说法正确的是( )。（A）内存与外设交换信息的时间只是外排序总时间的一小部分（B）外部排序就是在外存上进行排序，无需内存参与（C）败者
5、树是一棵完全二叉树（D）置换一选择排序得到的初始归并段长度一定相等12 图 11 中计算机硬件系统基本组成部件、和 的名称分别是( )。（A）控制器、 运算器、存储器、输入设备、输出设备（B） 运算器、控制器、 存储器、输入设备、 输出设备（C） 运算器、存储器、 控制器、输入设备、 输出设备（D）运算器、 控制器、存储器、输出设备、输入设备13 已知小写英文字母“a”的 ASC码值为 61H，现字母“g” 被存放存某个存储单元中，若采用偶校验(假设最高位作为校验位)，则该存储单元中存放的十六进制数是( )。（A）167H（B） E6H（C） 67H（D）E7H14 页式存储系统的逻辑地址是由
6、页号和页内地址两部分组成的。假定页面的大小为 4KB，地址变换过程如图 1-2 所示，图中逻辑地址用十进制数表示。逻辑地址经过变换后，十进制数物理地址 a 应为( ) 。（A）33 220（B） 8644（C） 4548（D）250015 下列关于 ROM 和 RAM 的说法中，正确的是( )。CDROM 与 EPROM 都采用随机存储方式 SRAM 读后不需要刷新，而 DRAM 读后需要刷新 Cache 可以由 ROM 或者 RAM 组成（A）、和（B）仅 和（C）仅 （D）仅16 下列关于 Flash 存储器的说法正确的是( )。（A）Flash 存储器属于易失性存储器（B） Flash
7、存储器不具备写功能（C） Flash 存储器是不可擦除的存储器（D）Flash 存储器同时具有 ROM 和 RAM 的功能17 某机器采用 16 位单字长指令，采用定长操作码，地址码为 5 位，现已定义 60条二地址指令，那么单地址指令最多有( )条。（A）4（B） 32（C） 128（D）25618 指令( ) 从主存中读出。（A）总是根据程序计数器(PC)（B）有时根据 PC，有时根据转移指令（C）根据地址寄存器（D）有时根据 PC，有时根据地址寄存器19 当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断请求的是( )。外部事件 Cache 浮点运算下溢 浮点运算上
8、溢（A）仅、（B）仅 、（C）仅 、（D）仅、20 某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 16001200 像素，颜色深度为 24 位，若不采用压缩存储技术，使用内部存储器最多可以存储( )张照片。（A）12（B） 25（C） 13（D）2321 下面关于 PCI 总线的描述中，错误的有 ( )。PCI 总线是一个与处理器性能相关的高速外围总线PCI 总线可对传输信息进行奇偶校验 PCI 设备一定是主设备系统中允许有多条 PCI 总线（A）仅、（B）仅 、（C）仅 和（D）仅、22 下列说法正确的是( )。（A）在统一编址方式下，访问主存储器和访问 IO 设备是通过不同的指
9、令来区分的（B）计算机的外部设备就是指输入和输出设备（C）中断隐指令属于程序控制型指令（D）在中断服务程序中，恢复现场之前需要关中断23 操作系统通常为用户提供了多种使用接口，其中不包括( )。（A）图标、菜单等用户图形界面接口（B）汇编语言（C）批命令，如 shell（D）系统调用命令24 以下服务中，能发挥多线程系统的特长的是( )。利用线程并发地执行矩阵乘法运算Web 服务器利用线程请求 HTTP 服务键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作（A）、（B） 、（C） 、（D）、25
10、 现在有 3 个同时到达的作业 J1、J2 和 J3，它们的执行时间分别为 T1、T2 和T3，且 T1T2 T3。如果该系统中有两个 CPU，各自按照单道方式运行且采用短作业优先算法，则平均周转时间是( )。（A）(T1+T2+T3) 3（B） (2T1+T2+T3)3（C） (T1+2T2+T3)3（D）(2T1+T2+T3)3 或 (T1+2T2+T3)326 一个正在访问临界资源的进程由于申请等待 IO 操作而被中断时( )。（A）可以允许其他进程进入与该进程相关的临界区（B）不允许其他进程进入任何临界区（C）可以允许其他就绪进程抢占处理器，继续运行（D）不允许任何进程抢占处理器27
11、某分页存储管理系统中，设页面尺寸为 4KB，某进程的页表数据 (块号)为：8、9、10、15、18、20、21、22、23，则该进程的逻辑地址 0x05AF8H 对应的物理地址是( )。（A）0x5000（B） 0x5AF8（C） 0x12AF8（D）0x14AF828 某虚拟存储器的用户编程空间共 32 个页面，每页 1KB，主存为 16KB。假定某时刻用户页表中已调入主存的页面的虚页号和物理页号对照表如表 11 所示，则与表 12 十六进制虚地址对应的物理地址为( )。（A）1E5C，2A5C（B） 1E5C，缺页中断（C） 125C， 2A5C（D）125C，缺页中断29 假定有一个请求
12、分页存储管理系统，测得系统各相关设备的利用率如下：CPU利用率为 10，磁盘交换区为 997：其他 IO 设备为 5。试问：下面措施中将可能改进 CPU 利用率的是( )。增大内存的容量 增大磁盘交换区的容量 减少多道程序的道数 增加多道程序的道数 使用更快速的磁盘交换区 使用更快速的CPU（A）、（B） 、（C） 、（D）、30 如果文件需要采用随机存取，且文件大小不固定，则应采用( )物理结构。（A）直接（B）索引（C）随机（D）顺序31 一个交叉存放信息的磁盘，信息存放方式如图 13 所示。每个磁道有 8 个扇区，每个扇区 512B，旋转速度为 3000rmin。假定磁头已在读取信息的磁
13、道上，0 扇区转到磁头下需要 12r，且设备对应的控制器不能同时进行输入输出，在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2，问依次读取一个磁道上所有的扇区的数据到内存平均传输速度为( )。（A）571KBs（B） 671KBs（C） 771 KB s（D）871KBs32 为了使并发进程有效输入输出，应该采用( )结构的缓冲技术。（A）双缓冲（B）环形缓冲（C）缓冲池（D）多队列轮转33 计算机网络可分为通信子网和资源子网，下列属于通信子网的是( )。网桥 交换机 计算机软件 路由器（A）、（B） 、（C） 、（D）、34 用 PCM 对语音进行数字化，如果将声音分为 12
14、8 个量化级，一个典型的电话通道是 4kHz，那么一路语音需要的数据传输率为( )。（A）56kbits（B） 64kbits（C） 128kbits（D）1024kbits35 在可靠传输机制中，发送窗口的位置由窗口前沿和后沿的位置共同确定，经过一段时间，发送窗口的后沿的变化情况可能为( )。原地不动 向前移动 向后移动（A）、（B） 、（C） 、（D）都有可能36 在 IPv6 协议中，一个数据流可以由( )进行标识。（A）源地址、目的地址和流名称（B）源地址、目的地址和流标号（C）源地址、端口号和流标号（D）MAC 地址、端口号和流名称37 假定在一个局域网中计算机 A 发送了 ARP
15、请求分组，希望找出计算机 B 的硬件地址，局域网上的所有计算机都能接收到这个广播发送的 ARP 请求分组。这时由( )使用 ARP 响应分组进行回应。（A）计算机 A（B）计算机 B（C）路由器（D）不一定38 一个有 50 个路由器的网络，采用基于距离一向量的路由选择算法，路由表的每个表项长度为 6B，每个路由器都有 3 个邻接路由器，每秒与每个邻接路由器交换1 次路由表，则每条链路上由于路由器更新路由信息而耗费的带宽为( )。（A）2400bits（B） 3 600bits（C） 4800bits（D）6000bits39 设某 TCP 的拥塞窗口的慢启动门限值初始为 8(单位为报文段，且
16、最大报文段长度为 1KB)，当拥塞窗口上升到 12 时，网络会发生超时。按照以上给出的条件，第12 次传输时，拥塞窗口的大小为( )。（A）5（B） 6（C） 7（D）840 关于 FTP 的工作过程，下面说法错误的是 ( )。（A）每次数据传输结束后，FTP 服务器同时释放 21 和 20 端口（B） FTP 的数据连接是非持久的（C） FTP 的文件传输需要两条 TCP 连接（D）FTP 可以在不同类型的操作系统之间传送文件二、综合应用题41-47 小题，共 70 分。41 带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径
17、不止一条，在找到一条最短路径的同时，还需要输出不同最短路径的条数。现有一种解决该问题的方法：(1)初始化结点集合 S 为仅包含源结点 s；用一个整型数组 Counterv来记录从结点 s 到结点 v 的最短路径的条数；各结点 Counter 的初始值为 0。(2)从未加入 S 的结点中选择当前距离最小的结点 v(“当前距离”是指从 s 到 v 且仅经过 S 中结点的最短距离)，将其加入 S。(3)对每个与 v 相邻的结点 w，若 w 不在 S 内，检查： 若 v 的加入使得 w 的当前距离变小，则更新 w 的当前距离为(v，w)的边长与 v 的当前距离之和，并日令 Counterw=1。 若
18、v 的加入是 s 到 w 的长度相同的另一条最短路径，则 Counterw+；(4)重复步骤 (2)和(3)，直到所有结点都被收录到集合 S 中。 若该方法可行，请证明之；否则，请举例说明。41 假设有一带头结点的循环双链表表示的线性表 L=(a1，a 2，a n-1，a n)。 设计在时间和空间上都尽可能高效的算法，将线性表 L 改造成L=(a1，a 3，a n， a4，a 2)。要求：42 给出算法的基本设计思想。43 根据基本设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。44 说明你所设计算法的时间复杂度与空间复杂度。44 某字长为 8bit 的计算机中，x
19、和 y 为无符号整数，已知 x=68，y=80，x 和 y 分别存放在寄存器 A 和 B 中。请回答下列问题(要求最终用十六进制表示二进制序列 )。45 寄存器 A 和 B 中的内容分别是什么?46 若 x 和 y 相加后的结果存放存寄存器 C 中，则寄存器 C 中的内容是什么? 运算结果是否正确? 此时，零标志 ZF 是什么?加法器最高位的进位 Cn 是什么?47 若 x 和 y 相减后的结果存放在寄存器 D 中，则寄存器 D 中的内容是什么?运算结果是否正确? 此时，零标志 ZF 是什么?加法器最高位的进位 Cn 是什么?48 无符号整数加减运算时，加法器最高位进位 Cn 的含义是什么?它
20、与进借位标志 CF 的关系是什么?49 无符号整数一般用来表示什么信息?需要对无符号整数的运算结果判断溢出吗?为什么?49 某双总线模型机如图 83 所示。双总线分别记为 B1 和 B2；图 83 中连线的方向标明数据通路及流向，并注有相应的控制信号(微命令)；A 、B、C、D 为 4 个通用寄存器；X 为暂存器；M 为多路选择器，用于选择进入暂存器 x 的数据，存储器为双端口，分别面向总线 B1 和 B2。50 写出该模型机的取指令周期流程。51 分别指出指令 ADD(A)，(B) 中源操作数和目的操作数的寻址方式，并写出该指令的执行流程。52 分别指出指令 ADD(A)，#N 中源操作数的
21、寻址方式，并写出该指令的执行流程。53 写出指令 JMP Label(该指令完成 (PC)+N(PC)，其中 N 为指令提供的位移量)的执行流程。54 给出一个单车道的简易桥，如图 84 所示。车流如箭头所示。桥上不允许有两车交会，但允许同方向车依次通行(即桥上可以有多个同方向的车)。该桥最大可载重 5 辆汽车。用 P，V 操作实现交通管理，以防桥上交通堵塞。54 设正在处理器上执行一个进程的页表如表 8 一 1 所示。表中的虚页号和物理块号是十进制数，起始页号(块号)均为 0。所有地址均是存储器字节地址。页的大小为 1024B。若发生缺页中断，使用 LRU 页面置换算法将缺页调入再进行地址变
22、换，页表中访问字段记录本页最近已有多长时间未被访问。55 详述在设有快表的请求分页存储器管理系统中，一个虚地址转换成物理内存地址的过程。56 根据给出的某进程的页表，系统给该进程分配的最大内存物理块数为 3，进程先后使用下面两个虚地址访问内存，其对应的物理内存地址分别是多少?请详述整个地址变换过程，并参照给出的页表，画出每次操作后的页表。 a)4475(写操作) b)1197(读操作 )56 设有 4 台主机 A、B、C 和 D 都处在同一物理网络中，它们的 IP 地址分别为19215528112、19215528120、19215528135 和19215528202，子网掩码都是 2552
23、55255224，请回答：57 该网络的 4 台主机中哪些可以直接通信?哪些需要通过设置路由器才能通信? 请画出网络连接示意图，并注明各个主机的子网地址和主机地址。58 若要加入第 5 台主机 E，使它能与主机 D 直接通信，则其 IP 地址的范围是多少?59 若不改变主机 A 的物理位置，而将其 IP 改为 19215528168，则它的直接广播地址和本地广播地址各是多少?若使用本地广播地址发送信息，请问哪些主机能够收到?60 若要使该网络中的 4 台主机都能够直接通信，可采取什么办法?计算机专业（基础综合）模拟试卷 66 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分
24、。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 首先抓基本运算语句，即 k=5*k；设其执行时间为 T(n)。对于 j 每循环一次，该语句的执行次数为 m，有 5mn，即 mlog5n。所以， T(n)=i=1nj=1nm=mi=1nj=1n=mn2=n2log5n=O(n2log5n)2 【正确答案】 A【试题解析】 ：循环双链表为空时头结点体现如图 1-6 所示。可见，当满足 Lprior=L&Lnext=L 时，双链表为空，并且循环双链表与循环单链表一样，没有空指针域，所以正确。 ：链表也是线性表，链表的插入和删除操作不需要大量的数据移动，所
25、以错误。 ：静态链表尽管使用的是数组存储方式，但是数据之间是靠指针(游标)相互关联的，故不管是删除静态链表中的哪一个结点，都不需要移动元素，只需要修改指针即可，所以错误。 ：线性表采用链表存储，前驱和后继之间的联系需要依靠由前驱指向后继的指针，而与前驱和后继在内存中的物理位置无关，因此对于整条链表的存储，不需要划分一块连续的存储空间；但将链表中的结点挨个连续存储在一片空间中也未尝不可。对于线性表的链式存储，连续或者不连续的存储空间都能满足要求，所以错误。3 【正确答案】 A【试题解析】 因为是循环队列，所以应该分 rearffont 和 rearfront 两种情况来讨论。 (1)当 rear
26、front 时，队列中元素个数为 rearfront=(rearfront+m)m 因为 0rear-frontm，所以 rearfront+m 与 m 取余后结果还是 rear-front。(2)当 rearfront 时，队列中元素个数为 m-(frontrear)=rearfront+m=(rearfront+m)m 因为 0rearfront+mm，所以 rear-front+m 与m 取余后结果还是 rearfront+m。综合(1)、(2)可知，A 选项正确。知识点总结：循环队列的两大状态和两大操作以及三大重点提醒。(1)两大状态(数学式子表示)。1) 队空状态：qrear=qfr
27、ont 。2) 队满状态：(q rear+1)MAX=qfront。(2)两大操作。 1)元素 x 进队操作(移动队尾指针)。qrear=(qrear+1)MAX；qdataqrear=x；2)元素 x 出队操作(移动队头指针)。 qfront=(qu front+1)MAX；x=qdataqfront；重点提醒 1：有些教材说循环队列队尾指针指向队尾元素，有些教材说循环队列队尾指针指向队尾元素的下一个元素。不同的说法可能导致很多题目的答案总是相差 1。所以如果在考研试卷中碰到，且题目没有说明(不过像考研试卷一般都会说明)，一律认为是循环队列队尾指针指向队尾元素的下一个元素。重点提醒 2：元素
28、入队时，先移动指针，后存入元素；元素出队时，也是先移动指针，再取出元素。有些书上可能有不同的顺序，其实本质是一样的，考生只需去适应一种写法，对于程序设计题目已经足够。对于选择题，则可根据题目描述确定是先存取元素，再移动指针，还是其他处理顺序。重点提醒 3：循环队列的队尾指针、队头指针、队中元素个数，知道其中任何两者均可算出第三者。4 【正确答案】 B【试题解析】 ：的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目时一定要先想到这种特殊情况，所以错误。 ：二叉树的左右子树是有顺序的，不能随意交换，所以正确。 ：一般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用
29、顺序结构存储，所以错误。 ：该结论只对完全二叉树才成立，所以错误。 综上所述，只有正确。5 【正确答案】 C【试题解析】 每个非叶子结点的平衡因子均为 0，说明了该平衡二叉树为满二叉树，所以结点总数为 2k 一 1。 总结：(1) 设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，则 N 0=0，N 1=1，N 2=2，N h=Nh-1+Nh-2+1 例如，深度为 5 的平衡二叉树中含有最少的结点数为 N5=12。 (2)二叉排序树的查找效率取决于其深度。对于结点个数相同的二叉排序树，平衡二叉树的深度最小，因此效率最高。6 【正确答案】 D【试题解析】 赫夫曼树中只有度为 O 或 2
30、的结点，由 D 选项可以画出对应的二叉树，如图 1-7 所示。 由赫夫曼树的性质可知，树中不应该含度为 1 的结点，因此D 选项不可能。7 【正确答案】 A【试题解析】 最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一定相等，故错误；既然最小生成树不唯一，并且最小生成树的边都为 n-1 条，说明图 G 的边数一定会大于 n 一 1，故正确；最小生成树不唯一，和 G 的权值最小的边的条数没有任何关系，故 错误。8 【正确答案】 A【试题解析】 有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个顶点 v 出发的遍历，在 dfs(v)结束之前
31、出现一条从顶点 jv的边，由于 j 在生成树上是 v 的子孙，则图中必定存在包含 v 和 j 的环，因此可以；用拓扑排序的方法，在拓扑排序过程中，每次要删去一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环，因此正确。而最短路径和关键路径(建立在无环的 AOE 网的基础之上)都是不可以判断的。补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图一定有什么?想必 90以上的考生都会选择有环，但是没有环这个选项，只有顶点数目大于 l 的强连通分量这个选项，此时考生必须知道顶点数目大于 1 的强连通分量就表明有环。9 【正确答案】 D【试题
32、解析】 可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线图如图 1 一 8 所示。 A 选项中28 的右子树中出现了小于它的 18，不满足二叉排序树的规定，排除。 B 选项中 36的左子树中出现了大于它的 46，不满足二叉排序树的规定，排除。 C 选项中 28 的左子树中出现了大于它的 36，不满足二叉排序树的规定，排除。补充：在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于折半查找的时间复杂度，即 0(log2n)。平衡二叉树的查找效率最高，因为二叉树的查找效率取决于二叉树的高度，对于结点个数相同的二叉树，平衡二叉树
33、的高度最小。10 【正确答案】 B【试题解析】 直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为n 一 1(n 为元素数) 。简单选择排序：每趟排序都是选出一个最小(或最大)的元素，所以排序趟数固定为 n1(n 为元素数) 。交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为 d(d 为组成元素的关键字位数)。 综上所述，、都是无关的，所以选 B。11 【正确答案】 C【试题解析】 A：影响外排序时间的主要因素就是内存与外设交换信息的总次数，所以 A 错误。 B：外部排序也是在内存上进行排序，只不过需要分为
34、多步而已，所以 B 错误。 C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以 C正确。 补充知识点：败者树和堆有什么区别? 提示：外排序中败者树和堆排序的区别在于： (1)败者树是在双亲结点中记下刚进行完的这场比赛的败者，而让胜者去参加更加高一层的比赛，便可得到一棵败者树。而堆排序可看做一种胜者树，即双亲结点表示其左右孩子中的胜者。 (2)在败者树中，参加比较的 n 个关键字全部为叶子结点，双亲即为其左、右子女的败者，败者树中结点总数为 2n 一 1，加上冠军结点恰好为 2n。而堆是由 n 个关键字组成的完全二叉树，每个关键字作为树中的一个结点，根是 n 个关键字中的胜者，树中结点总数
35、为 n。 D ：使用置换-选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的过程也可以得到答案，所以 D 错误。 外排序的基本过程： 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为以下两个阶段： (1)建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中。 (2)按归并树模式，把(1)生成的初始归并段加以归并，一趟趟扩大归并段和减少归并段数，直到最后归并成一个大归并段为止。 例如：设有一个包含 4500 个记录的输入文件，现用一台其内存至多可容纳 750 个记录的计算机
36、对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳 250 个记录，这样全部记录可存储在 4500250=18 个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中可用于排序的存储区域能容纳 750 个记录，所以内存中恰好能存 3 个块的记录。在外排序一开始，把 18 块记录每 3 块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到 6 个初始归并段，然后一趟一趟进行归并排序，如图 1-9 所示。12 【正确答案】 B【试题解析】 图中实线框为 CPU，而 CPU 包含五大部件中的运算器和控制器，排除 C 选项。控制器为计算机提供工作统一的时钟及其
37、发出各种控制命令来协调计算机的各部件自动地工作，所以控制器应该与其他四大部件相连，可得为运算器，为控制器。最后，根据数据的流向可以判断， 为输入设备，为输出设备。剩下为存储器。13 【正确答案】 D【试题解析】 由于“a”的 ASC码值为 61H，而“g”是第 7 个字母，所以可以得到“g”的 ASC码值应为 61H+6=67H=1100111B。现在 “g”的 ASC码值中有 5 个“1”，按照偶校验的规则，应该在最高位上添加一个 1，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进制数为 E7H(11100111)。14 【正确答案】 A【试题解析】 本题考查的是页式存储系统管理
38、中的地址变换知识。在页式存储系统管理中，逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为 4KB，逻辑地址 8644 除以 4096，取整为 2，取余为 452。页号为2，查页表得物理块号为 8。因此，a 的有效地址为 84096+452=33220。15 【正确答案】 D【试题解析】 对于选项：首先，ROM 和 RAM 都是采用随机存取方式。由于EPROM 属于 ROM，故采用随机存取方式。而 CDROM 属于光盘，为非随机存储，故错误。 对于选项：SRAM 采用双稳态触发器来记忆信息，因此不需要刷新；而 DRAM 采用电容存储电荷的原理来存储信息，只能维持很短的时
39、间，因此需要刷新，故正确。对于选项：Cache 需要有信息的输入和输出，而 ROM 只可读，不可输入，因此不能作为 Cache，故错误。16 【正确答案】 D【试题解析】 Flash 存储器是一种具有较高存储容量、较低价格、非易失性、可在线擦除与编程的新一代读写存储器。从基本工作原理上看，Flash 存储器属于ROM。型存储器，但由于它又可以随时改写其中的信息，所以从功能上看，它又相当于随机存储器(RAM)。 Flash 存储器与其他存储器的区别总结，如表 1-6 所示。17 【正确答案】 A【试题解析】 首先可以计算出操作码字段的长度为 1655=6。所以一共可以定义 26=64 条指令，既
40、然二地址指令占了 60 条，且是定长操作码，故单地址指令最多可以有 6460=4 条，所以选 A。 如果此题将条件改为采用不定长操作码，答案又是什么?分析如下： 如果采用不定长(扩展)操作码，每条二地址指令可扩展为 32条单地址指令，那么单地址指令最多有 324=128 条。18 【正确答案】 A【试题解析】 指令总是根据程序计数器(PC)从主存中读出(一定要记住)。可能考生会想到无条件转移指令的情况，认为不一定总是根据 PC 读出。实际上，正确的执行顺序是这样的，当前指令正在执行时，其实 PC 已经是下一条指令的地址了，如果遇到了无条件转移指令，则只需要简单地把跳转的地址覆盖 PC 的内容就
41、可以了，最终的结果还是指令需要根据程序计数器从主存读出。19 【正确答案】 C【试题解析】 ：外部事件是可以提出中断请求的。例如通过敲击键盘来终止现在正在运行的程序，就可以看做一个中断，所以可以。 ：Cache 是属于存储设备，不能提出中断请求，所以不可以。 、：浮点运算下溢，可以当做机器零处理，不需要中断来处理；而浮点运算上溢，必须中断来做相应的处理，所以不可以，可以。20 【正确答案】 D【试题解析】 24 位图像是典型的 JPG 图片，RGB 各占 8 位，合计 3B。未经压缩的图片大小=160012003B55MB，128MB55MB=233，所以内置的存储空间最多可存储 23 张照片
42、。21 【正确答案】 D【试题解析】 PCI 总线与 CPU 及时钟频率都无关，故错误；PCI 总线支持即插即用并且可对数据和地址进行奇偶校验，并且 PCI 总线采用猝发传送方式，故正确；主设备指获得总线控制权的设备，所以 PCI 设备不一定都是主设备，故错误；系统中肯定允许有多条 PCI 总线，以此来提升计算机的效率，故 正确。22 【正确答案】 D【试题解析】 A：在统一编址方式下，访问主存储器和访问。 IO 设备是通过不同的地址码来区分的；在独立编址方式下，访问主存储器和访问 IO 设备是通过不同的指令来区分的，所以 A 错误。B：除主机外的硬件装置统称为外围设备或外部设备，包括输入输出
43、设备和外存储器，所以 B 错误。C：中断隐指令并不是一条真正的指令，因此不可能把它预先编入程序中，只能在响应中断时由硬件直接控制执行。它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断隐指令不在指令系统中，不属于程序控制指令，所以 C 错误。补充：在中断周期中，由中断隐指令自动完成保护断点、寻找中断服务程序入口地址以及硬件关中断的操作。D：为了防止在恢复现场过程中又出现新的中断，在恢复现场前需要增加关中断操作，所以 D 正确。提醒：请注意区分，保护现场前的关中断由中断隐指令完成，但是恢复现场前的关中断是由中断服务程序完成的。23 【正确答案】 B【试题解析】 OS 提供用户与计算机硬件
44、系统之间的接口，其中包括以下 3 种方式：(1)命令方式。这是指由 OS 提供了一组联机命令(语言)，用户可通过键盘输入有关命令，来直接操作计算机系统。(2)系统调用方式。 OS 提供了一组系统调用，用户可在自己的应用程序中通过相应的系统调用，来操作计算机。(3)图标、窗口方式。用户通过屏幕上的窗口和图标来操作计算机系统和运行自己的程序。 因此本题选 B。24 【正确答案】 D【试题解析】 在多线程操作系统中，通常一个进程中包括多个线程，每个线程都是作为利用 CPU 的基本单位，是花费最小开销的实体。线程具有下述属性：(1)轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的，即能
45、保证独立运行的资源。它包含了一个线程 ID、一个程序计数器、一个寄存器组和一个堆栈。(2)独立调度和分派的基本单位。(3)可并发执行。(4)共享进程资源。在同一进程中的各个线程，都可以共享该进程所拥有的资源，包括共享代码段、数据段以及其他的操作系统资源(如打开的文件)等。多线程最大的优点就是并发执行。在 4 个服务中，只有键盘操作是无法并发执行的，因为整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处理整个系统的键盘操作，所以选择 D。25 【正确答案】 B【试题解析】 J1、J2 和 J3 同时在 0 时刻到达，按短作业优先算法，选择 J1 和J2 执行，则
46、J1 和 J2 等待时间为 0。又因为 T1T2，所以 J1 先于 J2 完成，即在T2 时刻，释放 CPU，J3 开始，则 J3 的等待时间为 T1。然后 J2 完成，最后 J3 完成。J1 周转时间为 T1。J2 周转时间为 T2。J3 周转时间为 T1+T3。所以平均周转时间为(2T1+T2+T3)3。知识点回顾： 周转时间=等待时间+运行时间= 结束时间-到达时间26 【正确答案】 C【试题解析】 如果允许其他进程进入临界区，就无法完成对临界资源的互斥访问，所以不允许其他进程进入与该进程相关的临界区，排除 A，但可以允许其他进程进入与该进程无关的临界区，排除 B，同时排除 D。就绪进程
47、就是获得了除处理机之外所有资源的进程，即不需要访问题干所提及的临界资源，因此是允许其抢占处理器，继续运行，因此本题选 C。27 【正确答案】 D【试题解析】 05AF8H 对应的十进制数为 23288，23288=54K+2808 ，这样对应的是 5 号物理块，物理块号为 20，物理地址为 204K+2808=84 728=0x14AF8。28 【正确答案】 D【试题解析】 每页 1KB，默认字长为 1B，那么页内地址需要 10 位，则剩下的 6位为虚页号。计算过程如表 1 一 7 所示。29 【正确答案】 B【试题解析】 正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入和
48、换出过程，可提高 CPU 利用率。错误。因为系统实际已处于频繁地换入和换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量无用。正确。因为从给定的条件中磁盘交换区的利用率为 997，说明系统现在已经处于频繁地换入和换出过程中，可减少主存中的程序。错误。系统处于频繁地换入和换出过程中，再增加主存中的用户进程数，只能导致系统的换入和换出更频繁，使性能更差。错误。因为系统现在处于频繁地换入和换出过程中，即使采用更快的磁盘交换区，其换入和换出频率也不会改变，因此没用。错误。系统处于频繁地换入和换出过程中，CPU 处于空闲状态，利用率不高，提高 CPU 的速度无济于事。 综上所述，本题选 B。30 【正确答案】 B【试题解析】 直接存取方法在文件大小不固定的情况下容易形成碎片，因此排除A。 索
