数据结构——期末复习

1、数据结构期末复习数据结构期末复习主要知识点主要知识点算法的时间复杂度计算方法算法的时间复杂度计算方法单链表单链表堆栈和队列的概念和应用堆栈和队列的概念和应用串的概念和应用串的概念和应用树的概念和应用树的概念和应用图的概念和应用图的概念和应用查找和排序查找和排序算法满足以下性质算法满足以下性质: (1)输入性输入性(2)输出性输出性 (3)有限性有限性 (4)确定性确定性 (5)可执行性可执行性算法设计满足以下目标算法设计满足以下目标: (1)正确性正确性 (2)可读性可读性 (3)健壮性健壮性 (4)高时间效率高时间效率 (5)高空间效率高空间效率算法的时间复杂度计算方法算法的时间复杂度计算方

2、法常见的时间复杂度表示：常见的时间复杂度表示：O(1)，O(n)，O(n2) ，O(n3)，O(lbn) ，O(lgn)算法时间复杂度定义算法时间复杂度定义:T(n)=O(f(n),当且仅当存在正常数当且仅当存在正常数c和和n0，对所有的对所有的n(n n0)满足满足T(n)cf(n) 。T（n）为算法的）为算法的基本语句执行次数，称为时间复杂度，随基本语句执行次数，称为时间复杂度，随n增大与增大与f（n）增）增长接近相同，级，用长接近相同，级，用O(f（n）)表示其复杂度即可称同一个表示其复杂度即可称同一个数量。数量。推导大推导大O阶的方法阶的方法:(1)用常数用常数1取代运行时间中的所有加

3、法常数。取代运行时间中的所有加法常数。(2)在修改后的运行次数函数中，只保留最高阶项。在修改后的运行次数函数中，只保留最高阶项。(3)如果最高阶项在且不是如果最高阶项在且不是1，则去除与这个项相乘的常数，则去除与这个项相乘的常数最后得到的结果就是大最后得到的结果就是大O阶阶 例例1 求和算法，求求和算法，求1+2+3.+99+100=5050。int i,sum=0,n=100; /执行了执行了1次次 for(i=1;i=n;i+) /执行执行n+1次次 sum=sum+i; /执行执行n次次 printf(“%d”,sum); /执行了执行了1次次 该算法一共执行了该算法一共执行了1+n+1

4、+n+1=2n+3次次在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：数量必须表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(n) 称为线性阶称为线性阶注意：分析这类算法的复杂度关键是分析循环结构的运行情况注意：分析这类算法的复杂度关键是分析循环结构的运行情况 例例2 求和算法，求求和算法，求1+2+3.+99+100=5050。int sum=0,n=100; /执行

5、了执行了1次次sum=(1+n)*n/2 /执行执行1次次printf(“%d”,sum); /执行了执行了1次次 该算法一共执行了该算法一共执行了1+1+1=3次次在求时间复杂度的时候只需要分析影响一个算法时在求时间复杂度的时候只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(1) 称为常数阶称为常数阶注意：不管这个常数是多少，我们都记做注意：不管这个常数是多少，我们都记做O(1) ，而，而不是不是O(3)。 例例3 求和算法，求求

6、和算法，求1+2+3.+99+100+.=int i,j,x=0,sum=0,n=100; /执行了执行了1次次 for(i=1;i=n;i+) for(j=1;j=n;j+) x+; /执行执行n*n次次 sum=sum+x; printf(“%d”,sum); /执行了执行了1次次 在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分在求时间复杂度的时候我们忽略头尾循环判断的开销，只需要分析影响一个算法时间复杂度的主要部分即可，即基本操作的数量析影响一个算法时间复杂度的主要部分即可，即基本操作的数量必须表示成输入规模的函数：必须表示成输入规模的函数：该算法的该算法的时间复杂度为时间复杂

7、度为 T(n)=O(n2) 称为平方阶称为平方阶注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数注意：循环的时间复杂度等于循环体的复杂度乘以该循环的次数 例例1-3 设数组设数组a和和b在前边部分已赋值，求如下两个在前边部分已赋值，求如下两个n阶矩阶矩阵相乘运算算法的时间复杂度。阵相乘运算算法的时间复杂度。for(i=0;in;i+) for(j=0;jn;j+) cij=0; /基本语句基本语句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本语句基本语句2 该算法的该算法的时间复杂度为时间复杂度为 T(n)=O(n3) 例例1-4 设设n为如下算法处理的数据

8、个数，求如下算法的为如下算法处理的数据个数，求如下算法的时间复杂度。时间复杂度。 for(i=1;i=n;i=2*i) printf(“i=%dn”，i)；解解: :设基本语句的执行次数为设基本语句的执行次数为T(n), ,有有2 2T T( (n n) ) n,即有即有T(n) lbn。所以该算法的时间复杂度为所以该算法的时间复杂度为T(n)=O(lb n)。 称为对数阶称为对数阶 例例1-5:下边的算法是用冒泡排序法对数字下边的算法是用冒泡排序法对数字a中的中的n个整数个整数类型的数据元素类型的数据元素(a0an-1)，从小到大进行排序，求该算从小到大进行排序，求该算法的时间复杂度。法的时

9、间复杂度。void BubbleSort(int a,int n) int i,j,flag=1; int temp; for(i=1;in&flag=1;i+) flag=0; for(j=0;jaj+1) flag=1; temp=aj; aj=aj+1; aj+1=temp; 解解:该算法基本语句执行次数与原始数据序列大小情况有关该算法基本语句执行次数与原始数据序列大小情况有关系，此时，按系，此时，按最坏情况统计最坏情况统计。设基本语句的执行次数为设基本语句的执行次数为T(n),最坏情况下有最坏情况下有 T(n)n+4*n2/2因因T(n) n+2* n2 c* n2,其中其中c为常数，

10、所以该算法的时间复杂度为为常数，所以该算法的时间复杂度为T(n)=O(n2)。 算法的时间复杂度是衡量一个算法好坏的重要指标。一算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有般来说，具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际可接受、可实际使用使用的算法的算法;具有具有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小小时才可使用的算法。时才可使用的算法。 例例1-6 下面的算法是在一个有下面的算法是在一个有n个数据元素的数组个数据元素的数组a中删中删除第除第i个位置的数组元素，要求当删除成功时数组元素个数个位置的数组元素，要求当删

11、除成功时数组元素个数减减1，求该算法的时间复杂度。其中数组下标从，求该算法的时间复杂度。其中数组下标从0至至n-1。int Delete(int a, int &n,int i) int j; if(i=n) return 0; /删除位置错误，失败返回删除位置错误，失败返回 for(j=i+1;jnext=p-next;p-next=s;注：两条语句顺序不能颠倒，即注：两条语句顺序不能颠倒，即“先勾右链，再勾左链先勾右链，再勾左链”单链表单链表2).删除带头结点单链表第一个数据元素结点删除带头结点单链表第一个数据元素结点pa0a1an-1headdata next核心操作语句为：核心操作语句

12、为：p=head；s=p-next; *x=s-datap-next=p-next-next; free(s);3).在不带头结点单链表第一个数据元素前插入结点在不带头结点单链表第一个数据元素前插入结点a0a1an-1headxs(a) 插入前插入前a0a1an-1headxs(b) 插入后插入后核心操作语句为：核心操作语句为：s-next=head;head=s;4).在不带头结点单链表其他数据元素前插入结点在不带头结点单链表其他数据元素前插入结点pai-1a0aian-1headdata nextxs核心操作语句为：核心操作语句为：s-next=p-next;p-next=s;5).删除不

