2012全国硕士研究生入学统一考试计算机学科专业基础综合试题模拟试题3

1、2012 全国硕士研究生入学统一考试计算机学科专业基础综合试题模拟题三一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题要求。1.在具有 n 个结点的顺序表，算法的时间复杂度是 O(1)的操作是 A. 访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in) B在第 i 个结点后插入一个新结点(1in) C删除第 i 个结点(1in) D将 n 个结点从大到小排序 2.使用双链表存储线性表，其优点是 I 提高查找速度 II 更方便数据的插入和删除 III 节约存储空间 IV 很快回收存储空间 AI、II BI、IV C仅

2、II DII、III、IV 3.若进栈序列为 a,b,c，则通过出栈操作可能得到 a,b,c 的不同排列个数为 A.4 B.5 C.6 D.7 4.若对 n 阶对称矩阵 A1.n，1.n以行序为主序方式下将其下三角的元素（包括主对角线上的所有元素）依次存放于一维数组 B1.n(n+1)/2中，则在 B 中确定 aij (i<j)的位置 k 的关系是 Ai(i-1)/2+j Bj(j-1)/2+i Ci(i+1)/2+j Dj(j+1)/2+i 5.在线索化二叉树中，t 所指结点没有左子树的充要条件是 At->left=NULL C. t->ltag=1 且 t->lef

3、t=NULL B. t->ltag=1 D. 以上都不对 6.若采用邻接矩阵来存储简单有向图，则其某一个顶点 i 的入度等于该矩阵 A第 i 行中值为 1 的元素个数 B. 所有值为 1 的元素个数 C第 i 行及第 i 列中值为 1 的元素总个数 D第 i 列中值为 1 的元素个数 7.在有 11 个元素的有序表 A1.11中进行折半查找，查找元素 A11时，被比较的元素的下标依次是 A.6,8,10,11 B. 6,9,10,11 C. 6,7,9,11 D. 6,8,9,11 8.设散列表表长 m=14，散列函数 H(k)=k MOD 11，表中已有 15,38,61,84 四个元

4、素，如果用线性探测法处理冲突，则元素 49 的存储地址是 A8 B3 C5 D9 9.以下关于查找方法的说法正确的是 I 顺序查找法只能在顺序存储结构上进行。II 折半查找法可以在有序的双向链表上进行 III 分块查找的效率与线性表被分为多少块有关 A. I、II B. II、III C. I、III D. 只有 III 10.下述排序方法中，比较次数与待排序记录的初始状态无关的是 A. 插入排序和快速排序 B. 归并排序和快速排序 C. 选择排序和归并排序 D. 插入排序和归并排序 11.堆排序、快速排序、归并排序就排序算法所用的辅助空间而言，从小到大的关系是 A.堆排序、快速排序、归并排序

5、 C.快速排序、归并排序、堆排序 12.有关运算器的描述，_是正确的。 B. 堆排序、归并排序、快速排序 D. 归并排序、快速排序、堆排序 A. 只做加法 B. 只做算术运算 C. 既做算术运算又做逻辑运算 D. 只做逻辑运算 13.冯诺依曼机工作的基本方式的特点是_。 A. 多指令流单数据流 B. 按地址访问并顺序执行指令 C. 堆栈操作 D. 存贮器按内容选择地址 14.在机器数_中，零的表示形式是唯一的。 A. 原码 B. 补码 C. 移码 D. 反码 15.在定点二进制运算器中，减法运算一般通过_来实现。 A. 原码运算的二进制减法器 B. 补码运算的二进制减法器 C. 原码运算的十进

6、制加法器 D. 补码运算的二进制加法器 16.某计算机字长 32 位，其存储容量为 4MB，若按半字编址，它的寻址范围是_。 A. 4MB B. 2MB C. 2M D. 1M 17.EPROM 是指_。 A. 读写存储器 B. 只读存储器 C. 闪速存储器 D. .光擦除可编程只读存储器 18.主存储器和 CPU 之间增加 cache 的目的是_。 A. 解决 CPU 和主存之间的速度匹配问题 B. 扩大主存贮器容量 C. 扩大 CPU 中通用寄存器的数量 D. 既扩大主存贮器容量，又扩大 CPU 中通用寄存器的数量 19.指令的寻址方式有顺序和跳跃两种方式，采用跳跃寻址方式，可以实现_。

