计算机网络:

(9分)主机H登录FTP服务器后自服务器上估一个大小为18000B的文件F，假设H传输F建立数据连接时，选择的初始序号为100，MTU=1000B，拥塞控制初始闻值为4MSS，RTT=10ms，忽略TCP的传输时延，在F的传榆过程中，H以MSS段向服务器发送散据，且未发生差错、丢包和乱序。

(1)FTP的控制连接是持久的还是非持久的?FTP的数据连接是持久的还是非持久的?H登录FTP服务器时，建立的TCP连接是控制连持还是数据连接?

(2)H通过数据连接发送F时，F的第一个字节序号是多少?在断开数据连接的过程中，FTP发达的第二次挥手的ACK序号是?

(3)F发送过程中,当H收到确认序号为2101的确认段时，H的拥塞窗口调整为多少?收到确认序号为7101的确认段时，H的拥塞窗口调整为多少?

(4)H从请求建立数据连接开始，到确认F已被服务器全部接收为止，至少需要多长时间期间应用层数据平均发送速率是多少?

[

(13 分)已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct { //MAX_SIZE 为已定义常量 
 int SqBiTNode[MAX_SIZE]; //保存二叉树结点值的数组 
 int ElemNum; //实际占用的数组元素个数 
} SqBiTree;

T 中不存在的结点在数组 SqBiTNode 中用-1 表示。例如，对于下图所示的两棵非空二叉树 T1 和 T2，

T1 的储存结果如下：

T1.SqBiTNode

T2.ElemNum=10

T2 的储存结果如下：

T2.SqBiTNode

T2.ElemNum=11

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若 是，则返回 true，否则，返回 false。要求： 

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

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

【答案解析】 

【答案一】 

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

对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]；若有右孩子，则其值保 存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子 树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。 

使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数。若当 前遍历的结点值小于等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。 （2）算法实现 

#define false 0 
#define ture 1 
typedef int bool ; 
bool judgeInOrderBST( SqBiTree bt , int k , int * val )
 //初始调用时 k 的值是 0 
{ if ( k < bt.ElemNum && bt.SqBiTNode [k] ! = -1 )
{ 
 if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false; 
 if ( bt.SqBiTNode [k] <= * val ) return false; 
 * val = bt.SqBiTNode [k] ; 
 if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false;
 } 
 return ture; 
}

【答案二】 

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

对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在 SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值 保存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。 

二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子 树中的全部结点值。设置两个数组 pmax 和 pmin。根据二叉搜索树的定义，SqBiTNode[i]中 的值应该大于以 SqBiTNode[2i+1]为根的子树中的最大值（保存在 pmax[2i+1]中），小于以 SqBiTNode[2i+2]为根的子树中的最小值（保存在 pmin[2i+1] 中）。初 始 时， 用数 组 SqBiTNode 中前 ElemNum 个元素的值对数组 pmax 和 pmin 初始化。 

在数组 SqBiTNode 中从后向前扫描，扫描过程中逐一验证结点与子树之间是否满足上述 的大小关系。 

（2）算法实现

#define false 0 
#define ture 1 
typedef int bool ; 
bool judgeBST( SqBiTree bt ) 
{ int k , m , * pmin , * pmax ; 
 pmin = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ; 
 pmax = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ; 
 for ( k = 0 ; k < bt.ElemNum ; k++ ) //辅助数组初始化 
 pmin [k] = pmax [k] = bt.SqBiTNode [k] ; 
 for ( k = bt.ElemNum - 1 ; k > 0 ; k - - )
 //从最后一个叶结点向根遍历 
 { if ( bt.SqBiTNode [k] ! = -1 ) 
 { m = ( k - 1 ) / 2 ; //双亲 
 if ( k % 2 = = 1 && bt.SqBiTNode [m] > pmax [k] )
 //其为左孩子 
 pmin [m] = pmin [k] ; 
 else if ( k % 2 = = 0 && bt.SqBiTNode [m] < pmin
 [k] ) //其为右孩子
pmax [m] = pmax [k] ; 
 else return false ; 
} 
 } 
 return ture ;
}

（10 分）现有 n(n>100000)个数保存在一维数组 M 中，需要在查找 M 中最小的 10 个数。 请回答下列问题。 

（1）设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简述其算法 思想（不要程序实现）。

（2）说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

【答案解析】

（1）算法思想

【答案一】

定义含 10 个元素的数组 A，元素值均为该数组类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，数组 A 中保存的就是最小的 10 个数。

【答案二】

定义含 10 个元素的大根堆 H，元素值均为该堆元素类型能表示的最大数 MAX。

for M 中的每个元素 s

if（s

当数据全部扫描完毕，堆 H 中保存的就是最小的 10 个数。

（2）算法平均情况下的时间复杂度是 O（n），空间复杂度是 O(1)

