注：以下习题参考 计算机网络（第八版）谢希仁 编著，数据结构与算法 王曙燕 主编。

一、计算机网络第6章 应用层（上） 习题与解答

---

6-01 互联网的域名结构是怎样的？它与目前的电话网的号码结构有何异同之处？

答案：

域名结构：采用层次树状结构，由标号序列组成，标号之间用点“.”分隔，如 www.example.com。顶级域（如 com、edu、cn）→ 二级域 → 三级域 → ...，每个标号不超过 63 字符，总长度不超过 255 字符。

与电话号码结构的异同：

• 相同点：都是层次结构（电话：国家区号→城市区号→本地号码；域名：顶级域→二级域→...）

• 不同点：

  • 域名是面向人的、按组织/性质划分；电话号码是面向地域的

  • 域名从左到右范围由小到大；电话号码从左到右范围由大到小

  • 域名长度不固定；电话号码长度相对固定

---

6-02 域名系统的主要功能是什么？域名系统中的本地域名服务器、根域名服务器、顶级域名服务器以及权限域名服务器有何区别？

答案：

主要功能：将域名解析为 IP 地址，实现主机名到 IP 地址的映射。

四种域名服务器区别：

类型	作用
本地域名服务器	用户主机直接查询的服务器，负责代理域名解析
根域名服务器	顶级域名服务器的顶级，知道所有顶级域名服务器的 IP
顶级域名服务器	管理某个顶级域（如 .com）下的所有二级域名
权限域名服务器	负责某个具体域的权威解析（如 example.com）

---

6-03 举例说明域名转换的过程。域名服务器中的高速缓存的作用是什么？

答案：

转换过程（以 www.example.com 为例）：

1. 主机向本地域名服务器查询

2. 本地服务器向根服务器查询

3. 根服务器返回 .com 顶级服务器地址

4. 本地服务器向 .com 服务器查询

5. .com 服务器返回 example.com 权限服务器地址

6. 本地服务器向权限服务器查询，得到 IP 地址

7. 本地服务器将结果返回主机

高速缓存作用：暂存最近查询的域名解析结果，减少重复查询，提高效率。

---

6-04 设想有一天整个互联网的 DNS 系统都瘫痪了（这种情况不太会出现），试问还有可能给朋友发送电子邮件吗？

答案：

可能，如果对方 IP 地址已知，直接使用 IP 地址发送；或通过本地 hosts 文件手动解析域名。但若完全依赖 DNS 且无备份，则无法发送。

---

6-05 文件传送协议 FTP 的主要工作过程是怎样的？为什么说 FTP 是带外传送控制信息的？主进程和从属进程各起什么作用？

答案：

工作过程：

1. 客户端与服务器端口 21 建立 TCP 控制连接

2. 客户端发送命令，服务器响应

3. 数据传输时，服务器与客户端建立数据连接（端口 20 或协商端口）

带外传送：控制信息（命令/响应）与数据分别用不同 TCP 连接传输，控制连接在整个会话期间保持，数据连接按需创建

主从进程：

• 主进程：负责接收新请求，创建从属进程

• 从属进程：负责处理单个用户的具体命令和数据传输

---

6-06 简单文件传送协议 TFTP 与 FTP 的主要区别是什么？各用在什么场合？

答案：

对比项	FTP	TFTP
运输层	TCP	UDP
认证	需要用户名/密码	无认证
功能	文件管理（列表、删除等）	仅文件传输
适用场合	交互式文件传输	无盘工作站启动、小文件传输

---

6-07 远程登录 TELNET 的主要特点是什么？什么叫作虚拟终端 NVT？

答案：

主要特点：用户通过网络远程登录到主机，仿佛在本地终端上操作；适应异构系统差异（操作系统、键盘等）

虚拟终端 NVT：一种中间标准格式，客户端将本地终端的字符转换为 NVT 格式发送，服务器将 NVT 格式转换为服务器格式输出

---

6-08 解释以下名词：WWW, URL, HTTP, HTML, CGI, 浏览器，超文本，超媒体，超链，页面，活动文档，搜索引擎。

答案：

