题目来源：”西工大计算机“公众号，答案为手工核对整理

第一章 绪论

1. 简述数据结构的定义和组成

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，包括逻辑结构、物理结构和数据运算。

2. 数据的存储结构有哪几种？每种的优缺点是什么？

顺序存储

特点：存储空间的地址连续，数据元素依次存放；利用物理相邻表示（存储）逻辑关系。

优点：存储密度大；可以随机访问，在O(1)内查询、修改元素。

缺点：表示关系能力弱；维护关系困难（逻辑关系发生变化，物理上难同步），在O(n)内插入和删除数据；存储空间必须一次获得（适用性差）。

链式存储

特点：占用空间任意，元素任意存放；在存放元素的同时，还存放与其有关系的元素的地址（指针）。

优点：空间任意；显式地存储关系；表示关系的能力强；在O(1)内插入、删除元素（只需改变结点的指针），便于动态管理内存。

缺点：空间开销大，占用空间较多，存储密度小；必须通过指针来访问元素，在O(n)内查找、修改元素。

索引存储

特点：存储空间是多段连续空间，在存储结点信息的同时，还建立附加的索引表，索引表由若干索引项组成。

优点：顺序和链式结合；数据检索速度快，保证数据的唯一性。

缺点：创建索引和维护索引需要时间，而且索引也会占用一定的物理空间；对数据增删查改的同时也要对索引进行维护。

哈希存储

特点：又称散列存储，数据元素的存储位置和关键码（在数据结构中，指的是数据元素中能起标识作用的数据项）之间有着确定对应关系，其基本思想是由结点的关键码值决定结点的存储地址，除了用于查找外还可以用于存储，存储空间是连续空间。（有的HASH函数为取模函数）

优点：利用数据的某一特征访问和存储，访问速度快，在O(1)内遍历元素。

缺点：好的HASH很难；有时会产生冲突。

3. 什么是算法的时间复杂度和空间复杂度？大O表示法？

时间复杂度是一个函数，它定量描述了该算法的运行时间。空间复杂度定量描述了算法在运行过程中占用存储空间大小。

算法的时间复杂度通常用大O符号表述，定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。

4. 数据结构的复杂度O(1)是什么意思？

常数阶的复杂度，最低的时空复杂度，也就是耗时与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。

5. 什么是抽象数据结构？

抽象数据类型（Abstract Data Type,ADT）是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与它在计算机中的表示和实现无关。

6. 数据的基本单位和最小单位分别是什么？

最小单位是bit，即比特；基本单位是B，即字节，1字节等于8个比特。

7. 简述一个好的算法应该达到哪些目标？

正确性：算法的输出应该符合预期的结果，即算法应该在给定的输入条件下能够产生正确的输出。

可读性：算法应该易于阅读和理解，这样可以方便其他开发人员或团队成员进行代码的维护和修改。

高效性：算法应该在可接受的时间内完成任务，并且在处理大量数据时也能够快速有效地运行。

可扩展性：算法应该能够处理不同规模的数据和不同类型的问题，并且能够轻松地进行修改和扩展。

鲁棒性：算法应该具备较强的鲁棒性，即能够应对各种异常情况和输入错误，并且不会因为一些不可预测的情况导致程序崩溃或出错。

可重用性：算法应该能够在不同的场景和项目中被重复使用，这可以提高代码的可维护性和开发效率。

8. 算法的五个重要特征

输入、输出、有穷性、确定性和可行性

第二章 线性表 栈 队列 串 数组

1. 线性表和顺序表以及链表的区别

顺序表与链表均属于线性表，只是在逻辑结构和存储方式上有所不同。

顺序表：线性表采用顺序存储的方式存储就称之为顺序表，顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

链表：线性表采用指针