# Shared Flashcard Set

## Details

Mid Term
N/A
53
Computer Science
02/18/2015

Term
Definition
Term
 Select the answer that best describes the asymptotic runtime of the operation       fsu::Vector:: Destructor   Here n is the size of the vector.
Definition
 Θ(n)
Term
 An abstract data type [ADT] consists of the following.
Definition
 A collection of data of some type T A set of operations on the data Axioms, or rules, governing the way operations interact
Term
 Select the most appropriate statement for the asymptotic runtime for the binary_search algorithm with input size n.
Definition
 Θ(log n)
Term
 Declare an fsu::Queue object q with elements of type fsu::String and underlying container fsu::List.
Definition
 fsu::Queue < fsu::String , List < fsu::String > > q;
Term
 The following represents output from the call d.Dump() from the fsu::Deque object d: content_[i]: A B C D E F G H I J    i mod 10: 0 1 2 3 4 5 6 7 8 9                    e       b What is the result of the output statement   std::cout << d[5];?
Definition
 C?
Term
 Select the most appropriate statement of the asymptotic runtime for the sequential_search algorithm with input size n.
Definition
 O(n)
Term
 This is an illustration of a vector of characters to be used in answering the question: element: B D F F F H K K M X index:   0 1 2 3 4 5 6 7 8 9 What is the return value of the call upper_bound('N') ?
Definition
 9
Term
 Using a data stack to evaluate the postfix expression 1 2 3 + 4 5 + * 6 + + what is the best representation of the stack during the evaluation?
Definition
 stack --> --------- 1 1 2 1 2 3 1 5 1 5 4 1 5 4 5 1 5 9 1 45 1 45 6 1 51 52
