Frage 1
Frage
Write a traversal loop for an fsu::Vector object v .
Antworten
-
for (size_t i = 0; i <= size; ++i) { /* whatever */ }
-
for (size_t i = 0; i < v.Size(); ++i) { /* whatever */ }
-
for (size_t i = 0; i < size; ++i) { /* whatever */ }
-
None of the other choices
-
for (size_t i = 0; i <= v.Size(); ++i) { /* whatever */ }
Frage 2
Frage
To find a pointer max to the largest element in the array a we can use the following generic
algorithm call (there are size elements in a)
Antworten
-
None of the other choices
-
max = fsu::g_max_element ( a, a + size );
-
max = fsu::g_max_element ( a.Begin() );
-
max = fsu::g_max_element (a);
-
max = fsu::g_max_element ( a.Begin(), a.End() );
Frage 3
Frage
Consider the following implementation of an fsu::List operation:
Frage 4
Frage
Consider the following code implementing an fsu::List operation:
Select the missing line of code from the choices below.
Antworten
-
newLink->prev_ = location;
-
newLink->prev_ = location->next_;
-
newLink->next_ = location->prev_;
-
None of the other choices
-
newLink->prev_ = location->prev_;
Frage 5
Frage
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 Y
index: 0 1 2 3 4 5 6 7 8 9
What is the return value of the call upper_bound('F') ?
Frage 6
Frage
Declare a vector object widgetVector with elements of type Widget, size 15, and
initial element values equal to ZED.
Antworten
-
fsu::Vector<Widget> widgetVector (15,ZED);
-
WidgetVector widgetVector (15,ZED);
-
fsu::Vector<Widget>(15,ZED) widgetVector;
-
None of the other choices
-
fsu::Vector<Widget(15,ZED)> widgetVector;
Frage 7
Frage
Which of the following are required (but often only implictly given) components of an algorithm?
Selected
Antworten
-
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)
-
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
-
Correctness Proof: THEOREM. If the assumptions hold and the algorithm body
is executed then the outcomes are true.
-
RunTime Proof: THEOREM. If the assumptions hold then the asserted runtime
estimates are correct.
-
RunSpace Proof: THEOREM. If the assumptions hold then the asserted
Frage 8
Frage
Necessary components in a recursive function implementation are (select all that apply):
Antworten
-
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 process terminates
normally in a return
-
The use of a stack as part of the algorithm
-
A dimensional reduction: an assignment of a local variable to itself
with smaller variable
Frage 9
Frage
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];
Frage 10
Frage
Select the most appropriate statement for the asymptotic runtime for
the binary_search algorithm with input size n.
Antworten
-
O(log n)
-
Θ(log n)
-
O(n)
-
Θ(n)
Frage 11
Frage
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential
containers.
(Here i is an iterator, t is a container element, and n is an integer.)
Antworten
-
PushFront(t)
-
PushBack(t)
-
Insert(i,t)
-
[n] (bracket operator)
-
SetSize(n)
-
Front()
-
Back()
-
Begin()
Frage 12
Frage
To copy the elements from an fsu::Deque<> d to an fsu::Vector<> v we can use the
following generic algorithm call:
Antworten
-
fsu::g_copy (d.Begin(), d.End(), v.Begin(), v.End());
-
fsu::g_copy (d.Begin(), d.End(), v.Begin());
-
None of the other choices
-
fsu::g_copy (d.Begin(), d.End(), v, v + d.Size);
-
fsu::g_copy (d.Begin(), d.End(), v);
Frage 13
Frage
Select a minimal set of operations that distinguish fsu::List from other fsu:: sequential
containers.
(Here i is an iterator, t is a container element, and n is an integer.)
Antworten
-
PushBack(t)
-
PushFront(t)
-
Insert(i,t)
-
[n] (bracket operator)
-
SetSize(n)
-
Front()
-
Back()
-
Begin()
Frage 14
Frage
Select the answer that best describes the asymptotic runtime of the operation
fsu::List::PushBack(t)
Here t is an item of type fsu::List::ValueType and n is the size of the list.
Antworten
-
O(1)
-
Amortized
O(1)
-
O(n)
-
Amortized
O(n)
Frage 15
Frage
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;
Frage 16
Frage
You are given the declaration
fsu::List<fsu::String> L;
Write a client program fragment that inserts the strings"Help", "I", "May", "You" into L (in this
order) so that
L.Display(std::cout, ' ');
results in the sentence "May I Help You".
Antworten
-
L.PushFront("Help");
L.PushFront("I");
L.PushFront("May");
L.PushFront("You");
-
L.PushBack("Help");
L.PushFront("I");
L.PushFront("May");
L.PushBack("You";);
-
L.PushFront("Help");
L.PushBack("I");
L.PushFront("May");
L.PushBack("You");
-
None of the other
choices
-
L.PushBack("Help");
L.PushBack("I");
L.PushBack("May");
L.PushFront("You");
Frage 17
Frage
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?
Frage 18
Frage
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential
containers.
(Here i is an iterator, t is a container element, and n is an integer.)
Antworten
-
PushBack(t)
-
PushFront(t)
-
Insert(i,t)
-
[n] (bracket operator)
-
SetSize(n)
-
Front()
-
Back()
-
Begin()
Frage 19
Frage
The following represents data of type char stored in a vector:
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 lower_bound(H) ?
Frage 20
Frage
Declare an fsu::List object L with elements of type fsu::String.
Antworten
-
fsu::List<fsu::String> L;
-
L = fsu::List<fsu::String>;
-
None of the other choices
-
fsu::List L<fsu::String>;
-
L = new fsu::List<fsu::String>;
Frage 21
Frage
Select the most appropriate statement of the asymptotic runtime for
the sequential_search algorithm with input size n.
Antworten
-
O(log n)
-
Θ(log n)
-
O(n)
-
Θ(n)
Frage 22
Frage
This is an illustration of a vector of characters to be used in answering the question:
What is the return value of the call lower_bound('F') ?
Frage 23
Frage
Consider the following code implementing an fsu::List operation:
Select the missing line of code from the choices below.
Antworten
-
newLink->prev_ = location->prev_;
-
newLink->prev_ = location;
-
None of the other choices
-
newLink->prev_ = location->next_;
-
newLink->next_ = location->prev_;
Frage 24
Frage
Select the answer that best describes the asymptotic runtime of the operation
fsu::Deque:: bracket operator [i]
Here i is an item of type size_t and n is the size of the deque.
Antworten
-
O(1)
-
Amortized
O(1)
-
O(n)
-
Amortized
O(n)
Frage 25
Frage
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.
Frage 26
Frage
An abstract data type [ADT] consists of the following (select all that apply):
Antworten
-
A set of operations on the data
-
Axioms, or rules, governing the way operations
interact
-
An implementation in a modern programming
language
-
Theorems, or provable behaviors derived from the
axioms
-
A collection of data of some type T
Frage 27
Frage
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential
containers.
(Here i is an iterator, t is a container element, and n is an integer.)
Antworten
-
PushBack(t)
-
PushFront(t)
-
Insert(i,t)
-
[n] (bracket operator)
-
SetSize(n)
-
Front()
-
Back()
-
Begin()
Frage 28
Frage
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? (Check all that apply.)
Antworten
-
PushBack(t)
-
PopBack()
-
PushFront(t)
-
PopFront()
Frage 29
Frage
Select a minimal set of operations that distinguish fsu::List from other fsu:: sequential
containers.
(Here i is an iterator, t is a container element, and n is an integer.)
Antworten
-
PushBack(t)
-
PushFront(t)
-
Insert(i,t)
-
[n] (bracket operator)
-
SetSize(n)
-
Front()
-
Back()
-
Begin()
Frage 30
Frage
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? (Check all that apply.)
Antworten
-
PushBack(t)
-
PopFront()
-
PushFront(t)
-
PopBack()
Frage 31
Frage
Which of the following are optional (but very desirable) components of an algorithm?
Antworten
-
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)
-
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
-
Correctness Proof: THEOREM. If the assumptions hold and the algorithmn body is
executed then the outcomes are true.
-
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.
Frage 32
Frage
Select the answer that best describes the asymptotic runtime of the operation
fsu::List::PushBack(t)
Here t is an item of type fsu::List::ValueType and n is the size of the list.
Antworten
-
O(1)
-
Amortized
O(1)
-
O(n)
-
Amortized
O(n)
Frage 33
Frage
Select the most appropriate statement of the asymptotic runtime for
the sequential_search algorithm with input size n.
Antworten
-
O(log n)
-
Θ(log n)
-
O(n)
-
Θ(n)
Frage 34
Frage
Select the answer that best describes the asymptotic runtime of the operation
fsu::List:: Destructor
Here n is the size of the list.
Antworten
-
O(1)
-
Amortized
O(1)
-
O(n)
-
Amortized
O(n)
Frage 35
Frage
Select the answer that best describes the asymptotic runtime of the operation
fsu::Vector::PushBack(t)
Here t is an item of type fsu::Vector::ValueType and n is the size of the vector.
Antworten
-
O(1)
-
Amortized
O(1)
-
O(n)
-
Amortized
O(n)
Frage 36
Frage
This is an illustration of a vector of characters to be used in answering the question:
What is the return value of the call lower_bound('Z') ?
Frage 37
Frage
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:
Antworten
-
i = fsu::g_upper_bound(d.Begin(), d.End(), x);
-
i = fsu::g_upper_bound(d, x);
-
None of the other choices
-
i = fsu::g_lower_bound(d, x);
Frage 38
Frage
This is an illustration of a vector of characters to be used in answering the question:
What is the return value of the call upper_bound('X') ?
Frage 39
Frage
Declare a Deque object d with elements of type String.
Antworten
-
fsu::Deque < char > d;
-
d = new fsu::Deque< char >;
-
fsu::Deque< char , fsu::List < char >>
d;
-
None of the other choices
-
d fsu::Deque < char >;
Frage 40
Frage
Suppose that we know Algorithm A has runtime Θ(n 2 ), where n is a measure of input
size. Which of the following statements is also true? (Check all that apply.)(Not sure if this one is correct)