数据结构教学全套课件(李学刚)电子资源同步训练及参考答案 单元1 同步训练及答案.doc

《数据结构教学全套课件(李学刚)电子资源同步训练及参考答案 单元1 同步训练及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单元1同步训练及答案一、选择题1、数据的运算定义在数据的逻辑结构上，只有确定了（ ），才能具体实现这些运算。A、数据对象B、逻辑结构C、存储结构D、数据操作2、数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（ ）三方面内容。A、数据的逻辑结构、数据的存储结构、数据的描述B、数据的逻辑结构、数据的存储结构、数据的运算C、数据的存储结构、数据的运算、数据的描述D、数据的逻辑结构、数据的运算、数据的描述3、数据的逻辑结构包括（ ）。A、线性结构和非线性结构B、线性结构和树型结构C、非线性结构和集合结构D、线性结构和图状结构4、基

2、本的逻辑结构包括（ ）。A、树型结构、图状结构、线性结构和非线性结构B、集合结构、线性结构、树型结构和非线性结构C、集合结构、树型结构、图状结构和非线性结构D、集合结构、线性结构、树型结构和图状结构5、数据的存储方法主要包括（ ）。A、顺序存储方法和链式存储方法B、顺序存储方法和结构存储方法C、链式存储方法和结构存储方法D、索引存储方法和结构存储方法6、算法是对特定问题求解步骤的一种描述，是一系列将输入转换为输出的计算步骤。其特性除了包含输入和输出外，还包括（ ）。A、有穷性、正确性、可行性B、有穷性、正确性、确定性C、有穷性、确定性、可行性D

3、、正确性、确定性、可行性7、如果将与计算机软硬件相关的因素确定下来，那么一个特定算法的运行工作量就只依赖于（ ）。A、计算机硬件B、实现算法的语言C、问题的规模D、编译生成的目标代码的质量8、评价一个算法时间性能的主要标准是（ ）。A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度9、下面程序段各语句执行次数之和为（ ）。i=s=0;while(s

4、;j++)s++;A、O(n)B、O(lgn)C、O(n2)D、O(n3)二、解答题1、简述下列概念：数据、数据元素、数据结构、逻辑结构、存储结构、线性结构、非线性结构。2、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。3、常用的存储表示方法有哪几种?4、设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n)) (2)g(n)=O(f(n)) (3)h(n)=O(n1.5)(4)h(n)=O

5、(nlgn)5、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?6、分析下面程序段执行的时间复杂度。(1)i=1;k=0; while(i<=n-1){k+=10*i;i++;}(2)i=0;k=0;　do{k=k+10*i;i++; 　}while(ij)j++;elsei++;　}7、算法的时间复杂度仅与问题的规模相关吗?8、按增长率由小至大的顺序排列下列各函数：　　参考答案一、选择题1、C2、B3、A4、D5、A6、

6、C7、C8、D9、C10、C二、解答题1、答：数据：指能够被计算机识别、存储和加工处理的信息载体。数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容：数据的逻辑结构、存储结构和数据的运算。逻辑结构：指数据元素之间的逻辑关系。存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点

7、都有且只有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前驱和直接后继。数组、广义表、树和图等数据结构都是非线性结构。2、答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点（它的前面无记录）和一个终端结点（它的后面无记录），其他的结点则各有一个也

8、只有一个直接前驱和直接后继（它的前面和后面均有且只有一个记录）。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如