数据结构第1章-答案

1、资料收集于网络如有侵权请联系网站删除谢谢一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的( 操作对象) 以及它们之间的( 关系和运算) 等的学科。02、数据结构被形式地定义为(D,R) ，其中 D 是 ( 数据元素 ) 的有限集合， R 是 D 上的 ( 关系 ) 有限集合。03、数据结构包括数据的( 逻辑结构 ) 、数据的 ( 存储结构 ) 和数据的 ( 运算 ) 这三个方面的内容。04、数据结构按逻辑结构可分为两大类，它们分别是( 线性结构 ) 和 ( 非线性结构 ) 。05、线性结构中元素之间存在 ( 一对一 ) 关系，树形结构中元素之间存在 ( 一对多 ) 关系，图

2、形结构中元素之间存在( 多对多 )关系。06、在线性结构中，第一个结点( 没有 ) 前驱结点，其余每个结点有且只有1 个前驱结点；最后一个结点(没有)后续结点，其余每个结点有且只有1 个后续结点。07、在树形结构中，树根结点没有( 前驱 ) 结点，其余每个结点有且只有( 1) 个前驱结点；叶子结点没有(后续)结点，其余每个结点的后续结点数可以(任意多个 )。08、在图形结构中，每个结点的前驱结点数和后续结点数可以(任意多个 )。09、数据的存储结构可用四种基本的存储方法表示，它们分别是(顺序)、(链式)、(索引)、(散列)。10、对于给定的 n个元素，可以构造出的逻辑结构有( 集合 ) 、(

3、线性结构 ) 、( 树形结构 ) 、( 图状结构 ) 四种。11、数据的运算最常用的有5 种，它们分别是 (插入)、(删除)、(修改)、(查找)、(排序)。12、一个算法的效率可分为(时间)效率和 (空间)效率。13、数据结构中评价算法的两个重要指标是算法的( 时间复杂度 ) 和 ( 空间复杂度 ) 。14、一个数据结构在计算机中的( 映射 ) 称为存储结构。15、算法的五个重要特性是( 有穷性 ) 、 ( 确定性 ) 、( 可行性 ) 、输入、输出。16、已知如下程序段for (i=n; i>=1; i-)/语句 1 x+;/语句 2for (j=n; j>=i; j-) /语句

4、 3y+;/语句 4语句 1 执行的频度为 ( n+1) ；语句 2执行的频度为 ( n) ；语句 3执行的频度为 ( n(n+3)/2 ) ；语句 4执行的频度为 ( n(n+1)/2 ) 。17、在下面的程序段中，对的赋值语句的频度为( 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)/6 O(n3)18、下面程序段中带下划线的语句的执行次数的数量级是( O( log 2n ) )i=1;

5、while(i<n)i=i*2;n19、下面程序段中带下划线的语句的执行次数的数量级是( O(n log 2 ) ) 。i=1;while (i<n) for(j=1; j<=n; j+) x=x+1; i=i*2; n220、下面程序段中带有下划线的语句的执行次数的数量级是( O( log 2) ) 。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

6、、在有 n 个选手参加的单循环赛中，总共将进行( n(n-1)/2) 场比赛。二、判断题× 01、数据元素是数据的最小单位。× 02、数据的逻辑结构是指数据的各数据项之间的逻辑关系。× 03、算法的优劣与算法描述语言无关，但与所用计算机有关。 04、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 × 05、算法可以用不同的语言描述，则算法实际上就是程序了。 × 06、程序一定是算法。 07、数据的物理结构是指数据在计算机内的实际存储形式。× 08、数据结构的抽象操作的定义与具体实现有关。× 09、在顺序存储结构中，有时

7、也存储数据结构中元素之间的关系。× 10、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 11、数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。× 12、数据的逻辑结构说明数据元素之间的顺序关系, 它依赖于计算机的储存结构。三、单项选择题B01、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_和运算等的学科。A) 结构B) 关系C) 运算D) 算法BD02、数据的逻辑结构被形式地定义为B=(K,R) ，其中 K 是_的有限集合，R 是 K 上的 _有限集合。第 1 空的选项：A)算法B)数据元素C)数据操作D)逻

8、辑结构第 2 空的选项：A) 操作 B)映像 C)存储 D)关系A03、数据结构在计算机内存中的表示是指_。A) 数据的存储结构B) 数据结构C) 数据的逻辑结构D) 数据元素之间的关系C04、数据结构中，与所使用的计算机无关的是数据的_结构。A) 存储 B) 物理 C) 逻辑 D) 物理和存储C05、算法分析的目的是 _。A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性A06、算法分析的两个主要方面是_。A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性C07、计算机算法指的是

9、 _。A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法B08、计算机算法必须具备输入、输出和_等 5 个特性。A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性精品文档资料收集于网络如有侵权请联系网站删除谢谢D) 易读性、稳定性和安全性A09、在决定选取何种存储结构时，一般不考虑_。A) 各结点的值如何B) 结构个数的多少C) 对数据有哪些运算D) 所用编程语言实现这种结构是否方便C10、在存储数据时，通常不仅要存储各数据元素的值，而还要存储_。A) 数据的处理方法B) 数据元素的类型C) 数据元素之间的关系D) 数据的存储方法B11

10、、算法的计算量的大小称为计算的_。A)效率B)复杂性C)现实性D)难度A12、下面说法错误的是_。(1) 算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模 n下，复杂度 O(n) 的算法在时间上总是优于复杂度O( 2 n ) 的算法(3) 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4) 同一个算法，实现语言的级别越高，执行效率就越低A) (1)B) (1)、 (2)C) (1)、 (4)D) (3)C13、从逻辑上可以把数据结构分为_两大类。A)动态结构、静态结构B)顺序结构、链式结构C) 线性结构、非线性结构 D) 初等结构、构造型结构D14、以下与数据的存储

11、结构无关的术语是_。A)循环队列B)链表C)哈希表D)栈A15、以下数据结构中，_是非线性数据结构。A)树B)字符串C)队列D)栈C16、以下属于逻辑结构的是_。A)顺序表B)哈希表C)有序表D)单链表四、分析下面各程序段的时间复杂度01、 for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答： O（ mn ）02、 s=0;for (i=0; i<n; i+)for(j=0; j<n; j+)s+=Bij;sum=s;答： O（ n 2 ）03、 x=0;for (i=1; i<n; i+)for (j=1; j<=n-i

12、; j+)x+;答： O（ n 2 ）04、 i=1;while(i<=n)i=i*3;答： O（ log 3n ）精品文档资料收集于网络如有侵权请联系网站删除谢谢五、设有数据逻辑结构S=(D,R) ，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、 D=d1,d2,d3,d4R=(d1,d2),(d2,d3),(d3,d4) 答：此图为线性结构d1 d2 d3 d4d1无直接前驱，是首结点d4无直接后继是尾结点02、 D=d1,d2, ,d9R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(

13、d4,d5), (d6,d7),(d8,d9) 答：此图为树形结构d1无直接前驱，是根结点d2,d5,d7,d9无直接后继是叶子结点03、 D=d1,d2, ,d9R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)答：此图为图形结构d1， d2无直接前驱，是开始结点d6,d7无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。02、顺序存储结构和链式存储结构的特点是什么?答：顺序存储结构是指数据元素的