比较顺序存储结构和链式存储结构 - 副本

中南大学现代远程教育课程考试（考试）复习题及参考答案数据结构(使用教材：余腊生编著，人民邮电出版社出版，《数据结构—基于C++模板类的实现》一、判断题1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

[ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

[ ]3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

[ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

[ ] 5．一个广义表的表尾总是一个广义表。

[ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

[ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

[ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

[ ] 9．直接选择排序是一种稳定的排序方法。

[ ] 10．30、闭散列法通常比开散列法时间效率更高。

[ ] 11．有n个结点的不同的二叉树有n!棵。

[ ] 12．直接选择排序是一种不稳定的排序方法。

[ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

[ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

[ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

[ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

在设计再散列函数时，要求计算出的值与表的大小m互质。

[ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

[ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

线性表知识点总结线性表的特点：1. 有序性：线性表中的元素是有序排列的，每个元素都有唯一的前驱和后继。

2. 可变性：线性表的长度是可变的，可以进行插入、删除操作来改变表的元素数量。

3. 线性关系：线性表中的元素之间存在明确的前驱和后继关系。

4. 存储结构：线性表的存储结构有顺序存储和链式存储两种方式。

线性表的操作：1. 查找操作：根据元素的位置或值来查找线性表中的元素。

2. 插入操作：将一个新元素插入到线性表中的指定位置。

3. 删除操作：将线性表中的某个元素删除。

4. 更新操作：将线性表中的某个元素更新为新的值。

线性表的顺序存储结构：顺序存储结构是将线性表的元素按照其逻辑顺序依次存储在一块连续的存储空间中。

线性表的顺序存储结构通常采用数组来实现。

数组中的每个元素都可以通过下标来访问，因此可以快速的进行查找操作。

但是插入和删除操作会导致元素位置的变动，需要进行大量数据搬移，效率较低。

线性表的链式存储结构：链式存储结构是将线性表的元素通过指针相连，形成一个链式结构。

每个元素包含数据和指向下一个元素的指针。

链式存储结构不需要连续的存储空间，可以动态分配内存，适合插入和删除频繁的场景。

但是链式结构的元素访问不如顺序结构高效，需要通过指针来逐个访问元素。

线性表的应用场景：1. 线性表适用于数据元素之间存在明确的前后关系，有序排列的场景。

2. 顺序存储结构适用于元素的插入和删除操作较少，对元素的随机访问较频繁的场景。

3. 链式存储结构适用于插入和删除操作较频繁的场景，对元素的随机访问较少。

线性表的操作的时间复杂度：1. 查找操作：顺序存储结构的时间复杂度为O(1)，链式存储结构的时间复杂度为O(n)。

2. 插入和删除操作：顺序存储结构的时间复杂度为O(n)，链式存储结构的时间复杂度为O(1)。

线性表的实现：1. 顺序存储结构的实现：使用数组来存储元素，通过下标来访问元素。

2. 链式存储结构的实现：使用链表来实现，每个元素包含数据和指向下一个元素的指针。

国家二级ACCESS机试选择题（公共基础知识）模拟试卷2(题后含答案及解析)题型有：1. 选择题选择题1．下列叙述中正确的是( )。

A．所谓算法就是计算方法B．程序可以作为算法的一种描述方法C．算法设计只需考虑得到计算结果D．算法设计可以忽略算法的运算时间正确答案：B解析：算法是指对解题方案的准确而完整的描述，算法不等于数学上的计算方法，也不等于程序。

算法设计需要考虑可行性、确定性、有穷性与足够的情报，不能只考虑计算结果。

算法设计有穷性是指操作步骤有限且能在有限时间内完成，如果一个算法执行耗费的时间太长，即使最终得出了正确结果，也是没有意义的。

算法在实现时需要用具体的程序设计语言描述，所以程序可以作为算法的一种描述方法。

知识模块：公共基础知识2．下列叙述中正确的是( )。

A．算法的复杂度包括时间复杂度与空间复杂度B．算法的复杂度是指算法控制结构的复杂程度C．算法的复杂度是指算法程序中指令的数量D．算法的复杂度是指算法所处理的数据量正确答案：A解析：算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。

算法的复杂度包括时间复杂度与空间复杂度。

算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度是指算法在执行过程中所需要的内存空间。

知识模块：公共基础知识3．下列叙述中正确的是( )。

A．算法的时间复杂度与计算机的运行速度有关B．算法的时间复杂度与运行算法时特定的输入有关C．算法的时间复杂度与算法程序中的语句条数成正比D．算法的时间复杂度与算法程序编制者的水平有关正确答案：B解析：为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。

为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。

算法所执行的基本运算次数还与问题的规模有关；对应一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关。

蜂考数据结构答案1.什么是数据结构?数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

结构包括逻辑结构和物理结构。

数据的逻辑结构包括4种(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系(2)线性结构：数据元素之间是一对一的关系——线性表、栈、队列(3)树形结构：数据元素之间是一对多的关系(4)图状结构：数据元素之间是多对多的关系。

物理结构包括顺序存储结构和链式存储结构。

2.解释一下顺序存储与链式存储顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。

链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

3.头指针和头结点的区别?头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

4.线性结构的特点(1)集合中必存在唯一的一个"第一个元素";(2)集合中必存在唯一的一个"最后的元素";(3)除最后元素之外，其它数据元素均有唯一的"后继";(4)除第一元素之外，其它数据元素均有唯一的"前驱"。

5.数组和链表的区别?从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。

链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。

链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

数据的逻辑结构和存储结构的关系数据的逻辑结构和存储结构是计算机科学中的两个重要概念，它们之间存在着密切的关系。

本文将从数据的定义、逻辑结构和存储结构的概念入手，探讨它们之间的联系和作用。

一、数据的定义数据是指在计算机中可以被处理和操作的信息，它可以是数字、文字、图像、声音等形式。

数据是计算机科学中最基本的概念，所有的计算机应用都离不开数据的处理。

二、逻辑结构的概念逻辑结构是指数据元素之间的逻辑关系，它是对数据元素之间关系的抽象描述。

逻辑结构分为线性结构、树形结构、图形结构等几种类型。

线性结构是指数据元素之间是一对一的关系，如线性表、栈、队列等；树形结构是指数据元素之间是一对多的关系，如二叉树、多叉树等；图形结构是指数据元素之间是多对多的关系，如图。

三、存储结构的概念存储结构是指数据在计算机中的存储方式，它是对数据的物理存储结构的描述。

存储结构分为顺序存储结构和链式存储结构两种类型。

顺序存储结构是指数据元素在计算机中的存储是连续的，如数组；链式存储结构是指数据元素在计算机中的存储是不连续的，通过指针来实现数据元素的链接，如链表。

四、逻辑结构和存储结构的关系逻辑结构和存储结构之间存在着密切的关系，它们之间的联系主要体现在以下几个方面。

1.逻辑结构决定了存储结构逻辑结构是对数据元素之间关系的描述，它决定了数据元素在计算机中的存储方式。

不同的逻辑结构需要不同的存储方式来实现。

比如，线性结构可以采用数组来实现顺序存储结构，也可以采用链表来实现链式存储结构。

2.存储结构影响了数据的处理效率存储结构对数据的处理效率有很大的影响，不同的存储结构对数据的处理效率也不同。

比如，数组的存储结构可以实现随机访问，对于查找操作效率很高；而链表的存储结构只能通过指针来访问，对于查找操作效率较低，但对于插入和删除操作效率较高。

3.逻辑结构和存储结构的选择需要根据实际应用场景来确定在实际应用中，需要根据数据的处理需求和计算机的硬件条件来选择适合的逻辑结构和存储结构。

数据结构(C语言)数据组织（数据、数据元素、数据项）的三个层次：数据可由若干个数据元素构成，而数据元素又可以由一个或若干个数据项组成。

四种基本的数据结构：集合、线性结构、树形结构、图状结构。

顺序存储的特点是在内存中开辟一组连续的空间来存放数据，数据元素之间的逻辑关系通过元素在内存中存放的相对位置来确定。

链式存储的特点是通过指针反映数据元素之间的逻辑关系。

数据类型：原子类型、结构类型。

线性表定义：线性表是n个数据元素的有限序列。

线性表的顺序存储结构：表中相邻的元素a和b所对应的存储地址A和B 也是相邻的。

（也就是数据都是按照表中情况进行连续存储的情况）线性表的链式存储结构：该线性表中的数据元素可以用任意的存储单元来存储。

表中的各个相邻的数据（元素）是通过一个指针地址来进行链接的，以找到下一个数据（元素）在哪。

其形式一般为：数据地址线性表的顺序和链式存储结构的比较：在线性表的长度变化比较大，预先难以确定的情况下，最好采用动态链表作为存储结构。

当线性表的长度变化不大时，采用顺序存储结构比较节省存储空间。

在顺序表结构的线性表上主要进行查找、读取而很少做插入和删除的操作。

链式结构的线性表中比较适应做插入和删除的操作。

一元多项式的加减法运算可先将一元多项式进行了改变存储之后再进行运算比较适宜，将一元多项式转换为用在内存中的前一项表示阶数，后一项表示对应该阶数的系数。

然后利用这种形式进行加减运算。

栈和队列栈是限定在表的同一端进行插入或删除操作的线性表，即进栈、出栈。

（特殊的线性表）栈的顺序存储结构：利用一组地址连续的存储单元依次从栈底到栈顶存放数据元素，栈底位置固定不变，可将栈底设在向量低下标的一端。

栈的链式存储结构：用单链表作为存储结构的栈称为链栈，链表的最后一个结点表示栈底，第一个结点表示栈顶。

队列也是一种特殊的线性表。

它所有的插入操作均限定在表的一端进行，而所有的删除操作则限定在表的另一端进行。

允许删除元素的一端称为队头，允许插入元素的一端称为队尾，删除元素称为出队，插入元素称为进队。

c语言数据结构期末考试试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，算法的时间复杂度是指（）。

A. 执行算法所需要的计算量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：A2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 存储密度高B. 存储密度低C. 存储空间少D. 存储空间多答案：A3. 在一个单链表中，若头节点不包含数据，其头节点的作用是（）。

A. 存储数据B. 存储空指针C. 存储尾节点的指针D. 存储首元素的指针答案：D4. 一个算法的空间复杂度是指（）。

A. 执行算法所需要的计算量B. 执行算法所需要的存储空间C. 执行算法所需要的时间D. 执行算法所需要的内存大小答案：B5. 栈的特点是（）。

A. 先进先出B. 后进先出C. 随机进先出D. 随机进后出答案：B6. 以下哪个数据结构是动态的（）。

A. 数组B. 链表C. 栈D. 队列答案：B7. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A8. 哈希表解决冲突的方法不包括（）。

A. 开放定址法B. 链地址法C. 线性探测法D. 二分查找法答案：D9. 以下哪种排序算法的时间复杂度为O(nlogn)（）。

A. 冒泡排序B. 快速排序C. 选择排序D. 插入排序答案：B10. 以下哪个不是图的遍历算法（）。

A. 深度优先搜索B. 广度优先搜索C. 回溯D. 归并排序答案：D二、填空题（每题2分，共20分）1. 在C语言中，动态分配内存的函数是___________。

答案：malloc2. 线性表的两种存储结构是顺序存储结构和___________。

答案：链式存储结构3. 栈的基本操作包括入栈和___________。

答案：出栈4. 在二叉树中，度为2的节点称为___________。

答案：分支节点5. 哈希表中，解决冲突的方法之一是___________。

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

（）28、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

线性表之顺序表与单链表的区别及优缺点线性表主要有顺序表和链表两种存储形式，贴主想问的，应该是将线性表la和l b头尾连接,要求时间复杂度为o(1),且占用辅助空间尽量小.应该使用哪种存储形式对吧？答案是应当采用链表。

具体理由看文章。

这里比较的是基于C语言实现的顺序表与单链表，与其他语言的实现可能会有差异，但我相信语言是相通的，它们的实现机制应该也差不多。

1、What什么是顺序表和单链表①顺序表：顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。

只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L 是元素占用存储单元的长度。

②单链表：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

它的数据是以结点（类型一般为结构体）来表示的，每个结点的构成：数据（类型为要存储的数据的类型）+ 指针（结构体指针），数据就是链表里具体要存储的东西，指针就是用来把每个节点都连接起来，使它们形成一个链状。

结点：链表：2、Compare二者的优缺点比较①空间上的比较（Space）a. 空间的开辟：顺序表的实现一般是实现连续开辟一段空间，然后在进行数据的增删查改（静态顺序表），所以顺序表一般是固定空间大小的；而单链表则是一次只开辟一个结点的空间，用来存储当前要保存的数据及指向下一个结点或NULL的指针，所以单链表的空间大小时动态变化的。

（当然，顺序表也可以在初始化时利用mallo c函数来开辟一块空间，每当空间不够用时，再用realloc来把当前空间扩容成2倍，从而也能实现空间的动态变化（动态顺序表））。

、b. 空间的使用：当我们不知道要存储多少数据时，用顺序表来开辟的空间如果太大，就会造成一定程度上的浪费，而用单链表是实现时，因为是每需要存储一个数据时，才开辟一个空间，虽然有非数据项的指针占空间，但相比顺序表来说，浪费不是那么明显；反之，当我们知道存储的数据的数量时，用顺序表来开辟对应的空间大小，来存储数据，因为顺序表中每个元素的存储密度为1，就完全不会有浪费的空间，而用单链表，因为每个结点都会有非数据项得指针，那么就会造成空间的浪费。