考研复习 Day 34 | 习题--计算机网络 第六章（应用层 下）、数据结构 查找算法（下）

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

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

6-26 一个二进制文件共 3072 字节长。若使用 base64 编码，并且每发送完 80 字节就插入一个回车符 CR 和一个换行符 LF，问一共发送了多少个字节？

答案：4200 字节

解析：

• Base64 编码：3072 ÷ 3 = 1024 组，每组输出 4 字节 → 4096 字节

• 每 80 字节后插入 CR+LF（2 字节），最后一段 16 字节后也插入

• 插入次数 = ⌈4096 / 80⌉ = 52 次

• 总字节 = 4096 + 52 × 2 =4200 字节

6-27 试将数据 11001100 10000001 00111000 进行 base64 编码，并得出最后传送的 ASCII 数据。

答案：

• 编码结果：zIE4

• 对应的二进制代码：01111010 01001001 01000101 00110100

解析：

• 24 位数据按 6 位一组：110011、001000、000100、111000

• 十进制：51、8、4、56

• Base64 字符表：51→z、8→I、4→E、56→4

6-28 试将数据 01001100 10011101 00111001 进行 quoted-printable 编码，并得出最后传送的 ASCII 数据。这样的数据用 quoted-printable 编码后，其编码开销有多大？

答案：

• 编码后 ASCII 数据：01001100 00111101 00111001 01000100 00111001（对应 "L=9D9"）

• 编码开销：66.7%

解析：

• 0x4C（'L'）直接输出

• 0x9D（>127）→ =9D

• 0x39（'9'）直接输出

• 原 3 字节 → 编码后 5 字节，开销 = (5-3)/3 ≈ 66.7%

6-29 电子邮件系统需要将人们的电子邮件地址编成目录以便于查找。要建立这种目录应将人名划分为几个标准部分（例如，姓、名）。若要形成一个国际标准，那么必须解决哪些问题？

答案：

应划分的标准部分：姓、名、中间名、称呼/头衔

必须解决的问题：

1. 不同文化中姓名的先后顺序（西方：名在前姓在后；中国/日本：姓在前名在后）

2. 不同语言的字符集统一（Unicode）

3. 姓名中特殊字符的处理（连字符、空格、点号）

4. 重名消歧

5. 各式各样的头衔和称呼难以统一格式

6. 隐私保护

6-30 电子邮件系统使用 TCP 传送邮件。为什么有时我们会遇到邮件发送失败的情况？为什么有时对方会收不到我们发送的邮件？

答案：

发送失败原因：

• 对方的邮件服务器不工作或不可达

• 对方服务器拒绝接收（垃圾邮件过滤、黑名单）

• 邮件大小超过限制

• 收件人地址不存在

对方收不到原因：

• 对方的邮件服务器出故障，邮件丢失

• 邮件被误判为垃圾邮件放入垃圾箱

• 对方邮箱已满

• 邮件被中间中继服务器丢弃

6-31 基于万维网的电子邮件系统有什么特点？在传送邮件时使用什么协议？

答案：

特点：

• 无需配置邮件客户端，使用浏览器访问

• 邮件存储在服务器端，可从任何设备访问

• 界面统一，用户体验好

传送协议：

• 浏览器与 Web 服务器：HTTP/HTTPS

• Web 服务器与邮件服务器之间：SMTP和POP/IMAP

6-32 DHCP 协议用在什么情况下？当一台计算机第一次运行引导程序时，其 ROM 中有没有该主机的 IP 地址、子网掩码或某台域名服务器的 IP 地址？

答案：

DHCP 用途：计算机首次接入网络时，动态获取 IP 地址、子网掩码、默认网关、DNS 服务器地址等配置信息。

第一次引导时 ROM 中：

• 没有主机 IP 地址

• 没有子网掩码

• 没有域名服务器 IP 地址（可通过 DHCP 获取）

6-33 什么是网络管理？为什么说网络管理是当今网络领域中的热门课题？

答案：

网络管理：对网络设备（路由器、交换机、服务器等）进行监视、配置、故障诊断、性能分析和安全控制的统称。

