计算机学科专业基础考研综合模拟试题及详细解析

1、计算机科学与技术学科联考计算机学科专业基础模拟试题（第一套）一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中， 只有一个选项最符合试题要求。1假设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度为（）。void fun(int n) int i,j,k;for(i=1;i=n;i+) for(j=1;j=n;j+)k=1;while(kprior=L&L-next=L线性表的插入和删除总是伴随着大量数据的移动 只有删除静态链表的尾结点才不需要移动元素 若线性表采用链式存储结构，要求内存中可用存储单元的地址必须不连续 A仅B仅、C仅、D、和3循环队

2、列用数组 A0.m-1存放其元素值，已知其头尾指针分别是 front 和 rear（且队 尾指针 rear 指向队尾元素的下一个元素），则当前队列中的元素个数是（）。A(rear-front+m)%mB(rear-front+1)%mCrear-front-1Drear-front 4下列关于二叉树的叙述中正确的是（）。 对于任何一棵二叉树，叶子结点数都是度为 2 的结点数加 1 二叉树的左右子树不可以任意地交换第 4 页（共 32 页）二叉树只适合使用链式结构存储，不可能用顺序结构存储 结点按层序编号的二叉树，第 i 个结点的左孩子（假设存在）的编号为 2i A仅、B仅C仅、D仅、5已知一棵

3、深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树共有结 点总数为（）。A2k-1-1B2k-1+1C2k-1D2k+16根据使用频率为 5 个字符设计的赫夫曼编码不可能是（ ）。 A000，001，010，011，1B0000，0001，001，01，1 C000，001，01，10，11D00，100，101，110，1117在具有 n 个顶点的图 G 中，若最小生成树不唯一，则（）。 G 的边数一定大于 n-1G 的权值最小的边一定有多条 G 的最小生成树代价不一定相等A仅B仅、C仅、D仅8以下哪些方法可以判断出一个有向图是否有环（）。 深度优先遍历求最短路径拓扑排序求

4、关键路径A仅、B仅、C仅、D、和 9在一棵二叉排序树上，查找关键字为 35 的结点，依次比较的关键字有可能是（）。 A28，36，18，46，35B18，36，28，46，35C46，28，18，36，35D46，36，18，28，35 10排序趟数与序列的原始状态无关的排序方法是（ ）。 直接插入排序简单选择排序冒泡排序基数排序A仅、B仅、C仅、D仅、 11下列关于外部排序说法正确的是（）。 A内存与外设交换信息的时间只是外排序总时间的一小部分 B外部排序就是在外存上进行排序，无需内存参与 C败者树是一棵完全二叉树D置换-选择排序得到的初始归并段长度一定相等12图 1-1 中计算机硬件系统基

5、本组成部件、和的名称分别是（）。A控制器、运算器、存储器、输入设备、输出设备B运算器、控制器、存储器、输入设备、输出设备 C运算器、存储器、控制器、输入设备、输出设备 D运算器、控制器、存储器、输出设备、输入设备图 1-1 计算机硬件系统基本组成部件13已知小写英文字母“a”的 ASCII 码值为 61H，现字母“g”被存放在某个存储单元中， 若采用偶校验（假设最高位作为校验位），则该存储单元中存放的十六进制数是（）。A167HBE6HC67HDE7H14页式存储系统的逻辑地址是由页号和页内地址两部分组成的。假定页面的大小为 4KB， 地址变换过程如图 1-2 所示，图中逻辑地址用十进制数表示

6、。逻辑地址经过变换后，十进制数 物理地址 a 应为（）。A33220B8644C4548D2500图 1-2 页式存储系统的逻辑地址变换过程15下列关于ROM和RAM的说法中，正确的是（）。 CD-ROM 与EPROM都采用随机存储方式 SRAM读后不需要刷新，而DRAM读后需要刷新 Cache可以由ROM或者RAM组成A、和B仅和C仅D仅16下列关于 Flash 存储器的说法正确的是（）。AFlash 存储器属于易失性存储器BFlash 存储器不具备写功能CFlash 存储器是不可擦除的存储器DFlash 存储器同时具有 ROM 和 RAM 的功能17某机器采用 16 位单字长指令，采用定长

7、操作码，地址码为 5 位，现已定义 60 条二地 址指令，那么单地址指令最多有（）条。A4B32C128D25618指令（）从主存中读出。 A总是根据程序计数器（PC） B有时根据 PC，有时根据转移指令 C根据地址寄存器D有时根据 PC，有时根据地址寄存器19当有中断源发出请求时，CPU 可执行相应的中断服务程序，以下可以提出中断请求的 是（）。外部事件Cache浮点运算下溢浮点运算上溢A仅、B仅、C仅、D仅、20某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 16001200 像素，颜色深度 为 24 位，若不采用压缩存储技术，使用内部存储器最多可以存储（）张照片。A12B25C

8、13D2321下面关于 PCI 总线的基描述中，错误的有（）。 PCI总线是一个与处理器性能相关的高速外围总线 PCI总线可对传输信息进行奇偶校验 PCI设备一定是主设备 系统中允许有多条PCI总线A仅、B仅、C仅和D仅、 22下列说法正确的是（）。A在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的 B计算机的外围设备就是指输入和输出设备 C中断隐指令属于程序控制型指令 D在中断服务程序中，恢复现场之前需要关中断 23下列关于分时操作系统和实时操作系统说法错误的是（）。 分时操作系统的时间片固定，那么用户数越多，响应时间越长在主存容量为 M 的多用户分时操作系统中，当

9、注册用户数为 N 时，每个用户拥有的 主存空间为 M/N对于实时操作系统而言，处理机效率一般不作为其设计目标 铁路信号系统、门禁系统和股票交易系统都需要实时操作系统支持 A、B、C只有D只有24以下服务中，能发挥多线程系统的特长的是（）。 利用线程并发地执行矩阵乘法运算Web 服务器利用线程请求 HTTP 服务 键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应相应的键盘输入 基于 GUI 的 debugger 用不同线程处理用户的输入、计算、跟踪等操作 A、B、C、D、25现在有 3 个同时到达的作业 J1、J2 和 J3，它们的执行时间分别为 T1、T2 和 T3，且 T1T2T3。

10、如果该系统中有两个 CPU，各自按照单道方式运行且采用短作业优先算法，则平 均周转时间是（ ）。A（T1+T2+T3）/3B（2T1+T2+T3）/3C（T1+2T2+T3）/3D（2T1+T2+T3）/3 或（T1+2T2+T3）/326对计数型信号量 S 执行 V 操作后，下列选项错误的是（）。 当 S.value0 时，唤醒一个阻塞队列进程只有当 S.value0 时，唤醒一个阻塞队列进程 当 S.value0 时，唤醒一个就绪队列进程 只有当 S.valuefront 和 rearfront 时，队列中元素个数为rear-front=(rear-front+m)%m因为 0rear-f

11、rontm，所以 rear-front+m 与 m 取余后结果还是 rear-front。（2）当 rearfront 时，队列中元素个数为m-（front-rear）=rear-front+m=（rear-front+m)%m因为 0rear-front+mm，所以 rear-front+m 与 m 取余后结果还是 rear-front+m。综合（1）、（2）可知，A 选项正确。 知识点总结：循环队列的两大状态和两大操作以及三大重点提醒。（1）两大状态（数学式子表示） 1）队空状态：q.rear=q.front。 2）队满状态：（q.rear+1）%MAX=q.front。（2）两大操作1）