名词	解释
WWW	万维网，基于互联网的信息服务系统
URL	统一资源定位符，标识资源的地址格式
HTTP	超文本传输协议，Web 数据传输协议
HTML	超文本标记语言，网页编写语言
CGI	通用网关接口，Web 服务器与后端程序的交互接口
浏览器	客户端软件，用于请求和渲染 Web 页面
超文本	包含超链接的文本
超媒体	超文本的扩展，包含多媒体信息
超链	从一个文档指向另一文档的引用
页面	Web 文档
活动文档	包含动态内容的文档（如 JavaScript、Flash）
搜索引擎	提供信息检索服务的 Web 系统

---

6-09 假定一个超链接从一个万维网文档链接到另一个万维网文档时，由于万维网文档上出现了差错而使超链接指向一个无效的计算机名字。这时浏览器将向用户报告什么？

答案：浏览器会报告 “无法解析域名” 或 “服务器未找到”（404 Not Found）（类似 DNS 解析失败错误）。

---

6-10 假定要从已知的 URL 获得一个万维网文档。若该万维网服务器的 IP 地址开始并不知道。试问：除 HTTP 外，还需要什么应用层协议和运输层协议？

答案：

• 应用层协议：DNS（解析域名）

• 运输层协议：UDP（DNS 通常用 UDP）和 TCP（HTTP 用 TCP）

---

6-11 你所使用的浏览器的高速缓存有多大？请进行一个实验：访问几个万维网文档，然后将你的计算机与网络断开，然后再回到你刚才访问过的文档。你的浏览器的高速缓存能够存放多少个页面?

（此题为实验题，无标准答案，需实际测试）

---

6-12 什么是动态文档？试举出万维网使用动态文档的一些例子。

答案：

动态文档：服务器根据请求动态生成的文档（非预存静态文档）

例子：搜索引擎结果页面、网上购物车页面、实时股票行情、个性化推荐页面

---

6-13 浏览器同时打开多个 TCP 连接进行浏览的优缺点如何？请说明理由。

答案：

• 优点：并行下载多个对象，缩短页面加载时间

• 缺点：消耗更多网络资源（带宽、连接数），服务器负载增加；可能触发拥塞控制

---

6-14 请判断以下论述的正误，并简述理由。

(1) 用户点击某网页，该网页有 1 个文本文件和 3 张图片。此用户可以发送一个请求就可以收到 4 个响应报文。

错误。每个对象通常需要一个单独的 HTTP 请求（除非使用流水线或多路复用）。

(2) 有以下两个不同的网页：www.abc.com/html 和 www.abc.com/m2.html。用户可以使用同一个 HTTP/1.1 持续连接传送这两个网页的请求和响应。

正确。持续连接允许同一 TCP 连接发送多个请求/响应。

(3) 在客户端与服务器之间进行非持续连接，只需要用一个 TCP 报文段就能够装入两个不同的 HTTP 请求报文。

错误。非持续连接每个 TCP 连接只发一个请求，收到响应后关闭。

(4) 在 HTTP 响应报文中的主体实体部分永远不会是空的。

错误。某些响应（如 304 Not Modified）没有实体主体。

---

6-15 假定你在浏览器上点击一个URL，但这个URL的IP地址以前并没有缓存在本地主机上。因此需要用 DNS自动查找和解析。假定要解析到所要找的 URL 的IP地址共经过n个 DNS服务器，所经过的时间分别为RTT1，RTT2 ,…, RTTn。假定从要找的网页上只需要读取一张很小的图片(即忽略这张小图片的传输时间)。从本地主机到这个网页的往返时间是 RTT。试问从点击这个URL 开始，一直到本地主机的屏幕上出现所读取的小图片，一共要经过多长时间?

答案：

T=(RTT1+RTT2+...+RTTn)+(RTTw+RTTw)

即 DNS 解析时间 + (TCP 连接 + HTTP 请求/响应) + 图片传输(忽略)。简化T=∑RTTi+2RTTw

---

6-16 在上题中，假定同一台服务器的 HTML 文件中又链接了三个非常小的对象。若忽略这些对象的发送时间，试计算客户点击读取这些对象所需的时间。

(1)没有并行TCP连接的非持续 HTTP;
(2)使用并行TCP连接的非持续HTTP;
(3)流水线方式的持续 HTTP。

答案：

(1) 无并行非持续 HTTP：RTT1+RTT2+...+RTTn+8RTTw