热门原因：

• 网络规模爆炸式增长

• 网络复杂性增加（异构、虚拟化、云）

• 服务质量（QoS）要求提高

• 网络安全威胁加剧

• 自动化运维需求

6-34 解释下列术语：网络元素、被管对象、管理进程、代理进程。

答案：

6-35 SNMP 使用 UDP 传送报文。为什么不使用 TCP？

答案：

1. 简单性：UDP 无连接，实现简单，适合网络管理这种偶发性通信

2. 低开销：UDP 首部小，不占用过多网络资源

3. 不依赖连接：即使网络出现拥塞或故障，UDP 仍能发送告警（TCP 可能因连接问题而无法发送）

4. 容忍丢包：管理信息可重复发送，少量丢失可接受

6-36 为什么 SNMP 的管理进程使用报错重发机制来避免正常情况，而代理进程用陷阱向管理进程报告属于较少发生的异常情况？

答案：

• 管理进程使用报错重发：主动查询时，请求可能丢失，需要重发保证可靠性

• 代理进程使用陷阱（Trap）：异常情况是偶发的，用 Trap 无需等待查询，能及时报告；如果异常频繁，则 Trap 开销可控

这样设计平衡了效率和可靠性。

6-37 SNMP 使用哪几种操作？SNMP 在 Get 报文中设置了请求标识符字段，为什么？

答案：

SNMP 操作类型：

• GetRequest（管理→代理：获取单个变量）

• GetNextRequest（管理→代理：获取下一个变量）

• SetRequest（管理→代理：设置变量）

• GetResponse（代理→管理：响应请求）

• Trap（代理→管理：主动告警）

请求标识符字段作用：区分不同请求，匹配响应，支持重发机制。

6-38 什么是管理信息库 MIB？为什么要使用 MIB？

答案：

MIB（管理信息库）：一个虚拟数据库，定义了被管设备中所有可访问的变量（如接口状态、路由表、流量计数等）。

使用 MIB 的原因：

• 统一被管对象命名和定义

• 使不同厂商设备支持统一的网络管理协议

• 便于管理进程查询和设置设备参数

6-39 什么是管理信息结构 SMI？它的作用是什么？

答案：

SMI（管理信息结构）：定义 MIB 中变量的数据类型、命名方法和编码规则的规范。

作用：

• 保证 MIB 定义的一致性和可读性

• 规定数据类型的表示方法（INTEGER、OCTET STRING、IPAddress 等）

• 为 ASN.1 编码提供基础

6-40 用 ASN.1 基本编码规则对以下 4 个数组 (SEQUENCE-OF) 进行编码。假定每一个数字占用 4 个字节。2345, 1236, 122, 1236

答案（按图片）：

30 18
02 04 00 00 09 29
02 04 00 00 04 D4
02 04 00 00 00 7A
02 04 00 00 04 D4

解析：

• 30：SEQUENCE 标记

• 18：总长度 24 字节

• 每个整数：02（INTEGER）+ 04（长度）+ 4 字节值

• 122 = 0x0000007A

6-41 SNMP 要发送一个 GetRequest 报文，以便向一个路由器获取 ICMP 的 icmpInParmProbs 的值。在 icmp 中变量icmpInParmProbs 的标号是 5，它是一个计数器，用来统计收到的类型为参数问题的 ICMP 差错报告报文的数目。试给出这个 GetRequest 报文的编码。

答案：

变量 icmpInParmProbs 的对象标识符是1.3.6.1.2.1.5.5，加上后缀 ".0"

编码：

A0 1D
02 04 00 01 06 14
02 01 00
02 01 00
30 0F
30 0D
06 09 01 03 06 01 02 01 05 05 00
05 00

6-42 对象 tcp 的 OBJECT IDENTIFIER 是什么？

答案：{1.3.6.1.2.1.6}

6-43 在 ASN.1 中，IP 地址 (IPAddress) 的类型是应用类。若 IPAddress = 131.21.14.2，试求其 ASN.1 编码。

答案：40 04 83 15 0E 02

