[考研类试卷]计算机专业（基础综合）模拟试卷74及答案与解析.doc

1、计算机专业（基础综合）模拟试卷 74 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 此程序的复杂度为( ) 。for(int i=0； i0；j-)Aij=i+j；（A）O(m 2)（B） O(n2)（C） O(m*n2)（D）O(m+n)2 假设线性表中元素为(a 1，a 2，a i-1，a i，a i+1an)，设第一个元素 a1 的内存地址为 LOC(a1)，而每个元素在计算机内占 t 个存储单元，则第 i 个元素 ai 的首地址为( )。（A）LOC(a i)=(i 一 1)t(其中 1in)（B）

2、 LOC(ai)=LOC(a1)+it(其 1in)（C） LOC(ai)=LOC(a1)+(i1)t(其中 1in)（D）LOC(a i)=LOC(a1)+(i+1)t(其中 1in)3 设栈 S 和队列 Q 的初始状态为空，元素 e1，e 2，e 3，e 4，e 5 和 e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2，e 4，e 3，e 6，e 5，e 1，则栈 S 的容量至少应该是( )。（A）6（B） 4（C） 3（D）24 如果一棵完全二叉树共有 26 个结点，度为 1 的结点个数为( )。（A）0（B） 1（C） 3（D）135 已知某二叉树的

3、中序遍历序列是 debac，后序遍历序列是 dabec，则它的前序遍历序列是( )。（A）ached（B） decab（C） deabc（D）cedba6 关于 AVL(平衡二叉树) ，下列说法错误的是( )。（A）左子树与右子树高度差最多为 1（B）插入操作的时间复杂度为 O(10gn)（C）平衡二叉树是二叉排序树中的一种（D）使用平衡二叉树是为了节省空间7 设无向图 C=(V，E) 和 G=(V，E)，如果 G是 G 的生成树，则下面说法中错误的是( )。（A）G是 G 的子图（B） G是 G 的连通分量（C） G是 G 的极小连通子图且 V=V（D）G是 G 的一个无环子图8 对如下所示

4、的有向图进行拓扑排序，得到的拓扑序列可能是( )。（A）3，1，2，4，5，6（B） 3，1，2，4，6，5（C） 3，1，4，2，5，6（D）3，1，4，2，6，59 在下列查找的方法中，平均查找长度与结点个数 n 无关的查找方法是( )。（A）顺序查找（B）二分法（C）利用二叉搜索树（D）利用哈希(Hash)表10 已知一个待排序列已经基本有序，使用下面( )排序算法的效率较高。（A）直接插入排序（B）冒泡排序（C）简单选择排序（D）堆排序11 已知关键序列 5，8，12，19，28，20，15，22 是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。（A）3，5，12，8，2

5、8，20，15，22，19（B） 3，5，12，19，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，1 2，5，8，28，20，15，22，1912 运算器的主要功能是进行( )。（A）只作加法（B）逻辑运算（C）算术运算和逻辑运算（D）算术运算13 计算机在进行浮点数的相加(减)运算之前先进行对阶操作，若 x 的阶码大于 y的阶码，则应将( ) 。（A）x 的阶码缩小至与 y 的阶码相同，且使 x 的尾数部分进行算术左移（B） x 的阶码缩小至与 y 的阶码相同，且使 x 的尾数部分进行算术右移（C） y 的阶码扩大至与 x 的阶码相同，且使 y

6、的尾数部分进行算术左移（D）y 的阶码扩大至与 x 的阶码相同，且使 y 的尾数部分进行算术右移14 若二进制定点小数真值是一 01101，已知机器中用补码表示，那么这个二进制定点小数在机器中表示为( )。（A）10010（B） 11101（C） 10011（D）1011115 某机字长 32 位，主存容量 1 MB，按字编址，块长 5 12 B，Cache 共可存放 16个块，采用直接映射方式，则 Cache1 电址长度为( )。（A）11 位（B） 13 位（C） 1 8 位（D）20 位16 某 DRAM 芯片内部存储元排列成 10241024 的矩阵，已知其存取周期为O1s，最大刷新间

