# DS final exam answer

## part I (15%)

#### (1) b
#### (2) c
#### (3) d

## part II (85%)

### problem 1 (20%)

queue que;
que.push(first node); // 加入第一個節點
// n 為 節點數
bool visit[n] ={0}; // 0 :not visited , 1 : visited

while(!que.empty()){ // 不是空的繼續
    cur_node = que.front(); //拿出目前節點
    que.pop(); // 拿出後移除該節點
    if(visit[cur_node]){ // vitisted 過
        continue; // 下一輪
    }
    visit[cur_node] = 1 ; // 將此節點改成visited
    foreach neighbor_node in cur_node{ //找出目前節點的相鄰節點
        que.push(neighbor_node); // 將相鄰節點加入到queue中
    }
}

queue = {} 
first_node = 1;

放 1 到 queue ; current queue : {1}
拿出最前面的 1，並移除; current queue : {}
檢查 1 是否 尋訪 => 沒有
放相鄰點 : 2 , 4 ; current queue : {2,4}

拿出最前面的 2，並移除; current queue : {4}
檢查 2 是否 尋訪 => 沒有
放相鄰點 : 3 ; current queue : {4,3}

拿出最前面的 4，並移除; current queue : {3}
檢查 4 是否 尋訪 => 沒有
放相鄰點 : 3 , 5 ,6 ; current queue : {3 ,3 ,5 ,6}

拿出最前面的 3，並移除; current queue : {3 ,5 ,6}
檢查 3 是否 尋訪 => 沒有
放相鄰點 : 5 ; current queue : {3,5,6,5}

拿出最前面的 3，並移除; current queue : {5 ,6 ,5}
檢查 3 是否 尋訪 => 有

拿出最前面的 5，並移除; current queue : {6 ,5}
檢查 5 是否 尋訪 => 沒有
放相鄰點 : 3 ,5 ; current queue : {6 ,5 ,3 ,5}

拿出最前面的 6，並移除; current queue : {5 ,3 ,5}
檢查 6 是否 尋訪 => 沒有
放相鄰點 : 4 ; current queue : {5 ,3 ,5 ,4}

拿出最前面的 5，並移除; current queue : {3 ,5 ,4}
檢查 5 是否 尋訪 => 有

拿出最前面的 3，並移除; current queue : {5 ,4}
檢查 3 是否 尋訪 => 有

拿出最前面的 5，並移除; current queue : {4}
檢查 5 是否 尋訪 => 有

拿出最前面的 4，並移除; current queue : {}
檢查 4 是否 尋訪 => 有

queue 為空 : 結束

#### 評分標準

1. 邏輯對 : 15%
3. 範例說明如何找 : 5%

### problem 2 (20%)
#### (a)

AB&&C||EF>!||

#### (b)

ABC<CD>||!&&!CE<||

#### 評分標準

1. 寫對才有分

### problem 3 (10%)

int  Chain:Length(){
    int length = 0; // 初始長度 = 0 
    // 每個都尋訪，走一次加1
    for(ChainNode *current =first; current!=0;currnet=current->link){
        length++; 
    }
    // 回傳
    return length;
}

Time complexity = O(length of list) or O(n) 

#### 評分標準

1. 寫成function : 3%
2. 內部邏輯對 : 5%
3. 時間複雜度 : 2%

### problem 4 (15%)
#### (a)

1. {0,5} : 10
2. {2,3} : 12
3. {1,6} : 14
4. {1,2} : 16
5. {4,3} : 22
6. {5,4} : 25

#### 評分標準

1. 有小到大權重畫圖或說明 : 12%
* 畫錯但有解釋會部分給分

#### (b)

#### 99

#### 評分標準

1. 算對才有分

### problem 5 (20%)
#### (a) 5%
##### 插入45

##### 插入20

#### 評分標準

1. 基本上畫對才給分
2. 有步驟、有說明會部分給分
3. 插入一個對3% , 對兩個2%
4. 只寫插入兩個結果，最多4%

#### (b) 15%

##### 插入40

##### 插入50 (left bias)
##### 插入50 (right bias)

#### 評分標準

1. 基本上畫對才給分
2. 有步驟、有說明會部分給分
3. 插入一個對8% , 對兩個15%
4. 只寫插入兩個結果，最多12%