5数据结构复习题.doc

数据结构复习题1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：A.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。B.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.解释拓扑排序，并简述如何进行拓扑排序。由某个集合上的一个偏序得到该集合上的一个全序，这个操作就成为拓扑排序。拓扑排序的操作如下：1）在有向图中选一个没有前驱的顶点并输出之；2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。四、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对应的二叉树。123456789101112131415dataABCDEFGHIJKLMNOparent0111223344566783.写出下图所示的AOV网的可能拓扑序列，要求至少写出五个。ABCDEF答案：可能的拓扑序列有：1）Abdcef2）Abcdef3）bcedf4）Cabdef5）Cabedf6）Acbdef7）Acbedf4.设有一个求解汉诺塔（Hanoi）的递归算法void HANOI (int n , int peg1 , int peg2 , int peg3) if (n= =1) printf（”move %d to %dn”,peg1,peg3）; else HANOI (n-1, peg1, peg3, peg2);printf（”move %d to %dn”,peg1,peg3）;HANOI (n-1, peg2, peg1, peg3) ; 假定采用HANOI（3，1，2，3）去调用上述算法，则写出整个输出结果的前四行内容。答案：汉诺塔的递归处理过程如下表示：move 1 to 3 move 1 to 2 move 3 to 2 move 1 to 3 5.若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。答：已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点：A / B C / / D EF/ / G H I(2)以同样的方法可画出该二叉树： A / B F C G / D E H(3)这两棵不同的二叉树为： A A / B B6.在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。7.描述一趟快速排序算法。答：具体做法为：附设两个指针low和high，它们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。8.设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。算法如下：void InsertIncreaseList( Seqlist *L , Datatype x )int i;if ( L-length=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; /