1、计算机专业（基础综合）模拟试卷 72 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在具有 n 个结点的顺序表，算法的时间复杂度是 D(1)的操作是( )。（A）访问某个结点（B）插入一个新结点（C）删除一个已经存在的结点（D）将顺序表从大到小排序2 若线性表最常用的运算是查找第 i 个元素及其前驱的值，则下列存储方式最节省时间的是( )。（A）单链表（B）双链表（C）单循环链表（D）顺序表3 已知循环队列存储在一维数组 A0，n 一 1中，且队列非空时 front 和 rear分别指向对头和队尾。若初始时
2、队列为空，且要求第一个进入队列的元素存储在aO处，则初始时 front 和 reaR 的值分别为( )。（A）O，0（B） 0，n-1（C） n-1，0（D）n-1 ，n-14 某二叉树的高度为 50，树中只有度为 O 和度为 2 的结点，那么此二叉树中所包含的结点数最少为( ) 。（A）88（B） 90（C） 99（D）1005 在线索化二叉树中，t 所指结点没有左子树的充要条件是 ( )。（A）t-left=NULL（B） t-ltag=1（C） t-ltag=1 且 t 一left=NULL（D）以上都不对6 在含有 15 个结点的平衡二叉树上，查找关键字为 28(存在该结点)的结点，则
3、依次比较的关键字有可能是( )。（A）30，36（B） 38，48，28（C） 48，18，38，28（D）60，30，50，40，38，367 以下关于图的说法正确的是( )。I一个有向图的邻接表和逆邻接表中的结点个数一定相等用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的（A）I，（B） ，（C） I，（D）仅有8 存在一个由 8 个结点组成的图，结点从 07 编号，图中有 13 条有向边，分别是：0-7 0-1 1-4 1-6 2-3 3-4 4-2 5-2 6-0 6-3 6-5 7-17-3，下面
4、选项中哪个是该图的强连通分量( )。（A）0-1-4（B） 3-5-6（C） 0-1-6-7（D）1-4-39 有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找失败时所需的平均比较次数是( )。（A）3712（B） 6213（C） 3912（D）491310 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序，这种排序算法称作( )。（A）直接插入排序（B）基数排序（C）快速排序（D）归并排序11 数据序列 F=2，1，4 ，9，8，10，6，20只能是下
5、列排序算法中( )的两趟排序后的结果。（A）快速排序（B）冒泡排序（C）选择排序（D）插入排序12 在计算机的不同发展阶段，操作系统最先出现在( )。（A）第一代计算机（B）第二代计算机（C）第三代计算机（D）第四代计算机13 浮点加减运算结果满足( )时，应作“ 机器零”处理。（A）尾数为“ 全 0”（B）阶码上溢（C）阶码下溢（D）A 或者 C14 补码定点小数除法中，被除数和除数应满足( )。（A）O被除数除数（B） O被除数除数（C） 0除数被除数（D）0被除数除数15 已知 Cache 命中率 H=098，主存比 Cache 慢 4 倍，已知主存储取周期为200ns，平均访问时间是(
6、 )。（A）125 ns（B） 75 ns（C） 55 ns（D）53 ns16 某 8 位机的地址码为 16 位，主存按字节编址，该机所允许的最大主存空间是( )。（A）1 6 KB（B） 24 KB（C） 48 KB（D）64 KB17 下面的寻址方式中，指令中包含操作数的地址的是( )。（A）直接寻址（B）立即寻址（C）寄存器寻址（D）间接寻址18 在基址寻址方式中，若基址寄存器 BR 的内容为 2D3 CH，形式地址 A 的内容为 53 H，则有效地址 EA 为( )。（A）53H（B） 2D3CH（C） 2D8FH（D）803CH19 中央处理器中不包括( )。（A）指令寄存器 （B
7、）指令译码器（C）数据寄存器（D）地址寄存器20 某指令流水线由 5 段组成，第 1、3、5 段所需时间为 ，第 2、4 段所需时间分别为 3，如下图所示，那么连续输入 n 条指令时的吞吐率(单位时间内执行的指令个数)TP 是。21 某机采用计数器定时查询方式来进行总线判优控制，共有 4 个主设备竞争总线使用权，当计数器初值恒为 102(二进制)时，4 个主设备的优先级顺序为( )。（A）设备 0设备 1设备 2设备 3（B）设备 2设备 1设备 0设备 3（C）设备 2设备 3设备 0设备 1（D）设备 2=设备 3=设备 0=设备 122 CPU 在响应中断的过程中，保护现场的工作由( )
8、完成。（A）中断隐指令（B）中断服务程序（C） A 或 B（D）A 和 B 共同 23 操作系统提供给用户的接口方式包括( )。（A）命令方式和函数方式（B）命令方式和系统调用方式（C）命令方式和文件管理方式（D）设备管理方式和系统调用方式24 下面选项中，不能实现进程之间通信的是( )。（A）数据库（B）共享内存（C）消息传递机制（D）管道25 为了实现进程之间的同步和互斥，我们使用 PV 操作，从本质上讲 PV 操作是( )。（A）机器指令（B）系统调用命令（C）作业控制命令（D）低级进程通信原语26 避免死锁是指在资源的动态分配过程中，防止系统进入( )状态。（A）死锁（B）安全（C）不
9、安全（D）循环27 操作系统对内存的管理方式中，( )不会产生内部碎片。（A）分页式存储管理（B）分段式存储管理（C）同定分区式存储管理（D）段页式存储管理28 某个页式存储管理系统，接收了一个大小一共 7 页的程序，其依次访问的页为：1，2，3，4，2，1，5，6，2，1，2，3，7。若分配给该程序的内存空间为 4 页，并一次预装入。用 LRU 调度算法，首先淘汰的页面是( )。（A）1（B） 2（C） 3（D）429 位示图可用于磁盘空间的管理。设某系统磁盘共有 500 块，块号从 0 到 499；第 0 字的第 0 位表示第 0 块，第 0 字的第 1 位表示第 1 块，依次类推。若用位
10、示图法管理这 500 块的磁盘空间，当字长为 32 位时，第 i 个第 j 位对应的块号是( )。（A）32i+j（B） 32i+j-1（C） 32i+j-32（D）32i+j-32-130 某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有 10项，其中前 8 项是直接索引项，第 9 项是一次间接索引项，第 10 项是二次间接索引项。假定物理块的大小是 1K，每个索引项占用 4 个字节，则该文件系统中最大的文件可以达到( ) 。（A）65 536 K（B） 32 768 K（C） 65 793 K（D）34 000 K31 设备管理中，设备映射表(DMT)的作用是( ) 。（
11、A）管理物理设备（B）管理逻辑设备（C）实现输入输出（D）建立逻辑设备与物理设备的对应关系32 在一个磁盘上，有 1 000 个柱面，编号从 0999，假设最后服务的请求是在磁道 345 上，并且读写头正在朝磁道 0 移动。按 FIFO 顺序排列的队列中包含了如下磁道上的请求：123、874、692、475、105、376。利用 SCAN 调度算法满足系统请求，那么磁盘臂必须移过的磁道的数目为( )。（A）1298（B） 2013（C） 1219（D）196733 ( )是一个事实的网络工业标准。（A）TCP IP（B） OSIISO（C） IEEE80211（D）以上均不正确34 RS232
12、-C 接口规范所处的层次是 ( )。（A）物理层（B）数据链路层（C）网络层（D）传输层35 若数据链路的发送窗口尺寸 WT=4，在发送 3 号帧、并接到 2 号帧的确认帧后，发送方还可连续发送的帧数是( )。（A）2 帧（B） 3 帧（C） 4 帧（D）1 帧36 一个大型跨国公司的管理者从网络管理中心获得一个 A 类 IP 地121OO0，需要划分 1000 个子网，选择子网号的位长为( )。（A）11（B） 10（C） 12（D）1337 一台主机的 IP 地址为 1111100，子网掩码为 255000。现在用户需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下
13、4个 IP 地址和子网掩码：IIP 地址：11111，子网掩码：2550 00IP 地址：11121，子网掩码：2550 00IP 地址：12111，子网掩码：2550 00IP 地址：13121，子网掩码：2550 00那么 IP 地址和子网屏蔽码可能是该主机的默认路由的是 ( )。（A）I 和（B） I 和 I II（C） I和（D）和38 TCP 是采用 ( )来控制流量的。（A）设定拥塞窗I（B） TCP 首部中的接收窗口（C）设定拥塞阀值（D）通过标志位来通知39 在 TCP IP 模型中，主机采用 ( )标识，运行在主机上的应用程序采用 ( )标识。（A）端口号，主机地划 L（B）
14、主机地址，IP 地址（C） IP 地址，主机地址（D）IP 地址，端口号40 一个 FTP 的用户，发送了 LST 命令来获取服务器的文件列表，这时候服务器应该通过( )端口来传输该列表。（A）21（B） 20（C） 22（D）19二、综合应用题41-47 小题，共 70 分。41 下图为一棵 AVL 树( 关键码按字典顺序排列 )：请画出插入关键码 won后的 AVL 树。42 单链表 L 是一个带有头结点的有序链表，设计一个算法判断 L 是否为按数值递减的链表。如果 L 是递减链表，那么就返回 1，否则返回 0。请回答下列问题：(1)给出算法的主要思想；(2)写出算法的实现函数；(3)总结
15、所用算法的时间和空间复杂度。43 一个由高速缓冲存储器 Cache 与主存储器组成的二级存储系统。已知主存容量为 1 MB，按字节编址，缓存容量为 32 KB，采用组相连方式进行地址映射与变换，主存与缓存的每一块为 64 B，缓存共分 8 组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)。(2)假定 Cache 的存取周期为 20s，命中率为 O 95，希望采用 Cache 后的加速比大于 10。那么主存储器的存取速度应大于多少?(访存时 CPU 同时访问 Cache 和主存，如Cache 命中则中断主存访问)44 某一计算机系统采用“主存Cache” 存储层次结构，主存容量有 8
16、个块，Cache容量有 4 个块，采用直接地址映像。(1)如果主存块地址流为 0，1，2，5，4，6，4，7，1，2，4，1，3，7，2，主存内容一开始未装入 Cache 中，列出每次访问后 Cache 中各块的分配情况；(2)指出块命中的时刻； (3)求出此期间 Cache 的命中率。45 假定在一个处理机上执行的操作如下：这些作业假定按A，B，C ，D，E 次序先后几乎同时(时间差相对时间片大小忽略不计 )到达。 (1)给定相应的图示来说明分别用 FCFS，RR( 时间片=1)，sJF 和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情况； (2)分别给出采用上述调度算法时每个
17、作业的周转时间和平均周转时间。46 某车站售票厅，任何时间最多可容纳 100 名购票者进入，当售票厅中少于 100名购票者时，厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用 PV 操作管理这些并发进程时，应怎样定义信号量?写出信号量的初值以及信号量各种取值的含义。(2)根据所定义的信号量，把应执行的：PV 操作填入下列进程中，以保证进程能够正确地并发执行。Cobegin process pi(i=1，2，n)Begin_进入售票厅；购票；退出；endCoend(3)若欲购票者最多为 n 个人，写出信号量可能的变化范围(最大值和最小值)。47 已知
18、某局域网采用 CSMACD 协议实现介质访问控制，数据传输速率为 100 Mbps。(1)此局域网采用了以太网，为了达到 100 Mbps 的数据传送率，那么线路的带宽最小为多少?(2)如果信号在网络中的传播速度是 200 000 kms，那么该网络的最大长度应该为多少?(3)在(2)的基础上，此局域网内有两台主机 A 和 B，二者相距 2 km，若主机 A 和主机 B 发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经多长时间?最长需经过多长时间?( 假设主机甲和主机乙发送数据过程中，其他主机不发送数据)计算机专业（基础综合）模拟试卷 72 答案与解析一、单项
19、选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A【试题解析】 顺序表是随机存取结构，因此时间复杂度为 O(1)；选项 B 和 C 插入和删除都需要移动元素，时间复杂度为 O(n)；选项 D 是排序问题，时间复杂度是O(n)O(n 2)2 【正确答案】 D【试题解析】 线性表中常用的操作是取第 i 个元素，所以应选择随机存取结构，即顺序表，同时在顺序表中查找第 i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取，查找第 i 个元素的前驱也不方便，双链表虽然能快速查找第i 个元素的前驱，但不能实现随机存取
20、。3 【正确答案】 B【试题解析】 在队列中插入元素时，只能在队尾进行操作。rear 指针指向队尾元素，因此插入时，要先将 rear 指针向后移动一个，然后再将元素插入数组中。如果要使得第一个进入队列的元素存储在 A0处，rear 指针初始值应该为 n-1。而插入第一个元素之后，front 指针不变，队尾指针要指向队尾元素。因此，rear 指针初始值应该为 n-1，front 指针为 0。4 【正确答案】 C【试题解析】 除根结点层只有 1 个结点外，其他各层均有两个结点，结点总数=2(50-1)+l=99。5 【正确答案】 B【试题解析】 线索二叉树中某结点是否有左孩子，不能通过左指针域是否
21、为空来判断，而要判断左标志是否为 1。6 【正确答案】 C【试题解析】 设 ni 表示深度为 h 的平衡二叉树中含有的最少结点数，有n0=0，n 1=1，n 2=2； 计算的公式为： nh=nh-1+nh-2+1； n 3=n2+n1+1=4； n4=n3+n2+1=7； n 5=n4+n3+1=12； n 6=n5+n4+1=2015。 也就是说，高度为 6 的平衡二叉树的最少有 20 个结点，因此 15 个结点的平衡二叉树的高度为 5，而最小叶子结点的层数为 3，所以选项 D 错误。如下图所示：A 在查找 30 后，指针应该指向左孩子，而不是右孩子；B 与 A 存在同样的问题，因而 A、B
22、 错误。而 C 选项的查找路径，如下图所示：7 【正确答案】 A【试题解析】 说法 I 是正确的，邻接表和逆邻接表的区别仪在于出边和入边，边表的结点个数都等于有向图中的边的个数。 说法是正确的，邻接矩阵的空间复杂度为 D(n2)，与边的个数无关。 说法是错误的，有向图的邻接矩阵不一定是不对称的，例如，有向完全图的邻接矩阵就是对称的。8 【正确答案】 C【试题解析】 先画出图，即可得出答案。9 【正确答案】 B【试题解析】 长度为 12 的折半查找判定树中有 13 个外结点，如下图所示：对于长度为 12 的有序表，折半查找失败时的平均查找长度为：ASL=(43+510)13=621310 【正确
23、答案】 C【试题解析】 题干中描述的是快速排序的过程。11 【正确答案】 A【试题解析】 对于后三种排序方法，两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列不满足。12 【正确答案】 C【试题解析】 根据计算机发展的历史划分，在硬件方面，第三代计算机的逻辑元件与存储器均由集成电路实现；在软件方面，操作系统日益成熟。故选择选项 C。13 【正确答案】 D【试题解析】 当尾数为“全 O”时，不论阶码为何值，该浮点数真值都为 O，应作“机器零”处理；当阶码下溢时，说明浮点数的真值小于该机可以表示的最小值，也应作“机器零”处理，故选 D。14 【正确答案】 B【试题解析】 n
24、位补码定点小数的表示范围是一 11 一 2-(n-1)，故被除数的绝对值应小于等于除数的绝对值，否则结果会溢出；此外应避免被除数为 0，因为此时结果一定为 0，这个除法没有意义，浪费了机器时间。15 【正确答案】 D【试题解析】 R=T mT c=4；T c=Tm4=50 ns；T a=TcE=T c43O98=501 06=53 ns。16 【正确答案】 D【试题解析】 内存空间为：2 168=64 KB。17 【正确答案】 A【试题解析】 若指令中包含着操作数的有效地址，则指令的寻址方式就是直接寻址。直接寻址时指令中地址码字段给出的地址 A 就是操作数的有效地址，即形式地址等于有效地址：E
25、A=A。由于这样给出的操作数地址是不能修改的，与程序本身所在的位置无关，所以又叫做绝对寻址方式。而间接寻址指令中给出的地址 A不是操作数的地址，而是存放操作数地址的主存单元的地址，简称操作数地址的地址：EA=(A)。18 【正确答案】 C【试题解析】 基址寻址方式下，EA=(BR)+A，结合题中条件，EA=(BR)+A=2D3C16+5316=2D8F16，选 C。19 【正确答案】 D【试题解析】 中央处理器主要由控制器和运算器两部分构成。控制器由程序计数器 PC、指令寄存器 IR、指令译码器、时序产生器、操作控制器组成；运算器由算术逻辑单元 ALU、累加寄存器 AC、数据缓冲寄存器 DR、
26、状态条件寄存器 PSW组成。20 【正确答案】 B【试题解析】 流水线的实际吞吐率均小于最大吞吐率。本题中还存在着瓶颈段，吞吐率将受到瓶颈段的影响。 吞吐率 TP 指的是流水线机器在单位时间里能流出的任务数或结果数。如果流水线各段的经过时间相同，流水线的最大吞吐率。如果流水线各段的经过时间不同时，流水线的最大吞吐率，此时受限于流水线最慢子过程经过的时间。流水线中经过时间最长的子过程瓶颈子过程。 存在瓶颈段的流水线的实际吞吐率为：21 【正确答案】 C【试题解析】 计数器初值为 102，故设备 2 的优先级最高，计数器值会递增，然后返回到 0，故优先级顺序为设备 2设备 3设备 0设备 1。22
27、 【正确答案】 D【试题解析】 保护现场包括保护程序断点和保护 CPU 内部各寄存器内容，其中，保护程序断点的任务由中断隐指令完成；而保护 CPU 内部其他寄存器的任务由中断服务程序来完成，故 D 为正确选项。23 【正确答案】 B【试题解析】 用户利用操作系统管理和使用计算机，操作系统的提供给用户的接口有命令接口、系统调用以及图形化界面等。24 【正确答案】 A【试题解析】 本题考查进程间的通信，进程间的通信主要有管道、命名管道、消息传递、共享内存、文件映射和套接字等。数据库不能用于进程间的通信。25 【正确答案】 D【试题解析】 从本质上讲，PV 操作是一种不能够被中断的低级进程通信原语。
28、26 【正确答案】 C【试题解析】 避免死锁是指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件，便可获得较高的资源利用率及系统吞吐率，但在实现上有一定的困难。27 【正确答案】 B【试题解析】 在内存的管理方式中，分段式存储管理方式中只能产生外零头，不会产生内零头即内部碎片。28 【正确答案】 C【试题解析】 本题根据 LRU 替换算法可知，应淘汰的为 3 号页面。29 【正确答案】 A【试题解析】 根据题目中的条件可知，一个字长为 32 位，可以表示 32 个块的状态。那么，我们可以归纳得出：第 0 块对应的是第 0 字的第
29、0 位，即 320+0；第 1 块对应的是第 0 字的第 1 位，即 320+1；第 31 块对应的是第 0 字的第 31 位，即 320+31；第 32 块对应的是第 1 字的第 0 位，即 321+0；第 33 块对应的是第 1 字的第 2 位，即 321+1；第 63 块对应的是第 0 字的第 31 位，即 321+31；那么第 i 字第 j 位对应的块号是 32i+j。30 【正确答案】 C【试题解析】 多级索引的逻辑并不复杂，二级间接索引表最多有 256 张，但是并没有用满。只用了 255 张，而且第 255 张中也没有全部用足 256 条表项。计算时一定要认真仔细，一般不会有太多变
30、化，但是对多级索引的方法一定要掌握。(1)直接索引为 81 K=8 K；一级间接索引为(1 K 4B)1 K=256 K；二级间接索引为(1 K4B)(1 K4B)1 K=64 M。(2)64 M 的文件需要 64 M1 K=64 K=65 536 个磁盘块，所以其占用直接索引 8块，一级间接索引 256 块，二级间接索引 65 272 块，还要加上一级间接索引表 1块，二级间接索引表 1 块+255 块，所以一共占有磁盘空间 65 793 块。31 【正确答案】 D【试题解析】 本题考查设备管理中，重要的数据结构的作用。既然是映射关系，必定有源和目标，能说明存在这关系的只有 D 选项。32
31、【正确答案】 C【试题解析】 SCAN：移动磁道的顺序为345、123、105、0、376、475、692、874。磁盘臂必须移过的磁道的数目为222+18+105+376+99+217+182=1219。33 【正确答案】 A【试题解析】 目前，众多的网络产品厂家都支持 TCPIP 协议，并被广泛用于因特网(Internet) 连接的所有计算机上，所以 TCPIP 已成为一个事实上的网络工业标准。34 【正确答案】 A【试题解析】 本题考食物理层接口特性。RS232 是物理层通信接口，其规范也处于物理层，答案是 A。35 【正确答案】 B【试题解析】 本题考查滑动窗口的机制。这里收到 2 号
32、帧的确认后，即，1，2 号帧已经正确接收，因此窗口向有移动 3 个帧，目前已经发送了 3 号帧，因此可连续发送的帧数是窗口大小一已经发送的帧数，即 41=3，因此答案是 B。36 【正确答案】 B【试题解析】 该公司需要有 1 000 个物理网络，加上主机号全 0 和全 1 的两种特殊地址，子网数量至少为 1002；选择子网号的位长为 10，可以用来分配的子网最多为 1 024，满足用户要求。37 【正确答案】 A【试题解析】 本题考查默认路由的配置，主机地址是一个标准的 A 类地址，其网络地址为 11000。选项 I 的网络地址为 11 000，选项的网络地址为11000，选项的网络地址为
33、1200O ，选项的网络地址为13000，因此和主机在同一个网络是选项 I 和，因此答案为 A。38 【正确答案】 B【试题解析】 TCP 首部中的接收窗口是用来标识接收方的缓冲能力的，避免快速的发送方淹没慢速的接收方。39 【正确答案】 D【试题解析】 在 TCPIP 模型中，IP 地址用来标识主机，使用 IP 地址来完成数据包的路由。而端门号则存在于传输层的央部中，用来标识主机上的不同进程。40 【正确答案】 B【试题解析】 FTP 中数据传输端口是 20，而文件的列表是通过数据连接来传输的。二、综合应用题41-47 小题，共 70 分。41 【正确答案】 在 AVL 树中进行插入运算的过
34、程： (1)在 AVL 树中插入一个新结点 x 时，若 AVL 树为空，则令新结点 x 为插入后 AVL 树的根结点。 否则，将结点 x 的关键字与根结点 T 的关键字进行比较： 若相等：不需要插入； 若xkeykey：结点 x 插入到 T 的左子树中； 若 xkeyT-key ：结点 x 插入到 T的右子树中。 (2)插入后，如果此 AVL 树仍为平衡二叉树，则不需要旋转。 如果插入后，破坏了 AVL 树的平衡性，则需要通过旋转将其转化为平衡二叉树。 插入关键码 won 后的 AVL 树，如图 1、图 2、图 3、图 4 所示：42 【正确答案】 (1)遍历链表 L，将前后两个结点的数值依次
35、作比较，判断链表是否为递减的，如果是就返回 1，不是就返回 0。(2)算法的实现过程如下：#include“stdioh”int increase(LinkList*L)int min； 记录链表中的最小值LinkList *P，*q；辅助指针P=L-next： if(P) min=P-data；因为链表带头结点q=P-next：while(q!=null)if(q-datamin)当前元素的值大于其相邻的前一个元素的值，则不为降序return 0；else min=q-data； 修改最小值q=q-next； 指针后移return 1：(3)遍历链表的时间复杂度为 O(n)，算法实现过程中使
36、用的辅助空间为常量，空间复杂度为 O(1)。43 【正确答案】 (1)主存按字节编址，块大小为 64 B=26B，故字块内地址 6 位；缓冲共分 8(=23)组，故组地址 3 位；Cache 地址格式如下表所示：主存容量为 1 MB，故主存地址为 20 位，主存地址格式中主存字块标记位数为 20-3-6=11 位，主存地址格式如下表所示： (2)设主存存取周期为 T，则 Cache 主存系统的平均存取时间 T1 为： T1=20s095+T(1-O 95) 根据题意，希望 Cache 的加速比大于 10，则应满足T10T 1，代入上式解得： T380s ，即要求主存储器的存取周期应大于 380
37、s。44 【正确答案】 (1)主存块地址流为0，1，2，5，4，6，4，7，1，2，4，1，3，7，2，主存内容一开始未装入 Cache中，每次访问后 Cache 中各块的分配情况如下： (2)命中时刻的时刻为装入第二个 4、第三个 4 以及第三个 1 和第三个 2 的时刻。 (3)命中率=415100=26 67。45 【正确答案】 (1)先来先服务 FCFSA 的周转时间是 10；B 的周转时间是 11；C 的周转时间是 13；D 的周转时间是 14；E 的周转时间是 19。因此，平均周转时间为(10+11+13+14+1 9)5=134 。 (2)时间片 RRA 的周转时间是 19；B的
38、周转时间是 2；C 的周转时间是 7；D 的周转时间是 4；E 的周转时间是 14。因此平均周转时间为(19+2+7+4+14)5=92。(3)短作业优先 SJFA 的周转时间是 19；B 的周转时间是 1；C 的周转时间是 4；D 的周转时间是 2；E 的周转时间是 9。因此平均周转时间为(19+1+4+2+9)5=7。(4)高优先级调度算法A 的周转时间是18；B 的周转时间是 1；C 的周转时间是 8；D 的周转时间是 1 9；E 的周转时间是6。因此平均周转时间为(18+1+8+19+6)5=104 。A 的周转时间是16；B 的周转时间是 l；C 的周转时间是 1 8；D 的周转时间
39、是 19；E 的周转时间是6。因此平均周转时间为(16+1+18+19+6)5=12。46 【正确答案】 (1)应定义一个信号量 S，S 的初值为 100，当 0S100 时，允许厅外的购票者进入；当 S=0 时，厅内已有 100 人，欲购票者暂不能进入；当 S0 时， S表示等待进入者的人数。(2)用 PV 操作管理时保证进程正确执行的程序如下：Cobegin process pi(i=1，2，3，n)beginp(s)；进入售票厅；购票：退出；v(s)；end；Coend：(3)若购票者最多为 n 人，则信号量 s 的变化范围：m ns1 000。47 【正确答案】 (1)以太网采用了曼彻
40、斯特编码，一个比特的数据需要两个信号来传输，那么为了达到 100 Mbps 的数据传送速率，需要线路达到 200 Mbps 的带宽。(2)以太网的最小帧长度是 64 字节，那么发送一个最小帧需要的时间： T1=648(bit)(10010 6)(bps) 设网络的最大长度为 L，那么信号沿网络传输一个来回的时间： T 2=2L(m)(20010 6)(ms) T 1 要大于或等于 T2，则可以得到 T2 的最大长度为 512 m。 (3)当 A，B 同时向对方发送数据时，两台主机均检测到冲突所需时间最短： 当一方发送的数据马上要到达另一方时，另一方开始发送数据，两台主机均检测到冲突所需时间最长：