7、A. 堆栈寻址 ； B. 程序的条件转移 ； C. 程序的无条件转移 ； D. 程序的条件转移或无条件转移 20.由于 CPU 内部的操作速度较快，而 CPU 访问一次主存所花的时间较长，因此机器周期通常用_来规定。 A. 主存中读取一个指令字的最短时间 B. 主存中读取一个数据字的最长时间 C. 主存中写入一个数据字的平均时间 D. 主存中取一个数据字的平均时间 21.系统总线中地址线的功能是_。 A. 选择主存单元地址 B. 选择进行信息传输的设备 C. 选择外存地址 D. 指定主存和 I/O 设备接口电路的地址 22.在单级中断系统中，CPU 一旦响应中断，则立即关闭_标志，以防本次中断

8、服务结束前同级的其他中断源产生另一次中断进行干扰。 A. 中断允许 B. 中断请求 C. 中断屏蔽 D. 中断保护 23.分布式操作系统与网络操作系统本质上的不同之处是 A实现各台计算机之间的通信 B共享网络中的资源 C满足较大规模的应用 D系统中若干台计算机相互协同完成同一任务 24.若有一进程拥有 100 个线程，这些线程都属于用户级线程，则在系统调度执行时间上占用的时间片是 A1 B100 C1/100 D0 25.出现下列的情况可能导致死锁的是 A进程释放资源 B一个进程进入死循环 C多个进程竞争资源出现了循环等待 D多个进程竞争使用共享型的设备 26.在一个多道系统中，就绪的进程数目

9、越多，处理机的效率变化的情况是 A 变高 B 变低 C 不变 D 不确定 27.某进程页面访问序列为 4，3，2，1，4，3，5，4，3，2，1，5，且开始执行时内存中没有页面，分配给该进程的物理页框数是 3，则采用 FIFO 页面置换算法和 LRU（最近最久未使用）页面置换算法时缺页率分别是 A83；75 B85%；70 C75，83 D84；75 28.考虑下面的段的分配，0 段的段基址为 100，段长 500，1 段的段基址为 1000，段长 60，2 段的段基址为 90，段长 200，3 段的段基址为 1300，段长 400，4 段的段基址为 1600，段长 120。则逻辑地址（2，8

10、8）和逻辑地址（4，123）对应的物理地址分别是 A178，1723 C178，越界中断 B越界中断，1723 D188，越界中断 29.可能使系统产生抖动现象的存储分配方案是 动态分区分配；简单页式；虚拟页式；简单段页式；简单段式；虚拟段式 A和 B和 C和 D和 30.某一个磁盘共有 16 个盘面，每个盘面上从外到内共有 30000 个磁道（或称 30000 个柱面），每个磁道有 250 个扇区。假定存储信息时以一个扇区作为一个存储块，盘面号（磁头号）、磁道号和扇区号均从 0 开始编号，那么，盘块号 1002578 对应的盘面号、磁道 号和扇区号是 A1，2500，78 B10，250，7

11、8 C2，250，161 D0，4010，78 31.为了防止各种意外可能破坏文件，文件系统用来保护文件的方法是 A为文件加密 C建立副本和定时转储 B对每个文件规定使用权限 D为文件设置口令 32.在下列问题中，不是设备分配中应考虑的方面是 A及时性 B设备的固有属性 C设备无关性 D安全性 33OSI 参考模型中，第 N 层和其上的第 Nl 层的关系是 A.第 N 层为第 N+1 层提供服务 B.第 N+1 层将从第 N 层接收的信息增加了一个头 C.第 N 层利用第 N+1 层提供的服务 D.第 N 层对 N+1 层没有任何作用 33.盘转速提高一倍，即可使 。 A 存取速度提高一倍 B

