数据结构复习题总结

数据结构复习题总结

1. 已知抽象数据结构ADT的形式定义如下，请画出该数据结构的逻辑结构图。 ADT = { 数据元素：D；结构关系：R；基本操作：… }
   其中：D = { a, b, c, d, e, f, g }；
   R =
   {,,,,,,,,,,,}。

2. 如图所示的连通网，请示使用克鲁斯卡尔算法构造最小生成树，要求画出构造的过程。

3. 用图示的方法描述头插法建立单链表的过程，要求写出关键性语句。

4. 请画出算术表达式A/B^C+D*E求值时运算数栈和运算符栈的变化过程。

5. 已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树。

6. 给定一组权值{0.40,0.30,0.15,0.05,0.04,0.03,0.03}，请构造一个哈夫曼树。

7. 已知待散列的线性表为(36,15,40,63,22)，散列用的一维地址空间为[0…6]，假定选用的散列函数是H(K) = K mod 7，若发生冲突采用线性探查法处理，请构造完成散列表。

8. 用增量序列{8、4、2、1}对关键字{56，37，59，41，98，47，94，50，63，52，42，54，60，72，86，90}进行希尔排序，用图表示排序过程。

9. 对关键字序列{8，5，10，5， 7，3}利用大根堆进行排序，用图表示排序过程。

10. 二叉树按照二叉链表存储，编写算法将二叉树的左右子树进行交换。