408-2013

        一、单项选择题（2分/题）

        1.已知两个长度分别为 m 和 n 的升序链表，若将他们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度为______。

        A.O(n)        B.O(mn)        C.O(min(m,n))        D.O(max(m,n))

        解答：D

        最坏情况下，需要将两个链表都遍历一遍，时间复杂度为 O(m+n)=O(max(m,n))

        2.一个栈的入栈序列为 1，2，3......n，其出栈序列为 p1，p2，p3......pn。若 p2 =3，则 p3 可能取值个数为____。

        A.n-3        B.n-2        C.n-1        D.无法确定

        解答：C

        p2=3，那么 p3 可能为出 3 外任意一数，有n-1种可能。

        3.若将关键字1，2，3，4，5，6，7 依次插入初始为空的平衡二叉数 T 中，则 T 中平衡因子为 0 的分支节点个数为_____。

        A.0        B.1        C.2        D.3

        解答：D

        将 1，2，3，4，5，6，7 依次插入后，T 如下图所示，因此平衡因子为 0 的分支节点个数为

        4.已知三叉树的 6 个叶节点的权分别是 2，3，4，5，6，7，T 的带权（外部）路径长度最小是______。

        A.27        B.46        C.54        D.56

        解答：B
        最小带权路径为 1*7+1*6+2*5+2*4+3*3+3*2=46

        5.若 X 是后序线索二叉树中的叶节点，且 X 存在左兄弟节点 Y ，则 X 的右线索指向的是____。

        A.X 的父节点                        B.以 Y 为根的子树的最左下节点

        C.X 的左兄弟节点 Y             D.以 Y 为根的的子树的最坐下节点

        解答：A        

        因为是后序线索二叉树，因此 X 的右节点指向后序遍历时的下一个节点。又因为 X 是叶节点，依次指向 X 的父节点。

        6.在任意一颗非空二叉排序树 T1 中，删除某节点 v 后形成二叉排序树 T2，再将 V 插入 T2 形成二叉排序树 T3。下列关于 T1 和 T3 的叙述中，正确的是____。        

        I.若 v 是 T1 的叶节点，则 T1 和 T3 不同

        II. 若 v 是 T1 的叶节点，则 T1 和 T3 相同

        III.若 v 不是 T1 的叶节点，则 T1 和 T3 不同

        Ⅳ.若 v 不是 T1 的叶节点，则 T1 和 T3 相同

        A.I,III        B.I,Ⅳ        C.II,III        D.II,Ⅳ

        解答：A        

        若是 T1 的叶节点，会插入到相同的位置。若不是，原来的位置会被其余节点替代，再插入时会形成一颗新的树。

        7.设图的邻接矩阵 A 如下所示。各顶点的度依次是____。

                                                               A

         A.1,2,1,2        B.2,2,1,1,        C.3,4,2,3        D.4,4,2,2

        解答：C

        顶点 1 入度为 1，出度为 2，因此其度为  3，选C         

        8.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历的是_____。

        

        A.h,c,a,b,d,e,g,f        B.e,a,f,g,b,h,c,d        C.d,b,c,a,h,e,f,g        D.a,b,c,d,h,e,f,g

        解答：D

        A项，h 与 c,a 相连；c 与 b,d 相连，a与 e 相连； e 与 f，g相连，满足要求。

        B项，e 与 a,f,g 相连； a 与 b,h 相连; b 与 c，d 相连，满足要求

        C项，d 与b，c相连；b 与 a 相连，c 与 h 相连；a 与 e 相连；e 与 f，g 相连，满足要求

        D项目，a 与b，e 相连，a之后出现的确实 b，c ，不满足要求，此处应该是 深度优先。

        9.下列 AOE 网表示一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是______。

        

        A.c 和 e        B.d 和 c        C.f 和 d        D.f 和 h

        解答：C

        该 AOE 网的关键路径为 bdeh,bfh,bdcg,只有 C 项中的活动在所有关键路径中都出现至少一个，因此选 C。

        10.在一颗高度为 2 的 5 阶 B 树中，所含关键字的个数最少是____。

        A.5        B.7        C.8        D.14

        解答：A

        5 阶段 B 树，关键字个数最少时，根节点只有 1 个关键字，非根节点只有 5/2 个关键字。B 树所有叶子节点都位于同一层，因此根节点至少有两个子节点。综上，至少有  1+2+2=5 个关键字。

        11.对给定关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分配后收集到的关键字序列是_____。

        A.007,110,119,114,911,120,122        B.007,110,119,114,911,122,120

        C.007,110,911,114,119,120,122        D.110,120,911,122,114,007,119

        解答：C

        基数排序：依次根据个位，十位，百位......进行排序

         第一趟排序后为110，120，911，122，114，007，119。

        第二趟排序后为007，110，911，114，119，120，122。

        因此选C。

        12.某计算机主频为 1.2GHz，其指令分为 4  类，他们在基准程序中所占比例及 CPI 如下表所示。

        该机的 MIPS 数是______。

        A.100        B.200        C.400        D.600

        解答：C

        假设该基准程序有 10 条指令，则其消耗 5*2+2*3+1*4+2*5=30 个时钟周期，则平均每条指令耗费 3 个时钟周期。 计算机主频为 1.2GHz，则每秒有 1.2*1000*10^6=1200 * 10^6 个时钟周期，因此 该机的 MIPS 数为 400 。

        13.若某数采用 IEEE 754 单精度浮点数格式表示为 C640 0000H，则该数的值为______。

        A.1.5*2^13        B.1.5*2^12        C.0.5*2^13        D.0.5*2^12

        解答：C

        C640H= 1100 0110 0100 0000B

        首位为  1 ，是符号位。

        接着八位是阶数，1000 1100B，原值为 1000 1100B-0111 1111B=0000  1101B=13

        剩余是尾数，100 0000 0000 0000 0000 0000B=0.5，所以值为 1.5。

        所以值为 1.5*2^13。

        14.某字长为 8 位的计算机中，已知整型变量 x 和 y 的机器数分别为 [x]补=1 1110100，[y]补=1 0110000。若整型变量 z=2x+y/2，则 z 的机器数是_____。

        A. 1 1000000        B.0 0100100        C.1 0101010        D.溢出

        解答：A

        2*x，x左移一位， 1110 1000

        y/2，y带符号右移一位，1101 1000

        2*x+y/2=1110 1000 +1101 1000 =  1100 0000。

        15.用海明码对长度为 8 位的数据进行检/纠错时，若能纠正一位错，则校验位数至少是____。

        A.2        B.3        C.4        D.5

        解答：C

        海明码：n 表示数据位数，k表示校验位数，海明码纠错一位时应满足此不等式：2^k>=n+k+1，当 k >= 4 时，此不等式成立。 

        16.某计算机主存地址空间大小为 256MB，按字节编址。虚拟地址空间大小为 4GB，采用页式存储管理，页面大小为 4KB，TLB 采用全相连映射，有 4 个页表项，内容如下表所示。

        

