2011-2012-1数据结构期末复习重点
2011/12/22 注：以第4章-第9章为主，红色表示要求掌握的算法。
Chapter 1 Basic Concepts
1．什么是算法？
2．理解Ω、O、Θ、o的含义。
3．对顺序、条件、单循环、循环嵌套语句进行复杂度分析的一般规则。
4．能够运用大O的复杂度分析的方法，对算法进行复杂度分析，并掌握检验分析结果的方法和测量算法运行时间的方法。
Chapter 3-4 Stacks and Queues, Linked Lists
1．ADT的定义。
2. 单链表表示Lists时的数据结构定义、插入操作和删除操作的实现、时间复杂度分析。
3. List的链表表示中为什么要引入头节点（head node）？
4. 双向循环链表表示Lists时的数据结构定义、插入操作和删除操作的实现、时间复杂度分析
5. 什么叫栈，栈有什么特点？
6. 什么叫队列，队列有什么特点？
7. 循环队列的数据结构定义，循环队列中为什么需要有一个单元空着不用？
8. 循环队列中rear、front 初始值是什么？循环队列判空和判满的条件是什么？
算法：
1. 单链表表示List时的数据结构定义、插入操作和删除操作的实现。
2. 双向循环链表表示List时的数据结构定义、插入操作和删除操作的实现。
3. 循环队列表示队列时的进队列和出队列操作。
Chapter 5 Trees
1.二叉树的基本术语
结点的度、树的深度、双亲结点、孩子结点、兄弟结点、叶子结点、路径、路径长度、结点的深度、结点的高度。
2.树
了解树的树的孩子兄弟表示法和双亲表示法，
（1）能将其与二叉树进行互换;
（2）对于给定的某树，可以画出其孩子兄弟表示法示意图；
（3）对于给定的某树，可以画出其双亲表示法示意图。
3.二叉树：
（1）二叉树的5条性质。
（2）二叉树的存储结构
①数组表示法，对于给定的二叉树，能画出其数组表示示意图，反过来，给定二叉树的数组表示时的存储情况，可以画出该二叉树。
②二叉链表表示法，对于给定的二叉树，能画出其二叉链表表示示意图
③线索化二叉树，对于给定的二叉树，能画出其先序、中序和后序线索化二叉树示意图。（3）二叉树的遍历
①对于给定的二叉树，能给出其先序、中序、后序和层次遍历结果。
②给定某二叉树的中序、先序（或后序）序列能画出该二叉树。
③掌握二叉树的中序非递归算法和层次遍历算法。
④掌握求二叉树叶子结点数、结点数、高度或深度等递归算法。
4. Huffman树
（1）掌握Huffman树的构造方法,了解前缀编码的含义;
（2）能用Huffman树来设计字符的不等长编码。对给定的某英文文本，能利用Huffman树设计其各字符的编码，并能计算总编码长度。
5. 二叉搜索树(BST)
（1）二叉搜索树(BST)的定义，对BST进行中序遍历后可得一有序序列；
（2）掌握二叉搜索树的插入、查找算法；
（3）对给定的整数序列，能构造出BST树，并能删除其上的某个结点。
6. A VL树
（1）对给定的整数序列，能构造出A VL树。
算法：
1. 二叉树的中序非递归算法;
2. 二叉树的层次遍历算法;
3. 二叉树叶子结点数、结点数、高度或深度等递归算法;
4.二叉搜索树的插入、查找算法。
Chapter 6 Graphs
1.图的基本术语：
有向图，无向图，有向完全图，无向完全图，邻接点，子图，路径，路径长度，简单路径，回路，连通，强连通，连通分量，强连通分量，生成树，顶点的度，顶点的度与边数的关系。
2.图的存储结构：
（1）图的邻接矩阵表示；
（2）图的邻接表表示；
（3）图的逆邻接表表示；
能对给定图的逻辑结果画出其相应的存储结构，或根据某图的存储结构画出图的逻辑结构。
3.图的遍历
（1）图的深度优先搜索算法；
（2）图的广度优先搜索算法；
（3）对给定的图，能给出从某个顶点出发的dfs和bfs遍历结果。
4.了解Prim和Kruskal算法思想，了解它们的时间复杂度和适用场合，对给定的某边带权值的无向网，能画出相应的最小生成树，并能计算总代价。
5.对给定的某有向无环图，能给出拓扑排序序列。
算法：
1. 图的深度优先搜索算法;
2. 图的广度优先搜索算法;
3. 求图中某个顶点的邻接点;
4. 求图中某个顶点的度。
Chapter 7 Sorting
1. 掌握直接插入排序的算法思想，了解其适合的场合。
2. 掌握希尔算法思想，能用该排序算法对给定的整数序列进行排序，理解h k-sort。
3. 掌握大顶堆和小顶堆的概念，掌握堆排序算法，能用该排序算法对给定的整数序列进行排序，并能判断某序列是否为堆并调整为堆。
4. 掌握归并排序的算法, 能用该排序算法对给定的整数序列进行排序，能给出各趟结果。
5. 掌握快速排序算法，能用来对实际的例子进行排序。
6. 能对直接插入排序、希尔排序、堆排序、归并排序和快速排序进行基于时间和空间复杂度的比较，了解它们各自的适用场合。
算法：
1. 堆排序算法
2. 快速排序算法
3. 归并排序算法
Chapter 7 hashing
（1）了解哈希表的基本概念：哈希函数、哈希表、冲突，装填因子(loading density)及其意义。
（2）掌握常用的哈希函数构造方法和开放定址法的处理冲突方法，并能构造哈希表。
例如：选取哈希函数H（k）=（3k）MOD11 (可换成其他函数)。用开放定址法处理冲突，f(i,k)= i((7k）MOD10+1)(i=1，2，3，…)(可换成是线性探测和二次探测)。试在0~10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）造哈希表，并求等概率情况下查找成功时的平均查找长度。
（3）能计算查找成功时的平均查找长度。
《数据结构》实验指导书 贵州大学 电子信息学院 通信工程
目录 实验一顺序表的操作 (3) 实验二链表操作 (8) 实验三集合、稀疏矩阵和广义表 (19) 实验四栈和队列 (42) 实验五二叉树操作、图形或网状结构 (55) 实验六查找、排序 (88) 贵州大学实验报告 (109)
实验一顺序表的操作 实验学时：2学时 实验类型：验证 实验要求：必修 一、实验目的和要求 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。 2、以线性表的各种操作（建立、插入、删除等）的实现为重点。 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现。 二、实验内容及步骤要求 1、定义顺序表类型，输入一组整型数据，建立顺序表。 typedef int ElemType; //定义顺序表 struct List{ ElemType *list; int Size; int MaxSize; }; 2、实现该线性表的删除。 3、实现该线性表的插入。 4、实现线性表中数据的显示。 5、实现线性表数据的定位和查找。 6、编写一个主函数，调试上述算法。 7、完成实验报告。 三、实验原理、方法和手段 1、根据实验内容编程，上机调试、得出正确的运行程序。 2、编译运行程序，观察运行情况和输出结果。 四、实验条件 运行Visual c++的微机一台 五、实验结果与分析 对程序进行调试，并将运行结果进行截图、对所得到的的结果分析。 六、实验总结 记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等，并将其写入实验报告中。
【附录----源程序】 #include 第二章线性表 一、顺序表和链表的优缺点 1.顺序表 定义：用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即：在顺序表中逻辑结构上相邻的数据元素，其物理位置也是相邻的。 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素（平均约需移动一半结点，当n很大时，算法的效率较低） 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 2.链式存储结构 定义：由分别表示a1,a2,…,a i-1,a i,…,a n的N 个结点依次相链构成的链表，称为线性表的链式存储表示 优势： (1)能有效利用存储空间； 动态存储分配的结构，不需预先为线性表分配足够大的空间，而是向系统“随用随取”，在删除元素时可同时释放空间。 (2)用“指针”指示数据元素之间的后继关系，便于进行“插入”、“删除”等操作； 插入或删除时只需要修改指针，而不需要元素移动。 劣势： (1)不能随机存取数据元素； (2)丢失了一些顺序表的长处，如线性表的“表长”和数据元素在线性表中的 “位序”，在单链表中都看不见了。如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。 二、单链表中删除一个节点和插入一个节点的语句操作，p29 1.插入元素操作 算法基本思想：首先找到相应结点，然后修改相应指针。 假定在a，b之间插入结点X，s指向X, p指向a，指针修改语句为： s->next=p->next; p->next =s; 2.删除元素操作 算法基本思想:首先找到第i-1 个结点，然后修改相应指针。 删除b结点，其中，P指向a，指针修改语句为：p->next=p->next->next； 三、单链表的就地逆置习题集2.22 算法的基本思想：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个元素结点）。 算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针p用来指向当前结点，p为空时结束。 void reverse (Linklist H){ LNode *p; p=H->next; /*p指向第一个数据结点*/ H->next=NULL; /*将原链表置为空表H*/ while (p){ q=p; p=p->next; q->next=H->next; /*将当前结点插到头结点的后面*/ H->next=q; } } 第三章栈和队列 一、栈和队列的特性 1.特点 栈必须按“后进先出”（LIFO）的规则进行操作，仅限在表尾进行插入和删除的操作。 队列（FIFO）必须按“先进先出”的规则进行操作，队尾插入，队头删除。 二、循环队列为空和满的判定方法，p63 队空条件：front == rear; 队满条件：(rear + 1) % maxSize == front 数据结构设计与技巧讲义 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 【知识点解析】 1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 《数据结构(C语言版)》复习重点 重点在二、三、六、七、九、十章，考试内容两大类：概念，算法 第1章、绪论 1.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2.数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构 4.逻辑结构：是数据元素之间的逻辑关系的描述。 5.物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。 其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构6.算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 其5个重要特性：有穷性、确定性、可行性、输入、输出 7.时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n))；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如：(a){++x;s=0;} (b)for(i=1;i<=n;++i){++x;s += x;} (c)for(j=1;j<=n;++j) for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的语句的频度分别为1、n和n2，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n2)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。 8.空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。 第2章、线性表 1.线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。 2. 线性表的顺序存储结构：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。 存储位置计算：假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+(i-1)*L式中LOC(a1)是线性表第一个元素a1的存储位置，通常称做线性表的起始位置或基地址。 3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。 《数据结构》实验指导书 专业：____________班级：_______________组序：_____________ 学号：______________姓名：_______________ 中国矿业大学管理学院 2014 年9 月 上篇程序设计基础 实验一 Java编程环境 【实验目的】 1．掌握下载Java sdk软件包、Eclipse软件的安装和使用方法 2．掌握设置Java程序运行环境的方法 3．掌握编写与运行Java程序的方法 4．了解Java语言的概貌 【实验内容】 一 JDK下载与安装 1. 下载JDK 为了建立基于SDK的Java运行环境，需要先下载免费SDK软件包。SDK包含了一整套开发工具，其中包含对编程最有用的是Java编译器、Applet查看器和Java解释器。下载链接 https://www.doczj.com/doc/6314990877.html,。 2.安装SDK 运行下载的JDK软件包，在安装过程中可以设置安装路径及选择组件，默认的组件选择是全部安装，安装成功后，其中bin文件夹中包含编译器（javac.exe）、解释器（java.exe）、Applet查看器（appletviewer.exe）等可执行文件，lib文件夹中包含了所有的类库以便开发Java程序使用，demo文件夹中包含开源代码程序实例。 安装成功后，文件和子目录结构如图1所示。其中bin文件夹中包含编译器（javac.exe）、解释器（java.exe）、Applet查看器（appletviewer.exe）等可执行文件，lib文件夹中包含了所有的类库以便开发Java程序使用，sample文件夹包含开源代码程序实例，src压缩文件中包含类库开源代码。 图1 二．设置环境变量 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 数据结构以及C语言常问与难点 1.序言 2.常问与难点，为避免重复发帖，特设此帖并置顶，以供浏览查阅。 3.内容主要是将本版的好帖子收集起来，并加以整理，仅给出知识点分析与问题解答，并不给出原帖链接，致歉。 4.本版中的好东西会慢慢添加进来（各位版主齐心协力，每天添加一个知识点，用不了多久就会很强大），本帖观点只 是各位版主和我个人的分析，不一定尽善尽美，但一定是尽心尽力。各位热心研友如有修正和补充，请在回复中说明。 5.特代表研友感谢各位版主的辛勤奉献，代表版主感谢热心研友对王道的支持（呵呵）。特别地，祝备考10的研友们一 切顺利，考上理想的学校。珍惜时间，努力才是王道。 1.目录，共占用一个代码区 2. 3. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 4.typedef struct LNode{ 5. ElemType data; 6. struct LNode *next; 7.} LNode, *LinkList; 8. 9. 2.符号&的含义，指针进阶。涉及知识点：引用机制，实参与形参，C语言中地址与指针（以及指向指针的指针），指 针的传递（暂不涉及数组与指针的知识，将在以后介绍）。 10. 11. 3.如下方式动态分配内存的全部细节解释。涉及知识点：动态分配内存，define，强制类型转换，malloc()，顺序 表存储结构，顺序表与数组，链表结点的内存分配，指针细节，附完整程序。 12.L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 复制代码 1.正文，每个问题占用一个代码区 复制代码 1. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 2.typedef struct LNode{ 3. ElemType data; 4. struct LNode *next; 5.} LNode, *LinkList; 6. 7.如下是一个最简单的结构体定义： 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 《数据结构》实验指导书 实验类别：课内实验实验课程名称：数据结构 实验室名称：软件工程实验室实验课程编号：N02070601 总学时：64 学分： 4 适用专业：计算机科学与技术、网络工程、物联网工程、数字媒体专业 先修课程：计算机科学导论、离散数学 实验在教学培养计划中地位、作用： 数据结构是计算机软件相关专业的主干课程，也是计算机软硬件专业的重要基础课程。数据结构课程实验的目的是通过实验掌握数据结构的基本理论和算法，并运用它们来解决实际问题。数据结构课程实验是提高学生动手能力的重要的实践教学环节，对于培养学生的基本素质以及掌握程序设计的基本技能并养成良好的程序设计习惯方面发挥重要的作用。 实验一线性表的应用（2学时） 1、实验目的 通过本实验，掌握线性表链式存储结构的基本原理和基本运算以及在实际问题中的应用。 2、实验内容 建立某班学生的通讯录，要求用链表存储。 具体功能包括： （1）可以实现插入一个同学的通讯录记录； （2）能够删除某位同学的通讯录； （3）对通讯录打印输出。 3、实验要求 （1）定义通讯录内容的结构体； （2）建立存储通讯录的链表结构并初始化； （3）建立主函数： 1）建立录入函数（返回主界面） 2）建立插入函数（返回主界面） 3）建立删除函数（返回主界面） 4）建立输出和打印函数（返回主界面） I）通过循环对所有成员记录输出 II）输出指定姓名的某个同学的通讯录记录 5）退出 实验二树的应用（2学时） 1、实验目的 通过本实验掌握二叉排序树的建立和排序算法，了解二叉排序树在实际中的应用并熟练运用二叉排序树解决实际问题。 2、实验内容 建立一个由多种化妆品品牌价格组成的二叉排序树，并按照价格从低到高的顺序 打印输出。 3、实验要求 （1）创建化妆品信息的结构体； （2）定义二叉排序树链表的结点结构； （3）依次输入各类化妆品品牌的价格并按二叉排序树的要求创建一个二叉排序树链表；（4）对二叉排序树进行中序遍历输出，打印按价格从低到高顺序排列的化妆品品牌信息。 实验三图的应用（2学时） 2018考研计算机：数据结构重难点及 复习建议 新东方在线推荐： 一、重难点解析和复习建议 数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。 当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。 下面我们来解析一下知识点： 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。 树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二 数据结构基础知识整理 *名词解释1、数据：是信息的载体，能够被计算机识别、存储和加工处理。 *2、数据元素：是数据的基本单位，也称为元素、结点、顶点、记录。一个数据元素可 以由若干个数据项组成，数据项是具有独立含义的最小标识单位。 *3、数据结构：指的是数据及数据之间的相互关系，即数据的组织形式，它包括数据的 逻辑结构、数据的存储结构和数据的运算三个方面的内容。 *4、数据的逻辑结构：指数据元素之间的逻辑关系，即从逻辑关系上描述数据，它与数 据的存储无关，是独立于计算机的。 *5、数据的存储结构：指数据元素及其关系在计算机存储器内的表示。是数据的逻辑结 构用计算机语言的实现，是依赖于计算机语言的。 *6、线性结构：其逻辑特征为，若结构是非空集，则有且仅有一个开始结点和一个终端 结点，并且其余每个结点只有一个直接前趋和一个直接后继。 *7、非线性结构：其逻辑特征为一个结点可能有多个直接前趋和直接后继。 *8、算法：是任意一个良定义的计算过程，它以一个或多个值作为输入，并产生一个或 多个值作为输出；即一个算法是一系列将输入转换为输出的计算步骤。 *9、算法的时间复杂度T(n)：是该算法的时间耗费，它是该算法所求解问题规模n趋向无穷大时，我们把时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度。 *10、最坏和平均时间复杂度：由于算法中语句的频度不仅与问题规模n有关，还与输入实例等因素有关；这时可用最坏情况下时间复杂度作为算法的时间复杂度。而平均时间复杂度是指所有的输入实例均以等概率出现的情况下，算法的期望运行时间。 *11、数据的运算：指对数据施加的操作。数据的运算是定义在数据的逻辑结构上的，而 实现是要在存储结构上进行。 *12、线性表：由n(n≥0)个结点组成的有限序列。其逻辑特征反映了结点间一对一的关 系（一个结点对应一个直接后继，除终端结点外；或一个结点对应一个直接前趋，除开始结点外），这是一种线性结构。 *13、顺序表：顺序存储的线性表，它是一种随机存取结构。通过将相邻结点存放在相邻 物理位置上来反映结点间逻辑关系。 *14、单链表：每个结点有两个域：一个值域data；另一个指针域next，用来指向该结 数据结构重点难点 1.数据结构重点内容： 什么是数据结构？ 数据元素和数据项的基本概念。 4大类逻辑结构。 算法的时间复杂度。 线性结构的基本特征； 在线性表（n个元素）的第i个位置前插入一个元素核心语句； 链表插入的核心语句； 栈 ( Stack )的定义和特点； 栈的操作实现(1) 入栈(2)出栈； 会做入栈出栈的题；实现递归； 队列的定义和特性； 顺序循环队列的表示和实现； 链式队列的存储结构； 判断链队列是否空； 串的基本概念； 串长的求法； 空串和空白串的区别； 串相等的条件； 串联接操作； 串的表示和实现； 数组的两种顺序映象的方式：1)以行序为主序，2)以列序为主序； 稀疏矩阵的压缩存储； 广义表的定义； 广义表的长度定义； 广义表的深度定义； 非空广义表的表头、表尾； 二叉树的定义； 二叉树的特点； 二叉树的性质； 二叉树的第i层上至多有多少个结点； 深度为k的二叉树中至多含有2k-1个结点；二叉树的先（根）序遍历； 二叉树的中（根）序遍历； 二叉树的后（根）序遍历； 线索二叉树的生成——线索化； 森林与二叉树的转换； 树与二叉树的转换； 树的先根遍历和后根遍历； Huffman树定义； 构造Huffman树的步骤并会做题；Huffman树编码； 图的结构定义； 图的数组(邻接矩阵)存储表示并会做题；图的邻接表存储表示并会做题； 有向图的十字链表存储表示并会做题； 深度优先搜索遍历图； 广度优先搜索遍历图； 普里姆算法求最小生成树； 克鲁斯卡尔算法求最小生成树； 求每一对顶点之间的最短路径； 顺序表的查找； 有序表的折半查找； 有序表的折半查找适用条件； 二叉排序树的构建过程； 《数据结构与算法》实验指导书马晓波秦俊平刘利民编 内蒙古工业大学信息工程学院计算机系 2008年9月1日 《数据结构与算法》实验教学大纲 三、实验目的、内容与要求 实验一线性表的创建与访问算法设计(4学时) （一）实验目的 数据结构于算法实验是计算机类本科学生计算机软件知识重要的实验环节，它将使学生从实践上学会用高级语言程序设计、实现复杂的数据结构，为大型软件设计奠定基础。本实验以某种线性表的创建与访问算法设计作为实验内容，举一反三，全面、深刻掌握线性结构的实现方法，培养解决问题的能力。 （二）实验内容 1、编写生成线性表的函数，线性表的元素从键盘输入； 2、编写在线性表中插入元素的函数； 3、编写在线性表中删除元素的函数； 4、编写输出线性表的函数； 5、编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏 幕输出。 方案一采用顺序存储结构实现线性表。 方案二采用单链表结构实现线性表。 （三）实验要求 1、掌握线性结构的机器内表示； 2、掌握线性结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验二二叉树的创建与访问算法设计(4学时) （一）实验目的 本实验以二叉树的创建与访问算法设计作为实验内容，掌握树型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成二叉树的函数，二叉树的元素从键盘输入； 2、编写在二叉树中插入元素的函数； 3、编写在二叉树中删除元素的函数； 4、编写遍历并输出二叉树的函数。 方案一采用递归算法实现二叉树遍历算法。 方案二采用非递归算法实现二叉树遍历算法。 （三）实验要求 1、掌握树型结构的机器内表示； 2、掌握树型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 实验三图的创建与访问算法设计(4学时) （一）实验目的 本实验以图的创建与访问算法设计作为实验内容，掌握图型结构的实现方法，培养解决负责问题的能力。 （二）实验内容 1、编写生成图的函数，图的元素从文件输入； 2、编写在图中插入元素的函数； 3、编写在图中删除元素的函数； 4、编写遍历并输出图的函数。 方案一采用BFS深度优先搜索算法实现图的遍历。 方案二采用DFS广度优先搜索算法实现图的遍历。 （三）实验要求 1、掌握图结构的机器内表示； 2、掌握图型结构之上的算法设计与实现； 3、列表对比分析两种数据结构的相应操作的时间复杂度、空间复杂度，阐明产生差异的原因。 四、考核方式 1、学生课前要认真阅读实验教材，理解实验内容与相关理论知识的关系，并完成预习报告； 2、实验课上教师讲解实验难点及需要注意的问题，并对实验数据签字； 3、学生课后要完成实验报告，并将签字的实验数据与实验报告交给带课教师； 4、教师根据学生实验情况，及时对实验内容和方法进行必要的调整和改进。 根据实验预习报告、实验课考勤、课上实验能力与实验效果、实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。 五、建议教材与教学参考书 1、建议教材 [1]严蔚敏、吴伟民主编. 数据结构（C语言版）. 北京：清华大学出版社，1997 2、教学参考书 [1] 严蔚敏、吴伟民主编. 数据结构题集（C语言版）. 北京：清华大学出版社，1997 [2] 李春葆编. 数据结构习题与解析. 北京：清华大学出版社，2002 [3] 刘振鹏主编. 数据结构. 北京：中国铁道出版社，2003 [4] 许卓群编．数据结构．北京：中央电大出版社， 2001 [5] Anany Levitin著．潘彦译．算法设计与分析．北京：清华大学出版社， 2004 数据结构学习难点讲解 数据结构复习 本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 需要达到<识记>层次的基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。 需要达到<领会>层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。 -------------------------------------------------------------------------------- 对于基本概念，仔细看书就能够理解，这里简单提一下： 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1数据结构整理完整版
数据结构设计与技巧
数据结构复习重点要点
数据结构实验指导书2014(1)
数据结构复习提纲(整理)
数据结构以及C语言常问与难点
数据结构复习要点(整理版).docx
《数据结构》实验指导书
2018考研计算机：数据结构重难点及复习建议
数据结构基础知识整理
数据结构重点难点
数据结构实验指导书
数据结构学习难点讲解
大学数据结构期末知识点重点总结
相关主题
文本预览