数据结构第1章-答案.doc

01、数据结构是一门研究非数值计算的程序设计问题中计算机的(操作对象)以及它们之间的(关系和运算)等的学科。02、数据结构被形式地定义为(D,R),其中D是(数据元素)的有限集合,R是D上的(关系)有限集合。03、数据结构包括数据的(逻辑结构)、数据的(存储结构)和数据的(运算)这三个方面的内容。04、数据结构按逻辑结构可分为两大类,它们分别是(线性结构)和(非线性结构)。05、线性结构中元素之间存在(一对一)关系,树形结构中元素之间存在(一对多)关系,图形结构中元素之间存在(多对多)关系。06、在线性结构中,第一个结点(没有)前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点(没有)后续结点,其余每个结点有且只有1个后续结点。07、在树形结构中,树根结点没有(前驱)结点,其余每个结点有且只有(1)个前驱结点;叶子结点没有(后续)结点,其余每个结点的后续结点数可以(任意多个)。08、在图形结构中,每个结点的前驱结点数和后续结点数可以(任意多个)。09、数据的存储结构可用四种基本的存储方法表示,它们分别是(顺序)、(链式)、(索引)、(散列)。10、对于给定的n个元素,可以构造出的逻辑结构有(集合)、(线性结构)、(树形结构)、(图状结构)四种。11、数据的运算最常用的有5种,它们分别是(插入)、(删除)、(修改)、(查找)、(排序)。12、一个算法的效率可分为(时间)效率和(空间)效率。13、数据结构中评价算法的两个重要指标是算法的(时间复杂度)和(空间复杂度)。14、一个数据结构在计算机中的(映射)称为存储结构。15、算法的五个重要特性是(有穷性)、(确定性)、(可行性)、输入、输出。16、已知如下程序段for(i=n;i>=1;i--)//语句1{x++;//语句2for(j=n;j>=i;j--)//语句3y++;//语句4}语句1执行的频度为(n+1);语句2执行的频度为(n);语句3执行的频度为(n(n+3)/2);语句4执行的频度为(n(n+1)/2)。17、在下面的程序段中,对x的赋值语句的频度为(n(n+1)(n+2)/6)。for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x+=y;解释:1+(1+2++(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6O(n3)18、下面程序段中带下划线的语句的执行次数的数量级是(O())i=1;while(i<n)i=i*2;19、下面程序段中带下划线的语句的执行次数的数量级是(O(n))。i=1;while(i<n){for(j=1;j<=n;j++){x=x+1;i=i*2;}}20、下面程序段中带有下划线的语句的执行次数的数量级是(O())。i=n*n;while(i!=1)i=i/2;21、计算机执行下面的语句时,“语句s”的执行次数为((n+3)(n-2)/2)。for(i=1;i<n-1;i++)for(j=n;j>=i;j--)语句s;22、在有n个选手参加的单循环赛中,总共将进行(n(n-1)/2)场比赛。二、判断题×01、数据元素是数据的最小单位。×02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。×03、算法的优劣与算法描述语言无关,但与所用计算机有关。√04、健壮的算法不会因非法的输入数据而出现莫