（15 分）某 CPU 中部分数据通路如题 43 图所示，其中，GPRs 为通用寄存器组；FR 为标 志寄存器，用于存放 ALU 产生的标志信息；带箭头虚线表示控制信号，如控制信号 Read、 Write 分别表示主存读、主存写，MDRin 表示内部总线上数据写入 MDR，MDRout 表示 MDR 的内容送内部总线。 

请回答下列问题。 

（1）设 ALU 的输入端 A、B 及输出端 F 的最高位分别为 A₁₅、B₁₅ 及 F₁₅，FR 中的符号标志 和溢出标志分别为 SF 和 OF，则 SF 的逻辑表达式是什么？A 加 B、A 减 B 时 OF 的逻辑表达 式分别是什么？要求逻辑表达式的输入变量为 A₁₅、B₁₅及 F₁₅。

（2）为什么要设置暂存器 Y 和 Z？ 

（3）若 GPRs 的输入端 rs、rd 分别为所读、写的通用寄存器的编号，则 GPRs 中最多有多少 个通用寄存器？rs 和 rd 来自图中的哪个寄存器？已知 GPRs 内部有一个地址译码器和一个多 路选择器，rd 应连接地址译码器还是多路选择器？ 

（4)取指令阶段（不考虑 PC 增量操作）的控制信号序列是什么？若从发出主存读命令到主存 读出数据并传送到 MDR 共需 5 个时钟周期，则取指令阶段至少需要几个时钟周期？

（5）图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？

【答案解析】 

（1)SF =F₁₅；加运算时， 

减运算时，

（2）因为单总线结构中每一时刻总线上只有一个数据有效，而 ALU 有两个输入端和一个输 出端，因而需要设置 Y 和 Z 两个暂存器，以缓存 ALU 的一个输入端和输出端数据。 

（3）GPRs 中最多有 2⁴=16 个通用寄存器；rs 和 rd 来自指令寄存器 IR；rd 应连接地址译码 器。 

（4）取指阶段的控制信号序列为：①PCout，MARin ②Read ③MDRout，IRin。取指令阶段 至少需要 7 个时钟周期。 

（5）图中控制信号由控制部件（CU）产生。指令寄存器 IR 和标志寄存器 FR 的输出信号会 连到控制部件的输入端。

（8 分）假设某磁盘驱动器中有 4 个双面盘片，每个盘面有 20000 个磁道，每个磁道有 500 个扇区，每个扇区可记录 512 字节的数据，盘片转速为 7200r/m（转/分），平均寻道时间为 5ms。 请回答下列问题。 

（1）每个扇区包含数据及其地址信息，地址信息分为 3 个字段。这 3 个字段的名称各是什么？ 对于该磁盘，各字段至少占多少位？ 

（2）一个扇区的平均访问时间约为多少？ 

（3）若采用周期挪用 DMA 方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲 区大小为 64 位，则在一个扇区读写过程中，DMA 控制器向 CPU 发送了多少次总线请求？若 CPU 检测到 DMA 控制器的总线请求信号时也需要访问主存，则 DMA 控制器是否可以获得 总线使用权？为什么？

【答案解析】 

（1）3 个字段的名称为柱面号（或磁道号）、磁头号（或盘面号）、扇区号；该磁盘的柱面号、 磁头号、扇区号字段至少分别占⌈log₂20000⌉=15 位、⌈log₂（4×2）⌉=3 位、⌈log₂500⌉=9 位。 

（2）该磁盘转一圈的时间为 60×10³/7 200≈8.33ms，一个扇区的平均访问时间约为 5+8.33/2+8.33/500≈9.18ms。

（3）在一个扇区读写过程中，DMA 控制器向 CPU 发送了 512B/64b=64 次总线请求。DMA 控制器可以获得总线使用权。因为一旦磁盘开始读写就必须按时完成数据传送，否则会发生 数据丢失。

（7 分)某文件系统的磁盘大小为 4KB，目录项由文件名和索引节点号构成，每个索引节点 占 256 字节，其中包含直接地址项 10 个，一级、二级和三级间接地址项各 1 个，每个地址项 占 4 字节。该文件系统中子目录 stu 的结构如题 45（a）图所示，stu 包含子目录 course 和文 件 doc，course 子目录包含文件 course1 和 course2。各文件的文件名、索引节点号、占用磁盘 块的块号如题 45（b）图所示。

请回答下列问题。 

（1）目录文件 stu 中每个目录项的内容是什么？

（2）文件 doc 占用的磁盘块的块号 x 的值是多少？ 

（3）若目录文件 course 的内容已在内存，则打开文件 coursel 并将其读入内存，需要读几个 磁盘块？说明理由。 

（4）若文件 course2 的大小增长到 6MB，则为了存取 course2 需要使用该文件索引节点的哪 几级间接地址项？说明理由。

【答案解析】

