408-2016

        一、单项选择题

        1.已知表头元素为 c 的单链表在内存中的存储状态如下表所示。

        先将 f 存放在 1014H 处并插入到单链表中，若 f 在逻辑上处于 a 和 e 之间，则a，e，f 的链接地址依次是______。

        A.1010H,1014H,1004H        B.1010H,1004H,1014H

        C.1014H,1010H,1004H        D.1014H,1004H,1010H

        解答：D

        a 链接 b ，因此a 的链接地址为 1014H，e 链接嗲地址不变，因此是 1004H，选 D。

        2.已知一个带有表头节点的双向循环链表L，节点结构为 prev，data，next，其中 ， prev 和next 分别是指向其直接前驱和直接后继节点指针，现在要删除 p 所指节点，正确的语序是____。

        A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);

        B.p->next->prev=p->next;p->prev->next=p->next;free(p);

        C.p->next->prev=p->next;p->prev->next=p->prev;free(p);

        D.p->next->prev=p->prev;p->prev->next=p->next;free(p);

        解答：D

        3.设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1~9 的 9 列列车，驶入的顺序依次是 8，4，2，5，3，9，1，6，7。若期望的驶出次序为 1~9，则 n 至少是________。

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

        解答：C

        若要 驶出顺序为 1~9 ，则 8，4，2，5，3，9 需能够停在车轨中，且有车轨供 1 驶入驶出。但 ABCD 中无7 这一选项，故同一车轨中可能停靠多辆火车。因此至少有  4 条车轨，1 号车轨停留 8，9；2 号车轨停留 4，5；3 号车轨停留 2，3；4 号车轨供 1 驶入驶出。

        4.有一个 100 阶的 三对角矩阵 M ，其元素 m(i,j)（1<=i<=100,1<=j<=100）按行优先依次压缩存入下标 0 开始的一维数组 N 中，元素 m（30，30）在N 中的下标为_______。

        A.86        B.87        C.88        D.89

        解答：B

        三对角矩阵，元素在主对角线及其两侧分布。

        前 30 行元素有 2+29*3=89 个元素（第一行只有 2 个元素），且最后一个元素在 N 中的下标为 88，M（30，30）是倒数第二个元素，因此 m(30,30) 在 N 中下标为 87.

        5.若森林 F 有 15 条边，25 个节点，则F 包含树的个数为____。

        A.8        B.9        C.10        D.11

        解答：C

        15 条边，若每条边属于不同的树，则有 30 个节点。每削减一棵树，节点数量 减一，因此 F 包含树的个数为 10。

        6.下列选项中，不是下图深度优先搜索序列的 是______。

        

        A.V1,V5,V4,V3,V2        B.V1,V3,V2,V5,V4

        C.V1,V2,V5,V4,V3        D.V1,V2,V3,V4,V5

        解答：D

        D 项 V2->V5可达，V2->V3 不可达

        7.若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是______。

        A.O（n）        B.O(n+e)        C.O(n^2)        D.O(ne)

        解答：B

       根据拓扑排序的规则，输出每个顶点的同时还要删去以他为起点的边，因此各顶点和边都需要进行遍历。

        8.使用迪杰斯特拉（Dijskra）算法求下图中从顶点 1 到其他顶点的最短路径，依次得到的各最短路径的目标顶点是______。

         

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

        解答：B

        9.在有 n（n>1000） 个元素的升序数组 A 中查找关键 x。查找算法的伪代码如下：

k=0;
while(k<n 且 A[k]<x)    k=k+3;
if(k<n 且 A[k]==x)    查找成功;
    else if(k-1<n 且 A[k-1]==x)    查找成功;
        else if(k-2<n 且 A[k-2]==x)    查找成功;
            else     查找失败;

        本查找与折半查找算法相比，有可能具有更少比较次数的情形是_______。

        A.当 x 不在数组中               B.当 x 接近数组开头       

       C.当 x 接近数组结尾处        D.当x 处于数组中间位置

        解答：B

        当查找元素为第一个元素时，本查找算法只需比较一次，而折半查找至少需比较1次。

        10.B+树不同于 B 树的特点之一是______。

        A.能支持顺序查找                B.节点中含有关键字

        C.根节点至少有两个分支       D.所有叶节点都在同一层

        解答：A

        B树，多路平衡查找树

        B+树，多路平衡查找树，但非叶节点只做索引使用

        B树只能进行多路查找，而在 B+ 树中，所有叶子节点均保存在同一层，且每个叶子节点均包含指向下一个叶子节点的指针，故 B+树支持顺序查找。

       

        11.对 10TB 的数据文件进行排序，应使用的方法是_____.

        A.希尔排序        B.堆排序        C.快速排序        D.归并排序

        解答：D

        当对 10TB 的数据文件进行排序时，内存中一次放不下，因此需使用外部排序，而外部排序一般使用归并排序。

        12.将高级语言源程序转化为机器级目标代码文件的是______。

        A.汇编程序        B.链接程序         C.编译程序        D.解释程序

        解答：C

        

        13.有如下 C 语言程序段：

