一、填空題

度數與邊數的關系

無向圖和有向圖

判空判滿

二、程式填空

2.1 順序表插入運算

p33 演算法2.1

public void insert(int i, Object x) throws Exception {
    if (curLen == listElem.length) {
        // 順序表已滿
        throw new Eception("順序表已滿");
    }
    if (i < 0 || i > curLen) {
        throw new Exception("插入位置不合法");
    }
    for (int j = curLen; j>i; j--) {
        // 元素后移
        listElem[j] = listElem[j - 1];
    }
    // 插入
    listElem[i] = x;
    curLen++;
}

2.2 統計二叉樹中結點個數

p165 演算法6.10

public int countNode(BiTreeNode tree) {
    int count = 0;
    if (tree != null) {
        LinkQuene quene = new LinkQuene();
        quene.offer(tree);
        while (!L.isEmpty()) {
            tree = (BiTreeNode) quene.poll();
            count++;
            if (T.lchild != null) {
                quene.offer(tree.lchild);
            }
            if (T.rchild != null) {
                quene.offer(tree.rchild);
            }
        }
    }
    return count;
}

2.3 順序查找

p286-287 演算法9.1-9.2

public int seqSearch(Comparable key) {
    int i = 0, n = length();
    while (i<n && r[i].key.compareTo(key)!=0) {
        i++;
    }
    // 如果找到了那么會在i<n停下
    if (i < n) {
        return i;
    } else { // 如果一直找不到，那么最后會i>=n而退出回圈
        return -1;
    }
}

2.4 堆排序調整堆演算法

p257-259 演算法p7.11-7.12

public void sift(int low, int high) {
    int i = low;
    int j = 2 * i + 1;
    Record temp = r[i];
    while (j < high) {
        // 如果右子結點小于左子結點，則對右子結點進行操作
        // 升序大頂堆，降序小頂堆，此處為小頂堆，小的在上大的在下
        if (j < high - 1 && r[j].key.compareTo(r[j + 1].key > 0)) {
            // j++換到右子結點
            j++;
        }
        if (temp.key.compareTo(rp[i].key) > 0) {
            r[i] = r[j];
            i = j;
            j = 2 * i + 1;
        } else {
            j = high + 1;
        }
    }
    r[i] = temp;
}

public void heapSort() {
    int n =this.curLen;
    RecordNode temp;
    // 創建堆
    for (int i = n/2-1; i>=0; i--) {
        sift(i, n);
    }
    /*
	將堆頂元素與末尾元素交換，將最小元素"沉"到陣列末端;
	重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，
	反復執行調整+交換步驟，直到整個序列有序，
	這里做的作業就是上面示意圖表示的
	 */
    for (int i = n - 1; i > 0; i--) {
        temp = r[0];
        r[0] = r[i];
        r[i] = temp;
        // 剩余未排序的部分元素再次構建堆
        sift(0 ,i);
    }
}

三、問答題

3.1 排序

3.1.1 時間復雜度和空間復雜度

p241-262 四大排序演算法，比較長，寫在最后面

3.2 最小生成樹

p215-220 克魯斯卡爾演算法 普里姆演算法

構造最小生成樹一定有下面兩個特點：

1、盡量選取最小的權值的邊，并且不能有回路

2、n個頂點只選取n-1條邊，

3.2.1 克魯斯卡爾演算法

根據邊的權值遞增的方式，一次找出權值盡可能最小的邊建立最小生成樹，并且規定每次新增的邊不能使生成樹形成回路，直到找到n-1條邊為止，

最小生成樹不是唯一的，

3.2.2 普里姆演算法

不知道怎么說，看圖好懂一些

3.3 建立二叉排序樹

p294 292-299

3.3.1 二叉排序樹定義

1. 若左子樹不為空，則左子樹上所有結點的值均小于根結點的值，
2. 若右子樹不為空，則右子樹上所有結點的值均大于根結點的值，
3. 根結點的左右子樹也都是二叉排序樹，

3.4 哈希表處理沖突的方法：開放定址法的線性探測

p317

開放定址法是哈希表處理沖突的一種方法，它的基本思想是：當沖突發生時，形成一個地址序列，沿著這個序列逐個探測，知道找到一個“空”的開放地址，就將發生沖突的關鍵字存放在該地址，