12、元素 x 进队操作（移动队尾指针）。 q.rear=(q.rear+1)%MAX； q.dataq.rear=x；2）元素 x 出队操作（移动队头指针）。 q.front=(qu.front+1)%MAX； x=q.dataq.front；重点提醒 1：有些教材说循环队列队尾指针指向队尾元素，有些教材说循环队列队尾指针 指向队尾元素的下一个元素。不同的说法可能导致很多题目的答案总是相差 1。所以如果在考 研试卷中碰到，且题目没有说明（不过像考研试卷一般都会说明），一律认为是循环队列队尾 指针指向队尾元素的下一个元素。重点提醒 2：元素入队时，先移动指针，后存入元素；元素出队时，也是先移动指针，

13、再 取出元素。有些书上可能有不同的顺序，其实本质是一样的，考生只需去适应一种写法，对于程序设计题目已经足够。对于选择题，则可根据题目描述确定是先存取元素，再移动指针，还 是其他处理顺序。重点提醒 3：循环队列的队尾指针、队头指针、队中元素个数，知道其中任何两者均可算 出第三者。4B。 ：的描述只有在非空二叉树的情况下才成立，所以考生在做这种概念题目的时候一定要先想到这种特殊情况，所以错误。 ：二叉树的左右子树是有顺序的，不能随意交换，所以正确。 ：一般的二叉树确实不能使用顺序结构存储，但是完全二叉树和满二叉树一般都使用顺序结构存储，所以错误。 ：该结论只对完全二叉树才成立，所以错误。 综上所述

