淘豆网
1/9
下载文档
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
数据结构抄.doc
文档介绍:
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象  以及它们之间的 关系  和运算等的学科。2.数据结构被形式地定义为(D,R),其中D是 数据元素  的有限集合,R是D上的 关系 有限集合。3.数据结构包括数据的逻辑结构 、数据的存储结构 和数据的 运算 这三个方面的内容。4.数据结构按逻辑结构可分为两大类,它们分别是 线性结构 和 非线性结构 。5.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。6.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点 没有  后续结点,其余每个结点有且只有1个后续结点。7.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;叶子结点没有 后续 结点,其余每个结点的后续结点数可以任意多个 。8.在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个  。9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序 、链式、索引 和 散列 。10.一个算法的效率可分为 时间  效率和 空间 效率。1.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗?答:简单地说,数据结构定义了一组按某些关系结合在一起的数据元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。2.简述线性结构与非线性结构的不同点。答:线性结构反映结点间的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。1.【严题集2.2①】在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与表长和该元素在表中的位置 有关。2.线性表中结点的集合是有限  的,结点间的关系是 一对一  的。3.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时,需向后移动n-i+1个元素。4.向一个长度为n的向量中删除第i个元素(1≤i≤n)时,需向前移动n-i个元素。5.在顺序表中访问任意一结点的时间复杂度均为O(1) ,因此,顺序表也称为随机存取 的数据结构。6.【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。7.【严题集2.2①】在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值 指示。8.在n个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为O(n)。1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?答:①顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。优点:存储密度大(=1?),存储空间利用率高。缺点:插入或删除元素时不方便。②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针优点:插入或删除元素时很方便,使用灵活。缺点:存储密度小(<1),存储空间利用率低。顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。2.【严题集2.1①】描述以下三个概念的区别:头指针、 内容来自淘豆网www.taodocs.com转载请标明出处.