13、带头结点单链表第一个数据元素结点删除不带头结点单链表第一个数据元素结点a0a1an-1headdata next6).删除不带头结点单链表其他数据元素结点删除不带头结点单链表其他数据元素结点pai-1a0aian-1headdata nextai+1核心操作语句为：核心操作语句为：s=head-next;head=head-next; free(s);核心操作语句为：核心操作语句为：s=p-next; *x=s-datap-next=p-next-next; free(s);1、在带头结点的单链表、在带头结点的单链表head中，若中，若p所指结点不是最后结点所指结点不是最后结点，在，在p之后插

14、入之后插入s所指结点，则执行的核心代码是（所指结点，则执行的核心代码是（ ）。）。s-next=p；p-next=s；s-next=p-next；p-next=s；C. s-next=p-next；p=s；D. p-next=s；s-next=p；2、在带头结点的单链表、在带头结点的单链表head中，若删除中，若删除p所指结点的后继结所指结点的后继结点，则执行的核心代码是（点，则执行的核心代码是（ ）。）。p-next=p-next-next；p=p-next；p-next=p-next-next；C. p-next=p-next；D. p=p-next-next；习题练习习题练习BA4、单链

15、表中，增加一个头结点的目的是为了（、单链表中，增加一个头结点的目的是为了（ ）。）。使单链表至少有一个结点。使单链表至少有一个结点。 标识表结点中首结点的位置。标识表结点中首结点的位置。C. 方便运算的实现。方便运算的实现。 D. 说明单链表是线性表的链式存储。说明单链表是线性表的链式存储。5、带头结点的单链表、带头结点的单链表head为空的判定条件是（为空的判定条件是（ ）。）。A. head=NULL B. head-Next=NULL C. head-next=head D. head!=NULLCB6、已知已知head为带头结点的单链表，为带头结点的单链表，p为其中非首元的结点，分为其