開放定址法的一般形式為：
H i = ( H ( k e y ) + d i ) % m , ( i = 1 , 2 , … , k ( k ≤ m ? 1 ) ) H_i=(H(key)+d_i)\%m,(i=1,2,\dots,k(k\le m-1)) Hi?=(H(key)+di?)%m,(i=1,2,…,k(k≤m?1))
其中，H(key)是關鍵字的哈希函式，%是取模，m為哈希表長，di為每次再探測時的地址增量，

線性探測法即地址增量為 d i = 1 , 2 , … , m ? 1 d_i=1,2,\dots,m-1 di?=1,2,…,m?1的開放定址法，其中i為探測次數，這種方法在解決沖突的時候一，依次探測下一個地址，直到有空的地址后插入，若整個空間都找不到空余的地址，則產生溢位，

線性探測法很容易造成資料元素的“聚集”現象，即多個哈希地址不同的關鍵字都在爭奪同一個后繼哈希地址，這種現象對查找不利，

其根本原因是查找序列過分集中在發生沖突的存盤單元后面，而沒有在整個哈希表空間上分散開來，

3.5 BFS DFS

p206-209

3.5.1 廣度優先搜索BFS

從圖中的某個頂點V開始，先訪問該頂點，在依次訪問該頂點的每一個未被訪問的鄰接點 w 1 , w 2 , … w_1,w_2,\dots w1?,w2?,…，然后按照鄰接點的訪問順序訪問 w 1 , w 2 , … w_1,w_2,\dots w1?,w2?,…未被訪問的子鄰接點，

重復上述程序知道圖中所有頂點都被訪問為止，

3.5.2 深度優先搜索DFS

從圖的某個頂點V開始訪問，然后訪問它的任意一個鄰接點 w 1 w_1 w1?，再從 w 1 w_1 w1?出發，訪問與 w 1 w_1 w1?相鄰且為被訪問過的頂點 w 2 w_2 w2?，再從 w 2 w_2 w2?出發進行類似訪問，如此進行下去，知道所有子結點的鄰接點都被訪問過，

之后，退回一步，回到上一個被訪問的頂點（遞回），看看是否還有其他未被訪問的鄰接點，如果有，則訪問此結點，然后再次從該子結點出發，進行類似的訪問操作，

重復以上操作，直到圖中所有結點均被訪問，

3.6 哈夫曼樹的構造

哈夫曼演算法：

假設 n n n個葉結點的權值分別為 w 1 , w 2 , … , w n {w_1,w_2,\dots,w_n} w1?,w2?,…,wn?，則

1. 由已知給定的 n n n個權值 w 1 , w 2 , … , w n {w_1,w_2,\dots,w_n} w1?,w2?,…,wn?，構造一個由 n n n棵二叉樹構成的森林 F F F，森林中每一個結點單獨作為一棵樹（即每棵樹僅有一個結點，就是根結點），每棵樹的權值分別為 w 1 , w 2 , … , w n {w_1,w_2,\dots,w_n} w1?,w2?,…,wn?，
2. 在森林中選擇根結點的權值最小和次小的兩棵樹，分部把它們作為左子樹和右子樹，構建一顆新的二叉樹，該新二叉樹的根結點權值為左右孩子的權值之和，
3. 將新二叉樹的左右子樹從森林中移除，將新產生的二叉樹加入森林中
4. 重復上述兩點，直到森林中只剩下一顆二叉樹為之，這棵樹就是哈弗曼樹，

四、綜合題

4.1 根據前中序遍歷建立二叉樹、森林

p179 181

4.1.1根據前中序遍歷建立二叉樹

思路

1. 取先根遍歷序列中第一個結點作為根結點
2. 在中根遍歷序列中尋找根結點，確定根結點在中根遍歷序列中的位置，設為 i ( 0 ≤ i ≤ c o u n t ) i(0 \le i \le count) i(0≤i≤count)，其中 c o u n t count count為二叉樹遍歷序列的結點個數
3. 在中根遍歷序列中確定：
   1. 根結點之前的 i i i 個結點序列構成左子樹的中根遍歷序列
   2. 根結點之后的 c o u n t ? i ? 1 count-i-1 count?i?1 個結點序列構成右子樹的中根遍歷序列
4. 在先跟遍歷序列中確定：
   1. 根結點之后 i i i 個結點序列構成左子樹的先跟遍歷序列
   2. 剩下的 c o u n t ? i ? 1 count-i-1 count?i?1 個結點序列構成右子樹的先跟遍歷序列