12、 平均寻道时间缩小到原来的一半 C 磁盘传输速度提高一倍 D 平均等待时间缩小到原来的一半 34待传送数据总长度为 L 位，分组长度为 P 位，其中头部开销长度为 H 位，源节点到目的节点之间的链路数为 h，每个链路上的延迟时间为 D 秒，数据传输率为 B bps，电路交换建立连接的时间为 S 秒，则传送所有数据，电路交换需时间是 A.hD+L/B 秒 B.S+hD+L/P 秒 C.S+hD+L/B 秒 D.SL/B 秒 35若数据链路的发送窗口尺寸 WT=4，在发送 3 号帧、并接到 2 号帧的确认帧后，发送方还可连续发送的帧数是 A 2 帧 B 3 帧 C 4 帧 D 1 帧 36TCP/

13、IP 网络中，某主机的 IP 地址为 130.25.3.135 ，子网掩码为 255.255.255.192 ，那么该主机所在的子网的网络地址是 A.130.25.0.0 B.130.25.3.0 C.130.25.3.128 D.130.25.3.255 37为了限制路由信息传播的范围，OSPF 协议把网络划分成 4 种区域（Area），其中连接各个区域的传输网络是 A不完全存根区域 B标准区域 C主干区域 D存根区域 38一台主机的 IP 地址为 .100，子网掩码为 255.0.0.0。现在用户需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下 4 个 IP 地址和

14、子网掩码： IIP 地址：.1，子网掩码：255.0.0.0 IP 地址：.1，子网掩码：255.0.0.0 IP 地址：.1，子网掩码：255.0.0.0 IP 地址：.1，子网掩码：255.0.0.0 请问 IP 地址和子网屏蔽码可能是该主机的默认路由的是 A.I 和 B和 C、和 D和 39以太网交换机中的端口/MAC 地址映射表是 A.是由交换机的生产厂商建立的 B.是交换机在数据转发过程中通过学习动态建立的 C.是由网络管理员建立的 D.是由网络用户利用特殊的命令建立的 40下面关于电子邮件的说法中，不正确的是 A电子邮件只能发送文本文件 B电子邮件可以发送图形文件 C电子邮件可以发

15、送二进制文件 D电子邮件可以发送主页形式的文件 二、综合应用题：4147 小题，共 70 分。请将答案写在答题纸指定位置上。41.（10 分）对于下图 G，按下列条件试分别写出从顶点 0 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 （1）假定它们均采用邻接矩阵表示; （2）假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。42. （13 分）一棵二叉树的繁茂度定义为 R 层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。 43.（10 分）某机主存容量为 4M16 位，且存储字长等于指令字长，若该机的指令系统具

16、备 120 种操作。操作码位数固定，且具有直接、间接、立即、相对四种寻址方式。 （1）画出一地址指令格式并指出各字段的作用； （2）该指令直接寻址的最大范围； （3）一次间址的寻址范围； （4）相对寻址的寻址范围。 44.（13 分）设主存容量 1MB，有 16KB 直接相联映像的 Cache，假定该 Cache 的块为 8 个32 位的字。解答下列问题： （1）写出 Cache 地址格式。 （2）写出主存地址格式。 （3）块表的容量为多大？ （4）画出直接方式地址映像及变换示意图。 （5）主存地址为 ABCDE8F8 的单元在 Cache 中的什么位置？ 45.（7 分）设有某多道程序系统中

17、有用户使用的内存 100K，打印机 1 台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算法，进程调度时机选择在进程执行结束或新进程创建时，现有进程如下表所示： 进程调度表 进程 创建时间 要求执行时间 要求内存 申请打印机 P0 P1 P2 P3 P4 0 4 10 11 16 8 4 1 20 14 15K 30K 60K 20K 10K 1 1 0 1 0 假设系统优先分配内存低地址区域，且不允许移动，那么，求解： （1）给出进程调度算法选中进程的次序，并说明理由。

18、（2）全部进程执行结束全部所用的时间是多少？平均周转时间是多少？ 46.（8 分）大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为 512B，有一个文件，包含了 590 个逻辑记录，每个记录占 255B；其中，为检索方便，采用成组法存储，在每个物理块上只存放 2 个记录。文件 A 在该文件目录中的位置如下图所示。 root bin dev usr etc tmp home proc tom smith mary tony jone doc picture music A B C 文件目录中的位置 此树形文件目录结构由根目录结点和作为文件中间的目录结点以及作为信息文件的