16、中非首元的结点，分别写出以下操作的序列：别写出以下操作的序列：（1）将）将s结点插入结点插入p结点之后；结点之后；（2）删除）删除p的直接后继结点；的直接后继结点；（3）删除尾元结点；）删除尾元结点；s-Next=p-Next; p-Next=s;q= p-Next; p-Next= p-Next-Next; free(q);p=head;While(p-Next-Next!=NULL) p=p-Next;q= p-Next;p-Next= p-Next-Next;free(q);堆栈和队列的基本概念和应用堆栈和队列的基本概念和应用堆栈的数据元素及逻辑关系与线性表完全相同，但是操作受限。堆栈的

17、数据元素及逻辑关系与线性表完全相同，但是操作受限。(1)(1)定义定义: :限定只能在固定一端进行插入和删除操作的线性表。限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。特点：后进先出。故又称故又称后进先出表后进先出表(2)允许进行插入和删除操作的一端称为允许进行插入和删除操作的一端称为栈顶栈顶，另一端称为，另一端称为栈底。栈底。队列的基本概念队列的基本概念堆栈的基本概念堆栈的基本概念(1)(1)定义定义: :只能在表的一端进行插入操作，在表的另一端进行只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表（又称删除操作的线性表（又称先进先出表先进先出表）。一个队列的示意图

18、）。一个队列的示意图如下：如下：a0a1a2an-1队头队头队尾队尾队尾插入队尾插入队头删除队头删除1、有六个元素、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪的顺序进栈，问下列哪一个不是合法的出栈序列？（一个不是合法的出栈序列？（ ）。）。5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2、一个栈的输入序列为、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能，则下列序列中不可能是栈的输出序列的是（是栈的输出序列的是（ ）。）。A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D.

19、1 5 4 3 23、 某堆栈的输入序列为某堆栈的输入序列为a, b，c ，d,下面的四个序列中，下面的四个序列中，不可能是它的输出序列的是（不可能是它的输出序列的是（ ）。）。a，c，b，d B. b, c，d，a C. c，d，b， a D. d, c，a，b习题练习习题练习CBD5、栈和队列的共同点是栈和队列的共同点是（ ） 。A都是先进后出都是先进后出。 B都是先进先出都是先进先出。C只允许在端点处插入和删除元素只允许在端点处插入和删除元素。 D没有共同点没有共同点。6、以下以下（ ）不是队列的基本运算不是队列的基本运算?A从队尾插入一个新元素从队尾插入一个新元素。B从队列中删除第从队

20、列中删除第i个元素个元素。C判断一个队列是否为空判断一个队列是否为空。D读取队头元素的值读取队头元素的值。CB7、顺序循环队列中判定队列满的条件为（、顺序循环队列中判定队列满的条件为（ ）。）。 A.rear=front B. count 0 C. count 0 & rear=front D. count 0 | rear=front8、顺序循环队列中判定队列、顺序循环队列中判定队列空空的条件为（的条件为（ ）。）。 A.rear=front B. count = 0 C. count 0 & rear=front D. count 0 | rear=frontCB9、输入序列为输入序列为A

