《数据结构》-数据结构作业 第一章.docx

数据结构的主要研究对象是什么?
答:数据结构的研究内容为:为在计算机上解决具体问题,应如何对所需的数据/信息及其关系进行组织(组织起来的数据就具有了结构关系),以及如何对他们基本操作。简而言之,研究数据的组织方式(结构)及相应的抽象操作。
有哪几种基本的逻辑结构?它们各自的特点是什么?
答:(1)数据的逻辑结构分为集合、线性结构、树、图等;
(2)
①.集合
数据结构中,数据元素之间不考虑关系问题(无前驱/后继之分),称这种结构为集合。
在集合中,各元素是“平等”的,它们的共同关系是都属于同一个集合。
②线性结构
数据结构中若数据元素之间只存在前后顺序关系(每个元素都有唯一前驱和后继,第一个元素可以没有前驱,最后一个可以没有后继),称这种结构为线性结构。
线性表、栈、队列、串等均为线性结构。
③树形结构
如果除一个特殊元素没有前驱外,其他每个元素都有唯一的前驱,则称这种结构为树形结构,简称树。将无前驱的元素成为树根。
树形结构中的元素可分为三种:一种成为根,每个树结构都只有一个根,根无前驱,但可以有若干后继;一种为叶子,叶子无后继,但有且仅有一个前驱;其余为普通结点,有且必有一个前驱,有若干个后继。
树形结构通常用来表达层次关系,也常用于快速检索,为提高数据检索速度。
④图状结构
在图状结构中,任一数据元素均可由多个前驱和多个后继。该种结构也称为网状结构。
图状结构表达能力最强,它可以表达任意复杂的数据结构。
树形结构和图状结构均称为非线性结构。
有哪几种基本的存储结构?它们各自的特点是什么?
答(1)存储结构包括顺序存储、链式存储、索引存储、散列存储等;
(2)
①顺序存储
顺序存储是面向线性关系的存储方法。对于线性数据结构,可将其数据元素按相应的线性关系的前后次序,存储在物理存储器中,使得数据元素在此线性关系下的逻辑次序与它们在存储器中的存放次序一致,这就是顺序存储。
为了能使存储次序表达逻辑次序,在存储器中,任意相邻两数据元素之间的存储单元数目应相等。
②链式存储
链式存储的每个数据元素的存储区分为两部分:第一部分为数据区,存储元素的内容;第二部分为指针区,存放该数据元素和其他数据元素之间的关系信息,这种关系信息一般为地址。
对于线性结构,指针区中可以只设一个地址,而对于非线性关系,可能需要多个地址。
链式存储与顺序存储相比,它的存储空间开销比较大(增加了指针区),但由于各数据元素的存储区不要求是连续排列的,所以对内存空闲区分布的要求不高,很适合动态存储管理。
链式存储适用的范围很广,理论上讲,可适用于任何数据结构的存储。因为显式地存储了关系,所以空间利用率比较低。
③索引存储
索引存储主要针对集合和线性表,面向检索操作。它主要是在数据结构的存储区(称为数据区)外,增加一个或者若干个索引区。
索引存储并不强调对关系的存储,而主要针对数据内容,所以,一般只适合集合结构和线性结构。
④散列存储
散列存储(也称为杂凑法)是一种按照元素内容存储元素的方法。
散列存储时面向内容的存储,不适合存储复杂的数据结构。
数据结构有哪些要素?
答:①属性读取:读取数据结构的各基本属性的值;
②属性设置:给数据结构的基本属性赋值;
③查找:在数据结构中