# 期末考複習筆記
## 尚未打加入筆記
1. DAG :有方向的圖
2. min spanning tree :https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/zui-xiao-sheng-cheng-shu
3. Prim’s algorithm：https://ithelp.ithome.com.tw/articles/10205823
4. Kruskal's Algorithm：https://ithelp.ithome.com.tw/articles/10205466
5. Dijkstra's Algorithm：https://ithelp.ithome.com.tw/articles/10206105
6. Floyd Algorithm: https://ithelp.ithome.com.tw/articles/10209186
## 資料結構
## part6 Tree
### List Representaion
#### GetDeapth

Algorithm depth(T, v):
  If T.isRoot(v) then
      return 0
  else
      return 1+depth(T, T.parent(v))

#### GetHeight

Algorithm heigh1(T):
  h=0
  for each vT do
      if T.isExternal(v) then
        h=max(h, depth (T, v))
  return h

#### 前序中序後序

Algorithm preOrder(v)
visit(v)
for each child w of v
	preorder (w)

Algorithm postOrder(v)
for each child w of v
	postOrder (w)
visit(v)

## 1
> 1. (10 pts) Mark by T(=true) or F(=False) each of the following statements. You don’t
> need to prove it. Let G be an undirected graph. We use m and n to denote the number
> of edges and vertices, respectively.
> (1) For G, the maximum possible value of m is n(n + 1).
> (2) If G is connected and has exact n − 1 edges, then Q has no cycle.

### 1
Ans : False
解釋: 它是無向圖 1->2 跟 2->1 一致，所以我們可以這麼計算
N個頂點都可以連接到(N-1)個節點，但依照上面的解釋，我們必須/2

所以這個無向圖:m = n(n-1)/2

### 2
Ans: True
解釋:我們可以嘗試建立一個來看看會有甚麼問題
若有三個點我們可以製作出有環的情形為
G={(1,2),(2,3),(3,1)}
G={(1,2),(2,1),(1,3)}(X不存在，因為是無向圖)

所以我們只有第一個可能性，但我們的限制是n-1條邊，不符合

正式證明:
cycle = n root,will need n+1 edge
so We have m root
Suppose: x root is in cycle(x<=n)
we should use x+1 edge
we remain n-x root
we need to connect to graph need n-x edge

so we need x+1+n-x edge = n+1 edge
so n-1 edge undirect graph no cycle

## 2
> (20 pts) Mark by T(=True) or F(=False) each of the following statements. You don’t
> need to prove it. All the definitions are according to the textbook and the classnotes.
> (1) Let T be a B-tree of order 5, the possible degrees of internal nodes (except the root)
are 2, 3, 4, and 5.
(2) When inserting a node to an AVL tree, the height-balance property may not be
restored with at most one restructuring.
(3) The preorder and inorder traversal can UNIQUELY define a binary tree.
(4) Suppose one uses an unsorted list to implement a priority queue P. Then, the sort
using P is known as Selection sort.
### 1
> 它會有order m代表它的節點分支量最多為m
> 1. 根至少要有2個節點
> 2. 每個內部節點分支量最低為[m/2] *m/2<=degree<=m
> 3. 葉節點都要在同一層

**Ans: False**
依照公式 degress應該在
ceil(m/2)<=degree<=m
帶入5
答案為3,4,5

### 2(*)
插入時若超過key的最大上限，我們只能夠做分割
ex:
分割有可能會分割log(n)
**Ans: True**
因為它切割新的child可能會讓他的parent超出限制，所以又要對parent做一次切割
### 3
**Ans: True**
https://yongjhih.medium.com/%E5%BE%9E%E5%89%8D%E5%BA%8F%E8%88%87%E4%B8%AD%E5%BA%8F%E5%BB%BA%E6%A7%8B%E4%BA%8C%E5%85%83%E6%A8%B9-a8825340d491
### 4
**Ans:True**
https://www.cyut.edu.tw/~ckhung/b/al/heap.php
| Column 1 | insert | remove | change | is_empty | search |
| -------------- | ------ | ------ | --------- | -------- | ------ |
| unsorted array | O(1) | O(n) | srch+O(1) | O(1) | O(n) |
Sort time = O(n * (新增耗時 + 刪除耗時)) = O(n * (n)) = O(n^2) 根 select sort依樣