19、叶结点组成，每个目录项占 127B，每个物理块存放 4 个目录项。根目录的内容常驻内存。 （1）若文件采用隐式链接文件结构，设每块的连接字占 4B，存放在每个物理块的尾部。如果要将文件 A 读入内存，至少要读取几次硬盘？为什么？ （2）若文件采用连续文件结构，如果要将文件 A 的逻辑记录号为 480 的记录读入内存，至少要读取几次硬盘？为什么？ 47.（9 分）某路由器的 IP 地址是 ，它在以太网上的物理地址为 2345AB4F67CD，它收到了一个分组，分组中的目的 IP 地址是 。（1）试给出这个路由器发出的 ARP 请求分组中的各项目。假定不划分子网。（2）假定目的主机在以太网上的物理

20、地址为AABBA24F67CD，试给出目的主机发送的ARP响应分组中的各项目。（3）将问题 1 的结果封装成数据链路层的帧，试填充所有的字段。（4）将问题 2 的结果封装成数据链路层的帧，试填充所有的字段。题 47-1 图 ARP 报文格式题 47-2 图以太网帧结构 计算机学科专业基础综合试题参考答案(模拟题三) 一、单项选择题1.A 【答案解析】顺序表是随机存取结构，选项 A 中实质是查找第 i 个结点和第 i-1 个结点，因此时间复杂度为 O(1)；选项 B 和 C 插入和删除都需要移动元素，时间复杂度为 O(n)；选项 D是排序问题，时间复杂度是 O(n)O(n2)。2.C 【答案解析

21、】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节省存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。3.B 【答案解析】若进栈序列为 a,b,c，可以考虑所有进栈出栈情况，则可能得到 a,b,c 的出栈序列是 abc，acb，bac，bca，cba。【归纳总结】对于 n 个不同元素进栈，出栈序列的个数为：´n1+1nC2n 。1C=【解题技巧】当 n=3 时，出栈序列的个数为636 ´ 54´=5，即可快速得出正确答案。4.B 44 ´ 3 &

22、#180; 21【答案解析】将对称矩阵 A 中的下三角的元素存放于 B 数组中，若求 aij(ij)的位置 k 的关系，答案为 A，即 i(i-1)/2+j。但是，本题求 aij (i<j)的位置 k 的关系，aij (i<j)这个元素没被存放，也就是说需要找到与 aij (i<j)这个元素相等的元素 aji，这就需要将备选答案 A 中 i(i-1)/2+j 的 i 与 j 互换，因此正确答案为B，即 j(j-1)/2+i。5.B 【答案解析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为 1。6.D 【答案解析】由邻接矩阵的定义可知，对

23、于无向图，其邻接矩阵的第 i 行的和即为第 i 个顶点的度。对于有向图，邻接矩阵的第 i 行元素的和即为第 i 个顶点的出度，而邻接矩阵的第j 列元素的和即为第 j 个顶点的入度。7.B 【答案解析】由折半查找过程可得，第一次 ë(1 + 11) / 2û = 6 ，第二次 ë(6 +1) +第三次 ë(9 + 1) + 11) / 2û = 10，第四次 11。或者由下图所示的折半查找的判定树可求得下标。6 3 9 11) / 2û = 9 ，2 1 4 5 7 8 10 11 8.A 【答案解析】元素 15,38,61,84 分别

24、存储在 4,5,6,7 单元，而元素 49 的散列地址为 5，发生冲突，向后探测 3 个单元，其存储地址为 8。9.D 【答案解析】I 和 II 的说法都是错误的，顺序查找法可以在顺序存储结构和链式存储结构上进行，而折半查找只能在可以进行随机存取的存储结构上进行，即只能在顺序存储的有序表上进行。10.C 【答案解析】选择排序在最好、最坏、平均情况下的时间性能均为 O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为 O(nlogn)。11.A 【答案解析】本题主要考查各种排序的空间复杂度。堆排序只是需要在元素比较进行交换时需要常数个存储空间，它需要的辅助空间为 O(1)；快速排序在递归过

