数据结构之绪论

逻辑结构与存储结构

1. 可以用( )定义一个完整的数据结构。

A. 数据关系
B. 抽象数据类型
C. 数据对象
D. 数据元素

答案: B. 抽象数据类型 解释: 抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用三元组（数据对象，数据关系，基本操作集）来表示，从而构成一个完整的数据结构定义。

2. 以下数据结构中，()是非线性数据结构。

A. 树
B. 字符串
C. 队列
D. 栈

答案: A. 树 解释: 树和图是典型的非线性数据结构，其他选项如字符串、队列和栈都属于线性数据结构。

3. 以下属于逻辑结构的是()。

A. 顺序表
B. 哈希表
C. 有序表
D. 单链表

答案: C. 有序表 解释: 有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系。它既可以用链式存储，也可以用顺序存储，因此它属于逻辑结构。其他选项描述了数据的存储结构和运算方式。

4. 以下与数据的存储结构无关的术语是()。

A. 循环队列
B. 链表
C. 哈希表
D. 栈

答案: D. 栈 解释: 栈是一种抽象数据类型，描述的是一种逻辑结构，可以采用顺序存储或链式存储。而循环队列、链表和哈希表则是特定的存储结构。

5. 以下关于数据结构的说法中，正确的是()。

A. 数据的逻辑结构独立于其存储结构
B. 数据的存储结构独立于其逻辑结构
C. 数据的逻辑结构唯一决定其存储结构
D. 数据结构仅由其逻辑结构和存储结构决定

答案: A. 数据的逻辑结构独立于其存储结构 解释: 数据的逻辑结构是面向实际问题的抽象表达方式，独立于存储结构，而存储结构是逻辑结构在计算机上的映射，两者相互关联，但逻辑结构不依赖于存储结构。

6. 在存储数据时，通常不仅要存储各数据元素的值，而且要存储()。

A. 数据的操作方法
B. 数据元素的类型
C. 数据元素之间的关系
D. 数据的存取方法

答案: C. 数据元素之间的关系 解释: 在存储数据时，不仅要存储数据元素的值，还需要存储数据元素之间的关系，以确保数据结构的完整性和功能性。

7. 链式存储设计时，结点内的存储单元地址()。

A. 一定连续
B. 不一定连续
C. 一定不连续
D. 部分连续，部分不连续

答案: A. 一定连续 解释: 在链式存储中，各个结点的存储空间可以在物理上不连续，但一个结点内的存储单元地址（如数据域和指针域）必须是连续的。

综合应用题

对于两种不同的数据结构，逻辑结构或物理结构一定不相同吗？

解答:
两种不同的数据结构，其逻辑结构和物理结构并不一定不同。例如，二叉树和二叉排序树，它们可以采用相同的逻辑结构和存储方式。二叉树通常用于表示层次关系，二叉排序树则用于排序和查找。尽管它们的运算功能相似，例如建立树、插入、删除和查找结点，但定义不同。比如查找操作，二叉树的时间复杂度为 $O(n)$，而二叉排序树的查找时间复杂度则为 $O(\log n)$，这体现了逻辑结构相同但功能不同的运算效率差异。
试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同。

解答:
以线性表为例，它既可以采用顺序存储方式，也可以采用链式存储方式。在顺序存储方式下，插入和删除元素时，需要移动大量元素，平均情况下移动一半的元素，时间复杂度为 $O(n)$。而在链式存储方式下，插入和删除操作只需要调整指针，时间复杂度为 $O(1)$。这说明在不同存储方式下，同样的插入或删除操作会有不同的运算效率。

复杂度

01. 一个算法应该是( )

A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
D. A 和 C

答案: B. 问题求解步骤的描述
解释: 程序可能不具备有穷性，比如操作系统中可能存在死循环。而算法必须具备有穷性、确定性等特性。算法是对问题求解步骤的抽象描述，程序则是算法的具体实现。虽然算法有五个基本特性，但这是算法的条件，而不是定义本身。

02. 某算法的时间复杂度为 O(n)，表明该算法的()

A. 问题规模是 n
B. 执行时间等于 n
C. 执行时间与 n 成正比
D. 问题规模与 n 成正比

答案: C. 执行时间与 n 成正比
解释: 时间复杂度 O(n) 表示该算法的执行时间 T(n) 与问题规模 n 成正比，即 T(n) ≤ cn (c 为常数)，而问题规模仍是 n。

03. 以下算法的时间复杂度为()

void fun(int n) {
    int i = 1;
    while (i <= n) i = i * 2;
}

A. O(n)
B. O(n²)
C. O(nlogn)
D. O(logn)