解析：

• 40：应用类标记（IPAddress）

• 04：长度 4 字节

• 83 15 0E 02：131.21.14.2

6-44 什么是应用编程接口 API？它是应用程序和谁的程序接口？

答案：

API（应用编程接口）：应用程序与操作系统或网络协议栈之间的接口，提供一组函数调用供应用程序使用。

接口对象：应用程序 ↔ 操作系统/协议栈（如 socket API）

6-45 试举出常用的几种系统调用的名称，说明它们的用途。

答案：

6-46 图 6-37 表示了各应用协议在层次中的位置。

(1) 简单讨论一下为什么有的应用层协议要使用 TCP 而有的却要使用 UDP？
(2) 为什么 MIME 画在 SMTP 之上？
(3) 为什么路由选择协议 RIP 放在应用层？

答案：

(1)

• 使用 TCP：需要可靠传输（FTP、HTTP、SMTP、TELNET）

• 使用 UDP：实时性要求高、可容忍丢包（DNS、SNMP、TFTP、RIP）

(2)MIME 是 SMTP 的扩展，用于在邮件中传输多媒体内容，因此位于 SMTP 之上。

(3)RIP 作为应用层进程运行，通过 UDP 交换路由信息，而非在操作系统内核中实现。

6-47 现在流行的 P2P 文件共享应用程序有哪些特点？存在哪些值得注意的问题？

答案：

特点：

• 去中心化，没有单一服务器

• 每个节点既是客户端也是服务器

• 可扩展性好，节点越多速度越快

• 资源利用率高

问题：

• 版权侵权

• 恶意软件传播

• 安全隐患（隐私泄露）

• 网络流量控制困难

6-48 使用客户-服务器方式进行文件分发。一台服务器把一个长度为 F 的大文件分发给 N 个对等方。假设文件传输的瓶颈是各计算机（包括服务器）的上传速率 u。试计算文件分发到所有对等方的最短时间。

答案：N × F / u

解析：服务器需要发送 N 份文件，服务器上传速率 u 为瓶颈。

6-49 重新考虑上题的文件分发任务，但采用 P2P 文件分发方式，并且每个对等方只能在接收完整个文件后才能向其他对等方转发。试计算文件分发到所有 N 个对等方的最短时间。

答案：log₂(N+1) × F / u

解析：整文件转发 P2P，时间由最慢的节点决定，呈对数增长。

6-50 再重新考虑上题的文件分发任务，但可以把这个非常大的文件划分为一个个非常小的数据块进行分发，即一个对等方在下载完一个数据块后就能向其他对等方转发，并同时可下载其他数据块。不考虑分块增加的控制信息，试计算整个文件分发到所有对等方的最大时间。

答案：F / u

解析：理想流水线 P2P，系统总上传能力足够，瓶颈为单个节点的上传速率 u。

6-51 假定某服务器有一文件 F = 15 Gbit 要分发给分布在互联网各处的 N 个对等方。服务器上传速率 u_s = 30 Mbit/s，每个对等方的下载速率 d = 2 Mbit/s，上传速率为 u = 300 kbit/s。设 (1) N = 10, (2) N = 1000。试分别计算在客户-服务器方式下和在 P2P 方式下，该文件分发时间的最小值。

答案：

(1) N = 10：

• 客户-服务器方式：7.5 × 10³ 秒（7500 秒）

• P2P 方式：7.5 × 10³ 秒（7500 秒）

(2) N = 1000：

• 客户-服务器方式：5 × 10⁵ 秒（500000 秒）

• P2P 方式：45.5 × 10³ 秒（45500 秒）

二、数据结构第8章 查找 算法设计题

(1) 在顺序查找算法中，如果将监视哨由原来的 0 号单元改为 n 号单元，算法应如何修改？

核心思路

• 原算法：将待查关键字放在下标 0 处，从后向前查找

• 改为 n 号单元：将待查关键字放在下标 n 处，从前向后查找

C语言代码