21、BC，可以变为，可以变为CBA时，经过的栈操作为时，经过的栈操作为（ ）。Apush，pop，push，pop，push，popBpush，push，push，pop， pop， popCpush，push，pop， pop，push，popDpush，pop，push，push，pop， pop10、允许对队列进行的操作有允许对队列进行的操作有（ ）。A对队列中的元素排序对队列中的元素排序B取出最近进队的元素取出最近进队的元素C在队头元素之前插入元素在队头元素之前插入元素D删除队头元素删除队头元素11、对于循环队列对于循环队列（ ）。A无法判断队列是否为空无法判断队列是否为空B无法判断队列是

22、否为满无法判断队列是否为满C队列不可能满队列不可能满D以上说法都不对以上说法都不对BDD12、若用一个大小为若用一个大小为6的数值来实现循环队列，且当前的数值来实现循环队列，且当前rear和和front的值分别为的值分别为0和和3，当从队列中删除一个元素，再加，当从队列中删除一个元素，再加入两个元素后，入两个元素后，rear和和front的值分别为的值分别为（ ）。A1和和5 B2和和4 C4和和2D5和和113、队列的队列的“先进先出先进先出”特性是指特性是指（ ）。A最早插入队列中的元素总是最后被删除最早插入队列中的元素总是最后被删除。B当同时进行插入、删除操作时，总是插入操作优先当同时进

23、行插入、删除操作时，总是插入操作优先。C每当有删除操作时，总是要先做一次插入操作每当有删除操作时，总是要先做一次插入操作。D每次从队列中删除的总是最早插入的元素每次从队列中删除的总是最早插入的元素。DB、串（又称字符串）是由、串（又称字符串）是由n(n 0)n(n 0)个字符组成的有限序列。个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）（它是数据元素为单个字符的特殊线性表。）、串长、串长: :串中字符的个数（串中字符的个数（n0n0）。）。、空串、空串: :串中字符的个数为串中字符的个数为0 0 时称为空串时称为空串 。、空格串、空格串: :由一个或多个空格符组成的串。由一个或

24、多个空格符组成的串。、子串、子串: :串串S S中任意个连续的字符序列叫中任意个连续的字符序列叫S S的子串的子串; S; S叫主串。叫主串。、子串位置、子串位置: :子串的第一个字符在主串中的序号子串的第一个字符在主串中的序号( (从从0 0开始开始) )。、字符位置、字符位置: :字符在串中的序号字符在串中的序号( (从从0 0开始开始) ) 。、串相等、串相等: :串长度相等，且对应位置上字符相等。（即两个串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）串中的字符序列一一对应相等。）串的基本概念和应用串的基本概念和应用35 1、现有以下、现有以下4个字符串：个字符

25、串：a =“BEI” b =“JING” c = “BEIJING” d = “BEI JING” 他们各自的长度？他们各自的长度？答：答：a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是0。 a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？答：答：a ：3，b ：4，c ：7，d：8。 空串是哪个串的子串？空串是哪个串的子串？ a是不是自己的子串？是不是自己的子串？答：空串是任意串的子串；任意串答：空串是任意串的子串；任意串S S都是都是S S本身的子串本身的子串，除，除S S本身外，本身外，S S的其他子串称为的其他子串称为S S的的真子串。

26、真子串。子串个数问题？子串个数问题？如：串如：串S=S=“produceproduce”，则，则S S共多少个子串？长为共多少个子串？长为2,32,3的子串的子串分别多少个？分别多少个？习题练习习题练习2 2、设、设S1=“Data Structure Course”,S2=“Structure”,S1=“Data Structure Course”,S2=“Structure”,S3=“Base”S3=“Base”，求，求（1 1）Length(S1); Length(S1); （2 2）Compare(S2,S3)Compare(S2,S3)；（3 3）Insert(S1,5,S3)Ins