答案: D. O(logn)
解释: 在每次循环中，变量 i 的值乘以 2，因此循环的次数满足 $ 2^t n $，即 $ t _2 n $，所以算法的时间复杂度为 $ O(n) $。

04. 有以下算法，其时间复杂度为()

void fun(int n) {
    int i = 0;
    while (i * i * i <= n) i++;
}

A. O(n)
B. O(nlogn)
C. O(√n)
D. O($n^{1/3}$)

答案: D
解释: 循环的条件是 $ i^3 n $，因此变量 i 的最大值接近 $ n^{1/3} $。

05. 下列程序段的最坏情况下的时间复杂度是()

for(i = n - 1; i > 1; i--)
    for(j = 1; j < i; j++)
        if(A[j] > A[j+1])
            swap(A[j], A[j+1]);

A. O(n)
B. O(nlogn)
C. O(n²)
D. O(n³)

答案: C. O(n²)
解释: 这是冒泡排序的代码。在最坏情况下，两个嵌套循环分别执行 $ n $ 和 $ n-1 $ 次，导致其总的时间复杂度为 $ O(n²) $。

06. 以下算法中加下划线的语句的执行次数为()

int m = 0, i, j;
for (i = 1; i <= n; i++)
    for (j = 1; j <= 2 * i; j++)
        m++;

A. n(n+1)
B. n
C. n²
D. O(n³)

答案: A. n(n+1)
解释: 外循环执行 n 次，内循环在第 i 次时执行 $ 2 i $ 次。因此，语句 m++ 总共执行次数为 $ _{i=1}^{n} 2i = 2 = n(n+1) $。

07. 下列说法中错误的是()

I. 算法原地工作的含义是指不需要任何额外的辅助空间
II. 在相同规模 n 下，复杂度为 O(n) 的算法在时间上总是优于复杂度为 O(2^n) 的算法
III. 所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
IV. 同一个算法，实现语言的级别越高，执行效率越低

A. I B. I, II C. I, IV D. III

答案: C. I, IV
解释:

I 错误：原地工作算法（In-place Algorithm）指的是算法在运行过程中使用的辅助空间是常量级别的，而不是完全不需要任何额外的辅助空间。
IV 错误：虽然高层次语言的抽象程度高，理论上可能影响执行效率，但现代编译器和虚拟机的优化使得高层语言的执行效率并不总是低于低层次语言，且不能以此作为普遍结论。
II 正确：在相同规模 n 下，O(n) 的算法时间复杂度优于 O(2^n) 的算法。
III 正确：时间复杂度通常表示的是最坏情况下的算法执行时间上界。

08. 设 n 是描述问题规模的非负整数，下面的程序片段的时间复杂度是()

x = 2;
while (x < n / 2) {
    x = 2 * x;
}

A. O(log n)
B. O(n)
C. O(nlogn)
D. O(2^n)

答案: A. O(log n)
解释: 基本运算是 x = 2 * x，每次循环 x 乘以 2，执行次数满足 $ 2^t $，所以 $ t _2(n/2) $。因此时间复杂度为 $ O(n) $。

09. 求整数 n (n ≥ 0) 的阶乘的算法如下，其时间复杂度是()

int fact(int n) {
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n^2)

答案: B. O(n)
解释: 阶乘的递归算法每次递归调用时 n 减 1，递归深度是 n，所以算法的时间复杂度为 $ O(n) $。

10. 已知两个长度分别为 m 和 n 的升序链表，若将它们合并为长度为 m + n 的一个降序链表，则最坏情况下的时间复杂度是()

A. O(n)
B. O(mn)
C. O(min(m, n))
D. O(max(m, n))

答案: D. O(max(m, n))
解释: 合并两个升序链表可以通过逐步比较每个链表的头结点，将较大的结点插入新链表中。在最坏的情况下，需要比较 m 和 n 次才能合并。由于两个链表的长度为 m 和 n，最坏情况下的时间复杂度为 O(max(m, n))。

11. 下列程序段的时间复杂度是()

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= n; j++)
        count++;

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n^2)

答案: C. O(n log n)
解释: 外层循环 for(k = 1; k <= n; k *= 2) 的次数为 $ O(n) $ 因为每次循环 k 都乘以 2。内层循环 for(j = 1; j <= n; j++) 执行 n 次。两者相乘，因此时间复杂度为 $ O(n n) $。

12. 下列函数的时间复杂度是()