(2) 并行 TCP 连接的非持续 HTTP：RTT1+RTT2+...+RTTn+4RTTw

(3) 流水线持续 HTTP：RTT1+RTT2+...+RTTn+3RTTw

---

6-17 浏览器中的可选解释程序名称

答案：JavaScript 引擎、CSS 渲染引擎、PDF 阅读器插件、Flash（历史）、Java Applet（历史）、图片解码器（JPEG/PNG/GIF）

---

6-18 一个万维网网点有1000万个页面，平均每个页面有10个超链。读取一个页面平均要100ms。请问:要检索整个网点所需的最少时间是多少?

答案：至少需要读取所有页面：107×0.1=106107×0.1=106 秒 ≈ 11.6 天

---

6-19 搜索引擎可分为哪两种类型?各有什么特点?

答案：

• 全文检索型：基于关键词全文匹配（如 Google、百度）

• 目录型：人工分类目录（如早期 Yahoo）

---

6-20 试述电子邮件的最主要的组成部件。用户代理 UA 的作用是什么?没有 UA 行不行?

答案：

• 主要组成：用户代理 UA、邮件服务器、邮件传输协议（SMTP）、邮件访问协议（POP/IMAP）

• UA 作用：用户读写、发送、接收、管理邮件

• 没有 UA 不行：用户无法直接与邮件系统交互

---

6-21 电子邮件的信封和内容在邮件的传送过程中起什么作用?和用户的关系如何?

答案：

• 信封：包含收/发件人地址，用于邮件传输

• 内容：包含邮件标题、正文、附件等，供用户阅读

• 信封由 MTA 使用，内容由 UA 使用

---

6-22 电子邮件的地址格式是怎样的?请说明各部分的意思。

格式：username@domain（如 zhangsan@example.com）

• username：用户名/邮箱名

• domain：邮件服务器的域名

---

6-23 试简述 SMTP 通信的三个阶段的过程。

答案：

1. 握手/建立连接：客户端与服务器建立 TCP 连接（端口 25）

2. 邮件传送：MAIL FROM → RCPT TO → DATA 命令传送邮件内容

3. 关闭连接：QUIT 命令结束会话

---

6-24 试述邮局协议 POP的工作过程。在电子邮件中，为什么需要使用POP和SMTP这两个协议?IMAP与POP有何区别?

答案：

• SMTP：用于邮件发送和中继

• POP：用于从邮件服务器下载邮件到客户端（通常删除服务器邮件）

• IMAP：服务器端管理邮件，支持多文件夹、在线操作

区别：POP 是“下载”模型，IMAP 是“在线/离线访问”模型

---

6-25 MIME与SMTP的关系是怎样的?什么是 quoted-printable 编码和 base64 编码?

答案：

• SMTP：只支持 7 位 ASCII，不能直接传非文本

• MIME：扩展 SMTP，支持多媒体、非 ASCII、二进制文件

编码：

• quoted-printable：适合主要是 ASCII 的数据，用 = 后跟十六进制表示特殊字符

• base64：将任意二进制数据用 A–Z、a–z、0–9、+、/ 表示，每 3 字节编码为 4 个字符

---

二、数据结构第8章 查找（上） 习题与解答

---

一、单项选择题

(1) 在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与______数量级相当。

A. 顺序查找
B. 折半查找
C. 分块查找
D. 哈希查找

答案：B

解析：随机情况下，二叉排序树高度约为 O(log₂n)，与折半查找同数量级。

---

(2) 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是______。

A. (100, 80, 90, 60, 120, 110, 130)
B. (100, 120, 110, 130, 80, 60, 90)
C. (100, 60, 80, 90, 120, 110, 130)
D. (100, 80, 60, 90, 120, 130, 110)

答案：C

解析：C 选项的插入顺序导致树结构与 A、B、D 不同，需画图验证。

---

(3) 顺序查找适合于存储结构为______的线性表。

A. 散列存储
B. 压缩存储
C. 索引存储
D. 顺序或链式存储

答案：D

解析：顺序查找不要求数据有序，适用顺序表和链表。

---

(4) 如果要求用线性表既能较快地查找，又能适应动态变化的要求，则可采用______查找方法。

