Data Structure Quiz 1

Using counting sort , it will take linear time.

Using counting sort , a single scan will identify if there exist any repeated element in the given array. Therefore , it takes O(n) time.

Breadth first search is a graph traversal algorithm that starts traversing the graph from root node and explores all the neighbouring nodes. Then, it selects the nearest node and explore all the unexplored nodes. The algorithm follows the same process for each of the nearest node until it finds the goal.
Queue is a suitable structure for BFS.

Queue follows FIFO mechanism hence the order will be 4 3 2 1.

In double ended queue elements can be added and deleted from both ends. Hence, 1 2 3 4 5 6 and 6 5 4 3 2 1 sequences can be realized as the output of a double ended queue.

There are two pointer variables namely FRONT and REAR. The FRONT denotes the location of the first element of the queue. The rear describes the location of the rear element of the queue. When the queue is empty, the values of front and rear are-1 and -1 respectively.

The concatenation of two lists is to perform on O(1) time by the use of circular doubly linked list. The reason behind this, that it has the pointer in the both direction in front and backward.

Singly Linked List:

(i) Elements will be inserted using tail pointer and Elements will be deleted using head pointer
(ii) In a single linked list , any number of elements can be inserted without declaring prior size
(iii) An item of large size can be stored in a linked list using structures.

Doubly-linked list, with only a head pointer - only having a head pointer makes it hard to implement the FIFO requirement.

Array - imposes an a priori limit on the size of the collection that other data structures do not.

Binary tree - doesn't organize the elements in a way that makes it convenient to implement FIFO.

Hash table - makes FIFO impossible.

Struct node *temp = x ->next;
x->data = temp->data;
x->next = temp->next;
free(temp);

Hence, If the given pointer is of the last node then it is not possible to delete that node.

For insertion/deletion of a record in a circularly linked list involves 2 pointers. But for reversing the linked list, it involves 3 pointers.