离散数学课件总复习之习题讲解.ppt

《离散数学课件总复习之习题讲解.ppt》由会员分享，可在线阅读，更多相关《离散数学课件总复习之习题讲解.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构重点题型与课后题讲解重点题型与课后题讲解20122012年秋季年秋季年秋季年秋季各内容重点题型讲解各内容重点题型讲解作业中易错题讲解作业中易错题讲解课后练习讲解课后练习讲解各内容重点题型讲解各内容重点题型讲解内内内内 容容容容比比比比 例例例例示例例题示例例题示例例题示例例题线性表线性表线性表线性表 15%15%P862.22P862.22栈和队列栈和队列栈和队列栈和队列15%15%P1333.22P1333.22数组、矩阵和串数组、矩阵和串数组、矩阵和串数组、矩阵和串1010%P1854.13P1854.13二叉树、堆、二叉树、堆、二叉树、堆、二叉树、堆、HuffmanHuf

2、fman 20%20%P2485.18P2485.18、5.205.20散列散列散列散列 10%10%P2956.9P2956.9图图图图110%0%P3938.10P3938.10、P3958.24P3958.24搜索结构搜索结构搜索结构搜索结构 20%20%P3437.15P3437.15排序排序排序排序P4409.2P4409.2P862.22设设在在一一个个带带附附加加头头结结点点的的单单链链表表中中所所有有元元素素结结点点的的数数据据值值按按递递增增顺顺序序排排列，试编写一个函数，列，试编写一个函数，删除表中所有大于删除表中所有大于min，小于，小于max的元素的元素（若存在）。（若

