搜索
1.衡量算法效率的方法主要有两大类：事后统计:利用计算机的时钟(不可取)事前分析估算:用高级语言编写的程序运行的时间主要取决于如下因素:算法选用的策略,问题规模,使用语言,编译程序,机器执行指令的速度2.计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备有穷性:执行有限步，每步有限的时间确定性:每条指令有确切含义，相同输入只能得到相同输出可行性:操作通过已实现的基本运算执行有限次来实现输入:零个至多个输入输出:一个至多个输出3.算法设计的要求：正确性,可读性,健壮性,效率与低存贮量要求4.程序是算法的一种实现,算法是供人阅读的,程序是让机器执行的算法用计算机语言实现时就是程序,程序不具有算法的有穷性5.评价一个算法优劣的重要依据是看执行该算法的程序需要占用多少机器资源:程序所用算法运行时所要花费的时间代价,程序中使用的数据结构占有的空间代价6.算法主要由程序的控制结构(顺序，分支，循环)和原操作(必需的操作)构成，算法的时间主要取决于两者。7.若所用额外存储空间相对于输入数据量来说是常数，称算法为原地就地工作8.可以用抽象数据类型定义一个完整的数据结构9.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界10.同一个算法，实现语言的级别越高，执行效率就越低11.一个算法应该是问题求解步骤的描述12.算法的计算量的大小称为计算的复杂性13.算法分析的目的是分析算法的效率以求改进14.递归定义由两部分组成:递归基础/出口,递归规则15.KMP算法的最大特点是指示主串的指针不回溯16.树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和双亲表示法17.首元结点:链表中存储第一个数据元素a1的结点,也称为第一元素结点头结点:在链表的首元结点之前附设的一个结点;数据域内只放空表标志,表长等信息或者是空的;也可做监视哨头指针:指向链表中第一个结点(有头结点的指向头结点,无头结点则指向首元结点)的指针.单链表可由一个头指针唯一确定,能够标识一个单链表,也常做链表的名字带头结点的单链表head为空的条件是head-next=NULL18.采用邻接表存储的图，其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+143.深度优仙遍历,拓扑排序判断出一个有向图是否有环（回路）44.二叉查找树的查找效率与二叉树的树型有关,在呈单枝树时其查找效率最低45.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用后序遍历方法最合适46.采用分块查找方法，既能实现较快地查找线性表，又能适应动态变化的要求47.顺序表又称为向量,采用定长的一维数组存储48.链表逻辑上相邻的元素在物理位置上不要求也相邻