void List<T>::Reverse ()

{

   typename List<T>::Link * link, * temp;

   // reverse links between head and tail

   link = head_->next_;

   while (link != tail_)

   {

      temp = link->prev_;

      link->prev_ = link->next_;

      link->next_ = temp;

      /* MISSING LINE OF CODE */

   }

   // swap head and tail

   temp = head_;

   head_ = tail_;

   tail_ = temp;

   tail_->prev_ = tail_->next_;

   tail_->next_ = 0;

   head_->next_ = head_->prev_;

   head_->prev_ = 0;

}

Select the missing line of code from the choices below.

Select the answer that best describes the asymptotic runtime of the operation

    fsu::Vector<T>:: Destructor

Here n is the size of the vector.

• A collection of data of some type T
• A set of operations on the data
• Axioms, or rules, governing the way operations interact

Select the most appropriate statement for the asymptotic runtime for the

binary_search algorithm with input size n.

The following represents output from the call d.Dump() from the

fsu::Deque<char> 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

C?

Select the most appropriate statement of the asymptotic runtime for the

sequential_search algorithm with input size n.

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') ?

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?

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

Consider the following implementation of an fsu::List operation:

template < typename T >

ConstListIterator<T> List<T>::Insert (ConstListIterator<T>

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.

newLink->next_->prev_ = newLink;

newLink->prev_->next_ = newLink;

Searching a vector of size n using the lower_bound algorithm has asymptotic runtime

S -->

------------

...

RAC

RA

RAD

RA

R

RB

RBX

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)

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

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

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)

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)

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)

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

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:

Select the answer that best describes the asymptotic runtime of the operation

fsu::Vector<T>:: bracket operator [i]

Here i is an item of type size_t and n is the size of the vector.

Select the answer that best describes the asymptotic runtime of the operation

Deque<T>::PushBack(t)

Here t is an item of type Deque<T>::ValueType and n is the size of the vector.

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') ?

The following represents output from the call d.Dump() from

the fsu::Deque<char> 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') ?

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

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)

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)

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)

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)

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

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)

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)

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.

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:

i = fsu::g_upper_bound(d.Begin(), d.End(), x);

Select the answer that best describes the asymptotic runtime of the operation

fsu::List<T>::Remove(t)

Here t is an item of type fsu::List::ValueType and n is the size of the list.

The following represents output from the call d.Dump() from

the fsu::Deque<char> 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() ?

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 

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') ?

You are given the declaration

fsu::List<fsu::String> 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 "?

L.PushFront("ARE");

L.PushBack("DOING");

L.PushFront("WHAT");

i = L.Begin();

++i;

++i;

L.Insert(i,"YOU");

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.)

Declare a deque object wd with elements of type Widget, and initialize with 10

elements equal to the Widget ZED.

fsu::Deque<Widget> wd;

for ( size_t i = 0 ; i < 10 ; ++i )

    wd.PushFront(ZED);

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)

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)

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') ?

Write a traversal loop for an fsu::RingBuffer object b using the

fsu::RingBufferIterator object i

Suppose that table is a container that implements the Table API.

table.Insert(kval,dval) increases table.Size() by one. 

(True/False)

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)

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?

PushBack(t)

PopBack()

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?

PushBack(t)

PopFront()

Which of the following are required (but often only implictly given) components of an

algorithm?

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.

Consider the following code implementing an fsu::List operation:

template < typename T >

bool operator != (const List<T>& x1, const List<T>& x2)

{

   /* MISSING LINE OF CODE */

}

Necessary components in a recursive function implementation are (select all that apply):

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. 

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.)

PushFront(t)

[n] (bracket operator)

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)?