数据结构考点解析PPT学习教案

1、会计学1数据结构考点解析数据结构考点解析2第1页/共183页3及其不同的实现。第2页/共183页4第3页/共183页55) 线性表的应用：掌握使用线性表基本操作实现应用算法第4页/共183页6线性表和非线性表是从逻辑上划分的。而循环链表是存储结构，是线性表的一种特殊的表示，是线性链表的一种扩展。它在形态上有线性的特征，在行为上有线性表的循序访问的特点。第5页/共183页7定义为Union类型即可。因为线性表的定义只规定了元素间的关系及每个表元素是原子类型，并未规定每个表元素的类型必须相同。Union是一种等价类型，它允许不同类型数据共享同一存储空间，可保证每个表元素所占空间相同。第6页/共18

2、3页8的实现代码。具体的线性表实例一定与某一存储表示相联系，因此，要使用相应的基于该存储结构实现的操作。第7页/共183页9问题5. 想要以O(1)的时间代价存取第 i 个表元素，线性表应采用顺序表还是单链表？解析：“顺序表”，因为单链表只能顺序地逐个访问，顺序表可以直接访问第 i 个元素。第8页/共183页10但增删要大量移动存储块；反之，选择链表，因它在增删元素时不需移动存储，修改指针即可，但只能顺序访问，存取速度慢。从空间角度来看，顺序表存储密度（有效存储/总存储）高，空间利用率好；链表存储密度较低，空间利用率差一些。第9页/共183页11pqr第10页/共183页12解析：“双向链表”

3、。只要事先定位于该表结点，通过该结点的前驱指针和后继指针，直接能够找到该元素的直接前驱或直接后继。第11页/共183页13例例1： 在一个单链表中，已知在一个单链表中，已知q结点是结点是p结点的前趋结点，结点的前趋结点，若在若在q和和p之间插入之间插入s结点，则须执行结点，则须执行 ( )As-next=p-next; p-next=s Bq-next=s; s-next=pCp-next=s-next; s-next=p Dp-next=s; s-next=q第12页/共183页14例例2： 假设有一个带表头结点的链表，表头指针为假设有一个带表头结点的链表，表头指针为head，每个结点含三个

4、域：每个结点含三个域：data, next和和prior。其中。其中data为整为整型数域，型数域，next和和prior均为指针域。现在所有结点已经由均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用域连接起来，试编一个算法，利用prior域（此域域（此域初值为初值为NULL）把所有结点按照其值从小到大的顺序链）把所有结点按照其值从小到大的顺序链接起来。接起来。定义类型定义类型LinkList如下：如下：typedef struct node int data; struct node *next,*prior;LinkList;第13页/共183页15例例3： 设顺序表设

5、顺序表L是一个递减有序表，试写一算法，将是一个递减有序表，试写一算法，将x插插入其后仍保持入其后仍保持L的有序性。的有序性。/-线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构-#define maxlen 100 /线性表存储空间最大容量线性表存储空间最大容量typedef structElemType *elem; /存储空间基址存储空间基址 int len; /当前长度当前长度SqList;第14页/共183页16例例4：完成以下算法，对单链表实现就地逆置。完成以下算法，对单链表实现就地逆置。void LinkList_reverse(Linklist &L)/链表的就地逆置链表

6、的就地逆置;为简化算法为简化算法,假设表长大于假设表长大于2 Linklist p,q,s; p=L-next; q=p-next; s=q-next; p-next=NULL;第15页/共183页17例例5：循环链表存储结构示意图如下，请填空：循环链表存储结构示意图如下，请填空：typedef struct LNode / 结点类型结点类型ElemType data; / 数据单元数据单元LNode *next; / 指针单元指针单元*Link,*Position; /定义两个结点指针别名，用于操作函数定义两个结点指针别名，用于操作函数typedef LNode *LinkList; / 简

7、单链表类型简单链表类型元素元素1元素元素n头结点头结点第16页/共183页18循环链表初始化函数循环链表初始化函数InitList的参考代码，一个空的的参考代码，一个空的循环链表至少要包含一个头结点。循环链表至少要包含一个头结点。void InitList(LinkList &L) / 操作结果：构造一个空的循环链表操作结果：构造一个空的循环链表L。L = (1) ; / 产生头结点，使产生头结点，使L指向此头结点指向此头结点if (!L) / 存储分配失败存储分配失败 exit(OVERFLOW); （2） ; / 指针域指向头结点指针域指向头结点第17页/共183页19循环链表销毁函数循环