14、，只有正确。5C。每个非叶子结点的平衡因子均为 0，说明了该平衡二叉树为满二叉树，所以结点总数为 2k-1。总结：（1）设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，则N0=0，N1=1，N2=2， L ，Nh=Nh-1+Nh-2+1例如，深度为 5 的平衡二叉树中含有最少的结点数为 N5=12。（2）二叉排序树的查找效率取决于其深度。对于结点个数相同的二叉排序树，平衡二叉树的深度最小，因此效率最高。6D。赫夫曼树中只有度为 0 或 2 的结点，由 D 选项可以画出对应的二叉树，如图 1-7 所示。图 1-7 D 选项对应的二叉树由赫夫曼树的性质可知，树中不应该含度为 1 的结点，

15、因此 D 选项不可能。7A。 最小生成树边的权值之和最小，若两棵树同时为最小生成树，那么它们的边的权值之和一定相等，故错误；既然最小生成树不唯一，并且最小生成树的边都为 n-1 条，说明图 G 的边 数一定会大于 n-1，故正确；最小生成树不唯一，和 G 的权值最小的边的条数没有任何关系， 故错误。8A。 有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个顶点 v 出发的遍历，在 dfs(v)结束之前出现一条从顶点 j 到 v 的边，由于 j 在生成树上是 v 的子 孙，则图中必定存在包含 v 和 j 的环，因此可以；用拓扑排序的方法，在拓扑排序过程中，每 次要删去

16、一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环， 因此正确。而最短路径和关键路径（建立在无环的 AOE 网的基础之上）都是不可以判断的。补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图一定有什么？想必 90%以上的考生都会选择有环，但是没有环这个选项，只有顶 点数目大于 1 的强连通分量这个选项，此时考生必须知道顶点数目大于 1 的强连通分量就表明 有环。9D。 可以根据选项画出查找路线上的结点，根据二叉排序树的规定来排除不满足条件的选项。根据题目选项所得查找路线如图 1-8 所示。图 1-8 查找路线图A 选项中 28 的右

17、子树中出现了小于它的 18，不满足二叉排序树规定，排除。 B 选项中 36 的左子树中出现了大于它的 46，不满足二叉排序树规定，排除。 C 选项中 28 的左子树中出现了大于它的 36，不满足二叉排序树规定，排除。补充：在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度相当于折 半查找的时间复杂度，即 O(log2n)。平衡二叉树的查找效率最高，因为二叉树的查找效率取决于二叉树的高度，对于结点个数相同的二叉树，平衡二叉树的高度最小。10B。直接插入排序：每趟排序都是插入一个元素，所以排序趟数固定为 n-1（n 为元素数）。 简单选择排序：每趟排序都是选出一个最小（或最大）的元素

18、，所以排序趟数固定为 n-1（n 为元素数）。交换类的排序：其趟数和原始序列状态有关，所以冒泡排序与初始序列有关。 基数排序：每趟排序都要进行“分配”和“收集”，排序趟数固定为 d（d 为组成元素的关键字位数）。综上所述，、都是无关的，所以选 B。 11C。A：影响外排序时间的主要因素就是内存与外设交换信息的总次数，所以 A 错误。B：外部排序也是在内存上进行排序，只不过需要分为多步而已，所以 B 错误。 C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以 C 正确。 补充知识点：败者树和堆有什么区别？解析：外排序中败者树和堆排序的区别在于：（1）败者树是在双亲结点中记下刚进行完的这场比