27、ert(S1,5,S3)；（4 4）Delete(S1,5,9);Delete(S1,5,9);（5 5）SubString(S1,5,9,T)SubString(S1,5,9,T)；（6 6）Search(S1,0,S2);Search(S1,0,S2);（7 7）Replace(S1,0,S2,S3);Replace(S1,0,S2,S3);36Length(S1)=21Length(S1)=21。返回值为返回值为1 1。输出输出“Data BaseStructure CourseData BaseStructure Course”。输出输出“Data CourseData Course”

28、。输出输出T=“Structure”T=“Structure”。返回值为返回值为5 5。输出输出“Data Base CourseData Base Course”。3 3、串的长度是指串的长度是指（ ）。A A串中所含不同字母的个数串中所含不同字母的个数B B串中所含字符的个数串中所含字符的个数C C串中所含不同字符的个数串中所含不同字符的个数D D串中所含非空格字符的个数串中所含非空格字符的个数4 4、串是一种特殊的线性表，其特殊性体现在串是一种特殊的线性表，其特殊性体现在（ ）。A A可以顺序存储可以顺序存储B B数据元素是一个字符数据元素是一个字符C C可以链式存储可以链式存储D D数

29、据元素可以是多个字符数据元素可以是多个字符BBABCGEIDHFJFLK结点的度结点的度：结点所拥有的子树的个数结点所拥有的子树的个数( (也可称分支数也可称分支数) )。 叶结点（或叶子结点）叶结点（或叶子结点）：度为度为0 0的结点，也称作的结点，也称作终端结点。终端结点。 分支结点分支结点：度不为度不为0 0的结点，一棵树中除叶结点外的所有结的结点，一棵树中除叶结点外的所有结点都是分支结点。点都是分支结点。 树的基本概念和应用树的基本概念和应用孩子结点孩子结点：树中某个结点的所有子树的根结点，称为该结点的树中某个结点的所有子树的根结点，称为该结点的孩子结点。孩子结点。双亲结点双亲结点：若

30、树中某结点有孩子结点，则这个结点就称作它的若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点。孩子结点的双亲结点。 兄弟结点兄弟结点：具有相同的双亲结点的结点之间互为兄弟结点。具有相同的双亲结点的结点之间互为兄弟结点。 树的度树的度：树中所有结点的度的最大值。树中所有结点的度的最大值。 结点的层次：结点的层次：从根结点到树中某结点所经路径上的分支数，从根结点到树中某结点所经路径上的分支数，根的层次为根的层次为0 0，其它为双亲层次加，其它为双亲层次加1 1 。树的深度：树的深度：树中所有结点的层次的最大值。树中所有结点的层次的最大值。 无序树：无序树：树中任意一个结点的各孩子结点之

31、间的不要求区分树中任意一个结点的各孩子结点之间的不要求区分次序，即左右颠倒后还是同一棵树；（本章的次序，即左右颠倒后还是同一棵树；（本章的“树树”）。）。 有序树：有序树：树中任意一个结点的各孩子结点有严格排列次序的树中任意一个结点的各孩子结点有严格排列次序的树（本章的树（本章的“二叉树二叉树”）。）。森林：森林：m（m0）棵树的集合。）棵树的集合。 二叉树基本特点：二叉树基本特点： 每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2的结点）；的结点）； 左子树和右子树左子树和右子树次序不能颠倒次序不能颠倒。所以下面是两棵不同的树。所以下面是两棵不同的树。二叉树形态

32、：二叉树形态：二叉树的所有结点的形态有五种：空二叉树的所有结点的形态有五种：空 、无左右、无左右子树、只有左子树、只有右子树、左右子树均存在。子树、只有左子树、只有右子树、左右子树均存在。（形态只看形状，不看具体结点元素值）（形态只看形状，不看具体结点元素值）分析：只有三个结点（假设分别为分析：只有三个结点（假设分别为A,B,C）的二叉树形态共有）的二叉树形态共有哪些情况？哪些情况？满二叉树：满二叉树：在一棵二叉树中，如果所有在一棵二叉树中，如果所有分支结点分支结点都存在左都存在左 子树和右子树，并且所有叶子结点都在同一层上，这样的子树和右子树，并且所有叶子结点都在同一层上，这样的 二叉树称为