8、链表销毁函数DestroyList的参考代码的参考代码（循环链表（循环链表L尾结点的尾结点的next指针指向指针指向L）void DestroyList(LinkList &L)/ 操作结果：销毁循环链表操作结果：销毁循环链表L。 LinkList q, p = L-next; / p指向第一个结点指向第一个结点while ( (3) ) / 没到表尾没到表尾 q = p-next; free(p); p = q; （4） ; L = NULL;第18页/共183页207) 特殊矩阵8) 稀疏矩阵第19页/共183页21出栈顺序吗？解析：“否”，因序列的进出栈顺序为 IA IB IC ID O

9、D, 当D 出栈后，栈顶为C，不能让B先出来。所以D, B, C, E, A 不是可能的出栈顺序。第20页/共183页22访问、插入和删除，队列要求只能在表的一端（队尾）插入，在另一端（队头）访问和删除，不能在表的中间做上述运算。这决定了在栈和队列上只能顺序访问，不能直接存取，无论采用何种存储表示。这表现了它们优秀的“结构化”特性。第21页/共183页23决条件是什么？解析：进栈的先决条件是栈未满，栈满再进栈就会产生溢出；出栈的先决条件是栈不空，栈空再退栈可报告操作失败。第22页/共183页24.链头还是链尾？解析：“链头”，链式栈一般采用单链表，栈顶指针即为链头指针。进栈出栈均在链头进行，每

10、次都要修改栈顶指针。链空即栈空，top = NULL。第23页/共183页25成功则进栈操作失败。StackNode *s = new StackNode; if ( s = NULL ) cerr “结点存储分配失败！” endl; exit (0); 第24页/共183页26x = Q.elemQ.front; Q.front = (Q.front+1) % m;第25页/共183页27- x = Q.elem(Q.front+Q.length) % m; 问题13. 链式队列的队头和队尾在链表的什么地方？第26页/共183页28解析：采用多个链式队列，并设置队头指针数组frn和队尾指针数

11、组ren，分别指示各队列的队头和链尾，其中 n 是队列个数。第27页/共183页29解析：用指针动态定义存放队列元素的数组，当队列已满时，可创建一个更大的同类型的新数组，把队列元素全部复制到新数组，然后修改队列指针，释放老数组。注意区分 Q.rear Q.front 和Q.front Q.rear 的情形。第28页/共183页30构来存放递归过程每层的局部变量、返回地址和实参副本？解析：“栈”，因递归调用时需为每层分配，在退出时逐层释放，这正是后进先出的机制，可用栈来组织。第29页/共183页31进时用栈记下回退路径以便回溯之用，比在路径上各个结点中增加访问标识更方便。例如图的深度优先搜索，采

12、用在每个边结点中增加标志域的非递归算法比用栈的递归算法更复杂。第30页/共183页32解析：判栈空：top = -1;设表中第 k 个元素进栈：Sk = top; top = k;设出栈元素是第 k 个元素：k = top; top = Stop;第31页/共183页33队列，这些队列是按数组方式组织的还是按链表方式组织的？解析： “按链表方式组织的”，各个队列的增长速度不一，按链表组织可以自由增长。第32页/共183页34解析： “链表结点指针”，存放各有序子链表的头指针。每次从队列中退出两个子链表的头指针，归并后把结果子链表的头指针进队列。如此重复，直到队列中只剩下一个链表指针为止。第33

13、页/共183页35解析： “是”，按照下标确定每个元素存储地址的计算时间都相同，按地址存取任一元素的时间也相同。第34页/共183页36义int a5 = 1, 3, 5, 7, 9; int * data = a;有int *elem = new int5; while (data != 0) *elem = *data; elem+; data+; for (int k = 0; k n; k+) cout link。第36页/共183页38解析：两个对称矩阵相加的结果矩阵是对称矩阵。相乘的结果矩阵一般不对称，除非二个对称矩阵是相同的。第37页/共183页39221000232100123