A. 分块查找
B. 顺序查找
C. 折半查找
D. 基于属性

答案：A

解析：分块查找结合索引和顺序查找，支持动态插入删除。

---

(5) 已知一个如下10个记录的表，其关键字序列为(2, 15, 19, 25, 30, 34, 44, 55, 58, 80)，用折半查找法查找关键字为55的记录，比较次数是______。

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

答案：C

解析：

• low=1, high=10, mid=5 → 30

• low=6, high=10, mid=8 → 55 ，共3次比较

---

(6) 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，该树共有______个结点。

A. 2^(k-1) - 1
B. 2^(k-1)
C. 2^(k-1) + 1
D. 2^k - 1

答案：D

解析：平衡因子全0 → 满二叉树，结点数 = 2^k - 1。

---

(7) 下面关于 m 阶 B 树说法正确的是______。

① 每个结点至少有 n 棵非空子树。
② 树中每个结点至多有 m-1 个关键字。
③ 所有叶子在同一层上。
④ 当插入一个数据项引起 B 树结点分裂后，树长高一层。

A. ①②③
B. ②③④
C. ②③
D. ③④

答案：C

解析：①错误（根结点除外）；④错误（不一定长高）。

---

(8) 哈希表的地址区间为 0~17, 哈希函数为 H(K) = K mod 17。采用线性探测法处理冲突，并将关键字序列 26, 25, 72, 38, 18, 59 依次存储到哈希表中，则元素 59 存放在哈希表中的地址为______。

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

答案：C

解析：

• 26→9，25→8，72→4，38→4→5，18→1，59→8→9→10

---

