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

1、2012 全国硕士研究生入学统一考试计算机学科专业基础综合试题模拟题三 、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个 选项中，只有一个选项最符合试题要求。1. 在具有n个结点的顺序表，算法的时间复杂度是0(1)的操作是B. I、 IVa,b,c,则通过出栈操作可能得到B.5C.6A. 访问第i个结点(1 < i奇n求第B. 在第i个结点后插入一个新结点C. 删除第i个结点(1 < i < n)D. 将n个结点从大到小排序2. 使用双链表存储线性表，其优点是 I 提高查找速度III 节约存储空间 A I、II3. 若进栈序列为A. 4i个结点

2、的直接前驱(2 < i < n)(1 < i < n)II 更方便数据的插入和删除IV 很快回收存储空间C.仅 IID. II、III、IVa,b,c 的不同排列个数为D.74. 若对n阶对称矩阵A1.n，仁n以行序为主序方式下将其下三角的元素(包括主对角线上的所有元素)依次存放于一维数组B1.n(n+1)/2中，则在B中确定a (ivj)的位置 k 的关系是A. i(i-1)/2+jB. j(j-1)/2+iC. i(i+1)/2+jD. j(j+1)/2+i5. 在线索化二叉树中， t 所指结点没有左子树的充要条件是A. t->left=NULLB. t-&g

3、t;ltag=1C. t->ltag=1 且 t->left=NULLD. 以上都不对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,11C. 6,7,9,11D. 6,8,9,118. 设散列表表长m=14，散列函数 H(k)=k MOD 11 ，表中已有 15,38,61,84四个元

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

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

6、，其存储容量为4MB，若按半字编址，它的寻址范围是A.4MB B. 2MB C. 2MD.1M17. EPROM 是指 。A. 读写存储器B. 只读存储器C. 闪速存储器D. .光擦除可编程只读存储器18. 主存储器和 CPU 之间增加 cache 的目的是 。A. 解决 CPU 和主存之间的速度匹配问题B. 扩大主存贮器容量C. 扩大 CPU 中通用寄存器的数量D. 既扩大主存贮器容量，又扩大 CPU 中通用寄存器的数量19. 指令的寻址方式有顺序和跳跃两种方式，采用跳跃寻址方式，可以实现 。A. 堆栈寻址 ； B. 程序的条件转移 ；C. 程序的无条件转移 ； D. 程序的条件转移或无条件

7、转移20. 由于 CPU 内部的操作速度较快，而 CPU 访问一次主存所花的时间较长，因此机器周期通常用来规定。A. 主存中读取一个指令字的最短时间B. 主存中读取一个数据字的最长时间C. 主存中写入一个数据字的平均时间D. 主存中取一个数据字的平均时间21. 系统总线中地址线的功能是 。A. 选择主存单元地址 B. 选择进行信息传输的设备C. 选择外存地址 D. 指定主存和 I/O 设备接口电路的地址22. 在单级中断系统中， CPU 一旦响应中断，则立即关闭 标志，以防本次中断服务结束前同级的其他中断源产生另一次中断进行干扰。A. 中断允许 B. 中断请求 C. 中断屏蔽 D. 中断保护2

8、3. 分布式操作系统与网络操作系统本质上的不同之处是A.实现各台计算机之间的通信B 共享网络中的资源C.满足较大规模的应用D 系统中若干台计算机相互协同完成同一任务24. 若有一进程拥有 100 个线程，这些线程都属于用户级线程，则在系统调度执行时间上占 用的时间片是A 1B10025. 出现下列的情况可能导致死锁的是A.进程释放资源C.多个进程竞争资源出现了循环等待C1/100D0B. 个进程进入死循环D.多个进程竞争使用共享型的设备26. 在一个多道系统中，就绪的进程数目越多，处理机的效率变化的情况是A. 变高B. 变低C. 不变D. 不确定27. 某进程页面访问序列为 4，3，2，1，4

9、，3，5，4， 3，2，1，5，且开始执行时内存中没有页面，分配给该进程的物理页框数是3，则采用 FIFO 页面置换算法和 LRU （最近最久未使用）页面置换算法时缺页率分别是A. 83； 75B. 85%；70 C. 75， 83D. 84； 7528. 考虑下面的段的分配， 0 段的段基址为 100，段长 500， 1 段的段基址为 1000，段长 60， 2 段的段基址为 90，段长 200， 3 段的段基址为 1300，段长 400，4 段的段基址为 1600， 段长 120。则逻辑地址（ 2， 88）和逻辑地址（ 4，123）对应的物理地址分别是A. 178, 1723B .越界中断

10、，1723C. 178，越界中断D. 188，越界中断29. 可能使系统产生抖动现象的存储分配方案是I动态分区分配；简单页式；川虚拟页式；W简单段页式；V简单段式；W虚拟段式A.I和口B .川和WC.V和WD.m和W30. 某一个磁盘共有 16 个盘面,每个盘面上从外到内共有 30000 个磁道（或称 30000 个柱 面）,每个磁道有 250 个扇区。假定存储信息时以一个扇区作为一个存储块,盘面号（磁 头号）、磁道号和扇区号均从 0 开始编号,那么,盘块号 1002578 对应的盘面号、磁道31.32.3333.343536373839的40号和扇区号是A. 1, 2500, 78B. 10

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

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

13、网络地址是为了限制路由信息传播的范围，OSPF协议把网络划分成4种区域（Area），其中连接各个区域的传输网络是A.不完全存根区域B .标准区域C.主干区域 D .存根区域一台主机的IP地址为,子网掩码为 。现在用户需要配置该主机 的默认路由。经过观察发现，与该主机直接相连的路由器具有如下4个IP地址和子网掩码：I. IP 地址：，子网掩码：II. IP 地址：，子网掩码：川.IP 地址：，子网掩码:IV. IP 地址：，子网掩码：请问IP地址和子网屏蔽码可能是该主机的默认路由的是A.I和I B.I和川C.I、川和VD .川和V以太网交换机中的端口 /MAC地址映射表是A.是由交换机的生产厂商

14、建立的B.是交换机在数据转发过程中通过学习动态建立C. 是由网络管理员建立的D.是由网络用户利用特殊的命令建立的下面关于电子邮件的说法中，不正确的是A.电子邮件只能发送文本文件B .电子邮件可以发送图形文件C.电子邮件可以发送二进制文件D .电子邮件可以发送主页形式的文件二、综合应用题：4147小题，共70分。请将答案写在答题纸指定位置上。41. （ 10分）对于下图 G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。（1 ）假定它们均采用邻接矩阵表示；（2）假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大圏G42.

15、 （ 13分）一棵二叉树的繁茂度定义为R层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。43. （ 10分）某机主存容量为 4M16位，且存储字长等于指令字长，若该机的指令系统具备120种操作。操作码位数固定，且具有直接、间接、立即、相对四种寻址方式。（1 ）画出一地址指令格式并指出各字段的作用；（2）该指令直接寻址的最大范围；（3）次间址的寻址范围；（4）相对寻址的寻址范围。44. （ 13分）设主存容量 1MB，有16KB直接相联映像的 Cache，假定该 Cache的块为8个 32位的字。解答下列问题：（1）写出 Cache地址格式。（2）写出主存地址格式。（3）块表的容

16、量为多大？（4）画出直接方式地址映像及变换示意图。（5）主存地址为 ABCDE8F8的单元在 Cache中的什么位置？45. （ 7分）设有某多道程序系统中有用户使用的内存100K，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计, 采用最短剩余时间优先的进程调度算法，进程最短剩余时间相同时采用先来先服务的算 法，进程调度时机选择在进程执行结束或新进程创建时，现有进程如下表所示：进程调度表进程创建时间要求执行时间要求内存申请打印机P00815K1P14430K1P210160K0P3112020K1P416、配内存低地址区14域且不允许移动

17、，那忆么求解0系、统优丿先J 配匚内存低地址区中弄佬Z4、圧r4-t、卄工域，且不兀许移动,1血八甘*丄站口口 T口那么，求解由给出进程调度算法选中进程1 的次序，丿Ibu明理山。（2）全部进程执行结束全部所用的时间是多少？平均周转时间是多少？46. （8分）大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小为512B，有一个文件，包含了590个逻辑记录，每个记录占255B ;其中，为检索方便，采用成组法存储，在每个物理块上只存放2个记录。文件 A在该文件目录中的位置如下图所示。root此树形文件目录结构由根目录结点和作为文件中间的目录结点以及作为信息文件的叶结点组成，每

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

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

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

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

22、对于有向图，邻接矩阵的第i行元素的和即为第i个顶点的岀度，而邻接矩阵的第j列元素的和即为第j个顶点的入度。7. B【答案解析】由折半查找过程可得，第一次11(111) / 2 = 6，第二次 11) / 2 =9，8. A【答案解析】元素 15,38,61,84 分别存储在 4,5,6,7 单元，而元素 49 的散列地址为 5，发生冲 突，向后探测 3 个单元，其存储地址为 8。9. D【答案解析】 I 和 II 的说法都是错误的，顺序查找法可以在顺序存储结构和链式存储结构上 进行，而折半查找只能在可以进行随机存取的存储结构上进行，即只能在顺序存储的有序表 上进行。10. C 【答案解析】选择