（1）目录文件 stu 中两个目录项的内容是： 

（2）文件 doc 占用的磁盘块的块号 x 的值为 30。 

（3）需要读 2 个磁盘块。先读 course1 的索引节点所在的磁盘块，再读 course1 的内容所在 的磁盘块。 

（4）存取 course2 需要使用索引节点的一级和二级间接地址项。6MB 大小的文件需占用 6MB/4KB=1536 个磁盘块。直接地址项可记录 10 个磁盘块号，一级间接地址块可记录 4KB/4B=1024 个磁盘块号，二级间接地址块可记录 1024 × 1024 个磁盘块号，而 10+1024<1536<10+1024+1024×1024。

（8 分）某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作，其中 T1 执行 A、E 和 F，T2 执行 B、C 和 D。题 46 图表示上述 6 个操作的执行顺序所必须满足的约 束：C 在 A 和 B 完成后执行，D 和 E 在 C 完成后执行，F 在 E 完成后执行。请使用信号量的 wait( )、signal( )操作描述 T1 和 T2 之间的同步关系，并说明所用信号量的作用及其初值。

【答案解析】

（9 分）某网络拓扑如题 47 图所示，R 为路由器，S 为以太网交换机，AP 是 802.11 接入 点，路由器的 E0 接口和 DHCP 服务器的 IP 地址配置如图中所示；H1 与 H2 属于同一个广播 域，但不属于同一个冲突域；H2 和 H3 属于同一个冲突域；H4 和 H5 已经接入网络，并通过 DHCP 动态获取了 IP 地址。现有路由器、100BaseT 以太网交换机和 100BaseT 集线器（Hub） 三类设备各若干台。 

请回答下列问题。 

（1）设备 1 和设备 2 应该分别选择哪类设备？ 

（2）若信号传播速度为 2×10⁸m/s，以太网最小帧长为 64B。信号通过设备 2 时会产生额外 的 1.51μs 的时间延迟，则 H2 与 H3 之间可以相距的最远距离是多少？

（3）在 H4 通 DHCP 动态获取 IP 地址过程中，H4 首先发送了 DHCP 报文 M，M 是哪种 DHCP 报文？路由器 E0 接口能否收到封装 M 的以太网帧？S 向 DHCP 服务器转发的封装 M 的以太 网帧的目的 MAC 地址是什么？ 

（4)若 H4 向 H5 发送一个 IP 分组 P，则 H5 收到的封装 P 的 802.11 帧的地址 1、地址 2 和地 址 3 分别是什么？

【答案解析】 

（1）设备 1 选择 100BaseT 以太网交换机，设备 2 选择 100BaseT 集线器。 

（2）设 H2 与 H3 之间的最远距离是 D，根据 CSMA/CD 协议的工作原理有：

解得：D=210m。 

（3）M 是 DHCP 发现报文（DISCOVER 报文）；路由器 E0 接口能收到封装 M 的以太网帧； 目的 MAC 地址是 FF-FF-FF-FF-FF-FF。 

（4）H5 收到的帧中，地址 1、地址 2 和地址 3 分别是：00-11-11-11-11-E1、00-11-11-11-11- C1 和 00-11-11-11-11-D1。

软件生存周期一般可分为        、可行性研究、        、设计编码、        、运行与维护阶段。

按软件的功能进行划分，软件可以划分为        、        、和应用软件。

可行性研究主要集中在以下四个方面        、         、         和抉择。

用户界面的        是用户界面设计最重要的也是最基本的目标。

常见的软件概要设计方法有 3 大类：以数据流图为基础构造模块结构的        方法，以数据结构为基础构造模块的        方法，以对象、类、继承和通信为基础的        方法。

        和        共同构成系统的逻辑模型。

软件测试的方法有        和        (即黑盒法)。

单元测试一般以        测试为主，        测试为辅。

成本估计方法主要有        、        和算法模型估计三种类型。

什么是软件危机？为什么会产生软件危机？

[答案解析]

软件危机是指软件在开发和维护过程中遇到的一系统严重问题，主要包含二方面的问题，一是如何开发利用软件，二是如何维护数量不断膨胀的已有软件。产生软件危机的原因，一方面与软件本身的特点有关，另一方面和软件开发与维护的方法不正确有关。

耦合性有哪几种类型？其耦合度的顺序如何？

[答案解析]

低：非直接耦合→数据耦合→标记耦合→控制耦合→外部耦合→公共耦合→内容耦合：高

简述需求分析工作可以分成哪四个方面？

软件需求分析的有哪三个基本原则？

[答案解析]

需求分析阶段分成四个方面：对问题的识别、分析与综合、制定规格说明和评审。

三个基本原则：必须能够表达和理解问题的数据域和功能域；必须按自顶向下、逐步分解的方式对问题进行分解和不断细化；要给出系统的逻辑视图和物理视图。