Test1

NETB201 - Test 1

Mark the correct/incorrect definitions and assertions about linear data structures.
(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 stack 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 stack 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.
(yes) size() - O(1)
(no) isEmpty() - O(n)

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 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 show the object currently stored at the position in parentheses. For a list 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 nonnegative integers to nonnegative reals. Is the following propositions 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();

Mark the correct/incorrect definitions and assertions about abstract data types.
(yes) The adapter design pattern adjusts functions from one ADT class so they can be used to implement functions of another ADT class.
(no) The running times of functions in the realization of a deque ADT by a doubly linked list are all O(n).