25、程中需要栈结构来保存递归的信息，它需要的辅助空间为 O(log2n)；归并排序需要长度为元素个数的线性空间来保存归并的结果，它需要的辅助空间为 O(n). 12.C 13.B 14. B 15. D 16C17D 18A 19.D 20A21D22B23. D 【答案解析】分布式计算机系统是由多台计算机组成的系统。与网络操作系统的主要区别在于任务的分布性，即把一个大任务分为若干个子任务，分派到不同的处理器上执行。实现各台计算机之间的通信，共享网络中的资源以及提供各类服务是网络操作系统和分布式操作系统所必须具备的功能，相互没有本质的区别；选项 C“满足较大规模的应用”没有体现多机系统的特性；网络

26、操作系统一般不会拆开一个作业，而分布式操作系统却会在用户不知道的情况下自动将作业拆分，分布到不同的计算机或处理机上运行，再将结果汇总。分布式操作系统需要更加严格的通信协议，同步技术，共享技术等，也具有更高的强健性。因此，最适合的答案为 D. 24.A 【答案解析】本题主要考查关于进程和线程之间资源共享的知识点。在引入线程的操作系统中，线程是进程中的一个实体，是系统独立调度和分派的基本单位。但是线程自己基本上不拥有系统资源，所以它不是资源分配的基本单位，它只拥有一部分在运行中必不可少的与处理机相关的资源，如线程状态、寄存器上下文和栈等，它同样有就绪、阻塞和执行三种基本状态。它可与同属一个进程的其

27、他线程共享进程所拥有的全部资源。一个线程可以创建和撤 销另一个线程；同一个进程中的多个线程之间可以并发执行。由于用户线程不依赖于操作系统内核，因此，操作系统内核是不知道用户线程的存在的，用户线程是由用户来管理和调度的，用户利用线程库提供的 API 来创建、同步、调度和管理线程。所以，用户线程的调度在用户程序内部进行，通常采用非抢先式和更简单的规则，也无须用户态和核心态切换，所以速度很快。由于操作系统不知道用户线程的存在，所以，操作系统把CPU 的时间片分配给用户进程，再由用户进程的管理器将时间分配给用户线程。那么，用户进程能得到的时间片即为所有用户线程共享。因此，正确答案应为 A。 25.C

28、【答案解析】本题考查死锁的四个必要条件。死锁的四个必要条件是：互斥；占有并等待；非剥夺；循环等待。本题中，出现了循环等待的现象，意味着可能导致死锁的出现。进程释放资源不会导致死锁，进程自己进入死循环只能产生饥饿，不涉及到别人。共享型设备允许多个进程申请使用，故也不会造成死锁。正确答案为 C。 26.C 【答案解析】从进程的状态图中可以看出，进程就绪数目越多，争夺 CPU 的进程就越多，但是，只要就绪队列不为空，CPU 总是可以调度进程运行，保持繁忙。这与就绪进程的数目没有关系，除非就绪队列为空，则 CPU 进入系统懈怠，此时 CPU 的效率会下降。因此正确答案为 C。 27.C 【答案解析】根

29、据题意分析，缺页率；缺页次数/访问的页面数 100，所以此题相当于计算缺页次数。采用 FIFO 算法进行页面调度时页面装入和调出的情况如下表。 FIFO 算法进行页面调度 序列 4 3 2 1 4 3 5 4 3 2 1 5 A B C 4 3 4 2 3 4 1 2 3 4 1 2 3 4 1 5 3 4 5 3 4 5 3 4 2 5 3 1 2 5 1 2 5 缺页 Y Y Y Y Y Y Y N N Y Y N 缺页率为 9/12 = 75% 采用 LRU 算法进行页面调度时页面装入和调出的情况如下表。 LRU 算法进行页面调度 序列 4 3 2 1 4 3 5 4 3 2 1 5 A

30、 B C 4 3 4 2 3 4 1 2 3 4 1 2 3 4 1 5 3 4 4 5 3 3 4 5 2 3 4 1 2 3 5 1 2 缺页 Y Y Y Y Y Y Y N N Y Y Y 缺页率为 10/12 = 83% 因此，正确答案为 C。 28.C 【答案解析】简单地考察逻辑地址到物理地址转换的问题，理解缺页中断和越界中断的问题。逻辑地址（2，88），在第 2 段，因为 88 小于 100，所以对应的物理地址为：基址+偏移量 =90+88 = 178。逻辑地址（4，123），在第 4 段，因为 123 大于 120，造成段内地址超过该段的长度，所以产生越界中断。因此逻辑地址（2，

