数据结构形考简答题
1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。
2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。
答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。
优点：一般情况下，存储密度大，存储空间利用率高。
缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。
链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。
优点：插入和删除元素时很方便，使用灵活。
缺点：存储密度小，存储空间利用率低。
1．栈、队列和线性表的区别是什么？
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作
2．设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过S ，一个元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是多少？
出队序列是e2,e4,e3,e6,e5,e1的过程：
（1）e1入栈（栈底到栈顶元素是e1）
（2）e2入栈（栈底到栈顶元素是e1，e2）
（3）e2出栈（栈底到栈顶元素是e1）
（4）e3入栈（栈底到栈顶元素是e1，e3）
（5）e4入栈（栈底到栈顶元素是e1，e3，e4）
（6）e4出栈（栈底到栈顶元素是e1，e3）
（7）e3出栈（栈底到栈顶元素是e1）
（8）e5入栈（栈底到栈顶元素是e1，e5）
（9）e6入栈（栈底到栈顶元素是e1，e5，e6）
（10）e6出栈（栈底到栈顶元素是e1，e5）
（11）e5出栈（栈底到栈顶元素是e1）
（12）e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S 的容量至少是3。
3．有5个元素，其入栈次序为：A 、B 、C 、D 、E ，在各种可能的出栈次序中，以元素C 、D 最先的次序有哪几个？
从题中可知，要使C 第一个且D 第二个出栈，应是A 入栈，B 入栈，C 入栈，C 出栈，D 入栈。之后可以有以下几种情况：
（1）B 出栈，A 出栈，E 入栈，E 出栈，输出序列为：CDBAE 。
（2）B 出栈，E 入栈，E 出栈，A 出栈，输出序列为CDBEA 。
（3）E 入栈，E 出栈，B 出栈，A 出栈，输出序列为CDEBA
所以可能的次序有：CDBAE ，CDBEA ，CDEBA
4．简述广义表和线性表的区别和联系。
广义表是线性表的的推广，它也是n （n>0）个元素a1，a2，…，ai ，…，an 的有限序列，其中ai 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特性，线性表可以看成广义表的特殊情况，当ai 都是原子时，广义表退化成线性表。