非選擇題部分

　　注意事項：

　　用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。

　　二、填空題(本大題共13小題，每小題2分，共26分)

　　16.數據的基本單位是_________。

　　17.雙向循環(huán)鏈表中，在p所指結點的后面插入一個新結點*t，需要修改四個指針，分別為

　　t->prior=P;t->next=p->next;_________;p->next=t;。

　　18.在帶有頭結點的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結點為首結點的條件是_________。

　　19.若線性表中最常用的操作是求表長和讀表元素，則順序表和鏈表這兩種存儲方式中，較節(jié)省時間的是_________。

　　20.不含任何數據元素的棧稱為_________。

　　21.稀疏矩陣一般采用的壓縮存儲方法是_________。

　　22.100個結點的二叉樹采用二叉鏈表存儲時，用來指向左、右孩子結點的指針域有_________個。

　　23.已知完全二叉樹的第5層有5個結點，則整個完全二叉樹有_________個結點。

　　24.n個頂點的有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i列的所有元素之和等于頂點

　　Vi的_________。

　　25.具有10個頂點的有向完全圖的弧數為_________。

　　26.要完全避免散列所產生的“堆積’’現象，通常采用_________解決沖突。

　　27.在長度為n的帶有崗哨的順序表中進行順序查找，查找不成功時，與關鍵字的比較次數為_________。

　　28.歸并排序算法的時間復雜度是_________。

　　三、應用題(本大題共5小題，每小題6分，共30分)

　　29.稀疏矩陣A如題29圖所示，寫出該稀疏矩陣A的三元組表示法。

　　30.設二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。

　　31.寫出題31圖所示無向圖的鄰接矩陣，并寫出每個頂點的度。

　　題31圖

　　32.已知散列表的地址空間為0至13，散列函數H(k)=kmod11，(mod為求余運算)，待散列序列為(26，61，38，84，49)，用二次探測法解決沖突，構造該序列的散列表，要求寫出處理沖突的過程。

　　33.將一組鍵值(80，50，65，13，86，35，96，57，39，79，59，15)應用二路歸并排序算法從小到大排序，試寫出各趟的結果。

　　四、算法設計題(本大題共2小題，每小題7分，共14分)

　　34.設單鏈表及鏈棧S的結構定義如下：

　　typedef struct node

　　{ Data Type data;

　　struct node*next;

　�。齦inkstack;

　　編寫一個算法void ReverseList(1inkstack *head)，借助于棧S將帶頭結點單鏈表head中序號為奇數的結點逆置，序號為偶數的結點保持不變。(例如：單鏈表的邏輯結構為(a1，a2，a3，a4，a5，a6)，逆置后變?yōu)?a5，a2，a3，a4，a1，a6))。

　　說明：棧的初始化運算用InitStack(S);進棧運算用Push(S，x);判�？者\算用EmptyStack(S);出棧運算用Pop(S);取棧頂元素運算用Gettop(S)。

　　35.以二叉鏈表作為存儲結構，試編寫遞歸算法實現求二叉樹中葉子結點個數。