1、计算机专业（基础综合）模拟试卷 58 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。（A）单链表（B）带有头指针的单循环链表（C）双链表（D）带有尾指针的单循环链表2 循环队列用数组 A0m-1存放其元素值，已知其头尾指针分别为 front 和 rear，则当前元素个数为( ) 。（A）(rear-front+m)MOD m（B） rear-front+1（C） rear-front-1（D）r
2、ear-front3 二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1，8，列下标 j=1， 2， ，10。设每个字符占一个字节。若 A 按行先存储，元素 A8，5的起始地址与当 A 按列先存储时起始地址相同的元素是 ( )。（A）A8 ，5（B） A3，10（C） A5，8（D）A0 ，94 已知某二叉树的中序、层序序列为 DBAFCE、FDEBCA，则该二叉树的后序序列为( )。（A）BCDEAF、（B） ABDCEF（C） DBACEF（D）DABECF5 在平衡二叉树中，下面叙述正确的是( )。（A）任意结点的左、右子树结点数目相同（B）任意结点的左、右子树高度相
3、同（C）任意结点的左、右子树高度之差的绝对值不大于 1（D）不存在度为 1 的结点6 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有 n 个结点，采用三叉链表存储时，每个结点的数据域需要 d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为 k(起始下标为 1)，采用顺序存储更节省空间的情况是( ) 。（A）d12n(k-n)（B） d12n(k-n)（C） d12n(k+n)（D）d12n(k+n)7 二叉树若用顺序方法存储，则下列 4 种算法中运算时间复杂度最小的是( )。（A）先
4、序遍历二叉树（B）判断两个指定位置的结点是否在同一层上（C）层次遍历二叉树（D）根据结点的值查找其存储位置8 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。（A）求关键路径的方法（B）求最短路径的迪杰斯特拉方法（C）深度优先遍历算法（D）广度优先遍历算法9 有一个有序表为1，3， 9，12，32，41，45，62，75，77，82，95，99)，当折半查找值为 82 的结点时，查找成功的比较次数是( )。（A）1（B） 2（C） 4（D）810 下面关于 B-树和 B4 一树的叙述中，不正确的是( )。（A）B-树和 B+树都是平衡的多分树（B） B-树和 B+树都
5、可用于文件的索引结构（C） B-树和 B+树都能有效地支持随机检索（D）B-树和 B+树都能有效地支持顺序检索11 最好情况下的算法时间复杂度为 O(n)的是( ) 。（A）插入排序（B）归并排序（C）快速排序（D）堆排序12 哈佛(Harvard)结构的基本特点是 ( )。（A）采用多指令流单数据流（B）程序和数据在不同的存储空间（C）堆栈操作（D）存储器按内容选择地址13 若二进制定点小数真值是-01101，机器中表示为 10010，则该数采用的编码方法是( )。（A）原码（B）补码（C）反码（D）移码14 汉字“啊”的十进制区位码为 “16-01”，它的十六进制机内码是( )。（A）16
6、01H（B） 9081H（C） BOA1H（D）B081H15 原码乘法时，符号位单独处理，乘积的符号是( )。（A）两个操作数符号相“与”（B）两个操作数符号相“或”（C）两个操作数符号相“异或“（D）两个操作数中绝对值较大数的符号16 页式存储系统的逻辑地址是由页号和页内地址两部分组成，地址变换过程如下图 4-1 所示。假定页面的大小为 8K，图中所示的十进制逻辑地址 9612 经过地址变换后，形成的物理地址 a(十进制) 是( )。（A）42380（B） 25996（C） 9612（D）819217 在指令系统的各种寻址方式中，获取操作数最快的方式是( )。（A）直接寻址（B）立即寻址（
7、C）寄存器寻址（D）间接寻址18 在计算机体系结构中，CPU 内部包括程序计数器 PC、存储器数据寄存器MDR、指令寄存器 IR 和存储器地址寄存器 MAR 等。若 CPU 要执行的指令为：MOV R0，#100(即将数值 100 传送到寄存器 R0 中 )，则 CPU 首先要完成的操作是( )。（A）100R0（B） 100MDR（C） PCMAR（D）PCIR19 在微指令的编码方式中，若微命令数相同，下列叙述中正确的是( )。直接控制方式与编码控制方式的微指令长度相等最短编码控制和直接控制方式不影响微指令字长编码控制方式的微指令比直接控制方式的微指令短直接控制的微指令比字段编码的微指令长
8、字段直接编码的微指令与字段间接编码的微指令长度相等字段间接编码的微指令比字段直接编码的微指令长（A）和（B） 和（C） 和（D）、和20 下列计算机总线属于串行总线的是( )。（A）PCI（B） 1 394（C） EISA（D）ISA21 某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 16001200 像素，颜色深度为 24 位，若不采用压缩存储技术，使用内部存储器最多可以存储的照片数是( )。（A）12（B） 25（C） 13（D）2322 中断向量表中保存的是( )。（A）被中断程序的返回地址（B）中断服务程序人口地址（C）中断优先级（D）中断源编码23 对于设计实时操作系统，
9、不属于其设计目标的是( )。（A）安全可靠（B）处理机效率（C）及时响应输入（D）快速处理请求24 操作系统中引入进程概念以后，下列现象不能解决的是( )。（A）提高资源利用率（B）正确描述程序的执行情况（C）提高编程能力（D）使处理机与外设之间能有效地并行25 两个旅行社甲和乙为旅客到某航空公司订飞机票，形成互斥资源的是( )。（A）旅行社（B）航空公司（C）飞机票（D）旅行社与航空公司26 在进程互斥和同步的处理中可以采用管程的方法，下列不属于管程的组成部分的是( )。（A）数据结构说明（B）状态字（C）一组过程函数（D）初始化语句27 能在计算机系统中实现内存保护的方法是( )。（A）当
10、“基址寄存器值 访问逻辑地址限长寄存器的值”时不许访问（B）每次地址访问需要修改基址寄存器和限长寄存器的值（C） “基址寄存器+限长寄存器的值 “是访问的有效地址（D）采用基址寄存器和限长寄存器可以实现存储保护28 在某个计算机系统中，内存的分配采用按需调页的方式，测得当前 CPU 的利用率为 8，硬盘交换空间的利用率为 55，硬盘的繁忙率为 97，其他设备的利用率可以忽略不计，由此断定系统发生异常，此异常可能会是( )，解决办法是( )Belady 现象 抖动 死锁 饥饿 加大交换空间容量 增加内存容量增加 CPU 数量 增加并发进程数（A）和（B） 和 VI（C） 和（D）和29 某操作系
11、统内存管理系统采用动态可变分区的方式，管理使用链表的方式，若某时刻的内存分配如表 4-1 所列。当一个进程退出时能使得链表中表项减少 2 项的进程的进程号是( )。（A）2115（B） 2346（C） 3877（D）455330 通常对文件系统来说，文件名和文件属性可以找到的地方是( )。（A）目录（B）索引（C）字典（D）作业控制块31 为保证文件的安全，操作系统一般采用多种方式来保护文件。为防止未经授权对文件的访问而造成的篡改或破坏，所采取的方法是( )。（A）访问控制列表（B）转储备份（C）加密数据（D）口令保护32 CPU 输出数据的速度远远高于打印机的打印速度，为解决这一矛盾，可采用
12、的技术是( ) 。（A）并行技术（B）通道技术（C）缓冲技术（D）虚存技术33 在不同网络结点的对等层之间通信需要的是( )。（A）模块接 H（B）对等层协议（C）电信号（D）传输介质34 关于数据交换，下列叙述不正确的是( )。（A）电路交换是面向连接（B）分组交换比报文交换具有更好的网络响应速度（C）报文交换无存储转发过程（D）分组交换有存储转发过程35 当 DHCP 客户计算机第一次启动或初始化 IP 时，广播发送给本地子网的消息是( )。（A）DHCP DISCOVER（B） DHCP REQUEST（C） DHCP OFFER（D）DHCP ACK36 网络由 6 个路由器互连而成，
13、路由器之间的链路费用如图 4-2 所示，从 PC 机到服务器的最短路径和通路费用是( )。（A）136，7（B） 1456，4（C） 1436，6（D）12456，737 一个 C 类网络的子网掩码为 255255252252，则该 C 类网络的主机数目是( )。（A）2046（B） 1022（C） 510（D）12838 主机 A 向主机 B 发送 IP 分组，途中经过了 4 个路由器，那么，在 IP 分组的发送和转发过程中，共使用 ARP 协议的次数是( )。（A）1（B） 3（C） 4（D）539 关于以太网交换机，下面的论述中不正确的是( )。（A）交换机工作在数据链路层（B）交换机的
14、每个端口形成一个冲突域（C）交换机支持多端口同时收发数据（D）交换机是一种多端口中继器40 一台主机要解析 wwwabc.educn 的 IP 地址，如果这台主机配置的域名服务器为 2021206668，因特网顶级域名服务器为 11286，而存储wwwAbc.educn 与其 IP 地址对应关系的域名服务器为 2021131610，那么这台主机解析该域名通常首先查询的服务器是( )。（A）2021206668 域名服务器（B） 11286 域名服务器（C） 2021131610 域名服务器（D）不能确定，可从这三个域名服务器中任选一个二、综合应用题41-47 小题，共 70 分。41 假设有
15、12 个初始归并段，其长度分别为85，68，62，9，18，60，20，3，6，8，44，30；现要进行 4 路外部归并排序，试画出表示归并过程的最佳归并树，并计算树的带权路径长度 WPL。42 一棵二叉树的繁茂度定义为 R 层结点数的最大值与树的高度的乘积。编写一个算法求二叉树的繁茂度。43 某微机的寻址范围为 64 KB，其存储器选择器信号为 M，接有 8 片 8 KB 的存储器，试完成下列问题。(1)画出选片译码逻辑图。(2)写出每片 RAM 的寻址范围。(3)如果运行时发现不论往哪片存储器存放 8KB 数据，以 4000H 起始地址的存储芯片都有与之相同的数据，分析故障原因。(4)如果
16、运行时发现以 0000H 为起始地址的一片存储芯片不能读写，分析故障原因。(5)若发现译码器中的地址线 A13与 CPO 断线，并搭接到低电平，问后果如何?(6)如果发现只能对第 14 片 RAM 进行读写，试分析故障原因。44 某模型机的通路结构如图 71 所示，用寄存器传送语句(如 PCMAR)，拟出下列指令从读取到执行的完整流程。 (1)数据传送指令 MOV X(R0)，Y(R 1)，源和目的操作数地址均采用变址寻址，第 1 个参数 X 为源操作数的形式地址，第 2个参数为目的操作数的形式地址，分别位于指令的第 2 个和第 3 个存储字。 (2)数据求反指令 COM-(R0)，采用自减型
17、寄存器间接寻址，结果送回自减后的地址单元。 45 某工厂有一个仓库可以存放甲、乙两种零部件，甲零件可以存放 m 件，乙零件可以存放 n 件，车间 A 专门生产甲零件，每次 1 件，每生产 1 件存放进仓库 1 件；车间 B 专门生产零件乙，每次 1 件，每生产 1 件存放进仓库 1 件。总装车间每次从仓库取出 2 件甲零件、1 件乙零件组装成成品，车间 A、B 和总装车间必须互斥进入仓库。当仓库内甲、乙零件分别达到 m、n 件时，车间 A、B 分别停止生产。而仓库内任何一种零件为 0 时，总装车间停产。根据上述规则，请利用信号量机制，设计一个可以让车间 A、B 和总装车间协调运转的程序，并说明
18、各个信号量的意义，用类 C 语言写出整个过程。46 某文件系统空间的最大容量为 1 6TB(1T=240)，以存储块为基本分配单位，存储块大小为 4 KB。文件控制块(FCB)包含一个 1024B 的索引表区。请回答下列问题。(1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节? (2)假设索引表区采用如下结构：第 015 字节采用格式表示文件创建时预分配的连续存储空间，其中起始块号占 8B，块数占 8B；剩余 1008 字节采用直接索引结构，一个索引项占 8B，则可支持的单个文件最大长度是多少字节?为了使单个文
19、件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47 主机 H 通过快速以太网连接到某网络中，H 与服务器 S 使用 TCP 通信时，在H 上捕获的其中 2 个 IP 分组如表 73(a)所列： 请回答下列问题。 (1)表 73(a)中的 IP 分组中，是应用层哪种协议 ?主机 H 和服务器的 IP 地址分别是多少? (2)假如第三条报文是表 73(b)中报文，请问这是正确的么?如果有错误，请给出正确的报文字段填充和原因，注意不考虑校验和字段。(3)第三条报文如果在网络中正确传输，需要填充的数据是多少? 注：IP 分组头和 TCP 段头结构分别如图 72(a)，图 72
20、(b)所示。 计算机专业（基础综合）模拟试卷 58 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适，考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以，答案是 D。2 【正确答案】 A【试题解析】 少用一个元素的空间以区分队空和队满，求循环队列中元素的个数的方法是(rear-front+m)MOD m。3 【正确答案】 B【试题解析】 元素 A8
21、，5的起始地址与当 A 按列先存储时的 Ai，j元素的起始地址相同，即 810+5-1=(j-1)9+i，将四个备选答案代入，可得正确答案。4 【正确答案】 B【试题解析】 按照遍历左子树要在遍历右子树之前进行的原则，根据访问根结点位置的不同，可得到二叉树的先序、中序和后序 3 种遍历方法。层序遍历时从根结点(第 1 层) 出发，首先访问第 1 层的树根结点，然后从左到右依次访问第 2 层上的结点，其次是第 3 层上的结点，依次类推，自上而下、自左向右逐层访问各层上的结点。由层序序列可得：F 是树根结点，D、E 是第 2 层结点；结合中序序列 DBA构成 F 的左子树，CE 构成 F 的右子树
22、，进一步有 C 是 E 的左结点、E 无右结点；这样 A 是第 4 层结点，据 DBA 序列有 B 是 D 的右结点，A 是 B 的右结点。易知后序序列为：ABDCEF。5 【正确答案】 C【试题解析】 平衡二叉树又称 AVL。它或者是一棵空树，或者是具有下列性质的二叉树：(1)左子树和右子树都是平衡二叉树；(2)左子树和右子树的深度之差的绝对值不超过 1。二叉树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度。可见，平衡二叉树上所有结点的平衡因子只可能是-1，0，1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。6 【正确答案】 A【试题解析】 顺序
23、存储所需空间为：kd ，三叉链表每个结点需要 3 个指针空间和1 个数据空间，即存储所需空间为：n(d+4*3) ，当 kdn(d+12)，即 d(12n/k-n)时，顺序存储更节省空间。对完全二叉树，k 等于 n，显然不论 d 值多大多小，顺序存储更省空间。7 【正确答案】 B【试题解析】 选项 A、C、D 运算的时间复杂度都是 O(n)，而选项 B 的运算的时间复杂度为 O(1)，因为对于指定位置 p 和 q 的两个结点，判断是否在同一层上，只需判断两者log 2p=log2q是否成立。8 【正确答案】 C【试题解析】 当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出
24、DFSTraverse 算法)即为逆向的拓扑序列。9 【正确答案】 C【试题解析】 构造相应的判定树如图 46 所示，先找中间结点 45。再找77，95，最后找到 82，经过 4 次比较。10 【正确答案】 D【试题解析】 因为 B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是 B 一树不具有这种结构特性，所以只支持从根结点的随机检索，而不支持直接从叶子结点开始的顺序检索。11 【正确答案】 A【试题解析】 直接插入排序在最好情况下，即待排序列已按关键码有序
25、时，每趟操作只需 1 次比较，不需移动。总比较次数=n-1 次。所以时间复杂度为 O(n)。归并排序和堆排序在平均情况和最好情况下的时间复杂度为 O(nlogn)。快速排序在平均情况下的时间复杂度为 O(nlogn)，最坏情况下的时间复杂度为 O(n2)。12 【正确答案】 B【试题解析】 哈佛结构的指令和数据是完全分开的，存储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来存放数据。存储器分为两部分，一个是程序存储器，用来存放指令，另一个是数据存储器，用来存放数据。在冯.诺依曼结构中不能同时取指令和取操作数，而哈佛结构允许同时获取指令字(来自程序存储器) 和操作数(来自
26、数据存储器) 。13 【正确答案】 C【试题解析】 真值-01101，对应的原码表示为 11101，补码表示为10011，反码表示为 10010。移码通常用于表示阶码，不用来表示定点小数。14 【正确答案】 C【试题解析】 区位码 16-01(十进制)=1001 H，国标码=1001 H+2020H=3021 H，机内码=3021H+8080H=BOAlH。汉字的区位码长 4 位，前两位表示区号，后两位表示位号，区号和位号用十进制数表示。汉字国标码和汉字机内码都是两字节长的代码，汉字机内码是在相应国标码的每个字节最高位上加“1”。3 种汉字编码的关系：汉字国标码一汉字区位码(十六进制)+202
27、0H汉字机内码一汉字国标码+8080H汉字机内码一汉字区位码(十六进制)+AOAOH通常，汉字的国标码和机内码都用十六进制数表示，而汉字区位码用十进制数表示，所以在 3 种汉字编码的转换时，千万不要忘记先将十进制的区位码变成十六进制之后，再利用上述关系式进行转换。15 【正确答案】 C【试题解析】 原码的符号位为“1”表示负数，为“0”表示正数。原码做乘法时，符号位单独处理，乘积的符号是两个操作数符号相“异或”，同号为正，异号为负。16 【正确答案】 B【试题解析】 由于页面大小为 8K，则十进制逻辑地址 9612 处于第 1 虚页中，页内地址 1420，其对应的实页为第 3 页，故 a=38
28、192+1420=25996。17 【正确答案】 B【试题解析】 立即寻址是一种特殊的寻址方式，指令中在操作码字段后面的部分不是通常意义上的地址码，而是操作数本身，也就是说数据就包含在指令中，只要取出指令，也就取出了可以立即使用的操作数，不必再次访问存储器，从而提高了指令的执行速度。18 【正确答案】 C【试题解析】 无论运行什么类型的指令，CPU 首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器 PC 中的内容)送往存储器地址寄存器。取指周期完成的微操作序列是公共的操作，与具体指令无关，取指公共操作如下：(1)将程序计数器 PC 中的内容送至存储器地址寄存器 MAR，记作(P
29、C)MAR；(2)向主存发读命令，记作 Read；(3)从主存中取出的指令送到存储器数据寄存器 MDR，记作 M(MAR)MDR；(4)将 MDR 的内容送至指令寄存器 IR 中，记作(MDR)IR；(5)将 PC 的内容递增，为取下一条指令做好准备，记作(PC)+1PC。19 【正确答案】 A【试题解析】 微指令的操作控制字段可分为直接控制法、最短编码法和字段编码法，字段编码法中又可以进一步分为字段直接编码法和字段间接编码法。若微命令数相同，微指令操作控制字段的长度由短至长依次为：最短编码一字段间接编码一字段直接编码一直接控制。操作控制字段短则相应的微指令字长就短。20 【正确答案】 B【试
30、题解析】 IEEE-1394 是高性能的串行总线。21 【正确答案】 D【试题解析】 颜色深度为 24 位(3 个字节)，每张照片的存储量为160012003B55 MB，128 MB55 MB=233，所以内置的存储空间最多可存储 23 张照片。22 【正确答案】 B【试题解析】 中断向量表是用来存放中断服务程序的入口地址的。23 【正确答案】 B【试题解析】 本题考查实时操作系统的设计目标。实时操作系统要求能对用户的请求在规定的时间内完成，同时需要保证进程运行的安全性和高可靠性。而处理机的效率不是实时操作系统设计所关心的。24 【正确答案】 C【试题解析】 本题考查引入进程的目的。在操作系
31、统中，为了使程序在多道程序环境下能并发执行，并能对并发执行的程序加以控制和描述，从而引入了进程的概念。而多道程序系统提高了资源的利用率，在多道程序系统中引入进程，可以更好地描述进程的执行情况，使得处理机与外设之间有效地并行，而编程能力只能靠程序员自己提高。25 【正确答案】 C【试题解析】 本题考查互斥资源的问题，一张飞机票不能售给不同的旅客，因此飞机票是互斥资源，其他因素只是为完成飞机票订票的中间过程，与互斥资源无关。26 【正确答案】 B【试题解析】 本题考查学生对管程的理解。一个管程定义了一个数据结构和能为并发进程所运行的一组操作，这组操作能同步进程和改变管程中的数据。由定义可知，管程由
32、三部分组成：局部于管程的共享数据说明；对该数据结构进行操作的一组过程函数；对局部于管程的数据设置初始值的语句。所以，状态字不是管程的组成部分。管程内的局部变量只能被局限于管程内的过程所访问。反之亦然，即局限于管程内的过程只能访问管程内的变量。任何进程只能通过管程提供的过程入口进入管程。任何时刻最多只能有一个进程在管程中运行。保证进程互斥地进入管程是由编译器负责的，也就是说，管程是一种编程语言的构件，它的实现需要得到编译器的支持。27 【正确答案】 D【试题解析】 本题考查存储保护的方法。考查基址、限长寄存器方式下是如何进行越界判断的。在基址、限长寄存器的保护方式下，系统为每个并发进程设置一个基
33、址寄存器和一个限长寄存器，限长寄存器保存的是进程的长度，所以有关系式：基址寄存器的值访问地址(基址寄存器的值+限长寄存器的值)。在此注意，进程地址一般是从 0 开始，故下限需要包含，但是不得包含上限。因此选项 A 上限缺少基址，选项 B 不可能实现，选项 C 只是表述了上限，只有选项 D 是正确的。28 【正确答案】 B【试题解析】 本题考查按需调页下提高系统效率的措施。首先判断系统异常是属于什么异常，从测试数据看，CPU 不忙，交换空间也不满，就是硬盘的 IO 非常繁忙，所以不是交换空间不够，系统也没有死锁，主要瓶颈在内外存交换上，因此可能的最大情况就是抖动，即由于内存紧缺，并发进程数多，采
34、用按需调页而引起的频繁地换人换出作业。对于抖动问题的解决，最好的办法是增加内存，或减少并发进程数，单纯地增大交换分区的大小或增加 CPU 数量或提高 CPU 处理能力都不能解决根本问题。29 【正确答案】 B【试题解析】 分区式存储管理法也称界地址存储管理法。是一种能满足多道程序设计需要的最简单的存储管理方案。可变分区存储管理是在作业装入和处理过程中，根据作业的实际需要动态地划分存储空间。在系统初启时，整个内存空间除操作系统占用区外，其余空间可以看成是一个大空闲区。随着作业一个个被调入内存运行，并且分给它们一个相应于作业大小的内存分区使用，直到作业完成后才释放其所占用的内存分区。由于各作业大小
35、和完成的时间是各不相同的，这样经过一段时间后，内存就由原来一个完整的分区而变成了多个分区，这些分区中有些分区被作业占用，有些分区是空闲的。管理这些分区可以采用链表的方式。本题中，我们看到确定的表项是 7 项，有分配使用的，也有空闲的，当一个进程退出时，它要归还所占用的分区，使得该分区变为空闲，若归还的分区上或下有空闲分区，则需要合并，形成一个大的空闲分区，为下次分配做好准备。根据题意，若要使得链表减少 2 项表项，则需要在归还一个分区后，至少合并掉 2 个空闲分区，这样才能减少 2 项表项，那么，只有进程的上下分区均为空闲分区时，归还以后分别与它们合并，由原来的 3项(2 空 1 用)合并为
36、1 项( 空) ，从而减少 2 项表项，因此正确答案为 B。30 【正确答案】 A【试题解析】 在文件系统中，为每个文件建立一个目录(或称文件目录或目录项)，文件目录记录文件的名字、文件长度和文件存放的外存地址以及文件属性、文件创建时间日期等信息。文件目录在大部分文件系统中又称为文件控制块，即 FCB。31 【正确答案】 A【试题解析】 本题考查的是文件的保护。系统中的文件有些是只能由文件拥有者使用，有些是可以共享的，独享的文件需要采取保护措施，防止非法用户存取文件。保护文件的方法可以有多种，定时转储备份可以防止设备故障造成的文件损坏；口令保护和加密数据可以保护文件被非法窃取时不会泄密；而对于
37、授权用户的使用，一般采用访问控制列表来对文件的权限进行分配，从而保证文件的安全。32 【正确答案】 C【试题解析】 缓冲技术的引入主要解决 CPU 速度和外设速度不匹配的问题，它同时减少了通道数量上的占用，提高了 CPU、IO 和通道的并发性，减少了中断的次数，放宽了 CPU 对中断响应的时间要求，例如打印、文件访问，网络收发等场合，均要用到缓冲技术。33 【正确答案】 B【试题解析】 本题考查计算机网络体系结构，注意对等层是指在计算机网络协议层次中，将数据直接传递给对方的任何两个同样的层次，因此对等层之间通信必需对等层之间的协议，这里选项 A 是相邻层之间通信所必需的，选项 C 和 D 属于
38、物理层，答案是 B。34 【正确答案】 C【试题解析】 该题考查数据交换的原理，要明确报文是一份完整的信息，而分组是报文分组的简称，又叫信息包，将报文划分为若干格式化信息单位作为网络层的数据传输单元。分组交换方式：将一份完整的报文划分为若干组，每个分组独立的从源节点发送到目的节点，目的节点收到这些分组后，再组装成源报文。其特点是化整为零，即将完整的较长的报文划分为较小的分组，以分组单位传输数据。优点是减少节点缓冲区容量，并有利于差错控制。而存储转发是指每个节点均设有缓冲区，分组到达某节点后，先存储在缓冲区中，等待输出链路空闲时再转发到下一个节点。本题中面向连接的只有电路交换，存储转发只有分组和
39、报文，由于分组交换的灵活性，使其具有更好的响应速度，因此答案是 C。35 【正确答案】 A【试题解析】 本题考查 DHCP 协议的工作原理，需要 IP 地址的主机在启动时就向 DHCP 服务器广播发送发现报文(DHCP DISCOVER) ，这时该主机就成为DHCP 客户。本地网络上所有主机都能收到此广播报文，但只有 DHCP 服务器才回答此广播报文。DHCP 服务器先在其数据库中查找该计算机的配置信息。若找到，则返回找到的信息。若找不到，则从服务器的 IP 地址池(address poo1)中取一个地址分配给该计算机。DHCP 服务器的回答报文叫做提供报文(DHCP OFFER)。客户计算机
40、初始化 IP 的时候，首先要查找 DHCP 服务器，因此要发送的消息是DHCP DISCOVER，答案是 A。36 【正确答案】 B【试题解析】 本题考查链路状态路由算法，将网络看成连通图。每条链路以其“费用”为权值。通过 Dijkstra 最短路径算法求出任意两个节点之间的最短距离，本题中，就是以 PC 机所连接的路由器 1 为根节点，计算到达其他网络的最短路径，也就是费用最小的路径，这样可以直接从选项中得出答案，是 B。37 【正确答案】 D【试题解析】 本题考查 IPv4 子网划分，首先明确 C 类网络的掩码是2552550255，而 252 的二进制是 1111 1100，由此可知可划
41、分 26=64 个子网，每个子网的主机数为 22-2= 2，因此该 C 类网络的主机数目是 642=128，因此答案是 D。38 【正确答案】 D【试题解析】 本题考查 ARP 协议的原理，注意 ARP 协议的四种典型情况，发送方是主机，要把 IP 数据报发送到本网络上的另一个主机。这时用 ARP 找到目的主机的硬件地址；发送方是主机，要把 IP 数据报发送到另一个网络上的一个主机。这时用 ARP 找到本网络上的一个路由器的硬件地址。剩下的工作由这个路由器来完成；发送方是路由器，要把 IP 数据报转发到本网络上的一个主机。这时用 ARP找到目的主机的硬件地址；发送方是路由器，要把 IP 数据报
42、转发到另一个网络上的一个主机。这时用 ARP 找到本网络上的一个路由器的硬件地址。剩下的工作由这个路由器来完成。本题中发送方首先是主机，然后是途中经过的路由器，4 台路由器，就要使用 4 次 ARP 协议，因此总共是 5 次，答案是 D。39 【正确答案】 D【试题解析】 本题考查交换机的工作原理和特性，交换机是工作在数据链路层的网络设备，每个端口是独立的冲突域，交换机的交换结构保证了多端口同时进行数据交换，多端口的中继器可以认为是集线器，其所有端口处于同一个冲突域内，因此答案为 D。40 【正确答案】 A【试题解析】 本题考查域名解析的过程，一个主机发出 DNS 查询报文时，这个查询报文首先
43、被送往该主机的本地域名服务器。当本地域名服务器不能立即回答某个主机的查询时，该本地域名服务器就以 DNS 客户的身份向某一根域名服务器查询。若根域名服务器也没有该主机的信息时(但此时根域名服务器一定知道该主机的授权域名服务器的 IP 地址)，有两种做法：(1)递归查询：根域名服务器向该主机的授权域名服务器发送 DNS 查询报文，查询结果再逐级返回给原主机；(2)递归与迭代相结合的方法：根域名服务器把授权域名服务器的 IP 地址返回给本地域名服务器，由本地域名服务器再去查询。无论是递归方式，还是迭代方式，主机进行域名解析的第一步都是向自己的本地域名服务器发起请求，因此答案为A。二、综合应用题41
44、-47 小题，共 70 分。41 【正确答案】 应加 4-(12-1)mod(4-1)-1=1 个虚段。WPL=(3+6+8)3+(9+18+20+30+44+60+62)2+(68+85)1=69042 【正确答案】 typedef struct BiTNodeTElemType data；struct BiTNode*ichild；*rchild； 左、右孩子指针BiTNode，*BiTree；typedef structBiTNode node；int layer；BTNRecord； 包含结点所在层次的记录类型int FanMao(Bitree T)int countMAx； coun
45、t 数组存放每一层的结点数InitQueue(Q)； Q 的元素为 BTNRecord 类型EnQueue(Q，T，0)；while(!QueueEmpty(Q) 利用层序遍历来统计各层的结点数DeQueue(Q，r)；countrlayer+：if(rnodeichild)EnQueue(Q，r nodeichild，rlayer+1)；if(rnoderchild)EnQueue(Q，r noderchild，rlayer+1)；h=r1ayer； 最后一个队列元素所在层就是树的高度for(maxn=count0，i=1；counti；i+)if(countimaxn)maxn=count
46、i； 求层最大结点数return h*maxn；43 【正确答案】 (1)选片译码逻辑如图 75 所示。 (2)8 片RAM 的寻址范围分别是：0000H1 FFFH、2000H3FFFH 、4000 H5FFFH、 6000H7FFFH、8000H9FFFH、A000H BFFFH 、COOOHDFFFH 和 EOOOHFFFFH。 (3)说明译码器有误， 输出始终为低。因该输出接至第3 片 RAM 的 端，该片对应的地址范围是 4000H5FFFH，故不论往哪片 RAM存放 8K 数据，该存储芯片始终被选中，所以都有与之相同的数据。 (4)说明 Y0 输出始终为高。因 RAM 的片选信号是
47、低电平有效，故用 Y0 作片选信号的存储芯片(对应 0000H1FFFH 地址范围 )不能读写，而其他芯片可以读写。 (5) 若发现 A13 与CPU 断线，并搭接到低电平的故障，则 信号均不可能输出 0，故第2、4、6、8 片 RAM 始终不被选中。 (6)说明译码器的 C 输入端始终为低，可以检查一下 A15 是否搭接到低电平上。44 【正确答案】 (1)MOV X(R 0)，Y(R 1) PCMAR，Read ；取指令 MMDRIR PC+1PC PCMAR，Read ；取源操作数形式地址 MMDRC PC+1PC C+R0MAR，Read ；形成源操作数有效地址，并取源操作数 MMDR
48、C ；源操作数暂存 C 中 PCMAR ，Read ；取目的操作数形式地址 MMDRD 11PC+1 一 PC 12D+R1MAR ；形成目的操作数有效地址 13CMDR ；将源操作数送存储器数据寄存器 14MDRM，Write ；将源操作数写入目的有效地址中 (2)COM-(R 0) PCMAR，Read ；取指令 MMDRIR PC+1PC R0-1R 0，R 0-1MAR，Read；修改 R0 的内容(源和目的操作数地址) MMDRD ；取出源操作数 DMDR ；将源操作数取反 MDRM，Write ；写入目的地址中45 【正确答案】 设信号量 mutex 用于车间的互斥， positionA、positionB 和partA，partB 为资源信号量，分别表示仓库中零件甲、乙的空位数和满位数，positionA+partA=m；positionB+partB=n；以下编程：deftype int semaphore； 定义信号量semaphore mutex=1； 进入仓库的互斥信号量semaphore positionA=m，positionB=n；车间 A、B 生产的零件甲、乙存放的位