14、210012321001232000122110000111000011100001110000111000011110000111000011100001110000111000011第38页/共183页40定不是稀疏矩阵。问题38. 用三元组表存储稀疏矩阵的非零元素，是否失去了直接存取的特性？如何改进？第39页/共183页410900000000000420010070003A列号列号值值13573-1122449行号行号13446第40页/共183页42 设有一个栈，元素的进栈次序为设有一个栈，元素的进栈次序为A, B, C, D, E,下列下列是不可能的出栈序列是不可能的出栈序列_。A

15、A, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 第41页/共183页43 设栈设栈S和队列和队列Q的初始状态均为空，元素的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈依次进入栈S。若每个元素出栈后立即。若每个元素出栈后立即进入队列进入队列Q，且，且7个元素出队的顺序是个元素出队的顺序是b,d,c,f,e,a,g,则栈则栈S的容量至少是的容量至少是 。A.1 B.2 C.3 D.4第42页/共183页44稀疏矩阵一般的压缩存储方法有两种，即（稀疏矩阵一般的压缩存储方法有两种，即（ ）。）。A.二维数组和三维数组二维数

16、组和三维数组 B.三元组和散列三元组和散列C.三元组和十字链表三元组和十字链表 D.散列和十字链表散列和十字链表第43页/共183页450000010000030200 一个稀疏矩阵如下图所示，则对应的三元组线性一个稀疏矩阵如下图所示，则对应的三元组线性表为表为_。 第44页/共183页46由两个栈共享一个向量空间的好处是：（由两个栈共享一个向量空间的好处是：（ ） A减少存取时间，降低下溢发生的机率减少存取时间，降低下溢发生的机率 B节省存储空间，降低上溢发生的机率节省存储空间，降低上溢发生的机率 C减少存取时间，降低上溢发生的机率减少存取时间，降低上溢发生的机率 D节省存储空间，降低下溢发

17、生的机率节省存储空间，降低下溢发生的机率第45页/共183页47第46页/共183页48的树。问题3. 二叉树的叶结点无子女，它是否无子树？解析：“否”，二叉树的定义是递归的，递归到空树为止，所以结点无子女，应称它子树为空。第47页/共183页49少？解析：由n0 = n2+1的性质，度为 2 的结点有465-1 = 464个，度为1 的结点有1024-465-464 = 95个。问题6. 计算深度的公式log2(n+1) 是针对何种二叉树的？解析：针对完全二叉树。但对理想平衡树也可用。第48页/共183页50问题9. n0 = n2+1公式有何用途？解析：对于完全二叉树最有用。例如组织对抗赛

18、可用胜者树，已知选手有n个人，取n0 = n,直接可求得比赛场次n2 = n0-1，是否有人轮空。第49页/共183页510 开始编号是合理的，这时某结点i 的双亲是 (i-1)/2，左子女是2i+1，右子女是2i+2。完全二叉树结点从 1 开始编号是传承了Pascal的做法。第50页/共183页52问题13. 使用二叉链表存储有n个结点的二叉树，空的指针域有多少？解析：n 个结点的二叉树有2n个指针域，其中 n-1 个指针域被使用，有 n+1 个空指针域。第51页/共183页53. 的是什么二叉树?解析：要求VLR = LVR，应是左子树均为空的单支树，或空树。abdcef123第52页/共

19、183页54同的是何二叉树?解析：只有根结点的二叉树或空树。123123第53页/共183页55即，当右子树都空时, 或左子树都空时, 或空树时满足要求。LRVVLR VLR123LVRLVVL 123123LVVL RVVR 第54页/共183页56解析：“是”。问题23. 一棵有 n 个结点的二叉树的前序序列固定，可能的不同二叉树有多少种？解析：用catalan函数求：abdceC211nnn第55页/共183页57构？解析：“队列”，使用队列，在逐层访问过程中一旦当前层次的结点出队进行处理，就需把它下一层的结点进队列。当当前层的结点全部退出队列并处理完后下一层结点已经在队头了。第56页/

20、共183页58abdcefg第57页/共183页59线索的结点为止，该结点即所求。第58页/共183页60ThreadNode * inLast(ThreadNode *p) ThreadNode *q = p; while (q & !q-rtag) q = q-right;第59页/共183页61ThreadNode *q = p-right; if (q & !p-rtag) q = inFirst(q); return q; abdcefg第60页/共183页62 return q;abdcefg第61页/共183页63g g 前序后继为 c, c 可从 g 沿右线索链到 a，a 的右