31、88）对应的物理地址是 178：而逻辑地址（4，123）产生越界中断，正确答案为 C. 29.D 【答案解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其它页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上。对换的信息量过大，内存容量不足不是引起系统抖动现象的原因，而选择的置换算法不当才是引起抖动的根本原因，例如，先进先出算法就可能会产生抖动现象。本题中只有虚拟页式和虚拟段式才存在换入换出的操作，简单页式和简单段式因已经全部将程序调入内存，因此不需要置换，也就没有了抖动的现象。故。正确答案为 D.30.C 【答案解析】本题考查磁盘的结构。磁盘的存储是按

32、照磁头（或盘面），磁道（或柱面）和扇区三要素唯一确定的，但是，在具体的使用时，是将所有的可用存储块按一维编号来进行分配的。由于多盘面的磁盘系统中所有的磁头装在同一个转动轴上，是同步一起移动的，所以选择高效的编址方式能够提高磁盘的读写时间。不同于按磁头、磁道、扇区的顺序编址，多盘组磁盘的编址首先是按磁道来编，从磁盘外边缘到磁盘中心从 0 开始编号，本题中是 0到 29999。确定了磁道，接下去随着磁盘的转动，所有磁头一起从某一起始点开始，寻找扇区，扇区的编号也是从 0 开始，本题中是 0 到 249。找到扇区后再按磁头寻找，磁头从上到下从 0 开始编号，本题中是 0 到 15。在了解了盘组磁盘的

33、编址方式后，下面的计算就比较简单了。首先确定磁道，1002578/(250*16)并下取整（即舍去小数部分）得 250，得到磁道号，余下逻辑块编号的偏移量是 2578，接下去确定扇区号，2578/16 并下取整得 161，得到扇区号，余下逻辑块编号的偏移量是 2，此号便是磁头号了，所以，其对应的三要素单位为2，250，161。 31.C 【答案解析】本题主要考查文件保护、防止系统故障或人为误操作造成的破坏。文件的保护是防止文件被破坏，造成文件可能被破坏的原因有时是硬件故障、软件失误引起的，有时是由于共享文件时引起的错误，应根据不同的情况，采用不用的保护措施。前者主要采用定时备份、转储，后者建立

34、访问控制列表等方法，故，正确答案是 C. 32.A 【答案解析】在进行设备分配时应考虑的因素有：设备的固有属性，设备无关性，安全性。设备的固有属性：对于独占设备、共享设备、虚拟设备等具有不同的属性的设备，通常采用不同的分配算法。设备无关性：又称为设备独立性，是指应用程序使用的逻辑设备独立于系统实际配置的物理设备。安全性：即避免死锁的产生。综上分析选项B、C、D都是设备分配应考虑的问题。显然选项 A 不是设备分配应考虑的问题。故，正确答案为 A。 33A 【答案解析】本题考查 OSI 模型的层次关系，在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务，同时要实现本层协议，还需要使用

35、下层所提供的服务。本层的服务用户只能看见服务而无法看见下面的协议。下层的协议对上层的服务用户是透明的。也就是下一层要为上一层提供服务，并为上一层数据进行封装，因此答案为 A，这里选项 B 和C 的说法正好相反，应该是第 N 层将从第 N+1 层接收的信息增加了一个头，第 N+1 层利用第N 层提供的服务。 34C 【答案解析】本题考查电路交换的原理，电路交换包括三个阶段：建立电路。在传送数据之前，由发送方发出建立电路请求，交换机根据该请求，设法选择一条空闲的信道连接到接收方。接收方收到该呼叫后，返回一应答信号确认本次电路连成，则本次连接成功。传送数据。建立电路连接后，发送方通过已建立的电路向接

36、收方发送数据。拆除电路。数据传输完毕，发送方或接收方任一方发出拆线信号，终止电路连接，释放所占用的信道资源。因此传送所有数据所需的时间是连接建立时间，链路延迟，发送时间的和，因此是 S+hD+L/B，答案是 C。 35B 【答案解析】本题考查滑动窗口的机制，发送方可连续发送 K 帧而无需对方应答，但需要将已发出但尚未收到确认的帧保存在发送窗口中，以备由于出错或丢失而准备重发。接收方按正确的次序接受和递交数据帧，并返回确认信息。接收方可能因为一帧出错，不能正确接受并递交主机，对后面连续发送来的 n 帧均丢失，这就是累积确认的概念。本题收到了 2 号帧的确认后，即 0，1，2 号帧已经正确接收，因