33、满二叉树。（所有的存在的层次上结点都满）二叉树称为满二叉树。（所有的存在的层次上结点都满）完全二叉树：完全二叉树：如果一棵深度为如果一棵深度为k k，有，有n n个结点的二叉树中各个结点的二叉树中各 结点能够与深度为结点能够与深度为k k的顺序编号的满二叉树从的顺序编号的满二叉树从1 1到到n n标号的标号的 结点相对应的二叉树称为完全二叉树。（相对于深度相同结点相对应的二叉树称为完全二叉树。（相对于深度相同 的满二叉树来说完全二叉树只可能最后一层缺少最后面连的满二叉树来说完全二叉树只可能最后一层缺少最后面连 续的结点）续的结点） 如下图所示如下图所示满二叉树也是一棵特殊的完全二叉树满二叉树也

34、是一棵特殊的完全二叉树。BACEDFGHIJKLMNO(a)满二叉树满二叉树 BACEDFGHIJ(b)完全二叉树完全二叉树 问题问题: :一个深度为一个深度为h h的完全二叉树最多有多少个结点的完全二叉树最多有多少个结点? ?最最少有多少个结点少有多少个结点? ?根结点深度为根结点深度为0 0。最多最多2 2(h+1)(h+1)-1-1个，最少个，最少2 2h h个个二叉树的性质二叉树的性质性质性质1 （理解、记结论）（理解、记结论）性质性质2 =-1，表示空二叉树，没有一个结点；，表示空二叉树，没有一个结点；=0，表示只有一个根结点。表示只有一个根结点。（理解、记结论）（理解、记结论）性质

35、性质3 具有具有n个结点的个结点的完全二叉树完全二叉树的深度的深度k为大于或等于为大于或等于lb(n+1)-1的最小整数。（的最小整数。（要求会根据结点数求深度要求会根据结点数求深度）如：如：20个结点的完全二叉树深度为？个结点的完全二叉树深度为？答：答：2 2k k-1n=2-1n=2k+1k+1-1-1，k=4k=4哈夫曼树的基本概念哈夫曼树的基本概念 从从A A结点到结点到B B结点所经过的分支序列叫做从结点所经过的分支序列叫做从A A结点到结点到B B结点的结点的路径；路径；从从A A结点到结点到B B结点所经过的分支个数叫做从结点所经过的分支个数叫做从A A结点到结点到B B结点结点

36、的的路径长度；路径长度；从二叉树的根结点到二叉树中所有叶结点的路径从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作长度之和称作该二叉树的路径长度。该二叉树的路径长度。设二叉树有设二叉树有n n个带权值的个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和称作该长度与相应叶结点权值的乘积之和称作该二叉树的带权路径长二叉树的带权路径长度（度（WPLWPL），），即：即：WPL = niiilw1 其中，其中，wi为第为第i i个叶结点的权值，个叶结点的权值，li为从根结点到第为从根结点到第i个个叶

37、结点的路径长度。叶结点的路径长度。 1 1、已知一棵树已知一棵树T=(D,R),T=(D,R),D=A,B,C,D,E,F,G,H,I,J,K,L,M,ND=A,B,C,D,E,F,G,H,I,J,K,L,M,N；R=, , , R=, , , ，, , , , , , , , 请画出这棵请画出这棵树，并回答以下问题：树，并回答以下问题：(1)(1)哪个是根结点？哪个是根结点？ (2)(2)哪些是叶子结点？哪些是叶子结点？ (3)(3)哪个是结点哪个是结点G G的双亲？的双亲？ (4)(4)哪些是结点哪些是结点E E的孩子？的孩子？(5)(5)哪些是哪些是E E的兄弟？的兄弟？ 习题练习习题练

38、习(6)(6)哪些是哪些是F F的兄弟？的兄弟？ (7)(7)结点结点N N的层次是多少？的层次是多少？(8)(8)以结点以结点C C为根的子树的深度是多少？为根的子树的深度是多少？ (9)(9)该树的深度是多少？该树的深度是多少？ (10)(10)该树的度是多少？该树的度是多少？2 2、某二叉树结点的中序序列为某二叉树结点的中序序列为ABCDEFGABCDEFG，后序序列为，后序序列为BDCAFGEBDCAFGE，则其左子树中结点数目为，则其左子树中结点数目为（ ）。）。A A3 3B B2 2 C C4 4D D5 53 3、对某二叉树进行先序遍历的结果为、对某二叉树进行先序遍历的结果为A

