《数据结构》必须掌握的知识点与算法 第一章绪论 1、算法的五个重要特性(有穷性、确定性、可行性、输入、输出) 2、算法设计的要求(正确性、可读性、健壮性、效率与低存储量需求) 3、算法与程序的关系: (1)一个程序不一定满足有穷性。例操作系统,只要整个系统不遭破坏,它将永远不会停止,即使没有作业需要处理,它仍处于动态等待中。因此,操作系统不是一个算法。 (2)程序中的指令必须是机器可执行的,而算法中的指令则无此限制。算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。 (3)一个算法若用程序设计语言来描述,则它就是一个程序。 4、算法的时间复杂度的表示与计算(这个比较复杂,具体看算法本身,一般关心其循环的次数与N的关系、函数递归的计算) 第二章线性表 1、线性表的特点: (1)存在唯一的第一个元素;(这一点决定了图不是线性表) (2)存在唯一的最后一个元素; (3)除第一个元素外,其它均只有一个前驱(这一点决定了树不是线性表) (4)除最后一个元素外,其它均只有一个后继。 2、线性表有两种表示:顺序表示(数组)、链式表示(链表),栈、队列都是线性表,他们都可以用数组、链表来实现。 3、顺序表示的线性表(数组)地址计算方法: (1)一维数组,设DataType a[N]的首地址为A0,每一个数据(DataType类型)占m个字节,则a[k]的地址为:A a[k]=A0+m*k(其直接意义就是求在数据a[k]的前面有多少个元素,每个元素占m个字节) (2)多维数组,以三维数组为例,设DataType a[M][N][P]的首地址为A000,每一个数据(DataType 类型)占m个字节,则在元素a[i][j][k]的前面共有元素个数为:M*N*i+N*j+k,其其地址为: A a[i][j][k]=A000+m*(M*N*i+N*j+k); 4、线性表的归并排序: 设两个线性表均已经按非递减顺序排好序,现要将两者合并为一个线性表,并仍然接非递减顺序。可见算法2.2 5、掌握线性表的顺序表示法定义代码,各元素的含义; 6、顺序线性表的初始化过程,可见算法2.3 7、顺序线性表的元素的查找。 8、顺序线性表的元素的插入算法,注意其对于当原来的存储空间满了后,追加存储空间(就是每次增加若干个空间,一般为10个)的处理过程,可见算法2.4 9、顺序线性表的删除元素过程,可见算法2.5 10、顺序线性表的归并算法,可见算法2.7 11、链表的定义代码,各元素的含义,并能用图形象地表示出来,以利分析; 12、链表中元素的查找 13、链表的元素插入,算法与图解,可见算法2.9 14、链表的元素的删除,算法与图解,可见算法2.10 15、链表的创建过程,算法与图解,注意,链表有两种(向表头生长、向表尾生长,分别用在栈、队列中),但他们的区别就是在创建时就产生了,可见算法2.11 16、链表的归并算法,可见算法2.12 17、建议了解所谓的静态单链表(即用数组的形式来实现链表的操作),可见算法2.13 18、循环链表的定义,意义 19、循环链表的构造算法(其与单链表的区别是在创建时确定的)、图解
算法设计与分析实验报告 贪心算法 班级:2013156 学号:201315614 姓名:张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 排序算法 一、插入排序(Insertion Sort) 1. 基本思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。 2. 排序过程: 【示例】: [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97] Procedure InsertSort(Var R : FileType); //对R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找R[I]的插入位置// begin R[J+1] := R[J]; //将大于R[I]的元素后移// J := J - 1 end R[J + 1] := R[0] ; //插入R[I] // end End; //InsertSort // 二、选择排序 1. 基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。 2. 排序过程: 【示例】: 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 [38 65 97 76 49 27 49] 第二趟排序后13 27 [65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 97 76] 中南大学考试试卷 2013 -- 2014学年下学期时间100分钟 2014 年6 月6日 算法分析与设计课程 48 学时 3 学分考试形式:闭卷 专业年级:12级计算机、信安、物联本科生,总分100分,占总评成绩70 % 注:此页不作答题纸,请将答案写在答题纸上 一、简答题(本题30分,每小题5分) 1、陈述算法在最坏情况下的时间复杂度和平均时间复杂度;这两种评估算法复杂性的方 法各自有什么实际意义? 1最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。意义:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长2平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。意义:在输入不同的情况下算法的运行时间复杂度可能会发生变化。平均时间复杂度给出了算法的期望运行时间,有助于算法好坏的评价以及在不同算法之间比较时有一个统一标准 2、简单描述分治法的基本思想。 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些子问题,然后将各个子问题的解合并得到原问题的解。 3、何谓最优子结构性质? 如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。 4、何谓P、NP、NPC问题 P(Polynomial问题):也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题。 5、试比较回溯法与分支限界法。 1、引言 1.1回溯法 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。这种以深度优先方式系统搜索问题解的算法称为回溯法。 专题1:算法初步知识点及典型例题(原卷版) 【知识梳理】 知识点一、算法 1.算法的概念 (1)古代定义:指的是用阿拉伯数字进行算术运算的过程。 (2)现代定义:算法通常是指按照一定规则解决某一类问题的明确和有限的步骤。 (3)应用:算法通常可以编成计算机程序,让计算机执行并解决问题。 2.算法的特征: ①指向性:能解决某一个或某一类问题; ②精确性:每一步操作的内容和顺序必须是明确的;算法的每一步都应当做到准确无误,从开始的“第一步”直到“最后一步”之间做到环环相扣,分工明确.“前一步”是“后一步”的前提,“后一步”是“前一步”的继续. ③有限性:必须在有限步内结束并返回一个结果;算法要有明确的开始和结束,当到达终止步骤时所要解决的问题必须有明确的结果,也就是说必须在有限步内完成任务,不能无限制的持续进行. ④构造性:一个问题可以构造多个算法,算法有优劣之分。 3.算法的表示方法: (1) 用自然语言表示算法: 优点是使用日常用语, 通俗易懂;缺点是文字冗长, 容易出现歧义; (2) 用程序框图表示算法:用图框表示各种操作,优点是直观形象, 易于理解。 注:泛泛地谈算法是没有意义的,算法一定以问题为载体。 例1.下面给出一个问题的算法: S1输入x; S2若x≤2,则执行S3;否则,执行S4; S3输出-2x-1; S4输出x2-6x+3. 问题: (1)这个算法解决的是什么问题? (2)当输入的x值为多大时,输出的数值最小? 知识点二:流程图 1. 流程图的概念: 流程图,是由一些图框和流程线组成的,其中图框表示各种操作的类型,图框中的文字和符合表示操作的内容,流程线表示操作的先后次序。 2. 图形符号名称含义 开始/结束框 用于表示算法的开始与结束 输入/输出框 用于表示数据的输入或结果的输出 处理框描述基本的操作功能,如“赋值”操作、数学 运算等 判断框判断某一条件是否成立,成立时在出口处标明 “是”或“Y”;不成立时标明“否”或“N” 流程线 表示流程的路径和方向 连接点 用于连接另一页或另一部分的框图 注释框 框中内容是对某部分流程图做的解释说明 3. (1)使用标准的框图的符号; (2)框图一般按从上到下、从左到右的方向画; (3)除判断框图外,大多数框图符号只有一个进入点和一个退出点。判断框是具有超过一个退出点的唯一符号; (4)一种判断框是“是”与“不是”两分支的判断,而且有且仅有两个结果;另一种是多分支判断,有几种不同的结果; (5)在图形符号内描述的语言要非常简练清楚。 4.算法的三种基本逻辑结构: (1)顺序结构:由若干个按从上到下的顺序依次进行的处理步骤(语句或框)组成。这是任何一个算法都离不开的基本结构。 (2)条件结构:算法流程中通过对一些条件的判断,根据条件是否成立而取不同的分支流向的结构。它是依据指定条件选择执行不同指令的控制结构。 (3)循环结构:根据指定条件,决定是否重复执行一条或多条指令的控制结构称为循环结构。 知识点三:基本算法语句 程序设计语言由一些有特定含义的程序语句构成,与算法程序框图的三种基本结构相对应,任何程序设计语言都包含输入输出语句、赋值语句、条件语句和循环语句。以下均为BASIC 常见内部排序算法比较 排序算法是数据结构学科经典的内容,其中内部排序现有的算法有很多种,究竟各有什么特点呢?本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序,直接插入排序,简单选择排序,快速排序,堆排序,针对关键字的比较次数和移动次数进行测试比较。 问题分析和总体设计 ADT OrderableList { 数据对象:D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0} 数据关系:R1={〈ai-1,ai〉|ai-1, ai∈D, i=1,2,…,n} 基本操作: InitList(n) 操作结果:构造一个长度为n,元素值依次为1,2,…,n的有序表。Randomizel(d,isInverseOrser) 操作结果:随机打乱 BubbleSort( ) 操作结果:进行起泡排序 InserSort( ) 操作结果:进行插入排序 SelectSort( ) 操作结果:进行选择排序 QuickSort( ) 操作结果:进行快速排序 HeapSort( ) 操作结果:进行堆排序 ListTraverse(visit( )) 操作结果:依次对L种的每个元素调用函数visit( ) }ADT OrderableList 待排序表的元素的关键字为整数.用正序,逆序和不同乱序程度的不同数据做测试比较,对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息,用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕,要求列表现是比较结果. 要求对结果进行分析.各种排序算法比较
中南大学2014算法试卷及答案分析
专题1:算法初步知识点及典型例题(原卷版)
几种常见内部排序算法比较