The questions of Test_1

with two model answers - one correct (yes) and one incorrect (no)

Mark the correct and incorrect definitions 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 queue is a container of objects that are inserted and removed according to the first-in last-out (FILO) principle.

Let us have a  stack ADT with n elements realized by an array. Mark the correct or incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) push(o) - O(n)

Let us have a  stack ADT with n elements realized by a singly linked list. Mark the correct or incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) isEmpty() - O(n)

Let us have a  queue ADT with n elements realized by an array. Mark the correct or incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) front() - O(n)

Let us have a  queue ADT with n elements realized by a singly linked list. Mark the correct or incorrect
correspondence between a function of this ADT and its performance.
(yes) dequeue() - O(1)
(no) size() - O(n)

Let us have a  double ended queue (deque) ADT with n elements realized by a doubly linked list. Mark the correct or incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) last() - O(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 performance.
(yes) elemAtRank(r) - O(1)
(no) replaceAtRank(r,e) - 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 performance.
(yes) size() - O(1)
(no) isEmpty() - O(n)

Let us have a  list ADT with n elements realized by a doubly linked list. Mark the correct and incorrect correspondence between a function of this ADT and its performance.
(yes) remove(p) - O(1)
(no) isLast(p) - O(n)

Let us have a  sequence ADT with n elements realized by a doubly linked list. Mark the correct/incorrect correspondence between a given function of this ADT and its performance.
(yes) atRank(r) - O(n)
(no) elemAtRank(r) - O(1)

Let us have a  sequence ADT with n elements realized by a circular array. Mark the correct/incorrect correspondence between a function of this ADT and its performance.
(yes) size() - O(1)
(no) removeAtRank(r) - O(1)

Let us have a  stack ADT S = (9,7,2). The top element is 2. Determine the correct triples: operation - output - new stack. The triple is correct, when applying the given function on S, the second triple member is its the return value and the third member is the new stack S.
(yes) push(5) - NONE - (9,7,2,5)
(no) top() - NONE - (9,7)

Let us have a  queue ADT Q = (8,7,2). The front element is 8. Determine the correct triples: operation - output - new queue. The triple is correct, when applying the given function on Q, the second triple member is its the return value and the third member is the new queue Q.
(yes) enqueue(5) - NONE - (8,7,2,5)
(no) first() - 8 - (7,2)

Let us have a  double-ended queue (deque) ADT D = (8,1,2). The front element is 8. Determine the
correct triples: operation - output - new deque. The triple is correct, when applying the given function on D, the second triple member is its the return value and the third member is the new deque D.
(yes) insertFirst(5) - NONE - (5,8,1,2)
(no) insertLast(9) - 9 - (8,1,2,9)

Let us have a  vector ADT V = (4,7,2). Determine the correct triples: operation - output - new vector. The triple is correct, when applying the given operation on V, the second triple member is its the output value and the third member is the new vector 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 = (p1(8)->p2(3)). We use variables p1, p2, and so on, to denote different positions, and we show the object currently stored at such a position in parentheses. Determine the correct triples: function - output - new list. The triple is correct, when applying the given function on L, the second triple member is its the output value and the third member is the new list L.
(yes) insertFirst(2), p4(2), (p4(2)->p1(8)->p2(3))
(no) remove(p1), NONE, (p1(8))