21、子女即为g 的前序后继。abdcefg第62页/共183页64abdcefg第63页/共183页65p q q p左子树中序第一个结点的左线索。ThreadNode *inParent(ThreadNode *p) if (p) abdcefg第64页/共183页66abdcefg第65页/共183页67abdcefg第66页/共183页68 crt-prethtree(p-left, pre);abdcefgh第67页/共183页69abdcefgh第68页/共183页70个结点一定是其左子树上前序最后一个结点；若其左、右子树都为空，则其前序最后一个结点即为它自己。ThreadNode *

22、preLast(ThreadNode *p) abdcefgh第69页/共183页71若结点p有左子女，则前序后继即为其左子女指针所指结点, 否则为abdcefgh第70页/共183页72q，若p是q的左子女，则其前序下的前驱即为q，否则到abdcefgh第71页/共183页73abdcefgh第72页/共183页74(5) 编号为 k 的结点在第几层？解析：(1) 第 i 层最多有mi-1个结点。(2) 高度为 h 的m叉树最多有(mh-1)/(m-1)个结点。(3) 当k = 0时结点 k 是根，没有父结点；当 k 0 时结点 k 第73页/共183页75问题39. 使用树的双亲表示，寻找

23、某结点 i 的双亲、所有子女、兄弟的时间复杂性是多少？012345 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 层层 2 层层 3 层层第74页/共183页76问题40. 树的先根次序序列的特性是什么？解析：在树的先根次序序列中，第一个元素一定是树的根，如果树的结点个数大于1，它后面紧跟的一定是第一棵子树的根，.。子树又是树，同样满足上述特性。第75页/共183页77问题42. 森林中树T1、T2、T3的结点数为m1、m2、m3，在该森林的二叉树表示中，根的左子树和右子树各有多少结点？C11)2(1nnn二叉树表示第76页/共183页78解析：左指针为

24、空的都是森林中各棵树的叶结点，非叶结点有n-m个。每个非叶结点的子女-兄弟链都有一个右指针为空的结点，加上根结点的右指针为空，故右指针为空的结点有n-m+1个。第77页/共183页79用何种遍历算法？从大到小排列，又采用何种算法？C211nnn第78页/共183页80如果查找成功，说明树中已有要插入的元素，新元素不插入；如果查找失败，则把新结点插入到查找失败的位置。注意，新结点将作为叶结点插入。二叉排序树是向下增长的，最高是单支树情形，若树结点数为n，最大高度为n。第79页/共183页81据，查找失败时查找指针走到外结点。kicspyfkicspyfabdeghjl0qrtx z第80页/共1

25、83页822, 外结点的度为0。n0 = n2+17181)433221(171ASL成功成功kicspyfkicspyf8252)4531(281ASL不成功不成功第81页/共183页83khspykhspy中序遍历h,k,p,s,y顺序插入第82页/共183页84到最大数目，就得到它的最小高度：n2h-1 hlog2(n+1)；若让根的左右子树的结点个数达到最少，可得第83页/共183页85有Nh = Fh+2-1。另外，斐波那契数满足渐进公式：由此可得.251 ,5Fnn.251 ,5Fnn第84页/共183页86的叶结点所在层次的方法与推导高度为 h 的平衡二叉树最少结点. 15N2h

26、h1)(N5h2h1)(Nlog5log2hh1.1615log2第85页/共183页87L1=1L2=2L3=2L4=3L5=3第86页/共183页88字值最小和次小的两棵树合并。在合并时是最小的做左子树还是次小的做左子树？解析：都可以。可参考算法的实现代码，但手工构造时没有限制。第87页/共183页89的Huffman编码，一段报文的总（二进制）编码数用什么衡量？解析：首先根据报文中各字符出现的频度和每个字符的Huffman编码，计算带权路径长度，它就是该报文的总（二进制）编码数，也叫做总编码长度。第88页/共183页90s2 为根的子树（s1 并入 s2, 还是 s2 并入 s1, 根据

27、算法的具体实现而定）；(3) UFSets(S), 把集合S初始化为一个森林。第89页/共183页91解析：即使使用数组作为存储结构，它也是非线性结构。逻辑结构才区分线性还是非线性。因为堆是用完全二叉树组织，可以利用二叉树性质很容易地找某结点的双亲、子女和兄弟。第90页/共183页9249-31 = 18个结点，则形成初始堆的最大关键字比较次数为： 第6层：18*2*1+1*1*1 = 37 ； 第5层：10*2*2+6*2*1 = 52； 第4层：5*2*3+3*2*2 = 42；18/2+124-1023-5第91页/共183页9324032322416106*26)(7*25)(7*24

28、)(7*23)(7*22)(7*21)(7*(2*2i)(h22543210-1h1i-1i）（第92页/共183页94已知二叉树以二叉链表为存储结构，其结点结构已知二叉树以二叉链表为存储结构，其结点结构定义如下：定义如下：Typedef struct BiTNode ElemType data; Struct BiTNode *lchile,*rchild; Int leaf; BiTNode,*BiTree;其中其中leaf域表示该结点的子孙域表示该结点的子孙 ( 含孩子结点含孩子结点 )中所含中所含的叶子结点的个数。开始时，的叶子结点的个数。开始时，leaf域值均为域值均为0,T为指为指

29、向某二叉树根结点的指针。请编写一个算法，填写向某二叉树根结点的指针。请编写一个算法，填写该二叉树中每个结点的该二叉树中每个结点的leaf域。域。第93页/共183页95给定一组字母给定一组字母(A,B,C,D,E,F)，其出现的频率分别为，其出现的频率分别为（6，8，11，3，20，12），），(1)按权值（按权值（6，8，11，3，20，12）设计相应）设计相应 的哈夫曼树。的哈夫曼树。(2) 写出每一个字母的哈夫曼编码。写出每一个字母的哈夫曼编码。(3) 求哈夫曼树的带权路径长度。求哈夫曼树的带权路径长度。第94页/共183页96已知一棵哈夫曼树的顺序存储结构如表已知一棵哈夫曼树的顺序存储

30、结构如表1所示。所示。画出哈夫曼树的逻辑结构树型表示；画出哈夫曼树的逻辑结构树型表示；求权值为求权值为5、7、3、9、6所对应字符的哈夫曼编码；所对应字符的哈夫曼编码；求哈夫曼树的带权路径长度求哈夫曼树的带权路径长度WPL。第95页/共183页97假定一个线性表为假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。求出其平均查找长度。 第96页/共183页98已知某二叉树的中序、后序序列分别为已知某二叉树的中序、后序序列分别为DBAFCE、ABDCEF，则

31、该二叉树的层序序列为，则该二叉树的层序序列为 。 ABCDEAF BDBACEF CDABECF DFDEBCA 第97页/共183页99由元素序列由元素序列16,3,7,11,9,26,18,14,15构造平衡二叉树，构造平衡二叉树，则该平衡二叉树的根为则该平衡二叉树的根为 。 A16 B26 C15 D11第98页/共183页100 二叉排序树结点删除算法二叉排序树结点删除算法二叉排序树结点删除算法思想：二叉排序树结点删除算法思想：设被删结点的指针为设被删结点的指针为p，其双亲结点的指针为，其双亲结点的指针为f，分以下三种情况处理：分以下三种情况处理： p指示的是叶子结点指示的是叶子结点(

32、即即p-lchild=NULL且且p-rchild=NULL)当当*p是是*f的左孩子时的左孩子时(即即f-lchild=p)，置，置f-lchild=NULL；当当*p是是*f的右孩子时的右孩子时(即即f-rchild=p)，置，置f-rchild=NULL； p指示的结点是单分支结点指示的结点是单分支结点 (即即p-rchild=NULL或或p-lchild=NULL)当当*p是是*f的左孩子时的左孩子时(即即f-lchild=p)： 若若*p结点只有左子树，置结点只有左子树，置f-lchild= p-lchild；若若*p结点只有右子树，置结点只有右子树，置f-rchild= p-rch

33、ild。当当*p是是*f的右孩子时的右孩子时(即即f-rchild=p)： 若若*p结点只有左子树，置结点只有左子树，置f-rchild= p-lchild；若若*p结点只有右子树，置结点只有右子树，置f-rchild= p-rchild。第99页/共183页101 p指示的结点是双分支结点指示的结点是双分支结点(即即p-lchildNULL且且p-rchildNULL)找到找到*p结点的中序前驱结点结点的中序前驱结点*q，即，即*p的左子树的的左子树的最右下结点，最右下结点，*q必为单分支结点或叶结点必为单分支结点或叶结点(其右指针为空其右指针为空)；把把*q的值赋给的值赋给*p结点的值域，

34、将删除结点的值域，将删除*p结点的操作结点的操作转换为删除转换为删除*q结点的操作。结点的操作。在以下程序的空白处填上适当的内容，实现以上在以下程序的空白处填上适当的内容，实现以上二叉排序树结点删除算法。二叉排序树结点删除算法。 第100页/共183页102#define EQ(a,b)(a)=(b)#define LT(a,b)(a)rchild) q=p; p=p-lchild; free(q); /右子树空,重接左子树 else if (!p-lchild) q=p; p=p-rchild; free(q); /左子树空,重接右子树 else /左右子树均不空 q=p; s=p-lchi

35、ld; /转左 while (s-rchild) q=s; _(1)_ ; /然后向右到尽头，s指向被删结点的前驱 p-data=s-data; /s的数据域代替p的数据域 if (_(2)_) q-rchild=s-lchild; /重接*q的右子树 else q-lchild=s-lchild; /重接*q的左子树 free(s); /else第101页/共183页103Status DeleteBST(BiTree &T,KeyType key)/若二叉排序树若二叉排序树T中存在关键字等于中存在关键字等于key的数据元素时的数据元素时, /则删除该数据元素结点并返回则删除该数据元素结点并

36、返回TRUE,否则返回否则返回FALSE. if (!T) /不存在关键字等于不存在关键字等于key的数据元素的数据元素 coutdata.key) Delete(T); /找到关键字等于找到关键字等于key的数据元素的数据元素 else if LT(key,T-data.key) DeleteBST(_(3)_,key); else DeleteBST(T-rchild,key); return TRUE; /else第102页/共183页104第103页/共183页105n(n-1)/2 条边，最少有 0 条边；如果是连通图，最多有 n(n-1)/2 条边，最少有 n-1 条边。问题3.

37、有 n 个顶点的有向图最多有多少条边，最少第104页/共183页106度数总和等于边数的 2 倍，这是因为一条边与两个顶点关联，它们在计算度数时做了重复计算。有向图情形，所有顶点的出度总和等于入度总和，还等于边数，因为总体来看，边的出、入平衡。第105页/共183页107定的，还是人为可改变的？解析：图中各个顶点的序号是人为的，可以根据需要改变这些编号，并改变存放顺序。而且每个顶点都可与其他顶点用边连接。第106页/共183页108e 个非零元素，n2-e 个零元素。问题8. 为什么在有向图的邻接矩阵中，统计某行1的个数，得到顶点的出度；统计某列1的个数，第107页/共183页109问题9.

38、有一个存储 n 个顶点 e 条边的邻接表，某个算法要求检查每个顶点，并扫描每个顶点的边链表，那么这样的算法的时间复杂度是O(n*e)，还是O(n+e)?第108页/共183页110边的权值占 4 个字节，每个指针占 2 个字节。若一个无向图有 n 个顶点 e 条边，请问使用邻接矩阵经济还是使用邻接表经济？解析：邻接矩阵表示中顶点向量需要 n*4 个字节，邻接矩阵需要 n2*4 个字节，共 4*(n+n2) 字节。第109页/共183页111表组合起来形成十字链表，它适合于什么场合？解析：适合于往复处理的场合。例如，求强连通分量时需要正反向判断；求关键路径需要正反向求事件的最早和最迟时间等。第1

39、10页/共183页112用邻接表存储图，用深度优先搜索算法即可解决问题。问题13. 图的深度优先搜索类似于树的前序遍历，可归属于哪一类算法？第111页/共183页113解析：对无向图和有向图都适用。但如果无向图不是连通的，或有向图不是强连通的，调用一次遍历算法只能遍历一个连通分量或强连通分量。为了访问所有顶点，必须检查visited数组，找到未被访问的顶点，再次使用遍历算法进行遍历。第112页/共183页114第1个邻接顶点，NextAdjvex(G, v, w)环绕v找剩余邻接顶点。先向先向 w 分分支试探，支试探，退出后向退出后向其他其他 w 分分支试探支试探第113页/共183页115问

40、题17. 图的广度优先生成树是否比深度优先生成树的深度低？解析：是。深度优先搜索从某顶点出发沿某路径一直走下去，直到走不动再回溯，深度要深些。第114页/共183页116中选出权值最小的边的问题，用什么结构辅助最好？解析：用小根堆。形成初始堆的时间复杂度为O(n),以后每次选最小权值边的时间复杂度O(log2n)。第115页/共183页117问题21. Kruskal 算法中为了判断一条边的两个端点是否在同一连通分量上，采用何种辅助结构？解析：采用并查集。取 u = Find(i), v = Find(j)，若 u = v, 说明顶点 i 和 j 在同一连通分量上。连通它们则采用合并操作：Un

41、ion(u, v)。第116页/共183页118值最小的边（一定满足一个端点在 U，另一个端点在V-U），把它的另一个端点加入生成树顶点集合 U。如此重复，直到选出 n-1 条边。这个方法比其他传统方法都简单。第117页/共183页119短路径问题的算法，可否用它解决单目标最短路径问题？解析：可以，对 Dijkstra 算法做适当修改，可以得到求解单目标最短路径问题的算法。算法的首部第118页/共183页120部分用粗体说明if (!Sj & distj getWeight (j, u)+distu) distj = getWeight (j, u) + distu; pathj = u;第1

42、19页/共183页121拓扑排序针对AOV网络（工程计划网络）。问题26. 可以对一个有向图的所有顶点从新编号，把所有表示边的非零元素集中到邻接矩阵的上三角部分。根据什么顺序进行顶点的编号？第120页/共183页122顶点，输出它并把所有它发出的边删去，作为这些边的终顶点的入度减一，如此重复，找到所有的顶点全部输出，说明图中没有环；如果过程中还有顶点未输出，但没有入度为 0 的顶点了，说明图中有环。第121页/共183页123问题29. 为什么拓扑排序的结果不唯一？解析：在偏序图中从某顶点向前遍历可有多种选择方向，导致路径上顶点序列有多种组合。例如下图，拓扑有序序列有abdef,acdef,

43、abdf, acdf。abcdef第122页/共183页124问题31. 为有效地进行关键路径计算，应采用何种结构来存储AOE网络？解析：采用十字链表来存储AOE网络，因为需要一边拓扑排序，一边计算事件的最早开始时间Ae.第123页/共183页125则整个工程的工期不能缩短。可能存在一种特殊的关键活动，它位于所有关键路径上，这种关键活动被称为“桥”。只有它加速，才会使得整个工程的工期缩短。第124页/共183页126解析：不是。各边的权值不同，会导致各个活动的最迟允许开始时间不同，不可能所有活动的最迟允许开始时间减去最早开始时间都是0，所以一定有活动不是关键活动。第125页/共183页127n

44、n开曾走过的 v1, v2, , vn-1，无路可走了，然而它的度大于或等于 2，一定还有一条边回到前面走过的顶点 vi，因此该图存在环。第126页/共183页128在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。A. 出边数 B. 入边数 B. C. 度数 D. 度数减1第127页/共183页129已知下图所示的一个网，按照已知下图所示的一个网，按照Prim方法，从顶点方法，从顶点1 出发，求该网的最小生成树的产生过程。出发，求该网的最小生成树的产生过程。 第128页/共183页130第129页/共183页131第130页/共183页132第131页/共183页133编

45、写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。int degree (Graph & ga, int numb)第132页/共183页134第133页/共183页135查找不成功的平均查找长度niiicp1ASL成功成功njjjcq0ASL不成功不成功第134页/共183页136查找不成功的平均查找长度2121)(11ASL11nnnnincpniniii成功成功11)(11ASL00nnncqnjnjjj不成功不成功第135页/共183页1372121)(11ASL11nnnnincpniniii成功成功1211ASL10nnnnjncqnjnjjj不成功不成功第136页

46、/共183页138假定判定树高度为 h，结点数n = 2h-1。11）(log11)(log121ASL22111nnnnkncphkkniii 成功成功第137页/共183页139Huffman让查找概率高的元素离根最近。hnnhncqnjnjjj1)(1111ASL00不成功不成功第138页/共183页1401小于 k2, , pm-1 (若非空) 的各元素关键字值都大于 km-1；(4) 各棵子树高度的差的绝对值不超过 1。第139页/共183页141(mh-1)/(m-1)*(m-1) = mh-1问题7. 在一棵高度为 h 的平衡 m 叉查找树上如何查找与给定值相等的关键字？第140

47、页/共183页142第141页/共183页143(3) 叶结点下面是失败结点，是查找失败到达的结点，它们是虚拟结点，是实际上并不存在的结点，指向它们的指针为空。第142页/共183页1441)+1) logm(n+1)例如，当m = 2, n = 7, hlog2(7+1) = 3.让每个结点子树棵数达到最少，可得最大高度。第143页/共183页145h = log2(255+1)/2)+1 = 1+log2128 = 8. 第144页/共183页146判断结点溢出的条件是看插入后结点中关键字个数是否达到m 个，若是则结点溢出。结点溢出时需做结点分裂（仅有分裂动作）。把前 m/2-1 个关键字

