COP4530 Comprehensive

1. To find a pointer max to the largest element in the array a we can use the following genericalgorithm call (there are size elements in a)

Max = fsu::g_max_element (a);

Max = fsu::g_max_element (a, a + size);

Max = fsu::g_max_element (a.Begin());

Max = fsu::g_max_element (a.Begin(), a.End());

2. The following illustrates the contents of the control stack S during a depth-first search of a tree [tree3],beginning at vertex R = root and searching for the vertex X = goal. (Search left before right, beginning at the root.) The search process is started but not complete.

S -->------------...RADRADGRADRARRBRBX

S -->------------...RADRADGRADGBRADGBX

None of the other choices

S -->------------...RADFGBRADFGBX

S -->------------...CCDCDX

3. Declare an fsu::Stack object S with elements of type fsu::String and underlyingcontainer fsu::Vector.

Fsu::Stack < fsu::String , fsu::Vector < fsu::String > > S;

Fsu::Vector < fsu::String , Stack < fsu::String > > S;

None of the other choices

Fsu::Stack < fsu::String > S;

Fsu::Deque < fsu::String , fsu::Vector < fsu::String > > S;

4. Declare an fsu::List object L with elements of type fsu::String.

None of the other choices

5. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call lower_bound('F') ?

1

2

3

4

5

D

F

H

6. What is the result of a levelorder traversal of the following tree?

A B C D E

A B D C E

D B E C A

D B A C E

7. What is the result of a postorder traversal of the following tree?

A B C D E

A B D C E

D B E C A

D B A C E

8. The following represents output from the call d.Dump() from the fsu::Deque object d:What is the result of the following output statement?std::cout << d;

G H I J A B C

G H I J A B

None of the other choices

C D E F

C D E F G

9. Declare a Deque object d with elements of type String.

None of the other choices

D = new fsu::Deque < char >;

Fsu::Deque < char , fsu::List < char > > d;

D fsu::Deque < char >;

Fsu::Deque < char > d;

10. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call upper_bound('F') ?

1

2

3

4

5

D

F

H

11. The following represents output from the call d.Dump() from the fsu::Deque<char> object d:What is the result of the d.Dump() after the call d.PushFront('X') ?

None of the other choices

12. The following represents output from the call d.Dump() from the fsu::Deque<char> object d:What is the result of the following output statement?std::cout << d[5];

A

B

C

D

E

F

G

H

I

J

13. 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:

I = fsu::g_upper_bound(d, x);

I = fsu::g_upper_bound(d.Begin(), d.End(), x);

I = fsu::g_lower_bound(d.Begin(), d.End(), x);

I = fsu::g_lower_bound(d, x);

None of the other choices

14. Declare a vector object widgetVector with elements of type Widget, size 15, and initialelement values equal to ZED.

Fsu::Vector widgetVector;

WidgetVector widgetVector (15,ZED);

Fsu::Vector widgetVector (15,ZED);

Fsu::Vector(15,ZED) widgetVector;

None of the other choices

15. Select the answer that best describes the asymptotic runtime of the operationfsu::List:: DestructorHere n is the size of the list.

O(1)

Amortized O(1)

O(n)

Amortized O(n)

16. What is the result of a pre-order traversal of the following tree?

15 30 25 95 80 50

50 25 80 15 30 95

50 25 15 30 80 95

15 25 30 50 80 95

17. An abstract data type [ADT] consists of the following (select all that apply):

A set of operations on the data

Axioms, or rules, governing the way operations interact

A collection of data of some type T

An implementation in a modern programming language

Theorems, or provable behaviors derived from the axioms

Submit

18. Given the type definitiontypedef fsu::Pair < String , int > PairType;and instances:

P1 == p1

P1 == p2

P1 == p3

P1 == p4

Submit

19. Select a minimal set of operations that distinguish fsu::List from other fsu:: sequentialcontainers.

PushBack(t)

PushFront(t)

Insert(i,t)

[n] (bracket operator)

SetSize(n)

Front()

Back()

Begin()

20. What is the worstcase runtime for the Search algorithm in a AVL Binary Search Tree? (Select all that apply)

Theta(N)

Theta(H)

Theta(log N)

Theta(log H)

Submit

21. Write a traversal loop for an fsu::Vector object v .

