(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++; m=n*n/4 O() 数据结构复习题：绪论 填空题
1、一个数据结构在计算机中___映像___称为存储结构。
2、数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为________。 3、在线性结构中，第一个结点________前驱结点，其余每个结点有且只有_______个前驱结点：最后一个结点______后续结点，其余每个结点有且只有______个后续结点。 4、在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点:叶子结点没有______结点,其余每个结点后的后续结点可以_______
5、在图形结构中，每个结点的前驱结点数和后续结点数可以___任意多个_____。
6、线性结构中元素之间存在___一对一______关系，树形结构中元素之间存在___一对多____关系，图形结构中元素之间存在____多对多____关系。
7、算法的5个重要特性是_________、__________、__________、输入和输出。 8、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是________。
9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言是_______。
10、下面程序段的时间复杂度是_______。
for (i=0;i 11、下面程序段的时间复杂度是__O(sqrt(n))_____。 i=s=0; while(s i++; s+=i; } 12、下面程序段的时间复杂度是_______。 s=0; for (i=0;i for (j=0;j 13、下面程序段的时间复杂度是___O(log3n)_____。 i=1; - 6 - 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 \不是一素数\} O(sqrt(n)) (2) sum1(int n) { 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、数据的逻辑结构是指_____. - 7 - 17、一个数据结构在计算机中的_表示_____称为存储结构. 18、顺序存储方法是把逻辑上__相邻的结点___存储在物理位置上___相邻的存储单元___里;链式存储方法中结点间的逻辑关系是由 附加的指针字段表示____的. 19、数据结构是指研究数据的__存储结构___和__逻辑结构___以及它们之间的相互关系,并对这种结构定义相应的__运算___,设计出相应的__算法___,从而确保经过这些运算后所得到的新结构是原来的结构类型. 20、一个算法具有5个特性:_____、_____、_____、输入和输出。 21、算法的执行时间是_____的函数。 22、数据的逻辑结构是从逻辑上描述数据,它与数据的___存储结构、物理结构___无关,是独立于计算机的. 23、数据的逻辑结构被分为____________、____________、___________和____________４种。 24、数据的存储结构被分为____________、____________、____________和____________４种。 25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着____1:1________、____1：N________、_____M:N_______的联系。 26、一种抽象数据类型包括______数据______和____操作_______两个部分。 27、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为____________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为____________ 28、在下面程序段中，s=s+p语句的执行次数为______n______，p*=j语句的执行次数为______n*(n+1)/2______，该程序段的时间复杂度为______O(n*n)______。 int i=0,s=0; while(++i<=n) { int p=1; for(int j=1;j<=i;j++) p*=j; s=s+p;} 29、一个算法的时间复杂度为（3*n*n+2nlog2n+4n-7)/(5n)，其数量级表示为_____O(n)_______。 30、从一个数组a[10]中顺序查找元素时，假定查找每个元素的概率都相同，则进行一次查找运算时的平均查找长度（即同元素的平均比较次数）为____________。 31、从一个数组a[7]中顺序查找元素时，假定查找第1个元素a[0]的概率为1/3，查找第2个元素a[1]的概率为1/4，其找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为____35/12________。 32、对于一个n*n的矩阵Ａ的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是 ____(i-j)*(n-1)*d______。设两种存储时的开始存储地址均为ＬＯＣ(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、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的. - 8 - 数据结构复习题答案：绪论 问答题 1、解答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点： （1）程序运行时所需输入的数据总量。 （2）计算机执行每条指令所需的时间。 （3）程序中指令重复执行的次数。 2、答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。 3、答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。 2 线性表 沈阳理工大学应用技术学院 信息与控制学院 计算机科学与技术教研室 2011-5-8 - 9 - - 10 -
