数据结构课后习题答案讲解

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)(3) for(int i=1;i=n;i+) for(int j=1;j=i

2、;j+) for (int k=1;k=(y+1)*(y+1) y+;划线语句的执行次数为划线语句的执行次数为 n1/2 ,渐近时间复杂度为渐近时间复杂度为O(n1/2)2-4Loc(Aijk)=134+(i*n*p+j*p+k)*22-9. 设有长度为设有长度为n 的一维整型数组的一维整型数组A，设计一个算法，将原数，设计一个算法，将原数组中的元素以逆序排列组中的元素以逆序排列void Invert(T elements, int length) /length数组长度数组长度/elements为需要逆序的数组为需要逆序的数组 T e; for (int i=1;iLink; p-Link=

3、first;first=p; p=q;return first; 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(E); pop(); 3-1

4、. 设设A，B，C，D，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得后可立即出栈），问能否得到下列序列。若能得到，则给出相应的到，则给出相应的push和和pop序列；若不能，则序列；若不能，则说明理由。说明理由。（2）A，C，E，B，D（2）不能得到该序列，在）不能得到该序列，在E出栈时，出栈时，B和和D在栈在栈中，中，B比比D先进栈，所以先进栈，所以D应比应比B先出栈。先出栈。（3）不能得到该序列，在）不能得到该序列，在C出栈时，出栈时，A和和B在栈中在栈中，A比比B先进栈，所以先进栈，所以B应比应比A先出栈。先出栈。 3-1. 设设A，B，C，D

5、，E五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到后可立即出栈），问能否得到下列序列。若能得到，则给出相应的，则给出相应的push和和pop序列；若不能，则说序列；若不能，则说明理由。明理由。（3）C，A，B，D，E（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五个元素依次进栈（进栈五个元素依次进栈（进栈后可立即出栈），问能否得到

6、下列序列。若能得到后可立即出栈），问能否得到下列序列。若能得到，则给出相应的，则给出相应的push和和pop序列；若不能，则说序列；若不能，则说明理由。明理由。（4）E，D，C，B，A4-1. 设线性表采用顺序表示方式，并假定顺序表是设线性表采用顺序表示方式，并假定顺序表是有序的（设有序的（设表中元素已按非递减次序排列表中元素已按非递减次序排列）。编写）。编写函数，实现线性表的如下运算：函数，实现线性表的如下运算：（1）int Search_Insert(List *lst,T x)后置条件：在有序的顺序表中搜索元素后置条件：在有序的顺序表中搜索元素x。若若x在表中，则在表中，则返回返回x在表

7、中的位置在表中的位置。否则，若表未满，则在表中插入新元素否则，若表未满，则在表中插入新元素x，并且插，并且插入后，线性表仍然是有序的，入后，线性表仍然是有序的，返回新元素返回新元素x的位置的位置；若表已满，无法插入新元素，则若表已满，无法插入新元素，则返回返回-1。int Search_Insert(List *lst, T x) int i,j; for(i=0; (xlst-Elementsi)&(iSize);i+); / 查找首个大于等于查找首个大于等于x的元素位置，并记录在的元素位置，并记录在i中中 if (lst-Elementsi=x)return i;/x在表中时，返回在表中时

8、，返回x的位置的位置 if (IsFull(lst) /或或if(lst-Size=lst-maxList)return -1; /表已满时，无法插入，返回表已满时，无法插入，返回-1 for (j=lst-Size-1; j=i; j-)lst-Elementj+1=lst-Elementj; lst-Elementi=x; /新元素即插入位置新元素即插入位置i处处 lst.Size+; return i;/插入新元素并返回该元素的位置插入新元素并返回该元素的位置4-1. 设线性表采用顺序表示方式，并假定顺序表是设线性表采用顺序表示方式，并假定顺序表是有序的（设有序的（设表中元素已按非递减次

9、序排列表中元素已按非递减次序排列）。编写）。编写函数，实现线性表的如下运算：函数，实现线性表的如下运算：（2）void Search_Delete(List *lst, T x,T y)前置条件：前置条件：xSize=0) printf(“The list is empty”);return -1; int i,j,sum=0; for (i=0;tempix&in-1) return;/没有符合条件的元素没有符合条件的元素 for (j=i;lstj=y&jn;j+);/找到首个大于找到首个大于y的元素位置的元素位置j sum=j-i; while(jn) lsti+=lstj+;/删除删除

10、sum个元素个元素 n=n-sum;for (j=i;jy) /大于大于y的元素前移的元素前移lsti+=lstj+;else/小于等于小于等于y的元素删除的元素删除 j+; n-; 006003000700000008100000090261031473283310449列三元组：列三元组： 10302632833101474494.7 求对题图求对题图4-1的稀疏矩阵执行矩阵转置时数组的稀疏矩阵执行矩阵转置时数组num和和k的值。的值。col01234numcol10212kcol01134行三元组行三元组： （1）无序树：）无序树：9棵棵（2）有序树：）有序树：12棵棵（3）二叉树：）二

11、叉树：30棵棵3棵棵6棵棵6棵棵6棵棵各各6棵棵6-3. 设在度为设在度为m的树中，度为的树中，度为1，2，m的节点的节点个数分别为个数分别为n1,n2,nm，求叶子节点的数目。，求叶子节点的数目。设度为设度为0的节点个数为的节点个数为n0则：则：树的总度数树的总度数=节点总个数节点总个数-1即：即：1*n1+2*n2+m*nm =n0+ n1+n2+n3+.+ nm-1因此叶子节点数目为：因此叶子节点数目为：n0=n2+2*n3+.+ (m-1)nm+16-5. 找出所有二叉树，其节点在下列两种次序下找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现：恰好都以同样的次序出现：（1）

12、先序和中序；（）先序和中序；（2）先序和后序；（）先序和后序；（3）中）中序和后序序和后序（1）或者为空二叉树，或者所有结点的左子树都）或者为空二叉树，或者所有结点的左子树都是空的单支树是空的单支树（2）或者为空二叉树，或者只有根结点的二叉树）或者为空二叉树，或者只有根结点的二叉树（3）或者为空二叉树，或者所有结点的右子树都）或者为空二叉树，或者所有结点的右子树都是空的单支树是空的单支树ABFCDEGH先序：先序：DEHFJGCKAB中序：中序：HEJFGKCDAB后序：后序：HJKCGFEBADDEAFJGBCHKint SizeL(BTree Bt) return SizeofLeaf(B

13、t.Root); int SizeofLeaf(BTNode *p) if(!p) return 0; if( (!(p-RChild)&(!(p-LChild) )return 1; return SizeofLeaf(p-LChild)+SizeofLeaf(p-RChild); void 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); A:1010 B:1011 C:

14、100 D:00 E:01 F:11加权路径长度：加权路径长度：WPL=(2+3)4+53+(7+9+12)2=91 3725451456659176建成的二叉树建成的二叉树37254514566591删除删除76后后372514566591删除删除45后后282536343543339-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key % 11h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键采用线性探查法、二次探查法解决冲突，试用关键字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，555

15、5分别分别建立散列表。建立散列表。线性探查法：线性探查法：Keyh(Key)70425380335260545150655005545352570806050123456789109-3 9-3 设散列表设散列表ht11ht11，散列函数，散列函数h(key)=key % 11h(key)=key % 11。采用线性探查法、二次探查法解决冲突，试用关键采用线性探查法、二次探查法解决冲突，试用关键字值序列：字值序列：7070，2525，8080，3535，6060，4545，5050，5555分别分别建立散列表。建立散列表。二次探查法：二次探查法：Keyh(Key)704253803352605

16、45150655004535802570605055123456789109-4 9-4 对上题的例子，若采用双散列法，试以散列函对上题的例子，若采用双散列法，试以散列函数数h h1 1(key)=key % 11(key)=key % 11， h h2 2(key)=key % 9+1(key)=key % 9+1建立散建立散列表。列表。0558035257060455012345678910Keyh1(Key)704253803352605451506550h2(Key)88997162对80：（3+1*9）%11=1 对45：（1+1*1）%11=2 （1+2*1）%11=3（1+3*1

17、）%11=4 （1+4*1）%11=5（1+5*1）%11=6 对50：（6+1*6）%11=1 （6+2*6）%11=75 52 24 41 13 30 0(1)(1)各个顶点的入度和出度各个顶点的入度和出度顶点顶点 入度入度 出度出度0 03 30 01 12 22 22 21 12 23 31 12 24 42 23 35 51 11 1(2)(2)强连通分量强连通分量(3)(3)邻接矩阵邻接矩阵0 00 00 00 00 00 01 01 00 10 10 00 00 10 10 00 01 01 00 00 01 01 01 01 01 11 10 00 00 10 11 01 00

18、 00 00 00 02 24 41 13 35 50 05 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5void Degree(Graph g, int *d) int i; int n=g.Vertices; Enode* p; for (i=0;in;i+) di=0; for (i=0;inextArc)dp-adjVex+; for (i=0;in;i+) cout“d“i“=“di;10-6 10-6 在题在题10-210-2所建立的邻接表上进

19、行以顶点所建立的邻接表上进行以顶点2 2为起为起点顶点的深度优先搜索和宽度优先搜索。分别画出点顶点的深度优先搜索和宽度优先搜索。分别画出遍历所得到的深度优先搜索和宽度优先搜索的生成遍历所得到的深度优先搜索和宽度优先搜索的生成森林（或生成树）。森林（或生成树）。5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5题题10-2所建立的邻所建立的邻接表对应的图为：接表对应的图为：以顶点以顶点2为起点顶点的深度优先为起点顶点的深度优先搜索所得到深度优先搜索生成树：搜索

20、所得到深度优先搜索生成树：0 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 55 52 24 41 13 30 0深度优先遍历：深度优先遍历：2，4，5，0，1，3以顶点以顶点2为起点顶点的宽度优先为起点顶点的宽度优先搜索所得到宽度优先搜索生成树：搜索所得到宽度优先搜索生成树：5 52 24 41 13 30 00 0 5 5 0 0 1 12 23 34 45 50 0 3 3 4 4 4 4 0 0 2 2 1 1 1 10 01 12 23 34 45 5宽度优先遍历：宽度优先遍历：2，4

21、，1，5，0，34 42 25 50 03 31 11 17 72 21 15 56 69 92 24 42 25 50 03 31 11 17 72 21 15 5Prim算法以算法以1为源点，生成的最小代价生成树为：为源点，生成的最小代价生成树为：（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 87）03 08 70 97 75 53 26第第3趟趟 （03 12 61 87）08 70 97 75 53 26第第4趟趟 （03 0

22、8 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） （3）冒泡排序（注意冒泡排序只排了）冒泡排序（注意冒泡排序只排了7趟）趟）初始序列初始序列(61 87 12 03 08 70 97 75 53 26)第第1趟趟 61 12 03 08

23、 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（4）快速排序）快速排序初始序列初始序列61 87 12 03 08 70 97 75 53 26 第第1趟趟 (53 26 12 3 8)

24、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 （5）简单选择排序）简单选择排序初始序列初始序列 61 87 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