【数据结构】——线性表简答题模板

一、顺序表

【顺序表是什么/数组与顺序表的区别】

1、数组和顺序表的区别在哪里？

答：顺序表体现了数据元素之间的线性关系，即一对一的关系，以及对数据元素定义的一组运算操作，所以操作起来比数组更容易实现、方便操作，而数组只是物理区域上的一组连续的存储单元，它是具有相同类型的若干元素按无序的形式组织起的一种形式。

二、链表

【头指针与头结点的区别】

1、说明在线性表的链式存储结构中，头指针与头结点之间的根本区别，头结点与首元结点的关系。

答：①头指针具有标识作用，常用头指针代指链表的名称，同时可以防止链表为空；头结点的设置可以使插入或删除操作统一起来并且方便。
②首元结点是第一个元素结点，即头结点后的第一个结点。

---

【带头结点的单链表】

2、单链表设置头结点的作用是？

答：①防止单链表为空，若单链表为空时，则为一个空链表，即头结点L→next=NULL；
②保证了插入元素和删除元素操作的统一性，带有头结点的单链表，其存储位置存放在头结点L的指针域中，指向单链表的第一个结点。

---

【链表的分类】

3、链表可以通过指针分为哪些类别？

答：根据线性表的链式存储结构中每一个结点包含的指针个数，可将线性链表分成单链表和双链表，而又根据指针的连接方式，链表又可分成静态链表和（动态）链表。

三、顺序表与链表的对比

【顺序表和链表存储方式的区别】

1、简述顺序表和链表存储方式的特点。

答：①顺序表实现简单，可以随机存取，其存储密度大，但是执行插入、删除操作需要移动大量元素，效率低，另外其存储空间需事先分配，容易造成空间浪费或溢出。
②链表不支持随机存取，只能顺序存取，通过指针来体现元素之间的逻辑关系，存储密度比顺序表小，其执行插入、删除操作不需要移动元素，只需修改指针，效率高，另外它还支持动态分配存储空间，不会造成空间浪费或溢出。

---

【不同存储结构中数据元素之间的逻辑关系】

2、顺序存储结构和链式存储结构分别是通过什么来表示数据元素之间的逻辑关系的？

答：顺序存储结构是通过物理上相邻的地址来表示逻辑关系，而链式存储结构是通过指针来表示逻辑关系。

---

【线性表存储结构的选用】

3、若线性表插入和删除操作比较频繁，则宜采用什么存储结构？为什么？

答：链式存储结构，采用该结构在执行插入、删除操作时不需移动大量元素，只需修改指针，且可以支持存储空间的动态分配。

四、循环链表

【循环单链表的优点】

1、循环单链表最大的优点是什么？

答：循环单链表中从任一结点出发都可以访问到链表中的每一个元素。

五、静态链表

【静态链表的概念】

1、简述静态链表的定义以及其优缺点。

答：静态链表借助数组来描述链式结构，每个数组元素有两个分量，一是数据元素的值，二是指针，指针指向下一个元素在数组中的位置 (下标)。静态链表插入和删除操作时只需修改指针，而不需要不移动数据，但是静态链表不能随机存取。另外，若定义的数组太大，有可能浪费较多的存储空间。