数据结构知识点计算机数据结构与算法_计算机-数据结构与算法.pdf
1.衡量算法效率的方法主要有两大类：事后统计:利用计算机的时钟(不可取)事前分析估算:用高级语言编写的程序运行的时间主要取决于如下因素:算法选用的策略,问题规模,使用语言,编译程序,机器执行指令的速度 2.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备 有穷性:执行有限步，每步有限的时间 确定性:每条指令有确切含义，相同输入只能得到相同输出 可行性:操作通过已实现的基本运算执行有限次来实现 输入:零个至多个输入 输出:一个至多个输出 3.算法设计的要求：正确性,可读性,健壮性,效率与低存贮量要求 4.程序是算法的一种实现,算法是供人阅读的,程序是让机器执行的 算法用计算机语言实现时就是程序,程序不具有算法的有穷性 5.评价一个算法优劣的重要依据是看执行该算法的程序需要占用多少机器资源:程序所用算法运行时所要花费的时间代价,程序中使用的数据结构占有的空间代价 6.算法主要由程序的控制结构(顺序，分支，循环)和原操作(必需的操作)构成，算法的时间主要取决于两者。7.若所用额外存储空间相对于输入数据量来说是常数，称算法为原地就地工作 8.可以用抽象数据类型定义一个完整的数据结构 9.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 10.同一个算法，实现语言的级别越高，执行效率就越低 11.一个算法应该是问题求解步骤的描述 12.算法的计算量的大小称为计算的复杂性 13.算法分析的目的是分析算法的效率以求改进 14.递归定义由两部分组成:递归基础/出口,递归规则 15.KMP 算法的最大特点是指示主串的指针不回溯 16.树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和双亲表示法 17.首元结点:链表中存储第一个数据元素a1 的结点,也称为第一元素结点 头结点:在链表的首元结点之前附设的一个结点;数据域内只放空表标志,表 长等信息或者是空的;也可做监视哨 头指针:指向链表中第一个结点(有头结点的指向头结点,无头结点则指向首 元结点)的指针.单链表可由一个头指针唯一确定,能够标识一个单 链表,也常做链表的名字 带头结点的单链表 head 为空的条件是 head-next=NULL 18.采用邻接表存储的图，其DFS类似于二叉树的先序遍历 19.对于确定了的存储结构和源点,深度优先周游产生的序列是唯一的 20.栈可以作为实现程序设计语言过程调用时的一种数据结构 21.在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空.22.一个排序算法的时间复杂度与所需比较关键字的次数有关 23.不带头结点的链表表示的队列,在进行删除运算时头,尾指针可能都要修改 24.设有两个串 S1 和 S2，求 S2 在 S1 中首次出现的位置的运算称作模式匹配 25.串是字符的有限序列,模式匹配是串的一种重要运算,串既可以采用顺序存储,也可以采用链式存储 26.图的 BFS生成树的树高比 DFS生成树的树高:小或相等 27.对线性表进行二分查找时，要求线性表必须以顺序方式存储且数据元素有序 28.强连通分量是有向图中极大强连通子图 29.二叉树是树的特殊形式 30.串是一种特殊的线性表，特殊性在于数据元素是一个字符 31.KMP 时间复杂度 O(m+n),朴素模式匹配时间复杂度 O(m*n)32.对矩阵压缩存储是为了减少存储空间 33.单链表中，增加一个头结点的目的是为了方便运算的实现 34.在采用拉链法处理冲突所构成的开散列表上查找某一关键字，在查找成功的情况下，所探测的这些位置上的键值一定都是同义词 35.采用线性探测再散列法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找 36.在初始数据表已经有序时，快速排序算法的时间复杂度为O(n2)37.排序过程中的比较次数与排序方法无关的是选择排序法,二路归并排序 38.快速排序算法可能会在初始数据有序时，花费的时间反而最多 39.在初始序列已基本有序的情况下，排序效率最高的算法是直接插入 40.设计一个“好”的算法应考虑达到的目标有是健壮的,无二义性,可读性好 41.从逻辑结构上看，n 维数组的每个元素均属于 n 个向量 42.设 F是一个森林，B是由 F变换得赌二叉树。若 F中有 n 个非终端结点，则B中右指针域为空的结点有 n+1 43.深度优仙遍历,拓扑排序判断出一个有向图是否有环（回路）44.二叉查找树的查找效率与二叉树的树型有关,在呈单枝树时其查找效率最低 45.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用后序遍历方法最合适 46.采用分块查找方法，既能实现较快地查找线性表，又能适应动态变化的要求 47.顺序表又称为向量,采用定长的一维数组存储 48.链表逻辑上相邻的元素在物理位置上不要求也相邻 49.时间主要取决于如下因素算法选用的策略问题规模使用语言编译程序机器执行指令的速度计算机中的算法指的是解决某一个问题的有限运算序列它必须具备有穷性执行有限步每步有限的时间确定性每条指令有确切含义相同输入只能设计的要求正确性可读性健壮性效率与低存贮量要求程序是算法的一种实现算法是供人阅读的程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性评价一个算法优劣的重要依据是看执行该算法的程序需要的控制结构顺序分支循环和原操作必需的操作构成算法的时间主要取决于两者若所用额外存储空间相对于输入数据量来说是常数称算法为原地就地工作可以用抽象数据类型定义一个完整的数据结构所谓时间复杂度是指最坏情况下估
