发布时间 : 星期一 文章数据结构c语言版试题大全（含答案）更新完毕开始阅读13adb34dc850ad02de804116
_______。
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 - s=s+p;} 29、一个算法的时间复杂度为（3*n*n+2nlog2n+4n-7)/(5n)，其数量级表示为____________。 30、从一个数组a[10]中顺序查找元素时，假定查找每个元素的概率都相同，则进行一次查找运算时的平均查找长度（即同元素的平均比较次数）为____________。 31、从一个数组a[7]中顺序查找元素时，假定查找第1个元素a[0]的概率为1/3，查找第2个元素a[1]的概率为1/4，其找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为____________。 32、对于一个n*n的矩阵Ａ的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是 ____________。设两种存储时的开始存储地址均为ＬＯＣ(0,0)，每个元素所占存储单元数均为d。 33、设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________ 34、设有一个二维数组A[10][20]，按列为主序存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________。 37、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫____________，另一个叫____________域。 数据结构复习题答案：绪论 填空题 1、映射 2、线性结构|树形结构|图形结构|非线性结构 3、没有|1|没有|1 4、前驱|1|后续|任意多个 5、任意多个 6、一对一|一对多|多对多 7、有穷性|确定性|可行性 8、错误 9、正确 10、O(n*m) 11、O(√n) 12、O(n2) 13、O(log3n) 14、O(n) 15、O(√n)|O(n)|O(n2) 16、数据元素之间的逻辑关系 17、映像?表示?映像或表示 18、相邻的结点|相邻的存储单元|附加的指针字段表示 19、存储结构?物理结构|逻辑结构|运算|算法 20、可行性|有穷性|确定性 21、问题规模 22、存储结构、物理结构 23、集合结构、线性结构、树形结构、图形结构（次序无先后） 24、顺序结构、链接结构、索引结构、散列结构（次序无先后） 25、1:1|1:N|M:N 26、数据|操作 27、O(n) | O(m*n) - 11 - 28、n| n(n+1)/2 29、O(n) 30、5.5 31、35/12 32、(i-j)*(n-1)*d 33、322 34、226 37、值|指针 数据结构复习题：绪论 问答题 1、当你为解决某一问题而选择数据结构时,应从哪些方面考虑? 2、简述逻辑结构与存储结构的关系. 3、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的. 数据结构复习题答案：绪论 问答题 1、解答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点： （1）程序运行时所需输入的数据总量。 （2）计算机执行每条指令所需的时间。 （3）程序中指令重复执行的次数。 2、答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。 3、答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。 - 12 -