19、赛的败者，而让胜者去参加更加高一层 的比赛，便可得到一棵败者树。而堆排序可看做一种胜者树，即双亲结点表示其左右孩子中的 胜者。（2）在败者树中，参加比较的 n 个关键字全部为叶子结点，双亲即为其左、右子女的败者， 败者树中结点总数为 2n-1，加上冠军结点恰好为 2n。而堆是由 n 个关键字组成的完全二叉树， 每个关键字作为树中一个结点，根是 n 个关键字中的胜者，树中结点总数为 n。D：使用置换-选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的 过程也可以得到答案，所以 D 错误。外排序的基本过程： 基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为两个阶段：（1）建

20、立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内 排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中。（2）按归并树模式，把（1）生成的初始归并段加以归并，一趟趟扩大归并段和减少归并 段数，直到最后归并成一个大归并段为止。例如：设有一个包含 4500 个记录的输入文件，现用一台其内存至多可容纳 750 个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳 250 个记录，这样全部 记录可存储在 4500/250=18 个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中 可用于排序的存储区域能容纳 750 个记录，所以

21、内存中恰好能存 3 个块的记录。在外排序一开始，把 18 块记录每 3 块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到 6 个初始归并段。然后一趟一趟进行归并排序，如图 1-9 所示。图 1-9 归并排序12B。图中实线框为 CPU，而 CPU 包含五大部件中的运算器和控制器，排除 C 选项。控制器为 计算机提供工作统一的时钟及其发出各种控制命令来协调计算机的各部件自动地工作，所以控 制器应该与其他四大部件相连，可得为运算器，为控制器。最后，根据数据的流向可以判 断，为输入设备，为输出设备。剩下为存储器。13D。由于“a”的 ASCII 码值为 61H，而

22、“g”是第 7 个字母，所以可以得到“g”的 ASCII 码 值应为 61H +6=67H=1100111B。现在“g”的 ASCII 码值中有 5 个“1”，按照偶校验的规则， 应该在最高位上添加一个 1，使得“1”的个数为偶数个，最后可得该存储单元中存放的十六进 制数为 E7H（1110 0111）。14A。 本题考查的是页式存储系统管理中的地址变换知识。在页式存储系统管理中，逻辑地址除以页的大小，然后向下取整为页号，取余为页内地址。本题页面的大小为 4KB，逻辑地址 8644 除以 4096，取整为 2，取余为 452。页号为 2，查页表得物理块号为 8。因此，a 的有效地址为 8409

23、6+452=33220。15D。 对于选项：首先，ROM和RAM都是采用随机存取方式。由于EPROM属于ROM，故采用随机存取方式。而CD-ROM属于光盘，为非随机存储，故错误。 对于选项：SRAM采用双稳态触发器来记忆信息，因此不需要刷新；而DRAM采用电容存储电荷的原理来存储信息，只能维持很短的时间，因此需要刷新，故错误。 对于选项：Cache需要有信息的输入和输出，而ROM只可读，不可输入，因此不能作为Cache，故错误。16D。Flash 存储器是一种具有较高存储容量、较低价格、非易失性、可在线擦除与编程的新一 代读写存储器。从基本工作原理上看，Flash 存储器属于 ROM 型存储器

24、，但由于它又可以随时 改写其中的信息，所以从功能上看，它又相当于随机存储器（RAM）。Flash 存储器与其他存储器的区别总结（见表 1-6）。表 1-6 Flash 存储器与其他存储器区别内存类型非易失性高密度可写Flash 存储器是是是SRAM不是不是是DRAM不是是是ROM是是不是EPROM是是不是EEPROM是不是是17A。首先可以计算出操作码字段的长度为 16-5-5=6。所以一共可以定义 26=64 条指令，既然二 地址指令占了 60 条，且是定长操作码，故单地址指令最多可以有 64-60=4 条，所以选 A。如果此题将条件改为采用不定长操作码，答案又是什么？分析如下： 如果采用不

