1、计算机专业（基础综合）模拟试卷 54 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若已知一个栈的人栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 是( )。（A）i（B） n-i（C） n-i+1（D）不确定2 将一个 A1100，1100的三对角矩阵，按行优先存入 -维数组B1298 中，A 中元素 A66,65(即该元素下标 i=66，j=65)，在 B 数组中的位置 k为( )。（A）198（B） 195（C） 197（D）1963 查找效率最高的二叉排序树是
2、( )。（A）所有结点的左子树都为空的二叉排序树（B）所有结点的右子树都为空的二叉排序树（C）平衡二叉树（D）没有左子树的二叉排序树4 一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为 0，则该树的结点数是( ) 。（A）2 k-1-1（B） 2k-1（C） 2k-1+1（D）2 k-15 判断以下叙述的正确性( )。对有向图 G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点图的深度优先搜索中一般要采用栈来暂存访问过的顶点（A）、（B） 、（C） 、（D）、6 一个含有 n 个顶点和 e
3、条边的简单无向图，在其邻接矩阵存储结构中零元素的个数是( )。（A）e（B） 2e（C） n2-e（D）n 2-2e7 从二叉树的任一结点出发到根的路径上，所经过的结点序列必按其关键字降序排列的是( ) 。（A）二叉排序树（B）大顶堆（C）小顶堆（D）平衡二叉树8 顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索引表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的情况下，分块查找成功的平均查找长度为( )。（A）21（B） 23（C） 41（D）629 在下列存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系的是 ( )
4、。（A）树形存储结构（B）链式存储结构（C）索引存储结构（D）散列存储结构10 若对 27 个元素只进行三趟多路归并排序，则选取的归并路数是( )。（A）2（B） 3（C） 4（D）511 下列序列中，执行第一趟快速排序的结果是( )。（A）da，ax ，eb，de，bbffha ，gc（B） cd，eb，ax，daffha ，gc ，bb（C） gc，ax，eb，cd，bbffda，ha（D）ax，bb，cd ，daffeb，gc ，ha12 某计算机主存地址空间大小为 256MB，按字节编址。虚拟地址空间大小为4GB，采用页式存储管理，页面大小为 4KB，TLB(快表)采用全相联映射，有
5、4 个页表项，内容如表 5-1 所列。则对虚拟地址 03FF F180H 进行虚实地址变换的结果是( )。（A）0153180H（B） 0035180H（C） TLB 缺失（D）缺页13 在微程序控制的计算机中，若要修改指令系统，只要( )。（A）改变时序控制方式（B）改变微指令格式（C）增加微命令个数（D）改变控制存储器的内容14 生成多项式为 x3+x+1，则数据信息 10101 的 CRC 编码是( )。（A）1.00101e+007（B） 1.00001e+007（C） 1.01011e+007（D）111010015 判断加减法溢出时，可采用判断进位的方式，如果符号位的进位为 C0，
6、最高数值位为 C1，产生溢出的条件是( )。C0 产生进位C1 产生进位C0 、C1 都产生进位C0 、C1 都不产生进位C0 产生进位，C1 不产生进位 C0 产生进位，C1 产生进位（A）和（B） （C） （D）和16 内存按字节编址，地址从 90000H 到 CFFFFH，若用存储容量为 16K8bit 芯片构成该内存，至少需要的芯片数是( )。（A）2（B） 4（C） 8（D）1617 某计算机指令字长为 16 位，指令有双操作数、单操作数和无操作数 3 种格式，每个操作数字段均有 6 位二进制表示，该指令系统共有 m 条(m16)双操作数指令，并存在无操作数指令。若采用扩展操作码技术
7、，那么最多还可设计出单操作数指令的条数是( )。（A）2 6（B） (24-m)26-1（C） (24-m)26（D）(2 4-m)(26-1)18 指令流水线将一条指令的执行过程分为四步，其中第 1、2 和 4 步的经过时间为t，如下图 5-1 所示。若该流水线顺序执行，50 条指令共用 153 At，并且不考虑相关问题，则该流水线的瓶颈第 3 步的时间是( )。（A）2t（B） 3t（C） 4t（D）5t19 以下关于 CPU 的叙述中，错误的是( )。（A）CPU 产生每条指令的操作信号并将操作信号送往相应的部件进行控制（B）程序计数器 PC 除了存放指令地址，也可以临时存储算术逻辑运算
8、结果（C） CPU 中的控制器决定计算机运行过程的自动化（D）指令译码器是 CPU 控制器中的部件20 在系统总线中，地址总线的位数( )。（A）与机器字长有关（B）与存储单元个数有关（C）与存储字长有关（D）与存储器带宽有关21 假设某硬盘由 5 个盘片构成(共有 8 个记录面)，盘面有效记录区域的外直径为30cm，内直径为 10cm，记录位密度为 250 位mm，磁道密度为 16 道mm，每磁道分 16 个扇区，每扇区 512 字节，则该硬盘的格式化容量约是( )。22 下列说法正确的是( )。（A）计算机中一个汉字内码在主存中占有 4 个字节（B）输出的字型码 1616 点阵在缓冲存储器
9、中占有 32 个字节（C）输出的字型码 1616 点阵在缓冲存储器中占有 16 个字节（D）以上说法都不对23 下列操作系统的功能中，只需软件而不需要特殊硬件支持就能完成的功能是( )。（A）中断系统（B）地址映射（C）进程调度（D）时钟管理24 计算机系统中，创建的进程数量受到制约的主要因素是( )。（A）内存大小（B）终端数目（C）打开文件数（D）处理机数量25 能够综合考虑计算密集型和事务密集型进程的调度算法是( )。（A）时间片轮转（B）先来先服务（C）多重队列（D）彩票26 一次分配所有资源的方法可以预防死锁的发生，它破坏的死锁四个必要条件中的哪一个( )。（A）互斥条件（B）占有并
10、请求（C）非剥夺条件（D）循环等待27 有两个处理机 P1 和 P2，它们各自有一个 cache 和主存，分别为 C1、C2 和M1、M2，其性能如下表 5-2 所列：若两个处理机的指令系统相同，指令的执行时间与存储器的平均存取周期成 i，当执行某程序时，cache 的命中率为 70，则 P1 处理机的速度相比 P2 处理机是( )。（A）更快的（B）更慢的（C）相等的（D）不能确定的28 在页式存储管理中，每个页表的表项实际上是用于实现( )。（A）访问内存单元（B）静态重定位（C）动态重定位（D）装载程序29 操作系统中，建立文件系统的时刻是( )。（A）对磁盘进行分区时（B）对磁盘进行格
11、式化时（C）安装系统文件时（D）操作系统启动时30 FAT16 文件系统的一条目录项大小是 32 字节。该文件系统的根目录大小为 1个簇，每个簇有 8 个扇区，每个扇 512 字节，则根目录中能容纳的最大文件或子目录个数是( )。（A）64（B） 1（C） 128（D）25 631 一个文件的绝对路径名的出发点是( )。（A）当前目录（B）根目录（C）磁盘盘符（D）公共目录32 如果一个没有内存映射的 IO 设备与主存之间交换数据，希望这种数据交换不经过 CPU 来完成，那么，可以采用的方法是( )。（A）程序查询方式（B）中断技术（C）通道技术（D）DMA 方式33 下面对计算机网络体系结构
12、中协议所做的描述，错误的是( )。（A）网络协议的三要素是语法、语义和同步（B）协议是控制两个对等层实体之间通信的规则的集合（C）在 OSI 参考模型中，要实现第 N 层的协议，需要使用 N+1 层提供的服务（D）协议规定了对等层实体之间所交换的信息的格式和含义34 对于带宽为 6MHz 的信道，若用 8 种不同的状态来表示数据，在不考虑热噪声的情况下，该信道每秒最多能传送的位数是( )。（A）3610 6bps（B） 18106bps（C） 48106bps（D）9610 6bps35 根据 CSMACD 协议的工作原理，下列情形中需要提高最短帧长度的是( )。（A）网络传输速率不变，冲突域
13、的最大距离变短（B）冲突域的最大距离不变，网络传输速率提高（C）上层协议使用 TCP 的概率增加（D）在冲突域不变的情况下减少线路中的中继器数量36 考虑在一条 1 000m 长的电缆(无中继器)上建立一个 1Gbps 速率的 CSMACD网络，假定信号在电缆中的速度为 2108ms，那么该电缆的最小数据帧长是( )。（A）1250 B（B） 1230 B（C） 1280 B（D）1220 B37 将一条物理信道按时间分成若干时间片轮换的给多个信号使用，每一时间片由复用的一个信号占用，这样可以在一条物理信道上传输多个数字信号，这就是( )。（A）频分多路复用（B）时分多路复用（C）空分多路复用
14、（D）频分与时分混合多路复用38 主机 A 向主机 B 连续发送了两个 TCP 报文段，其序号分别为 70 和 100，如果主机 B 收到第二个报文段后发回的确认中的确认号是 180，主机 A 发送的第二个报文段中的数据大小是( )。（A）70（B） 30（C） 80（D）10039 以下关于路由器的路由表说法正确的是( )。路由表包含目的网络和到达该目的网络的完整路径路由表必须包含子网掩码目的网络和到达该目的网络路径上的下一个路由器的 IP 地址目的网络和到达该目的网络路径上的下一个路由器的 MAC 地址（A）、（B）只有 （C） 、（D）、40 FTP 客户和服务器之间一般需要建立的连接个
15、数是( )。（A）1（B） 2（C） 3（D）4二、综合应用题41-47 小题，共 70 分。41 已知下列各种初始状态(长度为 n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从大到小顺序排列)。 (1)关键字自小到大有序(key 1key 2key n)； (2)关键字自大到小逆序(key1key 2 key n)； (3)奇数关键字顺序有序，偶数关键字顺序有序(key1key 3，key 2key 4)； (4) 前半部分元素按关键字顺序有序，后半部分元素按关键字顺序逆序。 (key1key 2 key m，key m+1key m+2 keyn
16、，m 为中间位置)。42 设计一个算法，求无向图 G(采用邻接表存储)的连通分量个数。43 在虚拟地址和物理地址均为 32 位、页大小为 4KB 的某种体系结构中，假定存在表 8-1 所列的地址映像关系，问：对应于下列虚拟地址的物理地址分别是什么? (1)22433007H； (2)13385ABCH ； (3)ABC89011H 。 44 设某计算机有四个中断源，优先顺序按 1234 降序排列，若 1、2、3、4中断源的服务程序中对应的屏蔽字分别为 1110、0100、0110、1111，试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求，画出 CPU执行程序的轨迹。
17、45 某银行的营业厅有多个柜员窗口，可以同时办理业务。银行的营业厅中安排有n 张座椅供储户休息等候。每个储户在进入营业厅时会在排队机上取得一个号码，若此前没有客户，则排队机就会唤醒一个柜员为储户服务，当没有储户时柜员便可以休息。若储户较多，则所有柜员均会参与服务，当排队储户数超过柜员数时，没有被服务的储户便会在座椅上休息，并等候叫号。当座位满时，再进入营业厅的储户不再从排队机上获取号码，会离开去找另外的营业厅。若将银行的柜员和储户的行为看成是不同类型的进程，请设计一个程序，利用信号量来完成上述操作，用C 语言写出程序。46 在 Windows 操作系统中支持 FAT32 文件系统，一个文件的物
18、理结构是用文件分配表 FAT 来表示的，在 FAT32 中，FAT 表有 2 份，主 FAT 表和备用 FAT 表，都是从存储块起始排列，FAT 文件分配表的每个表项占 32 位。如果某分区为FAT32 磁盘文件系统，每簇 32 扇区，扇区的大小为 512 字节，请问：(1)该磁盘分区最大可容纳为多少字节?(2)每个 FAT 表占用的存储空间是多少字节?(3)FAT 表和备用 FAT 表共占用多少个簇?47 假设网络拓扑结构如图 82 所示，与 C 相连接的节点 B，E ，D 的权值分别是6，5，3。 如果 C 收到的三张矢量表如表 82(a)，(b)，(c)所列。 试根据距离矢量路由算法给出
19、 C 所构造的路由表，并给出计算过程，路由表结构如表 83 所列。 计算机专业（基础综合）模拟试卷 54 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 本题中所叙述的情况，栈的输出序列一定是输入序列的逆序。2 【正确答案】 B【试题解析】 根据三对角矩阵压缩方法，将 A1n1n 压缩至 B03n-3时， aij 与 bk 的对应关系为：k=2i+j-3 ；将 A1n1n 压缩至 B13n-2时， aij 与 bk 的对应关系为：k=2i+j-2 ；根据题目，A 中元素 A66,6
20、565，在 B 数组中的位置 k 为： k=2i+j-2=266+65-2=1953 【正确答案】 C【试题解析】 二叉排序树的查找效率取决于二叉排序树的深度，对于结点个数相同的二叉排序树，平衡二叉树的深度最小。4 【正确答案】 D【试题解析】 一棵深度为 k 的平衡二叉树，其每个非叶子结点的平衡因子均为0，也就是说每个非终端结点都有左子树和右子树且高度相等。因此，这样的平衡二叉树即为满二叉树，而高度为 k 的满二叉树的结点数是 2k-1。5 【正确答案】 B【试题解析】 叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。、叙述显然是正确的。6
21、 【正确答案】 D【试题解析】 由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，即图中的一条边对应邻接矩阵的两个非零元素。因此一个含有 n 个顶点和 e 条边的简单无向图的邻接矩阵中共有 n2-2e 个零元素。7 【正确答案】 C【试题解析】 对于一个堆，若堆顶为最小元素，则称为小顶堆；若堆顶为最大元素，则称为大顶堆。二叉排序树和平衡二叉树不符合。8 【正确答案】 B【试题解析】 分块查找成功的平均查找长度为 ASL=(s2+s+n)2s 。在本题中，n=123， s=123 3=41 ，故平均查找长度为 23。9 【正确答案】 D【试题解析】 散列存储结构将结点按其关键字的散列地址存储到散列
22、表中。10 【正确答案】 B【试题解析】 归并就是将两个或两个以上的有序表组合成一个新的有序表。设三趟归并中每次归并 x 个有序表，则有 27x 31，x=3。所以选取的归并路数为 3。11 【正确答案】 A【试题解析】 本题要按字典顺序进行排序，前半区间中的所有元素都应小于 ff，后半区间中的所有元素都应大于 ff。12 【正确答案】 A【试题解析】 虚存地址空间 4GB，则虚地址长度为 32 位，主存地址空间256MB，则主存地址长度为 28 位。页面大小 4KB，则页内地址长度为 12 位。虚拟地址 03FF F180H 中 180H 为页内地址，03FFFH 为虚页号，查 TLB(快表
23、)发现，该页在主存中，其实页号为 0153H，所以虚实地址变换后的结果为 0153180H。13 【正确答案】 D【试题解析】 在微程序控制的计算机中，若要修改指令系统，只需修改相应指令的微程序即可。这些微程序都存放在控制存储器中，所以只需改变控制存储器的内容。14 【正确答案】 C【试题解析】 CRC 编码由数据信息和校验位共同组成，前 5 位为数据位，后 3 位为检验位。101010001011，余数为 101，将余数 101(检验位)拼接在数据位的后面，就得到 CRC 码。循环冗余校验码是通过除法运算来建立有效信息位和校验位之间的约定关系的。假设，待编码的有效信息以多项式 M(X)表示，
24、将它左移若干位后，用另一个约定的多项式 G(X)去除，所产生的余数 R(X)就是检验位。有效信息和检验位相拼接就构成了 CRC 码。当整个 CRC 码被接收后，仍用约定的多项式 G(X)去除，若余数为 0 表明该代码是正确的；若余数不为 0 表明某一位出错，再进一步由余数值确定出错的位置，以便进行纠正。现生成多项式为 x3+x+1，表示除数为1011。15 【正确答案】 D【试题解析】 采用进位位来判断溢出时，当最高有效位和符号位的值不相同时才会产生溢出。16 【正确答案】 D【试题解析】 CFFFF-90000+1=40000 ，即 256KB，若用存储容量为 16K8bit 芯片则需芯片数
25、=(25 6K8)(16K8)=16(片)。17 【正确答案】 B【试题解析】 双操作数指令操作码字段占 4 位，单操作数指令操作码字段占 10 位，无操作数指令操作码字段占 16 位。现指令系统中有 m 条双操作数指令，则给单操作数和无操作数指令留下了(2 4-m)个扩展窗口。因为存在着无操作数指令，所以单操作数指令必须要给无操作数指令留下一个扩展窗口，最终最多可以设计出单操作数指令的数目为(2 4-m)26-1。18 【正确答案】 B【试题解析】 在图 51 中，第 3 个流水段的执行时间没有给出，显然这是一个瓶颈段，设它的执行时间为 X。通过列方程(3+X) t+49Xt=153t，可以
26、求得X=3。19 【正确答案】 B【试题解析】 程序计数器 PC 又称指令计数器，用来存放正在执行的指令地址或接着要执行的下一条指令地址，不能用于临时存储算术逻辑运算结果。20 【正确答案】 B【试题解析】 地址总线的位数与存储单元个数有关，地址总线的位数越长，可访问的存储单元个数就越多。双方向的多根信号线组成，CPU 可以沿这些线从主存或外设读入数据，也可以沿这些线向主存或外设送出数据；控制总线上传输的是控制信息，包括 CPU 送出的控制命令和主存(或外设 )返回 CPU 的反馈信号。地址总线宽度决定了 CPU 可以访问的最大的物理地址空间，简单地说就是 CPU 到底能够使用多大容量的主存。
27、例如，32 位地址线，可寻址的最大容量为 232=4 096MB(4GB)。21 【正确答案】 B【试题解析】 格式化容量计算中根据扇区数和扇区容量计算出每条磁道上的信息量，然后再乘以总磁道数。而总磁道数计算时，首先求出每面磁道数(柱面数)，再乘以记录面数。磁盘的容量有格式化容量与非格式化容量之分，磁盘上标称的容量为格式化容量。计算磁盘容量公式中的总磁道数是指记录面数与圆柱面数的乘积。其中柱面数的计算公式为：柱面数=(外半径-内半径)道密度格式化容量是磁盘实际可以使用的容量。新的磁盘在使用之前需要先进行格式化，格式化实际上就是在磁盘上划分记录区，写入各种标志信息和地址信息。这些信息占用了磁盘的
28、存储空间，故格式化之后的有效存储容量要小于非格式化容量。它的计算公式为：格式化容量=每道扇区数扇区容量 总磁道数22 【正确答案】 B【试题解析】 1616 点阵的汉字共计有 256 个点，相当于 32 个字节。23 【正确答案】 C【试题解析】 本题考查对操作系统的功能的理解。中断系统需要硬件的支持是显而易见的，在中断过程中保存和恢复寄存器的值均需要硬件支持；地址映射中需要TLB 和地址加法器等硬件支持；时钟管理需要硬件寄存器保存时钟值，进程调度由相关进程调度算法完成，不需要硬件支持。24 【正确答案】 A【试题解析】 本题考查系统中影响进程数量的限制因素。系统中创建进程的数量主要受到内存大
29、小限制。进程创建时需要分配资源，其中最主要的资源是内存，为每个进程分配内存是进程创建的主要工作。另外，进程控制块本身也要占用内存，存在系统开销。当进程创建数量较多时，系统开销本身就很大，剩下的资源分配给进程会不够；当采用虚拟存储技术时，还可能会引起抖动，严重影响系统性能。其余的选项均不会对进程创建的数量有影响，一个系统若有大量的处理机而内存较少时，也是不能发挥其作用的。25 【正确答案】 C【试题解析】 本题考查进程的调度算法。时间片轮转的主要目的是使得多个交互的用户能够及时得到响应，使得用户以为“独占“计算机在使用。因此它并没有偏好，也不会对特殊进程进行特殊服务。先来先服务最为公平，但是不能
30、区分计算密集型还是事务密集型的进程。彩票算法是一种随机算法，也不能改善综合性能，只有多重队列算法可以将不同类型的进程排列在不同的队列上，并设计针对不同队列的时间片分配和轮转算法，以获得较优的综合性能。26 【正确答案】 B【试题解析】 发生死锁的四个必要条件如下：互斥条件、占有并请求资源、非剥夺条件和循环等待条件。一次分配所有资源的方法是当进程需要资源时，一次性提出所有的请求，若请求的所有资源均满足则分配，只要有一项不满足，那么不分配任何资源，该进程阻塞，直到所有的资源空闲后，满足了进程的所有需求时再分配。这种分配方法不会部分占有资源，所以就打破了死锁的四个必要条件之一，实现了对死锁的预防。但
31、是，这种分配方式需要凑齐所有资源，所以，当一个进程所需的资源比较多时，资源的利用率会比较低，甚至会造成进程的饥饿。正确答案为 B。27 【正确答案】 B【试题解析】 本题考查多级存储层次下的平均访问时间的计算。根据题意，处理机执行指令的时间与存储器的平均存取周期成正比，因此只要计算出存储器的平均存取周期，即可比较出两者的优劣。对于处理机 P1，存储器的平均存取周期为：4007+(1 000+40)(1-0 7)=340 ns对于处理机 P2，存储器的平均存取周期为：5007+(900+50)(1-0 7)=320 ns因此可以看出，处理机 P1 需要更多的处理机时间，处理机 P1 比处理机 P
32、2 更慢。28 【正确答案】 C【试题解析】 本题考查页式存储管理的基本概念。页式存储管理的基本点是解决程序在内存中离散存放的问题，其寻址方式是借鉴于动态重定位的技术，在动态重定位技术中，通过设置基址寄存器，将程序的逻辑地址通过基址寄存器和地址加法器，动态地实现了地址转换(即每一条都是自动转换的)，操作系统在装载程序时可以不用像静态重定位那样计算程序代码的地址定位，使得地址转换快捷又简单。页式存储管理将动态重定位中的基址寄存器用一组页表来替代，当访问不同的页面时，在基址寄存器中只要存放该页面的页框号便可以快速地实现地址转换。所以说，页表项实际上是实现了动态重定位。29 【正确答案】 B【试题解
33、析】 本题考查对文件系统建立时刻的理解。文件系统是指管理一组信息集合的具体方式，主要体现在文件物理结构的实现上，因此只有建立文件系统，在该文件系统上才可以实现操作系统的安装、启动和加载等工作。磁盘分区是确定一个逻辑存储单元的大小；格式化是将文件系统创建到外存储设备上；安装操作系统只是在已经完成格式化，亦即已经确定了文件系统的外存储设备上建立操作系统启动的一系列过程；而操作系统启动是基于文件系统的使用的。30 【正确答案】 C【试题解析】 FAT16 文件系统每个目录项是 32 字节，根目录为 1 个簇，根据题意，簇的大小为 8512=4 096B，在根目录下存放 1 个文件或 1 个子目录需占
34、用 1条目录项，因此，有多少个目录项就对应有多少个文件或目录，因此，在根目录下能存放的最多目录项可以计算为 4096B32B=128，即在根目录下最多存放 128 个文件或目录。31 【正确答案】 B【试题解析】 本题考查文件路径名的概念。文件的路径名是从根目录到目标文件所经历的路径上各符号的集合。路径名有二种形式，第一种是绝对路径名，它由根目录出发，沿着目录的路径直到文件，绝对路径名总是从根目录出发，并且是唯一的。第二种是相对路径名，它与工作目录(也称当前目录)一起使用，用户一般预先指定一个目录为当前目录，这时，所有的路径名均从当前目录出发，这样的路径名，只要不是从根目录出发的，都称为相对路
35、径名。32 【正确答案】 C【试题解析】 本题考查对通道和 DMA 的理解。对于 CPU 干预的 10 操作，程序查询和中断技术都是必要的，而可以解放 CPU 且能控制数据交换的 IO 操作只能是通道技术和 DMA 方式。经过分析这两种方式，我们发现，DMA 方式需要将 IO设备的数据口地址映射到内存中，通道是不需要的，所以采用通道控制方式来作此传送是最佳的。33 【正确答案】 C【试题解析】 协议是控制两个对等层实体之间通信的规则的集合，网络协议的三要素是语法、语义和同步，其中语法和语义规定了对等层实体之间所交换的信息的格式和含义，但第 N 层协议要为第 N+1 层提供服务，因此选项 C 的
36、论述是错误的，答案是 C。34 【正确答案】 A【试题解析】 本题考查奈奎斯特定理的直接应用，注意这里采用 8 种不同的状态，因此离散个数为 8，由 C=2Hlog2N=26log28=36Mbps，因此答案为 A。35 【正确答案】 B【试题解析】 本题考查 CSMACD 协议原理。在 CSMACD 系统中，如果在帧传送的开头 T 长度时间内没有检测到冲突，那么随后也就不会再有冲突发生。令 t 为任意一个站的发送设备到达所有其他站的接收设备的延迟时间的最大值，那么 T=2t。也就是说，如果在 2t 的时间内没有检测到冲突，就表示这次传送的尝试成功了，因此在这段时间内传输的数据帧的长度就是最短
37、帧长度，假设最大距离是M，信号传播速度是 D，传输速率是 C，那么最短帧长度就是 C2(M/D)在本题中，如果传输速率不变，最大距离变短，最短帧长度也要变短，如果最大距离不变，传输速率提高，最短帧长度要增加，由于工作在数据链路层，因此传输层的 TCP 和物理层的中继器对其都没有影响，因此答案是 B。36 【正确答案】 A【试题解析】 本题考查 CSMACD 协议的基本原理，具体见 35 题答案解析部分，这里 a 代表单程端到端的传播延时，因此 2a=21000(210 8)=10s。在 1 Gbps速率下，每位的时间为 1 纳秒，所以最小帧长为 1010 -3=10000b=1 250 字节，
38、因此答案为 A。37 【正确答案】 B【试题解析】 本题考查信道复用的几种方式，题意指明这种复用是通过划分时间片，因此是时分多路复用，答案为 B。38 【正确答案】 C【试题解析】 本题考查 TCP 的可靠连接，重点是报文段的确认字段，由于主机B 收到第二个报文段后发回的确认中的确认号是 180，说明已经收到了第 179 号字节，也就说明第二个报文段的序号是从 100 到 179，故第二个报文段有 80 字节，因此答案是 C。特别注意在使用 TCP 传输数据时，如果有一个确认报文段丢失了，是不是一定会引起与该确认报文段对应的数据的重传?答案是不一定。例如某个确认丢失了，但是在该报文的重传计时器
39、到时之前，却收到了更高序号的确认，因为如果接收方没有收到低号的报文是不可能会发出高序号的确认的，所以说发送方此时不会在重传那个丢失确认的报文了。例如主机 A 连续发送两个报文段：(SEO=92，共 8 字节的数据 )和(SEQ=100 ，共 20 字节的数据)，均正确达到主机B。B 连续发送两个确认：(ACK=100)和(ACK=120)，但是前者在传送时丢失了。假如 A 在第一个报文段超时之前收到了对第二个报文段的确认，此时 A 知道，120号之前的所有字节(当然包括第一个报文段中的所有字节)均已被 B 正确接收，因此A 不会再重传第一个报文段。39 【正确答案】 B【试题解析】 本题考查网
40、络设备中路由器的作用结构和工作原理，路由器是网络互连的关键设备，其任务是转发分组。每个路由器都维护着一个路由表以决定分组的传输路径。当目的主机与源主机不在同一个网络中，则应将数据报发送给源主机所在网络上的某个路由器，由该路由器按照转发表(由路由表构造的)指出的路由将数据报转发给下一个路由器，这种交付方式称为间接交付。：为了提高路由器的查询效率和减少路由表的内容，路由表只保留到达目的主机的下一个路由器的地址，而不是保留通向目的主机的传输路径上的所有路由信息，故错误。：路由表并不一定包含子网掩码，一般只在划分了子网的网络中，路由器的路由表才使用子网掩码，如果不使用就根本不能得到网络号。而没有划分子
41、网的网络，使用默认的就可以，不需要在路由表上显示，故错误。：路由器的路由表的表项通常包含目的网络和到达该目的网络的下一个路由器的 IP 地址，因为路由器是工作在网络层，网络层使用的是 IP 地址，故正确，：路由器是工作在网络层的设备，对数据链路层是透明的，故 IV 错误。综上，只有正确，因此答案是 B。40 【正确答案】 B【试题解析】 本题考查 FTP 的基本原理。FTP 客户与服务器之间一般要建立两个连接，一个是控制连接，一个是数据连接，控制连接在整个会话期间一直保持打开，FTF客户发出的传送请求通过控制连接发送给服务器端的控制进程，但控制连接不用来传送文件。实际用于传输文件的是“数据连接
42、”。服务器端的控制进程在接收到 FTP 客户发送来的文件传输请求后就创建“数据传送进程”和“数据连接”，用来连接客户端和服务器端的数据传送进程。数据传送进程实际完成文件的传送，在传送完毕后关闭“数据传送连接”并结束运行。因此答案是 B。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 依题意，最好情况下的比较次数即为最少比较次数。(1)在这种情况下，插入第 i 个(2in)元素的比较次数为 1，因此，总的比较次数为 1+1+1+1=n-1。(2)在这种情况下，插入第 i 个(2in)元素的比较次数为 i，因此，总的比较次数为 2+3+4+n=(n-1)(n+2)2。(3)在这种
43、情况下，比较次数最少的情况是所有记录关键字均按升序排列，这时，总的比较次数为 n-1。(4)在这种情况下，后半部分元素的关键字均大于前半部分元素的关键字时需要比较次数最少，此时前半部分的比较次数=m-1 ，后半部分的比较次数 =(n-m-1)*(n-m+2)2，因此，总的比较次数为 m-1+(n-m-1)*(n-m+2)2=(n-2)(n+8)8(假设 n偶数，m=n 2)。42 【正确答案】 解法一：采用深度优先遍历方法。算法如下：#define MAX_VERTEX_NUM 20 最大顶点数为 20typedef struct ArcNode 边表结点int adjvex； 邻接点域str
44、uct ArcNode*nextarc； 指向下一个邻接点的指针域若要表示边上信息，则应增加一个数据域 infoArcNode；typedef struct VNode 顶点表结点VertexType data； 顶点域ArcNode *firstarc； 边表头指针VNode，AdjListMAX_VERTEX_NUM； AdjList 是邻接表类型typedef structAdjList adjlist； 邻接表int vexnum，arcnum； 顶点数和边数ALGraph； ALGraph 是以邻接表方式存储的图类型void DFS(ALGraph G，int V)ArcNode*p
45、；visitedv=1： 置已访问标记prinf(“d“，v) ； 输出被访问顶点的编号P=G-adjlistvfirstarc； p 指向顶点 v 的第一条边的终结点while(p!=NULL)if(visitedp-adjvex=0) 若 p-adjvex 顶点未访问，递归访问它DFS(G，P- adjvex)；p=p- nextarc； p 指向顶点 V 的下一条边的终结点int ConnNum1(ALGraph G) 求图 G 的连通分量int i，num=0 ；for(i=0；i G- n；i+)visitedi=0；for(i=0；i G- n；i+)if(visitedi=0)D
46、FS(G，i) ； 调用 DFS 算法num+：return(num)；解法二：采用广度优先遍历方法。算法如下：void BFS(ALGraph G，int v)ArcNode*p；int QuMAX_VERTEX_NUM，front=0，rear=0； 定义循环队列并初始化int W，i；for(i：0；iG-n；i+)visitedi=0； 访问标志数组初始化prinf(“2d“，v) ； 输出被访问顶点的编号visitedv=1； 置已访问标记rear=(rear+1)MAX_VERTEX_NUM；Qurear=v： v 入队while(front!=rear) 若队列不空时循环fron
47、t=(front+1)MAX_VERTEX_NUM ；w=Qufront； 出队并赋予 Wp=G-adjlistwfirstarc； 找与顶点 W 邻接的第一个顶点while(p!=NULL)if(visitedp-adjvex=0) 若当前邻接顶点未被访问printf(“2d“，p- adjvex)； 访问相邻顶点visitedp_adjvex=1； 置该顶点已被访问的标志rear=(rear+1) MAX_VERTEX_NUM! 该顶点人队Qurear=p- adjvex；p=p-nextarc； 找下一个邻接顶点printf(“n“)；int ConnNum2(ALGraph G) 求图 G 的连通分量int i，num=0 ；for(i=0；i G-n；i+)visitedi=0；for(i=0；i G-n；i+)if(visitedi=0)BFS(G，i)； 调用 BFS 算法num+：return(num)；43 【正确答案】 (1)虚拟地址 22433007H 中，虚页号为 22433H，其对应的实页号为 00
