数据结构c语言版第一章绪论

《数据结构c语言版第一章绪论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章绪论重点与难点要求掌握数据结构的基木概念，包括数据、数据元素、数据项、数据对彖、数据结构、逻辑结构等;重点掌握数据结构所含两个层次的具体含义及其关系；理解时间和空间复杂度的概念及度量方法，了解算法设计时的注意事项及算法特性和评价标准。典型例题1.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。【解】数据：指能够被计算机识别、存储和加工处理的信息载体。数据元索：就是数据的基本单位，在某些情况卜数据元索也称为元索、结点、顶点、记录。数据元索有时可以由若干数据项组成。数据类型：是一个值的集合以及在这些值上定义

2、的一组操作的总称。通常数据类型可以看作是程序设计语言中己实现的数据结构。数据结构：指的是数据之间的相互关系，即数据的组织形式。一•般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。逻辑结构：指数据元素之间的逻辑关系。存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.线性结构：数据逻辑结构屮的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。非线性结构：数据逻辑结构屮的另一大类，它的逻辑特征是

3、一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。2.常用的存储表示方法有哪几种？【解】常用的存储农示方法有四种：顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。链接存储方法：它不要求逻辑上和邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。散列存储方法：就是根据结点的关键字直接计算出该结点的存

4、储地址。3.有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为T1=O(2n),A2的时间复杂度为T2=0(n2)仅就时间复杂度而言，请具体分析这两个算法哪一个好。【解】对算法A1和A2的时间复杂度T1和T2取对数，得n和21og2n,显然算法A2好于A1.1.算法的时间复杂度仅与问题的规模相关吗？【解】算法的吋间复朵度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时,一般就是以最坏情况下的时间复杂度为准的。2.设n是偶数，试计算运行下列程序段后m的值并给出该

5、程序段的时间复杂度。m=0;for(i=0;in/2时,m=m+l的运行次数:0;m=m+l的运行次数：1+3+・・・+n-2j+l+n+l=(n+2)(n/2+1)/2=(n/2+l)2【解】由分析可知该程序段的吋间复杂度0(i?),m的值等于赋值语句呼m+1的

6、运行次数，其计算式为1+3+…+n-2j+l+n+l=(n+2)(n/2+1)/2=(n/2+1)23.分析下面程序段的时间复杂度。intfact(intn){if(n<=l)return(l);elsereturn(n*fact(n-l));}【解】设fact(n)的运行时间函数为T(n),通过分析可知当n<=l时T(n)期令运算的时间为常数a)当n>l时T(n)=T(n-l)+b(令乘法运算的时间为常数b)可解得T(n)=T(l)+b(n-1)=a+b(n-l)所以fact(n)的时间复杂度为O(n)习题精选一、.单项选择题1.在数据结构中，从逻辑

7、上可以把数据结构分成()。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.通常要求同一逻辑结构中的所有数据元素具冇相同的特性，这意味着()。A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且対应数据项的类型要一致C.每个数据元素都一样A.数据元素所包含的数据项的个数要相等1.以下说法正确的是()oA・数据元素是数据的最小单位A.数据项是数据的基本单位B.数据结构是带有结构的各数据项的集合C.一些表面上很不相同的数据可以有相同的逻辑结构2.算法分析的两个主要方面是：（）A.空间复杂性和吋I

8、'可复朵性C.可读性和文档性3.计算机算法必须具备输入、输出和A.可行性、可移植性和可扩充性C