数据结构121 数据的逻辑结构

02331数据结构第一章概论1.数据是信息的载体。

2.数据元素是数据的基本单位。

3.一个数据元素可以由若干个数据项组成。

4.数据结构指的是数据之间的相互关系，即数据的组织形式。

5.数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。

②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。

③数据的运算，即对数据施加的操作。

最常用的检索、插入、删除、更新、排序等。

6.数据的逻辑结构分类:线性结构和非线性结构①线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。

线性表是一个典型的线性结构。

栈、队列、串等都是线性结构。

②非线性结构：一个结点可能有多个直接前趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

7.数据的四种基本存储方法:顺序存储方法、链接存储方法、索引存储方法、散列存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

通常借助程序语言的数组描述。

（2）链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。

通常借助于程序语言的指针类型描述。

（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。

索引表由若干索引项组成。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。

若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。

索引项的一般形式是：(关键字、地址)关键字是能唯一标识一个结点的那些数据项。

数据结构判断题(共5页) -本页仅作为预览文档封面，使用时请删除本页-一、判断题 (每题1分,共131分)1. 线性表的逻辑顺序总是与其物理顺序一致。

（）【答案】错2. 线性表的顺序存储优于链式存储。

（）【答案】错3. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。

（）【答案】对4. 若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。

（）【答案】错5. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。

（）【答案】对6. 内部排序是指排序过程在内存中进行的排序。

（）【答案】对7. 当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。

（）【答案】错8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。

( )【答案】对9. 任何一棵二叉树的叶结点在三种遍历中的相对次序是不变的。

（）【答案】对10. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。

( )【答案】错11. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。

（）【答案】错12. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

（）【答案】对13. 对稀疏矩阵进行压缩存储是为了节省存储空间。

（）【答案】对14. 当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。

( )【答案】对15. 哈希查找法中解决冲突问题的常用方法是除留余数法。

（）【答案】错16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。

( )【答案】错17. 堆排序是一种稳定的排序算法。

( )【答案】错18. 如果有向图中各个顶点的度都大于2，则该图中必有回路。

填空题（10 ＊1’ = 10' ）一、概念题2。

2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2。

3。

当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2。

6。

带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。

3。

6。

循环队列的引入,目的是为了克服假溢出.4。

2。

长度为0的字符串称为空串。

4。

5.组成串的数据元素只能是字符。

4。

8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7.2。

为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5.7。

广义表的深度是广义表中括号的重数7。

8.有向图G可拓扑排序的判别条件是有无回路。

7.9。

若要求一个稠密图的最小生成树，最好用Prim算法求解。

8。

8.直接定址法法构造的哈希函数肯定不会发生冲突。

9。

2。

排序算法所花费的时间，通常用在数据的比较和交换两大操作。

1。

1。

通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。

1。

2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1。

3。

存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1。

4。

抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。

1。

5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。

2.9。

在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。

一、选择题1-1 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（）。

A ) 数据的逻辑结构是数据间关系的描述B) 数据的逻辑结构抽象反映数据元素间的逻辑关系C) 数据的逻辑结构具体反映数据在计算机中的存储方式D) 数据的逻辑结构分为线性结构和非线性结构C1-2 以下关于数据的存储结构的叙述中哪一条是正确的（）。

A) 数据的存储结构是数据间关系的抽象描述B) 数据的存储结构是逻辑结构在计算机存储器中的实现C) 数据的存储结构分为线性结构和非线性结构D) 数据的存储结构对数据运算的具体实现没有影响B二、简答题1-1 数据结构的存储方式有哪几种？1-2 算法的时间复杂度仅与问题的规模相关吗?1-1 数据结构的存储方式有哪几种？【解析】常用的存储表示方法有四种:1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。

由此得到的存储表示称为链式存储结构, 通常借助于程序语言的指针类型描述。

3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

组成索引表的索引项由结点的关键字和地址组成。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index ）。

若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

1-2 算法的时间复杂度仅与问题的规模相关吗?【解析】算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。

但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。

我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

三、应用题: 分析以下程序段的时间复杂度。

第1章概论1.数据、数据元素、数据结构、数据类型的含义分别是什么？数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。

数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。

数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。

数据类型包含取值范围和基本运算等概念。

2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。

数据的逻辑结构包含下面两个方面的信息：①数据元素的信息；②各数据元素之间的关系。

物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。

数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。

采用不同的存储结构，其数据处理的效率是不同的。

因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。

3.数据结构的主要操作包括哪些？对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有：●创建：建立一个数据结构；●清除：清除一个数据结构；●插入：在数据结构中增加新的结点；●删除：把指定的结点从数据结构中删除；●访问：对数据结构中的结点进行访问；●更新：改变指定结点的值或改变指定的某些结点之间的关系；●查找：在数据结构中查找满足一定条件的结点；●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。

4.什么是抽象数据类型？如何定义抽象数据类型？抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。

数据结构复习笔记作者: 网络转载发布日期: 无数据就是指能够被计算机识别、存储和加工处理的信息的载体。

