下载文档原格式
1、算法的概念是为了解决某类问题而规定的一个有限长的操作序列。
特性：①有穷性②确定性③可行性④输入⑤输出评价标准：①正确性②可读性③健壮性④高效性2、算法的复杂度: 算法计算量所需资源的大小时间复杂度：T(n)=O(f(n)),他表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度空间复杂度：S（n）=O（f（n）），算法所需空间的度量。
3、数据结构中的逻辑结构分为：线性和非线性结构4、线性表的两种存储方式：顺序存储和链式存储的特点及比较。
顺序存储：指用一组地址连续的存储单元依次存储线性表的数据元素链式存储：用一组任意的存储单元存储线性表的数据元素。
5、线性表的特点①存在唯一的一个被称作“第一个”的数据元素②存在唯一的一个被称作“最后一个”的数据元素③除第一个之外，结构中的每一个数据元素均只有一个前驱④除最后一个之外，结构中的每一个数据元素均只有一个后继6、在长度为n的顺序表中的第i个位置处插入一个元素，需要移动多少个元素？n-i+17、理解算法：线性表La和Lb，将两个表合并成一个新的线性表并存于La中。
8、带头结点的单链表和不带头结点的单链表为空的条件分别是？带头结点的循环单链表为空的条件是？带头结点的单链表为空的条件：没有下一个节点L->next=NULL不带头结点的单链表为空的条件：L=NULL循环单链表为空的条件：head->next=head带头结点的循环单链表为空的条件是9、在单链表中插入结点的算法中，指针如何修改。
P3410、理解单链表中插入新结点的算法p3411、理解双向链表中插入新结点的算法p4012、理解栈和队列的操作特点：先进后出，先进先出。
已知进栈顺序，求可能的出栈顺序。
链栈相对于顺序栈的优点是什么?链栈在入栈前不需要判断栈是否为满，只需要为入栈元素动态分配一个节点空间13、理解算法：执行进栈操作，则先要判断栈S是否为满，若不满再将记录栈顶的下标变量top加1，再将进栈元素放进栈顶位置上。
《数据结构与算法》一、选择题1. 组成数据的基本单位是( )。
(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。
(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。
(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i≥1）层最多有( )个结点。
(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p->next = p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p6、栈和队列的共同特点是( )。
(A)只允许在端点处插入和删除元素 (B)都是先进后出(C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( ).(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-110、下面程序的时间复杂为（）for（i=1,s=0; i<=n; i++）{t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。
(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
数据结构与算法复习题库含答案1. 问题描述：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
答案：可以使用哈希表来解决此问题。
首先初始化一个空的哈希表，然后遍历数组中的每个元素。
对于每个元素，首先计算目标值与当前元素的差值，然后在哈希表中查找该差值。
如果找到了该差值，则说明存在两个数的和等于目标值，返回这两个数的下标；否则，将当前元素插入到哈希表中。
时间复杂度为O(n)，其中n为数组的长度。
2. 问题描述：给定一个字符串，找出其中不含重复字符的最长子串的长度。
答案：可以使用滑动窗口来解决此问题。
维护一个窗口，其中包含没有重复字符的子串。
遍历字符串中的每个字符，如果该字符不在窗口中，将其加入窗口；如果该字符在窗口中，移动窗口的左边界直到窗口中不包含重复字符。
记录窗口的最大长度。
时间复杂度为O(n)，其中n为字符串的长度。
3. 问题描述：给定一个字符串和一个单词列表，找出字符串中可以由单词列表中的单词组成的所有子串的起始位置。
答案：可以使用滑动窗口和哈希表来解决此问题。
首先统计单词列表中每个单词的出现次数。
然后遍历字符串中的每个位置作为子串的起始位置，维护一个滑动窗口。
在窗口中依次取出长度和单词列表中单词总长度相等的子串，在哈希表中统计子串中每个单词出现的次数。
如果窗口中的子串与单词列表中的单词出现次数一致，则记录该子串的起始位置。
时间复杂度为O(n*m)，其中n为字符串的长度，m为单词列表中的单词个数。
4. 问题描述：给定一个无序的整数数组，找出其中缺失的第一个正整数。
答案：可以使用原地哈希表来解决此问题。
遍历数组中的每个元素，将每个正整数放到数组中对应的位置上。
遍历数组中的每个元素，如果该位置上的数不等于数组索引加一，则该索引加一即为缺失的第一个正整数。
时间复杂度为O(n)，其中n为数组的长度。
5. 问题描述：给定一个字符串s，找到s中最长的回文子串。
答案：可以使用动态规划来解决此问题。
复习题集─参考答案一判断题（√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。
（√）2. 抽象数据类型与计算机内部表示和实现无关。
（×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。
（×）4. 链表的每个结点中都恰好包含一个指针。
（×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（×）8. 线性表在物理存储空间中也一定是连续的。
（×）9. 顺序存储方式只能用于存储线性结构。
（√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。
（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。
（√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
（×）14.二叉树的度为2。
（√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
（×）16.二叉树中每个结点的两棵子树的高度差等于1。
（√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。
（√）18.具有12个结点的完全二叉树有5个度为2的结点。
（√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。
（×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。
（×）21.计算机处理的对象可以分为数据和非数据两大类。
《数据结构与算法》复习题一、选择题。
1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。
A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。
6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。
（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。
s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j]; sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。
for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。
i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。
《数据结构与算法》复习题一、选择题。
1．在数据结构中，从逻辑上可以把数据结构分为：线性结构和非线性结构。
2．数据结构在计算机内存中的表示是指：数据的存储结构。
3．在数据结构中，与所使用的计算机无关的是数据的：逻辑结构。
4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储：数据元素之间的关系。
5．在决定选取何种存储结构时，普通不考虑：各结点的值如何。
6．以下说法正确的选项是：一些外表上很不相同的数据可以有相同的逻辑结构。
7．算法分析的目的是：分析算法的效率以求改良，算法分析的两个主要方面是空间复杂度和时间复杂度。
11．在以下的表达中，正确的选项是二维数组是其：数据元素为线性表的线性表。
12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着：不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致。
13．链表不具备的特点是：可随机访问任一结点。
14．不带头结点的单链表 head 为空的判定条件是： head == NULL。
15．带头结点的单链表 head 为空的判定条件是： head->next ==NULL。
16．假设某表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点，那末采用：带头结点的双循环链表存储方式最节省运算时间。
17．需要分配较大空间，插入和删除不需要挪移元素的线性表，其存储结构是：静态链表。
18．非空的循环单链表 head 的尾结点〔由 p 所指向〕满足： p->next ==head。
20．如果最常用的操作是取第 i 个结点及其前驱，那末采用：顺序表存储方式最节省时间。
21．在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 O〔n〕。
22．在一个长度为 n〔n>1〕的单链表上，设有头和尾两个指针，执行：删除单链表中的最后一个元素操作与链表的长度有关。
23．与单链表相比，双链表的优点之一是：顺序访问相邻结点更灵便。
1、从逻辑上可以把数据结构分为（C）两大类。
A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对x的赋值语句的频度为（C）for (i=1;i<=n;i++)for (j=1;j<=n;i++)x=x+1;n) A． O(2n) B．O(n) C．O(n2) D．O(log24、下面关于线性表的叙述中，错误的是哪一个？（ B ）A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6、静态链表中指针表示的是（ B）.A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址7、下面的叙述不正确的是（ BC）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。
A. O(0)B. O(1)C. O(n)D. O(n2)9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。
A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B）。
数据结构与算法分析—期末复习题及答案1. 简答题a) 什么是数据结构？数据结构是一种组织和存储数据的方法，它涉及到将数据元素以及它们之间的关系组织成一种特定的方式，以便于有效地访问和操作。
b) 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。
线性结构包括数组、链表、栈和队列等；非线性结构包括树和图等。
c) 什么是算法？算法指的是完成特定任务或求解特定问题的一系列步骤或指令。
算法需要满足正确性、可读性、健壮性和高效性等特性。
d) 算法的时间复杂度和空间复杂度是什么？时间复杂度是指在算法执行过程中所需的时间资源，空间复杂度是在算法执行过程中所需的存储空间资源。
2. 选择题a) 在排序算法中，如果待排序序列已经基本有序，以下哪个算法的性能最优？选项：A. 快速排序B. 冒泡排序C. 插入排序D. 归并排序正确答案：C. 插入排序b) 以下哪个数据结构通常用于实现递归算法？选项：A. 数组B. 链表C. 栈D. 队列正确答案：C. 栈3. 填空题a) 计算以下给定二叉树的前序遍历结果：A/ \B C/ \ / \D E F G正确答案：A, B, D, E, C, F, Gb) 给出选择排序算法的伪代码：```for i in range(len(arr)):min_index = ifor j in range(i+1, len(arr)):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]```4. 案例题假设有一个包含100个元素的整数数组arr，对该数组进行排序后返回结果。
请使用任意一种排序算法，并给出算法的时间复杂度。
解答示例：我们可以使用快速排序算法来对数组进行排序，时间复杂度为O(nlogn)。
下面是该算法的Python代码实现：```def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)arr = [5, 3, 2, 8, 1, 4, 7, 6, 9]sorted_arr = quick_sort(arr)print(sorted_arr)```运行结果：[1, 2, 3, 4, 5, 6, 7, 8, 9]5. 解答题请描述并给出示例说明动态规划算法的应用场景。
算法与数据结构复习第1章绪论一、基本概念1、数据的基本单位是数据元素。
2、数据对象是性质相同的数据元素的集合。
3、数据项：数据的不可分割的最小单位。
4、数据结构是数据元素之间抽象的相互关系。
5、数据结构在计算机内存中的表示是指数据的存储结构。
6、数据逻辑结构的三种类型是线性结构和非线性结构（树型结构和图形结构）。
7、算法的5个重要特性是有穷性（或有限性）、确定性、可行性、输入和输出。
8、算法分析是为了找出高效的算法，算法效率通过空间复杂度和时间复杂度来描述。
9、空间复杂度是指在算法运行过程中临时占用的存储空间的大小。
10、时间复杂度是指算法中包含简单操作的次数。
例、求下列程序段的时间复杂度。
for( i=0;i<n;i++)for(j=0;j<m;j++)a[i][j]=0;时间复杂度是 O(n*m)第2章线性表一、线性表1、线性表是由零个或多个具有相同类型的元素组成的一个有序序列。
2、用数组表示的线性表#define malength 100struct LIST{Elementtype elements[malength];int last;};用数组表示一个线性表，表中的所有元素依次存储在数组的连续单元中。
在表头或中间插入或册除元素都要移动元素，移动多少个。
3、用指针表示的线性表struct celltype{Elementtype elements;celltype *next;};用指针把表中的各个元素（称结点）依次链接起来，形成一个单向链表。
在链表中插入或册除结点都不要移动结点，移动多少个。
不带头结点的单链表h:不带头结点的单链表h为空的判定条件是:h=NULL带头结点的单链表h:带头结点的单链表h为空的判定条件是: h->next=NULL二、栈1、栈的定义栈是一种特殊的线性表，栈是一种只能在叫做栈顶的一端进行进栈或出栈操作的线性数据结构。
栈的特点是“后进先出”。
例1、已知一个字符串，次序为3*-y-a/y^2，试利用栈写出把该串的次序改为3y-*ay2^/-的操作步骤。
例2、有6个元素a,b,c,d,e依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。
（1）edcba (2) decba (3) dceab (4) abcde解：对于（1）a,b,c,d,e 进栈，e,d,c,b,a出栈。
对于（2）a,b,c,d 进栈，d出栈,e进栈，e,c,b,a出栈。
对于（3）a,b,c,d 进栈，d出栈,c出栈,e进栈,e出栈,此时栈中，栈底是a,栈顶是b，不可能a先出栈，所以（3）是不可能是出栈序列。
对于（4）a进栈,a出栈,b进栈,b出栈,c进栈,c出栈,d进栈,d 出栈,e 进栈，e出栈。
2、栈的表示（1）用数组表示栈栈的结构体：typedef struct {int top ;elementtype elements[maxlength];} STACK ;STACK S ;栈的容量：maxlength – 1 ;栈空：S.top = maxlength ;栈满：S.top = 0 ;栈顶元素：S.elements[ S.top ] ;（2）用指针表示栈栈的结构体：struct node{Elementtype val;node *next;};typedef node *STACK;三、队列1、队列的定义队列是一种特殊的线性表，只允许在表的一端进行插入，另一端进行删除。
在表的一端进行插入的一端叫队列的尾；在表的一端进行删除的一端叫队列的头。
队列的特点是先进先出。
例1，一个队列的入队列序列是1，2，3，4，则队列的输出序列是1，2，3，4。
2、队列的表示用指针表示队列struct celltype {elementtype element ；celltype *next ；}注意：栈和队列的共同点是只允许在端点处插入和删除元素。
四、广义表一个广义表是n(n 0)个元素的一个有限序列。
n是广义表的长度。
当n=0时称为空表。
若(a1,a2,…,a n)表示广义表，则(a1)表示广义表的头，(a2,…,a n)表示广义表的尾。
广义表的长度指该广义表中所包含的元素的个数。
广义表的深度指该广义表中所包含括号的层数。
例、广义表((a,b),c,d)的表头是(a,b)，表尾是(c,d )。
第3章树一、树1、基本概念树具有层次结构。
树是n(n>0)个结点的有限集合T，在一棵树中满足如下两个条件：（1）有且仅有一个根结点；（2）其余的结点可分为m(m>0)棵互不相交的有限集合T1，T2，…, T m,其中每个集合T i又都是一棵树。
结点的度：树中每个结点具有的子树。
树的度：树中所有结点的度的最大值。
叶子：度为0的结点。
结点的层数：根结点为第一层，其孩子结点为第二层，如此类推得到每个结点的层数。
树的深度：树中结点的最大层数。
森林：0个或多个不相交的树的集合。
2、树的表示（不考）3、树的性质性质1：树中的结点数等于所有结点的度加1。
性质2：度为m树中第i层上至多有m i-1个结点（i 1）。
二、二叉树1、基本概念二叉树、左孩子、右孩子、满二叉树、完全二叉树。
二叉树的五种基本形态：空树，只有根结点，根的右子树为空，根的左子树为空，根的左、右子树不为空。
高度为K且有2K-1个结点的二叉树称为满二叉树。
在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则此二叉树称为完全二叉树。
高度为k的完全二叉树的性质：（1）所有结点都出现在k或k-1层。
（2）k-1层的所有叶结点都在非终结结点的右边。
（3）除k-1层的最右非终结结点可能有一个（只能是左分支）或两个分支外，其余非终结结点都有两个分支。
2、二叉树的性质性质1：二叉树上叶子结点数等于双分支数加1。
性质2：在二叉树中第i(i 1)层的结点数最多有2i-1个。
性质3：深度为h的二叉树至多有2h-1个结点。
3、二叉树的遍历顺序（1）先根遍历二叉树（2）中根遍历二叉树（3）后根遍历二叉树4、二叉树的存储二叉树的存储有顺序存储、链式存储和线索存储。
顺序存储一棵二叉树时，首先对该树中每个结点进行编号，然后以各结点的值对应存储到一维数组中。
树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同。
其编号过程为：首先把树根结点的编号定为1，然后按照层次从上到下、每层从左到右的顺序，对每一结点进行编号，当它的双亲结点的编号为i时，若它为左孩子，则编号为2i，若为右孩子，则编号为2i+1。
例1、某二叉树的结点数据采用顺序存储结构如下：（2）写出结点值为E的双亲结点及左、右子树。
解：结点值为E的双亲结点：B，左子树是：以F为根结点的子树。
右子树为空。
三、堆如果一棵完全二叉树的任意一个非终结点的元素都不小于其左儿子结点和右儿子结点的元素，则称此完全二叉树为最大堆。
如果一棵完全二叉树的任意一个非终结点的元素都不大于其左儿子结点和右儿子结点的元素，则称此完全二叉树为最小堆。
例、设有如下的元素{46,79,56,38,40,84}，画出将每一个元素插入堆中以后的最大堆。
(作业)四、哈夫曼树构成哈夫曼树的方法，编码的平均长度，带权路径长度WPL例，有一份电文中共使用5个字符：a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，画出构造哈夫曼树的过程（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。
试问编码的平均长度是多少？（作业）第4章图一、基本概念图、有向图、无向图、度、入度、出度、连通图、权二、性质1、在一个图中，边数是全部顶点的度数之和的 1/2倍。
2、在一个图中，所有顶点的度数之和等于所有边数的2倍。
3、n个顶点的连通图至少有n-1条边。
4、在有向图中，顶点的度是入度与出度之和。
5、具有n 1个顶点的开放树包含n-1条边。
三、图的存储方式图的存储方式有：邻接矩阵、邻接表1、在n个顶点的无向图中，邻接矩阵是n阶矩阵。
2、无向图的邻接矩阵中，第i行上的非零元素个数和第i列上的非零元素个数相等。
例、给出下图的邻接矩阵，并求顶点v4的度。
四、图的搜索在邻接矩阵、邻接表中，进行深度优先搜索、广度优先搜索。
例，已知图G的邻接表如下图，写出从顶点v1出发的深度优先搜索和广度优先搜索的序列。
从顶点v1出发，深度优先搜索的序列：v1,v3,v4,v5,v2从顶点v1出发，广度优先搜索的序列:v1,v3,v2,v4,v5在邻接表中，深度优先搜索算法类似于二叉树的先根顺序遍历。
五、最小生成树构造最小生成树的方法：普里姆算法、克鲁斯卡尔算法。
例、使用克鲁斯卡尔画出构造如下图所示的图的一棵最小生成树的过程。
第5章查找一、基本概念查找、关键字、二、分类静态查找、动态查找三、查找方法1、静态查找的方法：线性查找、折半查找、分块查找。
线性查找的存储结构仅限于顺序存储或链式存储，它的时间复杂度是O（n）。
折半查找的存储结构仅限于顺序存储，且结点按关键字有序排序。
折半查找的时间复杂度是O（log n）。
2、散列法散列法有内散列表和外散列表。
散列函数：直接定址法、质数除余法（除留余数法）、平方取中法、折叠法和数字分析法。
质数除余法: h(k)=k%m其中，k是关键字，m是散列表的长度，n是关键字的个数，m 最好是一个质数。
解决冲突的方法：线性探测再散列（线性探查法）。
D 0(k)=h(k)D i (k)= (D i-1(k)+1)%m ( 1≤i ≤m-1)平均查找长度： 11ni i i ASL p c n ===∑∑ni=1第i 个关键字查找次数例1、一个待散列存储的数据集合为{32,75,29,63,48,44,25,46,18,70}，散列地址空间为HT[15]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求每一元素的散列地址，画出最后得到的散列表，求平均查找长度。
第6章 排序一、概念排序：按照排序时存放数据的设备，排序分为内排序和外排序。
内排序方法有插入排序、交换排序、选择排序、归并排序和基数排序。
插入排序有直接插入排序和希尔排序。
交换排序分为：气泡排序和快速排序。
选择排序有直接选择排序和堆排序。
各排序的时间复杂度。
二、排序过程给出关键字，写出各排序的排序过程。
三、排序算法插入排序的算法、气泡排序的算法、直接选择排序的算法。
