[数据结构与算法]数据结构简答题综合

更新时间：2022年9月18日

注：还不是很全，简答题不好找

一、顺序表

1. 简述单链表中设置头结点的作用。【电子科技大学2008三、1 （6分）】

• **统一空表和非空表的处理。**无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。
• **第1个位置的插入删除更加方便。**由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。

2. 顺序表的缺点：

• 第一，在作插入或删除操作时，需要移动大量元素；
• 第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；
• 第三，表的容量难以扩充。

3. 线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二、4 （6分）】

般说链式存储结构克服了顺序存储结构的三个弱点。

• 首先，插入、删除不需移动元素，只修改指针，时间复杂度为0&#

了解本专栏 订阅专栏 解锁全文