1) What is the max height of a tree with 15 internal nodes? a) 6 b) 4 c) 10 d) 8 2) What is the formula for calculating the max height of a RBT with n internal nodes? a) 2(lgn + 1) b) 2(lgn) c) lgn+1 d) 2(lgn-1)+1 3) What's the time complexity of bucket sort? a) O(n) b) ɵ(n) c) ɵ(n2) d) O(n2) 4) To sort n elements, comparison sorts must make _____ comparison in the worst case a) Ω(nlgn) b) Ω(lgn) c) Ω(n) d) O(n) e) ɵ(n2) 5) What is the time complexity of radix sort? a) O(N+K) b) O(d(N+K)) c) O(NK) d) O(d(K)) 6) What is the time complexity of counting sort ? a) O(n+k) ; r = O(n) b) O(n+k) ; r = O(n2) c) O(n) ; r = O(n) d) O(k) ; r = O(n) 7) What is the worst case of Quicksort? a) O(n) b) O(n^2) c) O(nlgn) 8) What is the best case of Quicksort? a) O(lgn) b) O(n2) c) O(nlgn) 9) What is the best case of a hash table? a) O(n2) b) O(n) c) O(1) 10) What is the worst case of a hash table? a) O(n) b) O(1) c) O(n2) 11) A binary tree of height h has at most ___ leaves a) h2 b) 2h c) 2*h 12) A BST has a time complexity of ___ a) O(n2) b) O(nlgn) c) O(lgn) 13) How many leaves does a decision tree have at least? a) n b) nlgn c) n! 14) Which of the following is not a method to handle collisions in hash tables? a) chaining b) linear probing c) double hashing d) sorting e) quadratic probing f) open addressing 15) What do the leaves in a decision tree represent? a) all possible permutations b) the end of a branch 16) Which of the following does not make a good hash function? a) m is not a power of 2 b) m is not a prime number c) m is a power of 2 17) What is the load factor of a hash function and what does it represent? a) a = n/m ; the avg elements stored in the universe b) a = n/m ; the avg elements stored in a chain c) a = n/m ; the avg elements stored in the hash table d) a = m/n ; the avg elements stored in a chain e) a = m/n ; the avg elements stored in a chain 18) Which of the following uses 2 hash functions? a) quadratic probing b) linear probing c) double hashing 19) T/F, We include node x when counting the black height of node x? a) T b) F 20) T/F, a subtree has at least 2 bh(x) -1 internal nodes a) T b) F 21) T/F, min, max, successor, and predecessor all have a running time of O(lgn), but not search. a) T b) F 22) T/F, a newly inserted node within a RBT is always red a) T b) F 23) T/F, when rotating right right(x) = left(y) a) T b) F 24) T/F, when rotating left left(y) = right(x)   a) T b) F 25) Case 1 does not include the following: a) z is a left child b) z's uncle is red c) z's grandparent is black d) z is black 26) T/F, case 3 is when z is a left child and it's uncle is black a) T b) F 27) Which direction do you rotate in case 2? a) left b) right c) no rotation

CSCI 115 Exam 2 prep

par
Incorporer

Classement

Style visuel

Options

Changer de modèle

Restauration auto-sauvegardé :  ?