5. 由上述3、4兩個步驟又確定了左右子樹的先根和中根遍歷序列，遞回構建完整的二叉樹

圖解

代碼實作

/**
 * 通過前序遍歷序列和中序遍歷序列構建子樹
 * @param preOrder 前序遍歷序列
 * @param inOrder 中序遍歷序列
 * @param preIndex 前序遍歷序列索引
 * @param inIndex 中序遍歷序列索引
 * @param count 當前子樹的結點數
 */
public BinaryTreeNode(List<T> preOrder, List<T> inOrder, 
                      int preIndex, int inIndex, int count) {
	if (count > 0) {
		// 先獲取根結點
		T r = preOrder.get(preIndex);
		
		// 尋找根結點在中根遍歷序列中根的位置
		int i = 0;
		while (i < count) {
			if (r == inOrder.get(i + inIndex)) {
				break;
			}
			
			i++;
		}
		
		// 回圈結束后，i就是根結點在中序遍歷序列中的位置
		data = r;
		BinaryTreeNode<T> leftNode = new BinaryTreeNode<>(preOrder, inOrder, preIndex + 1, inIndex, i);
		if (leftNode.data != null) {
			left = leftNode;
		}
		BinaryTreeNode<T> rightNode = new BinaryTreeNode<>(preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1);
		if (rightNode.data != null) {
			right = rightNode;
		}
	}
}

4.1.2 森林與二叉樹之間的轉換

樹 ? \Rightarrow ? 二叉樹

p180

1. 加線
2. 刪線
3. 旋轉

根據演算法可得，任何一棵樹對應的二叉樹的根節點右子樹一定為空，

二叉樹 ? \Rightarrow ? 樹

p180-181

逆程序

1. 加線
2. 刪線
3. 旋轉

二叉樹 ? \Rightarrow ? 森林

p182

先把二叉樹切分成子二叉樹，再分別轉為樹

設 B B B是一顆二叉樹， r o o t root root是 B B B的根節點， L L L是 B B B的左子樹， R R R是右子樹，并且 B B B對應的森林 F ( B ) F(B) F(B)中含有 n n n棵樹： T 1 , T 2 , … , T n T_1,T_2,\dots,T_{n} T1?,T2?,…,Tn?，則二叉樹 B B B可按照如下規則轉換成森林 B ( F ) B(F) B(F)：

1. 若 B B B為空，則 F ( B ) F(B) F(B)為空森林
2. 若 B B B不為空，則 F ( B ) F(B) F(B)中第一棵樹 T 1 T_1 T1?的根節點為二叉樹 B B B中的根節點， T 1 T_1 T1?中根節點的子樹森林由B的左子樹 L L L轉換而成，即 F ( L ) = { T 11 , T 12 , … , T 1 m } F(L)=\{T_{11},T_{12},\dots,T_{1m}\} F(L)={T11?,T12?,…,T1m?}，B的右子樹R轉換成F(B)中其余樹組成的森林，即 F ( R ) = { T 2 , … , T n } F(R)=\{T_2,\dots,T_n\} F(R)={T2?,…,Tn?}

4.2 將兩個帶頭結點的回圈鏈表合成一個回圈鏈表

p50-51

五、排序演算法

5.1 冒泡排序

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復雜度： O ( 1 ) O(1) O(1)
• 穩定

