## NETB208 - Test_1

Mark the correct/incorrect definitions and assertions about *linear
data structures *
and *abstract data types*.

(yes) A stack is a container of objects that are inserted and
removed according to the last-in first-out (LIFO) principle.

(no) A singly linked list is an ADT which consists of collection of
nodes.

Let us have a **queue** ADT with *n* elements realized by
an *array*. Mark the correct/incorrect correspondence between
a function of this ADT and its running time.

(yes) size() - *O*(1)

(no) isEmpty() - *O*(*n*^{2})

Let us have a **queue** ADT with n elements realized by a *singly
linked list.* Mark the correct/incorrect correspondence between
a function of this ADT and its running time.

(no) size() - *O*(*n*)

(yes) isEmpty() - *O*(1)

Let us have a **deque** ADT with *n* elements realized by
a *doubly linked list*. Mark the correct/incorrect
correspondence between a function of this ADT and its running time.

(yes) size() - *O*(1)

(no) isEmpty() - *O*(log *n*)

Let us have a **vector** ADT with *n* elements realized by
an **array**. Mark the correct/incorrect correspondence between
a function of this ADT and its running time.

(yes) size() - *O*(1)

(no) isEmpty() - *O*(*n*)

Let us have a **list** ADT with *n* elements realized by
an *array*. Suppose that the **position** means the *
index*. Mark the correct/incorrect correspondence between a
given function of this ADT and its running time.

(no) size() - *O*(*n*)

(yes) isEmpty() - *O*(1)

Let us have a **list** ADT with *n* elements realized by a
*doubly linked list*. Mark the correct/incorrect correspondence
between a function of this ADT and its running time.

(no) size() - *O*(*n*)

(yes) isEmpty() - *O*(1)

Let us have a **stack** ADT S = (9,7,2) with top element 2. For
a given stack operation, determine its return value and its effect
on S.

(yes) push(5) - NONE - S=(9,7,2,5)

(no) push(3) - 3 - S=(9,7,3)

Let us have a **queue** ADT Q = (8,7,2). The front element is 8.
For a queue operation, determine its return value and its effect on
Q.

(yes) enqueue(5) - NONE - Q=(8,7,2,5)

(no) enqueue(7) - 7 - Q=(8,7,2,7)

Let us have a **deque** ADT D = (8,1,2). The front element is 8.
For a deque operation, determine its return value and its effect on
D.

(no) isEmpty() - true - D =(8,1,2)

(yes) size() - 3 - D =(8,1,2)

Let us have a **vector** ADT V = (4,7,2). For a vector
operation, determine its return value and its effect on V.

(yes) insert 1 at rank 0 - NONE - (1,4,7,2)

(no) insert 2 at rank 1 - NONE - (2,4,7,2)

Let us have a **list **ADT L = p_1(8) -> p_2(3). We use
positions p_1, p_2 etc. and put in parentheses the object, currently
stored at this position. For the given list ADT operation, determine
its return value and its effect on L.

(yes) insertFirst(2), p_4(2), p_4(2) -> p_1(8) -> p_2(3)

(no) insertFirst(4), p_3(4), p_3(4) -> p_2(3)

Mark correct/incorrect definitions about asymptotic notation.

(yes) *f*(*n*) is *O*(*g*(*n*)) if there
are positive constants c and *N *such that *f*(*n*)
<* c**g*(*n*) for *n *>* N*.

(no) *g*(*n*) is *O*(*f*(*n*)) if there
are positive constants c and *N* such that *f*(*n*)
<* c**g*(*n*) for *n* >* N*.

Is the following assertion true?

(yes) The running time of an algorithm typically grows with the
input size.

(no) If is *f*(*n*) a polynomial of degree *d*,
then *f*(*n*) is *O*(*d*^{n}).

Mark correct/incorrect assertions about asymptotic notation for
concrete functions.

(yes) 2*n* + 10 is *O*(*n*)

(no) *n* + *n*^{2} is *O*(*n*)

Let d(n), e(n), f(n) and g(n) be functions mapping non-negative
integers to non-negative reals. Is the following proposition true?

(yes) If d(n) is O(f(n)), then a+d(n) is O(f(n)) for any constant a.

(no) If d(n) is O(f(n)) and e(n) is O(2^{n}), then d(n)e(n)
is O(n^{2} f(n)).

We have a function template:

template<typename T>

T maxA(T*
arr, int s = 2)

{ T maxVal
= arr[0];

for
(int i = 1; i < s; i++)

if
(arr[i] > maxVal) maxVal = arr[i];

return
maxVal;

}

Mark correct/incorrect assertions or statements in the body of main
function.

(yes) `int a[3]={2,1,4}; cout << maxA(a,3);`

(no) `cout << maxA(10);`

We have the following code fragment:

void fun3()
{ throw runtime_error("RTE"); }

void fun2()
throw(runtime_error) { ... }

void fun1()
throw(runtime_error) { fun2(); }

int main()

{ try {
fun1(); }

catch
(runtime_error e) { cout << e.what(); }

return 0;

}

Replacing ... with the given below statement, the message RTE prints
on the screen. Is this assertion true?

(yes) fun3();

(no) fun1();

Look Code Fragment: NodeSequence2. Mark the correct/incorrect
assertions.

(yes) The function `rankOf` returns the rank of the element
at position `p`.

(no) `trailer` is a datum defined in the class `NodeSequence<Object>`.