2022年数据结构复习题 2.pdf

《2022年数据结构复习题 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构复习题 2.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构复习题1. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中， 应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：A.基于空间的考虑。当要求存储的线性表长度变化不大， 易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。B.基于时间的考虑。若线性表的操作主要是进行查找， 很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时， 宜采用链表做存储结构。 并且，若链表的插入和删除主要发生在表的首尾两端，

2、则采用尾指针表示的单循环链表为宜。2. 解释拓扑排序，并简述如何进行拓扑排序。由某个集合上的一个偏序得到该集合上的一个全序，这个操作就成为拓扑排序。拓扑排序的操作如下：1）在有向图中选一个没有前驱的顶点并输出之；2）从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出， 或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。四、已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树对应的二叉树。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 data A B C D E F G H I J K L M N O parent 0 1

3、 1 1 2 2 3 3 4 4 5 6 6 7 8 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 3. 写出下图所示的 AOV 网的可能拓扑序列，要求至少写出五个。答案： 可能的拓扑序列有：1）Abdcef 2）Abcdef 3）bcedf 4）Cabdef 5）Cabedf 6）Acbdef 7）Acbedf 4. 设有一个求解汉诺塔（ Hanoi）的递归算法void HANOI (int n , int peg1 , i

4、nt 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) ; A B C D E F 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 假定采用

5、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)

6、已知一棵二叉树的前序序列和后序序列分别为AB和 BA ，请画出这两棵不同的二叉树。答：已知二叉树的前序序列为ABDGHCEFI 和中序序列 GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和 ECIF结点， 又由前序序列可知B和 C分别为两棵子树的根结点 . 以此类推可画出所有结点：A/ B C/ / D EF / / G HI(2) 以同样的方法可画出该二叉树：A/ B F CG/ D EH(3)这两棵不同的二叉树为：AA名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

7、名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - / BB6. 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素 ? 答：在等概率情况下， 顺序表中插入一个结点需平均移动n/2 个结点。删除一个结点需平均移动 (n-1)/2个结点。具体的移动次数取决于顺序表的长度n 以及需插入或删除的位置i 。i 越接近 n 则所需移动的结点数越少。7. 描述一趟快速排序算法。答：具体做法为：附设两个指针low 和 high ，它们的初值分别为low 和 high ，设枢轴记录的关键字为pivotkey ，则首先从 high

8、所指位置向前搜索找到第一个关键字小于 pivotkey的记录和枢轴记录互相交换，然后从low 所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至 low=high 为止。8. 设顺序表 L 是一个递增有序表，试写一算法，将x 插入 L 中，并使 L 仍是一个有序表。答：因已知顺序表 L 是递增有序表，所以只要从顺序表终端结点（设为i 位置元素）开始向前寻找到第一个小于或等于x 的元素位置 i 后插入该位置即可。 在寻找过程中，由于大于 x 的元素都应放在 x 之后，所以可边寻找，边后移元素，当找到第一个小于或等于x 的元素位置 i 时，该位置也空出

9、来了。算法如下：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 ; / 比较并移动元素L-data i =x; L - length+; 9. 用邻接矩阵法写出下图的存储结构1 2 3 4 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 答：邻接矩阵： 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -