青岛农业大学海都学院软件技术专业15级数据结构笔记整理

木来

数据结构是重中之重,无论是专升本中C语言科目占15分,还是考研必考,都有足够的理由去反复读,最近还打算把数据结构课本重新看一遍。

在此之前,先重新通读一遍我自己整理的数据结构笔记~

把我凭记忆想起来的15级的数据结构考试原题先整理一下:

一、小题

1、无向完全图怎么求边数:

2、循环队列中已知队头指针、队尾指针还有长度,怎么求满边

3、邻接矩阵中哪种情况是对称的:

4、树和二叉树的分类

5、已知首地址、存储单元数量,求地址

6、折半查找法的两个条件

7、图遍历分为广度和深度,其中广度遍历什么辅助存储结构:遍历类似于子树的按层次遍历的过程

8、连通图最小生成树:

9、数据结构的四类结构:集合、线性结构、树形结构、图状结构

10、栈元素的特点及其进出原则;

    队列的特点及其进出原则

11、深度为K的二叉树,最多有2^K - 1个节点

12、对任何一颗二叉树T,起终端节点数为N,度为2的节点数为N2,则关系是什么

13、有向图的度是什么和什么的和

二、简答

1、画邻接表

2、根据权值画哈夫曼树

3、克鲁斯卡尔算法,最小生成树,要有过程

4、二叉树的中序遍历、递归算法

5、树转换成二叉树,然后写出先中后序遍历结果

 以下是我自己整理的学习笔记:

 

1.   数据的含义  P4  【填空】

2.   数据的基本单位  P4  【填空】

3.   一个数据可由若干个数据项组成  P4 【填空】

4.   数据的不可分割的最小单位是什么?  P4  【填空】

5.   数据结构的含义  P5

6.   数据结构的基本结构  P5【必考】

7.   数据元素之间的关系在计算机中有两种不同的表示方法,并由此得到两种不同的数据结构,分别是什么?P6【重点】

8.   引用参数以&打头,除可提供输入值外,还将返回操作结果。P8

9.   Struct是一个结构体  P9

10. 算法的五个特性  P13【重点】

11. 算法设计的要求 P13-14【重点】

12. 度量一个程序的执行时间的方法  P14

13. 时间复杂度的含义及公式  P15

14. 时间复杂度的计算 P15【必考】

15. 空间复杂度的公式及含义  P17

16. 在算法中重复执行的次数,作为算法运行时间的衡量准则。

17. 线性表是最常用且最简单的一种数据结构  P18

18. 一个线性表是n个数据元素的有限序列  P18

19. 一个数据元素可以由若干个数据项组成  P18

20. 指针是一个特殊的变量,指针指向的是内存,一般变量存的是数据本身  P19

21. 内存以字节为单位

22. 变量前加上&,拿到的是变量的内存地址

23. 变量前加*,表明是指针

24. *的作用:一是*的作用是取值,二是标识此变量是一个指针

25. 2-1 P20

26. 2-2 P20-21

27. Typdef是声明新的类型名来替代原有的类型名(自定义数据类型),新声明的结构体名在大括号后面

28. P22的代码及P22-23页的说明

29. #define是预处理宏定义命令,具体作用是方便定义和修改

30. Status表示状态,代表方法的返回类型 P23

31. 方法名后跟_sq的是顺序表,如果后跟_l是链式表

32. malloc是动态分配内存的关键字   P23

33. P23上面的顺序表初始化代码

34. (ElemType*)(int*),作用就是获取变量或者内存的首地址

35. Exit(overflow)是退出程序。

36. 方法前面若有*,即有一个指针指向方法的基址

37. 在顺序表中添加元素的代码  P24【重点】

38. 在顺序表中删除元素的代码  P24【重点】

39. realloc是重新分配内存空间的关键字

40. 插入一个元素的期望值是n/2  P25

41. 删除一个元素的期望值是n-1/2 P25

42. 顺序表定位元素的代码  p25-26【重点】

43. 顺序表的合并代码  P26【重点】

44. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)  P27

45. 结点包括两个域,一个是数据域、一个是指针域  P27

46. 元素+指针=结点

47. P28的线性表的单链表存储结构

48. 链式表的头结点有指针没元素,尾元素没有指针但有元素。

49. 单链表的查找元素的代码  P29【重点】

50. typdef是自定义一个新的结构

51. 单链表新增元素的代码 P29-30【重点】

52. 单链表删除元素的代码  P30【重点】

53. 从表尾到表头逆向建立单链表的算法 P30-31【重点】

54. 归并两个单链表的算法  P31

55. 循环链表是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针指向头结点,整个链表形成一个环。P35

56. 双向链表的含义  P35

57. 线性表中双向链表的存储结构 P35-36

58. 双向链表的增加元素的代码  P36【重点】

59. 双向连表的删除元素的代码  P37【重点】

60. 栈的定义  P44

61. P44的栈示意图

62. 队列的数据进出顺序是先进先出,后进后出

63. 对顺序栈的定义  P46

64. 栈的顺序存储表示  P46

65. 所有的递归都是由栈实现的

66. 初始化一个空栈的代码 P47【重点】

67. 获取栈顶元素的代码  P47【重点】

68. 增加栈元素的代码  P47【重点】

69. 删除栈元素的代码  P47【重点】

70. 栈中的元素进出顺序是先进后出,后进先出【重点】

71. 栈还有一个重要应用是在程序设计语言中实现递归【重点】 P54

72. 队列是一种先进先出的线性表  P58

73. 队列的示意图  P59

74. 栈和队列是逻辑结构

75. 所有的线性结构都可以使用顺序和链式来实现

76. 初始化队列代码  P62【重点】

77. 销毁队列代码  P62【重点】

78. 插入队列元素代码  P62【重点】

79. 删除队列元素代码  P62【重点】

80. 循环队列的初始化、插入和删除元素的代码 P64-65【重点】

81. 循环队列的出现是因为顺序循环队列存在假溢出

82. 串的索引方法代码 P72

83. 第六章是重点!

84. 先序、中序、后序遍历二叉树的步骤 P128【重点】

85. 先序遍历二叉树的递归算法 P129【重点】

86. 中序遍历二叉树的非递归算法 P130【重点】

87. 构造二叉树的算法 P131【重点】

88. 森林与二叉树的转换 P137-138【重点】

89. 树和森林的遍历 P138-139【重点】

意见反馈