Data Structures and Algorithms

True, AVL Tree are more balanced than Red-Black Tree

BFS用?實作

Queue

DFS用?實作

Stack

List can be constructed to a BST with worst case O(n)

False, skewed tree will have worst case O(n²)

“The height of tree is n and there are n elements“

Quick Sort: Best/Avg/Worst(when?)

O(nlogn)/O(nlogn)/O(n^2). When the data are sorted

Merge Sort: Best/Avg/Worst

O(nlogn)/O(nlogn)/O(nlogn)

Insertion Sort:Best(when?)/Avg/Worst

O(n)/O(n^2)/O(n^2)/  when the data are sorted

Selection Sort:Best/Avg/Worst

O(n^2)/O(n^2)/O(n^2)

Which is not stable sorting algorithm: Bubble,Insertion,Selection,Merge,Quick,Heap,Counting,Radix,Bucket

Selection,Quick,Heap

If a weighted graph with weight w_i\geq0  , then if a new graph with w_i+M,M\geq0 , the shortest path will remain the same.

False, 如果該shortest path有比較多edge，則他有可能不復為最短路徑

Have Euler Circuit

Every nodes have even degree

Have Euler Path

Only 2 nodes have odd degree

Preorder

中左右

Inorder

左中右

Postorder

左右中

Time complexity of 0-1 knapsack

O(nW) w is the size of the backpack

Time complexity for k-coloring problem when
1.k <= 2 
2. k >=3 

1. O(V+E) ( 判斷是否為二分圖)
   2. NP-C

二分圖一定沒有 WHAT?

奇環

A degree = t b tree's node can have at most ? key and ? child. Also the relation between degree and order?

degree=\lceil\frac{order}{2}\rceil
keys = 2t-1
child = 2t

It’s possible to run radix sort in linear time with respect to the length of the list

"True, but only when the length of elements are all fixed, otherwise it will be O(kn) k for digit,n for # of elements"

AD