108639 Final Review

1. 以Niklus Wirth的观点，程序等于什么?
   程序 = 数据结构 + 算法

2. 算法的重要特性
   有穷性 确切性 输入 输出 可行性

3. 好算法的标准
   正确性 可读性 健壮性 高效率低存储

4. 线性结构的特点
   （线性表的逻辑特性）
   a. 只有一个表头元素，表头元素没有前驱
   b. 只有一个表尾元素，表尾元素没有后继
   c. 除表头和表尾元素外，其他元素只有一个直接前驱，也只有一个直接后继

5. 线性结构与非线性结构的区别
   线性结构中的元素具有一对一的关系，而非线性结构不是。
   非线性结构中，至少存在一个元素，他具有两个或者两个以上的前驱或后继。

6. 列出所学过的线性结构与非线性结构
   线性结构：线性表，栈，队列，串，一维数组。
   非线性结构：树，图，广义表，多维数组。

7. 头指针、头结点、首元结点的区别
   a.头指针：指向单链表的第一个结点的指针。如果单链表有头结点，则头指针指向头结点；如果单链表没有头结点，则头指针指向第一个首结点。
   b.头结点：在单链表第一个元素结点之前设置的一个结点，数据域可以不存任何信息，指针域指向单链表的第一个元素结点。（为了操作方便，单链表一般都有）
   c.首元结点：单链表中第一个存储数据的结点。

8. 带头结点和不带头结点的线性链表的区别
   A. 带头结点的线性链表，头指针指向头结点；不带头结点的线性链表，头指针指向首元结点。
   B. 前者判空时，head->next == NULL ;后者，head == NULL
   C. 在“增删改查”操作中的区别：（在首元结点位置中，存在差异）

a. 增：后者，插入到链表的开头：
x->next = head; head = x;
插入到链表其他位置：(其中p为待插入位置的前一位)
x->next = p->next; p->next =x ;
b.删：后者，删除链表的开头：
temp = head; head = head ->next; free(temp);
删除链表的其他位置:(其中p为待删除位置的前一位)
temp = p->next; p->next = temp ->next; free(temp);

9. 单链表、双链表、循环链表的区别及各自的优缺点
   A. 单向链表：每个结点中只包含“同一个方向上的”一个指针域
   优点：（相较于数组，链表的优点）插入和删除的时候不需要移动大量元素。
   缺点：指针只能单方向移动。
   B.双向链表：每个结点有两个指针域，一个指向直接后继，一个指向直接前驱。
   优点：查找直接前驱时，较单向链表方便，因有指针直接指向直接前驱
   缺点：存储密度低，插入删除操作需要修改多个指针域。
   C.循环链表：最后一个结点的指针域指向头结点
   优点：
   缺点：

10. 栈和队列是什么样的线性表
    栈和队列是运算受限的线性表，栈得先进后出，队列得先进先出。

11. 指出顺序线性表、顺序栈、顺序队列的区别。

12. 举出几个栈和队列的实例及用栈和队列所能解决的问题
    队列实例：“排队买票”。栈实例：“握式子弹夹”
    队列能解决的问题：树的层次遍历；解决主机与外部设备之间速度不匹配的问题（打印机与缓冲区）；解决由多用户引起的资源竞争问题（CPU的资源竞争）。
    栈能解决的问题：后缀式求值；函数调用栈；

13. 指出通常解决队列，栈的溢出时所能用到的方法
    队列：循环队列，链队列
    栈：链栈，（多栈共享）

14. 循环队列的循环是怎样实现的
    用取模运算实现循环