25、定长（扩展）操作码，每条二地址指令可扩展为 32 条单地址指令，那么单地址指令最多有 324=128 条。18A。 指令总是根据程序计数器（PC）从主存中读出（一定记住）。可能考生会想到无条件转移指令情况，认为不一定总是根据 PC 读出。实际上，正确的执行顺序是这样的，当前指令正在执行时，其实 PC 已经是下一条指令的地址了，如果遇到了无条件转移指令，则只需要简单地 把跳转的地址覆盖 PC 的内容就可以了，最终的结果还是指令需要根据程序计数器从主存读出。19C。 ：外部事件是可以提出中断请求的，如可以通过敲击键盘来终止现在正在运行的程序，这个就可以看做一个中断，所以可以。：Cache 是属于存

26、储设备，不能提出中断请求，所以不可以。 、：浮点运算下溢，可以当做机器零处理，不需要中断来处理；而浮点运算上溢，必须中断来做相应的处理，所以不可以，可以。20D。24 位图像是典型的 JPG 图片，RGB 各占 8 位，合计 3B。未经压缩的图片大小=160012003B5.5MB，128MB/5.5MB=23.3，所以内置的存储空间最多可存储 23 张照片。21D。PCI 总线与 CPU 及时钟频率都无关，故错误；PCI 总线支持即插即用并且可对数据和 地址进行奇偶校验，并且 PCI 总线采用猝发传送方式，故正确；主设备指获得总线控制权 的设备，所以 PCI 设备不一定都是主设备，故错误；系

27、统中肯定允许有多条 PCI 总线，以 此来提升计算机的效率，故正确。22D。A：在统一编址方式下，访问主存储器和访问 I/O 设备是通过不同的地址码来区分的；在 独立编址方式下，访问主存储器和访问 I/O 设备是通过不同的指令来区分的，所以 A 错误。B：除主机外的硬件装置统称为外围设备或外部设备，包括输入、输出设备和外存储器， 所以 B 错误。C：中断隐指令并不是一条真正的指令，因此不可能把它预先编入程序中，只能在响应中 断时由硬件直接控制执行，它就好像是隐藏于机器中的指令，只有在响应中断时被执行。中断 隐指令不在指令系统中，不属于程序控制指令，所以 C 错误。补充：在中断周期中，由中断隐指

28、令自动完成保护断点、寻找中断服务程序入口地址以及硬件关中断的操作。D：为了防止在恢复现场过程中又出现新的中断，在恢复现场前需要增加关中断操作，所 以 D 正确。提醒：请注意区分，保护现场前的关中断由中断隐指令完成，但是恢复现场前的关中断是 由中断服务程序完成。23C。 正确。在分时操作系统中，响应时间跟时间片和用户数成正比。响应时间：从提交第一个请求到产生第一个响应所用时间。在 RR 算法中，用户作业时间 片结束后，就认为产生了第一个响应。错误。操作系统具有主存的共享性，因此每个用户拥有的主存空间大小是由用户程序的 大小决定的。正确。实时操作系统要求在安全的情况下对时间的要求较苛刻，为保证系统

29、的工作时效， 牺牲效率也是必然的。正确。铁路信号系统需要实时调度车辆，延时会出事故；门禁系统需要及时响应用户的 进入请求；股票交易系统需要当前的实时行情，上述应用均要求使用实时操作系统。综上所述，本题选 C。24D。在多线程操作系统中，通常一个进程中包括多个线程，每个线程都是作为利用 CPU 的基 本单位，是花费最小开销的实体。线程具有下述属性：（1）轻型实体。线程中的实体基本上不拥有系统资源，只是有一点必不可少的，即能保证 独立运行的资源。它包含了一个线程 ID、一个程序计数器、一个寄存器组和一个堆栈。（2）独立调度和分派的基本单位。（3）可并发执行。（4）共享进程资源。在同一进程中的各个线

