比较顺序存储结构和链式存储结构

1、试比较顺序存储结构和链式存储结构的优缺点;在什么情况下用顺序表比链表好答：① 顺序存储时,相邻数据元素的存放地址也相邻逻辑与物理统一；要求内存中可用存储单元的地址必须是连续的;优点：存储密度大＝1,存储空间利用率高;缺点：插入或删除元素时不方便;②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便,使用灵活;缺点：存储密度小<1,存储空间利用率低;顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作;若线性表的长度变化不大,且其主要操作是查找,则采用顺序表；若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表;顺序表与链表的比较基于空间的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度 = 1链表的存储密度 < 1基于时间的比较存取方式顺序表可以随机存取,也可以顺序存取链表是顺序存取的插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素,只需要修改指针顺序表和链表的比较顺序表和链表各有短长;在实际应用中究竟选用哪一种存储结构呢这要根据具体问题的要求和性质来决定;通常有以下几方面的考虑：┌───┬───────────────┬───────────────┐│ │ 顺序表│链表│├─┬─┼───────────────┼───────────────┤│基│分│静态分配;程序执行之前必须明确│动态分配只要内存空间尚有空闲,││于│配│规定存储规模;若线性表长度n变│就不会产生溢出;因此,当线性表││空│方│化较大,则存储规模难于预先确定│的长度变化较大,难以估计其存储││间│式│估计过大将造成空间浪费,估计太│规模时,以采用动态链表作为存储││考│ │小又将使空间溢出机会增多; │结构为好; ││虑├─┼───────────────┼───────────────┤││存│为1;当线性表的长度变化不大, │<1 │││储│易于事先确定其大小时,为了节约││││密│存储空间,宜采用顺序表作为存储││││度│结构; ││├─┼─┼───────────────┼───────────────┤│基│存│随机存取结构,对表中任一结点都│顺序存取结构,链表中的结点,需││于│取│可在O1时间内直接取得│从头指针起顺着链扫描才能取得;││时│方│线性表的操作主要是进行查找,很│││间│法│少做插入和删除操作时,采用顺序│││考││表做存储结构为宜; │││虑├─┼───────────────┼───────────────┤││插│在顺序表中进行插入和删除,平均│在链表中的任何位置上进行插入和│││入│要移动表中近一半的结点,尤其是│删除,都只需要修改指针;对于频│││删│当每个结点的信息量较大时,移动│繁进行插入和删除的线性表,宜采│││除│结点的时间开销就相当可观; │用链表做存储结构;若表的插入和││ │操│ │删除主要发生在表的首尾两端,则││ │作│ │采用尾指针表示的单循环链表为宜│为什么在单循环链表中设置尾指针比设置头指针更好答：尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便,设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O1; 若用头指针来表示该链表,则查找终端结点的时间为On;在链表中设置头结点有什么好处头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便;。

第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。

但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5. 选择题(1)~(6)：CCBDDA6．（1）O(1) （2）O(m*n) （3）O(n2)（4）O(log3n) （5）O(n2) （6）O(n)第2章1．选择题（1）~（5）：BABAD （6）~（10）：BCABD （11）~（15）：CDDAC 2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中不允许有重复的数据。