23、排序在最好、最坏、平均情况下的时间性能均为O(n) ，归并排序在最好、最坏、平均情况下的时间性能均为O(nlogn)。11. A 【答案解析】本题主要考查各种排序的空间复杂度。堆排序只是需要在元素比较进行交换时需要常数个存储空间，它需要的辅助空间为O(1)；快速排序在递归过程中需要栈结构来保存递归的信息，它需要的辅助空间为O(log2 n)；归并排序需要长度为元素个数的线性空间来保存归并的结果，它需要的辅助空间为O(n).12. C 13. B 14. B 15. D 16C17D 18A 19. D 20A21D22B23. D 【答案解析】分布式计算机系统是由多台计算机组成的系统。与网络操

24、作系统的主要区别在 于任务的分布性，即把一个大任务分为若干个子任务，分派到不同的处理器上执行。实现各 台计算机之间的通信，共享网络中的资源以及提供各类服务是网络操作系统和分布式操作系 统所必须具备的功能，相互没有本质的区别；选项C满足较大规模的应用”没有体现多机系统的特性；网络操作系统一般不会拆开一个作业，而分布式操作系统却会在用户不知道的 情况下自动将作业拆分，分布到不同的计算机或处理机上运行，再将结果汇总。分布式操作 系统需要更加严格的通信协议，同步技术，共享技术等，也具有更高的强健性。因此，最适 合的答案为 D.24. A 【答案解析】本题主要考查关于进程和线程之间资源共享的知识点。在引