short si=-32767
unsigned short usi=si;

        执行上述两条语句后，usi 的值为______。        

        A.-32767        B.32767        C.32768        D.32769

        解答：D

        32767 ， 0111 1111 1111 1111，因此，-32767 为 1000 0000 0000 0001 ，无符号整数表示时为 32769.

        14.某计算机字长为 32 位，按字节编址，采用小端（Little Endian）方式存储数据。假定有一个 double 变量，其机器数表示为 1122 3344 5566 7788H，存放在 0000 0840H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是______。

        A.22H        B.33H        C.77H        D.66H

        解答：A

        小段存储方式，低位存储在低地址，因此 0840H->88H，0841H->77H ......0846H 22H   

        15.有如下 C 语言程序段：

for(int k=0;k<1000;k++)
    a[k]=a[k]+32;

             若数组 a 及变量k 均为 int 型，占 4 字节，数据 Cache 采用直接映射方式，数据区大小为 1KB，块大小为 16B，该程序段执行前 Cache 为空，则该程序执行过程中访问数组 a 的 Cache 缺失率约为______。

        A.1.25%        B.2.5%        C.12.5%       D.25%

        解答：C

        语句 a[k]=a[k]+32 中，需要访存两次，因此一共访问 Cache 2000次。

        一个块大小为 16B，能存放 4 个数组元素。因此 2000 次中有 1000/4=250 次缺失，缺失率为 12.5% （每个元素两次访问 Cache，第二次一定命中）

        16.某存储器容量为 64KB，按字节编址，地址 4000H~5FFFH 为 ROM 区，其余为 RAM 区。若采用 8K*4 位的 SRAM 芯片进行设计，则需要该芯片的数量为_____。

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

        解答：C

        存储器容量为 64KB，其中 4000H~5FFFH 占 2*16*16*16B即 2^13B=8KB，因此有 56KB 为RAM 区。按字节编址，因此需要 2*(56/8)=14 块芯片

        ROM (read only memory)

        RAM(random access memory)

        17.某指令格式如下。

        其中 M 为寻址方式，I 为变址寄存器编号，D为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是______。

        A.I+D        B.(I)+D        C.((I)+D)        D.((I))+D

        解答：C

        变址寻址中 EA=(I)+D；间接寻址中，地址为保存数据的地址，即结果为C

        18.某计算机主存空间为 4GB ，字长为 32 位，按字节编址，采用 32 位字长指令字格式。若指令按字边界对齐存放，则程序寄存器（PC）和指令寄存器（IR）的位数至少是____。

        A.30、30        B.30、32        C.32、30        D.32、32

        解答：B

        主存空间为 4GB，字长为 32 位，因此至少有 4GB/32b=2^30 个地址（PC 只需要能够识别不同的指令，即给出指令在内存中的地址，即存储器的第几个字），因此 PC 的位数至少为 30。

        采用 32 位字长指令字，按字边界对齐存放，因此 IR 至少需要 32 位。

        19.在无转发机制的五段基本流水线（取址，译码/读寄存器，运算，访存，写回寄存器）中，下列指令序列中存在数据冒险的指令对是_____。

        I1. add R1,R2,R3;        (R2)+(R3)->(R1)

        I2. add R5,R2,R4;        (R2)+(R4)->(R5)

        I3. add R4,R5,R3;        (R5)+(R3)->(R4)

        I4. add R5,R2,R6;        (R2)+(R6)->(R5)

        A.I1和I2        B.I2 和 I3        C.I2 和 I4        D.I3 和 I4

        解答：B

        数据冒险：1.后一条指令会用到前一条指令的计算结果 2.在执行后一条指令时，前一条指令尚未执行完毕

        20.单周期处理器中所有指令的执行周期均为一个时钟周期。下列关于单周期处理器的叙述中，错误的是______。

        A.可以采用单总线结构控制通路        B.处理器时钟频率较低

        C.在指令执行过程中控制信号不变        D.每条指令的CPI 为 1

        解答：A

        A项，若采用单总线，可能会有多个部件争用总线，但单周期处理器不支持并发传送操作。故不能用单总线结构控制通路，A错误。

         控制信号即 PC 中的内容，可以自动加一，因此指令执行过程中控制信号不变。C 正确。

        所有指令的执行周期均为 一个时钟周期，即每条指令的 CPI 为 1，D正确

        有点指令执行时间较长，有的指令执行时间较短，要保证每条指令的 CPI 均为 1，处理器的时钟频率较低。

       

       

        21.下列关于总线设计的叙述中，错误的是______。

        A.并行总线传输总比串行总线传输速度快

        B.采用信号线复用技术可减少信号线总量

        C.利用突发传输方式可提高总线的利用率

        D.采用分离事务通信方式可提高总线利用率

        解答：A

        A项，并行总线传输：每一位由 1 条信号线传输。串行总线传输，所有位由 1 条信号线依次传输。并行传输通常比串行传输块，但如今时钟频率越来越高，并行导线之间的干扰越来越严重，因此当时钟频率越来越快时，并行导线的传输速率的提升速度可能反而不如串行传输。

        B项。信号线复用技术，将一条物理线路的全部带宽资源分成多个逻辑信道，让多个用户共享一条物理线路。

        C项，突发传输方式，多个数据单元被当成一个数据块来传输，从而提高传输效率

        D项，在分离通信方式中，发送和接收数据分开，发送数据前申请总线控制权，发送完毕即放弃总线控制，目标模块接收到其发送的数据后，准备好相应的数据再申请总线控制权，发送数据。

        22.异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或者异常情况的叙述中，错误的是______。        

        A.“访页时缺存”属于中断               B."整数除以0" 属于异常

        C."DMA  传送结束"属于中断        D."存储保护错"属于异常

        解答：A

        A 属于异常

        23.下列关于批处理系统的叙述中，正确的是_____。

        I.批处理系统中允许多个用户于计算机直接交互

        II.批处理系统分为单道批处理系统和多道批处理系统

        III.中断技术使得多道批处理系统的 I/O 设备可与 CPU 并行工作

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

        解答：A

        批处理系统：用户将一批作业提交给操作系统后就不再干预，由操作系统控制他们自动运行。

        I.批处理系统不具有交互性

        II. 单道批处理系统：将一批作业依次执行。多道批处理系统：内存中同时存放多个作业，按照一定的算法选择作业执行。

        III，中断技术，CPU中止正在执行的程序转去执行特殊事件的操作。

        24.某单 CPU 系统中由 输入和输出设备各 1 台，现有 3 个并发执行的作业，每个作业的输入、计算和输出时间分别为 2ms、3ms 和 4ms，且都按照输入、计算和输出的顺序执行，则执行完 3 个作业需要的时间至少是_____。

        A.15ms        B.17ms        C.22ms        D.27ms

        解答：B

        作业 1 执行完需要2ms+3ms+4ms=9ms，作业2需要额外的4ms，作业 3 需要额外的 4ms，因此至少需要 9ms+4ms+4ms=17ms

        25.系统中有 3 个不同的临界资源 R1，R2 和 R3，被四个进程 p1，p2，p3 和 p4 共享。各进程对资源的需求分别是:p1 申请R1 和 R2，p2申请R2 和 R3，p3 申请 R1 和 R3，p4 申请 R2。若系统出现死锁，则处于死锁状态的进程数至少是_____.

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

        解答：C

        p1 占有 R1，p2 占有 R2，p3 占有 R3

        26.某系统采用改进 CLOCK 置换算法，页表项中字段 A 为访问位，M 为修改位。A=0 表示页最近没有被访问过，A=1表示 页最近被访问过。M=0 表示页没有被修改过，M=1 表示页被修改过，按（A,M）所有可能取值，将页分为 4 类：（0，0），（0，1），（1，0），（1，1），则该算法淘汰页的次序是______.

        A.（0，0），（0，1），（1，0），（1，1）

        B.（0，0），（1，0），（0，1），（1，1）

        C.（0，0），（0，1），（1，1），（1，0）

        D.（0，0），（1，1），（0，1），（1，0）

        解答：A

        CLOCK置换策略，将所有页面按顺序排成一个圆形队列，顺时针移动指针，若访问位为0，替换该页；若访问位为 1， 将其置为0 ，并将指针移动到下一个页面。

        27.使用 TSL （Test and Set Lock）指令实现进程互斥的伪代码如下：

