数据结构实用教程第二版徐孝凯课后答案.pdf

file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt 第一章绪习 题 一 一、单选题 1.一个数组元数ai与( A )的表示等价。 A *(a+i) B a+i C *a+i D im;i+) for(int j=0;jn;j+) aij=i*j; A O(m2) B O(n2) C O(m*n) D O(m+n) 5.执行下面程序段时，执行S语句的次数为 (D )。 for(int i=1;i=n;i+) for(int j=1; j=i;j+) S; A n2 B n2/2 C n(n+1) D n(n+1)/2 6.下面算法的时间复杂度为( B) 。 int f(unsigned int n) if(n=0|n=1) return 1; Else return n*f(n-1); A O(1) B O(n) C O(n2) D O(n!) 二、填空题 1.数据的逻辑结构被除数分为 集合结构 、 线性结构 、 树型结构 和 图形结构 四种。 2.数据的存储结构被分为 顺序结构 、 链接结构 、 索引结构 和 散列结构 四种。 3.在线性结构、树型结构和图形结构中，前驱和后继结点之间分别存在着 1对1 、 1对N 和 M对N 的关系。 4.一种抽象数据类型包括 数据 和 操作 两个部分。 5.当一个形参类型的长度较大时，应最好说明为 引用 ，以节省参数值的传输时间和存储参数的空间。 6.当需要用一个形参访问对应的实参时，则该形参应说明为 引用 。 7.在函数中对引用形参的修改就是对相应 实参 的修改，对 值(或赋值)形参的修改只局限在该 函数的内部，不会反映到对应的实参上。 file:/D|/-上架商品-.教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt（第 110 页）2010-3-16 22:06:17 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt 8.当需要进行标准I/O操作时，则应在程序文件中包含 iostream.h 头文件，当需要进行文件I/O操作时， 则应在程序文件中包含 fstream.h 头文件。 9.在包含有 stdlib.h 头文件的程序文件中，使用 rand()%21 能够产生0-20之间的一个随机数。 10.一个记录r理论上占有的存储空间的大小等于所有域的 长度之和 ，实际上占有的存储空间的大小即 记录长度为 sizeof(r) 。 11.一个数组a所占有的存储空间的大小即数组长度为 sizeof(a) ，下标为i的元数ai的存储地址为 a+1 ， 或者为 (char*)a+i*sizeof(ai) 。 12.函数重载要求 参数类型 、 参数个数 或 排列顺序 有所不同。 13.对于双目操作符，其重载函数带有 2 个参数，其中至少有一个为 用户自定义 的类型。 14.若对象ra和rb中至少有一个属于用户定义的类型，则执行ra=rb时，需要调用 等于 号(=) 重载函数，该函数第一个参数应与 ra ，的类型相同，第二个参数应与 rb 的类型相同。 15.从一维数组an中顺序查找出一个最大值元素的时间复杂度为 O(n) ，输出一个二维 数组bmn中所有元素值的时间复杂度为 O(m*n) 。 16.在下面程序段中，s=s+p语句的执行次数为 n ，p*=j语句的执行次数为n(n+1)/2，该 程序段的时间复杂度为 O(n2) 。 int i=0,s=0; while(+i=n) int p=1; for(int j=1;j=0) r1=(float)(-q.b+sqrt(x)/(2*q.a); r2=(float)(-q.b-sqrt(x)/(2*q.a); return 1; else return 0; 按照ax*2+bx+c的格式(x2用x*2表示)输出二次多项式，在输出时要注意 去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。 void Print(Quadratic q) 解： void Print(Quadratic q) if(q.a) coutq.a0) cout+q.bx; else coutq.b0) cout+q.c; else coutq.c; cout; else if(x1=x2) return =; else return; 其时间复杂度为O(1) 将一个字符串中的所有字符按相反方的次序重新放置。 解： void Reverse(char*p) int n=strlen(p); for(int i=0;in/2;i+) char ch; ch=pi pi=pn-i-1; pn-i-1=ch; 其时间复杂度为O(n) 求一维double型数组an中的所有元素之乘积。 解： double product(double a,int n) double p=1; for(int i=0;in;i+) p*=ai; return p; 其时间复杂度为O(n) 计算ni=0 xi/i+1的值。 解： double Accumulate(double x,int n) double p=1,s=1; for(int i=1;i=n;i+) p*=x; s+=p/(i+1); file:/D|/-上架商品-.教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt（第 510 页）2010-3-16 22:06:17 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt return s; 其时间复杂度为O(n) 假定一维数组an中的每个元素值均在0，200区间内，分别统计出落在0，20) ,20,50),50,80),80,130),130,200等各区间的元素个数。 解： int Count(int a,int n,int c5)/用数组c5保存统计结果 int d5=20,50,80,130,201;/用来保存各统计区间的上限 int i,j; for(i=0;i5;i+)ci=0;/给数组c5中的每个元素赋初值0 for(i=0;in;i+) if(ai200) return 0;/返回数值0表示数组中数据有错，统计失败 for(j=0;j=n的条件，Lin和Col为引用 /形参，它是对应实参的别名，其值由实参带回 Lin=0;Col=0; for(int i=0;im;i+) for(int j=0;jaLinCol)Lin=i;Col=j; 其时间复杂度为O(m*n) 4.指出下列各算法的功能并求出其时间复杂度。 int prime(int n) int i=2; int x=(int)sqrt(n); while(ix) return 1; else return 0; 解： 判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为 O(n1/2)。 int sum1(int n) int p=1,s=0; for(int i=1;i=n;i+) p*=i; s+=p; return s; 解： 计算i!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。 int sum2(int n) int s=0; for(int i=1;i=n;i+) int p=1; for(int j=1;j=i;j+) p*=j; s+=p; return s; 解： 计算i!的值，时间复杂度为O(n2) int fun(int n) int i=1,s=1; while(sx) i=x%10; ci+; 解： 利用数组c10中的每个元素ci对应统计出inp所联系的整数文件中个位值同为i的整数个 数，时间复杂度为O(n) void mtable(int n) for(int i=1;i=n;i+) for(int j=i;j=n;j+) couti*j= setw(2)i*j; coutend1; 解： 打印出一个具有n行的乘法表，第i行(1in)中有n-i+1个乘法项，每个乘法项为i与j( ijn)的乘积，时间复杂度为O(n2)。 void cmatrix(int aMN,int d) /M和N为全局整型常量 for(int i=0;iM;i+) for(int j=0;jN;j+) aij*=d; 解： 使数组aMN中的每一个元素均详细以d的值，时间复杂度为O(M*N) void matrimult(int aMN,int bNL,int cML) / int i,j,k; for(i=0;iM;i+) for(j=0;jL;j+) cij=0; for(i=0;iM;i+) for(j=0;jL;j+) for(k=0;kN;k+) cij+=aik*bkj; file:/D|/-上架商品-.教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt（第 810 页）2010-3-16 22:06:17 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt 解： 矩阵相乘，即aMNbNLcML，时间复杂度为O(MNL)。 5.题目略 解： void InitSet(Seti=SETSIZE;i+) s.mi=0; 解：void InitSet(Setin;i+) s.mai=1; 解： Set operator + (Set s1,Set s2) Set s; InitSet(s); for(int i=1;i=SETSIZE;i+) if(s1.mi=1)|s2.mi=1) s.mi=1; return s; 解： Set operator*(Set s1,Set s2) Set s; InitSet(s); for(int i=1;i=SETSIZE;i+) if(s1.mi=1) return s; 解： Boolean operator(int elt,Set s) if(s.melt=1) return True; else file:/D|/-上架商品-.教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt（第 910 页）2010-3-16 22:06:17 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第一章 绪论.txt return False; 解： void Inisert(Set 解： void Delete(Set 解： ostreami=SETSIZE;i+) if(s.mi=1) ostri,; ostrnext=HL; p=HL; D p-next=HL-next;HL-next=p; 5.在一个单链表HL中，若要在指针q所指结点的后面插入一个自由指针p所指向的结点，则执行 D 。 A q-next=p-next;p-next=q; B p-next=q-next;q=p; C q-next=p-next;p-next=q D p-next=q-next;q-next=p; 6.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行 C 。 A p=q-next;p-next=q-next; B p=q-next;q-next=p; C p=q-next;q-next;q-next=q; D q-next=q=-Next-next;q-next=q; 二、填空题 1.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫 值 ，另一个叫 指针 域。 2.在下面数组a中链接存储着一个线性表，表头指针为a0.next，则该线性表为 (38,56,25, 60,42,74) 。 a 0 1 2 3 4 5 6 7 8 data 60 56 42 38 74 25 next 4 3 7 6 2 0 1 3.对于一个长度为l的顺序存储的线性表，在表头插入元素的时间复杂度帾 o(n) ，在表尾插 入元素的时间复杂度为 O(1) 。 4.对于一个单链接存储的线性表，在表头插入结点祫时话里有话复杂度为 o(1) ，在表尾插入 元素的时间复杂度为 o(n) 。 5.在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为 i-1 ，后继元素 的下标为 i+1 。 file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 121 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 6.在线性表的单链接存储中，若一个元素所在结点的地址为p，则后继结点的地址为 p-next ， 若假定p为一个数组a中的下标，则其后继结点的下标为 ap.next 。 7.在循环单链接表中，最后一个结点的指针域指向 表头 结点。 8.在双向链接表中每个结点包含有两个针域，一个指向其 前驱 结点，另一个指向其 后继 结点。 9.在循环双向链接表中表头结点的左指针域指向 表尾 结点，最后一个结点的右指针域指 向 表头 结点。 10.在以HL为表头指针的带表头附加结点的单链接表中，链表为空的条件分别为 HL-next=NULL HL-next=HL 。 11.在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的 表头，具体操作为 ai.next=a1.next;a1.next=i; 。 12.在由数组a中元素结点构成的单链表中，在插入下标为i的结点后，需要从空闲表头中删除一个 结点，并将该结点下标赋给i，具体操作为 i=a1.next;a1.next=ai.next; 。 13.在由数组a中元素结点构成的单链表中，删除下标为i的后继结点并将被删除结点的下标赋给i时 ，所进行的操作描述为 p=ai.next;ai.next=ap.next;i=p; 。 14.在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需 要进行的操作为 aj.next=ai.next;ai.next=j; 。 三、普通题 1. 解：(79,62,34,57,26,48) 解：(26,34,48,57,62,79) 解：(48,56,57,62,79,34) 解：(56,57,79,34) 解：(26,34,39,48,57,62) 2. 解： file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 221 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 为了排版方便，假定采用以下输出格式表示单链接表的示意图；每个括号内的数据表示一个元 素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为 表头指针。 (7(79,6),(62,5),(34,4),(57,3),(26,2),(48,0) (3(26,5),(34,2),(48,4),(57,6),(62,7),(79,0) (2(48,8),(56,4),(57,6),(62,7),(79,5),(34,0) (8(56,4),(57,7),(79,5),(34,0) 3.对于List类型的线性表,编写出下列每个算法。 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若 线性表为空则显示出错信息并退出运行。 解： ElemType DMValue(List exit(1); ElemType x; x=L.list0; int k=0; for(int i=1;iL.size;i+) ElemType y=L.listi; if(yx)x=y;k=i; L.listk=L.listL.size-1; L.size-; return x; 从线性表中删除第i个元素并由函数返回。 解：int Deletel(List exit(1); ElemType x; x=L.listi-1; for(int j=i-1;jL.size-1;j+) L.listj=L.listj+1; L.size-; file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 321 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt return x; 向线性表中第i个元素位置插入一个元素。 解：void Inser1(List exit(1); if(L.size=MaxSize) cerrList overflow!i-1;j-) L.listj+1=L.listj; L.listi-1=x; L.size+; 从线性表中删除具有给定值x的所有元素。 解：void Delete2(List while(iL.size) if(L.listi=x) for(int j=i+1;jL.sizr;j+) L.listj-1=L.listj; L.size-; else i+; 从线性表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解：void Delete3(List while(i=s)jL.size;j+) L.listj-i=L.listj; L.size-; else i+; 从有序表中删除其值在给定值s和t之间(要求s小于t)的所有元素。 解：void Delete4(List while(iL.size)/从有序表L中查找出大于等于s的第一个元素 if(L.listis)i+; else break; if(iL.size) While(i+jL.size)/求出s和t之间元素的个数 for(int k=i+j;kMaxSize) cerrList overflow!end1; exit(1); int i=0,j=0,k=0; while(iL1.size) i+; else /将L2中的元素赋给L L.listk=L2.listj; j+; file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 521 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt k+; while(iL1.size) /将L1中剩余的元素赋给L L.listk=L1.listi; i+;k+; while(jL2.size) /将L2中剩余的元素赋给L L.listk=L2.listj; j+;k+; L.size=k; 从线性表中删除所有其值重复的元素，使其所有元素的值均不同，如对于线性表(2,8,9, 2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。 解：void Delete5(List while(iL.size) int j=i+1; while(jnext=HL; HL=q; 删除单链表中的第i个结点。 解：void Delete1(LNode* j+; if(cp=NULL) cerrIndex is out range!next=cp-next; delete cp; 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息 并停止运行。 解：ElemType MaxValue(LNode*HL) /从单链表中查找出所有元素的最大值，该值由函数返回 file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 721 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt if(HL=NULL) cerrLinked list is empty!next; while(p!=NULL) if(maxdata) max=p-data; p=p-next; return max; 统计出单链表中结点的值等于给定值x的结点数。 解：int Count(LNode*HL,ElemType x) /统计出单链表中结点的值等于给定值x的结点数 int n=0; while(HL!=NULL) if(HL-data=x) n+; HL=HL-next; return n; 根据一维数组an建立一个单链表，使单链表中元素的次序与an中元素的次序相同， 并使该算法的时间复杂度为O(n)。 解：void Create(LNode* for(int i=n-1;i=0;i-) InsertFront(HL,ai; 将一个单链表重新链接成有序单链表。 解：void OrderList(LNode*/p指向待处理的第一个结点，初始指向原表头结点 HL=NULL; /HL仍为待建立的有序表的表头指针，禄始值为空 while(p!=NULL) /把原单链表中的结点依次进行有序链接 file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 821 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt LNode* q=p; /q指向待处理的结点 p=p-next; /p指向下一个待处理的结点 LNode* ap=NULL,*cp=HL; /cp指向有序表中待比较的结点，ap指向其前驱结点 while(cp!=NULL) /为插入q结点寻找插入位置 if(q-datadata) break; else ap=cp; cp=cp-next; /将q结点插入到ap和cpxf hko pp uj q-next=cp; if(ap=NULL) HL=q; else ap-next=q; 将两个有序单链表合并成一个有序单链表，合并后使原有单链表为空。 解：LNode*Mergel(LNode* /a结点作为结果的有序单链表的表头附加结点，这样便于处理，处理 /结束后返回a结点的镄针域的值 LNode*p= /p指向结果的有序单链表的表尾结点 p-next=NULL;/初始指向表头附加结点 while(p1!=NULL)p1=p1-next; else p-next=p2;p2=p2-; p=p-next; if(p1!=NULL)p-next=p1; if(p2!=NULL)p-next=p2; p1=p2=NULL; return a.next; file:/D|/-上架商品-.程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 921 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。如假定两个有序单链 表中的元素为(2,8,10,20)和(3,8,9,15,16)，则生成的新单链表中的元素为(2,3,8,8,9,10,15, 16,20)。 解：LNode*Merge2(LNode*p1,LNode*p2) /根据两个有序单链表生成一个新的有序单链表 LNode a; /用a作为新的有序单链表的表头附加结点 LNode*p= /p指向结果有序单链表的表尾结点 p-next=NULL; /初始指向表头附加结点 while(p1!=NULL if(p1-datadata) /由p1-data建立新结点，然后p1指针后移 newptr-data=p1-data; p1=p1-next; else /由p2-data建立新结点，然后p2指针后移 newptr-data=p2-data; p2=p2-next; /将newptr结点插入到结果的有序表的表尾 p-next=newptr; p=newptr; while(p1!=NULL) /继续处理p1单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p1-data; p1=p1-next; p-next=newptr; p=newptr; while(p2!=NULL) /继续处理p2单链表中剩余的结点 LNode*newptr=new LNode; newptr-data=p2-data; p2=p2-next; p-next=newptr; p=newptr; p-next=NULL; file:/D|/-上架商品-. (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 1021 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt return a.next; 根据一个元素类型为整型的单链表生成两个单链表，使得第一个单链表中包含原单链表中所有 元素值为奇数的结点，使得第二个单链表中包含原单链表中所有元素值为偶数的结点。原有单链表 保持不变。 解：void Separate(LNode*HL,LNode* /a和b结点分别作为p1和p2单链表的表头附加结点 LNode*t1= /t1和t2分别作为指向p1和p2单链表的 /表尾结点，初始指向表头附加结点 Lnode*p=HL; while(p!=NULL) /每循环一次产生一个新结点，并把它加入到p1或p2单链表 /的未尾 LNode*newptr=new LNode; if(p-data%2=1) newptr-data=p-data; t1-next=newptr; t1=newptr; else newptr-data=p-data; t2-next=newptr; t2=newptr; p=p-next; t1-next=t2-next=NULL; p1=a.next;p2=b.next; /把指向两个单链表的表头结点的指针分别赋给 /p1和p2返回 6.编写一个算法，使用表头附加结点的循环单链表解决约瑟夫(Josephus)问题。其问题是 ：设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人出列(即离开坐位， 不参加以后的报数)，接着从出列的下一个人开始重新从1报数，数到m的人又出列，如此下 去直到所有人都出列为止，试求出它们的出列次序。 假如，当n=8、m=4时，若从第一个人(假定每个人的编号依次为1,2.,n)开始报数，则得 到的出列次序为:4,8,5,2,1,3,7,6。 此算法要求以n、m和s(假定从第s个人开始第一次报数)作为值参。 解： void Josephus(int n,int m,int s) /使用带表头附加结点的循环单链表解决约瑟夫问题 file:/D|/-上架商品-. (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt（第 1121 页）2010-3-16 22:06:59 file:/D|/-上架商品-/数据结构实用教程 (第二版) 课后答案 (徐孝凯 著) 清华大学出版社/第二章 线性表.txt /生成表头附加结点，此时循环单链表为空 LNode*HL=new LNode; HL-next=HL; int i; /生成含有n个结点、结点依次为1,2,.n的带表头结点的循环单链表 for(i=n;i=1;i-) /生成新的结点 LNode*newptr=new LNode; newptr-data=i; /把新的结点插入到表头 newptr-next=HL-next; HL-next=newptr; /从表头开始顺序查找出第s个结点，对应第一个开始报数的人