数据结构期末总复习

一、基本要求

掌握的知识点如下：

线性表、顺序表和链表。要求掌握线性表的概念，两种存储结构的实现、优缺点及两种存储结构上的基本操作。

栈与队列。要求掌握栈和队列的概念，顺序栈、链栈的操作，栈的应用，循环队列、循环链队列的操作。

串的基本运算和模式匹配。掌握串的基本运算的含义，了解模式匹配算法和时间复杂度。 多维数组和广义表。掌握多维数组及特殊矩阵的地址公式，广义表的运算和存储。 树和二叉树。树、二叉树的定义、术语,二叉树的性质、存储、遍历、应用,线索二叉树的概念，树与二叉树的关系。

图的存储及其操作。掌握图的定义、术语，图的存储，图的遍历、图的操作（最小生成树、拓扑排序、关键路径、最短路径）概念。

表和树的查找。

掌握表和树查找的概念、平均比较次数，二叉排序树和平衡二叉树的插入、删除，了解B-树的定义。

Hash技术。掌握哈希表构造、解决冲突的方法及哈希表的查找。

排序算法。掌握直接插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并排序和希尔排序算法和时间复杂度，了解基数排序、外排序的概念和算法。

二、基本内容

第一章 数据结构与算法概念

数据结构：数据结构DS=(A,R)，其中A是数据元素的非空有限集合，R是定义在A上关系的非空有限集合。结构就是元素之间的关系。

算法：算法就是解决问题的方法和步骤。

算法的时间复杂度：算法中语句重复执行次数（或称语句频度）或算法中基本操作次数，一般用数量级符号○来描述。

抽象数据类型：抽象数据类型ADT=(A,R,P)，其中A是数据元素的非空有限集合，R是定义在A上关系的非空有限集合，P是(A，R)上非空的基本操作集合。

【例1-1】 求表2-1中程序段的各语句的语句频度和时间复杂度。

时间复杂度T(n)为所有语句频度之和，即T(n)=n+1+2 =

当n→∞时， 所以时间复杂度T(n)=○(n)

第二章 线性表

线性表的定义：线性表是n(n≥0)个元素的有限序列，当n=0，则称为空表；当n>0时，线性表通常表示为（a1 ，a2 ，．．．，an），其中a1无前驱，an无后继，其余结点有且只有一个前驱和一个后继。 2