39、BDEFCABDEFC，中序遍历，中序遍历的结果为的结果为DBFEACDBFEAC，则后序遍历的结果是（，则后序遍历的结果是（ ）。）。DBFEAC DBFEAC B. B. DFEBCADFEBCAC. BDFECAC. BDFECAD. BDEFACD. BDEFACCB4 4、设、设a,ba,b为一棵二叉树上的两个结点，在中序遍历时，为一棵二叉树上的两个结点，在中序遍历时，a a在在b b前面的条件是（前面的条件是（ ）。）。a a在在b b的右方的右方 B. B. a a在在b b的左方的左方C. aC. a是是b b的祖先的祖先D. aD. a是是b b的子孙的子孙5 5、若以、若以

40、4,5,6,7,84,5,6,7,8作为权值构造哈夫曼树，则该树的作为权值构造哈夫曼树，则该树的带权路径长度为（带权路径长度为（ ）。）。A. 67A. 67 B. 68B. 68C. C. 6969 D. 70 D. 70BC6 6、树最适合用来表示（、树最适合用来表示（ ）。）。有序数据元素。有序数据元素。 无序数据元素。无序数据元素。 C. C. 元素之间具有分支层次关系的数据。元素之间具有分支层次关系的数据。 D. D. 元素之间无联系的数据。元素之间无联系的数据。7 7、假设用于通讯的电文仅由、假设用于通讯的电文仅由8 8个字母个字母A A、B B、C C、D D、E E、F F、G

41、 G、H H组成，字母在电文中出现的频率分别为：组成，字母在电文中出现的频率分别为：0.070.07，0.190.19，0.020.02，0.060.06，0.320.32，0.030.03，0.210.21，0.100.10。请为这。请为这8 8个字母设计哈夫曼编码。个字母设计哈夫曼编码。C8 8、已知权值集合为、已知权值集合为5,7,2,3,6,95,7,2,3,6,9，要求给出哈夫曼树，要求给出哈夫曼树，并计算带权路径长度，并计算带权路径长度WPLWPL。9 9、已知一棵二叉树的先序序列：、已知一棵二叉树的先序序列：ABDGJEHCFIKLABDGJEHCFIKL；中序序；中序序列：列：

42、DJGBEHACKILFDJGBEHACKILF。画出二叉树的形态。画出二叉树的形态。1010、设有如下图所示的树，要求：、设有如下图所示的树，要求：（1 1）将其转换为二叉树；）将其转换为二叉树；（2 2）分别写出该树的先根遍历序列和后根遍历序列；）分别写出该树的先根遍历序列和后根遍历序列；（3 3）分别写出转换后的二叉树的前序、中序以及后序遍）分别写出转换后的二叉树的前序、中序以及后序遍历序列。历序列。ABCDEFGHIJK（1）完全图：）完全图：在有在有n个顶点的个顶点的无向图无向图中，若有中，若有n(n-1)/2条边，条边，即任意两个顶点之间有且只有一条边，则称此图为即任意两个顶点之间

43、有且只有一条边，则称此图为无向完全图无向完全图；在有；在有n个顶点的有向图中，若有个顶点的有向图中，若有n(n-1)条边，即任意条边，即任意两个顶点两个顶点之间之间有且只有有且只有方向相反的两条边方向相反的两条边，则称此图为，则称此图为有向完全图有向完全图。（2）邻接结点：）邻接结点：在无向图在无向图G中，若（中，若（u,v）是是E(G)中的一条边中的一条边，则称，则称u和和v互为邻接结点互为邻接结点，并称边（，并称边（u,v）依附于结点依附于结点u和和v；在；在有向图有向图G中，若中，若u,v是是E(G)中的一条边，则称结点中的一条边，则称结点u邻接到邻接到结点结点v，结点结点v邻接自结点邻

