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

　　a 、數(shù)據(jù)類型

　　b、時(shí)間復(fù)雜度

　　c、靜態(tài)鏈表

　　d、循環(huán)隊(duì)列

　　e、拓?fù)渑判?/P>

　　二、給出下列結(jié)構(gòu)的存儲(chǔ)描述（每題3分，共15分）

　　a、廣義表（給出一種）

　　b、雙向循環(huán)鏈表

　　c、線索二叉樹(shù)

　　d、鄰接表

　　e 、串

　　三、利用兩個(gè)棧s1，s2模擬一個(gè)隊(duì)列時(shí)如何用棧的運(yùn)算（push，pop，top，sempty）來(lái)實(shí)現(xiàn)下列隊(duì)列的運(yùn)算enq（入隊(duì)），deq（出隊(duì)），qempty（測(cè)隊(duì)空），試寫(xiě)出算法。（每個(gè)算法4分共12分）

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

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

　　六、給出以十字鏈表作存儲(chǔ)結(jié)構(gòu)，建立圖的算法，輸入（i，j，v）其中i，j為頂點(diǎn)號(hào)，v為權(quán)值。（10分）

　　七、寫(xiě)出在中序線索二叉樹(shù)里；找指定結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法。（10分）

　　八、分別以不同存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表就地逆轉(zhuǎn)的算法，即在原表的存儲(chǔ)空間內(nèi)將線性表（a1，a2，…，an）逆轉(zhuǎn)為（an，an-1，…a2，a1）

　　a.以一維數(shù)組作存儲(chǔ)結(jié)構(gòu)； b.一單鏈表作存儲(chǔ)結(jié)構(gòu)。（10分）

　　九、證明：如果給了一個(gè)二叉樹(shù)結(jié)點(diǎn)的先序序列和中序序列，則此二叉樹(shù)即可構(gòu)造出來(lái)，如果給了先序序列和后序序列行嗎？給了后序序列和中序序列呢？如果不行請(qǐng)舉反例。（10分）