数据结构试题库及答案.docx

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