假设主机H 通过HTTP/1.1 请求浏览某Web服务器S 上的Web 页 news408.html,news408.. html引用 了同目录下的1幅图像，news408.html 文件大小为1 MSS (最大段长),图像文件大小为3MSS,H 访 问 S的往返时间RTT=|0ms, 忽略HTTP 响应报文的首部开销和TCP 段传输时延。若H 已完成域名解 析，则从H 请求与S 建立TCP 连接时刻起，到接收到全部内容止，所需的时间至少是()。

A. 30ms C. 50ms D.60ms

[tag_link]

正确答案：B

HTTP/1.1 默认使用流水线的 长连接 ，所有请求都是连续发送的。

题目要求最少 时间，最理想的流程是 TCP 在第三次握手的报文段中捎带 HTTP 请求，以及 TCP 连接后慢开 始阶段不考虑拥塞情况。

假设接收方有足够大的缓存空间，即发送窗口等同于拥塞窗口，总 共需要经过：第 1 个 RTT，进行 TCP 连接，此时服务器 S 的发送窗口= 1MSS，并在第三次 握手时捎带 HTTP 请求；

第 2 个 RTT，服务器 S 发送大小为 1MSS 的 html 文件，主机 C 确认 后服务器 S 的发送窗口变为 2MSS；

第 3 个 RTT，服务器 S 发送大小为 2MSS 的图像文件， 主机 C 确认后服务器 S 的发送窗口变为 4MSS；

第 4 个 RTT，服务器 S 发送剩下的 1MSS 图 像文件，完成传输，总共需要 4 个 RTT，即 40ms。

解答题 数据结构 41 已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下： typedef struct { // MAX_SIZE 为已定义常量 Elemtype SqBiTNode [ MAX_SIZE ]; // 保存二叉树结点值的数组 int ElemNum ; // 实际占用的数组元素个数 } SqBiTree ; T 中不存在的结点在数组 SqBiTNode 中用 -1 表示。

例如，对于下图所示的两棵非空二叉树 T1 和 T2： 40 25 80 30 27 40 50 60 35 30 60 二叉树 T1 二叉树 T2 T1 的存储结果如下： 40 25 60 -1 30 -1 80 -1 -1 27 T1.SqlBiTNode T1.ElemNum = 10 T2 的存储结果如下： 40 50 60 -1 30 -1 -1 -1 -1 -1 T2.SqlBiTNode T2.ElemNum = 11 35 请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回 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）算法实现 // val 存储中序遍历中访问到的最大值 // 返回值：当前子树是否为 BST bool solve ( SqBiTree * tree , int k , int * val ) { if ( k >= tree -> ElemNum ) { // 空结点 return true ; } // 判断左子树是否为 BST bool ret = solve ( tree , 2 * k + 1 , val ); if ( ! ret ) { return false ; } int cur_val = tree -> SqbiTNode [ k ]; if ( cur_val == - 1 ) { // 空结点 return true ; } // 判断中序序列是否递增 if ( cur_val > * val ) { * val = cur_val ; } else { return false ; } // 判断右子树是否为 BST ret = solve ( tree , 2 * k + 2 , val ); if ( ! ret ) { return false ; } return true ; }