算法和数据结构.docx
- 文档编号:6882799
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:22
- 大小:250.36KB
算法和数据结构.docx
《算法和数据结构.docx》由会员分享,可在线阅读,更多相关《算法和数据结构.docx(22页珍藏版)》请在冰点文库上搜索。
算法和数据结构
1算法
考试的内容:
1.1算法的基本概念
1.算法的概念(必记):
算法是指解题方案的准确而完整的描述。
分析:
要用计算机实现某一任务时,先应设计出一整套解决问题的指导方案,然后具体实现。
整套的指导方案称之为算法,而具体的实现称之为程序。
并且在设计指导方案时,可不用过多考虑到实现程序的具体细节(即可以一点点的理想化),但在程序实现时,必须受到具体环境的约束(现实不同于理想)。
结论:
算法不等于程序,也不等于计算方法,程序的编制不可能优于算法的设计。
2.算法的基本特征(必记):
a.可行性:
由于算法总是在某个特定的计算工具上实现并执行的,因而受到计算工具的限制,所以在设计算法时,要考虑到设计的算法是否是可性的。
b.确定性:
算法中的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。
c.有穷性:
算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
d.拥有足够的情报:
算法有相应的初始数据。
3.算法的基本要素:
一个算法通常由两个基本要素所组成:
一是对数据对象的运算和操作,二是算法的控制结构。
基本运算和操作分为四类:
a.算术运算:
(加、减、乘、除等运算)
b.逻辑运算:
(与、或、非等运算)
c.关系运算:
(大于、小于、等于、不等于等运算)
d.数据传输:
(赋值、输入、输出等操作)
算法的控制结构:
算法中各操作之间的执行顺序称之为算法的控制结构。
一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
注意:
一个计算机系统能执行的所有指令的集合,称为该计算机系统的指令系统。
4.算法设计基本方法:
列举法、归纳法、递推、递归、减半递推技术、回溯法。
1.2算法的复杂度(必记)
算法的复杂度主要包括时间复杂度和空间复杂度。
1.算法的时间复杂度:
是指执行算法所需要的计算工作量,是由算法所执行的基本运算次数来度量。
可用平均性态和最坏情况两种分析方法。
其中平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量;而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。
2.算法的空间复杂度:
一个算法的空间复杂度,是指执行这个算法所需要的内存空间。
包含有三部分所组成:
算法程序所占的空间+输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。
历届的考题:
1、算法具有五个特性,以下选项中不属于算法特性的是(______)[2005.4]
A)有穷性B)简洁性C)可行性D)确定性
2、问题处理方案的正确而完整的描述称为______。
[2005.4]
4、算法复杂度主要包括时间复杂度和[_____]复杂度。
[2006.9]
(7)下列叙述中正确的是( )【2006年9月】
A)一个算法的空间复杂度大,则其时间复杂度也必定大
B)一个算法的空间复杂度大,则其时间复杂度必定小
C)一个算法的时间复杂度大,则其空间复杂度必定小
D)上述三种说法都不对
(1)下列叙述中正确的是( )【2007年4月】
A)算法的效率只与问题的规模有关,而与数据的存储结构无关
B)算法的时间复杂度是指执行算法所需要的计算工作量
C)数据的逻辑结构与存储结构是一一对应的
D)算法的时间复杂度与空间复杂度一定相关
(5)算法的有穷性是指( )【2008年4月】
A)算法程序的运行时间是有限的 B)算法程序所处理的数据量是有限的
C)算法程序的长度是有限的 D)算法只能被有限的用户使用
(4)算法的空间复杂度是指()【2009年9月】
A.算法在执行过程中所需要的计算机存储空间B.算法所处理的数据量
C.算法程序中的语句或指令条数D.算法在执行过程中所需要的临时工作单元数
1.2数据结构与算法
考试的内容:
数据结构作为计算机的一门学科,主要研究以下三个方面的问题:
a.数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构;
b.在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;
c.对各种数据结构进行的运算。
注意:
讨论以上问题主要目的是为了提高数据处理的效率。
提高效率包括两个方面:
一是提高数据处理的速度,二是节省在数据处理过程中所占用的计算机存储空间。
2.1什么是数据结构
简单地说,数据结构是指相互有关联的数据元素的集合。
而数据元素之间的关联通常是指其前后件关系(即先后顺序关系),如春、夏、秋、冬之间的先后顺序关系。
因此,一个数据结构应包含以下两方面的信息:
a.表示数据元素的信息;b.表示各数据元素之间的前后件关系。
1.数据的逻辑结构
所谓数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。
注意:
这种逻辑关系仅指元素之间的固有的一个先后顺序关系,而与它们在计算机中的存储顺序无关。
2.数据的存储结构
数据的存储结构的概念:
数据的逻辑结构在计算机存储空间中的存放形式(也称数据的物理结构)。
注意:
a、数据元素在计算机中存储空间中的位置关系可以与它们的逻辑关系相同,也可以不相同。
b、数据的存储结构有顺序、链接、索引等。
c、数据元素采用不同的存储结构,其数据处理的效率是不同的。
2.2数据结构的图形表示
一般用一个中间标有元素值的方框表示一个数据元素,用一条有向线段从前件结点指向后件结点。
在数据结构中,没有前件的结点成为根结点(如上图中的春与父亲);没有后件的结点称为终端结点(也称为叶子结点,如上图中的冬与儿子和女儿)。
注意:
在进行处理时,一个数据结构中的元素结点可能是在动态变化的。
这种变化可能是元素结点的个数发生变化,也可以是元素结点的先后顺序发生变化。
2.3线性结构与非线性结构
空的数据结构是:
一个数据元素都没有的数据结构。
根据数据结构中各数据元素之间前后件关系的复杂程度,可将数据结构分为二大类:
线性结构和非线性结构。
一个非空的数据结构满足下列两个条件,则为线性结构,线性结构又称为线性表。
a.有且只有一个根结点;b.每一个结点最多有一个前件,也最多有一个后件。
在上图中,左边的是线性结构,而右边的是非线性结构。
注意:
线性结构与非线性结构都可以是空的数据结构。
一个空的数据结构究竟属于线性结构还是属于非线性结构,要根据具体情况来确定。
如果对该数据结构的运算是按线性结构的规则来处理的,则属于线性结构;否则属于非线性结构。
历届的考题:
1、数据的存储结构是指(_____)[2005.4]
A)存储在外存中的数据B)数据所占的存储空间量
C)数据在计算机中的顺序存储方式D)数据的逻辑结构中计算机中的表示
2、下列叙述中正确的是(______)[2005.9]
A)一个逻辑数据结构只能有一种存储结构
B)数据的逻辑结构属于线性结构,存储结构属于非线性结构
C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理的效率
D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率
1.3线性表及其顺序存储结构
考试的内容:
3.1线性表的基本概念
非空线性表的结构特征如下:
a.有且只有一个根结点,它无前件;b.有且只有一个终端结点,它无后件;c.除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。
线性表中结点的个数n称为线性表的长度。
当n=0时,称为空表。
3.2线性表的顺序存储结构
线性表的顺序存储结构具有以下两个基本特点:
a.线性表中所有元素所占的存储空间是连续的;
b.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
注意:
在线性表的顺序存储结构中,其前后件两个元素在存储空间中是紧邻的,且前件元素一定在后件元素的前面。
在线性表的顺序存储结构中,如第一个元素的地址为ADR(a1),每个元素占用的存储空间大小为k个字节,则线性表中第i个元素的存储地址为:
ADR(a1)+(i-1)*k。
3.3顺序表的插入运算
在线性表的顺序存储结构中,当插入元素时,插入点后的元素都要向后移动一位,以让出一个存储空间。
在平均情况下,要在线性表中插入一个新元素,需要移动表中一半的元素。
因此,在线性表顺序存储的情况下,要插入一个新元素,其效率是很低的。
3.4顺序表的删除运算
在线性表的顺序存储结构中,当删除元素时,删除点后的元素都要向前移动一位,以保证元素都是相邻存储的。
在平均情况下,要在线性表中删除一个元素,需要移动表中一半的元素。
因此,在线性表顺序存储的情况下,要删除一个元素,其效率是很低的。
1.4栈和队列
注意的考点:
4.1栈及其基本运算
1.什么是栈
栈是一种特殊的线性表。
栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的一端称为栈底。
栈按照"先进后出"(FILO)或"后进先出"(LIFO)组织数据,栈具有记忆作用。
用top表示栈顶位置,用botton表示栈底。
2.栈的顺序存储及其运算
栈的基本运算有三种:
.入栈运算、退栈运算和.读栈顶元素。
4.2队列及其基本运算
1.什么是队列
队列是允许在一端进行插入、而在另一端进行删除的特殊的线性表。
允许插入的一端称为队尾,允许删除的一端称为排头(或队头)。
队列又称为"先进先出"(FIFO)或"后进后出"(LILO)的线性表,它体现了"先来先服务"的原则。
往队列的队尾插入一个元素称为入队运算,从队列的排头删除一个元素称为退队运算。
2.循环队列及其运算
所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。
队列空和队列满的条件如下:
队列空的条件为s=0;
队列满的条件为s=1且front=rear.
循环队列主要有两种基本运算:
入队运算和退队运算。
a.入队运算:
在循环队列的队尾加入一个新元素,首先将队尾指针进一(即rear=rear+1),并当rear=m+1时置rear=1;然后将新元素插入到队尾指针指向的位置。
注意:
当循环队列非空(s=1)且队尾指针等于排头指针时,说明循环队列已满,不能进行入队运算,这种情况称为"上溢"。
b.退队运算:
指在循环队列的排头位置退出一个元素并赋给指定的变量。
首先将排头指针进一(即front=front+1),并当front=m+1时置front=1;然后将排头指针指向的元素赋给指定的变量。
注意:
当循环队列为空(s=0)时,不能进行退队运算,这种情况称为"下溢"。
历届的考题:
1、下列关于栈的描述中错误的是(_______)[2005.4]
A)栈是先进后出的线性表B)栈只能顺序存储
C)栈具有记忆作用D)对栈的插入与删除操作中,不需要改变栈底指针
2、按照"后进先出"原则组织数据的数据结构是(______)[2006.4]
A)队列B)栈C)双向链表D)二叉树
3、列关于栈的描述正确的是(______)[2005.9]
A)在栈中只能插入元素而不能删除元素
B)在栈中只能删除元素而不能插入元素
C)栈是特殊的线性表,只能在一端插入或删除元素
D)栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素
4、数据结构分为逻辑结构和存储结构,循环队列属于____结构。
[2005.9]
5、按“先进后出”原则组织数据的数据结构是_____。
[2006.9]
1.5线性链表
注意的考点:
5.1线性链表的基本概念
1.链式存储
在顺序存储方式中所有的数据元素在内存中是相邻存放的,从而造成了在插入与删除数据元素时,需要大量移动相应的数据元素。
为了解决这种问题,可以将每个数据元素存储在内存中不相邻的不同位置,并利用上一个数据元素在存有数据的同时,也存放下一个数据元素所在的位置地址(称为一个存储单元,即结点),以便查找。
这就是链式存储方式。
在链式存储方式中,要求每个结点由两部分组成:
一部分用于存放数据元素值,称为数据域;另一部分用于存放地址,称为指针域。
其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。
注意:
a、在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
b、链式存储方式既可以用于表示线性结构,也可以用于表示非线性结构。
在用链式结构表示较复杂的非线性结构时,其指针域的个数要多一些。
2.线性链表
线性表的链式存储结构称为线性链表。
如果结点中有两个指针,一个用于指向前一个结点,而另一上用于指向后一个结点,则称之为双向链表。
3.带链的栈:
栈的链式存储结构称为带链的栈。
4.带链的队列:
队列的链式存储结构称为带链的队列。
5.2线性链表的基本运算:
查找、插入、删除。
历届的考题:
1、下列对于线性链表的描述中正确的是(____)[2005.4]
A)存储空间不一定是连续,且各元素的存储顺序是任意的
B)存储空间不一定是连续,且前件元素一定存储在后件元素的前面
C)存储空间必须连续,且前件元素一定存储在后件元素的前面
D)存储空间必须连续,且各元素的存储顺序是任意的
2、下列叙述中正确的是(_____)[2006.4]
A)线性链表是线性表的链式存储结构B)栈与队列是非线性结构
C)双向链表是非线性结构D)只有根结点的二叉树是线性结构
3、数据结构分为线性结构和非线性结构,带链的队列属于____。
[2006.9]
1.6树与二叉树
B)
C)
D)
B)
C)
D)
B)
C)
D)
B)
C)
D)
注意的考点:
6.1树的基本概念
树是一种简单的非线性结构,所有元素之间具有明显的层次特性。
a.在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称为树的根。
b.在树结构中,一个结点所拥有的后件个数称为该结点的度;在树中,所有结点中的最大的度称为树的度。
c.树具有明显的层次关系,即树是一种层次结构。
d.数的最大层次称为树的深度。
f.在树中,叶子结点没有子树。
6.2二叉树及其基本性质
1.什么是二叉树:
二叉树是一种很有用的非线性结构。
二叉树具有以下两个特点:
a.非空二叉树只有一个根结点;
b.每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
由以上特点可以看出,在二叉树中,每一个结点的度最大为2。
2.二叉树的基本性质:
(重要)
a.在二叉树的第k层上,最多有2k-1(k>=1)个结点。
b.深度为m的二叉树最多有2m-1个结点。
深度为m的二叉树是指二叉树共有m层。
c.在任意一棵二叉树中,度为0的结点(即叶子结点)总是比深度为2的结点多一个。
d.具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。
3.满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
a.满二叉树:
除最后一层外,每一层上的所有结点都有两个子结点。
这就是说,在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。
b.完全二叉树:
除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
注意:
满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。
完全二叉树还具有以下性质:
a.具有n个结点的完全二叉树的深度为log2n]+1。
6.3二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。
6.4二叉树的遍历:
(重要)
在先左后右的原则下,根据访问根结点的次序,二叉树的遍历可以分为三种:
前序遍历、中序遍历、后序遍历。
a.前序遍历:
首先访问根结点,然后遍历左子树,最后遍历右子树。
b.中序遍历:
首先遍历左子树,然后访问根结点,最后遍历右子树。
c.后序遍历:
首先遍历左子树,然后遍历右子树,最后访问根结点。
前序:
FCADBEGHP中序:
ACBDFEHGP后序:
ABDCHPGEF
注意:
在树结构中,每一个结点都代表一棵子树。
前序遍历中一定以根结点开头,后序遍历一定以根结点结尾,而中序遍历中,根结点前面的为树的左子树,而其后面的为树的右子树。
历届的考题:
1、在深度为7的满二叉树中,叶子结点的个数为()[2006.4]
A)32B)31C)64D)63
2、对下图1所示二叉树
进行中序遍历的结果是________。
[2006.9]
A)ACBDFEGB)ACBDFGEC)ABDCGEFD)FCADBEG
3、对如下图2所示二叉树,进行后序遍历的结果为()[2006.4]
A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA
4、某二叉树中,度为2的结点有18个,则该二叉树中有___个叶子结点。
[2005.4]
5、一棵二叉树第六层(根结点为第一层)的结点数最多为____个。
[2005.9]
1.7查找技术
注意的考点:
7.1顺序查找:
顺序查找的方法是:
用被查元素与线性表中的元素逐一比较,直到找出相等的元素,则查找成功;或者找遍所有元素都不相等,则查找失败。
顺序查找的优点:
对线性表的元素的逻辑次序无要求(不必对元素进行排序),对线性表的存储结构无要求(顺序存储、链接存储皆可)。
顺序查找的效率很低,但在以下情况下,只能采用顺序查找:
a.如果线性表为无序表,则不管是顺序存储结构还是链式存储结构,都只能用顺序查找。
b.即使是有序线性表,如果采用链式存储结构,也只能用顺序查找。
7.2二分法查找:
二分法查找是一种效率较高的线性表查找方法。
要进行二分法查找,则线性表结点必须是排好序的,且线性表以顺序方式存储。
二分法查找的方法:
首先用要查找的元素值与线性表中间位置的元素值相比较,这个中间结点把线性表分成了两个子表,比较相等则查找完成,不等则根据比较结果确定下一步的查找应在哪一个子表中进行,如此进行下去,直到找到满足条件的结点,或者确定表中没有这样的结点。
对于二分法查找的缺点是线性表排序需花费时间,顺序方式存储的插入、删除不便。
注意:
对于长度为n的有序线性表,在最坏的情况下,二分查找只需要比较比较[log2n]次,而顺序查找需要比较n次。
二分查找的效率要比顺序查找高得多。
历届的考题:
1、在长度为64的有序线性表中进行顺序查找,最坏情况下需要比较的次数为(____)[2006.9]
A)63B)64C)6D)7
2、下列数据结构中,能用二分法进行查找的是(_____)[2005.9]
A)顺序存储的有序线性表B)线性链表
C)二叉链表D)有序线性链表
3、对长度为n的线性表进行顺序查找,在最坏情况下所需要的比较次数为(____)[2005.4]
A)log2nB)n/2C)nD)n+1
1.8排序技术(记住每种排序的比较次数)
注意的考点:
排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
8.1交换类排序法
交换类排序的基本思想:
两两比较待排序线性表的元素值,并对不满足顺序要求的元素进行位置交换,直到全部满足为止.
1、冒泡排序法
将相邻的元素进行两两比较,若为逆序则进行交换。
将线性表照此方法从头到尾处理一遍称作一趟起泡,一趟起泡的效果是将元素值最大的记录交换到了最后的位置,即该线性表的最终位置。
若某一趟起泡过程中没有发生任何交换,则排序过程结束。
在最坏情况下,需要的比较N(N-1)/2次。
2、快速排序法
快速排序又称分区交换排序,是对冒泡排序的一种改进。
其基本方法是:
在待排序线性表中任取一个元素,以它为基准用交换的方法将所
有的元素分成两部分,元素值比它小的在一个部分,元素值比它大的在另一个部分。
再分别对两个部分实施上述过程,一直重复到排序完成。
在最坏的情况下与冒泡排序相当,然而快速排序的平均执行时间为O(nlog2n)。
8.2插入类排序法
插入排序的基本思想是:
每步将一个待排序元素按其元素值的大小插入到前面已排序的元素中的适当位置上,直到全部记录插入完为止。
1、简单插入排序
它是指将无序序列中的各元素依次插入到已经有序的线性表中。
在最坏情况下比较需要N(N-1)/2次。
2、希尔排序法
希尔排序的基本思想是把元素按下标的一定增量分组,对每组元素使用插入排序,随增量的逐渐减小,所分成的组包含的记录越来越多,到增量的值减小到1时,整个数据合成一组,构成一组有序元素,故其属于插入排序方法。
在最坏情况下需要的比较O(n1.5)次。
8.3选择类排序法
选择排序的基本思想是:
每次从待排序的元素中选出元素值最小(或最大)的记录,顺序放在已排序的记录序列的最后,直到全部排完。
1、简单选择排序
对线性表进行n-1趟扫描,第i趟扫描从剩下的n-i+1个记录中选出元素值最小的记录,与第i个记录交换。
最坏情况下需要比较N(N-1)/2次。
2、堆排序
堆排序的基本思想是:
对待排序的线性表,首先把它们按堆的定义排成一个序列(称为建堆),这就找到了最小的元素,然后将最小的元素取出,用剩下的元素再建堆,便得到次最小的的元素,如此反复进行,直到将全部元素排好序为止。
在最坏怀况下需要比较O(nlog2n)次。
8.4总结
假设线性表的长度为n,在最坏的情况下进行比较的次数:
历届的考题:
1、对于长度为n的线性表,在最坏情况下,下列各排序法所对应的比较次数中正确的是(_)[2005.4]
A)冒泡排序为n/2B)冒泡排序为nC)快速排序为nD)快速排序为n(n-1)/2
2、对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为_____。
[2006.4]
总复习图:
1.9精典模拟题
一.选择题
1.算法的时间复杂度是指______。
A.执行算法程序所需要的时间B.算法程序的长度
C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数
2.算法的空间复杂度是指______。
A.算法程序的长度B.算法程序中的指令条数
C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间
3.下面叙述正确的是______。
A.算法的执行效率与数据的存储结构无关
B.算法的空间复杂度是指算法程序中指令(或语句)的条数
C.算法的有穷性是指算法必须能在执行有限个步骤之后终止
D.以上三种描述都不对
4.在计算机中,算法是指______。
A.查询方法B.加工方法
C.解题方案的准确而完整的描述D.排序方法
5.算法一般都可以用哪几种控制结构组合而成______。
A.循环、分支、递归B.顺序、循环、嵌套
C.循环、递归、选择D.顺序、选择、循环
6.算法分析的目的是______。
(D)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构