1、计算机专业（基础综合）模拟试卷 56 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则下面最合适的存储方式是( )。（A）单链表（B）循环双链表（C）单循环链表（D）带有尾指针的单循环链表2 表长为 n 的顺序存储的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素所需移动元素的平均个数为( )。（A）n（B） n2（C） (n-1) 2（D）(n+1) 23 在下面的应用中，通常使用栈的是( )。 递归调用 括号匹配 表
2、达式求值（A）、（B） 、（C） 、（D）、4 用链表方式存储的队列，在进行删除运算时，下面正确的是( )。（A）仅修改头指针（B）仅修改尾指针（C）头、尾指针都要修改（D）头、尾指针可能都要修改5 在含有 15 个结点的平衡二叉树上，查找关键字为 28(存在该结点)的结点，则依次比较的关键字有可能是( )。（A）30，36（B） 38，48，28（C） 48，18，38，28（D）60，30，50，40，38，366 设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1，则 T中的叶子数是( ) 。（A）5（B） 6（C） 7（D）87 简单无向图的邻接矩阵是
3、对称的，可以对其进行压缩存储。若无向图 G 有 n 个结点，其邻接矩阵为 A1n，1n，且压缩存储在 B1n(n-1)2。若按行压缩存储对称矩阵的上三角元素，则当 n 等于 10 时，边(v6，v3)的信息存储在( )。（A）B18（B） B19（C） B20（D）B218 以下关于图的说法正确的是( )。在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧a，b若一个有向图的邻接矩阵中对角线以下元素均为 0，则该图的拓扑序列必定存在在 AOE 网中一定只有一条关键路径（A）、（B） 、（C） 、（D）仅有9 设无向图 G=(V，E)和 G=(V，E)，如果 G是 G 的生
4、成树，则下面说法中错误的是( )。（A）G是 G 的子图（B） G是 G 的连通分量（C） G是 G 的极小连通子图且 V=V（D）G是 G 的一个无环子图10 下列排序算法中，时间复杂度为 O(nlogn)且与用额外空间最少的是( )。（A）堆排序（B）起泡排序（C）快速排序（D）希尔排序11 采用简单选择排序，比较次数与移动次数分别是( )。（A）O(n)， O(log n)（B） O(log n)，O(n 2)（C） O(n2)，O(n)（D）O(nlog n) ，O(n)12 计算机系统的层次结构，下列五个级别机器由下到上的顺序是( )。机器语言机器汇编语言机器高级语言机器微程序控制机
5、器操作系统机器（A）（B） （C） （D）13 已知定点整数 x 的补码为 1 x3x2x1X0，且 x-8，则必是( )。（A）x 3=1，x 2x 0 至少有一个 1（B） x3=0，x 2x 0 至少有一个 1（C） x3=1，x 2x 0 任意（D）x 3=0，x 2x 0 任意14 在规格化浮点运算中，若某浮点数为 25110101，其中尾数为补码表示，则该数是( )。（A）不需规格化（B）需右移规格化（C）需将尾数左移一位规格化（D）需将尾数左移两位规格化15 “春”字的机内码为 B4BAH，由此可以推算它在 GB2312-80 国家标准中所在的区号是( ) 。（A）19 区（B）
6、 20 区（C） 3 区（D）3516 在一个按字节编址的计算机中，若数据在存储器中以小端方案存放。假定 int型变量 i 的地址为 08000000H，i 的机器数为 01234567H，地址 08000000H 单元的内容是( ) 。（A）OI H（B） 23 H（C） 45 H（D）67 H17 在 CPU 的状态寄存器中，若符号标志为“1”，表示运算结果是( )。（A）正（B）负（C）零（D）不一定18 在微程序控制器设计中，假设微命令采用最短编码法，需产生 N 种微操作。则微命令控制字段要设置的位数是( )。（A）log 2(N+1)（B） N（C） log2N（D）log 2N+1
7、19 下列是有关冯.诺依曼结构计算机中指令和数据存放位置的叙述，其中正确的是( )。（A）指令存放在内存中，数据存放在外存中（B）指令和数据任何时候都存放在内存中（C）指令和数据任何时候都存放在外存中（D）程序被启动前指令和数据都存放在外存中，而启动后指令和数据被装人内存20 一个磁盘的转速为 7 200 rmin，每个磁道有 160 个扇区，每个扇区有 512B，那么在理想情况下，其数据传输率为( )。（A）7 200160 KBs（B） 7 200 KBs（C） 9 600 KBs（D）19 200 KBs21 有效容量为 128KB 的 Cache，每块 16 字节，8 路组相联。字节地
8、址为1234567H 的单元调入该 Cache，其 Tag 应是( )。（A）1234H（B） 2468H（C） 04DH（D）12345H22 中断的概念是( ) 。（A）暂停正在运行的程序（B）暂停对内存的访问（C）暂停 CPU 运行（D）IO 设备的输入或输出23 当发生键盘中断时，进入中断处理程序的起始是( )。（A）发起中断的用户程序（B）操作系统系统程序（C）固化的硬件代码程序（D）既非用户亦非系统程序24 在单处理机的多进程系统中，进程什么时候占用处理机以及决定占用时间的长短是( )。（A）进程相应的代码长度（B）进程总共需要运行的时间（C）进程特点和进程调度策略（D）进程完成什
9、么功能25 下列方式中，不是死锁预防策略的是( )。（A）一次分配所有资源（B）银行家算法（C）建立 SPOOLing 系统（D）按序分配资源26 操作系统中的三级调度是( )。（A）处理机调度、资源调度和网络调度（B）处理机调度、内外存调度和作业调度（C）处理机调度、内外存调度和负载均衡调度（D）处理机调度、设备调度和作业调度27 在某计算机中采用了多级存储体系，设计有 cache，主存和磁盘。假设访问cache 一个字需要花费 10 ns，若该字不在 cache 中但是存在在主存中，那么需要100 ns 载入 cache，然后重新开始定位。若该字既不在 cache 中，也不在主存中，那么需
10、要 10 ms 的时间装入主存，再用 100 ns 复制到 cache，再开始定位。设 cahe的命中率为 090，主存的命中率为 075，那么，该系统访问一个字的平均时间是( )。（A）25 000 ns（B） 250 023 ns（C） 250 017 ns（D）250 020 ns28 在一个采用请求调页的虚拟存储系统中，存放在外存上的程序代码调入内存的时机是( ) 。（A）在进程创建填写进程表时（B）在进程创建分配内存时（C）在进程被调度占用处理机执行时（D）在每次产生缺页中断时29 有四个用户 Li，Zhang，Sun 和 Wang，对应的用户组分别为system，staff，stu
11、dent，stuation。下列五个文件的访问控制列表和访问控制权限如下：File0：(Li，*，rwx) ，(*，staff，rw-)File1：(*，system，rwx)File2：(Li，*，rw-)，(Wang ，staff ，rw-) ， (Sun，*，rw-)File3：(*，student，rw-)File4：(Zhang，*，-x) ，(*，stuation，rwx)那么，只能够读写其中两个文件的用户是( )。（A）Li（B） Zhang（C） Sun（D）Wang30 已知某磁盘的平均转速为转秒，平均寻道时间为 T 秒，每个磁道可以存储的字节数为 N，现向该磁盘读写 b 字
12、节的数据，采用随机寻道的方法，每道的所有扇区组成一个簇，请问：平均访问时间是( )。（A）bN*(r+T)（B） bN*T（C） (bN+T)*r（D）b*T N+r31 文件系统中，当调用 open()去打开一个文件时，其主要目的是( )。（A）把文件内容从外存调入内存（B）把文件的控制信息从外存调入内存（C）把文件系统的文件分配表调入内存（D）把文件系统的控制信息调入内存32 在 UNIX 操作系统中，为块设备提供了一种特殊的读取方式，它是 ( )。（A）提前读取（B）串行读取（C）并发读取（D）延迟读取33 OSI 模型中完成路径选择功能的层次是( )。（A）物理层（B）数据链路层（C）
13、网络层（D）传输层34 现采用调相与调幅相结合的调制方式，载波有四种相位变化和两种振幅变化，调制速率是 600 波特，那么数据速率是( )。（A）1 200 bps（B） 1 800 bps（C） 2 400 bps（D）3 600 bps35 数据链路层采用后退 N 帧协议，如果发送窗口的大小是 30，那么为了保证协议不会出错，序列号至少需要的位数是( )。（A）4（B） 5（C） 6（D）736 CSMACD 以太网中，发生冲突后，重发前的退避时间最大是( )。（A）65 536 个时间片（B） 65 535 个时间片（C） 1 024 个时间片（D）1 023 个时间片37 IEEE 8
14、0211 采用了 CSMACA 协议，下面关于这个协议的描述中错误的是 ( )。（A）各个发送站在两次帧间隔(IFS)之间进行竞争发送（B）每一个发送站维持一个后退计数器并监听网络上的通信（C）各个发送站按业务的优先级获得不同的发送机会（D）CSMACA 协议适用于突发性业务38 局域网交换机首先完整地接收数据帧，并进行差错检测。如果正确，则根据帧目的地址确定输出端口号再转发出去。这种交换方式是( )。（A）直接交换（B）改进直接交换（C）存储转发交换（D）查询交换39 主机甲向主机乙发送一个(FIN=1，seq=12220)的 TCP 段，期望与主机乙断开TCP 连接，若主机乙同意该连接请求
15、，则主机乙向主机甲发送的正确的 TCP 段可能是( )。（A）(SYN=0 ，ACK=1 ， seq=11221，ack=11221)（B） (SYN=1，ACK=1 ， seq=11220，ack=1 1220)（C） (SYN=1，ACK=1 ， seq=11221，ack=11221)（D）(SYN=0 ，ACK=1 ， seq=11220，ack=11220)40 在下列协议中，客户端和服务器之间采用面向无连接的协议进行通信的是( )。（A）FTP（B） SMTP（C） POP3（D）DHCP二、综合应用题41-47 小题，共 70 分。41 已知加权有向图如图 32 所示，回答下列问
16、题： (1)画出该有向图的邻接矩阵； (2) 试利用 Dijkstra 算法求图 32 中从顶点 a 到其他各顶点间的最短路径，并给出求解过程。42 已知数组 A1n 的元素类型为整型 int，设计一个时间和空间上尽可能高效的算法，将其调整为左右两部分，左边所有元素为负整数，右边所有元素为正整数。不要求对这些元素排序。(1)给出算法的基本设计思想；(2)根据设计思想，采用 C 或 C+或 Java 语言表述算法，关键之处给出注释；(3)说明你所设计算法的时间复杂度和空间复杂度。43 设主存容量 1 MB，有 16 KB 直接相联映像的 Cache，假定该 Cache 的块为 8个 32 位的字
17、。解答下列问题：(1)写出 Cache 的地址格式；(2)写出主存的地址格式；(3)块表的容量有多大；(4)主存地址为 DE8F8H 的单元在 Cache 中的什么位置。44 一台模型机共有 7 条指令，主频 25 MHz，各指令的使用频度与 CPI 如表 31所列，该机有 8 位和 16 位两种指令字长，采用 24 扩展操作码。8 位字长指令为寄存器一寄存器(RR)二地址类型，16 位字长指令为寄存器一存储器(RM) 二地址变址类型(地址码范围在-128127 之间)。(1)计算该机的 MIPS 速率；(2)计算操作码的平均码长；(3)设计该机的两种指令格式，标出各字段位数并给出操作码编码；
18、(4)该机允许使用多少个可编址的通用寄存器，多少个变址寄存器；(5)如何计算存储器有效地址。45 假设有 8 个记录 A、B，C、D、E、F、G、H 存放在磁盘里，每个磁道有 8 个扇区，正好可以存放 8 个记录。假设磁盘旋转速度为 20 msr，处理程序每读出一个记录后，用 2 ms 的时间进行处理，请问：(1)当记录 A、B 、C、D、E、F、G、H 按顺序放在磁道上时，顺序处理这 5 个记录花费的总时间是多少?(假设启动时的位置正好在 A 扇区的起点。)(2)如何采取优化方法，使处理这些记录所花费的总时间最短?求出该最短时间。46 在某个操作系统中，通过大量的实验，人们观察到在两次缺页中
19、断之间执行的指令数与分配给程序的页框数成正比，即可用内存加倍，缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要 100 ns，但若发生了缺页中断就需要 1 ms。一个程序运行了 60 s，期间发生了 1500 次缺页中断。如果该程序的可用内存增加到原来的 2 倍，那么，请计算，此时这个程序运行需要多少时间?47 下面是给出的一段 IP 数据包头所包含的数据， 45 00 00 30 52 52 40 00 80 06 2C 23CO A8 01 01 D8 03 E2 15，请根据 IPv4 头部格式回答如下问题： (1) 该 IP 包的发送主机和接收主机的地址分别是什么
20、? (2) 该 IP 包的总长度是多少?头部长度是多少?(3)该 IP 分组有分片吗? 如果有分片它的分片偏移量是多少? (4)该 IP 包是由什么传输层协议发出的? 注：IP 分组头结构分别如图 33 所示。计算机专业（基础综合）模拟试卷 56 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 B【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点要知道终端结点的前驱结点的地址，所以，带有尾指针的单循环链表不合适，而循环双链表
21、满足条件。2 【正确答案】 C【试题解析】 顺序表的删除运算的时间主要消耗在了移动表中元素上，删除第 i个元素时，其后面的元素 ai+1a n 都要向上移动一个位置，共移动了 n-i 个元素。在等概率情况下， 即 pi=1n，则：这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为 O(n)。3 【正确答案】 D【试题解析】 这类问题一般都先分析题目中的数据是具有“先进后出”还是“先进先出”特性，再判断其逻辑结构为栈或者队列。4 【正确答案】 D【试题解析】 链队列中删除元素一般仅修改队头指针，但只有一个元素时，出队后队空，此时还要修改队尾指针。5 【正确答案】 C【
22、试题解析】 设 Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，有 N 0=0 N1=1 N2=2 Nh=Nh-1+Nh-2+1 Nh=4，N 4=7，N 5=12，N 6=2015。也就是说，高度为 6 的平衡二叉树的最少有 20 个结点，因此 1 5 个结点的平衡二叉树的高度为5，而最小叶子结点的层数为 3，所以选项 D 错误。而 A 和 B 的查找过程不能构成二叉排序树，因而 A、B 错误。6 【正确答案】 D【试题解析】 由二叉树性质的推广，度为 4 的树应该有 1+n2+2n3+3n4 个叶结点(n i表示度为 i 的结点数目)，与度为 1 的结点的个数无关。 因此，如果用 n
23、0 表示叶结点的个数，则应该有 n0=1+2+21+31=8。7 【正确答案】 C【试题解析】 边(v6，v3)与边(v3，v3) 是同一条边。原第 i 行第 j 列元素在矩阵B(上三角形式)中的下标为：(n-1)+(n-2)+(n-(i-1)+(j-i)。本题中将数值代入，(10-1)+(10-2)+(6-3)-20。所以边(v6，v3)的信息存储在 B20中。8 【正确答案】 D【试题解析】 说法工是错误的，在一个有向图的拓扑序列中，若顶点 a 在顶点 b之前，只能说明顶点 a 到顶点 b 有一条路径。 说法是错误的，AOE 网中可能有不止一条关键路径，它们的路径长度相同。 说法是正确的。
24、任意 n 个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为 v0，v 1，v n-1，证明此时的邻接矩阵 A 为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标 i 和 j(ij) ，使得 Aij不等于 0，即图中存在从 vi 到 vi 的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v i 的位置一定在 vj 之前，而上述拓扑序列 v0，v 1，v n-1 中，由于 ij ，即 vi 的位置在 vj 之后，导致矛盾。因此说法是正确的。9 【正确答案】 B【试题解析】 选项 B 错误，因为连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中
25、顶点的所有边都加上，所以，连通分量中可能存在回路。10 【正确答案】 A【试题解析】 本题主要考查各种排序方法的性能分析。11 【正确答案】 C【试题解析】 对 n 个记录进行简单选择排序，所需进行的关键字间的比较次数为移动记录的次数，最小值为 0，最大值为 3(n-1)。所以简单选择排序的最好和平均时间复杂度均为 O(n2)。12 【正确答案】 B【试题解析】 现代计算机系统是一个硬件与软件组成的综合体，可以把它看成是按功能划分的多级层次结构。13 【正确答案】 A【试题解析】 这是一个负数，x-8，意味着 0x-8。x=-8 的补码表示为11000，应将-8 排除在外。14 【正确答案】
26、C【试题解析】 浮点数 26110101 的尾数不是规格化数，需要进行左规。15 【正确答案】 B【试题解析】 汉字国标码一汉字机内码-080H=B4BAH-8080 H=343AH，汉字区位码=汉字国标码-2020H=141AH，前两数 14 H 转换为十进制数为 20，对应区号，后两数 1AH 转换为十进制数位 26，对应位号。16 【正确答案】 D【试题解析】 小端方案是将最低有效字节存储在最小地址位置。在数 01234567H中，最低有效字节为 67H。17 【正确答案】 B【试题解析】 符号标志位 SF=0，表示为正数，符号标志位 SF=1，表示为负数。18 【正确答案】 C【试题解
27、析】 由于微命令控制字段必须是一个整数，所以在最短编码法中为log2N位。Llog 2N19 【正确答案】 D【试题解析】 计算机关机状态时，计算机中指令和数据存放在外存中，但是CPU 不能直接和外存交互信息，因此启动后的指令和数据被装入内存。20 【正确答案】 C【试题解析】 磁盘的转速为 7 200rmin=120r s，转一圈经过 160 个扇区，每个扇区有 512B 所以数据传输率为 12016051 21024=9 600KB s。21 【正确答案】 C【试题解析】 因为块的大小 16 字节，所以块内地址字段为 4 位；又因为 Cache容量为 128KB，八路组相联，所以可以分为
28、1 024 组，128KB(168)=1 024，对应的组号字段 10 位；剩下为标记字段。1234567 H=0001001000110100010101100111，标记字段为其中高 14 位，00010010001101=048DH22 【正确答案】 A【试题解析】 程序中断的实质是程序切换，由现行程序切换到中断服务程序，再由中断服务程序返回到现行程序。所以中断只是暂停正在运行的程序，而不会暂停CPU 的运行，也不会暂停对内存的访问。23 【正确答案】 B【试题解析】 中断处理程序是操作系统所提供的系统程序。键盘中断也不例外，当用户程序发起键盘中断时，需要保护现场，陷入内核，调用操作系统
29、的代码去完成键盘输入码的读取，并将结果在中断返回时带回到用户程序中去。现代操作系统不允许用户直接对硬件设备进行操作(早期汇编程序除外)，用户需要使用，必须采用系统调用或陷入的方式。硬件固化的代码程序可能有用户代码，也可能有系统代码，所以不正确。24 【正确答案】 C【试题解析】 本题考查进程调度的时机和进程调度的策略。进程调度的时机与进程特点有关，例如进程是 CPU 繁忙型还是 IO 繁忙型，自身的优先级等。但是仅有这些特点是不够的，能否得到调度还取决于进程调度策略，若采用优先级调度算法，则进程的优先级才起作用。至于占用处理机运行时间的长短，则要看进程自身，若进程是 IO 繁忙型，运行过程中要
30、频繁访问 IO，也就是说，可能会频繁主动放弃 CPU，所以，占用 CPU 的时间就不会长，一旦放弃 CPU，则必须等待下次调度。若进程是 CPU 繁忙型，则一旦占有 CPU 就可能会运行很长时间，但是，运行时间还取决于进程调度策略，大部分情况下，交互式系统为改善用户的响应时间，大多采用时间片轮转的算法，这种算法在进程长期占用 CPU 到一定时间后，会强制将其换下，以保证其他进程的 CPU 使用权。所以，本题的正确答案应为选项 C，其他都不是。25 【正确答案】 B【试题解析】 死锁发生的四个必要条件是互斥、部分分配、非剥夺和循环等待。死锁预防就是打破死锁的这四个条件，建立 SPOOLing 系
31、统可以部分解决互斥条件，一次分配所有资源是打破部分分配条件，按序分配资源是打破循环等待条件，而银行家算法是死锁避免的算法，不是死锁预防的算法。26 【正确答案】 B【试题解析】 本题考查进程调度的层次问题。在操作系统中存在着三级调度，作业调度是决定外存上的作业何时可以创建到内存成为进程；成为进程以后位于就绪队列，等待处理机调度，一旦被调度就占用处理机运行；若并发进程较多，将有些不具备运行条件的进程挂起，将其调出到外存，空出内存给更需要的进程使用，调节负载均衡。这三级调度方式中，作业调度和进程调度比较类似，内外存交换调度因为与存储有关，所以算法上与前两种差异较大。作业调度有先来先服务、短作业优先
32、、高优先级优先、高响应比优先等调度算法，进程调度有先来先服务、时间片轮转、高优先级优先、多级反馈队列等调度算法；在采用虚拟页式存储管理的系统中，内外存调度被请求页式的分配方式所替代。27 【正确答案】 D【试题解析】 本题考查多级存储层次下的平均访问时间。多级存储是现代计算机为了获得比较优异的存储器访问性能又比较廉价的一种实现方法。正确的计算需要搞清楚 CPU 访问一个字的流程。通常，若需要执行的指令字已经载入到 cache 中，那么，仅需要从 cache 中取出放到指令队列上即可，所花费的时间即是 cache 的访问时间。当 cache 中缺席时，产生中断，调用 cache 更新程序，将所需
33、的指令字载入 cache，然后返回到中断点继续定位，所需的时间是访问 cache 的时间和中断服务程序所花费的时间之和。同理，可以推断出访问不在主存中的指令字所需花费的时间是磁盘装入时间与内存中断服务程序时间以及 cache 访问时间的和。根据各自命中率的不同，可以计算出总时间为：1009+(10+110)(1-09)0 75+(10+100+10 000 000)(1-09)(1-075)=250 020 ns28 【正确答案】 D【试题解析】 本题考查虚拟存储系统中程序调入内存的时刻。在一个采用请求式调页的虚拟存储系统中，当一个程序需要执行时，首先由进程创建模块为新进程找到一张空白的进程表
34、，将该进程的基本信息填入这张表，例如进程号、父进程、进程组、优先级、状态字等，然后分配该进程虚拟内存空间(此时不做任何实际的分配)，打开文件获得句柄，链接到用户活动文件数据表中，分配设备等。做完这些工作，进程表将被放入就绪队列(假设所有资源均可用，只等 CPU 调度)，等待操作系统的调度模块调度。调度模块按照规定的调度算法，从就绪队列中选择一个进程(对于单核处理机) ，将运行状态赋予该进程，然后切换 CPU，使得 CPU 的程序计数器指向该进程起首执行处，开始运行。通常，新创建的进程是仅有虚拟地址空间的，所以，当第一次执行该进程时，代码不在物理内存，于是产生一次缺页中断。缺页中断机构把对应的页
35、面从外存调入内存，返回到中断点继续运行。对于请求式调页，每次产生缺页中断一般仅调入相关的一页，若运行过程中所需的页面不在内存，那么随时可以产生缺页中断，调入内存。若在进程运行过程中，所需的页面已经在内存了，那么就不需要再将代码调入内存。因此，真正将程序代码和数据调入内存的是缺页中断处理过程，其他过程不会对内外存的活动进行操作。29 【正确答案】 C【试题解析】 本题考查考生对文件保护中访问控制权限的理解。操作系统在对文件的保护中，可以采取用户口令认证、域保护和访问控制列表及访问控制权限表等方式。将访问矩阵按列进行划分，每一列建立一个控制表，即可得到各个对象的访问控制表。将矩阵按行进行划分，每一
36、行建立一个访问权限表，即可得到各个域的访问权限表，域在不同操作系统中可以按不同方式出现，例如可以是进程，也可以是用户等。当某个进程或用户需要访问某个文件时，先检查对象的访问控制表，检查是否有访问权限。若有，则为其建立访问权限表，并链接到该进程或用户，以后，该进程或用户可以直接利用该用户权限表进行访问。本题中，Li 可以读写的文件有三个 File0、1 和 2；Zhang 可以访问的文件有两个 File0 和 4，但是其中 File4 只能运行不能读写；Sun 可以读写的文件为 File2 和 3；Wang 可以读写文件 File4，但是 Wang 不是 staff 组员，所以不能读写 File
37、2。因此，满足条件的答案只有 C。30 【正确答案】 A【试题解析】 本题考查磁盘结构和磁盘读写的概念。磁盘是旋转盘式存储设备，每个盘面划分有若干存储信息的同心圆称为磁道，每个磁道又划分成多个扇区。本题中，将每道的所有扇区组成一个簇，意味着可以将一个磁道的所有存储空间组织成一个数据块组，这样有利于提高存储速度。读写磁盘时，磁头首先要找到磁道，称为寻道，然后才可以将信息从磁道里读出来或写进去。读写完一个磁道以后磁头会继续寻找下一个磁道，完成剩余的工作，所以，在随机寻道的情况下，读写一个磁道的时间要包含寻道时间和读写磁道时间，即 T+r 秒。由于总的数据量是 b 字节，它要占用的磁道数为 bN 个
38、，所以总的平均读写时间为 bN*(T+r)秒。如果不采用随机寻道，而是采用连续读写的方式，那么磁盘的存储方式是这样的，首先也是寻道，找到一组连续的磁道(用于连续读或写，写入的话磁道总容量必定大于要写入的信息总数)，花费时间 T 秒，然后再花费 r 秒将 N 个字节的信息写入(或读出)，然后磁头移动到下一道(此时，这个磁道与上一个磁道是紧紧挨着的，几乎可以不花费时间)，继续写入(或读出)N 字节，循环往复，直到全部信息写入(或读出)完成。这样的话，总时间可以缩短为 bN*r+T。因为其不需要每次都去寻道，只需一次寻道即可。所以，考生要注意题目的条件，找出符合题意的正确答案。31 【正确答案】 B
39、【试题解析】 本题考查对文件控制块(FCB)的理解。文件控制块是控制一个文件读写和管理文件的基本数据结构，当进程需要使用某个文件时，就会调用 open()来打开文件，该调用将文件的文件控制块从外存调入内存，存放在进程表中的用户活动文件表中，并在系统活动文件表中记录该文件的打开次数，若是共享文件，还需要将其链接的用户数加一。由于在进程表中存放有该文件的控制块，用户进程才能在调用 read()时找到该文件的位置并对文件的内容进行存取。而文件系统的信息，例如文件系统的控制信息，文件系统的文件分配表等是在挂载一个文件系统时就读入内存的，挂载文件系统可以是一个磁盘分区，也可以是一个文件目录。32 【正确
40、答案】 A【试题解析】 本题考查 UNIX 设备的读写概念。对于块设备，UNIX 操作系统为保证设备读写的性能，除了提供一般的读写操作以外，还提供了提前读取和延迟写入的特殊方式。在一个进程顺利读取块设备的数据后，系统会预见到下一步可能读取的数据，并将其放入内存缓冲区，称为预先读取，它缩短了读取数据的时间，可以改善系统的性能。同理，延迟写入并不真正将数据写入块设备，而是放在缓冲区内，当需要再次读取时，可以不必从块设备读取，缩短了读取时间，只有当缓冲区满了，才将整个缓冲区数据写入块设备，减少了设备启动的次数，改善了性能。33 【正确答案】 C【试题解析】 本题考查 OSI 模型中各个层次功能，完成
41、路径选择，也就是路由功能的是网络层，答案是 C。34 【正确答案】 B【试题解析】 本题考查奈奎斯特定理的应用，这里载波有四种相位变化和两种振幅变化，也就是离散值为 8，注意这里所提供的波特，由公式可得到 6001og28=1 800 bps，因此答案是 B。35 【正确答案】 B【试题解析】 本题考查后退 N 帧协议的原理。数据链路层的停止一等待协议、后退 N 帧协议、选择重传协议，以及 TCP 协议对发送窗口和接收窗口的要求，是理解协议工作原理精髓所在。后退 N 帧协议的最大发送窗口为 2n-1(其中 n 为帧号的位数)，题目中已经说明发送窗口的大小为 30，也就是说如果要使得协议不出错，
42、必须满足 302n-1，所以 n 至少要等于 5，因此答案是 B。36 【正确答案】 D【试题解析】 考查 CSMACD 的退避算法，这里的时间片就是基本退避时间，确定基本退避时间，一般是取为争用期 2。定义重传次数 k，k10，即 k=Min重传次数，10 从整数集合0，1，(2 k-1)中随机地取出一个数，记为 r。重传所需的时延就是 r 倍的基本退避时间。当重传达 16 次仍不能成功时即丢弃该帧，并向高层报告。本题中重传次数的最大值为 10，退避时间最大就是 210-1=1023 个时间片，因此答案是 D。37 【正确答案】 C【试题解析】 本题考查 CSMACA 协议的工作原理，IEE
43、E 80211 标准定义了两种操作模式，第一种模式是 DCF(分布式协调功能 )，该模式没有中心控制设备，所有站点都在竞争信道；另一种模式是 PCF(点协调功能 )，该模式有基站，作为中心控制设备通过轮询机制控制决定各个站点的传输顺序。根据 IEEE 80211 标准，DCF 是必须的而 PCF 是可选的。CSMACA 协议应用于 DCF 下，目的在于解决在允许竞争的情况下信道如何分配的问题。它支持的操作方式有两种：第一种操作方式采用延时算法进行访问控制。当一个要发送数据的站点检测到信道空闲时，站点需继续监听与IFS(interframe space，帧间间隔 )相等的一段时间，若此时信道依然
44、空闲，站点就可以发送帧；如果检测到信道正忙，则发送站点推迟到信道空闲时再发送数据。若冲突发生，则发生冲突的站点按照截断二进制指数退避算法延迟一段时间后，再试着重新发送数据。另一种操作方式类似于发收双方的握手过程。它是基于MACAW(Multiple Access with Collision Avoidance for Wireless，带冲突避免的无线多路访问)，采用虚拟信道监听的方法。CSMACA 协议利用 IFS 机制让 PCF和 DCF 共存在同一个通信单元内。因此答案是 C。38 【正确答案】 C【试题解析】 本题考查交换机的三种交换方式，直接交换在输入端口检测到数据帧时，检查帧头地
45、址，把数据帧直通到相应的端口，实现交换功能。存储转发交换把输入端口的数据帧先存储起来，然后进行 CRC(循环冗余码校验)检查，在对错误包处理后才取出数据帧的目的地址，通过查找表转换成输出端口送出帧。碎片隔离交换检查数据包的长度是否够 64 个字节，如果小于 64 字节，说明是假包，则丢弃该包；如果大于 64 字节，则发送该包。因此答案是 C。39 【正确答案】 A【试题解析】 本题考查 TCP 协议的连接管理中断开连接过程，主机甲的应用进程先向其 TCP 发出连接释放请求，并且不再发送数据。TCP 通知对方要释放从甲到乙这个方向的连接，将发往主机乙的 TCP 报文段首部的终止比特 FIN 置
46、1，其序号 x 等于前面已传过的数据的最后一个字节的序号加 1。主机乙的 TCP 收到释放连接通知后即发出确认，确认比特 ACK 置 1，其序号为 y，确认号为 x+1，同时通知高层应用进程，这样，从甲到乙的连接就释放了，连接处于半关闭(half-close)状态，相当于主机甲向主机乙说： “我已经没有数据要发送了。但你如果还发送数据，我仍接收。”因此本题中主机乙返回的 TCP 段应该是SYN=0，ACK=1 ，seq 是随机选择的序号，ack 必须是主机甲的序号加 1，也就是11221，答案是 A。40 【正确答案】 D【试题解析】 本题考查协议的下一层服务类型，FTP，POP3，SMTP
47、都是基于TCP 协议，而 TCP 协议是面向连接的。DHCP 建立在 BOOTP 的基础上，它扩展了 BOOTP 的功能，向主机投递配置信息，它根据主机所提出的具体请求可以提供 IP 地址和子网掩码等信息，并使用 BOOTP 众所周知的 UDP 端口 67 号作为服务器端口，是基于 UDP 协议，而 UDP 协议是面向无连接的，因此答案是 D。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 (1)有向图 G 的邻接矩阵 (2)顶点 a到其他各顶点间的最短路径的求解过程如表 33 所列。42 【正确答案】 用 C 语言算法描述如下：voild Adjust(int A) 调整数
48、组 A，使得 A 的左边为负整数，右边为正整数int i=1， j=n，temp；while(i j)(while(Ai0&ij)i+； Ai为负整数时，i 增 1while(Aj0&ij)j-； Aj为正整数时，j 减 1if(ij)Letup：Ai ；Ai：Aj；Aj ：temp；Ai为正整数、Aj为负整数时，交换i+：j-；(3)算法的时间复杂度为 O(n)；算法的空间复杂度为 O(1)。43 【正确答案】 (1)Cache 地址 14 位，其中 Cache 块号 9 位，块内地址 5 位。 (2)主存地址 20 位，包括主存块号(标记字段 6 位+块号 9 位)和块内地址 5 位。 (3)Cache 的块号为 9 位，所以块表的单元数为 29；块表中存放的是块标记，由于块标记为 6 位，所以块表的字长为 6 位。故块表的容量为 29 字6 位。 (4)Cache 有16102432=51 2 个块。因为主存地址 DE8F8=1101 1110 1000 11111000，主存地址中前 6 位是块标记，标记字段的值是 110111，中间 9 位为块号=101000111，最后 5 位为块内地址=11000。在直接映像方式下，Cache 地址即为块号+块内地址=10100011111000，所以主存地址 DE8F8H