数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。

数据项是具有独立含义的最小标识单位。

如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。

数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。

这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。

比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。

那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。

而存储结构则是指用计算机语言如何表示结点之间的这种关系。

如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。

(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。

)第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。

弄清了以上三个问题，就可以弄清数据结构这个概念。

--------------------------------------------------------------------------------通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解)数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

数据结构知到章节测试答案智慧树2023年最新海南师范大学第一章测试1.从一个二维数组b[m][n]中找出最大值元素的时间复杂度为参考答案:m*n2.在以下时间复杂度的数量级中，数量级最大的是参考答案:3.下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;参考答案:O(m*n)4.执行下面程序段时，执行S语句的次数为（）。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;参考答案:n(n+1)/25.线性结构是数据元素之间存在一种：（）。

参考答案:一对一关系6.数据结构中，与所使用的计算机无关的是数据的（）结构。

参考答案:逻辑7.算法分析的目的是：（）。

参考答案:分析算法的效率以求改进8.算法分析的两个主要方面是：（）。

参考答案:空间复杂性和时间复杂性9.计算机算法指的是：（）。

参考答案:解决问题的有限运算序列10.计算机算法必须具备输入、输出和（）等5个特性。

参考答案:可行性、确定性和有穷性11.一个算法的好坏可以通过复杂性、可读性、健壮性、高效性这四个方面进行评价。

参考答案:错12.数据结构是一门研究算法的学科。

参考答案:错13.数据结构中，数据的逻辑结构包括线性结构、图结构、树形结构、集合。

参考答案:对14.线性表的逻辑顺序与存储顺序总是一致的。

参考答案:错15.每种数据结构都具备三个基本运算：插入、删除和查找。

参考答案:错16.线性结构中元素之间只存在多对多关系。

参考答案:错17.在线性结构中，第一个结点没有前驱结点。

参考答案:对18.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

参考答案:对19.算法分析的目的是分析算法的效率以求改进。

参考答案:对20.同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。

《数据结构》习题库之三：判断题1. 程序就是算法，但算法不一定是程序。

（）2. 线性表只能采用顺序存储结构或者链式存储结构。

（）3. 线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。

（）4. 除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）5. 稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）6. 不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

（）7. 确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）8. 深度为h的非空二叉树的第i层最多有2i-1 个结点。

（）9. 满二叉树就是完全二叉树。

（）10. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

（）11. 非空二叉排序树的任意一棵子树也是二叉排序树。

（）12. 对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。

（）13. 若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。

（）14. 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。

（）15. 序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。

（）16. 算法一定要有输入和输出。

（）17. 算法分析的目的旨在分析算法的效率以求改进算法。

（）18. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。

（）19. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。

（）20. 线性链表中各个链结点之间的地址不一定要连续。

（）21. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。

（）22. 若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

（）23. 若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。

（）24. 符号link(p)出现在表达式中表示p所指的那个结点的内容。

全国自考《数据结构导论》真题及答案

《数据结构导论》是全国高等教育自学考试中的一门重要课程，下面我将提供一套真题及答案，供考生参考。本套真题主要包括选择题、填空题、判断题、简答题和综合应用题。

一、选择题（每题2分，共20分） 1. 下列哪一项不是数据结构的组成要素？ A. 数据元素 B. 数据元素之间的关系 C. 数据的逻辑结构 D. 数据的存储结构 答案：D 2. 下列哪种数据结构不属于线性结构？ A. 队列 B. 栈 C. 图 D. 线性表 答案：C 3. 在单链表中，若要删除第i个数据元素，其时间复杂度为（ ）。

A. O(1) B. O(i) C. O(n) D. O(log n) 答案：C 4. 对于顺序存储的线性表，下列哪种操作的时间复杂度不是O(1)？

A. 删除第一个元素 B. 删除最后一个元素 C. 在第一个元素前插入一个元素 D. 在最后一个元素后插入一个元素 答案：C 5. 在二叉树中，具有3个节点的二叉树有（ ）种。 A. 2 B. 3 C. 4 D. 5 答案：C 二、填空题（每题2分，共20分） 6. 在数据结构中，数据的逻辑结构分为________和________两大类。

答案：线性结构，非线性结构 7. 在顺序存储的线性表中，插入和删除操作的时间复杂度分别为________和________。

答案：O(n)，O(n) 8. 在二叉树的遍历中，先序遍历的顺序是________，中序遍历的顺序是________，后序遍历的顺序是________。

答案：根-左-右，左-根-右，左-右-根 9. 一个具有n个顶点的无向图最多有________条边，一个具有n个顶点的有向图最多有________条边。

答案：n(n-1)/2，n(n-1) 10. 在图的邻接矩阵表示中，若顶点Vi与顶点Vj之间存在一条边，则矩阵中对应元素为________。 答案：1或边的权值 三、判断题（每题2分，共10分） 11. 线性表的顺序存储结构一定比链式存储结构占用空间多。（ ）