南邮_数据结构作业答案讲解【知识探索】.ppt

《南邮_数据结构作业答案讲解【知识探索】.ppt》由会员分享，可在线阅读，更多相关《南邮_数据结构作业答案讲解【知识探索】.ppt（49页珍藏版）》请在三一文库上搜索。

1、第一章 习题讲解,1-19.确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do k=k+10*i; i+; while(i=n-1) 划线语句的执行次数为 n-1 ,渐近时间复杂度为O(n) (2）i=1; x=0; do x+; i=2*i; while （in）; 划线语句的执行次数为 log2n ,渐近时间复杂度为O(log2n),1,峰谷文书,(3) for(int i=1;i=(y+1)*(y+1) y+; 划线语句的执行次数为 n1/2 ,渐近时间复杂度为O(n1/2),2,峰谷文书,2-4Loc(Aijk)=134+(i

2、*n*p+j*p+k)*2,第二章 习题讲解,3,峰谷文书,2-9. 设有长度为n 的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列 void Invert(T elements, int length) /length数组长度 /elements为需要逆序的数组 T e; for (int i=1;ilength/2;i+) e=elementsi-1; elementsi-1=elementslength-i; elementslength-i=e; ,4,峰谷文书,2-12.设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。 Node* pInver

3、t(Node* first) Node *p=first, *q; first=NULL;while (p) q=p-Link; p-Link=first; first=p; p=q; return first; ,5,峰谷文书,3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 （1）A，B，C，D，E,（1）能得到该序列。 相应的push和pop序列为：push(A); pop(); push(B); pop(); push(C); pop(); push(D); pop(); push(

4、E); pop();,第三章 习题讲解,6,峰谷文书,3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 （2）A，C，E，B，D,（2）不能得到该序列，在E出栈时，B和D在栈中，B比D先进栈，所以D应比B先出栈。,第三章 习题讲解,7,峰谷文书,（3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。,3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 （3）C，A

5、，B，D，E,8,峰谷文书,（4）能得到该序列。 相应的push和pop序列为：push(A); push(B); push(C); push(D); push(E); pop(); pop(); pop(); pop(); pop();,3-1. 设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。 （4）E，D，C，B，A,9,峰谷文书,第四章 习题讲解,4-1. 设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算： （1）int Searc

6、h_Insert(List *lst,T x) 后置条件：在有序的顺序表中搜索元素x。 若x在表中，则返回x在表中的位置。 否则，若表未满，则在表中插入新元素x，并且插入后，线性表仍然是有序的，返回新元素x的位置； 若表已满，无法插入新元素，则返回-1。,10,峰谷文书,int Search_Insert(List *lst, T x) int i,j; for(i=0; (xlst-Elementsi)/插入新元素并返回该元素的位置 ,11,峰谷文书,4-1. 设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算： （2）void S

7、earch_Delete(List *lst, T x,T y) 前置条件：xy 后置条件：删除有序表中元素值在x和y之间（含x和y）的所有元素。,12,峰谷文书,void Search_Delete(List *lst, T x, T y) if (lst-Size=0) printf(“The list is empty”);return -1; int i,j,sum=0; for (i=0;tempin-1) return;/没有符合条件的元素 for (j=i;lstj=y ,for (j=i;jy) /大于y的元素前移 lsti+=lstj+; else/小于等于y的元素删除 j+

8、; n-; ,13,峰谷文书,4.6 给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。,列三元组：,4.7 求对题图4-1的稀疏矩阵执行矩阵转置时数组num和k的值。,行三元组：,14,峰谷文书,6-2. 对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？,（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵,3棵,6棵,6棵,6棵,各6棵,第六章 习题讲解,15,峰谷文书,6-3. 设在度为m的树中，度为1，2，m的节点个数分别为n1,n2,nm，求叶子节点的数目。,设度为0的节点个数为n0则： 树的总度数=节点总个数-1 即：1*n1+2*n2

9、+m*nm =n0+ n1+n2+n3+.+ nm-1 因此叶子节点数目为：n0=n2+2*n3+.+ (m-1)nm+1,16,峰谷文书,6-5. 找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现： （1）先序和中序；（2）先序和后序；（3）中序和后序,（1）或者为空二叉树，或者所有结点的左子树都是空的单支树 （2）或者为空二叉树，或者只有根结点的二叉树 （3）或者为空二叉树，或者所有结点的右子树都是空的单支树,17,峰谷文书,6-6. 设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 （B D C E） A （F H G ） （2）后序遍历 （D E C B）

10、（H G F） A 画出该二叉树。,18,峰谷文书,6-7 写出下图中二叉树的先序、中序和后序遍历结果,先序：DEHFJGCKAB 中序：HEJFGKCDAB 后序：HJKCGFEBAD,19,峰谷文书,int SizeL(BTree Bt) return SizeofLeaf(Bt.Root); int SizeofLeaf(BTNode *p) if(!p) return 0; if( (!(p-RChild) ,6-8.设二叉树以二叉链表存储，试编写求解下列问题的递归算法：（3）求一棵二叉树中的叶结点个数；,20,峰谷文书,（4）设计算法，交换一棵二叉树中每个结点的左、右子树。,void

11、 ExchBt(BTree Bt) Exch(Bt.Root); void Exch(BTNode *p) if (p) BTNode *q=p-LChild; p-LChild=p-RChild; p-RChild=q; Exch(p-LChild); Exch(p-RChild); ,21,峰谷文书,6-13. 将上图中的树转换成二叉树，并将下图中的二叉树转换成森林。,22,峰谷文书,6-18. 设S=A,B,C,D,E,F，W=2,3,5,7,9,12，对字符集合进行哈夫曼编码，W为各字符的频率（1）画出哈夫曼树（2）计算带权路径长度（3）求各字符的编码,A:1010 B:1011 C:

12、100 D:00 E:01 F:11,加权路径长度：WPL=(2+3)4+53+(7+9+12)2=91,23,峰谷文书,7-4为什么说对半搜索算法只适用于顺序有序表的情况？为什么说顺序搜索可用于顺序表和链表，也不受表的有序性限制？,解：1、对半搜索算法必须针对顺序存储的有序表，要求满足两个条件： 1）顺序存储，只有顺序存储才可以根据元素下标（地址）随机存取元素； 2）有序存储，只有有序存储才可以其实现对半查找。2、顺序搜索从头到尾逐个查找，所以可用于顺序表和链表，也不受表的有序性限制。,24,峰谷文书,补充：已知（1，2，3，4，5，6，7，8，9，10，11）找到9比较几次？,解： 第一次

13、比较：M=(1+11)/2=6，69， 找7，11； 第2次比较：M=(7+11)/2=9， 9=9， 成功。 所以一共比较2次成功,25,峰谷文书,8-1 建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？,建成的二叉树,26,峰谷文书,8-1 建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？,删除76后,27,峰谷文书,8-1 建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依次删除76，45，则树形分别如何？,删除45

14、后,28,峰谷文书,8-3 已知对一棵二叉搜索树进行先序遍历的结果是：28，25，36，33，35，34，43，请画出此二叉搜索树。,29,峰谷文书,9-3 设散列表ht11，散列函数h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55分别建立散列表。,线性探查法：,30,峰谷文书,9-3 设散列表ht11，散列函数h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键字值序列：70，25，80，35，60，45，50，55分别建立散列表。,二次探查法：,0,45,35,80,25,70,60

15、,50,55,1,2,3,4,5,6,7,8,9,10,31,峰谷文书,9-4 对上题的例子，若采用双散列法，试以散列函数h1(key)=key % 11， h2(key)=key % 9+1建立散列表。,对80：（3+1*9）%11=1 对45：（1+1*1）%11=2 （1+2*1）%11=3 （1+3*1）%11=4 （1+4*1）%11=5（1+5*1）%11=6 对50：（6+1*6）%11=1 （6+2*6）%11=7,32,峰谷文书,10-1 对如图所示的有向图，求：(1)每个顶点的入度和出度；(2)强连通分量；(3)邻接矩阵。,(1)各个顶点的入度和出度,顶点 入度 出度 03

16、0 122 212 312 423 511,(2)强连通分量,(3)邻接矩阵,0 00 00 0 1 00 10 0 0 10 01 0 0 01 01 0 1 10 00 1 1 00 00 0,33,峰谷文书,10-2 从只有6个顶点没有边的图开始，以边, , , , , , , , , 的次序，通过使用程序10-4的Add函数插入这些边，建立该图的邻接表结构。请画出所建成的邻接表结构。,34,峰谷文书,10-4 已知有向图的邻接表，写出计算各个顶点的入度的算法。,void Degree(Graph g, int *d) int i; int n=g.Vertices; Enode* p;

17、 for (i=0;inextArc) dp-adjVex+; for (i=0;in;i+) cout“d“i“=“di; ,35,峰谷文书,10-6 在题10-2所建立的邻接表上进行以顶点2为起点顶点的深度优先搜索和宽度优先搜索。分别画出遍历所得到的深度优先搜索和宽度优先搜索的生成森林（或生成树）。,题10-2所建立的邻接表对应的图为：,36,峰谷文书,以顶点2为起点顶点的深度优先搜索所得到深度优先搜索生成树：,深度优先遍历：2，4，5，0，1，3,37,峰谷文书,以顶点2为起点顶点的宽度优先搜索所得到宽度优先搜索生成树：,宽度优先遍历：2，4，1，5，0，3,38,峰谷文书,10-14

18、使用普里姆算法以1为源点，画出图10-27的无向图的最小代价生成树。,4,2,5,0,3,1,1,7,2,1,5,Prim算法以1为源点，生成的最小代价生成树为：,39,峰谷文书,11-2 设有记录序列：61，87，12，03，08，70，97，75，53，26。现按下列算法对它分别进行排序，请手工模拟算法的执行过程，给出每趟排序结果。（1）直接插入排序（3）冒泡排序（4）快速排序（5）简单选择排序,40,峰谷文书,（1）直接插入排序 初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61

19、 87）03 08 70 97 75 53 26 第3趟 （03 12 61 87）08 70 97 75 53 26 第4趟 （03 08 12 61 87）70 97 75 53 26 第5趟 （03 08 12 61 70 87）97 75 53 26 第6趟 （03 08 12 61 70 87 97）75 53 26 第7趟 （03 08 12 61 70 75 87 97）53 26 第8趟 （03 08 12 53 61 70 75 87 97）26 第9趟 （03 08 12 26 53 61 70 75 87 97）,41,峰谷文书,（3）冒泡排序（注意冒泡排序只排了7趟）

20、初始序列(61 87 12 03 08 70 97 75 53 26) 第1趟 61 12 03 08 70 87 75 53 26 97 第2趟 12 03 08 61 70 75 53 26 87 97 第3趟 03 08 12 61 70 53 26 75 87 97 第4趟 03 08 12 61 53 26 70 75 87 97 第5趟 03 08 12 53 26 61 70 75 87 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97,42,峰谷文书,（4）快速排序 初始序列61 87

21、12 03 08 70 97 75 53 26 第1趟 (53 26 12 3 8) 61 (97 75 70 87) 第2趟 ( 8 26 12 3) 53 61 (97 75 70 87) 第3趟 (3) 8 (12 26) 53 61 (97 75 70 87) 第4趟 3 8 12 (26) 53 61 (97 75 70 87) 第5趟 3 8 12 26 53 61 (87 75 70) 97 第6趟 3 8 12 26 53 61 (70 75) 87 97 第7趟 3 8 12 26 53 61 70 (75) 87 97,43,峰谷文书,（5）简单选择排序 初始序列 61 8

22、7 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26 第2趟 （03 08）12 61 87 70 97 75 53 26 第3趟 （03 08 12）61 87 70 97 75 53 26 第4趟 （03 08 12 26）87 70 97 75 53 61 第5趟 （03 08 12 26 53）70 97 75 87 61 第6趟 （03 08 12 26 53 61）97 75 87 70 第7趟 （03 08 12 26 53 61 70）75 87 97 第8趟 （03 08 12 26 53 61 70 75）

23、87 97 第9趟 （03 08 12 26 53 61 70 75 87）97,44,峰谷文书,11-4 从以下几个方面比较题11-2中各种排序算法。（1）最好、最坏和平均情况下的时间复杂度；（3）稳定性（对不稳定的算法给出一个简单的实例）；（4）指出第1趟排序结束后就能确定某个元素最终位置的算法。,45,峰谷文书,（1）最好、最坏和平均情况下的时间复杂度： 简单选择排序: 三种情况下的时间复杂度都为O(n2)。 直接插入排序： 最好情况下为O(n)； 平均和最坏情况下为O(n2)。 冒泡排序： 最好情况为O(n)； 最坏和平均情况下为O(n2)。 快速排序： 最好和平均情况下为O(nlog2n)； 最坏情况下时间复杂度为O(n2)。,46,峰谷文书,（3）稳定性： 不稳定的是简单选择排序和快速排序两种，其它是稳定的。 实例：3 3 1 简单选择排序过后变成了 1 3 3， 3 4 3 快速排序之后变成了3 3 4,47,峰谷文书,（4）第一趟排序结束后就能确定某个元素最终位置的算法： 简单选择排序：确定最小元素在第一位 冒泡排序：确定最大元素在最后一位 快速排序：确立分割元素在中间,48,峰谷文书,49,峰谷文书,