Data Structure LAB VIVA 1

For getting best time complexity in the worst case scenario, which type of sorting algorithms are used?

• Bubble sort of algorithm

• Selection sort of algorithm

• Quick sort of algorithm

• Merge sort of algorithm

The five items: A, B, C, D, and E are pushed in a stack, one after other starting from A. The stack is popped four items and each element is inserted in a queue. The two elements are deleted from the queue and pushed back on the stack. Now one item is popped from the stack. The popped item is

• A

• B

• C

• D

Consider the function f defined below. 

struct item

{
  int data;
  struct item next;
};

int f(struct item p)
{
  return (
          (p == NULL) ||
          (p->next == NULL) ||
          (( p->data <= p->next->data) && f(p->next))
         );
}

 For a given linked list p, the function f returns 1 if and only if

• not all elements in the list have the same data value.

• the elements in the list are sorted in non-decreasing order of data value

• the elements in the list are sorted in non-increasing order of data value

• None of them

Which of the following points is/are true about Linked List data structure when it is compared with array?

• The size of array has to be pre-decided, linked lists can change their size any time.

• It is easy to insert and delete elements in Linked List

• Random access is not allowed in a typical implementation of Linked Lists

• All of the above

How many stacks are needed to implement a queue. Consider the situation where no other data structure like arrays, linked list is available to you.

• 4

• 3

• 2

• 1

A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements ”1‘ and ”7‘ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

• 10, 8, 7, 5, 3, 2, 1

• 10, 8, 7, 2, 3, 1, 5

• 10, 8, 7, 1, 2, 3, 5

• 10, 8, 7, 3, 2, 1, 5

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operation are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

• Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT

• Full: (REAR+1) mod n == FRONT, empty: (FRONT+1) mod n == REAR

• Full: (FRONT+1) mod n == REAR, empty: REAR == FRONT

• Full: REAR == FRONT, empty: (REAR+1) mod n == FRONT

which data structure is used to implement deque?

• Stack

• Doubly linked list

• circular array

• Both B and C

Which of the following is true about Binary Trees?

• Every binary tree is either complete or full.

• Every complete binary tree is also a full binary tree.

• Every full binary tree is also a complete binary tree.

• None of the above

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

• 2^h -1

• 2^(h-1) – 1

• 2^(h+1) -1

• 2*(h+1)