数据结构第二版主编殷人昆课后答案市公开课一等奖百校联赛获奖课件.pptx

1数据结构数据结构数据结构数据结构 第一单元课后参考答案第一单元课后参考答案第一单元课后参考答案第一单元课后参考答案第1页2一、单项选择题一、单项选择题一、单项选择题一、单项选择题1.1.一个数组元素一个数组元素一个数组元素一个数组元素aiai与与与与A*(a+i)A*(a+i)表示等价表示等价表示等价表示等价.A*(a+i)A*(a+i)B a+iB a+iC*a+iC*a+iD&a+i D&a+i 2.2.对于两个函数对于两个函数对于两个函数对于两个函数,若函数名相同若函数名相同若函数名相同若函数名相同,但只是但只是但只是但只是_不一不一不一不一样则不是重载函数样则不是重载函数样则不是重载函数样则不是重载函数.A A 参数类型参数类型参数类型参数类型B B 参数个数参数个数参数个数参数个数C C 函数类型函数类型函数类型函数类型3.3.若需要利用形参直接访问实参若需要利用形参直接访问实参若需要利用形参直接访问实参若需要利用形参直接访问实参,则应把形参变量说明为则应把形参变量说明为则应把形参变量说明为则应把形参变量说明为_参数参数参数参数A A 指针指针指针指针B B 引用引用引用引用C C 值值值值第2页3 4.4.下面程序段时间复杂度为下面程序段时间复杂度为下面程序段时间复杂度为下面程序段时间复杂度为_._.forfor (intint i=0;i m;i+)i=0;i m;i+)for for(intint j=0;j n;j+)j=0;j n;j+)a i j =i*j;a i j =i*j;A O(mA O(m2 2)B O(nB O(n2 2)C O(m*n)C O(m*n)D O(m+n)D O(m+n)5.5.执行下面程序段时执行下面程序段时执行下面程序段时执行下面程序段时,执行执行执行执行S S语句次数为语句次数为语句次数为语句次数为_._.forfor (intint i=1;i=n;i+)i=1;i=n;i+)forfor (intint j=1;j=i;j+)j=1;j=i;j+)S;S;A nA n2 2B nB n2 2/2/2C n(n+1)C n(n+1)D n(n+1)/2D n(n+1)/2第3页46.6.下面算法时间复杂度为下面算法时间复杂度为下面算法时间复杂度为下面算法时间复杂度为B O(n).B O(n).intint f f (unsignedunsigned intint n n )if if(n=0|n=1(n=0|n=1 )returnreturn 1;1;elseelse returnreturn n*f(n-1);n*f(n-1);A O(1)A O(1)B O(n)B O(n)C O(nC O(n2 2)D O(n!)D O(n!)二、填空题二、填空题二、填空题二、填空题1.1.数据逻辑结构被分为数据逻辑结构被分为数据逻辑结构被分为数据逻辑结构被分为集合结构集合结构集合结构集合结构、线性结构线性结构线性结构线性结构、树型结构树型结构树型结构树型结构和和和和图形结构图形结构图形结构图形结构四种四种四种四种.2.2.数据存放结构被分为数据存放结构被分为数据存放结构被分为数据存放结构被分为次序次序次序次序、链接链接链接链接、索引索引索引索引和和和和散列散列散列散列四种四种四种四种;第4页53.3.在线性结构、树形结构和图形结构中在线性结构、树形结构和图形结构中在线性结构、树形结构和图形结构中在线性结构、树形结构和图形结构中,前驱和后继结点前驱和后继结点前驱和后继结点前驱和后继结点之间分别存在着之间分别存在着之间分别存在着之间分别存在着1:11:1、1:N1:N和和和和M:NM:N联络联络联络联络.4.4.一个抽象数据类型包含一个抽象数据类型包含一个抽象数据类型包含一个抽象数据类型包含数据定义数据定义数据定义数据定义和和和和操作操作操作操作两个部分两个部分两个部分两个部分.5.5.当一个形参类型长度较大时当一个形参类型长度较大时当一个形参类型长度较大时当一个形参类型长度较大时,应最好说明为应最好说明为应最好说明为应最好说明为引用引用引用引用,以节约以节约以节约以节约参数值传输时间和存放参数空间参数值传输时间和存放参数空间参数值传输时间和存放参数空间参数值传输时间和存放参数空间.6.6.当需要用一个形参访问对应实参时当需要用一个形参访问对应实参时当需要用一个形参访问对应实参时当需要用一个形参访问对应实参时,则该形参应说明为则该形参应说明为则该形参应说明为则该形参应说明为引用引用引用引用.7.7.在函数中对引用形参修改就是对对应在函数中对引用形参修改就是对对应在函数中对引用形参修改就是对对应在函数中对引用形参修改就是对对应实参实参实参实参修改修改修改修改,对对对对值或值或值或值或赋值赋值赋值赋值形参修改只局限在该函数内部形参修改只局限在该函数内部形参修改只局限在该函数内部形参修改只局限在该函数内部,不会反应到对应实不会反应到对应实不会反应到对应实不会反应到对应实参上参上参上参上.第5页68.8.当需要进行标准当需要进行标准当需要进行标准当需要进行标准I/OI/O操作时操作时操作时操作时,则应在程序文件中包含则应在程序文件中包含则应在程序文件中包含则应在程序文件中包含iostream.hiostream.h头文件头文件头文件头文件,当需要进行文件当需要进行文件当需要进行文件当需要进行文件I/OI/O操作时操作时操作时操作时,则应在程则应在程则应在程则应在程序文件中包含序文件中包含序文件中包含序文件中包含fstream.hfstream.h头文件头文件头文件头文件.9.9.在包含有在包含有在包含有在包含有stdlib.hstdlib.h头文件程序文件中头文件程序文件中头文件程序文件中头文件程序文件中,使用使用使用使用rand rand()()%2121能能能能够产生出够产生出够产生出够产生出020020之间一个随机整数之间一个随机整数之间一个随机整数之间一个随机整数.10.10.一个统计一个统计一个统计一个统计r r理论上占有存放空间大小等于全部域理论上占有存放空间大小等于全部域理论上占有存放空间大小等于全部域理论上占有存放空间大小等于全部域长度长度长度长度之和之和之和之和,实际上占有存放空间大小即统计长度为实际上占有存放空间大小即统计长度为实际上占有存放空间大小即统计长度为实际上占有存放空间大小即统计长度为sizeof(r)sizeof(r).11.11.一个数组一个数组一个数组一个数组a a所占有存放空间大小即数组长度为所占有存放空间大小即数组长度为所占有存放空间大小即数组长度为所占有存放空间大小即数组长度为sizeofsizeof(a)(a),下标为下标为下标为下标为i i元素元素元素元素a i a i 存放地址为存放地址为存放地址为存放地址为 a+ia+i,或者为或者为或者为或者为a+a+i i*sizeof sizeof(a(a i)i).第6页712.12.函数重载要求函数重载要求函数重载要求函数重载要求类型类型类型类型上上上上,数量数量数量数量上或上或上或上或排列次序排列次序排列次序排列次序上有所不一样上有所不一样上有所不一样上有所不一样.13.13.对于双目操作符对于双目操作符对于双目操作符对于双目操作符,其重载函数带有其重载函数带有其重载函数带有其重载函数带有两两两两参数参数参数参数,其中最少有其中最少有其中最少有其中最少有一个为一个为一个为一个为用户自定义用户自定义用户自定义用户自定义类型类型类型类型.14.14.若对象若对象若对象若对象rara和和和和rbrb中最少有一个是属于用户定义类型中最少有一个是属于用户定义类型中最少有一个是属于用户定义类型中最少有一个是属于用户定义类型,则执则执则执则执行行行行ra=rbra=rb时时时时,需要调用需要调用需要调用需要调用=重载函数重载函数重载函数重载函数,该函数第一个参数该函数第一个参数该函数第一个参数该函数第一个参数应与应与应与应与rara类型相同类型相同类型相同类型相同,第二个参数应与第二个参数应与第二个参数应与第二个参数应与rbrb类型相同类型相同类型相同类型相同.15.15.从一维数组从一维数组从一维数组从一维数组anan中次序查找出一个最大值元素时间复中次序查找出一个最大值元素时间复中次序查找出一个最大值元素时间复中次序查找出一个最大值元素时间复杂度为杂度为杂度为杂度为O(n)O(n),输出一个二维数组输出一个二维数组输出一个二维数组输出一个二维数组bmnbmn中全部元素值时中全部元素值时中全部元素值时中全部元素值时间复杂度为间复杂度为间复杂度为间复杂度为O(m*n)O(m*n).第7页816.16.在下面程序段中在下面程序段中在下面程序段中在下面程序段中,s=s+p,s=s+p语句执行次数为语句执行次数为语句执行次数为语句执行次数为_n_n_,p*=j,p*=j语句语句语句语句执行次数为执行次数为执行次数为执行次数为n(n+1)/2n(n+1)/2,该程序段时间复杂度为该程序段时间复杂度为该程序段时间复杂度为该程序段时间复杂度为O(nO(n2 2).intint i=0,s=0;i=0,s=0;whilewhile(+i=n)(+i=n)intint p=1;p=1;forfor (intint j=1;j=i;j+)p*=j;j=1;j=0)(x=0)r1=(r1=(floatfloat)(q.b+)(q.b+sqrt sqrt(x)/(2*q.a);(x)/(2*q.a);r2=(r2=(floatfloat)(q.b )(q.b sqrt sqrt(x)/(2*q.a);(x)/(2*q.a);returnreturn 1;1;elseelse returnreturn 0;0;第12页135)5)按照按照按照按照ax*2+bx+cax*2+bx+c格式（格式（格式（格式（x x2 2用用用用x*2x*2表示）输出二次多项表示）输出二次多项表示）输出二次多项表示）输出二次多项式式式式,在输出时要注意去掉系数为在输出时要注意去掉系数为在输出时要注意去掉系数为在输出时要注意去掉系数为0 0项项项项,而且当而且当而且当而且当b b和和和和c c值为负值为负值为负值为负时时时时,其前不能出现加号其前不能出现加号其前不能出现加号其前不能出现加号.voidvoid PrintPrint(QuadraticQuadratic q q)if if(q.a)(q.a)coutcout q.a x*2;q.a 0)(q.b 0)coutcout +q.b x;+q.b x;elseelse coutcout q.b x;q.b 0)(q.c 0)coutcout +q.c;+q.c;elseelse coutcout q.c ;q.c ;coutcout endlendl;第13页14 2.2.指出以下各算法功效并求出其时间复杂度指出以下各算法功效并求出其时间复杂度指出以下各算法功效并求出其时间复杂度指出以下各算法功效并求出其时间复杂度.1)1)intint Prime Prime(intint n)n)intint i=1;i=1;intint x=(x=(intint)sqrtsqrt(n);(n);whilewhile(+i=x)(+i x)(i x)returnreturn 1;1;elseelse returnreturn 0;0;判断判断判断判断n n是否是一个素数是否是一个素数是否是一个素数是否是一个素数,若是则返回若是则返回若是则返回若是则返回1,1,不然返回不然返回不然返回不然返回0,0,时间时间时间时间复杂度为复杂度为复杂度为复杂度为第14页152)int sum1(int n)int p=1,s=0;for(int i=1;i=n;i+)p*=i;s+=p;return s;计算计算:时间复杂度为时间复杂度为O(n)第15页163)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;第16页174)4)int fun(int n)int i=1,s=1;while(s=n1+2+3+.+i=n最小最小最小最小i i值值值值,时间复杂度时间复杂度时间复杂度时间复杂度为为为为O(O(sqrt sqrt(n)(n)第17页185)5)void UseFile(ifstream&inp,int c10)/假定假定假定假定inpinp所对应文件中保留有所对应文件中保留有所对应文件中保留有所对应文件中保留有n n个整数个整数个整数个整数.for(int i=0;i x)i=x%10;c i+;利用数组利用数组利用数组利用数组C C中每个元素对应统计中每个元素对应统计中每个元素对应统计中每个元素对应统计inpinp所联络整数文所联络整数文所联络整数文所联络整数文件中个位数值同为件中个位数值同为件中个位数值同为件中个位数值同为i i整数个数整数个数整数个数整数个数时间复杂度时间复杂度时间复杂度时间复杂度O(n)O(n)第18页196)6)voidvoid mtable mtable(intint n)n)forfor (intint i=1;i=n;i+)i=1;i=n;i+)forfor (intint j=i;j=n;j+)j=i;j=n;j+)cout cout i *j =i *j =setwsetw(2)i*j ;(2)i*j ;coutcout endl endl;打印出一个含有打印出一个含有打印出一个含有打印出一个含有n n行乘法表行乘法表行乘法表行乘法表,第第第第i i行中有行中有行中有行中有n-i+1n-i+1个乘法个乘法个乘法个乘法项项项项,每个乘法项为每个乘法项为每个乘法项为每个乘法项为i*j;i*j;时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(nO(n2 2)第19页207)7)void cmatrix(int aMN,int d)/M/M和和和和N N为全局整型常量为全局整型常量为全局整型常量为全局整型常量 for(int i=0;i M;i+)for(int j=0;j N;j+)a i j *=d;数组数组数组数组a a中每个元素均乘以中每个元素均乘以中每个元素均乘以中每个元素均乘以d d值值值值,时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(nO(n2 2)第20页218)8)voidvoid matrimult matrimult(intint aMN,aMN,intint bNL,bNL,intint cML)cML)/M,N/M,N和和和和L L均为全局整型常量均为全局整型常量均为全局整型常量均为全局整型常量int int i,j,k;i,j,k;forfor (i=0;i M;i+)(i=0;i M;i+)forfor(j=0;j L;j+)(j=0;j L;j+)c i j =0;c i j =0;forfor(i=0;i M;i+)(i=0;i M;i+)for for(j=0;j L;j+)(j=0;j L;j+)forfor(k=0;k N;k+)(k=0;k N;k+)c i j +=a i k *bk j;c i j +=a i k *bk j;矩阵相乘矩阵相乘矩阵相乘矩阵相乘,即即即即aMN*bMNcML aMN*bMNcML 时间复杂时间复杂时间复杂时间复杂度为度为度为度为O(M*N*L)O(M*N*L)第21页22 一、在下面每个程序段中一、在下面每个程序段中一、在下面每个程序段中一、在下面每个程序段中,假定线性表假定线性表假定线性表假定线性表LaLa类型为类型为类型为类型为ListList,元素元素元素元素类型类型类型类型ElemTypeElemType为为为为intint,并假定每个程序段是连续执行并假定每个程序段是连续执行并假定每个程序段是连续执行并假定每个程序段是连续执行,试试试试写出每个程序段执行后所得到线性表写出每个程序段执行后所得到线性表写出每个程序段执行后所得到线性表写出每个程序段执行后所得到线性表La.La.(1)(1)InitList InitList(LaLa););intint a =48,26,57,34,62,79 ;a =48,26,57,34,62,79 ;forfor (i=0;i 6;i+)(i=0;i 6;i+)InsertFront InsertFront(La,a i);(La,a i);TraverseList TraverseList(La);/(La);/(79,62,34,57,26,48)(79,62,34,57,26,48)(2)(2)InitList InitList(La);(La);forfor (i=0;i 6;i+)(i=0;i 6;i+)Insert Insert(La,a i );(La,a i );TraverseList TraverseList(La);/(La);/(26,34,48,57,62,79)(26,34,48,57,62,79)第22页23(3)(3)InsertInsert(La,56);(La,56);DeleteFrontDeleteFront(La);(La);InsertRearInsertRear(La,(La,DeleteFrontDeleteFront(La);(La);TraverseListTraverseList(La);(La);(48,56,57,62,79,34)(48,56,57,62,79,34)(4)(4)forfor (i=1;i=3;i+)(i=1;i=3;i+)intint x=x=GetElemGetElem(La,i);(La,i);if if(x%2=0)(x%2=0)DeleteDelete(La,x);(La,x);TraverseList TraverseList(La);(La);(56,57,79,34)(56,57,79,34)第23页24(5)(5)ClearList ClearList(La);(La);forfor (i=0;i 6;i+)(i=0;i 6;i+)InsertRear InsertRear(La,a i );(La,a i );Delete Delete(La,a 5 );(La,a 5 );Sort Sort(La);(La);Insert Insert(La,a5/2);(La,a5/2);TraverseList TraverseList(La);(La);(26,34,39,48,57,62)(26,34,39,48,57,62)第24页25二、对于二、对于二、对于二、对于ListList类型线性表类型线性表类型线性表类型线性表,编写出以下每个算法编写出以下每个算法编写出以下每个算法编写出以下每个算法.1)1)从线性表中删除含有最小值元素并由函数返回从线性表中删除含有最小值元素并由函数返回从线性表中删除含有最小值元素并由函数返回从线性表中删除含有最小值元素并由函数返回,空出位置由最终一空出位置由最终一空出位置由最终一空出位置由最终一个元素填补个元素填补个元素填补个元素填补,若线性表为空则显示犯错信息并退出运行若线性表为空则显示犯错信息并退出运行若线性表为空则显示犯错信息并退出运行若线性表为空则显示犯错信息并退出运行;ElemtypeElemtype DelMaxValue DelMaxValue(ListList&L)&L)if if(ListEmpty ListEmpty(L)(L)cerrcerr List is Empty!List is Empty!endlendl;exitexit(1);(1);ElemTypeElemType x =L.list 0 ;x =L.list 0 ;intint k=0;k=0;forfor(intint i=1;i L.i=1;i L.Size Size;i+);i+)ElemTypeElemType y=L.y=L.list list i ;i ;if if(y x)x=y ;k=i;(y x)x=y ;k=i;L.list k =L.list L.L.list k =L.list L.SizeSize-1;-1;L.L.SizeSize -;returnreturn x;x;第25页26(2)(2)从线性表中删除第从线性表中删除第从线性表中删除第从线性表中删除第i i个元素并由函数返回个元素并由函数返回个元素并由函数返回个元素并由函数返回.intint Delete Delete(ListList&L,&L,intint i)i)if if(i L.(i L.SizeSize)cerr cerr Index is outof range!Index is outof range!endlendl ;exitexit(1);(1);ElemTypeElemType x;x;x=L.list i 1;x=L.list i 1;forfor(intint j=i 1;j L.j=i 1;j L.SizeSize-1;j+)1;j+)L.list j =L.list j+1;L.list j =L.list j+1;L.Size-;L.Size-;returnreturn x;x;第26页27(3)(3)向线性表中第向线性表中第向线性表中第向线性表中第i i个元素位置插入一个元素个元素位置插入一个元素个元素位置插入一个元素个元素位置插入一个元素.voidvoid Insert Insert(ListList&L,&L,intint i,i,ElemTypeElemType x)x)if if (i L.(i L.SizeSize+1)+1)cerr cerr Index is outof range!Index is outof range!endlendl;exit exit(1);(1);if if (L.(L.SizeSize=MaxSize MaxSize)cerr cerr List overflow!List overflow!=i;j1;j=i;j-)L.L.listlist j+1 =L.j+1 =L.list list j ;j ;L.L.list list i i-1=x;1=x;L.L.SizeSize+;+;第27页28(4)(4)从线性表中删除含有给定值从线性表中删除含有给定值从线性表中删除含有给定值从线性表中删除含有给定值x x全部元素全部元素全部元素全部元素.voidvoid delete2 delete2(L Li ist st&L,&L,ElemTypeElemType x)x)intint i=0;i=0;whilewhile(i L.(i L.SizeSize)if if(L.list i =x)(L.list i =x)forfor (intint j=i+1;j L.j=i+1;j L.Size Size;j+);j+)L.list jL.list j-1=L.list j ;1=L.list j ;L.L.SizeSize -;elseelse i+;i+;第28页294.4.对于结点类型为对于结点类型为对于结点类型为对于结点类型为LNodeLNode单链表单链表单链表单链表,编写出以下每个算法编写出以下每个算法编写出以下每个算法编写出以下每个算法;(1)(1)将一个单链表按逆序链接将一个单链表按逆序链接将一个单链表按逆序链接将一个单链表按逆序链接,即若原单链表中存放元素次即若原单链表中存放元素次即若原单链表中存放元素次即若原单链表中存放元素次序为序为序为序为a a1 1,a,a2 2,.a,.an n,则逆序链接后变为则逆序链接后变为则逆序链接后变为则逆序链接后变为a an n,a,an-1 n-1,.a,.a 1 1.voidvoid Contrary Contrary(LNodeLNode *&*&HLHL)LNodeLNode *p=HL;*p=HL;HL=NULL;HL=NULL;whilewhile(p!=NULL)(p!=NULL)LNodeLNode*q=p;*q=p;p=pp=pnextnext;qqnextnext=HL;=HL;HL=q;HL=q;第29页30(2)(2)删除单链表中第删除单链表中第删除单链表中第删除单链表中第i i个结点个结点个结点个结点.voidvoid Delete1Delete1(LNodeLNode*&HL,*&HL,intint i)i)if if(i 1|HL=NULL)(i 1|HL=NULL)cerrcerrIndex is outof range!Index is outof range!endl endl;exitexit(1);(1);LNodeLNode*p,*q;*p,*q;p=NULL;q=HL;p=NULL;q=HL;whilewhile(q!=NULL)(q!=NULL)if if(j=i)(j=i)breakbreak;elseelse p=q;p=q;q=qq=qnextnext;j+;j+;第30页31if if(q=NULL)(q=NULL)cerrcerrIndex is outof range!Index is outof range!endlendl;exit exit(1);(1);if if(p=NULL)(p=NULL)HL=HL HL=HLnextnext;elseelse p pnextnext=q=qnextnext;deletedelete q;q;第31页32(3)(3)从单链表中查找出全部元素最大值从单链表中查找出全部元素最大值从单链表中查找出全部元素最大值从单链表中查找出全部元素最大值,该值由函数返回该值由函数返回该值由函数返回该值由函数返回,若单链表为空若单链表为空若单链表为空若单链表为空,则显示犯错信息并停顿运行则显示犯错信息并停顿运行则显示犯错信息并停顿运行则显示犯错信息并停顿运行.ElemTypeElemType MaxValueMaxValue(LNodeLNode *HL)*HL)if if(HL=NULL)(HL=NULL)cerr cerr Linked list is empty!Linked list is empty!endlendl;exit exit(1);(1);ElemTypeElemType max=HL max=HLdatadata;LNodeLNode *p=HL *p=HLnextnext;whilewhile(p!=NULL)(p!=NULL)if if(max p(max pdatadata)max=p)max=pdatadata;p=pp=pnextnext;returnreturn max;max;第32页33(4)(4)统计出单链表中结点值等于给定值统计出单链表中结点值等于给定值统计出单链表中结点值等于给定值统计出单链表中结点值等于给定值x x结点数结点数结点数结点数.intint CountCount(LNodeLNode *HL,*HL,ElemTypeElemType x)x)intint j=0;j=0;whilewhile(HL!=NULL)(HL!=NULL)if if(HL(HLdatadata=x)j+;=x)j+;HL=HLHL=HLnextnext;returnreturn j j;第33页