int fun(int n) {
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

A. O(log n)
B. O(√n)
C. O(n)
D. O(n log n)

答案: B. O(√n)
解释: 每次循环 i 自增 1，sum 以等差数列的形式增加，满足 $ sum = $。因此，循环次数 $ t $ 满足 $ t(t + 1)/2 < n $，得 $ t = O(√n) $，所以时间复杂度为 $ O(√n) $。

13. 设 n 是描述问题规模的非负整数，下列程序段的时间复杂度是()

1
2
3

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

A. O(log n)
B. O(√n)
C. O(n)
D. O(n log n)

答案: B. O(√n)
解释: 每次循环 x 自增 1，直到 $ (x+1)^2 > n $，即 $ x √n $，因此该程序的时间复杂度为 $ O(√n) $。

综合应用题解答

01. 递归方程分析

题目给定递归方程：

$ T(n) = \[\begin{cases} 1, & n = 1 \\ 2T(n/2) + n, & n > 1 \end{cases}\]

其中 $n$ 是问题规模，设 $n = 2^k$（即 $n$ 是 2 的整数次幂）。我们可以使用递归树方法或者主定理（Master Theorem）来求解该递归方程。

根据主定理中的形式 $T(n) = aT(n/b) + O(n^d)$，我们有：
- $a = 2$
- $b = 2$
- $d = 1$
比较 $n^{\log_b a} = n^{\log_2 2} = n^1$ 与 $n^d$：
- $n^{\log_2 2} = n$，与 $n^1$ 相等，符合主定理的第二种情况。因此，时间复杂度为：

$ T(n) = O(n n) $

答案: 时间复杂度为 $ O(n n) $。

02. 各程序段时间复杂度分析

(1) 程序段

i = 1;
k = 0;
y = 0;
while (i < n - 1) {
    while ((y + 1) * (y + 1) <= n)
        k = k + 10 * i;
        y = y + 1;
    }
    i++;
}

外层 while (i < n - 1) 循环执行 $n - 2$ 次。
内层 while ((y + 1) * (y + 1) <= n) 的条件为 $y^2 \leq n$，因此内层循环的复杂度为 $ O() $。
内层循环中的语句 k = k + 10 * i 为基本操作，执行次数为 $O(\sqrt{n})$ 每次外层循环都执行内层循环 $O(\sqrt{n})$ 次。

总的时间复杂度为外层循环 $n - 2 $ 次乘以内层循环 $O(\sqrt{n})$ 次，故该段代码的时间复杂度为：

$ T(n) = O(n ) $

(2) 程序段

1
2
3

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        for (k = 1; k <= j; k++)

最内层循环 for(k = 1; k <= j; k++) 执行 $j$ 次。
第二层循环 for(j = 1; j <= i; j++) 执行 $i$ 次。
最外层循环 for(i = 1; i <= n; i++) 执行 $n$ 次。

总的执行次数为：

$ {i=1}^n {j=1}^i {k=1}^j 1 = {i=1}^n {j=1}^i j = {i=1}^n = O(n^3) $

因此，时间复杂度为：

$ T(n) = O(n^3) $

(3) 程序段

1
2
3

for (i = 0; i < n; i++)
    for (j = 0; j < m; j++)
        a[i][j] = 0;

内层循环 for(j = 0; j < m; j++) 执行 $m$ 次。
外层循环 for(i = 0; i < n; i++) 执行 $n$ 次。

总的执行次数为 $n \times m$，因此时间复杂度为：

$ T(m, n) = O(m n) $

扩展

题目：求解斐波那契数列

斐波那契数列的定义如下：

$ F(n) = \[\begin{cases} 1 & n = 0,1 \\ F(n-1) + F(n-2) & n > 1 \end{cases}\]

有两种常用的算法：递归算法和非递归算法。试分别分析两种算法的时间复杂度。

解答：

1. 递归算法的时间复杂度

递归算法可以直接按照斐波那契数列的定义进行求解，代码如下：

int fib(int n) {
    if (n == 0 || n == 1) 
        return 1;
    else 
        return fib(n-1) + fib(n-2);
}

时间复杂度分析：

递归算法会重复计算很多子问题。例如，为了计算 $F(n)$，会计算 $F(n-1)$ 和 $F(n-2)$。为了计算 $F(n-1)$，又会计算 $F(n-2)$ 和 $F(n-3)$，如此反复。
递归树的结构类似于一个二叉树，树的高度为 $n$，每个节点会进行一次计算。因此，递归算法的时间复杂度由递归树的节点总数决定。

递归调用的次数近似为斐波那契数列的增长模式，每次都计算两个子问题，导致总的时间复杂度为：

$ T(n) = O(2^n) $

递归算法的时间复杂度为指数级别 $O(2^n)$，这是非常低效的。