## 3(skip)
> 3. (20pts) Mark by T(=true) or F(=False) each of the following statements. You don’t need
> to prove it. For the following statements about red-black trees, provide a justification for
> each statement.
> (1) A subtree of a red-black tree is itself a red-black tree.
> (2) The sibling of an external node is either external or it is red.
> (3) There is a unique (2, 4) tree associated with a given red-black tree.
> (4) There is a unique red-black tree associated with a given (2, 4) tree
https://youtu.be/xIp8HsOXrBU
### 1
Ans: True 兩邊都是AVL
### 2
Ans: True 定義上每個新的節點都是紅色
### 3
Ans: False 因為2,4可能會有三個分段點，與紅黑樹不同，無法製造出唯一個Tree
### 4
Ans: True 因為2,4tree 分段點允許 2個節點，並且其餘限制也滿足red black樹條件
## 4
> (15 pts) What is the dictionary ADT? (5 pts) What’s the difference between map and
> dictionary data structures? (5 pts) As we learned, a hash table can be used to implement
> a dictionary. Draw the 11-entry hash table that results from using the hash function,
> h(i) = (2i + 5) mod 11, to hash the keys 34, 22, 2, 88, 23, 72, 11, 39, 20, 16, and 5,
> assuming collisions are handled by linear probing. (5 pts)
### 1
### 2
兩個插在，Map不允許一個映射值有兩個數值，但Dict允許
### 3
https://ithelp.ithome.com.tw/articles/10246777

#include<iostream>
#include<set>
using namespace std;
int f(int x){
  return 2*x+5  ;
}
signed main(){
    int data[] = {4, 22, 2, 88, 23, 72, 11, 39, 20, 16, 5};
    int hash[11]={0};
    for(int i=0;i<11;i++){
        int k=0;
        while(hash[ (f(data[i])+k)%11]!=0){
            k++;
            continue;
        }
        hash[(f(data[i])+k) %11]=data[i];
    }
    for(int i=0;i<11;i++)
        cout<<hash[i]<<" ";
}

Ans : 39 20 4 5 16 22 88 23 72 2 11
## 5
> 5. (15 pts) Suppose that we have the following key values: 32, 20, 49, 82, 5, 13, 6, 24, 52.
> (1) (5 pts) Please show the min-heap built by insertion.
> (2) (5 pts) Suppose we use an array to represent this min-heap. Please show the corresponding array for the min-heap your derived in (1).
> (3) (5 pts) Using the min-heap derived in (1), execute an extract-min operation and
> draw the result step by step.
### 1
### 2
Ans : [5,20,6,24,32,49,13,82,52]

### 3

## 6
> 6. (20 pts) (Not Covered) Figure ?? is a graph G = (V, E). Please answer the following
> questions respectively.
> 1
> Figure 1: A graph G considered in Problem ??
> (1) (5 pts) (True or False) Is G biconnected?
> (2) (5 pts) How many biconnected components are in G?
> (3) (5 pts) Please give the articulation points. If there is no articulation point, please
> use ∅ to denote it.
> (4) (5 pts) Suppose we are performing a BFS starting with vertex a in alphabetical order.
> Please show the corresponding BFS-tree.
#### 定義
1. Biconnected graph: A graph with no articulation point called biconnected. In other words, a graph is biconnected if and only if any vertex is deleted, the graph remains connected.
2. articulation point:An Articulation point in a connected graph is a vertex that, if delete, would break the graph into two or more pieces (connected component).
#### 人話
1. 一個刪除任何節點，每個節點還是可以到達的圖
2. 關鍵點，刪除他圖就被分成兩張圖
#### 1
判斷是否有關鍵點
https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji-2/tu-xing-yan-suan-fa-guan-jie-dian-articulation-point
#### 2
biconnected components:拆開就會變成兩個不連通單元
#### 3
同一
#### 4
BFS搜尋，
## 7
(1) (5 pts) (True or False) Is D strongly connected? Why?
(2) (5 pts) Please give a linear time O(|V | + |E|) algorithm to verify whether a given a
digraph is strongly connected.
### 1
每個點可以到每一個節點
### 2

function alogrith(v){
    bool visted[n] let all False;
    stack p={0};
    queue q={0};
    while (visted all is True or p.isempty()){
        for (p.top all child as ch)
            if(visted[ch]==False){
                p.push(ch)
                q.push(ch)
                visted[ch]=True
                contiune
            }
               
        p.pop();
    }
    if(p.isempty())
        print("not strong connect");
    revese graph;
    visted[n] let all False;
    q = stack(q)
    p = {}
    while(!q.isempty()){
        if(visted[q.top]==True)
            q.pop
        points = dfs form q.top() find have visted point until visted point
        print(points is Scc)
    }
}