# Shared Flashcard Set

## Details

COP4531-Final exam
final exam
21
Computer Science
11/29/2009

Term
 Begin with the vector v = [ 50 , 20 , 40 , 10 , 5 , 30 , 45] .Show the vector after fsu::g_push_heap(v.Begin(), v.End()).
Definition
 v = [ 50 , 20 , 45 , 10 , 5 , 30 , 40 ]
Term
 COMPARISON SORT IS STABLE AND HAS BEST POSSIBLE WCRT?
Definition
 MERGE SORT
Term
 WHAT SORT IS STABLE, IN PLACE AND HAS BEST POSSIBLE WCRT?
Definition
 NONE
Term
 Begin with the vector v = [ 50 , 30 , 40 , 5 , 10 , 20 ].Show the vector after v.PushBack(45).
Definition
 Correct Answer: v = [ 50 , 30 , 40 , 5 , 10 , 20 , 45 ]
Term
 Code implementing merge_sort (A, p, r) for the index range [p,r)in the array is:
Definition
 void merge_sort(int* A, size_t p, size_t r){  if (r - p > 1)  {    q = (p+r)/2;    merge_sort(A,p,q);    merge_sort(A,q,r);    merge(A,p,q,r);   // defined in separate function using g_set_merge  }}
Term
 Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int). What, for a general binary tree, should the sum of all edge moves in an inorder traversal be? (n = size)
Definition
 2n
Term
 (!) What is the theoretical lower bound on the worst case asymptotic runtime for comparison sorts? (n = size of input)
Definition
 Ω (n log n)
Term
 The following sorts are stable
Definition
 Bit Sort Radix Sort Insertion Sort Counting Sort Merge Sort
Term
 (!) You are given the following declarations: fsu::TBinaryTree bt;fsu::TBinaryTreeInorderIterator i; Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int). For the bt = tree1 illustrated, complete the table of numbers of edge moves on the exam paper, showing the number of edge moves for each step in an inorder traversal. step                   no. of edge moves----                   -----------------                                                            Ai = bt.Begin();                                            / \                                                          B   C++i;                                                         / \                                                            D   E++i;                                                           [tree1]++i; ++i; ++i; The sequence of numbers of edge moves is:
Definition
 2 1 2 1 1 3
Term
 The worst case run time [WCRT] for TBinaryTree<>::Iterator::operator++() (where n = size of the tree) is:
Definition
 O(n)
Term
 The run space requirement of Bit Sort (n = size of input) is
Definition
 +Θ(n)
Term
 Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int). What does the calculation of the number of edge moves in a traversal illustrate about the computational complexity of the iterator increment operator fsu::TBinaryTreeInorderIterator<>::operator++() ? (n = size of tree)
Definition
 That it is amortized Θ(1)
Term
 Deriving the theoretical lower bound on the worst case asymptotic runtime for comparison sorts uses (select all that apply)
Definition
 The minimum height of a binary tree with N leaves The number of permutations of n items  Stirling's Formula  A decision tree
Term
 The run space requirement of Bit Sort ( n= size of input) is:
Definition
 +Θ (n)
Term
 What is the theoretical lower bound on the worst case asymptotic runtime for comparison sorts? (n = size of input)
Definition
 Ω(n log n)
Term
 The following comparison sort is stable and has the best possible worst case runtime:
Definition
 Merge Sort
Term
 Begin with the vector v = [ 50 , 30 , 40 , 5 , 10 , 20 ]. Show the vector after v.PushBack(45).
Definition
 v = [ 50 , 30 , 40 , 5 , 10 , 20 , 45 ]
Term
 The worst case run time [WCRT] for TBinaryTree<>::Iterator::operator++()(where n is the size of tree) is:
Definition
 O( n)
Term
 Given the array a = [ F , G , A , H , B , D ] show the result of the first call to Partition in Quick Sort with the pivot value chosen to be the last element of the array.
Definition
 [ A , B , D , H , G , F ]
Term
 A comparison sort is:
Definition
 A sort in which decisions are made based on key comparisons.
Term
 Deriving the theoretical lower bound on the worst case asymptotic runtime for comparison sorts uses (select all that apply)
Definition
 A decision treeStirling's FormulaThe number of permutations of n The minimum height of a binary tree with N
Supporting users have an ad free experience!