7、隔为 2 ms。当采用异步刷新方式时，死时间等于( )。（A）2 ms（B） 01 ms（C） 02s（D）01s17 计算机指令系统中采用多种寻址方式的目的是( )。（A）缩短指令字长（B）扩大寻址空间（C）提高编程灵活性（D）以上都包括18 在指令系统的各种寻址方式中，获取操作数最快的方式是( )。（A）直接寻址（B）立即寻址（C）寄存器寻址（D）间接寻址19 若 CPU 要执行的指令为：MOV R 0，R 1(即将寄存器 R1 中的数据传送到寄存器R0 中)，则 CPU 首先要完成的操作是( )。（A）R 1R 0（B） R1MDR（C） PCMAR（D）PCIR20 在计算机中，微程序

8、一般存放在( )。（A）主存储器（B）存储器控制器（C）控制存储器（D）辅助存储器21 某机字长 32 位，总线数据线宽度是 16 位，一个总线周期占用 4 个时钟周期，总线时钟频率为 10 MHz，则总线带宽是( )。（A）5 MBs（B） 10 MBs（C） 20 MBs（D）40 MBs22 当图像分辨率为 800*600，屏幕分辨率为 640*480 时，正确的是( )。（A）屏幕上显示一幅图像的 64左右（B）图像正好占满屏幕（C）屏幕上显示一幅完整的图像（D）图像只占屏幕的一部分23 操作系统的职能有三：管理系统硬软件资源、合理地组织计算机工作流程以及( )。（A）防止某些人以非法

9、手段进入系统（B）为用户提供良好的工作环境的接口（C）对用户的命令快速产生响应（D）作为服务机构向其他站点提供优质服务24 操作系统在运行中会采用调度策略选择新进程占用 CPU 完成其功能。下面的选项中，操作系统不会调度新进程的时机是( )。（A）当前运行进程的时间片用完（B）当前运行进程出错后阻塞（C）运行进程要等待某一个事件的发生（D）新进程被创建进入就绪队列25 单标志法中，两个进程 P1 和 P2 都要访问同一个临界资源，互斥访问的实现过程如下：对于上述过程，说法不正确的是( )。（A）进程 P1 判断 turn 变量的值与本身的标识“1”是否相等，如果不相等就一直执行这个 while

10、 循环语句直到 turn 的值等于 1 才退出（B）在运行结束后，进程会退出临界区，并将 turn 变量置为对方的值（C）单标志法能够实现进程互斥的访问临界区（D）单标志法不会导致资源浪费26 下列选项中，可以在操作系统用户态运行的指令是( )。（A）设置定时器初值（B）触发 trap 指令（C）内存单元复位（D）关闭中断允许位27 出现下列的情况可能导致死锁的是( )。（A）进程释放资源（B）一个进程进入死循环（C）多个进程竞争资源出现了循环等待（D）多个进程竞争使用共享型的设备28 在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是( )。（A

11、）存取控制列表（B）用户权限保护（C）程序状态保护（D）界地址保护29 一个 64 位的计算机系统中，地址线宽为 64 位，实际使用的虚拟地址空间的大小是 248，若采用虚拟页式存储管理，每页的大小为 213，即 8 KB，页表表项长为8 字节，采用多级页表进行管理，那么，多级页表的级次最小是( )。（A）3（B） 4（C） 5（D）630 要求每个文件在磁盘上占有一组连续的块的分配方法称作( )。（A）连续分配（B）间接分配（C）链接分配（D）索引分配31 文件系统中，文件访问控制信息存储的合理位置是( )。（A）文件控制块（B）文件分配表（C）用户口令表（D）系统注册表32 在某操作系统中

12、，假设时钟中断处理程序的执行时间为 4 ms，其中包括进程切换的开销，若果时钟中断频率为 80Hz，那么 CPU 用于时钟中断处理的时间比率是( )。（A）1 2、（B） 24（C） 32（D）4433 TCPIP 协议族中属于网络层协议的是 ( )。（A）ARP ， IP，ICMP（B） TCP，UDP（C） TCP，IP（D）SMTP，DNS34 传播时延是指( ) 。（A）发送数据时，数据块从结点进入传输媒体所需要的时间（B）电磁波在信道中需要传播一定的距离而花费的时间（C）结点缓存队列中分组排队所经历的时延（D）交换结点为存储转发而进行一些必要的处理所花费的时间35 一块网卡发出一个广