25、入线程的操作系统 中，线程是进程中的一个实体，是系统独立调度和分派的基本单位。但是线程自己基本上不 拥有系统资源，所以它不是资源分配的基本单位，它只拥有一部分在运行中必不可少的与处 理机相关的资源，如线程状态、寄存器上下文和栈等，它同样有就绪、阻塞和执行三种基本 状态。它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程；同一个进程中的多个线程之间可以并发执行。由于用户线程不依赖于操作系统内核，因此，操作系统内核是不知道用户线程的存在的，用户线程是由用户来管理和调度的，用户利用线程库提供的API来创建、同步、调度和管理线程。所以，用户线程的调度在用户程序内部进

26、行，通常采用非抢先式和更简单的规则，也无须用户态和核心态切换，所以速度很快。由于操作系统不知道用户线程的存在，所以，操作系统把CPU的时间片分配给用户进程，再由用户进程的管理器将时间分配给用户线程。那么，用户进程能得到的时间片即为所有用户线程共享。因此，正确答案应为Ao 25. C【答案解析】本题考查死锁的四个必要条件。死锁的四个必要条件是：互斥；占有并等待； 非剥夺；循环等待。本题中，出现了循环等待的现象，意味着可能导致死锁的出现。进程释 放资源不会导致死锁，进程自己进入死循环只能产生饥饿，不涉及到别人。共享型设备允许 多个进程申请使用，故也不会造成死锁。正确答案为Co26. C【答案解析】

27、从进程的状态图中可以看出，进程就绪数目越多，争夺CPU的进程就越多，但是，只要就绪队列不为空，CPU总是可以调度进程运行，保持繁忙。这与就绪进程的数目没有关系，除非就绪队列为空，则CPU进入系统懈怠，此时 CPU的效率会下降。因此正确答案为Co27. CB43214333522C4321444355缺页YYYYYYYNNYYN缺页率为9/2 = 75%润LFU算法1进行页面调度时页面装壬入和调出的情况如下表氐LRU算法进行页面调度143543【答案解析】根据题意分析，缺页率；缺页次数/访问的页面数100%，所以此题相当于计算缺页次数。采用FIFO算法进行页面调度时页面装入和调出的情况如下表。序

