数据结构复习题-第1章答案2014-5-16

第1章绪论一、选择题（每小题2分，共20分）1.以下哪一个不是算法的特性（）。A.有穷性B.确定性C.简洁性D.可行性2.数据结构的定义为(D，S)，其中D是()的集合。A.算法B.数据元素C.数据操作D.逻辑结构3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（）。x=2；while(xn/2)x=2*x；A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)4.执行下面程序段时，执行Ｓ语句的次数为（）．for（inti=1；i=n；i++）for(intj=1；j=i；j++)S；A.n²B.n²/2C.n(n+1)D.n(n+1)/25.在下面的程序段中，对x的赋值语句的频度为（）。for(i=1；i=n;i++)for(j=1；j=n；j++)x=x+1;A.O(2n)B.O(n)C.O(n2)D.O(log2n)6.在数据结构的讨论中把数据结构从逻辑上分为（）。A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构。7.下面程序段的时间复杂度为（C）for(inti=0；im；i++)for(intj=0；jn；j++)a[i][j]=i*j；A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)8.算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度9.数据结构在计算机内存中的表示是指（）。A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系10.在数据结构中，与所使用的计算机无关的是数据的（）结构。A．逻辑B．存储C．逻辑和存储D．物理11.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法12.在决定选取何种存储结构时，一般不考虑（）。A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。13.算法分析的目的是（），算法分析的两个主要方面是（）。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性15.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等16.以下说法正确的是（）。A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构二、判断题（每小题1分，共10分）1.数据元素是数据的最小单位。（）2.算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。（）3.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）4.算法的优劣与算法描述语言无关，但与所用计算机有关。（）5.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。()6.在决定选取何种存储结构时，一般不考虑各结点的值如何。（）7.抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。()8.抽象数据类型与计算机内部表示和实现无关。（）9.顺序存储结构只能用于线性结构，不能用于非线性型结构。（）10.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）11.在数据结构的讨论中把数据结构从逻辑上分为内部结构与外部结构。（）12.数据项是数据的基本单位。（）三、填空题（每空1分，共10分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。2.根据数据元素之间的关系不同，通常有以下四种结构，、、和网状结构。3.数据的物理结构主要有_____________和______________两种不同的表示方法。4.数据元素之间的关系在计算机中有两种不同的表示方法：和5.算法的5个重要特性是_________、__________、__________、输入和输出。6.一个算法的效率可分为效率和效率。7.下面程序段的时间复杂度是。for(i=0；in；i++)for(j=0；jm；j++)A[i][j]=0；8.下面程序段的时间复杂度是_______。for(i=0；in；i++)for(j=0；jn；j++)s+=B[i][j]；9.数据结构中评价算法的两个重要指标是算法的__________和__________。10.计算机执行下面的语句时，语句s的执行次数为_______。FOR(i=l；in-l；i++)FOR(j=n；j=i；j--)s；11.数据结构是研讨数据的__________和__________，以及它们之间的相互关系，并对与这种结构定义相应的__________，设计出相应的__________。12.数据的物理结构包括_________的表示和_________的表示。13.一个算法具有5个特性:__________、__________、__________，有零个或多个输入、有一个或多个输出。14.抽象数据类型的定义仅取决于它的一组_________，而与_________无关，即不论其内部结构如何变化，只要它的__________不变，都不影响其外部使用。15.一个数据结构在计算机中_________称为存储结构。16.在有n个选手参加的单循环赛中，总共将进行______场比赛。17.对于给定的n个元素，可以构造出的逻辑结构有_______，_______，_______，______四种。18.数据的逻辑结构是指_________________________________________________________。参考题：20.下面程序段的时间复杂度为________。(n1)答案O(n)sum=1；for(i=0；sumn；i++)sum+=1；21.下面程序段的时间复杂度是（O(log3n)）。i＝0；while（i=n）i=i*3；22.设m,n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是该函数的程序段，请将未完成的部分填入，使之完整intf(m,n)intm,n;{if(m==1)return__(1)___;if(n==1){return__(2)___;}if(mn){returnf(m,m);}if(m==n){return1+__(3)___;}returnf(m.n-1)+f(m-n,___(4)___);}②执行程序，f(6,4)=_______。答案①(1)1(2)1(3)f(m,n-1)(4)n②923.下面程序段的时间复杂度为________。(n1)答案O(n)sum=1；for(i=0;sumn;i++)sum+=1;24.下面程序段中带有下划线的语句的执行次数的数量级是_______。答案log2n2i：=n*nWHILEi1DOi:=i_div_2;25.下面程序段中带下划线的语句的执行次数的数量级是_______。答案nlog2ni:=1;WHILEinBEGINFORj:=1TOnDO_x:=x+1;i:=i*2END；26.下面程序段中带下划线的语句的执行次数的数量级是：_________答案log2ni：=1；WHILEinDOi：=i*2;25.在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）。答案1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6O(n3)FORi：＝１TOnDOFORj：＝１TOiDOFORk：＝1TOjDOｘ：＝ｘ＋delta；27.已知如下程序段FORi:=nDOWNTO1DO{语句1}BEGINx:=x+1；{语句2}FORj:=nDOWNTOiDO{语句3}y:=y+1;{语句4}END；语句1执行的频度为__________；语句2执行的频度为__________；语句3执行的频度为__________；语句4执行的频度为___________。答案n+1nn(n+3)/2n(n+1)/2。四、简答题（共10分）1.什么是算法?算法的5个特性是什么?试根据这些特性解释算法与程序的区别。2.数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括线性表、栈、队列、数组等；非线性结构包括树、图等；这两类结构各自的特点是什么？3.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。参考题：4.试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别？答案简单来说，数据结构定义了一组按某些关系结合在一起的数据元素；抽象数据类型是指一个数学模型以及定义在该模型上的一组操作；而程序设计语言中的数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。5.算法的时间复杂度仅与问题的规模相关吗?答案不是,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。6.常用的存储表示方法有哪几种?答案常用的存储表示方法有四种:顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：根据结点的关键字直接计算该结点的存储地址。7.试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答案例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。那么我们怎样把这个表中的数据存储到计算机里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题，我们从高级语言的层次讨论这个问题。最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。7.什么是数据结构?有关数据结构的讨论涉及哪三个方面?答案数据结构是指数据以及相互之间的关系。记为：数据结构={D,R}。其中，D是某一数据对象，R是该对象中所有数据元素之间的关系的有限集合。有关数据结构的讨论一般涉及以下三方面的内容：①数据元素以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构；②数据元素极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构；③施加于该数据结构上的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