30、程，都可以共享该进程所拥有的资源，包括共 享代码段、数据段以及其他的操作系统资源（如打开的文件）等。多线程最大的优点就是并发执行。在 4 个服务中，只有键盘操作是无法并发执行的，因为 整个系统只有一个键盘，而且键盘输入是人的操作，速度比较慢，完全可以使用一个线程来处 理整个系统的键盘操作，所以选择 D。25B。J1、J2 和 J3 同时在 0 时刻到达，按短作业优先算法，选择 J1 和 J2 执行，则 J1 和 J2 等待 时间为 0。又因为 T1T2，所以 J1 先于 J2 完成，即在 T2 时刻，释放 CPU，J3 开始，则 J3 的 等待时间为 T1。然后 J2 完成，最后 J3 完成。

31、J1 周转时间为 T1。 J2 周转时间为 T2。J3 周转时间为 T1+T3。 所以平均周转时间为（2T1+T2+T3）/3。知识点回顾：周转时间=等待时间+运行时间=结束时间-到达时间26B。 提醒：计数型信号量就是记录型信号量，不要被这个搞混了。 正确。当执行 V 操作后，S.value0，说明了在执行 V 操作之前 S.value0（此时 S.value 的绝对值就是阻塞队列中进程的个数），所以阻塞队列必有进程在等到，所以需要唤醒一个阻塞队列的进程。错误。由的分析可知，S.value0 就会唤醒。因为可能在执行 V 操作前，只有一个进 程在阻塞队列，也就是说 S.value=-1，执行

32、 V 操作后，唤醒该阻塞进程，S.value=0。和错误。S.value 的值和就绪队列中的进程没有此层关系，所以全错。 综上所述，本题选 B。27C。对于逻辑地址结构，因为 8 页=23 页，所以表示页号的地址有 3 位，又因为每页有 1024B= 210B，所以页内偏移地址有 10 位。因此总共逻辑地址有 13 位。对于物理地址结构，因为页面的大小和物理块的大小是一样的，所以每个物理块也是 1024B，而内存至少有 32 块物理块，所以内存大小至少是 321024B=215B。因此物理地址至少 要 15 位，不然无法访问内存的所有区域。28D。每页 1KB，默认字长为 1B，那么页内地址需

33、要 10 位，则剩下的 6 位为虚页号。计算过程 如表 1-7 所示。表 1-7 十六进制虚地址及物理地址十六进制虚地址0A5C1A5C二进制虚地址0000 1010 0101 11000001 1010 0101 1100二进制虚页号0000 100001 10二进制物理页号0001 00缺页中断二进制页内地址10 0101 1100二进制物理地址0001 0010 0101 1100十六进制物理地址125C29B。 正确。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入和换出过程，可提高 CPU 利用率。 错误。因为系统实际已处于频繁的换入和换出过程中，不是因为磁盘交换区容量

34、不够，因此增大磁盘交换区的容量无用。正确。因为从给定的条件中磁盘交换区的利用率为 99.7%，说明系统现在已经处于频繁 的换入和换出过程中，可减少主存中的程序。错误。系统处于频繁的换入和换出过程中，再增加主存中的用户进程数，只能导致系统 的换入和换出更频繁，使性能更差。错误。因为系统现在处于频繁的换入和换出过程中，即使采用更快的磁盘交换区，其换 入和换出频率也不会改变，因此没用。错误。系统处于频繁的换入和换出过程中，CPU 处于空闲状态，利用率不高，提高 CPU的速度无济于事。 综上所述，本题选 B。 30D。图 1-10 所示为文件系统模型。可将该模型分为 3 个层次，其最底 层是对象及其属

35、性；中间层是对对象进行操纵和管理的软件集合；最 高层是文件系统提供给用户的接口。其中对对象操纵和管理的软件集合这个层次，是文件系统的核心 部分。文件系统的功能大多是在这一层实现的，其中包括：对文件存 储空间的管理、对文件目录的管理、用于将文件的逻辑地址转换为物 理地址的机制、对文件读和写的管理以及对文件的共享与保护等功能。所以 A 选项是错误的。图 1-10 文件系统模型在多级目录结构中，从根目录到任何数据文件，都只有一条唯一的路径。在该路径上从树 的根（即主目录）开始，把全部目录文件名与数据文件名依次地用“/”连接起来，即构成该数 据文件的路径名。系统中的每个文件都有唯一的路径名。所以 B

