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?

奇環

B tree with Degree = T

degree=\lceil\frac{order}{2}\rceil

Max Child = 2t; Min child = t
Max Key = 2t-1; Min Key = t-1

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

N=mI+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}

DP/Divide and Conquer

DP問題有重複

Rabin-Karp

利用Hash

Boyer-Moore

利用Bad/Good Character

n^k k>1

比任何nlog^t(n)還要成長的快

Topological Sort

Kahn’s Algorithm，每次取出只出不進的點

Deletion for BST/AVL

補上Inorder Successor

Number of Node in a full BST with L leaf nodes

N=2L-1

For a bipartite graph to have Hamilton Path

|M-N| = 1

# of invalid stack sequence

Catalan Number

B tree with Order = M

Max Child = M; Min Child = ceil(M/2)

Max Key = M-1; Min Key = ceil(M/2)-1

Extended Master Therom

Let\ T(n)=aT(\frac{n}{b})+n^Elog^kn
1.n^{log_b^a}=n^E
2.k<(-1)=>O(n^E)
3.k=(-1)=>O(n^Elog(logn))

4.k>(-1)=>O(n^Elog^{k+1}n)

Q_{n+1}\ has\ V_{n+1}=?\ E_{n+1}=?

Q_n+1為兩個Qn再補上缺的邊=>V_{n+1}=2V_{n},E_{n+1}=2E_{n}+V_{n}

Find a longest simple path between two nodes (positive edge weights)

NP-H

Find a shortest simple path... with negative weight cycles

NP-H

Find a positive weight directed cycle

P

Find a largest cycle in a graph (edge-weight 1)

NP-H

Find a smallest cycle in a graph (edge-weight 1)

P

Find a maximum cut in a flow network

NP-H

The 2-CNF-Satisfiability problem

P

3-SAT

NP-C