河海大學計算機專業1998年研究生入學考試試題

　　一、名詞解釋：（每題3分，共15分）

　　a 、數據類型

　　b、時間復雜度

　　c、靜態鏈表

　　d、循環隊列

　　e、拓撲排序

　　二、給出下列結構的存儲描述（每題3分，共15分）

　　a、廣義表（給出一種）

　　b、雙向循環鏈表

　　c、線索二叉樹

　　d、鄰接表

　　e 、串

　　三、利用兩個棧s1，s2模擬一個隊列時如何用棧的運算（push，pop，top，sempty）來實現下列隊列的運算enq（入隊），deq（出隊），qempty（測隊空），試寫出算法。（每個算法4分共12分）

　　四、順序檢索時間為O（n），折半檢索時間為O（ ），Hash方法為O（1），為什么有高效的檢索算法，而低效率的方法不被放棄。（8分）

　　五、給出折半查找的遞歸算法，并給出算法時間復雜度性分析（5分）

　　六、給出以十字鏈表作存儲結構，建立圖的算法，輸入（i，j，v）其中i，j為頂點號，v為權值。（10分）

　　七、寫出在中序線索二叉樹里；找指定結點在后序下的前驅結點的算法。（10分）

　　八、分別以不同存儲結構實現線性表就地逆轉的算法，即在原表的存儲空間內將線性表（a1，a2，…，an）逆轉為（an，an-1，…a2，a1）

　　a.以一維數組作存儲結構； b.一單鏈表作存儲結構。（10分）

　　九、證明：如果給了一個二叉樹結點的先序序列和中序序列，則此二叉樹即可構造出來，如果給了先序序列和后序序列行嗎？給了后序序列和中序序列呢？如果不行請舉反例。（10分）