数据结构试题库集及答案.doc

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究(D)。 、存储结构及其基本操作2、算法分析的两个主要方面是(A)。 、具有线性结构的数据结构是(D)。 、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、(B)等5个特性。、可移植性和可扩充性 、有穷性和确定性 、有穷性和稳定性 、稳定性和确定性5、下面程序段的时间复杂度是(C)。 for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j; (m2) (n2) (m*n) (m+n)6、算法是(D)。 、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示(C)。(n) (nlog2n) (n2) (log2n)8、下面程序段的时间复杂度为(C)。 i=1; while(i<=n) i=i*3;(n) (3n) (log3n)(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的()和运算等的学科。 、下面程序段的时间复杂度是()。 i=s=0; while(s<n){ i++;s+=i; }(n) (n2) (log2n) (n3)11、抽象数据类型的三个组成部分分别为()。、数据关系和基本操作 、逻辑结构和存储结构 、数据元素和数据类型 、数据结构和数据类型12、一般从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是()。 ,以便调试、修改和扩充 ,算法能适当地做出反应或进行处理,不会产生不需要的运行结果 、下列程序段的时间复杂度为(B)。 x=n;y=0; while(x>=(y+1)*(y+1)) y=y+1; (n) B. C. O(1) (n2)二、填空题1、程序段“i=1;while(i<=n)i=i*2;”的时间复杂度为。2、数据结构的四种基本类型中,树形结构的元素是一对多关系。三、综合题1、将数量级O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增长率由小到大排序。答案:O(1)O(log2N)O(N)O(Nlog2N)O(N2)O(N3)O(2N)一、(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合。、数据的存储结构和数据的运算这三个方面的内容。,它们分别是线性结构和非线性结构。,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数能够任意多个。,每个结点的前驱结点数和后续结点数能够任意多个。,它们分别是顺序、链式、索引、散列。,它们分别是插入、删除、修改、查找、排序。。。二、单项选择题(B):A)一对多关系B)多对多关系C)多对一关系D)一对一关系(C),与所使用的计算机无关的是数据的结构;A)存储B)物理C)逻辑D)物理和存储(C):A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性(A):A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性(C):A)计算方法B)排序方法C)解决问题的有限运算序列D)