[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。

如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。

当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){ if(pa->data<pb->data){pc->next=pa; pc=pa; pa=pa->next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else //相等时取La中的元素，删除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next; delete pb ; pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

考研计算机复试笔试（数据结构C语⾔简答题篇）
1.⽐较顺序存储结构和链式存储结构的优缺点，什么情况下链表⽐顺序表好？
顺序存储时相邻元素的存储单元的地址也相连，可以随机存取。

优点是存储密度⼤，空间利⽤率⾼；缺点是插⼊或删除时不⽅便。

链式存储时相邻元素可以随意存放，只能顺序存取。

优点是插⼊或删除元素⽅便，使⽤灵活；缺点是存储利⽤率低
2.简述单链表（单向动态链表）的优缺点？
操作灵活，增加、删除元素时只需修改指针，从堆中分配空间，⾃由度⼤但难以管理，只能顺序存取，不⽀持随机访问。

3.算法时间复杂度与问题规模关系吗？
算法时间复杂度与问题规模和输⼊实例中的元素取值等相关，但在最坏情况下，时间复杂度只与问题的求解规模相关。

4.常⽤的存储表⽰⽅式有哪⼏种？
1.顺序存储⽅式；
2.链式存储⽅式；
3.索引存储⽅式；
4.散列存储⽅式
5.说明线性表、栈、队列的异同？
都是线性结构，都是逻辑结构概念，都可以⽤顺序存储或链式存储
栈和队列是受限的线性表
6.简述逻辑结构和存储结构的关系？
7.确定循环队列是空还是满的⽅式有哪些？
1.计数器；
2.设布尔变量；
3.空出⼀个元素
8.基本概念
数据项（不可分割的最⼩单位）-->数据元素（数据的基本单位）-->数据对象
9.数据元素之间的关系
1.集合；
2.线性结构；
3.树形结构；
4.图状/⽹状结构
10.。

谈顺序存储与链式存储的异同摘要：顺序存储与链式存储的应用范围较为广泛。

顺序存储就是用一组地址连续的存储单元依次存储该线性表中的各个元素，由于表中各个元素具有相同的属性，所以占用的存储空间相同，而链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。

关键词：顺序存储链式存储顺序存储与链式存储异同一、什么是顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。

采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

二、简述链式存储在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.链式存储结构不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要用地址连续的存储单元来实现。

因此在操作上，它也使得插入和删除操作不需要移动大量的结点。

线性表的链式存储结构主要介绍了单链表、循环链表、双向链表和静态链表四种类型，讨论了各种链表的基本运算和实现算法。

三、栈的存储结构：顺序存储和链式存储利用顺序存储方式实现的栈称为顺序栈。

顺序结构和链式结构
介绍
在计算机的物理存储结构上，分为顺序存储结构和链式存储结构，表⽰的是数据在内存中的分布位置
顺序存储结构
顺序存储结构是把数据元素存放在地址连续的存储空间⾥⾯。

当程序在内存中开辟⼀定数量的存储空间，这些空间的地址是紧挨着⼀起的。

在内存中是这样的
就像门牌号⼀样，建造房⼦也同时要编制好房号，通过指定的房号⼊住数据或者访问数据，数组是典型的顺序存储结构
链式存储结构
链式存储结构和顺序结构不同，它的存储空间地址是不连续的，东⼀个西⼀个的存储，在内存中见缝插针，相⽐顺序存储结构，它的空间利⽤率要⾼。

具体的在内存存储⽅式：
链式结构的重点是两两端点之间的关系
⼀个端点有下⼀个端点的访问地址，就是说你想要访问某个端点，就要先找到它的上⼀个端点。

直到你所能直接访问到的祖先端点
<<⽆间道>>的卧底就是这样⼦的
陈永仁是卧底，所以警局的⼈是不知道他的存在的，只有直属上司黄志诚知道。

想要拿到⿊帮情报，就要先叫黄志诚去找陈永仁，黄志诚找到陈永仁之后才能获得情报反馈给警局
如果⼀旦黄志诚被⿊帮解决掉，警局再也⽆法获得陈永仁提供的情报。

同理，链式存储结构⼀旦中间某个端点中断了，后⾯的端点就消失在内存中，数据还在，但没有办法找到它了。

顺序存储结构、链式存储结构、索引存储结构、散列存储结构介绍存储结构是指数据在计算机内存或磁盘等存储介质中的组织方式。

在数据结构中，常见的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

下面将分别对这四种存储结构进行详细介绍。

一、顺序存储结构（Sequential Storage Structure）：顺序存储结构是将数据元素按照其逻辑次序依次存储在一片连续的存储空间中，即在内存或磁盘上连续存放数据元素。

数据元素之间的逻辑关系通过其在存储空间中的物理位置来表示。

特点：顺序存储结构的存取速度较快，可以通过下标直接访问元素。

插入和删除操作需要移动大量元素，效率较低。

适用于元素数量固定、随机访问频繁的场景，如数组。

二、链式存储结构（Linked Storage Structure）：链式存储结构通过使用指针将数据元素存储在不连续的存储空间中，并通过指针将它们连接起来。

每个数据元素中都包含一个指向下一个元素的指针，从而构成了一个链表结构。

特点：链式存储结构的插入和删除操作效率较高，只需要修改指针的指向。

访问某个元素需要从头节点开始遍历，效率较低。

适用于元素数量不固定、插入和删除频繁的场景，如链表。

三、索引存储结构（Indexed Storage Structure）：索引存储结构是在顺序存储结构的基础上，为数据元素建立一个索引表，该索引表中的每个索引项包含了一个关键字和对应数据元素在存储空间中的地址。

特点：索引存储结构可以通过索引表快速定位数据元素，减少了遍历的时间。

插入和删除操作需要同时修改索引表和存储空间，效率相对较低。

适用于大型数据库等场景，可以提高查询效率。

四、散列存储结构（Hash Storage Structure）：散列存储结构是通过将数据元素的关键字映射到一个散列地址来进行存储和访问的。

具体的映射函数称为散列函数，它将关键字转换为一个固定长度的散列地址。

特点：散列存储结构可以快速定位数据元素，查找效率高。

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

指针域：存储直接后继位置的域。

指针或链：指针域中存储的信息。

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。

顺序表与链表的比较一、顺序表的特点是逻辑上相邻的数据元素，物理存储位置也相邻，并且，顺序表的存储空间需要预先分配。

它的优点是：（1）方法简单，各种高级语言中都有数组，容易实现。

（2）不用为表示节点间的逻辑关系而增加额外的存储开销。

（3）顺序表具有按元素序号随机访问的特点。

缺点：（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。

（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。

二、在链表中逻辑上相邻的数据元素，物理存储位置不一定相邻，它使用指针实现元素之间的逻辑关系。

并且，链表的存储空间是动态分配的。

链表的最大特点是：插入、删除运算方便。

缺点：（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。

存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。

（2）链表不是一种随机存储结构，不能随机存取元素。

三、顺序表与链表的优缺点切好相反，那么在实践应用中怎样选取存储结构呢？通常有以下几点考虑：（1）顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MaxSize”要有合适的设定，设定过大会造成存储空间的浪费，过小造成溢出。

因此，当对线性表的长度或存储规模难以估计时，不宜采用顺序表。

然而，链表的动态分配则可以克服这个缺点。

链表不需要预留存储空间，也不需要知道表长如何变化，只要内存空间尚有空闲，就可以再程序运行时随时地动态分配空间，不需要时还可以动态回收。

因此，当线性表的长度变化较大或者难以估计其存储规模时，宜采用动态链表作为存储结构。

但在链表中，除数据域外海需要在每个节点上附加指针。

如果节点的数据占据的空间小，则链表的结构性开销就占去了整个存储空间的大部分。

当顺序表被填满时，则没有结构开销。

在这种情况下，顺序表的空间效率更高。

由于设置指针域额外地开销了一定的存储空间，从存储密度的角度来讲，链表的存储密度小于1.因此，当线性表的长度变化不大而且事先容易确定其大小时，为节省存储空间，则采用顺序表作为存储结构比较适宜。

数据结构试卷B卷(含答案)-CAL-FENGHAI.-(YICAI)-Company One1《数据结构》试卷B一、填空题（每空1分，共15分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为。

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。

（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（每小题1分，共20分）（）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（）3. 判定一个栈ST（最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j（ ）5．具有n(n>0)个结点的完全二叉树的深度为 。