数据结构复习题：绪论 判断题
1、数据元素是数据的最小单位。 2、数据项是数据的基本单位。 3、数据元素是数据的最小单位
4、数据对象就是一组任意数据元素的集合
5、任何数据结构都具备3个基本运算: 插入、删除和查找. 6、数据是由一些类型相同的数据元素构成的
7、数据是逻辑结构与各数据元素在计算机中如何存储有关 8、如果数据元素值发生改变,则数据的逻辑结构也随之改变. 9、逻辑结构相同的数据,可以采用多种不同的存储方法. 10、逻辑结构相同的数据,结点类型也一定相同
11、逻辑结构不相同的数据,必须采用不同的存储方式来存储 12、数据的逻辑结构是指数据的各数据项之间的逻辑关系.
13、算法的优劣与算法描述语言有无关，但与所有计算机有关。
14、算法可以用不同的语言描述，如果用C或Pascal等高级语言来描述，则算法实际上就是程序了。 15、程序一定是算法。
16、算法最终必须由计算机程序实现。
19、健壮的算法不会因非法入输数据而出现莫名其妙的执行结果。
数据结构复习题答案：绪论 判断题 1、False 2、False 3、False 4、False 5、False 6、True 7、False 8、False 9、True 10、False 11、False 12、False 13、False 14、False 15、False 16、False 19、True
- 6 -
数据结构复习题：绪论 算法分析题
1、求两个n阶矩形的乘法C=A*B,其算法如下: #define MAX 100
void maxtrixmult(int ,float a[MAX][MAX],b[MAX][MAX],float c[MAX][MAX]) {
int i,j,k; float x;
for(i=1;i<=n;i++) //① {
for (j=1;j<=n;j++) //② {
x=0; //③ for(k=1;k<=n;k++) //④ x+=a[i][k]*b[k][j]; //⑤ c[i][j]=x; //⑥ } } }
计算①～⑥各语句的频度,并分析该算法的时间复杂度。
2、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m=0;
for(i=1;i<=n;i++)
for(j=2*1;j<=n;j++) m++;
3、阅读下列算法: void suan_fa(int n) {
int i,j,k,s,x;
for (s=0,i=0;i i++; j--; x+=2; } pirntf(\} (1) 分析算法中语句\的执行次数; (2) 分析算法中语句\的执行次数; - 7 - (3) 分析该算法的时间复杂度; (4) 假定n=5, 试指出执行该算法的输出结果。 6、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 int m=0,i,j; for (i=1;i<=n;i++) for (j=2*i;j<=n;j++) m++; 数据结构复习题答案：绪论 算法分析题 1、答： 语句 频度 for(i=1;i<=n;i++) //① ?? n+1 { for (j=1;j<=n;j++) //② ?? n(n+1) {x=0; //③ ?? n2 for(k=1;k<=n;k++) //④ ?? n2(n+1) x+=a[i][k]*b[k][j]; //⑤ ?? n3 c[i][j]=x; //⑥ ?? n2 所以：f(n)n+1+ n(n+1)+ n2+ n2(n+1)+ n3+ n2=2n3+4n2+2n+1=O( n3 ) 2、答：m+n(n-1) O(n2) 3、分析算法中语句”s++;”的执行次数：n+（n-1）+(n-2)+?+1=n(n+1)/2 分析算法中语句”x+=2;”的执行次数: n/2 分析该算法的时间复杂度: O(n2) 假定n=5，试指出执行该算法的输出结果: s=15, x=4 6、 数据结构复习题：绪论 填空题 1、一个数据结构在计算机中______称为存储结构。 2、数据逻辑结构包括________，_________和________三种类型，树形结构和图形结构合称为________。 3、在线性结构中，第一个结点________前驱结点，其余每个结点有且只有_______个前驱结点：最后一个结点______后续结点，其余每个结点有且只有______个后续结点。 4、在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点:叶子结点没有______结点,其余每个结点后的后续结点可以_______ 5、在图形结构中，每个结点的前驱结点数和后续结点数可以________。 6、线性结构中元素之间存在_________关系，树形结构中元素之间存在_______关系，图形结构中元素之间存在________关系。 7、算法的5个重要特性是_________、__________、__________、输入和输出。 8、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是________。 9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言是 - 8 - _______。 10、下面程序段的时间复杂度是_______。 for (i=0;i 11、下面程序段的时间复杂度是_______。 i=s=0; while(s i++; s+=i; } 12、下面程序段的时间复杂度是_______。 s=0; for (i=0;i for (j=0;j 13、下面程序段的时间复杂度是________。 i=1; while(i<=n) i=i*3; 14、有如下递归函数fact(n),分析其时间复杂度。int fact(int n) { if (n<=1) return 1; else return (n*fact(n-1)); } 15、指出下列各算法的时间复杂度 (1) prime(int n) { int i=2; while(n%i!=0 && i if (i*1.0>sqrt(n)) printf \是一素数\ else printf \不是一素数\} (2) sum1(int n) - 9 - { int p=1,sum=0,i; for (i=1;i<=n;i++) { p*=i; sum+=p; } returm (sum); } (3) sum2(int n) { int sum=0,i,j; for (i=1;i<=n;i++) { p=1; for (j=1;j<=i;j++) p*=j; sum+=p; } return (sum); } 16、数据的逻辑结构是指_____. 17、一个数据结构在计算机中的______称为存储结构. 18、顺序存储方法是把逻辑上_____存储在物理位置上______里;链式存储方法中结点间的逻辑关系是由_____的. 19、数据结构是指研究数据的_____和_____以及它们之间的相互关系,并对这种结构定义相应的_____,设计出相应的_____,从而确保经过这些运算后所得到的新结构是原来的结构类型. 20、一个算法具有5个特性:_____、_____、_____、输入和输出。 21、算法的执行时间是_____的函数。 22、数据的逻辑结构是从逻辑上描述数据,它与数据的______无关,是独立于计算机的. 23、数据的逻辑结构被分为____________、____________、____________和____________４种。 24、数据的存储结构被分为____________、____________、____________和____________４种。 25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着____________、____________、____________的联系。 26、一种抽象数据类型包括____________和____________两个部分。 27、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为____________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为____________ 28、在下面程序段中，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; - 10 -