数据结构第二 主编殷人昆课后答案PPT课件

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语句的次数为

2、_. for ( int i = 1 ; i = n ; i+ ) for ( int j = 1 ; j= 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、3页/共33页3. 在线性结构、树形结构和图形结构中,前驱和后继结点之间分别存在着1:1、1:N和M:N的联系.4. 一种抽象数据类型包括数据定义和操作两个部分.5. 当一个形参类型的长度较大时,应最好说明为引用,以节省参数值的传输时间和存储参数的空间.6. 当需要用一个形参访问对应的实参时,则该形参应说明为引用.7. 在函数中对引用形参的修改就是对相应实参的修改,对值或赋值形参的修改只局限在该函数的内部,不会反映到对应的实参上.第4页/共33页8. 当需要进行标准I/O操作时,则应在程序文件中包含iostream.h头文件,当需要进行文件I/O操作时,则应在程序文件中包含fstream.h头

4、文件.9. 在包含有stdlib.h头文件的程序文件中,使用rand ( )%21能够产生出020之间的一个随机整数.10. 一个记录r理论上占有的存储空间的大小等于所有域的长度之和,实际上占有的存储空间的大小即记录长度为sizeof (r).11. 一个数组a所占有的存储空间的大小即数组长度为sizeof (a) ,下标为i的元素a i 的存储地址为 a+ i, 或者为a + i*sizeof (a i ).第5页/共33页12. 函数重载要求类型上,数量上或排列次序上有所不同.13. 对于双目操作符,其重载函数带有两参数,其中至少有一个为用户自定义的类型.14. 若对象ra和rb中至少有一

5、个是属于用户定义的类型,则执行ra=rb时,需要调用=重载函数,该函数的第一个参数应与ra的类型相同,第二个参数应与rb的类型相同.15. 从一维数组an中顺序查找出一个最大值元素的时间复杂度为O(n),输出一个二维数组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 + s

6、qrt (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的值为负时,其前不能出现加号.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 ;

7、第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, 时间复杂度为)( nO第13页/共33页2) int sum1 ( int n ) int p = 1, s = 0 ; for ( int i = 1; i = n ; i+ ) p *= i ; s += p ; return s ; 计算: 时间复杂度为O(n)第1

8、4页/共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个整数.

9、 for ( int i = 0 ; i x ) i = 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 cmat

10、rix ( int aMN, int d) /M和N为全局整型常量 for ( int i = 0; i M; i+) for ( int j = 0; j N; j+) a i 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

11、; 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,并假定每个程序段是连续执行的,试写出每个程序段执行后所得到的线性表La. (1) InitList (La); int a = 48, 26, 57, 34, 62 ,79 ; for ( i = 0 ; i 6 ; i+ ) InsertFront ( La , a i ) ; TraverseList

12、 ( 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 ( La ) ) ; TraverseList ( La ) ;(48,56,57,62,79,34)(4) for ( i = 1; i = 3;

13、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类型的

14、线性表,编写出下列每个算法.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

15、 k = L . list L.Size -1 ;L . Size -;return x ;第24页/共33页 (2) 从线性表中删除第i个元素并由函数返回.int 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)

16、向线性表中第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 = MaxSize ) 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, ElemTy

17、pe 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) 将一个单链表按逆序链接,即若原单链表中存储元素的次序为a1, a2, .an ,则逆序链接后变为an, an-1 ,.a 1.void Contrary (LNode *& HL) LNode *p = HL ;HL

18、= 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+ ;第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 ;