数据结构学习复习模板计划练习题与参考标准答案.doc

数据结构练习题 第一部分 绪 论 一、单选题 一个数组元素 a[i] 与________的表示等价。 A 、 *(a+i) B 、 a+i C 、 *a+i D 、 a+i 对于两个函数，若函数名相同，但只是____________ 不同则不是重载函数。 A 、 参数类型 B 、 参数个数 C 、 函数类型 3. 若需要利用形参直接访问实参，则应把形参变量说明为 ________参数 A 、 指针 B 、 引用 C 、 值 下面程序段的时间复杂度为 ____________。 for(int i=0; im; i++) for(int j=0; jn; j++) a[i][j]=i*j; 2 2 、 O(m*n)D 、 O(m+n) A、 O(m )B 、 O(n )C 执行下面程序段时，执行 S 语句的次数为 ____________ 。 for(int i=1; i=n; i++) for(int j=1; j=i; j++) S; A 、 n 2 B 、 n 2/2 C 、 n(n+1) D 、 n(n+1)/2 下面算法的时间复杂度为 ____________。 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 2 D 、 O(n!) 、 O(n ) 二、填空题 数据的逻辑结构被分为 __________ 、 _________、__________ 和 __________ 四种。 数据的存储结构被分为 __________ 、 _________、__________ 和 __________ 四种。 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、 ________和________的联系。 一种抽象数据类型包括 __________ 和 __________两个部分。 当一个形参类型的长度较大时，应最好说明为 _________，以节省参数值的传输时间和存储参数的空间。 6. 当需要用一个形参访问对应的实参时，则该形参应说明为 __________。 在函数中对引用形参的修改就是对相应 __________ 的修改，对 __________ 形参的修改只局限在该函数的内部，不会反映到对应的实参上。 当需要进行标准 I/O 操作时，则应在程序文件中包含 ________________ 头文件，当需要进行文件 I/O 操作时，则应在程序文件中包含 ________________ 头文件。 在包含有 ________________ 头文件的程序文件中，使用 ________________ 能够产生 0～ 20 之间的一个随机整数。 10. 一个数组 a 所占有的存储空间的大小即数组长度为 ____________，下标为 i 的元素 a[i] 的存储地址为 __________，或者为 ______________________________ 。 函数重载要求 ____________ 、____________ 或 ____________有所不同。 对于 双 目操 作符 ， 其重 载 函数 带有 __________ 个 参数 ，其 中 至少 有 一个 为 ____________的类型。 13. 若对象 ra 和 rb 中至少有一个是属于用户定义的类型，则执行 ra==rb 时，需要调 用__________ 重载函数， 该函数的第一个参数应与 __________的类型相同， 第二个参数应与 __________的类型相同。 14. 从一维数组 a[n] 中顺序查找出一个最大值元素的时间复杂度为 个二维数组 b[m][n] 中所有元素值的时间复杂度为 ________。  ________，输出一 在下面程序段中， s=s+p 语句的执行次数为 ________， p*=j 语句的执行次数为 ________，该程序段的时间复杂度为 ________。 int i=0,s=0; while(++i=n) { int p=1; for(int j=1;j=i;j++) p*=j; s=s+p; } 一个算法的时间复杂度为 (3 n2+2nlog 2n+4n-7)/(5 n) ，其数量级表示为 ________。 第二部分 线性表 一、单选题 ．在一个长度为 n 的顺序存储线性表中， 向第 i 个元素 (1 ≤ i ≤ n+1) 之前插入一个新元 素时，需要从后向前依次后移 个元素。 A 、 n-i B 、 n-i+1 C 、 n-i-1 D 、