Test1

NETB201 - 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²)

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) < cg(n) for n > N.
(no) g(n) is O(f(n)) if there are positive constants c and N such that f(n) < cg(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ⁿ).

Mark correct/incorrect assertions about asymptotic notation for concrete functions.
(yes) 2n + 10 is O(n)
(no) n + n² 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ⁿ), then d(n)e(n) is O(n² 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>.