13、播，能收到这个广播的所有网卡的集合称为一个( )。（A）私有域（B）冲突域（C）广播域（D）路由域36 CIDR 路由如下：192168129024、192168130024、192168132024 和192168130024，采取路由汇聚方式，下面地址中能够访问到这四个网络的路由地址是( ) 。（A）192168128021（B） 192168128022（C） 192168130022（D）19216813202337 OSPF 协议使用( )分组来保持与其邻居的连接。（A）Hello（B） Keep-alive（C） SPF(最短路径优先)（D）LSU(链路状态更新)38 在 TCP

14、协议中，建立连接时被置为 1 的标志位和所处的字段是( )。（A）保留，ACK（B）保留，SYN（C）偏移，ACK（D）控制，SYN 39 下面( ) 协议中，是不使用 TCP 进行通信。（A）FTP（B） SMTP（C） TELNET（D）DHCP40 DNS 系统的网络应用模型是( )。（A）CS（B） BS（C） P2P（D）云二、综合应用题41-47 小题，共 70 分。41 对于下图 G，按下列条件试分别写出从顶点 O 出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示； (2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中

15、的结点是按顶点序号从大到小的次序链接的。42 已知某个序列存在“ 中值记录 ”，我们将其定义为：如果将此序列排序后，它是第 n2 个记录。对于任意一个序列求出其“中值记录” 。请回答下列问题：(1)给出算法的主要思想；(2)根据设计思想，采用 C 或 C+或 JAVA 语言表述算法，关键之处给出注释；(3)总结所用算法的时间和空间复杂度。43 设某计算机有四个中断源，优先顺序按 1234 降序排列，若 1，2，3，4中断源的服务程序中对应的屏蔽字分别为 11 lO，0100，OllO，11 1 1，试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求，画出 CPU执行程序

16、的轨迹。44 某机的指令格式如下所示： X 为寻址特征位：X=00：直接寻址；X=01 ：用变址寄存器 R0 寻址；X=10：用变址寄存器 R 寻址；X=11 ：相对寻址。 设(PC)=5431 H，(RX 1)：3515 H，(RX 2)=6766H(H 代表+六进制数)，请确定下列指令中的有效地址。 (1)8341 H；(2)1438H；(3)81 34H；(4)6228H。45 请求分页管理系统中，假设某进程的页表内容，如下表所示：页面大小为 4 KB，一次内存盼访问时间是 100 ns，一次快表(TLB)的访问时间是10 ns，处理一次缺页的平均时间为 108 ns(已含更新 TLB

17、和页表的时间)，进程的驻留集大小固定为 2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设： TLB 初始为空； 地址转换时先访问 TLB，若 TLB 未命中，再访问页表( 忽略访问页表之后的 TLB 更新时间)； 有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列 2362H、1565H、25A5H，请问： (1)依次访问上述三个虚地址，各需多少时间?给出计算过程。 (2)基于上述访问序列，虚地址 1565H 的物理地址是多少? 请说明理由。46 大部分文件系统以硬盘作为文件存储器。某一个文件系统中，其磁盘物理块的大小

18、为 512B，有一个文件，包含了 590 个逻辑记录，每个记录占 255 B；其中，为检索方便，采用成组法存储，在每个物理块上只存放 2 个记录。文件 A 在该文件目录中的位置如下图所示。此树形文件目录结构由根目录结点和作为文件中间的目录结点以及作为信息文件的叶子结点组成，每个目录项占 127 B，每个物理块存放 4 个目录项。根目录的内容常驻内存。 (1)若文件采用隐式链接文件结构，设每块的连接字占 4 B，存放在每个物理块的尾部。如果要将文件 A 读入内存，至少要读取几次硬盘?为什么? (2)若文件采用连续文件结构，如果要将文件 A 的逻辑记录号为 480 的记录读入内存，至少要读取几次硬

19、盘 ?为什么?47 在下列情况下，计算传送 1 000 KB 文件所需要的总时间，即从开始传送时起直到文件的最后一位到达目的地为止的时间。假定往返时间 RTT 是 100 ms，一个分组是 1KB(即 1024 字节)的数据，在开始传送整个的文件数据之前进行的起始握手过程需要 2RTT 的时间。 (1)带宽是 15 Mbps，数据分组可连续发送； (2)带宽是15 Mbps，但在结束发送每一个数据分组之后，必须等待一个 RTT 才能发送下一个数据分组； (3)带宽是无限大的值，即我们取发送时间为 O，并且在等待每个RTT 后可发送多达 20 个分组； (4)带宽是无限大的值，在紧接起始握手后我

20、们可以发送一个分组，此后，在第一次等待 RTT，后可发送 21 个分组，在第二次等待RTT 后可发送 22 个分组在第 n 次等待 RTT 后可发送 2n 个分组。计算机专业（基础综合）模拟试卷 74 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 内层循环语句最多执行次数为 m*n。2 【正确答案】 C【试题解析】 假设线性表中元素为(a 1，a 2，a i-1，a i，a i+1，a n)，设第一个元素 a1 的内存地址为 LOC(a1)，而每个元素在计算机内占 t 个存储单元

21、，则第 i 个元素 ai 的首地址 LOC(ai)为：LOC(a i)=LOC(a1)+(i 一 1)t(其中 1in)。3 【正确答案】 C【试题解析】 由于队列的性质，入队顺序和出队顺序是相同的。所以栈中元素的操作依次为：e 1 入栈、e 2 入栈、e 1 出栈、e 3 入栈、 e4 入栈、e 4 出栈、e 3 出栈、e 5 入栈、e 6 入栈、 e6 出栈、e 5 出栈、e 1 出栈。这期间栈中最多的数据是 3 个。4 【正确答案】 B【试题解析】 26 个结点，可知该二叉树有 5 层。由于前 4 层组成一棵满二叉树，共 15 个结点，则共有 11 个叶子结点，可知只有 1 个结点的度为

22、 1。5 【正确答案】 D【试题解析】 根据后根序与中根序可以构造出如下二叉树，很容易得到答案为D。6 【正确答案】 D【试题解析】 平衡二叉树没有节省空间，引入目的是防止排序二叉树左、右子树高度失衡。7 【正确答案】 B【试题解析】 选项 B 错误，因为连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。8 【正确答案】 D【试题解析】 在有向图中，3 号结点没有前驱只有后继，因此成为拓扑序列中的第一个结点。去掉 3 号结点，1 号结点成为没有前驱只有后继的结点，拓扑序列变成 3，1。依此类推，拓扑序列为 3，1，4，2，6，5

23、。9 【正确答案】 D【试题解析】 哈希表在查找过程中，平均的查找长度与结点个数 n 无关。10 【正确答案】 A【试题解析】 此题考查的知识点是各类排序的效率。简单选择排序和堆排序不受文件“局部有序”或文件长度；冒泡排序比较次数不变；直接插入排序比较次数减少，交换次数也较少，所以选择 A。11 【正确答案】 A【试题解析】 根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下：可以得出调整后的小根堆为 3，5，12，8，28，20，15，22，19。12 【正确答案】 C【试题解析】 运算器的主要功能是进行算术运算和逻辑运算，而传统计算机运算器的核心部件是加法电路，配以其他逻辑电路

24、即可以完成算术运算和逻辑运算。13 【正确答案】 D【试题解析】 在浮点数加减运算时，首先要进行对阶，根据对阶的规则，阶码和尾数将进行相应的操作。要对阶，首先应求出两数阶码 Ex 和 Ey 之差，即E=E x-Ey，若 E=0，表示两数阶码相等，即 Ex=Ey；若E0，表示 ExE y；若E0，表示 ExE y。 当 ExEy 时，要通过尾数的移位来改变 Ex 或 Ey，使Ex=Ey。对阶的规则是：小阶向大阶看齐。即阶码小的数的尾数右移，每右移一位，阶码加 1，直到两数的阶码相等为止。如：E x=Ey，无需对阶；E xE y，则 My 右移。每右移一位，E y+1E y，直至 Ex=Ey 为止

25、；E xE y，则 Mx 右移。每右移一位，Ex+1E x，直至 Ex=Ey 为止。14 【正确答案】 C【试题解析】 真值-01101，对应的原码表示为 11101，补码表示 10011，反码表示为 10010。移码通常用于表示阶码，不用来表示定点小数。15 【正确答案】 A【试题解析】 主存地址中除去主存字块标记的部分就是 Cache 地址，结构如下图所示： 其中，块长 512 B，主存按字(32 位)编址，512 B4 B=1 28=2 7，即块内字地址 7 位；Cache 共可存放 16 个块，采用直接映射方式，2 4=16，即 Cache 字块地址 4 位；故Cache 地址共 4+

26、7=11 位，选 A。16 【正确答案】 D【试题解析】 当采用异步刷新方式时，将对 DRAM 芯片内 1 024 行的刷新均匀分布在 2 ms 内的不同时间，每次刷新一行；这样每次刷新只需停止一个存取周期，即“死时间”为一个存取周期 01s ，故选 D。17 【正确答案】 D【试题解析】 指令中设置多种寻址方式可以使程序员编程更加灵活；采用寄存器寻址等方式可以缩短指令字长；采用间接寻址等可以扩大指令寻址空间，故A、B、C 选项的内容都正确，选 D。18 【正确答案】 B【试题解析】 立即寻址是一种特殊的寻址方式，指令中在操作码字段后面的部分不是通常意义上的地址码，而是操作数本身，也就是说数据

27、就包含在指令中，只要取出指令，也就取出了可以立即使用的操作数，不必再次访问存储器，从而提高了指令的执行速度。19 【正确答案】 C【试题解析】 无论运行什么类型的指令，CPu 首先需要取指令，取指令阶段的第一个操作就是将指令地址(程序计数器 PC 中的内容)送往存储器地址寄存器。取指周期完成的微操作序列是公共的操作，与具体指令无关，取指公共操作如下： (1)将程序计数器 PC 中的内容送至存储器地址寄存器 MAR，记作(PC)MAR； (2)向主存发读命令，记作 Read； (3)从主存中取出的指令送到存储器数据寄存器MDR，记作 M(MAR)MDR； (4)将 MDR 的内容送至指令寄存器

28、IR 中，记作(MDR)IR； (5)将 PC 的内容递增，为取下一条指令做好准备，记作(PC)+1PC。 题干虽然给出了一条具体的指令“MOV R 0，R 1”，实际上 CPU 首先要完成的操作是取指令，与具体指令是没有关系的。20 【正确答案】 C【试题解析】 微程序存放在控制存储器中，选 C。注意存控与控存的区别，控存是用来存放微程序，而存控是用来管理协调 CPU、DMA 控制器等对主存储器访问的部件。21 【正确答案】 A【试题解析】 总线数据宽度 16 位，即 2 B；一个总线周期占用 4 个时钟周期，总线时钟频率为 10MHz，即 1 s 内共有 25 M 个总线周期，共可传输 5

29、 MB 数据，总线带宽为 5 MBs。22 【正确答案】 A【试题解析】 屏幕分辨率的行、列像素数分别是图像分辨率的 80，所以屏幕上只能显示这幅图像的 64。23 【正确答案】 B【试题解析】 操作系统能够管理系统硬软件资源、合理地组织计算机工作流程以及向其他站点提供优质服务。24 【正确答案】 D【试题解析】 本题考查进程调度的时机。运行着的进程由于分配的时间到，或者运行结束，或者需要等待事件的发生(例如等待键盘响应)，或者出错，或者自我阻塞等均可以引起激活调度程序进行重新调度，选择一个新的就绪进程占有处理机运行。新的进程加入就绪队列不是引起调度的直接原因，当 CPU 正在处理其他进程的请

30、求时，该进程仍然需要等待。即使在采用高优先级优先调度算法的系统中，一个最高优先级的进程进入就绪队列，仍旧需要考虑是否允许抢先，当不允许抢先时仍然需要等待。25 【正确答案】 D【试题解析】 进程 P1 判断 tum 变量的值与本身的标识“1”是否相等，如果不相等就一直执行这个 while 循环语句直到 turn 的值等于 1 才退出；这一步骤与正好相同，都属于进入区。和 是进入临界区。在运行结束后，进程会退出临界区，并将 turn 变量置为对方的值。通过以上的讲解，可以知道，单标志法能够实现进程互斥的访问临界区。但是当一个进程不再进入临界区后，会导致其他进程再也不能进入临界区。这不符合“空闲让

31、进”的原则，资源也会发生浪费。26 【正确答案】 B【试题解析】 tr 印命令的一种常见用途是在脚本程序被中断时完成清理工作。27 【正确答案】 C【试题解析】 两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进，此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。死锁的起因：(1)互斥条件；(2) 不可剥夺条件；(3) 部分分配；(4) 环路条件。28 【正确答案】 D【试题解析】 本题考查分区保护的主要措施。在分区分配内存管理方法中，最常采用的方法是界地址保护法和基址、限长寄存器保护法。界地址保护法将每一

32、个进程在内存中的物理位置的上界和下界值存放到上下界地址寄存器中，进程的每一条指令或数据的物理地址均与这两个上下界寄存器比较，一旦低于下界寄存器或大于上界寄存器均发生越界中断，从而起到保护作用。基址、限长寄存器保护法是上述方法的改进。将进程的逻辑地址与限长寄存器比较，一旦越界就发出中断，保护内存。基址寄存器主要是用来进行逻辑地址到物理地址的转换。29 【正确答案】 B【试题解析】 本题考查虚拟页式存储管理中多级页表的计算。题目给定的条件，虚拟地址空间是 248，即没有完全使用 64 位地址。页面大小为 213，即 8 KB，则用于分页的地址线的位数为 48-13=35。下面计算每一级页表能容纳的

33、最多数量。由题意，每个页面为 8 KB，每个页表项为 8 字节，那么，一页中能容纳的页表项为8 KB 8 B=1 K，即 1 024 个页表项，可以占用 10 位地址线来寻址，故剩余的 35位地址线可以分为 3510=35，向上取整以后为 4。因此，至少 4 级页表才能完成此虚拟存储的页面映射。30 【正确答案】 A【试题解析】 连续分配方法要求每个文件在磁盘上占有一组连续的块。31 【正确答案】 A【试题解析】 文件系统中，利用文件控制块来存储和记录文件的包括操作权限等属性，便于操作系统对文件进行管理与保护。32 【正确答案】 C【试题解析】 时钟中断处理程序的执行时间为 4 ms=0004

34、 s。时钟中断频率为 80 Hz，那么时钟周期为 180 s 。CPU 用于时钟中断处理的时间比率=时钟中断处理程序的执行时间时钟周期=0 004s(180 s)=32 。33 【正确答案】 A【试题解析】 ARP(Address ResolutionProtoc01)地址解析协议用来将 IP 地址映射到以太网地址，属于网络层。IP(Internet Protocol)互联网协议，属于网络层。ICMP(Intemet Control MessageProtocol)Internet 控制消息协议，属于网络层。所以选 A。TCP、UDP 层于传输层，DNS 属于应用层，它们都不是网络层协议。34

35、 【正确答案】 B【试题解析】 35 【正确答案】 C【试题解析】 一块网卡发出一个广播，能收到这个广播的所有网卡的集合称为一个广播域。一个局域网就是一个广播域。36 【正确答案】 A【试题解析】 本题主要考查路由聚合的原理，首先从题目和选项可以得到，前两个字节都是一样，首先依次给出二进制表现形式：192168129024 是 19216810000001024：192168130024 是 19216810000010024；192168132024 是 19216810000100024；192168133024 是 19216810000101024。因此，能够包含这 4 条路由是 19

36、216810000000021，即192168128021，因此答案为 A。37 【正确答案】 A【试题解析】 此题属于记忆型的题目，OSPF 协议使用 Hello 分组来保持与其邻居的连接38 【正确答案】 D【试题解析】 本题考查 TCP 连接的过程，在建立连接的时候，必须把控制字段中的 SYN 位设置为 1，因此答案为 D。39 【正确答案】 D【试题解析】 DHCP 采用 UDP 来发送数据，所以 D 是采用面向无连接的协议的。40 【正确答案】 B【试题解析】 DNS 域名服务是基于客户服务器模式的分布式数据库系统。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 对

37、一个图进行遍历而得到的遍历序列不唯一的因素有许多： 首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，得到的结果也是不相同的。 其次，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。(1)采用邻接矩阵表示得到的顶点序列，邻接矩阵

38、如下所示：采用邻接矩阵进行深度优先遍历，在一个结点连接多个结点时，优先选择序号较小的结点；然后按深度优先遍历算法完成遍历。在本题给出的图 G 中，深度优先遍历的顺序为：0128345679。采用邻接矩阵进行广度优先遍历，在一个节点连接多个结点时，优先选择序号较小的结点；然后按广度优先遍历算法完成遍历。在本题给出的图 G 中，深度优先遍历的顺序为：0142738659。(2)采用邻接表表示得到的顶点如下所示：采用邻接表进行深度优先遍历，在一个结点连接多个结点时，优先选择序号较大的结点； 然后按深度优先遍历算法完成遍历。 在本题给出的图 G 中，深度优先遍历的顺序为：0438956712。 采用邻

39、接表进行广度优先遍历，在一个结点连接多个结点时，优先选择序号较大的结点； 然后按广度优先遍历算法完成遍历。 在本题给出的图 G 中，深度优先遍历的顺序为：O413728695。42 【正确答案】 (1)为了获取中值记录，我们将数组中的元素分成两组，一组是比当前记录大的数值，另外 一组是小于当前记录的数值。如果两组记录的数据数目相等或是最为接近，那么当前记录 即为要找的中值记录。 (2)算法的实现函数： ty pedef struct int g；大于该记录的个数 int t；小于该记录的个数 place； im GetMid(int a，int n)获取中值记录的函数 place bMAXSI

40、ZE； *对第i 个元素统计比它大和比它小的元数的个数，分别为 g 和 t* for(int i=0；iai)big+； if(aj 2)，算法实现过程中使用的辅助空间为数组，空间复杂度为 O(n)。43 【正确答案】 由于屏蔽码的作用，中断处理次序将发生变化。 1 的屏蔽字1110，说明可以中断 2，3，不能中断 4； 2 的屏蔽字 0100，说明不可以中断其他进程，优先级最低； 3 的屏蔽字 0110，说明可以中断 2，不能中断 1，4； 4 的屏蔽字 1l 11，说明可以中断所有进程，优先级最高。 因此，中断处理次序( 按降序排列)为： 4132，CPU 执行程序的轨迹如下图所示：1，2

41、，3，4 级中断源的中断请求同时出现，根据中断响应次序，首先响应第 1 级中断，但进入中断服务程序 1之后，发现其屏蔽字为 1110，即对第 4 级中断开放，所以应先执行中断服务程序4，当中断服务程序 4 执行完毕，再返回执行中断服务程序 1。接下来还剩下第 2和 3 级中断，仍然先响应第 2 级中断，但进入中断服务程序 2 之后，发现其屏蔽字为 0100，对第 3 级中断开放，所以应先执行中断服务程序 3，当中断服务程序 3 执行完毕，再返回执行中断服务程序 2。44 【正确答案】 (1)8341 H=(1000 0011 0100 0001)2； x=11，相对寻址，D=41 H，有效地址

42、 E=(PC)+D=5431 H+41 H=5472H。 (2)1438H=(0001 0100 0011 1000) 2； X=00，直接寻址，D=38H，有效地址 E=D=0038H。 (3)8134H=(1000 0001 0011 0100)； x=01，用变址寄存器 Rx，寻址，D=34H ，有效地址 E=(RX2)+D=35 15H+34H =3549H。 (4)6228H=(0110 0010 0010 1000) 2； x=10，用变址寄存器 RX2寻址，D=28H，有效地址 E=(RX2)+D=6766H+34H =679AH。45 【正确答案】 (1)根据页式管理的工作原理

43、，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为 4 KB=212B，则得到页内位移占虚地址的低 1 2 位，页号占剩余高位。可得三个虚地址的页号 P 如下( 十六进制的一位数字转换成 4 位二进制，因此，十六进制的低 12 位正好为页内位移，最高位为页号)：2362H：页号 P=2，有效位为 1，存在内存中。先访问快表 10 ns，因初始为空，不在快表中，因此，需要访问页表 100 ns 得到页框号，合成物理地址后访问主存 100 ns，共计 10 ns+100 ns+100 ns=210 ns。1565H：页号 P=1，有效位为 0，不存在内存中。先访问快表 10 ns 落空，

44、进行缺页中断处理 108ns，合成物理地址后访问主存 100 ns，共计 10 ns+100 ns+108ns+100 ns108ns。25A5H：页号 P=2，有效位为1，存在内存中。访问快表，因第一次访问已将该页号放入快表，因此花费 10 ns便可合成物理地址，访问主存 100 ns，共计 10 ns+100 ns=110 ns。 (2)当访问虚地址 1565H 时，产生缺页中断，合法驻留集为 2，必须从页表中淘汰一个页面。根据题目的最近最少使用置换算法，应淘汰 0 号页面，因此 1565H 的对应页框号为101H。由此可得 1565H 的物理地址为 101565H。46 【正确答案】 隐

45、式链接结构文件是将文件存放在外存上的非连续区域中，实质上就是一个链表，前一个物理块的最末端存放的是下一个物理块的指针，文件的结尾是结束标志“-1”。而连续文件结构将文件存放在外存上的一个连续区域中，这两个存储形式的最大区别是隐式链接文件结构不能随机存取，必须先一次存取前面的记录才能够找到所需的记录。而连续文件结构则可通过计算方式一次存取数据。(1)当文件采用隐式链接文件结构时，由题意知：磁盘物理块的大小为 512 B，每个物理块存放 2 个记录，而文件 A 包含 590 个逻辑记录，每个记录占 255 B，则要把文件 A 读入内存，所需读盘次数=5902=295 次。此外，还需计算找到文件 A

46、 的读盘次数。由于根日录在内存，所以从根目录 root 查起，不需要读硬盘，得到第一级目录 bin，dev，home 等的磁盘位置，第一次读硬盘将 home 的目录内容读入，查到 mary 的盘块地址指针。根据该指针，第二次读硬盘得到 mary 目录的信息，找到 doe 的盘块地址指针，依此，第三次读硬盘得到 do：的信息，从中找到文件A 的链表的起始指针。以后就读入文件 A 的内容。所以，把文件 A 读入内存需读盘次数为：295+3=298 次。某些操作系统是可以将子目录放入内存的，同学答题时应明确题意。(2)当文件为连续结构时，由于第一次读盘可获取 home 的信息内容，据此，第二次读硬盘

47、得到 mary 的内容，第三次读硬盘得到 doc 的内容，从中找到文件 A 的起始地址。通过计算，第 480 条逻辑记录在第 4802=240 号磁盘块中，只需要将文件A 的起始地址加上 240 的偏移量，1 次读盘就可读出第 479 和第 480 号的逻辑记录。即共需要读取 4 次硬盘，就将文件 A 的逻辑记录号为 480 的记录读入内存。47 【正确答案】 本题考查数据报交换的过程。数据报交换首先是分组交换，即把要发送的数据先分组，对各个分组编号，加上源地址和目的地址以及约定的分组头信息，IP 网络就是典型的数据报交换网络。因此，本题中的分组的具体形式是TCP 报文。时间的计算要包含握手时

48、间，传输时间和发送时间。注意：对 RTT 的要求，可以求解前 3 个问题。对于第 4 个问题，注意：首先要判断 n 的值是多少时才能刚好发送完全部数据，剩下的计算就简单了，详细过程见 解答部分。 (1)2 个起始的 RTT；1002=200 ms=02 s； 1 KB=8 bit1 024=8 192 bit： 发送时间：1 000 KB15 Mbps=8 1 92 000 bit1500 000 bits=546 s； 传输时间：RTT2=1002=50 ms=005 s ； 所以，总时间=起始握手时间+发送时间+传输时间，即 02+546+0 05=57t1s。 (2)总共发送 1 000 个分组，需要在上一小题答案的基础上再增加 999 个 RTT，571+999 落空，访问页表 100 ns01=10561 S ，所以总时间是 10561 S。 (3)1 000 KB1 KB=1 000 分组 1000 分组20 分组=50 个 RTT 50-1=49 个 RTT，总的延迟时间为2RTT+49RTT+O5RTT=515RTT=0 1515=515S。 (4)取n=9，1+2+4+2 9=29+1 一 1=1 023，这样就可以发送所有的 1 000 个分组，而且在第 9 次等待 RTT 后只需发送(512