3、存在）。an-1a1firstpq温习：温习：（1）带附加结点的单链表的结构）带附加结点的单链表的结构（2）单链表的删除）单链表的删除 q=p-link;p-link=q-link;deleteq;参考解析：参考解析：templatevoidrangeDelete(List&L,Tmin,Tmax)LinkNode*ptr=L.First(),*p=ptr-link;while(p!=NULL&p-datalink;while(p!=NULL&p-datalink=p-link;deletep;p=ptr-link;P1333.22假假设设以以数数组组Qm存存放放循循环环队队列列中中的的元元素

4、素，同同时时以以rear和和length分分别别指指示示循循环环队队列列中中的的队队尾尾位位置置和和队队列列中中所所含含元元素素的的个个数数。试试给给出出该该循循环环队队列列的的对对空空条条件件和和队队满满条条件件，并并写写出出相相应应的的插插入入（EnQueue）和和删删除除（DlQueue）元元素素的操作。的操作。温习：温习：（1）循环队列结构）循环队列结构01234567frontABCrear（3）循环队列插入）循环队列插入（4）循环队列删除）循环队列删除存入存放循环队列元素的数组存入存放循环队列元素的数组elementsrear=x;尾指针加一尾指针加一rear=(rear+1)%m

5、axSize;取队头元素取队头元素x=elementsfront;队头指针加一队头指针加一front=(front+1)%maxSize;（2）循环队列对空条件与队满条件）循环队列对空条件与队满条件队空条件：队空条件：front=rear;队满条件：队满条件：(rear+1)%maxSize=front；参考解析：参考解析：#include#include“Queue.h”templateclassSeqQueue:publicQueue/循环队列的类定义循环队列的类定义protected:intrear,length;/队尾指针与队列长度队尾指针与队列长度T*elements;/队列存放数组

6、队列存放数组intmaxSize;/队列最大容量队列最大容量public:SeqQueue(intsize=100);/构造函数构造函数SeqQueue()deleteelements;/析构函数析构函数boolEnQueue(Tx);/新元素进队列新元素进队列boolDeQueue(T&x);/退出队头元素退出队头元素voidmakeEmpty()length=0;/置空队列置空队列boolIsEmpty()constreturnlength=0;/判队列是否为空判队列是否为空boolIsFull()constreturnlength=maxSize;/判队列是否满判队列是否满;templa

7、teSeqQueue:SeqQueue(intsize):rear(0),length(0),maxSize(size)/构造函数：建立一个最大具有构造函数：建立一个最大具有maxSize个元素的空队列个元素的空队列elements=newTsize;assert(elements!=NULL);templateboolSeqQueue:EnQueue(Tx)/若队列不满若队列不满,则将则将x插入到该队列队尾插入到该队列队尾,否则返回否则返回falseif(IsFull()=true)returnfalse;/判队列是否已满，满则返回判队列是否已满，满则返回falseelementsrear=

8、x;/先存入先存入rear=(rear+1)%maxSize;/尾指针加一尾指针加一length+;/队列长度加队列长度加1returntrue;templateboolSeqQueue:DeQueue(T&x)/若队列不空则函数退队头元素并返回其值若队列不空则函数退队头元素并返回其值if(IsEmpty()=true)returnfalse;/判队列是否为空，空则返回判队列是否为空，空则返回falsex=elements(rear-length+maxSize)%maxSize;/取原队头元素值取原队头元素值length-;/队列长度减队列长度减1returntrue;P1854.13所所谓

9、谓回回文文，是是指指从从前前向向后后顺顺读读和和从从后后向向前前倒倒读读都都一一样样的的不不含含空空白白字字符符的的串串。例例如如did，madamimadam，pop即即是是回回文文。试试编编写写一一个个算算法法，以以判判断断一一个串是否是回文。个串是否是回文。解法一（基于字符串的顺序存储）解法一（基于字符串的顺序存储）算法思想：从数组两头向中间并进，检查对应字符是否相等，直到中间会合。算法思想：从数组两头向中间并进，检查对应字符是否相等，直到中间会合。#includeAstring.hboolpalindrome(AString&S)inti=0,j=S.Length()-1;while(

10、ij)if(Si!=Sj)returnfalse;elsei+,j+;returntrue;解法二（基于字符串的单链表存储结构）解法二（基于字符串的单链表存储结构）算算法法思思想想：利利用用栈栈。先先把把字字符符串串所所有有元元素素进进栈栈，再再逐逐个个退退栈栈与与从从头头遍遍历历链链表表同时进行，都相等说明是回文。同时进行，都相等说明是回文。#includeLinkedStack.hboolpalindrome(AString&S)LinkedStackSLS;charch;linkNode*p=S.First()-link;while(p!=NULL)/把字符串所有元素进栈把字符串所有元素

11、进栈SLS.Push(p-data);p=p-link;p=S.First()-link;while(!SLS.isEmpty()/退掉位于栈顶的元素，同时遍历链表与从栈退出来的元素进行比较退掉位于栈顶的元素，同时遍历链表与从栈退出来的元素进行比较SLS.Pop(ch);if(ch!=p-data)returnfalse;elsep=p-link;returntrue;P2485.18已已知知一一棵棵二二叉叉树树的的前前序序遍遍历历的的结结果果是是ABECDFGHIJ，中中序序遍遍历历的的结结果果是是EBCDAFHIGJ，试画出这颗二叉树。，试画出这颗二叉树。温习：温习：前序遍历：根左右前序遍

12、历：根左右中序遍历：左根右中序遍历：左根右后序遍历：左右根后序遍历：左右根前前序序参考解析：参考解析：C CB BE EA AD DF FGGHHI IJ J中中序序D DB BC CE EA AF FHHI IGGJ JD DB BC CE EF F HHI IGGJ JD DC CHHI IGGJ JHHI IABFCeEGD HJIP2485.20假假定定用用于于通通信信的的电电文文仅仅由由8个个字字母母c1,c2,c3,c4,c5,c6,c7,c8组组成成，各各字字母母在在电电文文中中出出现现的的频频率率分分别别为为5,25,3,6,10,11,36,4。试试为为这这8个个字字母母设设

13、计计不不等等长长Huffman编码，并给出该电文的总码数。编码，并给出该电文的总码数。温习：温习：Huffman树：树：WPL最小最小的二叉树，也是的二叉树，也是权值大的外结点离根结点最近权值大的外结点离根结点最近的扩充二叉树。的扩充二叉树。参考解析：参考解析：思路：每个结点看做一棵树，找权值最小的两棵树合为一棵树。思路：每个结点看做一棵树，找权值最小的两棵树合为一棵树。6 625253 35 51010111136364 4c1c2c3c4c5c6c7c86 625253 35 51010111136364 4c1c2c3c4c5c6c7c87 76 625253 35 5101011113

14、6364 4c1c2c3c4c5c6c7c87 711116 625253 35 51010111136364 4c1c2c3c4c5c6c7c87 7111117176 625253 35 51010111136364 4c1c2c3c4c5c6c7c87 71111171722226 625253 35 51010111136364 4c1c2c3c4c5c6c7c87 711111717222239396 625253 35 51010111136364 4c1c2c3c4c5c6c7c87 7111117172222393961616 625253 35 51010111136364

15、4c1c2c3c4c5c6c7c87 71111171722223939616110010000000001111111c1c2c3c4c5c6c7c81000001110 1001110101011111电文总码数：电文总码数：45225434631031123644257P2956.9设设散散列列表表为为HT13，散散列列函函数数H(key)=key%13，用用闭闭散散列列法法解解决决冲冲突突，对下列关键码序列对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。造表。（1）采采用用线线性性探探查查法法寻寻找找下下一一个个空空位位，画画出出相相应应的的散散列列表表

16、，并并计计算算等等概概率率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。（2）采采用用双双散散列列法法寻寻找找下下一一个个空空位位，再再散散列列函函数数RH(key)=(7*key)%10+1，寻寻找找下下一一个个空空位位的的公公式式为为Hi（Hi-1RH(key)）%13，H1=H(key)。画画出出相相应的散列表，并计算等概率下搜索成功的平均搜索长度。应的散列表，并计算等概率下搜索成功的平均搜索长度。温习：温习：HHi i（k k）=（HH0 0（k k）+d+di i）modmmodm（i=1,2,.ki=1,2,.k（km-1k

17、m-1）其中，每次再探测时的地址增量其中，每次再探测时的地址增量其中，每次再探测时的地址增量其中，每次再探测时的地址增量d d d di i i i可以有不同的取值：可以有不同的取值：可以有不同的取值：可以有不同的取值：（1 1 1 1）d d d di i i i=1=1=1=1，2 2 2 2，3 3 3 3，.；线性探测法线性探测法线性探测法线性探测法（2 2 2 2）d d d di i i i=1=1=1=12，-1-1-1-12，2 2 2 22，-2-2-2-22.；二次探测法二次探测法二次探测法二次探测法（3 3 3 3）d d d di i i i=伪随机序列；伪随机序列；伪

18、随机序列；伪随机序列；伪随机再散列伪随机再散列伪随机再散列伪随机再散列 如：双散列法如：双散列法如：双散列法如：双散列法 H Hi i（H H0 0ReHash(key)ReHash(key)）%m%m参考解析：参考解析：（1）线性探查法（）线性探查法（设设HH11=H（key）若发生冲突，则调用 Hi（k）=（H1（k）+di）%13（di=1,2,）由散列函数由散列函数H(key)=key%13可得可得:HH11(12)=12%13=12HH11(23)=23%13=10HH11(45)=45%13=6HH11(57)=57%13=5HH11(20)=20%13=7HH11(03)=3%1

19、3=3HH11(78)=78%13=0HH11(31)=31%13=5（发生冲突）（发生冲突）HH22(31)=（5+1）%13=6（发生冲突）（发生冲突）HH33(31)=（6+1）%13=7（发生冲突）（发生冲突）HH44(31)=（7+1）%13=8（成功）（成功）H1 1(15)=15%13=2H1 1(36)=36%13=10（发生冲突）（发生冲突）HH22(36)=（10+1）%13=11（成功）（成功）0 04 48 8121245451212787836362020 3131030315151 12 23 35 56 67 79 9 1010 111123235757ASLAS

20、L成功成功成功成功=（1+1+1+1+1+1+1+4+1+2）/10=14/10ASLASL不成功不成功不成功不成功=（2+1+3+2+1+5+4+3+2+1+5+4+3）/13=36/13（2）双散列法（）双散列法（设设HH11=H（key）若发生冲突，则调用 Hi（k）=（Hi-1（k）+RH(key)）%13，RH(key)=(7*key)%10+1由散列函数由散列函数H(key)=key%13可得可得:HH11(12)=12%13=12HH11(23)=23%13=10HH11(45)=45%13=6HH11(57)=57%13=5HH11(20)=20%13=7HH11(03)=3%

21、13=3HH11(78)=78%13=0HH11(31)=31%13=5（发生冲突）（发生冲突）RH(31)=(731)%10+1=8HH22(31)=（5+8）%13=0（发生冲突）（发生冲突）HH33(31)=（0+8）%13=8（成功）（成功）H1 1(15)=15%13=2H1 1(36)=36%13=10（发生冲突）（发生冲突）RH(36)=(736)%10+1=3HH22(36)=（10+3）%13=0（发生冲突）（发生冲突）HH33(36)=（0+3）%13=3（发生冲突）（发生冲突）HH44(36)=（3+3）%13=6（发生冲突）（发生冲突）HH44(36)=（6+3）%13

22、=9（成功）（成功）0 04 48 81212454512127878202003031 12 23 35 56 67 79 9 1010 111123235757ASLASL成功成功成功成功=（1+1+1+1+1+1+1+3+1+5）/10=16/10313115153636P3028.10对于如下图所示的有向图，试写出：对于如下图所示的有向图，试写出：（1）从顶点）从顶点出发进行深度优先搜索所得到的深度优先生成树（出发进行深度优先搜索所得到的深度优先生成树（DFS树）；树）；（2）从顶点）从顶点出发进行广度优先搜索所得到的广度优先生成树。出发进行广度优先搜索所得到的广度优先生成树。温习：温

23、习：深度优先搜索：不断探查和回溯深度优先搜索：不断探查和回溯广度优先搜索：逐层遍历广度优先搜索：逐层遍历4 42 23 31 15 5参考解析：参考解析：4 42 23 31 15 54 42 23 31 15 54 42 23 31 15 5深度优先搜索深度优先搜索广度优先搜索广度优先搜索P3178.24以以下下图图为为例例，按按Dijkstra算算法法计计算算得得到到的的从从顶顶点点A到到其其他他各各个个顶顶点点的的最最短路径和最短路径长度。短路径和最短路径长度。温习：温习：DijkstraDijkstra算算法法是是最最短短路路径径算算法法之之一一。具具体体做做法法：用用一一个个集集合合

24、S S存存放放已已经经求求得得最最短短路路径径的的终终点点。初初始始状状态态时时，集集合合S S只只有有一一个个源源点点v v0 0，以以后后每每次次求求得得一一条条最最短短路路径径，就就将将其其终终点点v vk k 加加入入集集合合S S，且且可可证证明明：下下一一条条最最短短路路径径必必然然是是从从v v0 0 出出发发，中中间间只只经经过过S S中中的的顶顶点点便便可可到到达达的的那那些些顶顶点点v vx x (v(vx x V-S V-S)的的路路径径中中的的一一条条，直直至至全全部部顶顶点点都都加加入入到到集集合合S S中。中。D DB BC CA AE E218552210D DB

25、 BC CA AE E218552210参考解析：参考解析：D DB BC CA AE E218552210D DB BC CA AE E218552210D DB BC CA AE E218552210源点源点终点终点最短路径最短路径最短路径长度最短路径长度AB10C 18181717D 15E 17D DB BC CA AE E218552210P3437.15将将关关键键码码DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依依次次插插入入一一棵棵初初始始为为空空的的AVL树树中中，画画出出每每插插入入一一个个关关键键码码后后的的AVL树树，并

26、并标明平衡旋转的类型。标明平衡旋转的类型。温习：温习：（1）AVL树树 如果T是一棵非空的二叉搜索树，TL和TR分别是其左子树和右子树，那么当T满足以下条件时，T是一棵AVL树：1）TL和TR 是AVL树；2）|hR-hL|1，hL和hR分别是左子树和右子树的高度，即平衡因子只能取0,1和-1。二叉搜索树：1）每个结点都有一个作为搜索依据的关键码(key)，所有结点的关键码互不相同，都是唯一的；2）左子树（如果非空）上所有结点的关键码都小于根结点的关键码。3）右子树（如果非空）上所有结点的关键码都大于根结点的关键码。（2）平衡化旋转）平衡化旋转从从插插入入位位置置沿沿通通向向根根的的路路径径回

27、回溯溯，检检查查各各节节点点的的平平衡衡因因子子，从从发发生生不不平平衡衡的的节节点起，沿刚才回溯的路径取直接下两层的节点，做平衡化旋转。点起，沿刚才回溯的路径取直接下两层的节点，做平衡化旋转。ARRCLLCBCABABBCAABCCABACBACCBAACBCABLRRLNOVDECDECFEBDECFEB+2FEBNOVDECFEBNOVDECOCTRRFEBNOVDECOCTJULFEBNOVDECOCTJULSEP+2NOVOCTFEBSEPJULDECRR参考解析：参考解析：FEBJULAUGJUNDECAPRNOVOCTMAYSEPMARJANP4409.2设设待待排排序序的的排排

28、序序码码序序列列为为12,2,16,30,28,10,16*，20,6,18，试试分分别别写写出出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。（1）直接插入排序）直接插入排序（2）希尔排序（增量为）希尔排序（增量为5,2,1）（3）起泡排序）起泡排序（4）快速排序）快速排序（5）简单选择排序）简单选择排序（6）锦标赛排序）锦标赛排序（7）堆排序）堆排序（8）二路归并排序）二路归并排序（9）基数排序）基数排序温习：温习：排序：排序：插入排序：直接插入排序、折半插入排序、希尔排序插入排序：直接插入排序、折半插入排序、希

29、尔排序交换排序：起泡排序、快速排序交换排序：起泡排序、快速排序选择排序：直接选择排序、堆排序选择排序：直接选择排序、堆排序归并排序归并排序参考解析参考解析（以希尔排序为例）：（以希尔排序为例）：30302 216161212282810101616*20206 61818d=5121210102 21616*1616202030306 6282818186 62 216161010181812121616*202030302828结果结果排序码比较次数：排序码比较次数：1+1+1+1+1=56 62 216161010181812121616*202030302828d=21616101018

30、181616*30306 62 21212202028286 62 2161610101616*12121818202030302828结果结果排序码比较次数：排序码比较次数：（1+1+2+1）+（1+1+1+1）=96 62 2161610101616*12121818202030302828d=116166 610102 21616*12121818202028283030结果结果排序码比较次数：排序码比较次数：1+1+3+1+3+1+1+1+2=14易错题讲解易错题讲解/C+基础问题基础问题P381.10（3）P391.12（1）/栈的利用栈的利用P1323.16（2）/矩阵的压缩存储矩

31、阵的压缩存储P1834.4P1323.16（2）已知已知Ackerman函数定义如下：函数定义如下：n+1当当m=0时时akm(m,n)=akm(m-1,1)当当m0，n=0时时akm(m-1,akm(m,n-1)当当m0，n0时时（2）利用栈，写出它的非递归求解算法。）利用栈，写出它的非递归求解算法。解析（以解析（以m=2,n=1为例分析）：为例分析）：akm(2,1)=akm(1,akm(2,0)akm(2,0)=akm(1,1)akm(1,1)=akm(0,akm(1,0)akm(1,0)=akm(0,1)akm(0,1)=222=333akm(1,3)=akm(0,akm(1,2)ak

32、m(1,2)=akm(0,akm(1,1)3=44=5int Ackerman(int m,int n)int i,j,k,top=-1;int Sm10,Sn10;Sm+top=m;Sntop=n;/Sm和Sn是栈，top是栈顶指针 while(1)i=Smtop;j=Sntop;top-;/出栈 if(i=0)/m=0情形，结果为n+1 k=j+1;if(top!=-1)Sntop=k;else return k;else if(j=0)/m0，n=0情形 Sm+top=i-1;Sntop=1;else Sm+top=i-1;Smtop=i;Sntop=j-1;P1834.4设设有有三三对

33、对角角矩矩阵阵Ann，将将其其三三条条对对角角线线上上的的元元素素逐逐行行存存储储到到数数组组B0：3n-3中，使得中，使得Bk=aij，求：，求：（1）用）用i,j表示表示k的下标变换公式；的下标变换公式；（2）用）用k表示表示i,j的下标变换公式。的下标变换公式。解析：解析：若若0in-1,则：则：k=(3i-1)+(j-i+1)=2i+ji=（k+1）/3取下整，取下整，j=k-2i若若1in,则：则：k=(3(i-1)-1)+(j-i+1)=2i+j-3i=（k+1）/3取下整取下整+1，j=k-2i+3课后练习讲解课后练习讲解1、已已知知有有序序表表为为（12，18，24，35，47

34、，50，62，83，90，115，134）,当当用用折折半半搜搜索索90时时，需需进进行行2次次搜搜索索可可确确定定搜搜索成功；搜索索成功；搜索40时需进行时需进行_4次搜索才能确定不成功。次搜索才能确定不成功。2、在、在双向链表双向链表存储结构中，存储结构中，删除删除p所指的结点时须修改指针所指的结点时须修改指针（A）。）。Ap-llink-rlink=p-rlink;p-rlink-llink=p-llink;Bp-llink=p-llink-llink;p-llink-rlink=p;Cp-rlink-llink=p;p-rlink=p-rlink-rlinkDp-rlink=p-lli

35、nk-llink;p-llink=p-rlink-rlink;3 3、用、用、用、用I I表示入栈操作，表示入栈操作，表示入栈操作，表示入栈操作，OO表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为表示出栈操作，若元素入栈顺序为12341234，为了得到，为了得到，为了得到，为了得到13421342出栈顺序，相应的出栈顺序，相应的出栈顺序，相应的出栈顺序，相应的I I和和和和OO操作串为（操作串为（操作串为（操作串为（C C）。）。）。）。AAIIOOIIOOBIIOOIIOOBIOIOIIOOIOIOIIOOCCIOIIOIOODIOIIOIOODI

36、OIIOOIOIOIIOOIO4 4、数组、数组、数组、数组A0.5,0.6A0.5,0.6的每个元素占的每个元素占的每个元素占的每个元素占5 5个字节，将其个字节，将其个字节，将其个字节，将其按列优先按列优先按列优先按列优先次次次次序存储在起始地址为序存储在起始地址为序存储在起始地址为序存储在起始地址为10001000的内存单元中，则元素的内存单元中，则元素的内存单元中，则元素的内存单元中，则元素A5A5，55的地的地的地的地址是（址是（址是（址是（A A）。）。）。）。AA1175B1175B1180C1180C1205D1205D1210121055、已知一棵完全二叉树中共有、已知一棵完

37、全二叉树中共有、已知一棵完全二叉树中共有、已知一棵完全二叉树中共有768768结点，则该树中共有结点，则该树中共有结点，则该树中共有结点，则该树中共有_ _384_384_个叶子结点。个叶子结点。个叶子结点。个叶子结点。完全二叉树中度为完全二叉树中度为完全二叉树中度为完全二叉树中度为1 1的节点数只有两种可能：要么为的节点数只有两种可能：要么为的节点数只有两种可能：要么为的节点数只有两种可能：要么为0 0个个个个（奇数个结点），要么为（奇数个结点），要么为（奇数个结点），要么为（奇数个结点），要么为1 1个（偶数个结点）。个（偶数个结点）。个（偶数个结点）。个（偶数个结点）。n0=n2+1n0

38、=n2+16 6、已知某二叉树的、已知某二叉树的、已知某二叉树的、已知某二叉树的中序遍历序列是中序遍历序列是中序遍历序列是中序遍历序列是dgbaechfdgbaechf，后序遍历序列后序遍历序列后序遍历序列后序遍历序列是是是是gdbehfcagdbehfca，则其前序遍历序列是（，则其前序遍历序列是（，则其前序遍历序列是（，则其前序遍历序列是（A A）。）。）。）。AAabdgcefhBabdgcefhBagdbecfhagdbecfhCCabdgechfDabdgechfDadbgcefhadbgcefh 6 6、有数据、有数据、有数据、有数据5353，3030，3737，1212，4545

39、，2424，9696，从空二叉树开，从空二叉树开，从空二叉树开，从空二叉树开始逐个插入数据来形成二叉搜索树，若希望高度最小，则应始逐个插入数据来形成二叉搜索树，若希望高度最小，则应始逐个插入数据来形成二叉搜索树，若希望高度最小，则应始逐个插入数据来形成二叉搜索树，若希望高度最小，则应选择下面哪个序列输入选择下面哪个序列输入选择下面哪个序列输入选择下面哪个序列输入 B B 。A A、4545，2424，5353，1212，3737，9696，3030BB、3737，2424，1212，3030，5353，4545，9696CC、1212，2424，3030，3737，4545，5353，9696

40、DD、3030，2424，1212，3737，4545，9696，53537 7、已知一长度为、已知一长度为、已知一长度为、已知一长度为1212的表（的表（的表（的表（JanJan，FebFeb，MarMar，AprApr，MayMay，JuneJune，JulyJuly，AugAug，SeptSept，OctOct，NovNov，DecDec）。）。）。）。（1 1）依次取表中各元素构造一棵二叉搜索树（按照在英文字典）依次取表中各元素构造一棵二叉搜索树（按照在英文字典）依次取表中各元素构造一棵二叉搜索树（按照在英文字典）依次取表中各元素构造一棵二叉搜索树（按照在英文字典中的先后顺序比较元素值

41、的大小）；并求其在等概率情况下搜索中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索中的先后顺序比较元素值的大小）；并求其在等概率情况下搜索成功时的平均搜索长度。成功时的平均搜索长度。成功时的平均搜索长度。成功时的平均搜索长度。（2 2）若对表中元素进行排序构成有序表，求在等概率情况下对）若对表中元素进行排序构成有序表，求在等概率情况下对）若对表中元素进行排序构成有序表，求在等概率情况下对）若对表中元素进行排序构成有序表，求在等概率情况下对此有序表进行折半搜索成功的平均搜索长度。此有序表进行折半搜索成功的平均搜索长度。此有序表进行折

42、半搜索成功的平均搜索长度。此有序表进行折半搜索成功的平均搜索长度。（3 3）按表中元素顺序构造一棵）按表中元素顺序构造一棵）按表中元素顺序构造一棵）按表中元素顺序构造一棵AVLAVL树，并求其在等概率情况下树，并求其在等概率情况下树，并求其在等概率情况下树，并求其在等概率情况下搜索成功的平均搜索长度。搜索成功的平均搜索长度。搜索成功的平均搜索长度。搜索成功的平均搜索长度。JanJanFebFebJulyJulyNovNovSeptSeptMarMarJuneJuneMayMayOctOctAprAprAugAugDecDec二叉搜索树二叉搜索树二叉搜索树二叉搜索树解答：解答：解答：解答：42/

43、1242/12JanJanFebFebJulyJulyNovNovSeptSeptMarMarJuneJuneMayMayOctOctAprAprAugAugDecDec3 34 42 23 34 41 13 34 42 24 43 34 4折半搜索折半搜索折半搜索折半搜索解答：解答：解答：解答：37/1237/12MarMarJanJanAprAprJulyJulyNovNovOctOctJuneJuneMayMaySeptSeptAugAugFebFebDecDecAVLAVL树树树树解答：解答：解答：解答：38/1238/12 8 8、在含、在含、在含、在含n n个顶点和个顶点和个顶点和个顶点和e e条边的无向图的邻接矩阵中，零元素的个条边的无向图的邻接矩阵中，零元素的个条边的无向图的邻接矩阵中，零元素的个条边的无向图的邻接矩阵中，零元素的个数为数为数为数为D D。A AeBeB2eC2eCn n2 2-eD-eDn n2 2-2e-2e预祝全体同学考试成功！预祝全体同学考试成功！