数据结构1800题 可修改 可打印
数据结构1800例题与答案
第一章 绪 论
一、选择题（每小题2分）
1．算法的计算量的大小称为计算的（ B ）。
A．效率 B．复杂性 C．现实性 D．难度
2．算法的时间复杂度取决于（C）。
A．问题的规模 B．待处理数据的初态 C．A和B D．都不是
3．计算机算法指的是（① C ），它必须具备（② B ） 这三个特性。
① A．计算方法 B．排序方法
C．解决问题的步骤序列 D．调度方法
② A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性
C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性
4．一个算法应该是（ B ）。
A．程序 B．问题求解步骤的描述
C．要满足五个基本特性 D．A和C.
根据给定文件的信息，我们可以提炼出以下几个重要的知识点：
### 一、算法的基本概念
#### 1.1 算法的复杂性
- **算法的计算量**：指算法执行时所需的操作次数，通常用来衡量算法的复杂性。在题目中提到的算法计算量大小即算法的**复杂性**(Complexity)，选项B正确。
- **算法的时间复杂度**：描述算法运行时间与输入数据规模的关系，取决于问题的规模和初始状态，但在多数情况下，更侧重于问题的规模(A)和数据的初始状态(B)对算法运行时间的影响，因此选项C是最全面的答案。
#### 1.2 计算机算法定义
- **算法**：一系列解决问题的清晰指令，必须具备可执行性(算法能被正确执行)、确定性(算法的每一步都明确无误)、有穷性(算法能在有限时间内完成)这三个特性。因此计算机算法指的是解决问题的步骤序列(C)，并且必须具备可执行性、确定性、有穷性(B)这三个特性。
#### 1.3 算法的性质
- 一个算法应该是一种**问题求解步骤的描述**(B)，不仅要包含解决问题的具体步骤，而且这些步骤还必须具备一定的特性，例如可执行性、确定性和有穷性等。
### 二、算法的错误理解
- 题目中的第5题指出了一些关于算法的常见误解：
- 算法并非一定要通过计算机程序实现，也可以通过其他形式表达，如伪代码等(D错误)。
- 算法和程序虽然密切相关，但含义并不相同(B错误)。
- 算法的可行性是指算法在理论上可以被执行，而不是指令不能有二义性(C错误)。
### 三、算法的空间与时间复杂度
- **算法的原地工作**：是指算法在执行过程中不需要额外的辅助空间，但并非所有算法都可以原地工作(1错误)。
- **时间复杂度**：在最坏的情况下，估算算法执行时间的上限，通常使用大O记号表示(O(n)比O(2n)好，因为常数系数在大O记号中通常忽略)(2正确)。
- **算法实现语言**：同一算法，实现语言的级别越高(如Python相对于C++)，执行效率往往越低(4正确)。
### 四、数据结构的分类
- 从逻辑上讲，数据结构可以分为**线性结构**和**非线性结构**两大类(C)。线性结构如数组、链表，非线性结构如树和图。
- 数据的存储结构是指数据在计算机内存中的存储方式，如**顺序存储**、**链式存储**等。而某些术语与数据的存储结构无关，如**栈**(D)。
### 五、数据结构的存储与表示
- 在连续存储设计中，存储单元的地址必须是连续的(A)，这是连续存储方式的特点之一。
- 逻辑结构是指数据元素之间的逻辑关系，例如有序表(C)描述了一种特定的逻辑关系。
### 六、数据结构的逻辑结构与物理结构
- 数据的逻辑结构描述了数据元素之间的逻辑关系，而数据的物理结构则关注数据在计算机中的存储形式。两者是数据结构的重要组成部分，逻辑结构不受存储结构的影响。
- 顺序存储方式的优点在于存储密度大，但插入和删除操作效率较低(11错误)。
- 抽象数据类型的定义仅依赖于其逻辑特性，与其实现方式无关，这意味着无论内部结构如何变化，只要逻辑特性不变，都不会影响其外部使用(9错误)。
通过对给定文档的分析，我们不仅了解了算法的基本概念、性质及其常见误区，还深入探讨了数据结构的分类、存储方式以及逻辑与物理结构的区别。这些知识点对于学习和理解数据结构与算法至关重要。
