数据结构第二 主编殷人昆课后答案.pptx

《数据结构第二 主编殷人昆课后答案.pptx》由会员分享，可在线阅读，更多相关《数据结构第二 主编殷人昆课后答案.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、单选题1.一个数组元素ai与A*(a+i)的表示等价.A*(a+i)B a+iC*a+iD&a+i 2.对于两个函数,若函数名相同,但只是_不同则不是重载函数.A 参数类型 B 参数个数C 函数类型3.若需要利用形参直接访问实参,则应把形参变量说明为_参数A 指针B 引用C 值第1页/共33页 4.下面程序段的时间复杂度为_.for(int i=0;i m;i+)for(int j=0;j n;j+)a i j =i*j;A O(m2)B O(n2)C O(m*n)D O(m+n)5.执行下面程序段时,执行S语句的次数为_.for(int i=1;i=n;i+)for(int j=1;j=

2、i;j+)S;A n2B n2/2C n(n+1)D n(n+1)/2第2页/共33页6.下面算法的时间复杂度为B O(n).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页/共33页3.在线性结构、树形结构和图形结构中,前驱和后继结点之间分别存在着1:1、1:N和M:N的联系.4.一种抽象数据类型包括数据定义和操作两个部分.5.当

3、一个形参类型的长度较大时,应最好说明为引用,以节省参数值的传输时间和存储参数的空间.6.当需要用一个形参访问对应的实参时,则该形参应说明为引用.7.在函数中对引用形参的修改就是对相应实参的修改,对值或赋值形参的修改只局限在该函数的内部,不会反映到对应的实参上.第4页/共33页8.当需要进行标准I/O操作时,则应在程序文件中包含iostream.h头文件,当需要进行文件I/O操作时,则应在程序文件中包含fstream.h头文件.9.在包含有stdlib.h头文件的程序文件中,使用rand()%21能够产生出020之间的一个随机整数.10.一个记录r理论上占有的存储空间的大小等于所有域的长度之和,

4、实际上占有的存储空间的大小即记录长度为sizeof(r).11.一个数组a所占有的存储空间的大小即数组长度为sizeof(a),下标为i的元素a i 的存储地址为 a+i,或者为a+i*sizeof(a i).第5页/共33页12.函数重载要求类型上,数量上或排列次序上有所不同.13.对于双目操作符,其重载函数带有两参数,其中至少有一个为用户自定义的类型.14.若对象ra和rb中至少有一个是属于用户定义的类型,则执行ra=rb时,需要调用=重载函数,该函数的第一个参数应与ra的类型相同,第二个参数应与rb的类型相同.15.从一维数组an中顺序查找出一个最大值元素的时间复杂度为O(n),输出一个

5、二维数组bmn中所有元素值的时间复杂度为O(m*n).第6页/共33页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;第11页/共33页5)按照ax*2+bx+c的格式（x2用x*2表示）输出二次多项式,在输出时要注意去掉系数为0的项,并且当b和c的值

6、为负时,其前不能出现加号.void Print(Quadratic q)if(q.a)cout q.a 0)cout +q.b x;else cout q.b 0)cout +q.c;else cout q.c ;cout endl;第12页/共33页 2.指出下列各算法的功能并求出其时间复杂度.1)int Prime(int n)int i=1;int x=(int)sqrt(n);while(+i x)return 1;else return 0;判断n是否是一个素数,若是则返回1,否则返回0,时间复杂度为第13页/共33页2)int sum1(int n)int p=1,s=0;for(

7、int i=1;i=n;i+)p*=i;s+=p;return s;计算:时间复杂度为O(n)第14页/共33页3)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;第15页/共33页4)int fun(int n)int i=1,s=1;while(s=n的最小i值,时间复杂度为O(sqrt(n)第16页/共33页5)void UseFile(ifstream&inp,int c10)/假定inp所对应的文件中保存有n个整数.for(int i=0;i x)i=

8、x%10;c i+;利用数组C中的每个元素对应统计inp所联系的整数文件中个位数值同为i的整数个数时间复杂度O(n)第17页/共33页6)void mtable(int n)for(int i=1;i=n;i+)for(int j=i;j=n;j+)cout i *j =setw(2)i*j ;cout endl;打印出一个具有n行的乘法表,第i行中有n-i+1个乘法项,每个乘法项为i*j;时间复杂度为O(n2)第18页/共33页7)void cmatrix(int aMN,int d)/M和N为全局整型常量 for(int i=0;i M;i+)for(int j=0;j N;j+)a i

