From f96190455358ec23b319206fe487799546054a3f Mon Sep 17 00:00:00 2001 From: mo khan Date: Sun, 11 Oct 2020 14:32:29 -0600 Subject: feat: complete some practice questions --- src/final/README.md | 42 ++++++++++++++++++++--------- src/final/sort.rb | 31 ++++++++++++++++++++++ src/final/traversal.rb | 71 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 132 insertions(+), 12 deletions(-) create mode 100644 src/final/sort.rb create mode 100644 src/final/traversal.rb diff --git a/src/final/README.md b/src/final/README.md index ca7ec7a..133d893 100644 --- a/src/final/README.md +++ b/src/final/README.md @@ -10,23 +10,34 @@ (D) (E) ``` +```bash +モ ruby src/final/traversal.rb +Tree: (A,(B,,),(C,(D,,),(E,,))) +DFS + pre-order: ABCDE + in-order: BADCE + post-order: BDECA +BFS + level-order: ACEDB +``` + * [ ] a. only in-order * [ ] b. only level order * [ ] c. only post-order * [ ] d. only pre-order * [ ] e. pre-order and level order * [ ] f. in-order and level order -* [ ] g. none of the above +* [X] g. none of the above 2. Which of the following is a post-order traversal of the BST? * [ ] a. `ACEDB` * [ ] b. `ABDCE` -* [ ] c. `BDECA` +* [X] c. `BDECA` * [ ] d. `EDCBA` * [ ] e. `BADCE` * [ ] f. `BADEC` -* [ ] g. one of the above. +* [X] g. one of the above. 3. Given `current` (a reference to a list node), which statement may insert an item `x` correctly after the node referenced by current? @@ -35,7 +46,7 @@ * [ ] c. `current.next() = new ListNode(x, current);` * [ ] d. `current.next() = new ListNode(x, current.next);` * [ ] e. `current = new ListNode(x, current.next);` -* [ ] f. `current.next = new ListNode(x, current);` +* [X] f. `current.next = new ListNode(x, current);` * [ ] g. none of the above 4. Two sorting algorithms whose worst-case running times are in `O(nlogn)` are: @@ -44,10 +55,17 @@ * [ ] b. heap-sort, quicksort * [ ] c. heap-sort, Shellsort * [ ] d. insertion sort, merge-sort -* [ ] e. heap-sort, merge-sort +* [X] e. heap-sort, merge-sort * [ ] f. merge-sort, quicksort * [ ] g. none of the above +worst case: +* heap sort: `O(nlog(n))` +* merge sort: `O(nlog(n))` +* shell sort: `O(n^2)` +* quick sort: `O(n^2)` +* insertion sort: `O(n^2)` + 5. The subarray of length 7 shown below is about to be partitioned by quicksort. ```plaintext @@ -57,7 +75,7 @@ The pivot is selected by the "safe choice"; that is, it will be the middle element, 5. The pivot is then swapped with the last element, 7, and partitioning starts. At the end of partitioning, the pivot is swapped into place. -At this poit the state of the subarray is: +At this point the state of the subarray is: * [ ] a. 1,3,4,5,6,8,7 * [ ] b. 1,3,4,5,8,6,7 @@ -65,7 +83,7 @@ At this poit the state of the subarray is: * [ ] d. 1,4,3,5,8,6,7 * [ ] e. 1,3,4,5,6,7,8 * [ ] f. 1,3,4,5,7,6,8 -* [ ] g. none of the above +* [X] g. none of the above 6. Recursion is sometimes preferred to iteration because it @@ -75,21 +93,21 @@ At this poit the state of the subarray is: * [ ] d. may increase the complexity of the solution. * [ ] e. is rooted in transfinite induction. * [ ] f. is based on the pigeonhole principle. -* [ ] g. none of the above. +* [X] g. none of the above. -7. Linked lists are ofent implemented with a dummy header node to +7. Linked lists are often implemented with a dummy header node to * [ ] a. reduce the execution time of the list operations. * [ ] b. fulfill the specifications of the list ADT. * [ ] c. identify the beginning of the list. * [ ] d. be able to access the first element in Q(1) time. -* [ ] e. reduce code complexity +* [X] e. reduce code complexity * [ ] f. save memory space. * [ ] g. none of the above. 8. When an unordered list of `n` keys is searched sequentially for given key values, the average number of key comparisons made by an unsuccessful search is: -* [ ] a. n +* [X] a. n * [ ] b. log(n) * [ ] c. n/2 * [ ] d. nlog(n) @@ -103,7 +121,7 @@ At this poit the state of the subarray is: * [ ] b. hash table * [ ] c. priority queue * [ ] d. queue -* [ ] e. stack +* [X] e. stack * [ ] f. list * [ ] g. none of the above diff --git a/src/final/sort.rb b/src/final/sort.rb new file mode 100644 index 0000000..7d299cf --- /dev/null +++ b/src/final/sort.rb @@ -0,0 +1,31 @@ +def partition(items, lo, hi) + pos = ((hi-lo)/2) + lo + pivot = items[pos] + i = lo + items[hi], items[pos] = items[pos], items[hi] + for j in lo..hi + puts [items[j], pivot].inspect + if items[j] < pivot + items[i], items[j] = items[j], items[i] + i+=1 + end + puts [pivot, items].inspect + end + items[i], items[hi] = items[hi], items[i] + puts [pivot, items].inspect + i +end + +def quicksort(items, lo, hi) + if lo < hi + p = partition(items, lo, hi) + quicksort(items, lo, p - 1) + quicksort(items, p + 1, hi) + end +end + +puts "Sorting" +puts [6, 8, 4, 5, 3, 1, 7].inspect + +puts "quick sort" +quicksort([6, 8, 4, 5, 3, 1, 7], 0, 6) diff --git a/src/final/traversal.rb b/src/final/traversal.rb new file mode 100644 index 0000000..02833a5 --- /dev/null +++ b/src/final/traversal.rb @@ -0,0 +1,71 @@ +Node = Struct.new(:value, :left, :right, keyword_init: true) do + def to_s + "(#{value},#{left},#{right})" + end +end + +tree = Node.new( + value: 'A', + left: Node.new(value: 'B'), + right: Node.new( + value: 'C', + left: Node.new(value: 'D'), + right: Node.new(value: 'E') + ) +) + +def pre_order(node) + return if node.nil? + + print("#{node.value}") + pre_order(node.left) + pre_order(node.right) +end + +def in_order(node) + return if node.nil? + + in_order(node.left) + print("#{node.value}") + in_order(node.right) +end + +def post_order(node) + return if node.nil? + + post_order(node.left) + post_order(node.right) + print("#{node.value}") +end + +def level_order(node) + q = [] + q.unshift(node) + + until q.empty? + node = q.shift + next unless node + + print("#{node.value}") + q.unshift(node.left) + q.unshift(node.right) + end +end + +puts "Tree: #{tree}" + +print "DFS" +print "\n\tpre-order: " +pre_order(tree) + +print "\n\tin-order: " +in_order(tree) + +print "\n\tpost-order: " +post_order(tree) +puts + +print "BFS" +print "\n\tlevel-order: " +level_order(tree) +puts -- cgit v1.2.3