判斷題：
1-1
算法分析的兩個主要方面是時間復雜度和空間復雜度的分析。 (2分)
1-2 將N個數據按照從小到大順序組織存放在一個單向鏈表中。如果采用二分查找，那麼查找的平均時間復雜度是O(logN)。 (3分) 1-3 通過對堆棧S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。輸出的序列為：123。 (3分) 1-4 所謂“循環隊列”是指用單向循環鏈表或者循環數組表示的隊列。 (2分) 1-5 在一棵二叉搜索樹上查找63，序列39、101、25、80、70、59、63是一種可能的查找時的結點值比較序列。 (3分) 1-6 將1、2、3、4、5、6順序插入初始為空的AVL樹中，當完成這6個元素的插入後，該AVL樹的先序遍歷結果是：4、2、1、3、5、6。 (3分) 1-7 一棵有124個結點的完全二叉樹，其葉結點個數是確定的。 (3分) 1-8 用鄰接表法存儲圖，占用的存儲空間數只與圖中結點個數有關，而與邊數無關。 (3分) 1-9 如果無向圖G必須進行兩次廣度優先搜索才能訪問其所有頂點，則G中一定有回路。 (3分) 1-10 某二叉樹的前序和中序遍歷序列正好一樣，則該二叉樹中的任何結點一定都無右孩子。(3分) 選擇題： 2-4
H的某個指定位置p開始執行下濾。
1 void PercolateDown( int p, PriorityQueue H )
2 {
3 int child;
4 ElementType Tmp = H->Elements[p];
5 for ( ; p * 2 <= H->Size; p = child ) {
6 child = p * 2;
7 if ( child!=H->Size &&
8
9 (6分) )
10 child++;
11 if ( H->Elements[child] > Tmp )
12
13
14 (6分);
15 else break;
16 }
17 H->Elements[p] = Tmp;
18 }
3-2
下列代碼的功能是返回帶頭結點的單鏈表L的逆轉鏈表。
1 List Reverse( List L )
2 {
3 Position Old_head, New_head, Temp;
4 New_head = NULL;
5 Old_head = L->Next;
6
7 while ( Old_head ) {
8 Temp = Old_head->Next;
9
10 (6分);
11 New_head = Old_head;
12 Old_head = Temp;
13 }
14
15 (6分);
16 return L;
17 }
參考答案：
判斷題：TFFFF TTFFF
選擇題：CACDB AADBD CB
程序填空題：
H->Elements[child+1] > H->Elements[child] H->Elements[p] = H->Elements[child]
Old_head->Next = New_head L->Next = New_head
