算法与数据结构复习资料

《算法与数据结构复习资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》复习重点一、第2章程序性能1、给出一个程序段，会写出该程序段的时间复杂度；二、第3章线性表1、顺序存储结构的特点①表中元素可以随机访问；②非表尾的插入和删除操作需要移动元素；③表空间无法动态扩充，需预先按最大空间分配，存储空间利用率低；④相邻元素的物理位置相邻⑤无需为维护表中元素的逻辑关系增加额外的存储空间2、若用数组实现表，设表元素总数为n，在第k个元素后插入一个新元素，需要后移的元素数目为n-k。设在表的任何合法位置上插入元素的概率均等，则插入操作所需要的元素移动平均次数为n/2。3、若用数组实现表，

2、设表元素总数为n，删除第k个元素，需要前移的元素数目为n-k。设删除表的任何元素的概率均等，则删除操作所需要的元素移动平均次数为（n-1）/2。4、链式存储结构的特点①表元素分散存放，物理位置不一定相邻；②每个结点包含指向下一结点的指针域；③只能顺序搜索，不能随机访问；④插入和删除操作只需要通过修改指针实现，效率较高⑤不需为表预留空间，存储空间利用率高，表容量可动态扩充⑥每个结点中的指针域需占用额外空间5、在带哨兵结点的单循环链表中，设置尾指针last指向链尾结点，每个结点中的后继指针域为next，则判断表空的表达式为la

3、st->next==last；在带哨兵结点的双循环链表中，设置指针header指向哨兵结点，每个结点中的后继指针域为next,前驱指针域为prior，则判断表空的表达式为header->next==header或header->prior==header。6、在带哨兵结点的单链表的插入和删除操作中，链指针的修改7、理解静态链表①静态链表中的指针域又称为游标或模拟指针，存放下一元素在数组中的下标②多条静态链表可共用一个数组空间③在数组空间中，静态链表中的元素可以分散存放，即相邻元素的下标不一定相邻④静态链表的扩充受到数组空间

4、容量的限制三、第4章栈1、栈的操作原则为先进后出或后进先出，插入和删除操作均在栈顶方向上进行。2、用数组实现栈的入栈和出栈函数；61、用数组实现栈的优缺点：①栈上的基本操作都能在常量时间内完成，效率较高；②为避免栈发生溢出，通常需要预置一个较大栈空间，存储空间利用率较低；为提高空间利用率，可让多栈共享数组空间；2、用链表实现栈的特点：链栈空间可以动态扩充一、第5章队列1、队列的操作原则是先进先出或后进后出，插入操作在队尾进行，删除操作在队头进行2、若用循环数组实现队列，设置front指向队头元素前一单元，rear指向队尾元

5、素，并采用总剩一个单元不利用的方法区分满空状态，则当front和rear满足什么关系时队列为空，满足什么关系时队列为满？3、用循环数组实现队列的入队和出队函数。二、第6章树1、树的基本概念，包括树的度、叶结点或终端结点、分支结点、内部结点、兄弟、堂兄弟、祖先、子孙、树的高度、有序树、无序树。2、树的表示法①父结点数组表示法可以快速找到结点的父结点，但查询儿子结点和兄弟结点可能要遍历整个数组；②在儿子表示法中，若采用定长结点的多重链表结构，则表示一棵有n个结点度为d的树必有nd-(n-1)个空链域③儿子链表表示法适合于查找子

6、结点，但不适合于查找父结点和兄弟结点④带双亲的儿子链表表示法适合于查找子结点、父结点和兄弟结点⑤左儿子右兄弟表示法方便查找子结点和兄弟结点，但不方便查找父结点⑥给出一棵树，会用父结点数组表示法、儿子链表表示法、左儿子右兄弟表示法表示它。3、二叉树的概念①二叉树是有序树②度为2的树不一定是二叉树③度为2的有序树不一定是二叉树④子树有严格左右次序之分，且度≤2的树是二叉树4、具有3个结点的树有5种形态，具有3个结点的二叉树有3种形态。5、满二叉树的特点：①所有叶结点都集中在最底层②不存在度为1的结点③每一层上的结点数均达到最大

7、值④所有分支结点都存在左子树和右子树例题：①高度为8的满二叉树的结点总数为255。61、完全二叉树的特点：①叶结点只可能在层次最大的两层上出现②最下层的叶结点一定集中在该层的左端③度小于2的结点只可能位于最下两层④除最下层外，其余各层均满⑤度为1的结点只可能出现在倒数第二层⑥对任一结点，若其右分支下的子孙最大层次为s，则其左分支下的子孙的最大层次必为s或s+12、二叉树的性质①具有n个结点的非空二叉树共有n-1个分支②非空二叉树的第i层上至多有2i-1个结点（i≥1）③高度为h的非空二叉树至多有2h-1个结点④高度为h的完

8、全二叉树至多有2h-1个结点，至少有2h-1个结点⑤若非空二叉树有n0个叶结点，n2个度为2的结点，则n0=n2+1⑥具有n个结点的完全二叉树的高度为h=log2n+1。⑦具有n个结点的二叉树的最小高度为log2n+1，最大高度为n。⑧若对具有n个结点的完全二叉树按照层次从上到下，每层从左到右的顺序进行