Term
 Consider the following implementation of an fsu::List operation:   template < typename T > ConstListIterator List::Insert (ConstListIterator i, const T& t) {    // 1. create new element    Link* newLink = NewLink(t);    if (newLink == 0) return End();    // 2. link new element into the list    newLink->next_ = i.curr_;    newLink->prev_ = i.curr_->prev_;    /* MISSING LINE OF CODE */    /* MISSING LINE OF CODE */    // 3. leave i at new entry and return    i.curr_ = newLink;    return i; } // end Insert((i,t))   Select the missing TWO LINES of code from the choices below.
Definition
Term
 Searching a vector of size n using the lower_bound algorithm has asymptotic runtime
Definition
 Θ(log n)
Term
 [image]
Definition
 S --> ------------ ... RAC RA RAD RA R RB   RBX
Term
 Suppose that table is a container that implements the Table API. If kval is a key in the table, then table.Retrieve(kval,dval) overwrites the data associated with kval with dval. (True/False)
Definition
 False
Term
 Given the code fragment:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; aa["xxx"] = 1; aa["yyy"] = 2; aa["xxx"] = 3; Display(aa); The result to screen should be (True/False)   xxx : 1 yyy : 2   xxx : 3
Definition
 False
Term
 Copy of Given the code fragment:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; aa["xxx"] = 1; aa["yyy"] = 2; aa["xxx"] = 3; Display(aa);   The result to screen should be (True/False)   1 : xxx 2 : yyy 3 : xxx
Definition
 False
Term
 Suppose that table is a container that implements the Table API. If kval is NOT a key table, then table.Insert(kval,dval) inserts kval into the table associated with data dval. (True/False)
Definition
 True
Term
 Suppose that table is a container that implements the Table API. If kval is a key in the table, the call table.Retrieve(kval,dval) sets dval to be a reference to the data stored with kval in the table and returns 1. (True/False)
Definition
 True
Term
 Suppose that table is a container that implements the Table API. If the key kval is not in the table, the call table.Retrieve(kval,dval) returns false. (True/False)
Definition
 True
Term
 Given the code fragment:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; aa["xxx"] = 1; aa["yyy"] = 2; aa["xxx"] = 3; Display(aa);   The result to screen should be (True/False)   xxx : 3 yyy : 2
Definition
 True
Term
 Suppose the fsu::Deque<> d has elements in sorted order and we wish to insert the element x in correct order in d. The following generic algorithm call returns an iterator to the first correct location to insert x:
Definition
 i = fsu::g_lower_bound(d.Begin(), d.End(),x);
Term
 Select the answer that best describes the asymptotic runtime of the operation fsu::Vector:: bracket operator [i] Here i is an item of type size_t and n is the size of the vector.
Definition
 O(1)
Term
 Select the answer that best describes the asymptotic runtime of the operation Deque::PushBack(t) Here t is an item of type Deque::ValueType and n is the size of the vector.
Definition
 Amortized O(1)
Term
 This is an illustration of a vector of characters to be used in answering the question: element: B D F F F H K K M X   index: 0 1 2 3 4 5 6 7 8 9   What is the return value of the call lower_bound('Y') ?
Definition
 10
Term
 The following represents output from the call d.Dump() from the fsu::Deque object d: content_[i]: A B C D E F G H I J    i mod 10: 0 1 2 3 4 5 6 7 8 9                    e       b   What is the result of the d.Dump() after the call d.PushFront('X') ?
Definition
 content_[i]: A B C D E F X H I J    i mod 10: 0 1 2 3 4 5 6 7 8 9                    e     b
Term
 Suppose that table is a container that implements the Table API. If kval is a key in the table, the call table.Retrieve(kval,dval) sets dval to be a reference to the data stored with kval in the table and returns 1. (True/False)
Definition
 True
Term
 Suppose that table is a container that implements the Table API. If kval is a key in the table, then table.Retrieve(kval,dval) overwrites the data associated with kval with dval. (True/False)
Definition
 False
Term
 Suppose that table is a container that implements the Table API. If kval is a key in the table, then table.Retrieve(kval,dval) overwrites the data associated with kval with dval. (True/False)
Definition
 False
Term
 Suppose that table is a container that implements the Table API. If kval is a key table, then table.Insert(kval,dval) overwrites the data associated with kval with dval. (True/False)
Definition
 True
Term
 Given the code fragment:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; aa["xxx"] = 1; aa["yyy"] = 2; aa["xxx"] = 3; Display(aa);   The result to screen should be (True/False)   xxx : 3 yyy : 2
Definition
 True
Term
 Given the code:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; std::cout << aa["xyz"]; // (1) aa["xyz"] = 20; // (2) std::cout << aa["xyz"]; // (3)   The key "xyz" is inserted into the table at line (3). (True/False)
Definition
 False
Term
 Given the code:   typedef KeyType String; typedef DataType int; AssociativeArray < KeyType, DataType > aa; std::cout << aa["xyz"]; // (1) aa["xyz"] = 20; // (2) std::cout << aa["xyz"]; // (3)   The key "xyz" is inserted into the table at line (1). (True/False)
Definition
 True
Term
 Which of the following are optional (but very desirable) components of an algorithm?
Definition
 RunTime Estimate: Statement of the runtime of the algorithm body, in asymptotic notation, as a function of input size   RunSpace Estimate: Statement of the algorithm runspace requirements, in asympotic "+" notation, as a function of input size   RunTime Proof: THEOREM. If the assumptions hold then the asserted runtime estimates are correct.   RunSpace Proof: THEOREM. If the assumptions hold then the asserted runspace estimates are correct.
Term
 Suppose the fsu::Deque<> d has elements in sorted order and we wish to insert the element x in correct order in d. The following generic algorithm call returns an iterator to the last correct location to insert x:
Definition
 i = fsu::g_upper_bound(d.Begin(), d.End(), x);
Term
 Select the answer that best describes the asymptotic runtime of the operation fsu::List::Remove(t) Here t is an item of type fsu::List::ValueType and n is the size of the list.
Definition
 Θ(n)
Term
 The following represents output from the call d.Dump() from the fsu::Deque object d: content_[i]: A B C D E F G H I J K L    i mod 10: 0 1 2 3 4 5 6 7 8 9 0 1                    e         b What is the result of the d.Dump() after the call d.PopFront() ?
Definition
 content_[i]: A B C D E F G H I J K L    i mod 10: 0 1 2 3 4 5 6 7 8 9 0 1                    e           b
Term
 This is an illustration of a vector of characters to be used in answering the question:   element: B D F F F H K K W Y   index: 0 1 2 3 4 5 6 7 8 9 What is the return value of the call upper_bound('K') ?
Definition
 8
Term
 You are given the declaration   fsu::List L; Write a client program fragment that inserts the strings "ARE", "DOING", "WHAT", "YOU" into L (in this order) so that   L.Display(std::cout, ' ');   results in the sentence "WHAT ARE YOU DOING "?
Definition
 L.PushFront("ARE"); L.PushBack("DOING"); L.PushFront("WHAT"); i = L.Begin(); ++i; ++i; L.Insert(i,"YOU");
Term
 Searching a list whose elements are in sorted order using an algorithm of your choice has what asymptotic runtime? (n is the size of the list.)
Definition
 O(n)
Term
 Declare a deque object wd with elements of type Widget, and initialize with 10 elements equal to the Widget ZED.
Definition
 fsu::Deque wd; for ( size_t i = 0 ; i < 10 ; ++i )     wd.PushFront(ZED);
Term
 A function to display the contents of an associative array could be implemented efficiently as follows:   Display(const AssociativeArray& aa) {    AssociativeArray::Iterator i;    for (i = aa.Begin(); i != aa.End(); ++i)    std::cout << *i.key_ << " : " << *i.data_ <<      '\n'; } (True/False)
Definition
 True
Term
 Suppose that table is a container that implements the Table API. After the call table.Retrieve(kval,dval), dval is a reference to the data stored with kval in the table. (True/False)
Definition
 False
Term
 This is an illustration of a vector of characters to be used in answering the question:   element: B D F F F H K K W Y   index: 0 1 2 3 4 5 6 7 8 9     What is the return value of the call lower_bound('K') ?
Definition
 6
Term
 Declare an fsu::Vector object v with elements of type fsu::String
Definition
 fsu::Vector v;
Term
 Write a traversal loop for an fsu::RingBuffer object b using the fsu::RingBufferIterator object i
Definition
 for (i = b.Begin(); i != b.End(); ++i) { /* whatever */ }
Term
 Suppose that table is a container that implements the Table API. table.Insert(kval,dval) increases table.Size() by one.  (True/False)
Definition
 False
Term
 A function to display the contents of an associative array could be implemented efficiently as follows:   Display(const AssociativeArray& aa) {    AssociativeArray::KeyType::Iterator i;    for (i = KeyType::Begin(); i !=                  KeyType::End(); ++i)    std::cout << i << " : " << aa[i] << '\n'; }   (True/False)
Definition
 False
Term
 The adaptor template defining fsu::Stack < T , C > defines an implementation of ADT Stack by re-defining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile?
Definition
 PushBack(t) PopBack()
Term
 The adaptor template defining fsu::Queue < T , C > defines an implementation of ADT Queue by re-defining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile?
Definition
 PushBack(t) PopFront()
Term
 Which of the following are required (but often only implictly given) components of an algorithm?
Definition
 Body: A recipe or set of instructions for a computation   Assumptions: Things that are assumed to be true prior to executing the body   Outcomes: Things that are true after executing the body (assuming the assumptions)   Correctness Proof: THEOREM. If the assumptions hold and the algorithmn body is executed then the outcomes are true.
Term
 Consider the following code implementing an fsu::List operation: template < typename T > bool operator != (const List& x1, const List& x2) {    /* MISSING LINE OF CODE */ }
Definition
 return !(x1 == x2);
Term
 Necessary components in a recursive function implementation are (select all that apply):
Definition
 A recursive call: in which the function itself is called, either directly or indirectly   A base case: in which no recursive call is made and the proess terminates normally in a return.
Term
 Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential containers. (Here is an iterator, t is a container element, and n is an integer.)
Definition
 PushFront(t) [n] (bracket operator)
Term
 The following represents data of type char stored in a vector:   BBDDDFFGGGHPQQQV   With the initial search range for lower_bound underscored. Which if the following represents the search range after ONE iteration of the loop body in upper_bound (G)?
Definition
 BBDDDFFGGGHPQQQV
Supporting users have an ad free experience!