For (size_t i = 0; i

For (size_t i = 0; i < size; ++i) { /* whatever */ }

For (size_t i = 0; i < v.Size(); ++i) { /* whatever */ }

22. What is the result of a pre-order traversal of the following tree?

A B C D E

A B D C E

D B E C A

D B A C E

23. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call lower_bound('Z') ?

7

8

9

10

K

Q

W

Y

24. What is the worstcase runtime for the Search algorithm in a RedBlack LeftLeaningBinary Search Tree? (Select all that apply)

Theta(N)

Theta(H)

Theta(log N)

Theta(log H)

Submit

25. Select a minimal set of operations that distinguish fsu::Vector from other fsu:: sequentialcontainers.(Here i is an iterator, t is a container element, and n is an integer.)

PushBack(t)

PushFront(t)

Insert(i,t)

[n] (bracket operator)

SetSize(n)

Front()

Back()

Begin()

26. To copy the elements from an fsu::Deque<> d to an fsu::Vector<> v we can use the following generic algorithm call:

Fsu::g_copy (d.Begin(), d.End(), v.Begin());

Fsu::g_copy (d.Begin(), d.End(), v);

None of the other choices

Fsu::g_copy (d.Begin(), d.End(), v, v + d.Size);

Fsu::g_copy (d.Begin(), d.End(), v.Begin(), v.End());

27. What is the worst-case runtime for the Search algorithm in a Red-Black Binary Search Tree? (Select all that apply)

Theta(N)

Theta(H)

Theta(log N)

Theta(log H)

Submit

28. Declare an ordered table object otable as an ordered set of pairs consisting of a key of typeKeyType and some data of type DataType. (Assume namespace fsu.)

All of the above

None of the above

29. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call upper_bound('X') ?

7

8

9

10

K

Q

W

Y

30. Select the most appropriate statement of the asymptotic runtime for the sequential_searchalgorithm with input size n.

O(log n)

Θ(log n)

O(n)

Θ(n)

31. Select the answer that best describes the asymptotic runtime of the operationfsu::Vector::PushBack(t)Here t is an item of type fsu::Vector::ValueType and n is the size of the vector.

O(1)

Amortized O(1)

O(n)

Amortized O(n)

32. Select the answer that best describes the asymptotic runtime of the operationfsu::Deque:: bracket operator [i]Here i is an item of type size_t and n is the size of the deque.

Amortized O(1)

O(n)

Amortized O(n)

O(1)

33. The adaptor template defining fsu::Stack < T , C > defines an implementation of ADT Stackby redefining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile? (Check all that apply.)

PushFront(t)

PushBack(t)

PopFront()

PopBack()

Submit

34. Select the answer that best describes the asymptotic runtime of the operationfsu::List::PushBack(t) Here t is an item of type fsu::List::ValueType and n is the size of the list.

O(1)

Amortized O(1)

O(n)

Amortized O(n)

35. Select the most appropriate statement for the asymptotic runtime for the binary_searchalgorithm with input size n.

Θ(log n)

O(log n)

O(n)

Θ(n)

36. Select the operations that define the associative container (Set) API. Here tval is a value anditer is an iterator.

Includes(tval)

Remove(iter)

Insert(iter,tval)

Insert(tval)

Remove(tval)

Submit

37. Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequentialcontainers.

PushBack(t)

PushFront(t)

Insert(i,t)

[n] (bracket operator)

SetSize(n)

Front()

Back()

Begin()

Submit

Cop4530 Comprehensive

1. To find a pointer max to the largest element in the array a we can use the following genericalgorithm call (there are size elements in a)

2.

What first name or nickname would you like us to use?

2. The following illustrates the contents of the control stack S during a depth-first search of a tree [tree3],beginning at vertex R = root and searching for the vertex X = goal. (Search left before right, beginning at the root.) The search process is started but not complete.

3. Declare an fsu::Stack object S with elements of type fsu::String and underlyingcontainer fsu::Vector.

4. Declare an fsu::List object L with elements of type fsu::String.

5. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call lower_bound('F') ?

6. What is the result of a levelorder traversal of the following tree?

7. What is the result of a postorder traversal of the following tree?

8. The following represents output from the call d.Dump() from the fsu::Deque object d:What is the result of the following output statement?std::cout << d;

9. Declare a Deque object d with elements of type String.

10. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call upper_bound('F') ?

11. The following represents output from the call d.Dump() from the fsu::Deque<char> object d:What is the result of the d.Dump() after the call d.PushFront('X') ?

12. The following represents output from the call d.Dump() from the fsu::Deque<char> object d:What is the result of the following output statement?std::cout << d[5];

13. 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:

14. Declare a vector object widgetVector with elements of type Widget, size 15, and initialelement values equal to ZED.

15. Select the answer that best describes the asymptotic runtime of the operationfsu::List:: DestructorHere n is the size of the list.

16. What is the result of a pre-order traversal of the following tree?

17. An abstract data type [ADT] consists of the following (select all that apply):

18. Given the type definitiontypedef fsu::Pair < String , int > PairType;and instances:

19. Select a minimal set of operations that distinguish fsu::List from other fsu:: sequentialcontainers.

20. What is the worstcase runtime for the Search algorithm in a AVL Binary Search Tree? (Select all that apply)

21. Write a traversal loop for an fsu::Vector object v .

22. What is the result of a pre-order traversal of the following tree?

23. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call lower_bound('Z') ?

24. What is the worstcase runtime for the Search algorithm in a RedBlack LeftLeaningBinary Search Tree? (Select all that apply)

25. Select a minimal set of operations that distinguish fsu::Vector from other fsu:: sequentialcontainers.(Here i is an iterator, t is a container element, and n is an integer.)

26. To copy the elements from an fsu::Deque<> d to an fsu::Vector<> v we can use the following generic algorithm call:

27. What is the worst-case runtime for the Search algorithm in a Red-Black Binary Search Tree? (Select all that apply)

28. Declare an ordered table object otable as an ordered set of pairs consisting of a key of typeKeyType and some data of type DataType. (Assume namespace fsu.)

29. This is an illustration of a vector of characters to be used in answering the question:element: B D F F F H K Q W Yindex: 0 1 2 3 4 5 6 7 8 9What is the return value of the call upper_bound('X') ?

30. Select the most appropriate statement of the asymptotic runtime for the sequential_searchalgorithm with input size n.

31. Select the answer that best describes the asymptotic runtime of the operationfsu::Vector::PushBack(t)Here t is an item of type fsu::Vector::ValueType and n is the size of the vector.

32. Select the answer that best describes the asymptotic runtime of the operationfsu::Deque:: bracket operator [i]Here i is an item of type size_t and n is the size of the deque.

33. The adaptor template defining fsu::Stack < T , C > defines an implementation of ADT Stackby redefining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile? (Check all that apply.)

34. Select the answer that best describes the asymptotic runtime of the operationfsu::List::PushBack(t) Here t is an item of type fsu::List::ValueType and n is the size of the list.

35. Select the most appropriate statement for the asymptotic runtime for the binary_searchalgorithm with input size n.

36. Select the operations that define the associative container (Set) API. Here tval is a value anditer is an iterator.

37. Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequentialcontainers.