数据结构期末复习（4）

二叉排序树（BST, Binary Search Tree）在最优情况下，可以达到查找深度为 O(log₂ n)。对于 100 个元素，log₂(100) 的值大约为 6.64，因此在最优情况下，可以在不超过 7 次比较中找到元素。在最理想情况下，具有平衡性质的二叉排序树能够在 5 次比较中找到目标元素。

其他选项的分析：

折半查找（选项 C）：折半查找适用于有序数组，log₂(100) 约为 7，因此在最坏情况下需要 7 次比较。
哈希查找（选项 B）：不基于元素之间的比较，因此不适用。
分块查找（选项 D）：在复杂情况下，可能需要更多的比较次数。

因此，正确答案是 A。

知识点讲解

二叉排序树查找：
- 二叉排序树是一种二叉树结构，左子树节点小于根节点，右子树节点大于根节点。
- 平均时间复杂度为 O(log₂ n)，在树是平衡时查找效率较高。
折半查找：
- 在有序数组中，通过逐步折半来查找目标元素。
- 时间复杂度为 O(log₂ n)。

知识点总结表格

知识点	说明
二叉排序树查找	左子树小于根，右子树大于根，`O(log₂ n)`
折半查找	适用于有序数组，`O(log₂ n)`
哈希查找	利用哈希函数，不进行比较

题目 21

给定有 n 个元素向量，建立一个有序单链表的时间复杂度是（）。

选项：

A. O(1)
B. O(n²)
C. O(n log₂ n)
D. O(n)

正确答案：B

解析

在构建有序单链表时，插入每个元素需要找到其正确位置并插入，这个操作的时间复杂度为 O(n)，因为需要遍历链表找到合适的位置。因此，对于 n 个元素，总的时间复杂度为：

O(n)×n=O(n2)O(n) \times n = O(n^2)O(n)×n=O(n2)

因此，建立一个有序单链表的时间复杂度为 O(n²)。

知识点讲解

有序单链表：
- 在插入元素时需要保持链表有序，因此每次插入前都需要遍历链表找到插入位置。
- 最坏情况下需要遍历整个链表，时间复杂度为 O(n)。
总时间复杂度：
- 对于 n 个元素，插入每个元素需要 O(n) 的时间，总的时间复杂度为 O(n²)。

知识点总结表格

知识点	说明
单链表	线性表的链式存储结构
插入有序单链表	需要遍历链表，找到合适位置，时间复杂度为 `O(n)`
总时间复杂度	插入 `n` 个元素，总时间复杂度为 `O(n²)`

题目 22

在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（）条边。

选项：

A. n/2
B. n-1
C. n
D. n+1

正确答案：B

解析

对于一个具有 n 个顶点的无向图，要使得所有顶点都相互连通，至少需要 n-1 条边。这是因为 n-1 条边能够构成一个树，树的定义就是一个包含所有节点且没有环的连通图，最少需要 n-1 条边。

知识点讲解

连通图：
- 一个无向图被称为连通图，如果任意两个顶点之间存在至少一条路径。
- 最少的边数为 n-1，这种结构是一棵树。
树的性质：
- 树是没有环的连通图，具有 n 个顶点和 n-1 条边。
- 所以，要使得图是连通的，至少需要 n-1 条边。

知识点总结表格

知识点	说明
连通图	任意两点之间存在路径
最小边数	连通 `n` 个顶点至少需要 `n-1` 条边
树的性质	没有环的连通无向图，具有 `n-1` 条边

题目 23

下列关键字序列中（）是堆。

选项：

A. 94, 23, 31, 72, 16, 53
B. 16, 23, 53, 31, 94, 72
C. 16, 53, 23, 94, 31, 72
D. 16, 72, 31, 23, 94, 53

正确答案：B

解析

堆是一种完全二叉树，且每个结点满足堆的性质：

大顶堆：每个节点的值都大于或等于其子节点的值。
小顶堆：每个节点的值都小于或等于其子节点的值。

在选项中，正确的堆应该满足完全二叉树的形状，同时所有父节点和子节点的值满足堆的性质。我们对每个选项的序列构建堆，发现选项 B 满足这些条件，是一个小顶堆。

知识点讲解

完全二叉树：
- 堆的结构必须是完全二叉树，即除最后一层外，所有层的节点都是满的。
堆的性质：
- 在大顶堆中，父节点的值大于等于子节点。
- 在小顶堆中，父节点的值小于等于子节点。

知识点总结表格

知识点	说明
堆	完全二叉树，满足堆的性质
大顶堆/小顶堆	父节点大于等于/小于等于其子节点
选项分析	选项 B 是一个符合堆性质的小顶堆

题目 25

在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。

选项：

A. O(n log₂ n)
B. O(n²)
C. O(1)
D. O(n)

正确答案：D

解析

在一个有序单链表中插入新节点，需要首先找到合适的位置，以保持链表的有序性。这个查找过程需要从链表头部开始，依次遍历节点，直到找到适合插入的位置。因此，查找插入位置的时间复杂度为 O(n)。

找到位置后，插入节点的操作本身是 O(1)，但由于查找操作是 O(n)，所以总体的时间复杂度为 O(n)。

知识点讲解

单链表的插入操作：
- 插入时，首先需要找到合适的插入位置，在单链表中需要逐个节点遍历查找，因此时间复杂度为 O(n)。
- 插入操作本身需要修改前一个节点的指针，因此是 O(1)。

知识点总结表格

知识点	说明
有序单链表	线性表的链式存储结构，保持有序
查找插入位置	需要遍历链表，时间复杂度为 `O(n)`
总时间复杂度	`O(n)`

题目 26

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

选项：

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

正确答案：D

解析

在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和，因为每条有向边有一个起点和一个终点。对于每一条边，都会对一个节点贡献一个入度，同时对另一个节点贡献一个出度，因此它们相等。

因此，正确答案是 D，即入度之和和出度之和相等，其倍数关系为 1。

知识点讲解

有向图中的度：
- 入度：某个顶点的入度是指指向该顶点的边数。
- 出度：某个顶点的出度是指从该顶点出发的边数。
- 所有顶点的入度之和等于所有顶点的出度之和。

知识点总结表格

知识点	说明
入度	指向某顶点的边的数量
出度	从某顶点出发的边的数量
入度与出度关系	总入度之和等于总出度之和

题目 27

下面关于串的叙述中，（）是不正确的？

选项：

A. 模式匹配是串的一种重要运算
B. 串是字符的有限序列
C. 串既可以采用顺序存储，也可以采用链式存储
D. 空串是由空格构成的串

正确答案：D

解析

空串是长度为 0 的串，表示没有任何字符。空串不包含空格、字母、数字等任何字符。因此，选项 D 是不正确的。

其他选项的分析：

A. 模式匹配是串的一种重要运算：正确，模式匹配（如字符串查找）是串的重要操作。
B. 串是字符的有限序列：正确，串是由有限个字符组成的序列。
C. 串既可以采用顺序存储，也可以采用链式存储：正确，串可以通过顺序存储或链式存储实现。

知识点讲解

空串：
- 空串是指长度为 0 的串，不包含任何字符。
- 不应将空串与包含空格的串混淆，空格是一个字符，而空串不包含任何字符。
串的存储方式：
- 顺序存储：字符连续存放在内存中，便于快速访问。
- 链式存储：字符可以分散存储，通过指针链接，便于插入和删除操作。

知识点总结表格

知识点	说明
空串	长度为 `0` 的串，不包含任何字符
模式匹配	串的一种重要运算，如查找子串
存储方式	顺序存储或链式存储

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能