【数据结构】——数据结构概论简答题模板

前言

本系列文章的主要选题来自于重点常考的《数据结构》、《数据结构与算法》等科目的简答题，对其进行一定的整理，且覆盖的都是重点题型和常考题型，以精炼的描述来回答问题，适合需要对《数据结构》知识点背诵和查漏补缺的小伙伴，若有错误，欢迎评论区指正！

一、数据结构的概念

【数据结构的内容】

1、数据结构是一门研究什么内容的学科？

答：数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。

【数据结构的选择】

2、应从哪些方面考虑解决问题时所选择的数据结构？

答：时间复杂度和空间复杂度。

【数据结构的评价标准】

3、评价各种不同数据结构的标准是什么?

答：数据结构的评价标准可以从两个方面考虑，
①所选的数据结构是否准确、完整地刻画了问题的基本特征；
②是否容易实现，例如逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现等等。

二、数据对象

【数据对象的定义】

1、什么是数据对象?

答：有相同性质的数据元素集合称为数据对象，它是数据的一个子集。

三、数据类型和抽象数据类型

【数据类型的定义】

1、数据类型是如何定义的?

答：数据类型是高级程序语言中的一个基本概念，是值的集合和操作的集合。

【数据结构和数据类型的区别】

2、数据结构和数据类型有什么区别？

答：数据结构包括三个方面，分别是数据的逻辑结构、数据的存储结构以及数据的运算。而数据类型是值的集合和操作的集合，它是数据结构的一种简化情况。

【抽象数据类型的定义】

3、什么是抽象数据类型，其主要特点是什么?它与数据类型有什么不同之处？

答：①抽象数据类型是指一个数学模型及定义在该模型上的一组操作，包括三个部分，可概括为数据对象、数据关系和基本操作。用抽象数据类型可以定义一个完整的数据结构，其定义取决于它的逻辑特性。另外，数据结构的抽象操作的定义与具体实现无关。
②抽象数据类型和数据类型实质上是一个概念，但抽象数据类型的范围更广，它不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。

【数据类型和抽象数据类型的区别】

4、抽象数据类型与数据类型有什么不同之处？

答：抽象数据类型和数据类型实质上是一个概念，但抽象数据类型的范围更广，它不再局限于机器已定义和实现的数据类型，还包括用户在设计软件系统时自行定义的数据类型。

四、逻辑结构

【数据的逻辑关系】

1、数据逻辑结构包括什么?它们各有什么特点？

答：逻辑结构指的是数据元素之间在逻辑上的关系，可分为线性结构和非线性结构，线性结构是一对一的关系，而非线性结构是一对多或多对多的关系。更细分也可以说，逻辑结构包括集合、线性结构、树形结构和图形(网状)结构。

五、存储结构（物理结构）

【数据的存储结构的定义】

1、什么是数据的存储结构？

答：数据的逻辑结构在计算机中的表示称为存储结构，也称为物理结构，其中包括数据元素的表示和关系的表示。

【数据的存储结构的四种类型】

2、数据存储结构包括哪几种类型?

答：存储结构包括顺序存储、链式存储、索引存储和散列存储四种类型。

【四种存储结构的特点】

3、数据元素之间的关系在计算机中有几种表示方法？各有什么特点？

答：①顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。该存储结构的优点是可以实现随机存取，每个元素占用最少的存储空间，顺序表的存储密度=1，而缺点是由于只能使用相邻的一整块存储单元，从而会产生较多的外部碎片，其存储密度大，但有些操作(如插入、删除) 效率较差；
②链式存储方式。每个存储结点除了包含数据元素信息外还包含一组(至少一个) 指针，其存储结构一部分存放结点的值，另一部分存放表示结点间关系的指针（结点内的存储单元要求连续，而不同结点的存储空间可以不连续）。指针反映数据元素间的逻辑关系，这种方式不要求存储空间连续，便于动态操作(如插人删除等)，该存储结构的优点是充分利用了所有的存储单元，不会造成碎片现象，而缺点是由于通过指针来表示逻辑关系，所以指针也要存储，从而占用额外的存储空间，但存储空间开销大，另外不能折半查找等。链表的存储密度<1，是由于结点中含有指针域。另外，链式结构只能顺序存取，不能随机存储；
③索引存储方式。在存储数据元素的同时还需要建立附加的索引表，索引表的索引项指示存储结点的存储位置。七优点是在查找数据元素时很快、容易找到，而缺点是由于附加了索引表，从而占用了额外的存储空间，同时，若需要增加和修改数据时，需修改索引表，会花费较多时间；
④散列存储方式。通过利用散列函数和解决冲突的方法对数据元素的关键字直接计算其存储地址，然后将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。该存储结构的优点是在对数据元素进行增加、删除结点操作时很快，而缺点是若定义的哈希函数不能完全贴合情况，则会发生元素存储单元的冲突，而减少冲突从而会花费时间和一定的空间上的开销。

【存储结构与运算的关系】