数据结构问题－请帮忙！！！

小弟马上就要参加考试了，恳请众高手帮助，非常谢谢。


1.已知一栈的输入序列为1、2、3、4、5, 试写出所有可能的出栈序列.


2.证明：对任何一棵具有n个结点、采用自顶向下从左而右对结点进行顺序编号（根据点编号为1）的完全二叉树，其叶结点的最小编号为n/2(当n为偶数时)或(n+1)/2(当n为奇数时).


3.已知如下数据序列：55，33，75，80，12，90，45，23，59，15，试为该时间序列构造一最大堆（根为最大值的堆），要求写出构造过程。


4.试写出将关键字35，50，17，80，40，90，12，19按AVL树插入算法依次插入一空树中，每一关键字插入后树的状态及平衡时用到的旋转类型（若有旋转）。


5.已知带权的无向连通图G（如下图,x不是结点，而是两线交叉得表示），试分别使用Prim算法和Krushal算法构造该图的最小生成树（从结点A开始），要求写出步骤。
              1      1
          A ---- D ----- F
           \    / \     /
           2\ 5/   \   /
             \/    4\ /3
             C       x
            / \     / \
          3/  3\   /   \
          /     \ /     \
         B ----- E ----- G
             2       3



6.设散列函数为H(k)=k mod 7, 散列表的地址空间为0-6, 对关键字序列(55,1,4,16,20,90,35), 请按线性探测法解决冲突的方法构造散列表,并指出各关键字查找时的比较次数.



7.已知两个带头结点的结点值递增的有序单链表L1、L2，结点数分别为n1、n2。试编写一算法将L1和L2合并成一个带头结点的结点值仍然递增的有序单链表L。要求，充分利用L1和L2中的结点构成L，算法的时间复杂性为O(n1+n2).



8.试编写一个算法，使得一组原来排成一队得混排得n辆汽车能够分开，让所有客车排在所有货车之前。要求，不使用辅助空间，且算法得时间复杂性为O(n).



9.已知有向图G及其中结点u,v。试编写算法，判断从u到v是否存在有向路径。

5 个解决方案