数据结构第六章PPT培训课件.pptVIP

第六章二叉树与树 提示 基本内容二叉树的概念、性质和存储结构；二叉树的遍历和线索化算法；树的定义、存储结构、树与二叉树的转换、树的遍历；哈夫曼树的构造； 学习要点1．掌握二叉树的结构特性，2．熟悉二叉树的各种存储结构的特点及适用范围；3．遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作；4．理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。5．熟悉树的各种存储结构及其特点，掌握树和与二叉树的转换方法，掌握树的遍历方法 ；6．了解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法； 内容提要 6.1 二叉树概念 6.2 二叉树遍历 6.3 树和森林 6.4 二叉树与树的应用 6.5 栈、递归、树与回溯法算法 小结 期中习题 第二章 线性表 一、填空题 1.为了便于讨论，有时将含n(n=0)个结点的线性结构表示成(a1，a2,……an)，其中每个ai代表一个______。a1称为______结点，an称为______结点，i称为ai在线性表中的________或______。对任意一对相邻结点ai、ai┼1(1=in),ai称为ai┼1的直接______ai┼1称为ai的直接______。 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为______或______。 3.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlist L，datatype x，int i) /*将X插入到顺序表L的第i-1个位置*/ { if( L.last == maxsize) error(“表满”)； if((i1)||(iL.last+1))error(“非法位置”); for(j=L.last;j=i;j--)______; L.data[i-1]=x; L.last=L.last+1; } 4.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________，平均时间复杂性量级是________。 5.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i1)||(iL.last))error(“非法位置”)； for(j=i+1;j=L.last;j++)________; L.last=L.last-1; } 6.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为________和________。 7.线性表的常见链式存储结构有________、________和________。 8.单链表表示法的基本思想是用________表示结点间的逻辑关系。 9.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为________，其它结点称为________。 10.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {________; j=0; while(p-next!=NULL) {________________; j++; } return(j); /*回传表长*/ } 11.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i) { p=find_lklist(head,i-1); if(____________________________) { q=________________; p-next=q-next; free(q); } else error(“不存在第i个结点