28、列43FIFO算法进行页面调度214354321I5A43214355521I1B43214354321C4321435432缺页YYYYYYYNNYYY缺页率为10/12 = 83%因j此，正确答案为 C)序列 432215A43214354321528. C【答案解析】简单地考察逻辑地址到物理地址转换的问题，理解缺页中断和越界中断的问题。逻辑地址（2，88），在第2段，因为88小于100,所以对应的物理地址为：基址 +偏移量=90+88 = 178o逻辑地址（4，123），在第4段，因为123大于120,造成段内地址超过该段 的长度，所以产生越界中断。因此逻辑地址（2, 88）对应的物理地

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

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

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

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

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

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

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

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

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

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

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

40、度优先序列广度优先序列G 0 1 2 8 3 4 5 6 7 9 O 1 4 2 7 3 8 6 5 9米用邻接表表示得到的顶点序列如下表所示：图深度优先序列广度优先序列G O 4 3 8 9 5 6 7 1 2 O 4 1 3 7 2 8 6 9 5答题要点】w m 口必川劝【血/丿15tit 画丿卩一应血 n42.【分析】数之后，再从计数器中挑出最大值。【解答】typedef struct BiTNodeTEIemType data;struct BiTNode *lchild;*rchild;BiTNode, *BiTree;typedef structBiTNode node;int

41、layer; BTNRecord;int FanMao(Bitree T) in t cou ntMAX;Ini tQueue(Q);EnQueue(Q,T,O);while(!QueueEmpty(Q) DeQueue(Q,r);/左、右孩子指针/包含结点所在层次的记录类型/cou nt数组存放每一层的结点数/Q 的元素为 BTNRecord类型/利用层序遍历来统计各层的结点数coun tr.layer+;if(r.no de->lchild)EnQueue(Q,r.node->lchild,r.laye 叶1);if(r.no de->rchild)EnQueue(Q,r

42、.node->rchild,r.laye 叶1);h=rayer;for(max n=coun t0,i=1;co un ti;i+) if(co un ti>max n) maxn=coun ti;return h*max n;/最后一个队列元素所在层就是树的高度/求层最大结点数43.【答题要点】格式：7位操作码2位寻址方式 7位地址码直接寻址0000-007FH16 位：216=64K(1 )(2)(3)(4)OOOO-FFFFH全部存储空间或 4M字或8M字节44.【答题要点】(1) Cache容量16KB, 16KB=24，所以 Cache地址为14位；块的大小为 8个32

43、位的字,即32字节，所以块内地址为5位，块地址 9位。Cache地址格式为：13块地址54块内地址(2)址为主存容量1MB，1MB=220，所以主存地址为 20位；块的大小为 32字节，所以块内地5位，块地址_9位块标记«6位。主存地址格式为19块标记0块地址块内地址(3)Cpche 的每一块在块表中有一项；Cache 的块地址为 9 位； 所以块表的单元数为6位，所以块表的字长为表中存放的是块标记，由于块标记为6 位。故块表的容量为:2929 ;块字X 6位。(4) 直接方式地址映像及变换示意图见教材。(5) cache 容量为 16KB=2"b,块长为 8X 32=32

44、B 所以 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 mod512 =10 1000 111;所以，地址 ABCDE8F8 的单元在 Cache 中的地址为 10 1000 1111 1000。45.【答题要点】本题考查的是

45、一个复杂的调度系统，综合了内存限制和10设备的限制，再结合调度算法，从而得到结果。考生要记住一定要耐心”和 细致”【解答】(1)当时刻0,进程P0到达，系统内存100K足够，打印机空闲，故调度进入内存运行。 运行到时刻4,进程P1到达，剩余内存 85K，可以分配，但是，打印机繁忙，因此，P2被创建进入内存，但是处于阻塞状态，等待打印机就绪，此时，处理机继续运行P0。运行到时刻8,进程P0运行结束，出让打印机，进程P1立即进入运行状态。运行到时刻10,进程P2到达，需要内存 60K，但是，由于内存中存在2块碎片，不能满足60K内存的需求，故，进程 P2在外存上后备，不得进入内存。运行到时刻11,

46、进程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立即创建进入内存，此时,系统里只有进

47、程 P2,运行1至U 47退出系统运行结束。总体情况如下表所示。所以，进程调度算法选中进程的次序为：PO; P1; P3; P4; P3; P2。运行P0P0P1P1P1P3P4P3P2结束就绪P3阻塞P1P30 15K0 15K015K0 45K10 45K0 45K空闲1545454565656565600内存100K100K100K100K100K100K100K100K100K100K打印, 机1-111-111100(2)据上:表，全部进程执行结束全部所用的时间是47;平均周转时间是 47/5=9.22 口46.L答题要点时间 0进程运行情况4810 11 1216304647后备.P2P2P2