48、和 m/2 个子树指针留在原第145页/共183页147断需要做结点调整的条件是什么？需要做结点合并的条件是什么？解析：当在叶结点中删除一个关键字后，结点内关键字个数少于 m/2-1，就需要做结点调整或合第146页/共183页148并，把双亲结点中两兄弟结点所夹关键字下移到被删关键字所在结点，再把右兄弟结点的全部子树指针和关键字左移到被删关键字所在结点，释放右兄弟结点。这种结点调整与合并可能要逐层向上进行。第147页/共183页149部关键字，它们处于同一层，且各个叶结点顺序链接。第148页/共183页150问题15. 为什么散列地址会产生冲突？解析：地址空间远小于关键字集合，使得不同关键字通

49、过函数计算，得到相同地址，产生冲突。第149页/共183页151突，会产生堆积（聚集），降低散列速度。为什么？解析：用这种方法解决冲突，寻找下一个“空位”的距离太小，使得局部区域聚集过多表项，不同探测序列交织在一起，导致某一探测序列拉长。第150页/共183页152函数如何设置？解析：要求表的大小设置为质数m，第2个函数用 h2(key) = key % (m-2)+1。它计算的任何值，除1外都与 m 互质，一定可探测到表中所有位置。第151页/共183页153200，则 Un1 / (1-)1.5 1/3n / m = 200 / m = 1/3，解得 m600取满足4k+3的质数，m =