int SeqSearch(int A[], int n, int key) { A[n] = key; // 监视哨放在 n 号单元 int i = 0; while (A[i] != key) i++; return i == n ? -1 : i; }

C++代码

int seqSearch(vector<int>& A, int key) { int n = A.size() - 1; A[n] = key; int i = 0; while (A[i] != key) i++; return i == n ? -1 : i; }

(2) 已知无序顺序表 L 中有 m 个数据元素，编写算法为 L 建立一个有序的索引表，要求索引表中的每一项数据元素的关键字和该数据元素在顺序表中的序号。

核心思路

1. 遍历顺序表，记录每个元素的关键字及其序号

2. 按关键字排序生成索引表

3. 索引表项包含（关键字，序号）

C语言代码

typedef struct { int key; int index; } IndexItem; void buildIndex(int L[], int m, IndexItem idx[]) { for (int i = 0; i < m; i++) { idx[i].key = L[i]; idx[i].index = i; } // 按 key 排序（冒泡排序示例） for (int i = 0; i < m - 1; i++) { for (int j = 0; j < m - i - 1; j++) { if (idx[j].key > idx[j + 1].key) { IndexItem temp = idx[j]; idx[j] = idx[j + 1]; idx[j + 1] = temp; } } } }

C++代码

struct IndexItem { int key; int index; }; void buildIndex(const vector<int>& L, vector<IndexItem>& idx) { for (int i = 0; i < L.size(); i++) { idx.push_back({L[i], i}); } sort(idx.begin(), idx.end(), [](const IndexItem& a, const IndexItem& b) { return a.key < b.key; }); }

(3) 编写并检查排序算法的递归算法。

核心思路

以归并排序为例：分治法，递归拆分再合并

C语言代码

void merge(int A[], int l, int m, int r) { int temp[r - l + 1]; int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (A[i] <= A[j]) temp[k++] = A[i++]; else temp[k++] = A[j++]; } while (i <= m) temp[k++] = A[i++]; while (j <= r) temp[k++] = A[j++]; for (int p = 0; p < k; p++) A[l + p] = temp[p]; } void mergeSort(int A[], int l, int r) { if (l < r) { int m = (l + r) / 2; mergeSort(A, l, m); mergeSort(A, m + 1, r); merge(A, l, m, r); } }

C++代码

void merge(vector<int>& A, int l, int m, int r) { vector<int> temp(r - l + 1); int i = l, j = m + 1, k = 0; while (i <= m && j <= r) temp[k++] = A[i] <= A[j] ? A[i++] : A[j++]; while (i <= m) temp[k++] = A[i++]; while (j <= r) temp[k++] = A[j++]; for (int p = 0; p < k; p++) A[l + p] = temp[p]; } void mergeSort(vector<int>& A, int l, int r) { if (l < r) { int m = (l + r) / 2; mergeSort(A, l, m); mergeSort(A, m + 1, r); merge(A, l, m, r); } }

(4) 已知二叉排序树采用二叉链表作为存储结构，且二叉排序树的各元素值均不相同，编写递归算法，按递减次序输出所有左子树非空、右子树为空的结点的数据域的值。

核心思路

• 中序遍历逆序（右→根→左）得到递减序列

• 对每个结点判断：左子树非空且右子树为空，则输出

C语言代码

void outputNodes(BiTree T) { if (!T) return; outputNodes(T->rchild); if (T->lchild && !T->rchild) { printf("%d ", T->data); } outputNodes(T->lchild); }

C++代码

void outputNodes(BiTree T) { if (!T) return; outputNodes(T->rchild); if (T->lchild && !T->rchild) { cout << T->data << " "; } outputNodes(T->lchild); }

(5) 编写算法，判断所给的二叉树是否为二叉排序树。

核心思路

• 中序遍历二叉排序树应得到递增序列

• 记录前驱结点，检查是否满足 BST 性质

C语言代码

int prev = INT_MIN; int isBST(BiTree T) { if (!T) return 1; if (!isBST(T->lchild)) return 0; if (T->data <= prev) return 0; prev = T->data; return isBST(T->rchild); }

C++代码

int prev = INT_MIN; bool isBST(BiTree T) { if (!T) return true; if (!isBST(T->lchild)) return false; if (T->data <= prev) return false; prev = T->data; return isBST(T->rchild); }

(6) 编写算法，输出给定二叉排序树中数据域值最大的结点。

核心思路

• 二叉排序树的最大值位于最右结点

C语言代码

BiTree findMax(BiTree T) { if (!T) return NULL; while (T->rchild) T = T->rchild; return T; }

C++代码

BiTree findMax(BiTree T) { if (!T) return nullptr; while (T->rchild) T = T->rchild; return T; }

(7) 编写算法，实现按递增有序输出二叉排序树结点数据域的值，如果有相同的数据元素，则仅输出一个。

核心思路

• 中序遍历输出

• 记录前驱，相同则跳过

C语言代码

int last = INT_MIN; void inorderUnique(BiTree T) { if (!T) return; inorderUnique(T->lchild); if (T->data != last) { printf("%d ", T->data); last = T->data; } inorderUnique(T->rchild); }

C++代码

int last = INT_MIN; void inorderUnique(BiTree T) { if (!T) return; inorderUnique(T->lchild); if (T->data != last) { cout << T->data << " "; last = T->data; } inorderUnique(T->rchild); }

(8) 已知哈希表的表长为 m，哈希函数 H(key)=key%m，采用线性探测再散列处理冲突，编写算法计算查找成功时的平均查找长度。

核心思路

• 模拟插入过程，记录每个关键字的探测次数

• 平均查找长度 = 总探测次数 / 关键字个数

C语言代码

double avgSearchLength(int keys[], int n, int m) { int hash[1000] = {0}; // 0 表示空 int total = 0; for (int i = 0; i < n; i++) { int pos = keys[i] % m; int cnt = 1; while (hash[pos] != 0) { pos = (pos + 1) % m; cnt++; } hash[pos] = keys[i]; total += cnt; } return (double)total / n; }

C++代码

double avgSearchLength(const vector<int>& keys, int m) { vector<int> hash(m, 0); int total = 0; for (int key : keys) { int pos = key % m; int cnt = 1; while (hash[pos] != 0) { pos = (pos + 1) % m; cnt++; } hash[pos] = key; total += cnt; } return (double)total / keys.size(); }

(9) 已知哈希表的表长为 m，哈希函数 H(key)=key%m，采用链地址法处理冲突，编写算法完成以下操作：

① 在哈希表中查找指定数据元素。
② 在哈希表中插入指定数据元素。
③ 在哈希表中删除指定数据元素。

核心思路

• 哈希表为链表数组

• 查找：计算哈希值，在对应链表中顺序查找

• 插入：查找是否存在，不存在则头插或尾插

• 删除：查找并删除链表结点

C语言代码

typedef struct Node { int key; struct Node* next; } Node; Node* hashTable[1000]; // 初始化 void initHash() { for (int i = 0; i < 1000; i++) hashTable[i] = NULL; } // ① 查找 int search(int key, int m) { int pos = key % m; Node* p = hashTable[pos]; while (p) { if (p->key == key) return 1; p = p->next; } return 0; } // ② 插入 void insert(int key, int m) { if (search(key, m)) return; int pos = key % m; Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key; newNode->next = hashTable[pos]; hashTable[pos] = newNode; } // ③ 删除 void deleteKey(int key, int m) { int pos = key % m; Node* p = hashTable[pos]; Node* prev = NULL; while (p) { if (p->key == key) { if (prev) prev->next = p->next; else hashTable[pos] = p->next; free(p); return; } prev = p; p = p->next; } }

C++代码

#include <list> #include <vector> using namespace std; class HashTable { private: vector<list<int>> table; int m; public: HashTable(int size) : m(size), table(size) {} // ① 查找 bool search(int key) { int pos = key % m; for (int x : table[pos]) { if (x == key) return true; } return false; } // ② 插入 void insert(int key) { if (search(key)) return; int pos = key % m; table[pos].push_front(key); } // ③ 删除 void remove(int key) { int pos = key % m; table[pos].remove(key); } };

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