数据结构总结心得

1. 在数据结构数据的概念中，数据的最小单位是数据项

2. 数据结构中的存储结构分为顺序存储结构和链式存储结构
   从逻辑上可分为线性结构和非线性结构

3. 带头结点的单链表head为空的条件是 head->next=NULL

4. 在具有n各个元素的循环队列中，队满时具有n-1个元素

5.栈的入栈操作和出栈操作都是在栈顶进行的

6.对哈希函数来说，具有相同函数值这种现象称为冲突

7.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为插入排序

8.任何一个C程序都由主函数和若干个被调用的其它函数组成

9.线性表L在需不断对L进行删除，插入情况下适用于使用链式结构实现

10.在单链表中，要将s所指结点插入p所指结点之后，其语句应为:s->next=p->next;p->next=s;

11.链表不具有的特点是：可随机访问任一元素

12. 正常情况下，删除非空的顺序存储结构的栈的栈顶元素，栈顶指针top的变化是top=top-1

13. 队列的先进先出特征是指 最后插入队列的元素总是最后被删除
      最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是rear=front
      队满的条件是（rear+1）%n=front

14. 简述下列概念：

数据元素：
数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：
是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：
是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N{0，+-1，+-2，...}，字母字符数据对象是集合C={'A','B'..'Z','a','b'...'z'}，学生信息表也可是一个数据对象。

数据结构：
是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：是数据结构的抽象描述，描述了数据元素之间的关系以及对这些数据元素进行操作的规则

存储结构：是数据结构在计算机内存或外部存储器上的具体表示形式，也称为物理结构

15. 试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系
例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等(1分)。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列(1分)。
对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继(1分)。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构(1分)
这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构(1分);如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构(1分)
即相同的逻辑结构，可以对应不同的存储结构。

16. 哈希表存储的基本思想是：
以数据表中的每个记录的关键字k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。

哈希函数的构造方法：除留余数法
用线性探测法将哈希表补充完整：

17. 哈希表的尺寸最好是一个质数,最小的质数尺寸是17。

18. 一个算法的效率可分为空间效率和时间效率

19. 队列的插入操作（入队）是在队尾，删除操作（出队）是在队头进行的。

20. FIFO：First Input First Output

21. 栈是一种先进后出的线性表，队列是一种先进先出的线性表

22. 若一个线性表中最常见的操作是取第i个元素和找第i个元素的前驱元素，则采用 顺序表 存储方式最节省时间

23. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的逻辑结构

24. 在含n个结点的顺序表中，算法的时间复杂度Tn=O()
访问第i个结点（1 <= i <= n）和求第i个结点的直接前驱（2 <= i <= n）:     0(1)
在第i个结点后插入一个新结点（1 <= i <= n）：O(1)
删除第i个结点（1 <= i <= n）：O(n)
将n个结点从小到大排序：
冒泡排序、插入排序、选择排序的时间复杂度为O(n^2)

25. 线性表的顺序存储结构是一种 随机存取 的存储结构

26. 判定一个顺序栈S（栈空间大小为n）为空的条件是 S->top=S->base

27. 用链地址法处理冲突，不会引起二次聚集现象

28. 直接插入排序是稳定的排序方法

29. 解决普通队列假溢出的方法是采用循环队列

30. 算法是解决问题的有限运算序列

31. 数据结构在计算机内存中的表示是指 数据元素之间的关系

32. 请总结顺序表的特点；在顺序表中插入和删除数据元素时，如何移动元素(或绘制适当的图例予以说明)?
①连续存储：顺序表中的元素在内存中是连续存储的，每个元素占据固定大小的内存空间，使得访问和操作元素更加高效。
②随机访问：由于元素在内存中连续存储，顺序表支持通过下标随机访问元素，时间复杂度为O(1)。这使得顺序表在需要频繁访问元素位置的场景中具有优势。
③插入和删除效率较低：在顺序表中的插入和删除操作通常需要移动其他元素，因此其时间复杂度为O(n)，其中n为元素的数量。尤其是在中间和开头插入或删除元素时，效率相对较低。
④静态大小：顺序表的大小通常在创建时就确定，难以动态调整。如果需要动态操作数据集合，可能需要重新分配更大的内存空间，并进行数据迁移。
⑤适用于随机访问和读取操作：由于支持常数时间的随机访问，顺序表适用于需要频繁访问、迭代或查找元素的场景，如排序算法等。
总的来说，顺序表适用于对数据的随机访问要求较高、元素集合相对稳定且规模不会经常改变的场景。然而，在需要频繁插入和删除操作的情况下，可能不是最佳选择，此时链表等数据结构可能更加合适。

在顺序表中插入或删除数据元素时，需要移动其他元素来保持元素的顺序性。移动元素的方式主要包括以下几种：
①在指定位置插入元素：当需要在顺序表的指定位置插入元素时，需要将插入位置后的所有元素向后移动一个位置，让出位置给新插入的元素。
②在指定位置删除元素：当需要在顺序表的指定位置删除元素时，需要将删除位置后的所有元素向前移动一个位置，覆盖被删除的元素。

具体来说，以在指定位置插入元素为例，移动元素的步骤如下：
①从最后一个元素开始，将其移动到下一个位置，直到需要插入的位置。
②将需要插入的元素放入指定位置。
移动元素的时间复杂度为O(n)，其中n为元素的数量

33.折半查找法的一般过程：
① 首先确定整个查找区间的中间位置 mid = (left + right)/2 。
② 用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后（右）半个区域继续进行折半查找；若小于，则在前（左）半个区域继续进行折半查找。
③ 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。

34.某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。

35.若一个结点是某二叉树的中序遍历序列的最后一个结点，则它（不一定）是该树的前序遍历序列中的最后一个结点。

36.虽然信息项序列的顺序不一样，但依次生成的二叉排序树却（不一定）是一样的。

37.将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点（不一定）是兄弟。

38.一棵有124个结点的完全二叉树，其叶结点个数是确定的。