36、选项的说法是不准确的。对文件的访问只需要通过路径名即可。对于 C 选项的描述，错在物理块大小是不可以任意指定的，它必须和外存分配方式相符合， 所以 C 选项错误。D 选项正确。基于文件系统的概念，可以把数据组成分为数据项、记录和文件 3 级。记录 是一组相关数据项的集合，用于描述一个对象在某方面的属性。记录是文件存取的基本单位， 数据项是文件可使用的最小单位。31A。在数据从控制器传送至内存的这段时间内，从磁头下通过的扇区数为 2。当数据从控制器 传送至内存后，磁头开始读数据时，刚好转到目标扇区。所以总时间为总时间=初始寻找 0 扇区时间+读扇区总时间+将扇区数据送入内存总时间 由题中条件可知

37、，旋转速度为：3000 转/分=50 转/秒，即 20ms/转。 读一个扇区需要时间：20/8ms=2.5ms读一个扇区并将扇区数据送入内存需要时间：2.53ms=7.5ms读出一个磁道上的所有扇区需要时间：20/2ms+87.5ms=70ms=0.07s每磁道数据量为 数据传输速度为8512B=4KB4KB/0.07s=57.1KB/s所以依次读出一个磁道上的所有扇区需要 0.07s，其数据传输速度为 57.1KB/s。 32A。单缓冲工作示意图和时序图如图 1-11 所示。从图中可以看出：数据由 I/O 控制器到缓冲区 和数据由缓冲区到工作区必须串行操作；同样，数据从缓冲区到工作区和 CP

38、U 从工作区中取 出数据进行处理也需串行进行；但由于在顺序访问时可采用预先读的方式，即 CPU 在处理一 块数据（从工作区取数据）的同时可从磁盘输入下一块数据，所以系统对一块数据的处理时间 为 max(T,C)+M。图 1-11 单缓冲工作示意图与时序图双缓冲的工作示意图和时序图如图 1-12 所示。由此可见，数据由 I/O 控制器到双缓冲和数 据由双缓冲区到工作区可以并行工作，因此，系统对一块数据的处理时间为 max(T,M+C)。33A。 从计算机网络组成的角度来看，典型的计算机网络从逻辑功能上可以分为两部分：资源子网和通信子网。 资源子网：由主计算机系统、终端、终端控制器、联网外部设备、

39、各种软件资源与信息资源等组成。资源子网负责全网的数据处理业务，负责向网络用户提供各种网络资源与网络服务。 通信子网（包括物理层、数据链路层、网络层）：由通信控制处理机、通信线路与其他通信设备组成，完成网络数据传输、转发等通信处理任务。图 1-12 双缓冲工作示意图与时序图综上所述，网桥、交换机、路由器都属于通信子网，而只有计算机软件属于资源子网。34A。PCM 代表 Pulse Code Modulation（脉冲编码调制）。补充：PCM 通常用在电话系统中对模拟数据进行采样。一般都把 PCM 采样时间设置成125ms，125ms 的采样时间对应于每秒 8000 次采样。一个典型的电话通道是

40、4kHz，根据奈奎斯特定理，为获取在一个 4kHz 通道中的全部信息 需要每秒 8000 次的采样频率。128=27，每个采样表示 7 个二进制位。80007bit/s=56000bit/s= 56kbit/s。35B。 发送窗口的后沿的变化情况只能有两种：（1）原地不动（没有收到新的确认）。（2）向前移动（收到了新的确认）。 发送窗口不可能向后移动，因为不可能撤销已收到的确认帧。 36B。流就是 Internet 上从特定主机的源站到特定的目的站的单播或组播数据分组，所经过的路 径上的路由器都能保证指定的服务质量。头部中的源地址、目的地址和流标号字段唯一地标识 了一个流。37D。 需要分两种