2. 非递归算法的时间复杂度

非递归算法通过保存前两个斐波那契数的值，逐步计算后面的值，避免了重复计算。代码如下：

int fib(int n) {
    if (n == 0 || n == 1)
        return 1;
    int a = 1, b = 1, c;
    for (int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

时间复杂度分析：

非递归算法的核心是通过迭代的方式，从 $F(2)$ 开始，逐步计算到 $F(n)$，每次只用到前两个数。
这个算法只需要执行 $n-1$ 次加法运算，因此它的时间复杂度为线性时间复杂度：

$ T(n) = O(n) $

相比递归算法，非递归算法在时间复杂度上有显著优势。

结论：

递归算法的时间复杂度为 $O(2^n)$，因为大量重复计算子问题。
非递归算法的时间复杂度为 $O(n)$，通过迭代避免了重复计算，效率更高。

知识点总结

1. 数据结构的三要素

数据结构由三要素组成，它们分别是：

数据的逻辑结构
描述数据元素之间的逻辑关系。数据的逻辑结构可以分为两类：
- 线性结构：数据元素之间是一对一的线性关系，如线性表、栈、队列等。
- 非线性结构：数据元素之间的关系复杂，可能是多对多的，如树、图、集合等。
数据的存储结构（物理结构）
描述数据元素在计算机中的存储方式。主要有两种存储结构：
- 顺序存储结构：数据元素存储在内存中的连续地址上，如数组。
- 链式存储结构：数据元素通过指针链接在一起，不要求存储在连续的内存地址上，如链表。
数据的运算
定义了在数据结构上可以进行的操作，主要包括：
- 插入
- 删除
- 查找
- 更新

2. 算法定义及五个特征

算法是指解题的步骤或规则的有限序列。算法的核心特征有以下五个：

有穷性：算法在执行有限步之后必须结束。
确定性：算法的每一步操作都有明确的含义，不会有二义性。
可行性：算法的每一步操作都能在有限时间内完成，且能通过基本运算实现。
输入：算法有零个或多个输入。
输出：算法至少有一个输出，且应反映问题的结果。

3. 算法复杂度

算法的复杂度用于衡量算法的效率，主要包括时间复杂度和空间复杂度。

3.1. 时间复杂度

时间复杂度 衡量算法在运行时所需要的时间，通常使用大 O 记号来表示。时间复杂度的计算步骤如下：

确定算法的基本操作：找出算法中执行次数最多的基本操作，如赋值、加法等。
计算基本操作的执行次数：分析算法中基本操作的执行频率。
忽略低阶项和常数：只保留最高阶项，忽略常数项，以体现算法在大规模问题下的增长趋势。

常见的时间复杂度有：

O(1)：常数时间复杂度，表示算法的执行时间不随输入规模变化。
O(log n)：对数时间复杂度，通常出现在二分查找等算法中。
O(n)：线性时间复杂度，常见于遍历列表的算法。
O(n log n)：通常出现在归并排序、快速排序等高效排序算法中。
O(n^2)：平方时间复杂度，常见于冒泡排序、选择排序等简单排序算法。
O(2^n)：指数时间复杂度，通常出现在递归问题中，如斐波那契数列的递归解法。
O(n!)：阶乘时间复杂度，通常出现在全排列等问题中。

3.2. 空间复杂度

空间复杂度 用于衡量算法在运行时所需要的额外空间。它同样使用大 O 记号表示。空间复杂度反映了算法对内存的需求。

常见的空间复杂度分析：

O(1)：表示算法只需要常数的额外空间，如使用几个变量进行计算。
O(n)：表示算法需要与输入规模成正比的额外空间，如在递归算法中，递归调用栈的深度与问题规模 $n$ 成正比。
O(n^2)：表示算法需要二维数组或矩阵来存储结果，空间需求为 $n^2$。

4. 复杂度分析举例

4.1. 线性搜索算法的时间复杂度分析

线性搜索的算法如下：

int linearSearch(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) 
            return i;
    }
    return -1;
}

分析：

每次循环的基本操作是数组的比较 $ arr[i] == key $，循环执行 $n$ 次，最坏情况下，算法需要遍历整个数组。
时间复杂度为 $O(n)$。

4.2. 二分查找算法的时间复杂度分析

二分查找的算法如下：

int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key)
            return mid;
        else if (arr[mid] < key)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return -1;
}

分析：

每次查找将问题规模减半，基本操作是比较 $ arr[mid] == key $。
时间复杂度为 $O(\log n)$。

4.3. 冒泡排序算法的时间复杂度分析

冒泡排序的算法如下：

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
        }
    }
}