50、607. 。第152页/共183页154假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT12，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。 第153页/共183页1557) 各种内部排序方法的比较第154页/共183页156问题2. 关键字比较次数与数据移动次数，哪个更费时间？解析：数据移动次数。因数据体积较大，存取时间比单纯提取关键字耗费的时间多得多。第155页/共183页157字值的不同数据的相对前后位置。典型的具有不稳定性的排序算法有简单选择排序、希尔排序、快速排序和堆

51、排序。第156页/共183页158问题5. 设待排序元素个数为n，分析直接插入排序的时间代价和空间代价。解析：关键字比较次数：最好n-1, 最差n*(n-1)/2,第157页/共183页159 i=1 43, 71, 86, 13, 38, 60, 27 比较2, 移动2i=2 43, 71, 86, 13, 38, 60, 27 比较2, 移动5i=3 13, 43, 71, 86, 38, 60, 27第158页/共183页160问题8. 给定一个序列 43, 71, 86, 13, 38, 60, 27，给出希尔排序前三趟的结果（用gap=gap/3+1）。解析：每趟按一定间隔gap，把

52、待排序序列分成gap个子序列，分别对各子序列做直接插入排序；然第159页/共183页161gap=1 13, 27, 43, 38, 60, 86, 71 比较8, 移动6 13, 27, 38, 43, 60, 71, 86第160页/共183页162前三趟的结果。解析：每趟在限定序列中从后向前两两比较，发生逆序即对调，一趟下来序列中最小者被换到最前第161页/共183页163问题11. 设待排序元素个数为n，分析起泡排序的时间代价和空间代价。第162页/共183页164比较6, 移动7 i=1 27, 38, 13,43,86, 60, 71 比较4, 移动7i=2 13,27,38,43,71,60, 86 比较1, 移动3 13, 27, 38, 43, 60,71, 86第163页/共183页165问题14. 给定一个序列 43, 71, 86, 13, 38, 60, 27，给出简单选择排序前三趟的结果。解析：每趟在序列中选出最小者，与序列第一个元素对调，序列中最小者到了序列最前端。然后把第164页/共183页166问题15. 设待排序元素个数为n，分析简单选择排序的时间代价和空间代价。解析：关键字比较次数：n(n-1)/2,数据移动次数：最好0, 最差3(n-1),附加存储：1第165页/共183页1671371864338