41、情况，分析如下：第一种：假设计算机 A 和计算机 B 在同一个局域网内，那么应该由计算机 B 使用 ARP 响 应分组将计算机 B 的硬件地址告诉计算机 A。第二种：假设计算机 A 和计算机 B 不在同一个局域网内，则应该由连接本网络的路由器 使用 ARP 响应分组将自己的硬件地址告诉计算机 A。综上所述，由谁通过 ARP 响应分组回应是不确定的。38C。在该网络上共有 50 个路由器，因此每个路由器的路由表大小为 6850bit=2400bit。在基 于距离-向量的路由选择算法中，每个路由器都定期地与所有相邻的路由器交换整个路由表， 并以此更新自己的路由表项。由于每个路由器每秒与自己的每个邻

42、接路由器交换 1 次路由表， 一条链路连接两个路由器，所以每秒在一条链路上交换的数据为 22400bit=4800bit，即由于更 新路由信息而耗费的带宽为 4800bit/s。39B。在慢启动和拥塞避免算法中，拥塞窗口初始值为 1，窗口大小开始按指数增长。当拥塞窗 口大于慢启动门限后，停止使用慢启动算法，改用拥塞避免算法。此时，慢启动的门限值初始 为 8，当拥塞窗口增大到 8 时改用拥塞避免算法，窗口大小按线性增长，每次增长 1 个报文段。 当增加到 12 时，出现超时，重新设置门限值为 6（12 的一半），拥塞窗口再重新设为 1，执行 慢启动算法，到门限值为 6 时执行拥塞避免算法。按照上

43、面的算法，拥塞窗口的变化为 1、2、4、8、9、10、11、12、1、2、4、6、7、8、9L ，从该序列可以看出，第 12 次传输时拥塞窗 口大小为 6。注意：在以上的序列中，6 被加粗，原因是很多考生直接从 4 增加到 8，导致误选 D 选项。原因是拥塞窗口的大小是与门限值有关的，在慢开始算法中不能直接变化为大于门限值，所以4 只能最多增加到 6，之后再执行拥塞避免算法。40A。FTP 使用两条 TCP 连接完成文件传输，一条是控制连接，另一条是数据连接，所以 C 选 项正确；在 FTP 中，控制连接在整个用户会话期间一直打开着，而数据连接有可能为每次文件 传送请求重新打开一次，即数据连接

44、是非持久的，而控制连接是持久的，所以 A 选项错误，B 选项正确；D 选项显然正确。二、综合应用题41【答案要点】首先解答此题需要很清楚地知道 B-树的基本定义，这个就不再一一列举了，参考教材即 可。另外，B-树插入和删除的详细过程也请参考教材，以下的讲解只是大概地描述几个较为关 键的步骤。（1）插入 33：第一步需要定位，33 应该被插入 35 和 41 的那个叶子结点。由于该叶子结 点没有了空位置（怎么检测是否有空位置？m 阶 B-树最多只能有 m-1 个关键字），所以需要进行分裂操作。插入后的情况应该是 35、41、33，那么怎么分裂？首先需要取一个新结点，把 原结点上的关键字按照升序排

45、列，即 33、35、41。从中间位置（即 m/2 之处）把关键字（不 包括中间位置的关键字）分成两部分，左部分所含的关键字放在旧结点中，右边所含的关键字 放在新结点中，中间位置的关键字连同新结点的存储位置插入到双亲结点中，如图 1-13 所示。如果双亲结点的关键字个数也超过分支数减 1，则要再分裂，再往上插，直至这个过程传 到根结点为止。从以上步骤可以得出插入 33 之后的 B-树，如图 1-14 所示。图 1-13图 1-14 插入 33 后的 B-树可能疑问点：结点下面的小方块都是什么？ 解析：小方块就是叶子结点，因为叶子结点本身不带有信息，所以有些教材都不画出来，但是叶子结点这一层是一定要计入树的高度。另外，叶子结点一般也被认为外部结点（类似于 折半查找判定树的外部结点）或是查找失败的结点。插入 97：过程与