public static void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length -1; i++) {
        for(int j = 0; j < arr.length - 1 - i; j++) {
            if(arr[j] > arr[j+1]) {
                //開始進行比較，如果arr[j]比arr[j+1]的值大，那就交換位置
                //保證大的數在后，小的數在前
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

5.2 選擇排序

每一次都查詢余下區間的極值并插入到有序序列的末端

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復雜度： O ( 1 ) O(1) O(1)
• 不穩定

public static void selectSort(int[] arr) {
    
    for (int i = 0; i < arr.length; i++) {
        // 查找獲取剩下區間的最小值下標
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 下標發生改變則調換元素，
        // 否則說明當前元素在正確的位置上，不用調換
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        
    }
}

5.3 直接插入排序

每一次將記錄直接插入到有序序列的適當位置

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)
• 空間復雜度： O ( 1 ) O(1) O(1)
• 穩定

不帶監視哨

/**
 * 插入排序
 * @param arr
 */
public static void insertSort(int[] arr) {
	// 默認第一個數已經排序好，從下標1開始
	for (int i = 1; i < arr.length; i++) {
		// 將要插入的第i條記錄暫存在temp中
		int insertValue = arr[i];
		// 將有序序列中比temp大的記錄后移
		int j = i - 1;
		while ((j >= 0) && (insertValue < arr[j])) {
			arr[j+1] = arr[j];
			j--;
		}
		// 因為最后還有j--才退出回圈，所以要j++
		arr[j+1] = insertValue;
	}
}

帶監視哨

每一次都將要插入的資料放在arr[0]處

遍歷到最后一輪時，j==0，則arr[0]==arr[k]，自動退出回圈，省去判斷下標越界的操作

/**
 * 直接插入排序-帶監視哨
 * @param arr
 */
public static void insertSortWithGuard(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
		// 將要插入的第i條記錄暫存在arr[0]中，arr[0]作為監視哨
		arr[0] = arr[i];
		// 將有序序列中比temp大的記錄后移
		int j = i - 1;
		// 遍歷到最后一輪時，j\==0，則arr[0]\==arr[k]，自動退出回圈
         // 省去判斷下標越界的操作
		while (arr[0] < arr[j]) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = arr[0];
	}
}

5.4 希爾排序

又稱縮小增量排序，每一次選擇不同的增量，將資料劃分成不同的組，每一次對單個組進行插入排序，并不斷縮小增量，直到有序

• 時間復雜度：取決于增量的選擇， [ O ( n 1.3 ) , O ( n 2.0 ) ] [~O(n^{1.3}),~O(n^{2.0})~] [ O(n1.3), O(n2.0) ]
• 空間復雜度： O ( 1 ) O(1) O(1)
• 不穩定

/**
 * 希爾排序
 * @param arr
 * @param incres 增量陣列increments
 */
public static void shellSort(int[] arr, int[] incres) {
	// 因為用得多所以不在回圈內定義
	int temp;
	// 遍歷增量陣列，interval為間隔
	for (int interval : incres) {
		// 分組，進行插入排序
		for (int i = interval; i < arr.length; i++) {
			temp = arr[i];

			// 后移
			int j;
			for (j = i - interval; j >= 0 && temp < arr[j]; j -= interval) {
				arr[j + interval] = arr[j];
			}
			// 插入
			arr[j + interval] = temp;
		}
	}
}

5.5 快速排序

是冒泡排序的改進

通過一趟排序將要排序的資料分割成兩部分，其中一部分的所有資料都比另一部分的所有資料小，然后再以同樣的方法對兩個子部分的資料進行快速排序，最終得到有序序列

• 時間復雜度：平均 O ( n log ? 2 n ) O(n\log_2n) O(nlog2?n)
• 空間復雜度：遞回 O ( log ? 2 n ) O(\log_2n) O(log2?n)
• 不穩定

public static void quickSort(int[] arr) {
	quickSort(arr, 0, arr.length - 1);
}

/**
 * @param arr   排序陣列
 * @param left  左哨兵
 * @param right 右哨兵
 */
public static void quickSort(int[] arr, int left, int right) {
	// 如果兩個哨兵相遇，則結束回圈
	if (left < right) {
		// 以最左邊的數作為中心點(pivot)
		int i = left, j = right, pivot = arr[left];
		while (i < j) {
			// 從右向左找第一個小于x的數
			while (i < j && arr[j] >= pivot) {
				j--;
			}
			if (i < j) {
				// 退出回圈有兩種情況，i > j 或者 arr[j] < pivot
				// 如果能夠進入該if陳述句說明是arr[j] < pivot，可以交換
				arr[i++] = arr[j];
			}
			// 從左向右找第一個大于等于pivot的數
			while (i < j && arr[i] < pivot) {
				i++;
			}
			if (i < j) {
				arr[j--] = arr[i];
			}
		}
		arr[i] = pivot;
		/*
		至此完成了一次移位調換
		int pivot = arr[i];
		arr[i++] = arr[j];
		arr[j--] = arr[i];
		...
		...
		arr[i] = pivot;
		 */
        
		// 遞回呼叫
		quickSort(arr, left, i - 1);
		quickSort(arr, i + 1, right);
	}
}