数据结构练习试题和答案解析.doc

绪论判断题数据的逻辑结构与数据元素本身的内容和形式无关。(√)一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。(√)数据元素是数据的最小单位。(×)数据的逻辑结构和数据的存储结构是相同的。(×)程序和算法原则上没有区别,所以在讨论数据结构时可以通用。(×)从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。(√)数据的存储结构是数据的逻辑结构的存储映象。(√)数据的物理结构是指数据在计算机内实际的存储形式。(√)数据的逻辑结构是依赖于计算机的。(×)算法是对解题方法和步骤的描述。(√)二、填空题数据有逻辑结构和存储结构两种结构。数据逻辑结构除了集合以外,还包括线性结构、树形结构和图形结构。数据结构按逻辑结构可分为两大类,它们是线性结构和非线性结构。树形结构和图形结构合称为非线性结构。在树形结构中,除了树根结点以外,其余每个结点只有1个前驱结点。在图形结构中,每个结点的前驱结点数和后继结点数可以任意多个。数据的存储结构又叫物理结构。数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。线性结构中的元素之间存在一对一的关系。树形结构中的元素之间存在一对多的关系。图形结构的元素之间存在多对多的关系。数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)3个方面的内容。数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系有限集合。算法是一个有穷指令的集合。算法效率的度量可以分为事先估算法和事后统计法。一个算法的时间复杂度是算法输入规模的函数。算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模的n的函数。若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n)。若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O(n2)。数据结构是一门研究非数值计算的程序问题中计算机的操作对象,以及它们之间的关系和运算的学科。三、选择题数据结构通常是研究数据的(A)及它们之间的相互关系。(C)。。数据在计算机存储内表示时,物理地址和逻辑地址相同并且是连续的,称之为(C)。(D)。(A)。,一部分存放结点的值,另一个部分存放表示结点间关系的指针。,存放结点的值。,存储表示结点间关系的指针。,一部分存放结点的值,另一部分存放结点所占单元素算法的计算量大小称为算法的(C)。(B)。,所有存储结点相继存放在一个连续的存储空间里,这种存储结构称为(A)结构。,还包含一组指针,该存储方式是(B)。(D)。,与所使用的计算机无关的是(C)。,数据元素之间关系最弱的是(A)。、内容、相对位置、个数无关的是数据的(A)。,存储结点存放在连续的存储空间,另外有一组指明结点存储位置的表,该存储方式是(C)存储方式。(A)。(C)。(D)。(1)(n)(log2n)(n2)下列算法的时间复杂度是(D)。for(i=0;i<n;i++)for(j=o;i<n;j++)c[i][j]=i+j;(1)(n)C.(log2n)(n2)算法分析的两个主要方面是(A)。、输出和(C)