9、j *=d;数组a中每个元素均乘以d的值,时间复杂度为O(n2)第19页/共33页8)void matrimult(int aMN,int bNL,int cML)/M,N和L均为全局整型常量int i,j,k;for(i=0;i M;i+)for(j=0;j L;j+)c i j =0;for(i=0;i M;i+)for(j=0;j L;j+)for(k=0;k N;k+)c i j +=a i k *bk j;矩阵相乘,即aMN*bMNcML 时间复杂度为O(M*N*L)第20页/共33页 一、在下面的每个程序段中,假定线性表La的类型为List,元素类型ElemType为int,并假定

10、每个程序段是连续执行的,试写出每个程序段执行后所得到的线性表La.(1)InitList(La);int a =48,26,57,34,62,79 ;for(i=0;i 6;i+)InsertFront(La,a i);TraverseList(La);/(79,62,34,57,26,48)(2)InitList(La);for(i=0;i 6;i+)Insert(La,a i );TraverseList(La);/(26,34,48,57,62,79)第21页/共33页(3)Insert(La,56);DeleteFront(La);InsertRear(La,DeleteFront(L

11、a);TraverseList(La);(48,56,57,62,79,34)(4)for(i=1;i=3;i+)int x=GetElem(La,i);if(x%2=0)Delete(La,x);TraverseList(La);(56,57,79,34)第22页/共33页(5)ClearList(La);for(i=0;i 6;i+)InsertRear(La,a i );Delete(La,a 5 );Sort(La);Insert(La,a5/2);TraverseList(La);(26,34,39,48,57,62)第23页/共33页二、对于List类型的线性表,编写出下列每个算法

12、.1)从线性表中删除具有最小值的元素并由函数返回,空出的位置由最后一个元素填补,若线性表为空则显示出错信息并退出运行;Elemtype DelMaxValue(List&L)if(ListEmpty(L)cerr List is Empty!endl;exit(1);ElemType x =L.list 0 ;int k=0;for(int i=1;i L.Size;i+)ElemType y=L.list i ;if(y x)x=y ;k=i;L.list k =L.list L.Size-1;L.Size-;return x;第24页/共33页(2)从线性表中删除第i个元素并由函数返回.i

13、nt Delete(List&L,int i)if(i L.Size)cerr Index is outof range!endl;exit(1);ElemType x;x=L.list i 1;for(int j=i 1;j L.Size-1;j+)L.list j =L.list j+1;L.Size-;return x;第25页/共33页(3)向线性表中第i个元素位置插入一个元素.void Insert(List&L,int i,ElemType x)if(i L.Size+1)cerr Index is outof range!endl;exit(1);if(L.Size=MaxSiz

14、e)cerr List overflow!=i;j-)L.list j+1 =L.list j ;L.list i-1=x;L.Size+;第26页/共33页(4)从线性表中删除具有给定值x的所有元素.void delete2(List&L,ElemType x)int i=0;while(i L.Size)if(L.list i =x)for(int j=i+1;j L.Size;j+)L.list j-1=L.list j ;L.Size-;else i+;第27页/共33页4.对于结点类型为LNode的单链表,编写出下列每个算法;(1)将一个单链表按逆序链接,即若原单链表中存储元素的次序

15、为a1,a2,.an,则逆序链接后变为an,an-1,.a 1.void Contrary(LNode *&HL)LNode *p=HL;HL=NULL;while(p!=NULL)LNode*q=p;p=pnext;qnext=HL;HL=q;第28页/共33页(2)删除单链表中的第i个结点.void Delete1(LNode*&HL,int i)if(i 1|HL=NULL)cerrIndex is outof range!endl;exit(1);LNode*p,*q;p=NULL;q=HL;while(q!=NULL)if(j=i)break;else p=q;q=qnext;j+;

16、第29页/共33页if(q=NULL)cerrIndex is outof range!endl;exit(1);if(p=NULL)HL=HLnext;else pnext=qnext;delete q;第30页/共33页(3)从单链表中查找出所有元素的最大值,该值由函数返回,若单链表为空,则显示出错信息并停止运行.ElemType MaxValue(LNode *HL)if(HL=NULL)cerr Linked list is empty!endl;exit(1);ElemType max=HLdata;LNode *p=HLnext;while(p!=NULL)if(max pdata)max=pdata;p=pnext;return max;第31页/共33页(4)统计出单链表中结点的值等于给定值x的结点数.int Count(LNode *HL,ElemType x)int j=0;while(HL!=NULL)if(HLdata=x)j+;HL=HLnext;return j;第32页/共33页感谢您的观看。第33页/共33页