do{
...
while(TSL(&Lock)) ;
critical section;
lock=FALSE;
...
 
}while(true);

        下列与该实现机制相关的叙述中，正确的是_____。

        A.退出临界区的进程负责唤醒阻塞态进程

        B.等待进入临界区进程不会主动放弃 CPU        

        C.上述伪代码满足“让权等待”的同步原则

        D.while(TSL(&Lock))语句应该在关中断的情况下执行

        解答：B

        退出临界区的进程会唤醒就绪 态进程而不是阻塞态进程。

        等待进入临界区的进程会一直执行 while(TSL(&Lock))，不会放弃CPU，正确。

        让权等待，当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。在本程序中，进程不会放弃CPU，因此不符合该原则。

        关中断：进制处理机相应中断源的中断请求。若在关中断情况下执行，且长时间处于while(true) 状态，计算机系统可能出现问题。

        28.某进程的段表内容如下所示。

        当访问短号为 2，段内地址为 400的逻辑地址时，进行地址转换的结果是_____。

        A.段缺失异常        B.得到内存地址 4400        C.越权异常        D.越界异常

        解答：D

        段长为 300，访问段内地址为 400 的逻辑地址，产生越界异常。

        段缺失异常，程序试图访问一个无限的内存地址或未分配的内存地址。

        29.某进程访问页面的序列如下所示。

            若工作集的大小为 6，则t 时刻的工作集为______.

        A.{6,0,3,2}        B.{2,3,0,4}        C.{0,4,3,2,9}        D.{4,5,6,0,3,2}

        解答：A

        包含最近 k 次内存访问所访问过的页面。最近 6 次访问过的是 {6,0,3,2,3,2}，因此工作集为{6,0,3,2}.

        30.进程 P1 和 P2 均包含并发执行的线程，部分伪代码描述如下。