15. 给出对称矩阵、三角矩阵的节省内存的存贮结构并写出相应的输入、输出算法。
    存贮结构： 一维数组
    对称矩阵(下标从1开始)： loc(a_ij) = loc(a₁₁) +loc(i(i-1)/2 +j -1)L i>=j
    loc(a_ij) = loc(a₁₁) +loc(j(j-1)/2 +i -1)L i<j
    下三角矩阵(下标从1开始）： loc(a_ij) = loc(a₁₁) +loc(i*(i-1)/2 +j -1)L i>=j
    loc(a_ij) = 0 i<j
    对角矩阵(三对角，下标从1开始)：loc(a_ij) = loc(a_{11)+(2i + j -3) i-1 <=j <= i+1}

16. 给出稀疏矩阵的节省内存的存贮结构并写出相应的输入、输出算法
    三元组表：
    十字链表：

17. 用十字链表存贮稀疏矩阵时，矩阵的每个元素同时在几条链上，分别被称为什么链？
    两条链；行链和列链。

18.给出树的不同的几种表示形式
（1） 层次表示法 （2）广义表表示法 （3）嵌套表示法 （4）凹入法表示法

19. 在二叉树的第i层上至多有多少个结点，深度为K的二叉树至多有多少个结点
    2^i-1 ; 2^k-1

20. 在一颗二叉树中,其叶子结点数n₀和度为二的结点数n₂之间的关系。
    n0 = n2 +1

21. 有n个结点的完全二叉树的深度。
    depth = log₂(向下取整) +1

22. 在二叉树的顺序存贮结构中如何求结点的双亲、孩子？
    下标从1开始 双亲： i/2（向下取整）
    左孩子 2i
    右孩子 2i+1

23. 有n个结点的二叉树用二叉链表存贮时有多少个空链域，用三叉链表存贮时有多少个空链域。
    n+1 ； n+2 ；

24. 为什么可在不增加指针域的情况下，对二叉树进行线索化，线索化的目的是什么？
    因为二叉树本身具有n+1个空链域。线索化是为了方便遍历树。

25. 对于已线索化的二叉树如何识别指针域是指向孩子还是指向其后继结点？
    增加标志域。

26. 树的几种存贮结构(双亲表示法、孩子表示法、孩子兄弟表示法)的优缺点，各自适应的运算。
    双亲表示法：便于查找双亲，但是找孩子难
    孩子表示法：涉及孩子的操作容易，涉及双亲的难
    孩子兄弟表示法：

27. 哪种存贮结构可将森林转为二叉树。此种结构各域的注释。说明在这个结构中怎样找到森林的n棵树。
    孩子兄弟表示法；左指针是第一孩子，右指针是兄弟（森林中树的根结点的右指针为另一棵树）；根结点的第n代右孩子。

28. 树的先根遍历、后根遍历对应其二叉树的哪种遍历，森林的先根遍历、中根遍历对应其二叉树的哪种遍历？
    树和森林的先根遍历对应二叉树的先序遍历；树和森林的后序遍历对应二叉树的中序遍历。（在考研数据结构中，森林的中根遍历和后序遍历是一回事）

29. 写算法求树中结点的度；树的度；树中的叶子结点数；树中的非终端结点数；树中某结点的兄弟、祖先、子孙、层次、堂兄弟；树的高度；森林中树的数目。

30. Huffman树能够解决的问题是什么？
    数据通信中的数据压缩编码问题

31. 何为完全图、稀疏图、稠密图
    完全图(顶点数为n)：对有向图来说，边数为n(n-1);对无向图来说，边数为n(n-1)/2；
    稀疏图：边数较少的图（e << n） （题目会规定额度）
    稠密图：边数较多的图

32. 写算法求无向图中结点的度；有向图中结点的入度和出度。
    无向图：邻接矩阵的一行或一列的数值和，代表对应定点的度。
    有向图：邻接矩阵的行代表对应顶点的出度，列代表入度

33. 图的数组表示法、邻接表存贮结构各自的优缺点，适应的运算
    图的数组表示法（邻接矩阵表示法）： 二维数组存储图
    优点：容易求各个顶点的度
    缺点：当图为稀疏图时浪费空间
    图的邻接表表示法：
    优点：容易找到第一个邻接点和下一个邻接点

34. 最小生成树的实际应用背景

    
    image.png

35. 什么图适合用Prim算法求最小生成树，什么图适合用Kruskal算法求最小生成树。
    Prim算法适用于稠密图；Kruskal算法适用于稀疏图。

36. 图示用 Prim算法及 Kruskal算法求最小代价生成树的过程。

    
    Prim算法
    Kruskal算法

37. 举例简述“拓扑排序”所解决的实际问题
    流程图，施工流程图，课程决定的优先权。

38. 请图示“拓扑排序”的过程。

    
    image.png

39. 举例简述“关键路径”所解决的实际问题。
    一个工程的并行的进行过程
    （1） 完成整个工程至少需要多少时间；
    （2） 哪些活动是影响工程的关键。

40. 顺序查找、折半查找、分块查找算法适合的关键字结构。
    顺序查找对关键字是否有序无要求，但是基于时间复杂度问题，关键字数量应该尽量小。（ASL1 = (n+1)/2 ; ASL2 = n）
    折半查找要求关键字是有序的。（平均查找长度近似为log₂(n+1) -1）
    分块查找要求块与块之间必须按照关键字大小有序排列。

41. 怎样从二叉排序树得到有序表。
    中序遍历

42. 已知长度为n的表，按表中元素顺序构造二叉平衡树，图示构造过程。
    在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。

43. 各种查找算法的平均时间复杂度。

    
    

44. 为一组关键字构造哈希函数并建立哈希表。

45. 指出希尔排序，归并排序，快速排序，堆排序，基数排序中稳定的排序方法，并对不稳定的举出反例。
    稳定的：归并排序，基数排序。
    不稳定的反例：

46. 堆排序算法选用什么样的存贮结构，按此算法得到的有序表是递增还是递减的。图示建堆过程。
    存贮结构：完全二叉树。
    若是小顶堆就是递增的，若是大顶堆就是递减的。
    建堆过程：

    
    image.png

47. 藉助于“比较”进行排序的算法在最坏情况下能达到的最好的时间复杂度是什么?
    n log₂n

48. 指出直接插入排序，冒泡排序，快速排序，堆排序，基数排序算法各适合的关键字结构。
    直接插入排序：整个序列已经基本有序。
    冒泡排序：整个序列已经基本有序。
    快速排序：待排序列越接近无序，本算法效率越高。（越接近有序，本算法效率低）
    堆排序：堆排序适合的场景是关键字数很多的情况，典型的例子是从10 000个关键字中选出前10个最小的。
    基数排序：基数排序适合的场景是序列中的关键字字数很多，但组成关键字的取值范围较小，如数字0~9是可以接受的。

49. 指出各种排序算法的平均时间复杂度、最坏情况的时间复杂度。

50. 请对学习<<数据结构>>这门课程进行全面总结。