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

Time Complexity of Floyd Warshall

O(V^3)

Time Complexity of Dijsktra

O(VlgV+E) using Fibonacci Heap

O(VlgV+ElgV) using Binary Heap

Time Complexity of Bellman Ford

O(VE)

Conversion between Red-Black Tree and 2-3-4 Tree

紅節點與父節點合併，black depth為height

False, Trie不是BST

m-nary tree has how many Internal and External node

L=(m-1)I+1
|E|=n-1=I+L-1

Every tree is a bipartite graph

True

An AVL tree with height = h has node’s n >= ?

n\geq F_{h+2}-1

Time Complexity of Strassen’s Matrix Multiplication

O(n^{log_{2}{7}})

The number of degree 0 nodes in a tree

#deg(2)+1

B+ Tree

A B tree that store data only in leaf， 利於執行連續搜尋3

The number of spanning in complete graph K_n

n^{n-2}