(9) 设有一组记录的关键字为 {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，用链地址法构造散列表，散列函数为 H(key)=key mod 13，散列地址为1的键中有______个记录。

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

答案：D

解析：地址1的关键字：14, 27, 53？无53；实际14(1), 27(1), 40? 没有。需重新计算：
14 mod13=1, 1 mod13=1, 27 mod13=1, 79 mod13=1 → 4个

---

(10) B+树是______。

A. 一种 AVL 树
B. 索引表的一种组织形式
C. 一种高度不小于 1 的树
D. 一种与二进制 Binary 有关的树

答案：B

---

(11) 在一棵高度为 h 的 B 树中插入一个新关键字时，为查找插入位置需读取______个结点。

A. h-1
B. h
C. h+1
D. h+2

答案：B

(12) 一棵高度为h的AVL树，离根最远的叶结点在第__层。
A. h-1
B. h
C. h+1
D. 2^h-1

答案：B

---

二、填空题

(1) 对线性表进行折半查找时，要求线性表必须 ( 顺序存储且关键字有序 )。

(2) 在有 N 个元素的顺序表中顺序查找，等概率情况下查找成功的平均查找长度为 ( (N+1)/2 )。

(3) 在平衡二叉树中插入一个结点后造成了不平衡，该结点的平衡结点为 A，并已知 A 的左孩子的平衡因子为 0，右孩子的平衡因子为 1，则应做 ( RL ) 型调整。

(4) 哈希查找中 k 个关键字具有同一哈希值，若用线性探测将这 k 个关键字对应的记录存入哈希表中，至少要执行 ( k(k+1)/2 ) 次探测。

(5) 散列函数有一个共同的性质，即函数值应当以 ( 均匀 ) 取其值域中的每个值。

(6) 一棵高度为 h 的 AVL 树，若其每个非叶结点的平衡因子都是 0，则该树共有 ( 2^h - 1 ) 个结点。

---

三、简答题与应用题

(1) 已知一个有7个数据元素的有序顺序表,其关字为{3,18,25,37,69,87,99},请给出用折半查找方法查找关键字值18的查找过程。

答案：

• low=1, high=7, mid=4 → 37 > 18

• low=1, high=3, mid=2 → 18 ，比较2次

---

(2) 已知关键字序列 {53, 17, 19, 61, 98, 75, 79, 63, 46, 40}，构造二叉排序树。

答案：

                  53
              /          \
            17         61
               \            \
               19         98
                   \         /
                   46   75
                   /      /  \
                40    63 79

---

(3) 根据如图8-62所示的二叉排序树,给出删除关健字 88后的二叉排序树。

答案：

                  70
               /        \
             38        92
                \         /
                42    75
                /  \       \
             40  60   83
                           /
                         78

---

(4) 已知一组关键字序列 {5, 88, 12, 56, 71, 28, 33, 43, 93, 17}，哈希表长13，哈希函数 H（key）= key%13，请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表,并计算查找成功时的平均查找长度。

答案：

一、线性探测再散列

线性探测公式：

构造过程

key	H	冲突	最终地址	探测次数
5	5	无	5	1
88	10	无	10	1
12	12	无	12	1
56	4	无	4	1
71	6	无	6	1
28	2	无	2	1
33	7	无	7	1
43	4	冲突(4)	4→5(冲突)→6(冲突)→7(冲突)→8	5
93	2	冲突(2)	2→3	2
17	4	冲突(4)	4→5(冲突)→6(冲突)→7(冲突)→8(冲突)→9	6

最终哈希表（地址0~12）：

地址	0	1	2	3	4	5	6	7	8	9	10	11	12
key			28	93	56	5	71	33	43	17	88		12

平均查找长度 ASL（成功）

ASL=（1+1+1+1+1+1+2+5+6）/10=1.9

---

二、二次探测再散列

二次探测公式：

（先判断 H(key)，再依次 +1²,−1²,+2²,−2²,…）

构造过程

key	H	探测地址	最终地址	探测次数
5	5	5	5	1
88	10	10	10	1
12	12	12	12	1
56	4	4	4	1
71	6	6	6	1
28	2	2	2	1
33	7	7	7	1
43	4	4(冲突)→4+1=5(冲突)→4-1=3	3	3
93	2	2(冲突)→2+1=3(冲突)→2-1=1	1	3
17	4	4(冲突)→4+1=5(冲突)→4-1=3(冲突)→4+4=8	8	4

最终哈希表：

地址	0	1	2	3	4	5	6	7	8	9	10	11	12
key		93	28	43	56	5	71	33	17		88		12

ASL（成功）

ASL=（1+1+1+1+1+1+3+3+4）/10=1.6

---

三、链地址法

每个哈希地址是一个链表。

构造过程

key	H	插入链表
5	5	5: [5]
88	10	10: [88]
12	12	12: [12]
56	4	4: [56]
71	6	6: [71]
28	2	2: [28]
33	7	7: [33]
43	4	4: [56, 43]
93	2	2: [28, 93]
17	4	4: [56, 43, 17]

各链表长度及查找次数

地址	链表	查找次数（等概率、顺序查找）
0	空	0
1	空	0
2	28, 93	1+2=3
3	空	0
4	56, 43, 17	1+2+3=6
5	5	1
6	71	1
7	33	1
8	空	0
9	空	0
10	88	1
11	空	0
12	12	1

ASL（成功）

ASL=（3+6+1+1+1+1+1）/10=1.4

---

(5) 根据如图8-63所示的三阶B树,给出插人关键字93后的B树。

答案：                   

                                   [75, 90]
                       /                 |            \
                   [50]             [80]         [93]
                 /         \          /     \        /     \
           [12,40] [60,70] [77] [85]  [90]  [95]               

---

(6) 试推导含12个结点的平衡二叉树的最大深度,并画出一棵这样的树。

答案：深度 h=5（如斐波那契树）

---

(7) 试从空树开始,画出按以下次序向三阶B树中插人关键字的建树过程：20，30，50，52，60，70。如果此后删除50和70,画出每一步执行后三阶B树的状态

答案：

一、插入建树

1. 插入 20 → [20]

2. 插入 30 → [20, 30]

3. 插入 50 → 分裂，30 上移

    [30]
   /      \
[20]   [50]

1. 插入 52 → [50, 52]

2. 插入 60 → 分裂，52 上移

    [30, 52]
   /      |    \
[20] [50] [60]

1. 插入 70 → [60, 70]

最终：

     [30, 52]
   /      |       \
[20] [50] [60, 70]

---

二、删除 50

删除后合并调整：

        [30, 60]
       /       |      \
    [20]  [52]  [70]

---

三、删除 70

删除后：

       [30]
     /        \
  [20]   [52,60]

---

注：以上习题解答的理解和计算，如果有任何错误，希望各位读者和大佬指出改正，非常感谢！！！