09 数据结构作业题讲解.pptx

第1页：作业题讲解封面

作业题讲解

第2页：算法S

作业1－5:试用ADL语言编写一个算法，判断任一整数n是否为素数算法S (n. flag)S1[n≤1？]IF (n≤1) THEN (flag←false. RETURN.)S2[初始化]i←2. flag←true.S3[求余判断]WHILE (i≤n-1) DO(IF (n MOD i)=0 THEN(flag←false. RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n)

第3页：算法S（续2）

算法S (n. flag)S1[n≤1？]IF (n≤1) THEN (flag←false. RETURN.)S2[初始化]i←2. flag←true.S3[求余判断]WHILE (i≤「n/2) DO(IF (n MOD i)=0 THEN(flag←false. RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n)

第4页：算法S（续2）

算法S (n. flag)S1[n≤1？]IF (n≤1) THEN (flag←false. RETURN.)S2[初始化]i←2. flag←true.S3[求余判断]WHILE (i≤「n1/2) DO(IF (n MOD i)=0 THEN(flag←false. RETURN.)i←i+1.)▌该算法的时间复杂性最好为：O(1)最坏情况为：O(n1/2)

第5页：作业

作业1－11证明对正整数n≥3，算法BS的元素比较次数T（n）≤5n/3-2。已知信息T（n）= 0 n=11 n=2T( n/2」)+T(「n/2 )+2 n>2数学归纳法证明证明n=3时成立假设n < k时都成立,证明n= k时也成立

第6页：作业（续2）

作业1－11n=3时，T(3)=T(1)+T(2)+2=3，5*3/3-2=3，命题成立。假设n<k时命题成立。n=k时, T(k)=T( )+T( )+2, ...(1)当k≥3时，有k>≥，即k-1≥ ≥所以有T( )≤5*( )/3-2,T( )≤5*()/3-2成立, ...(2)又知k= +, …(3)由(1)(2)(3)，有T(k)=T()+T( )+2≤ [5*( )/3-2]＋[5*( )/3-2]+2= 5*( + )/3-2= 5*k/3-2综上，命题得证。

第7页：编写算法

2-1编写算法Reverse ( A[ ], n)，将顺序存储的线性表A=( a1, a2, …, an )转换为A=( an,…, a2, a1)，要求转换过程中用尽可能少的辅助空间。

第8页：2-1只需从线性表的第一个数据元素开始

2-1只需从线性表的第一个数据元素开始，将第i个数据元素与第n-i+1个数据元素相交换即可。在这个过程中，i的变化范围是1到。这里只需要一个辅助空间temp.

第9页：2-1只需从线性表的第一个数据元素开始（续）

2-1算法Reverse（A，n . A）Reverse1.[元素互换]FOR i=1 TO DO( temp← A[i].A[i] ← A[n-i+1].A[n-i+1]← temp.).▌

第10页：2-8设计一个算法

2-8设计一个算法，将链表的链接完全颠倒。

第11页：算法1：类似于习题2-1

算法1：类似于习题2-1，将第i个与第n-i+1个结点的数据域互换。算法2：遍历链表的同时修改指针。算法3：使用堆栈，实现单链表求逆。2-8

第12页：算法reverse

算法reverse ( head. head)RV1[指针初始化]//q,p,r分别指向三个连续的结点q←NULL. p←next(head).r←next(p).RV2[反转链表]WHILE( r≠NULL ) DO( next(p)←q.//反转结点pq←p.//移动3个指针p←r.r←next(r).)RV3[最后一个结点的处理]next(p)←q.next(head)←p.▌

第13页：2-17对于顺序堆栈和链式堆栈s

2-17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（Stack & s，int n），要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）

第14页：算法思想示例

2-17算法思想示例：n = 34103412stemp3472103412stemp3472103412stemp3472从使用的角度来讲，链式堆栈与顺序堆栈没有区别。

第15页：顺序堆栈

2-17int SelectItem(Stack<int> &s, int n){AStack<int> temp(100);//顺序堆栈LStack<int> temp;//链式堆栈boolean flag = false;int loc=0;while(! s.isEmpty() && s.Peek()!=n){temp.Push(s.Pop());loc++;}

第16页：顺序堆栈（续）

2-17if(s.peek()== n)then { s.Pop(); flag = true;}while(!temp.isEmpty())s.Push(temp.Pop());if (flag)then s.Push(n) else loc =-1;return loc;}

第17页：对于一个用链接方式存储

2-22对于一个用链接方式存储的队列Q(此时队列为空)，执行以下操作序列：QInsert(10), QDelete, QInsert(7), QInsert(1),QInsert(8), QDelete.请用图来说明队列当前的状态。

第18页：2-17对于顺序堆栈和链式堆栈s（续2）

2-17对于顺序堆栈和链式堆栈s，分别编写函数SelectItem（Stack & s，int n），要求在堆栈中查找元素n在栈中第一次出现的位置，并将该位置元素移至栈顶，同时其他元素次序不变。（注意：用int匹配堆栈的模板）

第19页：算法思想示例（续2）

2-17算法思想示例：n = 34103412stemp3472103412stemp3472103412stemp3472从使用的角度来讲，链式堆栈与顺序堆栈没有区别。

第20页：顺序堆栈（续2）

2-17int SelectItem(Stack<int> &s, int n){AStack<int> temp(100);//顺序堆栈LStack<int> temp;//链式堆栈boolean flag = false;int loc=0;while(! s.isEmpty() && s.Peek()!=n){temp.Push(s.Pop());loc++;}

第21页：顺序堆栈（续2）

2-17if(s.peek()== n)then { s.Pop(); flag = true;}while(!temp.isEmpty())s.Push(temp.Pop());if (flag)then s.Push(n) else loc =-1;return loc;}

第22页：对于一个用链接方式存储（续2）

2-22对于一个用链接方式存储的队列Q(此时队列为空)，执行以下操作序列：QInsert(10), QDelete, QInsert(7), QInsert(1),QInsert(8), QDelete.请用图来说明队列当前的状态。

第23页：对于一个用链接方式存储（图）

front17front10frontrear7frontrearrearrear

第24页：对于一个用链接方式存储（续）

3-10设稀疏矩阵Mm*n中有t个非零元素，用三元组表的方式存储.请设计一个算法，计算矩阵M的转置矩阵N，且算法的时间复杂性为O(n+t).注意，书中给出的算法的复杂性为O(n*t).

第25页：算法的关键是求出

A=50 0 0 010 0 20 00 0 0 0-30 0-60 5A’=50 10 0-300 0 0 00 20 0-600 0 0 50050A[0]1010A[1]1220A[2]30-30A[3]32-60A[4]335A[5]0050B[0]0110B[1]03-30B[2]2120B[3]23-60B[4]335B[5]算法的关键是求出A中元素在B中的位置

第26页：算法的关键是求出（续）

3-10算法TRANSPOSE(A. B)TP1[初始化]n←Rows(B)←Cols(A).Cols (B)←Rows(A).t←Count(B)← Count(A).

第27页：计算存储位置

TP2[计算存储位置]//定义数组num存储A中每列非零元素个数FOR i=0 TOn-1 DOnum[i]←0.FOR i=0 TO t-1 DO（j←col(A[i]).num[j]←num[j]+1.）//数组pos存储A中每列第一个非零元素在B中的位置pos[0]←0.FOR i=1 TO n-1 DO(pos[i]←pos[i-1]+num[i-1].)

第28页：处理三元组表

TP3[处理三元组表]FOR i=0 TO t-1 DO( p←col(A[i]).k←pos[p].col( B[k]) ← row(A[i]).row(B[k]) ←col(A[i]).val(B[k]) ← val(A[i]).pos[p]← pos[p]+1.)▌

第29页：4-2由三个结点A

4-2由三个结点A，B和C可以构成多少棵不同的树？可以构成多少棵不同的二叉树？

第30页：树有

4-2树有2种形态：6+3=9种二叉树有5种形态：6*5=30种

第31页：4-3判断以下命题是否为真？若真

4-3判断以下命题是否为真？若真，请证明之；否则，举出反例。一棵二叉树形的所有的叶结点，在先根次序、中根次序和后根次序下的排列都按相同的相对位置出现。

第32页：先根

GFEDCBALKJIH先根：A B C EIFJDGHK L中根：EIC FJBGDKHLA后根：IEJF CG K LH D B A

第33页：数学归纳法令

数学归纳法令n等于二叉树的高度；n=1时；假设n=k时命题成立，n=k+1时，任意两个叶结点l1,l2：l1，l2都在根左（右）子树当中。l1，l2不在根的同一个子树当中。

第34页：4-5编写一算法

4-5编写一算法，判别给定二叉树是否为完全二叉树。

第35页：根据完全二叉树

根据完全二叉树的定义可知，对完全二叉树层次遍历应满足：1）若某结点没有左孩子，则一定无右孩子；2）若某结点有左孩子，但无右孩子，则其层次序列所有后继结点一定是叶结点。3）叶结点的层次序列的所有后继结点一定是叶结点。为此，在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。

第36页：completetree 函数

bool completetree(BintreeNode * t){ Queue Q;Bool B=1, CM=1;if (t!=NULL){ Q.Insert(t);while (!Q.QueueEmpty() && B)

第37页：4-10对以左儿子—右兄弟链接表示的树

4-10对以左儿子—右兄弟链接表示的树，编写计算树的深度的算法。

第38页：解题思路

4-10[解题思路1]树的深度dept(t)=max(t的各子树的深度)+1[解题思路2]基于所对应的二叉树求树的深度[解题思路3]对树做层次遍历，求树的深度

第39页：解题思路（续2）

[解题思路1]树的深度dept(t)=max(t的各子树的深度)+1算法Depth(t. d)D1[递归出口]IF t=NULL THEN ( d←-1 . RETURN )IF (GFC(t)=NULL) THEN ( d← 0 . RETURN )D2[递归调用]p=GFC(t). Max ←-1.

第40页：解题思路（续2）

[解题思路2]基于所对应的二叉树：dept(t)=max（左子树的深度+1，右子树的深度）ACBGDFEACBGDFE

第41页：算法Depth

算法Depth(t. d)D1[递归出口]IF t=NULL THEN ( d←-1 . RETURN )D2[递归调用]Depth(GFC(t). d1)Depth(GNB(t). d2)Max(d1+1, d2).RETURN.)▌

第42页：[解题思路3]对树做层次遍历

[解题思路3]对树做层次遍历，每遍历一层树的深度+1.关键在于如何判断本层遍历的结束。解决方法：可将队列中的结点结构变为(结点，该结点的层数i)。

第43页：算法Depth（续2）

算法Depth(t.d)//t指向与树自然对应的二叉树的根D1[判断t是否为NULL]IFt=NULLTHEN(d←-1.RETURN)D2[创建辅助队列,根结点入队]CREATE(Q).Q←(t,0).d←0.D3[利用队列Q遍历第d层结点]WHILENOT(IsEmpty(Q))DO((p,d)←Q.WHILEp≠NULLDO(IFFirstChild(p)≠NULLTHENQ←(FirstChild(p),d+1)p←NextBrother(p).))▌树的层次遍历ACBGDFE

第44页：请构造权值

4-12请构造权值为{ 5,13,21,7,18,30,41}的哈夫曼树。

第45页：4-12首先

4-12首先，在森林中取权值最小的两个根结点s和n，合成一棵二叉树，新生成的结点T1，作为这两个结点的父结点，T1的权值是两个子结点的权值之和；对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。

第46页：4-12首先（图）

{ 5，13，21，7，18，30，41 }2580551351241393051371821

第47页：第五章习题讲解

第五章习题讲解

第48页：5-7用邻接矩阵

5-7用邻接矩阵存储一个包含1000个顶点和1000条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？

第49页：矩阵中元素个数

１）矩阵中元素个数：1000000２）若图为有向图：非零元素的个数：1000若图为无向图：非零元素的个数：2000３）该矩阵是稀疏矩阵5-7

第50页：5-12设计一个算法

5-12设计一个算法，检测采用邻接表方法存储、具有n个顶点的有向图中是否存在从顶点v到顶点u的路径，若存在路径，算法给出信息TRUE，否则，给出信息FALSE .

第51页：算法DFS

算法DFS(Head,v,visited.visited)DFS1[初始化]CREATS(S).FORi=1TOnDOvisited[i]←0.S←v.DFS2[利用堆栈S深度优先遍历图]WHILENOT(ISEMTS(S))DO(v←S.IFvisited[v]=0THEN(PRINT(v).visited[v]←1.p←adjacent(Head[v]).WHILEp≠ DO(IFvisited[VerAdj(p)]=0THENS←VerAdj(p).p←link(p).)))▐

第52页：是有向图

5-13设G＝（V,E）是有向图，请给出算法，判断G中是否有回路，并要求算法的复杂性为O（n+e）。书中P146，拓扑排序算法：voidGraph::TopoOrder(){inttop=-1;for ( int i=0 ; i<n ; i + + )if ( count[i] = = 0 ){count[i] = top;top = i; }

第53页：检测图中是否有回路

for ( int i=0 ; i<n ; i + + )if (top = =-1)//检测图中是否有回路{ cout << " There is a cycle in network ! " << endl ;return ; }else{ intj=top ; top=count[top];cout<<j<<endl ;//输出栈顶jEdge *p = head[j].Adjacent ;while( p != NULL )//把j的所有邻接顶点的入度减1{ int k=p->VerAdj ;if (--count[k]= = 0 ){count[k]=top ; top=k; }p=p->link ;}}}

第54页：检测图中是否有回路（图）

5-14201234565010103151520353065431S1∞∞1510∞2∞401510∞2 3∞301510352 3 4∞301510352 3 4 5∞301510352 3 4 5 1∞301510351 4 5 2 3 6

第55页：最短路径长度

5-142012345650101031515203530最短路径最短路径长度2→3 102→4 152→4→5 302→4→1 352→6∞

第56页：最短路径长度（图）

5-15

第57页：最短路径长度（续2）

5-16 prim算法1216121635121635461216354661112163546611518

第58页：算法（续2）

5-16 Kruskar算法351246551234656512346561151234656111651234656111618

第59页：第七章排序

第七章排序7-27-57-187-247-49

第60页：对序列

7-2若对序列（7，3，1，8，6，2，4，5）按从小到大排序，请写出冒泡排序的第一趟结果。3，1，7，6，2，4，5，

第61页：7-5设计一算法

7-5设计一算法，在尽可能少的时间内重排数组，使所有取负值的关键词放在所有取非负值的关键词之前，并分析算法的时间复杂度。基本思想：以0为基准记录，使用快速排序的一次分划过程即可，时间复杂度为O(n).

第62页：奇偶交换排序算法

7-18奇偶交换排序算法的基本思想描述如下：排序过程通过对文件x[i](l≤i≤n)的若干次扫描来完成，第奇数次扫描，对所有下标为奇数的记录x[i]与其后面的记录x[i+1](l≤i≤n–1)相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]的内容；第偶数次扫描，对所有下标为偶数的记录x[i]与其后面的记录x[i+1](2≤i≤n–1)相比较，若x[i].KEY＞x[i+1].KEY，则交换x[i]和x[i+1]之内容，重复上述过程直到排序完成为止.

第63页：奇偶交换排序算法（续）

7-18(l)排序的终止条件是什么？(2)完成该算法的具体设计.(3)分析该算法的平均运行时间(最好/最坏).

第64页：算法Sort

算法Sort(X,n)S1[一趟扫描过程中，均没有记录交换则算法终止]change ← 1.while (change)(change ← 0.for i=1 to n-2 step 2//奇交换if (X[i].key>X[i+1].key)( X[i]↔X[i+1].change ← 1.)for i=0 to n-2 step 2//偶交换if (X[i].key>X[i+1].key)( X[i]↔X[i+1].change ← 1.))) ▌

第65页：7-18１）最好情况下

7-18１）最好情况下，比较一趟．每趟中奇交换偶交换比较次数共(n-1)次，无记录交换．２）最坏情况下比较(n／２)趟．每次比较都需要交换，总比较及交换次数为(n-1)*n/2次．３）最好时间O(n)最坏时间O(n2)平均时间O(n2)

第66页：填充如下排序算法中

7-24填充如下排序算法中的方框，并证明该算法的正确性.(实质是一趟快速排序算法)算法PartA(R,s,e)//分划文件(Rs,Rs+1,…,Re),且Ks-1=-∞,Ke+1=+∞PA1[初始化]i ←s. j ←①.K ←Ks. R ←Rs.e+1

第67页：分划过程

PA2[分划过程]while i<j do( j←j-1.while②do j←j-1.if (i≥j) then j←i.else (Ri←Rj.i ← i+1.while Ki<K do i ←i+1.if③then Rj←Ri.)).PA3④▌Kj≥Ki<jRj←R

第68页：算法C

7-49填充如下排序算法中的方框，并讨论该算法的稳定性.算法C(R，n)［C1］FOR i=1 TO n DO①.count[i] ←1

第69页：算法是稳定

［C2］FOR i=n TO 2②DOFOR j=i–1 TO 1 STEP–1 DOIF③THENCOUNT[j] ←COUNT[j]+1ELSE④▌STEP–1Kj>Kicount[i]← count[i]+1该算法是稳定的

第70页：有数据

1.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉查找树，若希望高度最小，则应选择下面哪个序列输入_____。[A] 45, 24, 53, 12, 37, 96, 30[B] 37, 24, 12, 30, 53, 45, 96[C] 12, 24, 30, 37, 45, 53, 96[D] 30, 24, 12, 37, 45, 96, 532.二叉查找树T中关键词互异，则T的最小关键词必无左孩子（指内结点），最大关键词必无右孩子（指内结点）。

此命题是否正确?最小和最大关键词是叶结点吗?一个新结点（其关键词不同于T的任意结点的关键词）总是作为叶结点被插在二叉查找树的合适的外结点处吗?第八章练习

第71页：设有序顺序表为{10

3.设有序顺序表为{10,20,30,40,50,60,70,80}，采用折半查找时，查找成功的平均查找长度是多少（各个关键词等概率）？4.试写一个判别给定二叉树是否为二叉查找树的算法。5.试给出对有序表进行顺序查找的算法，并画出关于有序表顺序查找的判定树，假设每次给定随机的查找值，且成功和不成功查找之概率相等，试求进行每一次查找时，与给定值进行比较的关键词个数的期望值。

第72页：下图所示的高度平衡二叉树（AVL树）中

6.下图所示的高度平衡二叉树（AVL树）中，依次插入关键词为6和10的两个结点，请分别画出依次插入后的AVL树。920832

第73页：答案

3.答案：画出相应的二叉判定树，计算查找成功的平均查找次数（查找长度）。3010204070608050查找成功的平均比较次数是(1+2+2+3+3+3+3+4)/8=21/8，查找失败的平均比较次数是。(3+3+3+3+3+3+3+4+4)/9=29/9

第74页：答案（续2）

9208326920836289362208103622098936220106.答案：