44、接自结点u，并称边并称边u,v和结点和结点u和结点和结点v相相关联。关联。 图的基本概念和应用图的基本概念和应用（3）结点的度结点的度：结点结点v的度是与它的度是与它相关联的边的条数相关联的边的条数，记作，记作TD(v)。有向图中：结点的度有向图中：结点的度 = 入度入度 + 出度出度。 即即TD(v)=ID(v)+OD(v)思考：在无向图中，所有顶点度的和是图中边数有何关系？思考：在无向图中，所有顶点度的和是图中边数有何关系？答：所有顶点度的和是图中边数的答：所有顶点度的和是图中边数的2倍。倍。有向图中：所有出度和有向图中：所有出度和=入度和入度和=边总数边总数（4）连通图和强连通图：）连通

45、图和强连通图：在无向图中，若从结点在无向图中，若从结点vi到结点到结点vj有有路径，则称结点路径，则称结点vi和结点和结点vj是连通的。如果图中任意一对结点是连通的。如果图中任意一对结点都是连通的，则称该图是都是连通的，则称该图是连通图连通图。在有向图中，若对于任意一对结点在有向图中，若对于任意一对结点vi和结点和结点vj（vivj）都存在都存在路径，则称图路径，则称图G是强连通图。是强连通图。（5）最小连通子图：）最小连通子图：G1包含包含G的全部结点，但只有的全部结点，但只有G中足够中足够构成连通图的最少数目的边，则构成连通图的最少数目的边，则G1称为称为G的最小连通子图的最小连通子图（6

46、）生成树生成树：一个连通图的最小连通子图称作该图的生成树。一个连通图的最小连通子图称作该图的生成树。有有n个结点的连通图的生成树有个结点的连通图的生成树有n个结点和个结点和n-1条边条边。 生成树一般是对无向图生成树一般是对无向图来讨论。来讨论。 一个有一个有n n个顶点的连通图的个顶点的连通图的生成树生成树是是原图的极小连通子图原图的极小连通子图，它，它包含原图中的所有包含原图中的所有n n个顶点，并且有保持图连通的最少的边。个顶点，并且有保持图连通的最少的边。 若在生成树中删除一条边就会使该生成树因变成非连通图而不若在生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；再

47、满足生成树的定义；若在生成树中增加一条边就会使该生成树中因存在回路而不再若在生成树中增加一条边就会使该生成树中因存在回路而不再满足生成树的定义；满足生成树的定义；一个连通图的生成树可能有许多；一个连通图的生成树可能有许多；有有n n个顶点的无向连通图，无论它的生成树的形状如何，一定个顶点的无向连通图，无论它的生成树的形状如何，一定有且只有有且只有n-1n-1条边。条边。 1 1、采用邻接表存储的图的深度优先遍历算法类似于二叉、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（树的（ ）。）。A A先序遍历先序遍历 B B中序遍历中序遍历 C C后序遍历后序遍历 D D按层遍历按层遍历2 2、

48、采用邻接表存储的图的广度优先遍历算法类似于二叉、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（树的（ ）。）。A A先序遍历先序遍历 B B中序遍历中序遍历 C C后序遍历后序遍历 D D按层遍历按层遍历3 3、具有、具有n n 个结点的连通图至少有（个结点的连通图至少有（ ）条边。）条边。A An n1 1B B n n C C n n（n n1 1）/2/2 D D 2n2nAAD4 4、使用克鲁斯卡尔算法构造出图、使用克鲁斯卡尔算法构造出图G G的一颗最小生成树。的一颗最小生成树。127654318672051084232512155 5、使用普里姆算法构造如下图所示的一颗最小生成

49、树。、使用普里姆算法构造如下图所示的一颗最小生成树。52346165356516426 6、已知如下图的邻接表，请给出顶点、已知如下图的邻接表，请给出顶点V1V1出发的深度优先出发的深度优先遍历序列，以及顶点遍历序列，以及顶点V1V1出发的广度优先遍历序列。出发的广度优先遍历序列。直接插入排序算法原理：直接插入排序算法原理： 顺序地把待排序的数据元素按其关键字值的大小插顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。入到已排序数据元素子集合的适当位置。直接插入算法效率直接插入算法效率时间复杂度：最好情况下（已经按关键字排序），时间时间复杂度：最好情况下（已经按关键字排序），时间复杂度为复杂度为O(n)O