//进程 P1
int x=0;
Thread 1(){
    int a;
    a=1;
    x+=1;
}
Tread 2(){
    int a;
    a=2;
    x+=2;
}
 
//进程 P2
int x=0;
Thread3(){
    int a;
    a=x;
    x+=3;
}
 
Thread4(){
    int b;
    b=x;
    x+=4;
}

        下列选项中，需要执行互斥操作的是_______。

        A.a=1 与 a=2        B.a=x 与 b=x        C.x+=1 与 x+=2        D.x+=1 与 x+=3

        解答：C

        C项二者属于同一个进程且可能互相干扰，因此需要执行互斥操作。

        31.下列关于 SPOOLing 技术的叙述中，错误的是_______。

        A.需要外存的支持               

        B.需要多道程序设计技术的支持

        C.可以让多个作业共享一台独占设备

        D.由用户作业控制设备与输入/输出井之间的数据传送

        解答：D

        SPOOLing 技术是外部设备联机并行操作的一种技术，通常称为"假脱机技术"。SPOOLing 技术利用专门的外围控制机，将低速 I/O 设备上的数据传送到高速磁盘上，或者相反。

        高速磁盘即外存，A正确。

        SPOOLing 技术需要进行输入/输出操作，单道批处理系统无法满足（单道批处理系统在内存中以脱机方式输入/输出数据，没有专门的控制程序来管理输入输出操作），B正确。

        SPOOLing 技术实现了将独占设备改造成共享设备的技术。C正确

        由系统控制设备与输入/输出井之间的数据传送，D错误。

        32.下列关于管程的叙述中，错误的是______.

        A.管程只能用于实现进程互斥

        B.管程是由编程语言实现的进程同步机制

        C.任何时候只能有一个进程在管程中执行

        D.管程中定义的变量只能被管程内的变量访问

        解答：A

        管程是一种封装共享资源访问的方式，通过信息隐藏和同步操作来提高并发编程的效率和安全性。

        题 33~41 均依据题 33~41 图回答。

        33.在 OSI 参考模型中，R1，Switch，Hub 实现的最高功能层分别是_______。

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

        解答:C

        R1 是路由器,工作在网络层, 从下往上 第三层.

        Switch 是交换机,工作在数据链路层,从下往上第 2 层.

        Hub 是集线器,工作中物理层,最下面一层.

        34.若连接 R2 和 R3 链路的频率带宽为 8kHz,信噪比为 30dB,该链路实际传输速率约为理论最大值的 50%,则该链路的实际数据传输速率约是______.

        A.8kbps        B.20kbps        C.40kbps        D.80kbps

        解答:C

        香农定理:在随机热噪声的信道上传播数据时,数据传输速率 Rmax与信道带宽B,信噪比 S/N (即信号的功率/噪声的功率,无单位) 关系为: 

        信噪比通常用分贝表示,此时 分贝数=10∗log10(S/N)

        当信噪比为 30dB时, 由30=10*log10 (S/N) 得到 S/N=1000,此时 Rmax=8k*log2(1+30)=8k*lo2(1000) 约为80kbps,其一半为 40kbps,故选C.

        35.若主机 H2 向主机 H4  发送一个数据帧,主机 H4 向主机 H2 立即发送一个确认帧,则除 H4 外,从物理层上还能收到该确认帧的主机有______.

        A.H2        B.H3        C.H1,H2        D.H2,H3

        解答:D

        H4 的确认帧发往集线器后,集线器会直接广播该帧,因此 H3 会收到该帧.该帧发往交换机后,因H2 已向 H4 发送过一个帧(即知道H2 的MAC地址),故直接转发即可.

        36.若 Hub 再生比特流过程中,会产生 1.535us 的延时,信号传播速度为 200m/us, 不考虑以太网的前导码,则 H3 和 H4 的理论最远距离为______.

        A. 200m        B.205m        C.359m        D.512m

        解答:B

        Hub 为100Base-T集线器,因此传输速率为 100Mbps.

        以太网规定的最短帧长为 64B,对于 100Mbps 的网络,争用期(端到端往返时延 RTT 和Hub 产生时延)为 (8b*64)/100=5.12us,则 单项传播时延为5.12us/2-1.535us=2.56us-1.535us=  1.025us, 则理论最远距离为 1.025*200m=205m

        37.假设 R1,R2,R3 采用RIP 协议交换路由信息,且均已收敛.若 R3 检测 到网络 201.1.2.0/25 不可达,并向  R2 通告依次新的距离向量,则 R2 更新后,其到达该网络的距离为_____.

        A.2        B.3        C.16        D.17

        解答:B

        RIP 协议的距离更新是通过定期广播整个路由表实现的.

        R3 检测到网络 201.1.2.0/25 不可达, R2将其距离设置为 16,并广播.此时 R2 收到 2 张路由表(R3 显示 该网络不可达, R1 上该网络的距离为 2) 此时 R2 上网络 201.1.2.0/25 的距离为 2, 下一跳为 R3, 需要更新, 取 R1 ,R2 中距离较小者 +1 ,为 3.

        38.假设连接 R1,R2 和 R3之间的点对点链路使用 201.1.3.x/30 地址,当 H3 访问Web 服务器 S 时,R2 转发出去的封装 HTTP 请求报文的 IP 分组的源 IP 地址和目的 IP 地址分别是_____.

        A.192.168.3.251 和 130.18.10.1        B.192.168.3.251 和 201.1.3.9

        C.201.1.3.8 和130.18.10.1                D.201.1.3.10 和130.18.10.1

        解答:D

        192.168. 开头是c 类私有地址,所以需要转换源地址. 201.1.3.x/30 只有 2 位表示主机,全 0和全 1 不能用, 201.1.3.8 最后两位全 0,故 选D.

        39.若 H1 和 H2 的默认网关和子网掩码分别配置为 192.168.3.1 和255.255.255.128, H3 和 H4 的默认网关 和子网掩码分别配置为 192.168.3.254 和255.255.255.128 ,则下列现象中可能发生的是______.

        A. H1 不能和 H2 进行正常 IP 通信        B.H2 与 H4 均不能访问 Internet

        C.H1 不能与 H3 正常通信                     D.H3 不能与 H4 进行正常通信

        解答:C

        A项. 由默认网关和子网掩码(子网) 可知,H1 和 H2 处于同一网段,故 H1 和 H2 可以正常通信.

       B项, H1 和 H2 的默认网关配置错误,因此 H2 不能访问Internet. H4 的默认网关配置无误,可以正常访问 Internet. 

        C项,由默认网关和子网掩码(子网) 可知, H1 和 H3处于不同的网段,需要通过路由器通信,但是 H1 的默认网关配置有误,因此不能正常通信.

        D项, 由默认网关和子网掩码(子网) 可知,H3 和 H4 处于同一网段,故 H3 和 H4 可以正常通信

        40.假设所有域名服务器均采用迭代方式进行域名解析.当 H4 访问规范域名为 www.abc.xyz.com 的网站时,域名服务器 201.1.1.1 在完成该域名解析的过程中,可能发出 DNS 查询的最少和最多次数分别是_____

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

        解答:B

        若本机高速缓存中存在该域名, DNS 查询次数最少为 0.

        在最坏情况下,分别有存在向 本地域名服务器,根域名服务器(.com),顶级域名服务器(xyz.com),权限域名服务器(abc.xyz.com) 服务器发出的 DNS 查询.最多 4 次.

      

        

        

        

        二、综合应用题

        41.假设题 33~41 图中的 H3 访问Web 服务器 S 时，S 为新建的 TCP 连接分配了 20KB（K=1024） 的接收缓存，最大段长 MSS=1KB，平均往返时间 RTT=200ms。H3 建立连接时的初始序号为 100，且持续以 MSS 大小的段向 S 发送数据，拥塞窗口初始阈值 为 32 KB，S 对收到的每个段进行确认，并通告新的接收窗口。假设 TCP 连接建立完成后，S 端的 TCP 接收缓存仅有数据存入而无数据取出。请回答一下问题：

        （1）在 TCP 建立阶段，H3 收到的 S 发送过来的第二次握手 TCP 段的 SYN 和 ACK 是多少？确认号是多少？

        （2）H3 收到的第 8 个确认段所通告的接收窗口是多少？此时  H3 的拥塞窗口是多少？H3 的发送窗口变为多少？

        （3）当  H3 的发送窗口等于0 时，下一个待发送的数据段序号是多少？H3 从发送的第一个数据段到发送窗口大小为0 时刻为止，平均数据传输速率是多少？（忽略段的传输时延）

        （4）若  H3 和 S 之间的通信已结束，在 t 时刻 H3 请求，断开该连接，则从 t 时刻起，S 释放该链接的最短时间是多少？

        解答：（1）SYN=0，ACK=1，确认号为 101（TCP握手阶段消耗一个序号，但不携带数据）

        （2）根据满开始规则，前 8 个确认段递增 1，因此 第 8 个TCP段的大小为 8KB，通告的接收窗口大小为12KB。

        第 8 个TCP段的大小仍未超过32KB，因此 H3 的拥塞窗口变为 9KB。

        H3 的发送窗口为拥塞窗口和接收窗口中的较小者，为 9KB。

        （3）当 H3 的发送窗口等于 0 时，将 20 个段发给了 S，第一个段的序号为 100，因此下一个待发送的数据段序号为 101+20*1024=20580.（TCP 建立连接阶段，H3 第一次发送的报文消耗一个序号，第二次发送的报文不消耗序号）

        从 H3 发送第一个数据段到发送窗口大小为 0 为止，一共发送了 20KB的数据，经过 5 个传输轮次（后几个传输轮次中，每次传输多个数据报，且每个数据报都会使拥塞窗口大小加一，因此 每个轮次中传输的数据报数量为 1，2，4，8，5），消耗 5*200ms，因此平均传输速率为 20KB/1000ms=20KBps

        （4）TCP 四次挥手，最多经过 1.5 个RTT即 300ms 就断开。

        42.如果一颗非空（k>=2）叉树T 中每个非叶子节点都有 k 个孩子，则 T 称为 正则 k 叉树。请回答一下问题并给出推导过程。

        （1）若 T 有 m 个非叶节点，则 T 中叶节点的个数是多少？

        （2）若  T 的高度是 h（单节点高度为1），则 T 的节点最多有多少个？最少为多少个？

        解答：（1）假设正则 k 叉树有 x 个叶节点，则树中节点总数 为 m+x，树中所含边数为 m+x-1。正则 k 叉树每个节点的的子节点均有 k 个孩子，因此树种边树又可表示为 m*k。因此 m*k=m+x-1，解的 x=m*(j-1)+1.

        （2）当其为满二叉树时节点个数最多，为 1+k+k^2+....+k^h=(1-k^n)/(1-k)。当除最后一层外，每层非叶子节点数量为 1 时，节点数量最少，为 1+k+k+...+k=1+(h-1)k.

        

        43.已知由n（n>=2） 个正整数构成的集合 A={ak|0<=k

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

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

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

        解答：（1）基于快速排序的思想对 A 进行排序使得 A 的有序序列中前 n/2-1 （向下取整）个元素全部在 第 n/2 个元素左边，其余元素全在第 n/2 个元素右边。

        （2）

class Solutin{
public：
    vector<vector<int>> func(vector A){
        vector<int> A1;
        vector<int> A2;
        int left=0;
        int right=A.size();
        int target=left+(right-left)/2-1;    //n/2 所在的位置
        while(left<=right){
            int stand=left;        //划分枢纽
            for(int i=stand+1;i<right;i++){
                if(A[i]<A[stand]){        //该元素小于基准元素，需移至目标元素左边
                    int temp=A[i];
                    A[i]=A[stand];
                    A[stand]=A[i+1];
                    A[i+1]=temp;
                    stand++;
                }
            }
            if(stand==target){            //根据枢纽新的位置确定是否及如何缩减区间
                break;
            }else if(stand<target){
                left=stand+1;
            }else{
                right=stand-1;
            }
        }
        for(int i=0;i<target;i++){        //将前target个元素放入A1中
            A1.push_back(A[i]);
        }
        for(int i=target;i<A.size();i++){    //将其余元素放入A2中
            A2.push_back(A[i]);
        }
        vector<vector<int>> res;            //将 A1，A2 放在一起返回
        res.push_back(A1);
        res.push_back(A2);
        return res;
    }
 
}

           （3）只需遍历 2 次数组，因此时间复杂度为 O(n)；需要使用 O(n) 的额外空间存放 A1 和 A2 作为结果返回，因此空间复杂度为 O(n)。

        44.假定 CPU 主频为 50MHz，CPI 为 4。设备  D 采用异步串行通信方式向主机传送 7 位 ASCII 字符，通信规程中有 1 位奇校验位和 1 位停止位，从 D 接收启动命令到字符送入 I/O 端口需要 0.5ms。请回答一下问题，要求说明理由。

        （1）每传送一个字符，在异步串行通信线上共需传输多少位？在设备 D 持续工作过程中，每秒钟最多可向 I/O 端口送入多少个字符？

        （2）设备 D 采用中断方式进行输入/输出，示意图如下。

        I/O 端口每收到一个字符请求一次中断，中断响应需要 10 个时钟周期，中断服务程序共有 20 条指令，其中第 15 条指令是启动 D 工作。若 CPU 需从 D 读取 1000 个字符，则完成这一任务所需时间大约是多少个时钟周期？CPU 用于完成这一任务的时间大约是多少个时钟周期？在中断响应阶段 CPU 进行了哪些操作？

        知识点：异步串行通信方式：通信系统的发送与接收设备均使用各自的时钟控制数据的接收与发送。串行指数据一位一位地传输。

        解答：（1）10 位，1 位起始位，7位 ASCII 字符，1 位奇偶校验位和  1 位停止位。

        每秒钟最多接收 1000ms/0.5ms=2000 个字符

        （2）每秒钟读取 2000个字符，因此读取 1000 个字符需要 0.5ms，CPU 主频位 50M hz，因此 1000 个字符的读取需要 0.5*50M =25000000 个时钟周期；每次中断响应需要 10 个时钟周期，1000 个字符需要 10000 个时钟周期；中断 服务程序有 20 条指令，前 15 条用于传送，计算机 CPI 为 4，因此单个字符需要 15*4=60 个时钟周期，1000个字符徐奥 60000个时钟周期。综上所述，传送 1000 个字符一共需要 25000000+60000+10000=25070000 个时钟周期。

        由图可知，CPU 仅在中断响应和执行中断服务程序时参与该任务，因此 CPU 大约消耗  10000+20*4*10000=90000 个时钟周期。

        在中断响应阶段，CPU 主要进行如下操作：关中断，保护端点和程序状态，识别中断源。

        45.某计算机采用页式存储管理系统，按字节编址，虚拟地址为 32 位，物理地址位 24 位，页大小为 8KB；TLB 采用全相连映射；Cache 数据区大小为 64KB，按二路组相联方式组织，主存块大小为 64B。存储访问过程如下所示：

        

        请回答以下问题：

        （1）图中字段 A~G 的位数各是多少？ TLB 标记字段 B 中存放的是什么信息？

        （2）将块号为 4099 的主存块装入 Cache 中，所映射的 Cache 组号是多少？对应的  H 字段是多少？

       （3）Cache 缺失处理时间的开销大还是缺页处理时间开销大？为什么？

       （4）为什么 Cache 可以采用直写（write through）策略，而修改页面内容时总是采用回写（write back）策略？

        知识点：AE-标记        F-块号        G-块内地址

        解答：（1）页大小为 8 KB=2^13B ，按字节编址因此页内地址占 13 位，即 D 有 13 位。虚拟地址 32 位，因此 A 有 32-13=19 位，B 也有 19 位；物理地址 有 24 位，D=13，因此 C=24-13=11；主存块大小位 64B=2^6B，因此 G 有 6 位； Cache 数据区大小为 64KB，采用二路组相连，主存块大小为 64B，因此 Cache 有 64KB/（64B*2）=2^9 组，即 H 有 9 位，因此F 也有 9位；E+F+G=24，因此 E=H=24-F-G=24-9-6=9

        综上，A=19 ，B=19，C=11，D=13，E=9    F=9，G=6

        TLB 标记字段 B 的内容是虚页号，表示该TLB 项对应的是那个虚页的页表项。

        （2）Cache 共有 512 组，块号为 4099，4099/512=8......3，因此映射的 Cache 组号是3 ，对应的 H 字段为 0 0000 1000B.

        （3）缺页处理开销大。Cache 缺失时访问的是 主存，缺页时访问的是磁盘。

        （4）数据更新写 Cache 需要写 Cache 和主存，而修改页面时要写主存和磁盘。写磁盘的访问速度比写主存慢很多，而相较而言，写主存和写Cache 相差不大，因此 Cache 可以采用直写（write through）策略，而修改页面内容时总是采用回写（write back）策略。

  46.某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数较小的进程运行，进程创建时由用户指定一个 nice 作为静态优先数。为了动态调整优先数，引入运行时间  cpuTime 和等待时间 waitTime，初值均为 0.进程处于执行态时，cpuTime 定时加一，且 waitTime 置 0；进程处于就绪态时，cpuTime 置 0，waitTime 定时加一。请回答以下问题：

        （1）若调度程序只将nice 的值作为进程的优先数，即 priority=nice，则可能会出现饥饿状态，为什么？

        （2）使用 nice，cpuTime 和 waitTime 设计一种动态优先数计算方法，以避免产生饥饿现象，并说明 waitTime 的作用？

        解答：（1）因为若priority=nice，因为对于优先数较大的进程而言，队列中可能一直存在优先数小于其优先值得进程。

        （2）令 priority=nice+k1*cpuTime-k2*waitTime，（k1>0,k2>0）。对于每一个进程，指定一个 k1 和 k2。cpu 每隔一定时间检查所有进程的 priority，优先执行 priority 最小的进程。

        waitTime 的作用是记录进程等待时间，提高等待时间长的进程的优先级别，避免进程等待时间过长产生饥饿现象

        47.某磁盘文件系统使用链接分配方式组织文件，簇大小为 4KB。目录文件的每个目录项包括文件名和文件的第一个簇，其他簇号存放在文件分配表 FAT 中。

        （1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中 dir，dir1 是目录，file1，file2 是用户文件。请给出所有目录文件的内容。

        

        （2）若 FAT 的每个表项仅存放簇号，占 2 字节，则 FAT 的最大长度是多少？该文件系统支持的文件长度最大是多少？

        （3）系统通过目录文件和 FAT 实现对文件的按名存储，说明 file1 的 106，108 两个簇号分别存放在 FAT 的哪个表项中。

        （4）假设仅 FAT 和 dir 目录文件读入内存，若需将文件 dir/dir1/file1 的第 5000 个字节读入内存，需要访问哪几个簇？

        知识点：FAT 的表项

        解答：（1）dir 目录中有 1 个目录 dir1,簇号是 48. 

        dir1 目录中有 2 个用户文件 file1 和 file2，file1 簇号为 100. file2 簇号为 200.

        （2）FAT 的表项为 2 字节即 16位，因此在 FAT 表中最多允许 2^16（65536）个表项，每个表项仅存放簇号且一个 簇号大小为 2B ，因此FAT 的最大长度为 2^16*2B=2^7KB=128KB

        每个簇的大小是4KB，因此文件的最大长度为 2^16 *4KB=256MB

        （3）FAT 的每个表项存放在上一个表项的簇中，因此 106 存放在簇号为 100 的表项中，108 存放在簇号为 106 的表项中。

        （4）首先在 dir 文件读取 dir1 的簇，接着在 dir1 中读取 file1 的第一个簇号，然后 file1 中寻找第 5000 个字节所在的簇号，最后访问磁盘中的该簇，因此需要访问目录文件 dir1 所在的 48 好簇，以及文件 file1 的 106 号簇（每一个簇的大小是 4KB即1024*4=4096。因此第 5000 个字节在第二个簇即 106 号簇中）。