37、此窗口向右移动 3 个帧，目前已经发送了 3号帧，因此可连续发送的帧数是窗口大小-已经发送的帧数，即 4-1=3，答案是 B。 36C 【答案解析】本题考查子网划分的计算，从掩码可以看出网络地址仅和第四个字节有关，因此 130.25.3.135 的二进制为 130.25.3.1000 0111，子网掩码的二进制为 255.255.255.1100 0000，两者相与，因此网络地址为 130.25.3.1000 0000，换算为十进制是 ，因此答案为C。 37C 【答案解析】本题考查层次路由与 OSPF 路由协议，如果将区域看成一个节点，则 OSPF 是以主干区域（area 0）为顶点，其他区域

38、为终端的星形拓扑结构。标准区域可以接收链路更新信息和路由总结。存根区域是不接受自治系统以外的路由信息的区域。如果需要自治系统以外的路由，它使用默认路由 .0。完全存根区域不接受外部自治系统的路由以及自治系统内其他区域的路由总结，需要发送到区域外的报文则使用默认路由 .0。不完全存根区域类似于存根区域，但是允许接收以 LSAType7 发送的外部路由信息，并且要把 LSAType7转换成 LSAType5。因此答案是 C.38A 【答案解析】本题考查默认路由的配置，路由器还可采用默认路由以减少路由表所占用的空间和搜索路由表所用的时间。这种转发方式在一个网络只有很少的对外连接时是很有用的。本题中主

39、机地址是一个标准的 A 类地址，其网络地址为 .0。选项 I 的网络地址为.0，选项 II 的网络地址为 11.0.0.0，选项的网络地址为 12.0.0.0，选项的网络地址为 .0，因此和主机在同一个网络是选项 I 和 II，因此答案为 A。 39B 【答案解析】本题考查交换机中地址映射表的原理，主要与路由器的路由表进行区分，路由表可以由人为配置静态路由，也可以通过动态协议建立，而对于交换机，映射表只能在数据转发中进行动态学习建立，并且每个表项都有定时器，具体是收到一帧后先进行自学习。查找转发表中与收到帧的源地址有无相匹配的项目。如没有，就在转发表中增加一个项目（源地址、进入的接口和时间）。

40、如有，则把原有的项目进行更新，因此答案为 B。 40A 【答案解析】本题考查电子邮件的主要功能，电子邮件不仅仅发送文本文件，注意邮件系统中 SMTP 不能传送可执行文件或其他的二进制对象。SMTP 限于传送 7 位的 ASCII 码，也就是文本文件，因此引入 MIME 协议，在没有改动 SMTP 或取代 SMTP 的前提下，增加了邮件主体的结构，并定义了传送非 ASCII 码的编码规则。因此答案为 A。 二、综合应用题41.【答题要点】导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方

41、法若不相同，得到的结果也是不相同的。另外，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结 构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。本题需要先建立图 G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表，然后再进行深度优先和广度优先遍历。【解答】（1）采用邻接矩阵表示得到的顶点序列如下表所示：图G 深度优先序列0 1 2 8 3 4

42、5 6 7 9 广度优先序列0 1 4 2 7 3 8 6 5 9 （2）采用邻接表表示得到的顶点序列如下表所示：图深度优先序列广度优先序列G 42.【答题要点】0 4 3 8 9 5 6 7 1 2 0 4 1 3 7 2 8 6 9 5 【分析】要用层次遍历以及队列来处理，可增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。【解答】typedef struct BiTNode TElemType data; struct BiTNode *lchild;*rchild; /左、右孩子指针BiTNode, *BiTree; typedef struct BiTNode