则对虚拟地址 03FF F180H 进行虚实地址变换的结果是_______。

        A.015 3180H        B.003 5180H        C.TLB 缺失        D.缺页

        解答：A

        虚拟地址空间大小为 4GB=4*2^10*2^10KB ，页面大小为 4KB，因此有 2^20 个页面，需要 20 位来表示，因此 03FF FH表示虚拟页号及标记，对应有效位为 1，因此页框号为 0153H，因此实地址为 0153 180H。选 A

        17.假设变址寄存器 R 的内容为 1000H，指令中的形式地址为 2000H；地址 1000H 中的内容是 2000H，地址 2000H 中的内容是 3000H，地址 3000H 中的内容是 4000H，则变地寻址方式下访问到的操作数是_____。

        A.1000H        B.2000H        C.3000H        D.4000H

        解答：D

        变址寻址地址=形式地址+编址寄存器地址。地址为 1000H+2000H=3000H，内容为 4000H。

        18.某 CPU 主频为 1.03 GHz，采用 4 级指令流水线指令，每个流水段的执行需要 1 个时钟周期。假定 CPU 执行了 100 条指令，在其执行过程中，没有发生任何流水线阻塞，此时流水线的吞吐率为_______。

        A.0.25*10^9 条指令每秒        B.0.97*10^9 条指令每秒

        C.1.0* 10^9 条指令每秒        D.1.03*10^9 条指令每秒

        解答：C

        100 条指令，第一条指令的执行需要 4 个时钟周期，其余指令的执行只需要 1 个时钟，因此 100 条指令的执行共花费 4+99=103 个周期。CPU 主频为 1.03GHz，因此每秒有 1.03G 个时钟周期，每秒执行 1 G 条执行，因此选C。

        19.下列选项中，用于设备和设备控制器（I/O 接口）之间互连的接口标准的是______。

        A.PCI        B.USB        C.AGP        D.PCI-Express

        解答：B

        USB 是一种连接外部设备的 I/O 总线标准，属于设备总线。是设备与设备控制器间的接口。

        PCI 用来连接主存的标准。

        AGP 用来连接网卡的标准。

        PCI-Express 用来连接视频卡的标准。

        20.下列选项中，用于提高 RAID 可靠性的措施有______.

        I.磁盘镜像         II.条带化        III.奇偶校验        Ⅳ.增加Cache机制

        A.I,II        B.I,III        C.I,III,IV        D.II,III,IV

        解答：B

        RAID 独立磁盘冗余阵列，即用多个独立的磁盘组成一个大的磁盘系统，从而实现比单个磁盘更好的存储性能和更高的可靠性。

        磁盘镜像，磁盘内容存在拷贝，可以提高可靠性。

        条带化是一种自动地将 I/O 负载均衡到多个物理磁盘上（将一个连续的数据分成很多小部分并将其存储在不同的磁盘上）的技术，目的是使多个进程同时访问数据的不同部分而不造成磁盘冲突，可以提高性能而不是可靠性。

        奇偶校验可以检错，提高可靠性。

        增加 Cache 机制可以提高性能而不是可靠性。

        21.某磁盘转速为 10000rpm，平均寻道时间是 6ms，磁盘传输速率仅为 20MB/s，磁盘控制器延迟为 0.2ms，读取一个 4KB 的扇区所需的平均时间为______。

        A.9ms        B.9.4ms        C.12 ms        D.12.4ms

        解答：B

        转速为 10000rpm，那么转一圈需要 60/10000 s=6ms，因此平均查询扇区时间为 3ms（因不知道当前在哪一个扇区，因此按半圈算）；寻道时间为 6ms；数据传输时间为 4/(20*10^3)=0.2 ms；延迟为 0.2ms，因此所需时间为 9.4ms。

        22.下列关于中断 I/O 方式和 DMA 方式比较的叙述中错误的是______。

        A.中断 I/O 方式请求的是 CPU 处理时间，DMA 方式请求的是数据控制权

        B.中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后

        C.中断 I/O 方式下数据传送通过软件完成，DMA 方式下数据仅有硬件完成

        D.中断 I/O 方式适用于所有外部设备，DMA 方式仅适用于快速外部设备

        解答：D

        DMA 方式适用于有大批量数据需要传送的设备如磁带机，磁盘机。

        23.用户在删除某文件的过程中，操作系统不可能执行的操作是_____。

        A.删除此文件所在的目录                        B.删除与此文件关联的目录项

        C.删除与此文件对应的文件控制块        D.释放与此文件关联的内存缓冲区

        解答：A

        该目录下可能还有其余文件，因此不能删除其所在目录

        24.为支持 CD-ROM 中视频文件的快速随机播放，播放性能最好的文件数据块组织方式是____。

        A.连续结构        B.链式结构        C.直接索引结构        D.多级索引结构

        解答：A

        随机存取只能是 连续结构（通过偏移量实现）和索引结构。相较而言，连续结构随机存取较快，因此选 A。

        25.用户程序发出磁盘 I/O 请求后，系统的处理流程是：用户程序->系统调用处理程序->设备驱动程序->中断处理程序。其中，计算数据所在柱面号、磁头号、扇区号的程序是_____。

        A.用户程序        B.系统调用处理程序        C.设备驱动程序        D.中断处理程序

        解答：C

        数据所在柱面号、磁头号、扇区号的计算随设备的不同而不同，因此应当是由厂家提供的设备驱动程序完成。

        26.若某文件系统的索引节点（inode）中由直接地址项和间接地址项，则下列选项中，与单个文件长度无关的因素是_______。

        A.索引节点的总数        B.间接索引地址的级数

        C.地址项的个数           D.文件快大小

        解答：A

        索引节点的总数是文件的数量，与单个文件长度无关。

        地址项的个数为直接地址索引+间接地址索引。

        27.设系统缓冲区和用户工作区均采用单缓冲，从外设读入 1 个数据块到系统缓冲区的时间为 100，从系统缓冲区读入 1 个数据块到用户工作区的时间为 5 ，对用户工作区的 1 个数据块进行分析的时间为 90（如下图所示）。进程从外设读入并分析 2 个数据块的最短时间为_____。

        

        

         A.200        B.295        C.300        D.390

        解答：B   C

        从外设读入 2 个数据块的时间为 200，第二个外设读入完毕后，第一个已完成剩余操作，因此所需时间为 200+95=295。

        0~100 缓冲区读入第一个数据块

        100~105，用户工作区读入第一个缓冲区。

        105~195，用户工作区分析第一个数据块，同时缓冲区读入第二个数据块

        195~205，外设继续读入第二个数据块。

        205~210，用户工作区读入第二个数据块。

        210~300，用户工作区分析第二个数据块。

        

        28.下列选项中，会导致用户进程从用户态切换到内核态的操作是______。

        I.处理越界错        II.sin() 函数调用        III.read 系统调用

        A.I,II        B.II,III        C.I,III        D.I,II,III

        解答：C

        能从用户态切换到内核态的三种方式：1.系统调用       2.异常        3.外围设备的中断

        越界错属于异常，II 不属于以上 3 种中的任意一种，故选 C

        29.计算机开机后，操作系统最终被加载到______。

        A.BIOS        B.ROM        C.EPROM        D.RAM

        解答：D

        解答：

        系统开机后，操作系统的程序会被自动加载到内存中的系统，这段区域是 RAM

        BIOS（Basic Input Output System）基本输入输出系统

        ROM  （Read-Only Memory）只读存储器

        EPROM（Erasable Programmable Read-only Memory）可擦除可编程只读存储器

        RAM （Random  Access Memory）随机存取存储器

        30.若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是_____。

        I.处理越界错        II.置换页        III.分配内存

        A.I,II        B.II,III        C.I,III        D.I , II 和 III

        解答:B

        发生缺页中断,没有越界,故不可能处理越界错.若内存中的相关空间已满,则要置换页,否则分配内存将所需页调入.

        31.某系统正在执行三个进程 P1,P2,P3, 各进程的计算(CPU)时间和 I/O 时间比例如下表所示.

        为提高系统资源利用率,则合理的优先级设置应为______.

        A.P1>P2>P3        B.P3>P2>P1        C.P2>P1=P3        D.P1>P2=P3

        解答:B

        先进行计算,在进行 I/O.因此计算时间越长,优先级应当越低,这样在本轮的 I/O 时可供下轮进行的计算时间越长.

        32.下列关于银行家算法的叙述中,正确的是____.

        A.银行家算法可以预防死锁

        B.当系统处于安全状态时,系统中一定无死锁进程

        C.当系统处于不安全状态时,系统中一定存在死锁进程

        D.银行家算法破坏了死锁必要条件中的"请求和保持"条件

        解答:B

        A项,当存在安全序列时,银行家算法可以预防死锁

        C项,当系统处于不安全状态时,随着资源的分配,系统中可能会出现死锁

        D项,银行家算法通过破坏死锁产生的必要条件来预防死锁

        33.在 OSI 参考模型中,下列功能需要由应用层的相邻层实现的是_______.

        A.对话管理        B.数据格式转换        C.路由选择        D.可靠数据传输

        解答:B

        与应用层相邻的是表示层.

        A项对话管理由会话层完成

        B项数据格式转换由表示层完成

        C项路由选择由网络层完成

        D项可靠数据传输由传输层完成

        34.若下图为 10BaseT 网卡收到的信号波形,则该网卡收到的比特串是______.

        

        A.0011 0110        B.1010 1101        C.0101 0010        D.1100 0101

        解答:A

        10BaseT 即 10Mbps 的以太网,采用曼彻斯特编码,将一个码元分为俩个相等的间隔,前一个间隔为低电平 ,后一个间隔为高电平表示 0(1),此时相反的就表示为 1(0).因此图中比特串可能为 0011 0110 或 1100 1001,只有前者出现,故选A.

        35.主机甲通过 1 个路由器(存储转发方式)与主机乙联系,两段链路的数据传输速率均为 10Mbps,主机甲分别采用报文交换和分组大小为 10kb 的分组交换向主机乙发送 1 个大小为 8Mb (1M=10^6) 的报文.若忽略链路传播时延,分组头开销和分组拆装时间,则两种交换方式完成该报文传输所需的总时间分别为______.

        A.800ms,1600ms        B.801ms,1600ms        C.1600ms,800ms        D.1600ms,801ms

        解答:D

        数据传输到链路上消耗时间为 8/10=0.8s=800ms.

        报文交换:整个报文先传输到相邻节点,相邻节点将其全部储存下来后再查找转发表转发.

                 本题中,数据先传输到路由器中,再传输到主机C,需要两个完整的数据传输过程,因此需要 800ms*2=1600ms

        分组交换:单个分组传输到相邻接待后,相邻节点即查找转发表转发. 

                  本题中, 报文大小为 8Mb=8*10^3kb, 分组大小为 10kb,因此报文会被分割为 800 个分组.单个分组传输到链路中的时间为 10/(10*10^3) s=1/10^3 s=1ms.第一个分组传输到主机乙耗时 2ms,因为路由器在转发前一个分组时 ,主机甲就在发送前一个分组,因此后续 799 个分组耗时 1s,所以总耗时为 799+2=801ms

        36.下列介质访问控制方法,可能发生冲突的是______.

        A.CDMA        B.CSMA        C.TDM       D.FDM

        解答:B

        介质访问控制(medium access control)简称 MAC,是解决公用信道使用产生竞争时,如何分配信道使用权的问题

        CSMA(Carrier Sense Multiple Access 即载波侦听多路访问协议) :在发送数据前先侦听信道,忙则等待,空闲则发送.可能发生冲突.

        CDMA(Code Division Multiple Access 即码分多址):给每个节点分配不同的编码,然后每个节点用它唯一的编码来对她发送的数据进行编码.如果精心选择这种编码,就能做到使不同的节点同时传输,并且他们各自对应的接收方仍能正确接收发送方发送的数据,而不在乎其他节点的干扰传输.

        FDM(Frequency-division multiplexing 即频分多路复用):将信道划分为不同的频段,每个节点拥有其中一个频段.

        TDM(Time-division multiplexing 即时分多路复用):将时间划分为时间帧,然后进一步将时间帧划分为时隙,然后将时隙分配给不同的节点.

        37. HDLC 协议对 01111100 01111110 组帧后对应的比特串为_____.

        A.011111100 001111110 10        B.01111100 01111101 011111110

        C.011111100 011111101 0         D.01111100 01111110 011111101

        解答:A

        HDLC 协议(High Level Data Link Control 即高级数据链路控制协议):面向比特的网络节点之间同步传输数据的数据链路层协议.

        HDLC 数据帧以 0111 1110 标识帧的开始与结束,因此每出现五个连续的 1 就在后面补一个0,即使后面一位为 0.因此结果为 01111100 00111110 10,选A

        38.对于 100Mbps 的以太网交换机,当输出端口无排队,以直通交换(cut-through switching)方式转发一个以太网帧(不包括前导码)时,引入的转发时延至少是_____.

        A.0us(微秒)        B.0.48us        C.5.12us        D.121.44us

        解答:B

        直通交换方式是指以太网交机可以在各端口间交换数据.他在输入端口检测到一个数据包时,检查该包的包头,获取包的目的地址,启动内部的动态查找表寻找到相应的输出端口,然后在输入输出交叉处连通,把数据包直通到相应的端口,实现交换功能.

      在直通方式时,交换机接收到 MAC 帧,不待接收完整,就按帧首部中的目的 MAC 地址来判别转发端口 , 目的 MAC 地址 6B即 48b,转发时延为 48/(100*10^6) s=0.48us

        39.主机甲和主机乙之间建立一个 TCP 连接,双方持续传输数据,且数据无差错与丢失.若甲收到 1 个来自乙的 TCP 段,该段的序号为 1913,确认序号为 2046,有效载荷为 100 字节,则甲立刻发送给乙的 TCP 段的序号与确认序号分别是_____.

        A.2046,2012        B.2046,2013        C.2047,2012        D.2047,2013

        解答:B

        乙发送的确认序号是甲上一次发送的最后一个字节的序号加一,因此甲本次发送的序号为 2046.

        乙发送的段的序号为 1913,共有 100 字节,因此末尾字节的序号为 2012,甲对此的确认是在此基础上加一,即 2013.

        40.下列关于 SMTP 协议的叙述中,正确的是______.

        I.只支持传输 7 比特 ASCII 码内容                        II.支持在邮件服务器之间发送邮件

        III.支持从邮件代理向邮件服务器发送邮件            IV.支持从邮件服务器向用户发送邮件

        A.I,II,III        B.I,II,IV        C.I,III,IV        D.II,III,IV

        解答:A

        SMTP 协议(Simple mail trasfer porotcol) 即简单邮件传输协议.

        SMTP 协议传输邮件时,需要发送方会向接收方发送信息以建立一个传输信道,而邮件服务器向用户发送邮件时,因为用户在线时间未知,需要用户主动发送信息建立信道,所以不适用 SMTP.

        二 、综合应用题

        41.（13 分）已知一个整数序列 A=（a0,a1,a2...an-1），其中 0<=ain/2 (0<=pk

        （1）给出算法的基本设计思想

        （2）根据设计思想，采用 C、C++ 或 Java 语言描述算法，关键之处给出注释。

        （3）说明你所设计算法的时间复杂度和空间复杂度。

        解答：

        （1）初始时，主元素为 -1，计数为0.然后遍历数组，若主元素与当前元素相同，计数加一；若主元素与当前元素不同，若计数大于 1 ，计数减一，否则将当前元素设置为主元素，计数变更为1.遍历结束后，若计数大于0，重新遍历对当前元素进行计数判断其是否为主元素，否则，不存在主元素。

        （2）

class Solution{
    public int findMainElement(int[] P){
        int main=-1;
        int cnt=0;
        for(int i=0;i<P.length;i++){
            if(P[i]==main){
                cnt++;
            }else{
                if(cnt==0){
                    main=P[i];
                    cnt=1;
                }else{
                    cnt--;
                }
            }
        }
        if(cnt==0){
            return -1;
        }
        return isMainElement(main,P):main:-1;
    }
    public boolean isMainElement(int main,int[] P){
        int m=0;
        int n=P.length;
        for(int i=0;i<n;i++){
            if(P[i]==main){
                m++;
            }
        }
        return m>n/2;
    }
}

      （3）时间复杂度：O(n)。空间复杂度:O(1)

        42.设包含 4 个元素的集合 S={"do","for","repeat","while"}，各元素的查找概率依次为 p1=0.35，p2=0.15，p3=0.15，p4=0.35。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2，请回答：

        （1）若采用顺序存储结构保存 S，且要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

        （2）若采用链式存储结构保存 S，且要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

        解答：（1）若采用顺序存储结构保存 S，元素排列应为{"do","while","for","repeat"}，使用顺序查找法，查找成功时的平均查找长度是 0.35+0.35*2+0.15*3+0.15*4=0.35+0.7+0.45+0.6=1.05+1.05=2.1。

        （2）若采用链式存储结构，元素排列应为{"do","while","for","repeat"}，使用顺序查找法，查找成功时的平均查找长度是 0.35+0.35*2+0.15*3+0.15*4=0.35+0.7+0.45+0.6=1.05+1.05=2.1。

        43.某 32 位计算机，CPU 主频为 800MHz，Cache 命中时的 CPI 为 4，Cache 块大小为 32 字节；主存采用 8 体交叉存储方式，每个体的存储字长为 32 位、存储周期为 40ns；存储器总线宽度为 32 位，总线时钟频率为 200MHz，支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备数据、传送数据。每次突发传送 32 字节，传送地址或 32 位数据均需要一个总线时钟周期。请回答一下问题，要求给出理由或计算过程。

        （1）CPU 和总线的时钟周期各为多少？总线的带宽（最大数据传输率）是多少？

        （2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？

        （3）存储器总线完成一次读突发传送总线事务所需的时间是多少？

        （4）若程序 BP 执行过程中，共执行了 100 条指令，平均每条指令需进行 1.2 次访存，Cache 缺失率为 5%，不考虑替换等开销，则 BP 的 CPU 执行时间是多少？        

        知识点：8 体交叉存储方式：8 个体，0存放在体1，1存放在 体2...... 7 存放在体 8，8 存放在体 1......

        在第三问中，8 个体要各进行一次存储。（不是很理解为啥）

        解答：（1）CPU 主频为 800MHz，因此 CPU 的时钟周期为 1/800M s=1.25ns

        总线时钟频率为 200MHz，因此总线的时钟周期为 1/200M s=5ns

        总线宽度为 32 位，因此总线带宽为 200MHz*32b=6400Mbps=800Mbps

        (2)Cache 大小为 32b，每次突发传送 32b，因此需要 1 个读突发传送总线事务读取一个主存块

        （3）送首地址花费一个总线时钟周期 5ns；准备及传送数据时，存取周期为 40ns，因此读第一个体需要 40ns，传输需要一个总线时钟周期即 5ns，因此第一个体需要花费 45ns，后续每个体需要  5ns 传送数据，因此此阶段花费 45+5*7=80ns。因此一共花费 80ns+5ns=85ns

       0ns 送首地址

       5ns 首地址传输结束，开始读第一个体

       10ns 开始读第二个体（存储周期为 40ns，每隔40ns/8 读一个体）

        ......

       40ns 第一个体读取结束，开始传输第一个体；开始读第 8 个体

        45ns  第一个体传输结束，第二个体读取结束。开始传输第二个体

        ......

        85ns 第8 个体传输结束

        （4）Cache 命中的指令执行时间（Cache 未命中时也要执行一个Cache 相关指令来获取Cache 未命中的结果）：100*4*1.25ns=500ns

        额外开销：100*5%*1.2*85ns=6*85ns=510ns

        因此总花费时间为 1010ns

        44.某计算机采用 16 位定长指令字格式，其中 CPU 有一个标志寄存器，其中包含进位/借位标志 CF，零标志 ZF 和符号标志 NF。假设为该机设计了条件转移指令，其格式如下：

                      15                   11      10          9           8            7                                 0

        其中，00000 为操作码 OP；C，Z，N 分别为 CF、ZF，NF 的对应检测位，某检测位为 1 时表示需检测对应标志位，需要检测的对应标志位中只要有一个 1 就转移，否则不转移。例如，若 C=1，Z=0，N=1，则需检测 CF 和 NF 的值，当 CF=1 或 NF=1 时发生转移：OFFSET 是相对偏移量，用补码表示。转移执行时，转移目标地址为 (PC)+2+2*OFFSET；顺序执行时，下条指令的地址是 (PC)+2。请回答下列问题：

        （1）该计算机存储器按字节编址还是按字编址？该条件转移指令向后（反向）最多可跳转多少条指令？

        （2）某条件转移指令的地址为 200CH，指令内容如下图所示，若该指令执行时 CF=0，ZF=0，NF=1，则该指令执行后 PC 的值是多少？若该指令执行时 CF=1，ZF=0，NF=0，则该指令执行后 PC 的值又是多少？请给出计算过程。

                               15                   11    10          9            8          7                                 0

        （3）实现 “无符号数比较小于等于时转移” 功能的指令中，C、Z 和 N 应各是多少？

        （4）以下是该指令对应的数据通路示意图，要求给出图中部件 1~3 的名称或功能说明？  

    

        解答：（1）按字节编址。

        最多可以向后跳转 2^7-1=127 条指令。 

        （2）若在该指令执行时 CF=0，ZF=0，NF=1，因为 NF 为 1，因此需要转移，此时OFFSET 为 1110 0011B ，2*OFFSET 为  1111 1111 1100 0110B 即 FFC6H，转移后 PC 的值为 200CH+0002H+FFC6H=200EH + FFC6H= 1FD4H

        若在该指令执行时，CF=1，ZF=0，NF=0，则不需要注意，指令执行后 PC 的值为 200CH+0002H=200EH。

        （3）C 为 1，Z 为 1，N 为 0。进行数之间的比骄傲通常是进行减法操作，在小于等于 0 时转移，若是负数，产生借位，若是零， 零标志为 为0，因此 C 和 Z 为 1。无符号数的减法操作不涉及符号标志 NF。

        （4）部件 1 用于存放当前指令，为指令寄存器。

        部件 2 用于实现 2*OFFSET，为移位寄存器。

        部件 3 用于实现 （PC）+2+2*OFFSET，为加法器。

        45.某博物馆最多容纳 500 人同时参观，有一个出入口，该出入口一次仅允许一人通过。参观者的活动描述如下：

cobegin
    参观者进程 i:{
            ...
        进门;
            ...
        参观;
            ...
        出门；
        ...
    }
coend;

        请添加必要的信号量和 P、V（或 wait()，signal()）操作，以实现上述过程中的互斥与同步。要求写出完整过程，说明信号量的含义并赋初值。

        解答：

        出入口仅允许一人通过，设为 mutex，初始值为 1；馆内允许最多 500 人入内，因此设为 aceess，初值为 500。

semaphore mutex=1;         //出入口
semaphore access=500;        //馆内允许进入人数
 
cobegin
    参观者进程 i:{
        P(access);          //等待允许入内
        P(mutex);   //等待占据入口，
        进门;
        V(mutex);   //释放入口
        参观;
        P(mutex);    //等待出口
        出门；
        V(mutex);    //释放出口
        V(access);         //博物馆内人数减少，允许他入内
    }
coend;

        

        46.某计算机主存按字节编址，逻辑地址和物理地址都是 32 位，页表项大小为 4 字节。请回答以下问题：

        （1）若使用一级页表的分页存储管理方式，逻辑地址结构如下 ：

则页的大小是多少字节？页表最大占用多少字节？

        （2）若使用二级页表的分页存储管理方式，逻辑地址结构如下：

设逻辑地址为 LA，请分别给出其对应的页目录号和页索引表的表达式。

        （3）采用（1）中的分页存储管理方式，一个代码段起始逻辑地址为 0000 8000H，其长度为8KB，被装载到从物理地址 0090 0000H 开始的 4连续主存空间中。页表从主存 0020 0000H 开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项的页框号以及代码页面 2 的起始物理地址。

        解答：（1)页内偏移量有 12 位，因此页的大小为 2^12B=4KB

        页号有 20 位，因此页表项最多有 2^20 个，最多占据 2^20*4B=2^22B=4MB 

        （2）页目录号：((unsigned int)LA)>>22        

        页索引表：((unsigned int)LA)>>12 &0x3FFH          （&0x3FFH将除低10位外全部置0）

        （3）起始逻辑地址 0000 8000H 被装载到 0090 0000H 的主存物理地址处，因此图中页框号 1 与逻辑地址 0000 8000H 的页号相同。而起始逻辑地址为 0000 8000H 即 0000 0000 0000 0000 1000 0000 0000 0000B ，页号为前 20 位 0000 0000 0000 0000 1000B 即 0008H ，因此页表项 1 为第 8 个页框号。而页表项大小为 4KB，因此物理地址  1 为 0200 0000H+8*4=0200 0020H，物理地址 2 为 0200 0000H+9*4=0200 0024H（按字节编址）

        采用 （1）的 方式时，页框号就是页号，因此页框号也是 20 位，因此页框号 1 位物理地址 0090 0000H 的前 20 位 0 0900H。

        页面大小为  4KB，因此物理地址 3 为 0090 0000H+ 4KB=0090 0000H+ 1 0000 0000 0000B=0090 1000H，前 20位为页框号即 0 0901H。

        47.假设 Internet 的两个自治系统构成的网络如题 47 图所示，自治系统 ASI 由路由器 R1 连接两个子网构成；自治系统 AS2 由路由器 R2,R3 互联并连接三个子网构成。各子网地址、R2 的接口名，R1 和 R3 的部分接口 IP地址 如题 47 图所示。

  请回答以下问题：

        （1）假设路由表结构如下表所示。请利用路由聚合技术，给出 R2 的路由表，要求包括到达题 47 图中所有子网的路由，且路由表中的路由项尽可能少。

        （2）若 R2 收到一个目的 IP 地址为 194.17.20.200 的 IP 分组，R2 会通过哪个接口转发该 IP 分组？

        （3）R1 和 R2 之间利用哪个路由协议交换路由信息？该路由协议报文被封装到哪个协议的分组中进行传输？

        解答：（1）

        （2）该 IP 地址与路由表中的 194.17.20.0/23 和194.17.20.128/25 均匹配，根据最长匹配原则，通过 E0 接口转发。

        （3）R1 和 R2 属于不同的自治系统，因此使用边界网关协议 BGP 交换路由信息。BGP 协议是应用层协议，报文被封装在 TCP 协议的分组中进行传输。