电大数据结构复核习题（简答题）.doc

电大数据结构复核习题（简答题） 简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。 什么情况下用顺序表比链表好？ 答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 解释头结点、第一个结点（或称首元结点）、头指针这三个概念的区别？ 答：头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 解释带头结点的单链表和不带头结点的单链表的区别。 答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。 在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。 在操作上，带头结点的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。 与单链表相比，双向循环链表有哪些优点？ 答：双向循环链表设置了指向前驱和后继的指针，所用的地址空间增加，以空间复杂度代价换取时间复杂度的提高。双向循环链表可以从任一结点开始遍历整个链表。在动态内存管理中，应用双向循环链表可以从上次查找过的 结点开始继续查找可用结点，而单链表却每次都需要从表头开始查找。相比之下，双向循环链表的时间效率更高。 简述栈和一般线性表的区别。 答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 简述队列和一般线性表的区别。 答：队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 链栈中为何不设头结点？ 答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。 利用一个栈，则： （1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。 答：（1）栈的操作特点是后进先出，因此输出序列有： A入，A出，B入，B出，C入C出，输出序列为ABC。 A入，A出，B入，C入，C出，B出，输出序列为ACB。 A入，B入，B出，A出，C入，C出，输出序列为BAC。 A入，B入，B出，C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA。 由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到。 （2）按照上述方法，可能的输出序列有：ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。不可能的输出序列有：DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD 用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？ 答：应是SXSSXSXX。各操