43、 node; int layer; BTNRecord; /包含结点所在层次的记录类型int FanMao(Bitree T) int countMAX; /count 数组存放每一层的结点数InitQueue(Q); /Q 的元素为 BTNRecord 类型EnQueue(Q,T,0); while(!QueueEmpty(Q) /利用层序遍历来统计各层的结点数DeQueue(Q,r); countr.layer+; if(r.node->lchild) EnQueue(Q,r.node->lchild,r.layer+1); if(r.node->rchild) EnQu

44、eue(Q,r.node->rchild,r.layer+1); h=r.layer; /最后一个队列元素所在层就是树的高度for(maxn=count0,i=1;counti;i+) if(counti>maxn) maxn=counti; /求层最大结点数return h*maxn; 43.【答题要点】（1）格式：7 位操作码2 位寻址方式7 位地址码（2）直接寻址 0000-007FH （3）16 位：216=64K 0000-FFFFH （4）全部存储空间或 4M 字或 8M 字节44.【答题要点】（1）Cache 容量 16KB，16KB=214，所以 Cache 地址为

45、 14 位；块的大小为 8 个 32 位的字，即 32 字节，所以块内地址为 5 位，块地址 9 位。Cache 地址格式为： 13 块地址 5 4 块内地址 0 （2）主存容量 1MB，1MB=220，所以主存地址为 20 位；块的大小为 32 字节，所以块内地址为 5 位，块地址为 9 位，块标记为 6 位。主存地址格式为：19 14 13 5 4 0 块标记块地址块内地址（3）Cache 的每一块在块表中有一项，Cache 的块地址为 9 位，所以块表的单元数为 29；块表中存放的是块标记，由于块标记为6位，所以块表的字长为 6位。故块表的容量为：29字×6 位。（4）直接方式

46、地址映像及变换示意图见教材。（5）cache 容量为 16KB=214B，块长为 8×32=32B，所以 Cache 有 16 ´ 1024/32=512 个块。因为 ABCDE8F8=1010 0111 1100 1101 1110 1000 1111 1000，所以块号=1010 1011 1100 1101 1110 1000 111，块内地址=11000。在直接映像方式下，主存中的第 i 块映像到 Cache 中第 i mod 512 个块中；1010 1011 1100 1101 1110 1000 111 mod 512 =10 1000 111；所以，地址 A

47、BCDE8F8 的单元在 Cache 中的地址为 10 1000 1111 1000。 45.【答题要点】本题考查的是一个复杂的调度系统，综合了内存限制和 IO 设备的限制，再结合调度算法，从而得到结果。考生要记住一定要“耐心”和“细致”。 【解答】 （1）当时刻 0，进程 P0 到达，系统内存 100K 足够，打印机空闲，故调度进入内存运行。 运行到时刻 4，进程 P1 到达，剩余内存 85K，可以分配，但是，打印机繁忙，因此，P2 被创建进入内存，但是处于阻塞状态，等待打印机就绪，此时，处理机继续运行 P0。 运行到时刻 8，进程 P0 运行结束，出让打印机，进程 P1 立即进入运行状态。

48、 运行到时刻 10，进程 P2 到达，需要内存 60K，但是，由于内存中存在 2 块碎片，不能满足 60K 内存的需求，故，进程 P2 在外存上后备，不得进入内存。 运行到时刻 11，进程 P3 到达，所需内存 20K 没有问题，创建进入内存，但是，其所需的打印机没空，故只能阻塞。P1 继续运行。 运行到时刻 12，进程 P1 退出，释放的内存不足以调入 P2；释放打印机，进程 P3 运行。 运行到时刻 16，进程 P4 到达，所需内存 10K 没有问题，创建进入内存，此时，进程P3 已经运行了 4，剩余时间为 16，比进程 P4 的 14 大，故进程 P4 抢先 P3，P4 运行，P3 带着打印机就绪（注意不是阻塞）。 运行到时刻 30，进程 P4 退出，释放内存 10K，但是进程 P2 还是不足以创建，进程 P3继续运行其剩余的 16。 运行到时刻 46，进程 P3 退出，内存释放，后备的进程 P2 立即创建进入内存，此时，系统里只有进程 P2，运行 1 到 47 退出系统运行结束。总体情况如下表所示。 所以，进程调度算法选中进程的次序为：P0；P1；P3；P4；P3；P2。 进程运行情况时间 0 4 8 10 11 12 16 30 46 47 后备 - - - P2 P2 P2 P2 P2 - -