GATE Computer Science Engineering(CSE) 2027 Test: Arrays, Stack, Queues

A dope vector is a data structure used to hold information about a data objects eg. an array, especially layout of array’s memory. It contain information such as rank of an array, type of elements of array etc.

(i, j) entries in column major order of size (m x n). 
Assume starting address is 1 so, m x (j - 1) + i

Sparse matrices are those matrices in which most of the elements are zero.
In contrast, if most of the elements are non-zero then the matrix is considered DENSE.

The tree whose preorder traversal yields * + AB - CD, is given in figure. Write the postorder traversal of the tree. That is the postfix form.

Postorder traversal = AB + CD-*

Stacks are used to evaluate postfix expressions, to store data in case of recursion and to convert infix forms to postfix forms.
However, resource allocation can’t be done using stack. Scheduling algorithms are used for allocation of CPU time

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

Stack is used for implementing recursion and depth first search.
For breadth first search, queue is used.

Immediately after visiting a node, append it to the queue. After visiting all its children, the node currently in the head of the queue is deleted. This process is recursively carried out on the current head of the queue, till the queue becomes empty.

The process of accessing data stored on tape is similar to manipulating data on a set.

In case of using link list, one cannot randomly access the data or only serial data access is there. But, in case of binary search one needs to jump randomly either to first half or other half, which is not possible with linked list.

Doubly linked lists have a few advantages over linear linked lists when it comes to certain operations. Specifically, the following operation is performed more efficiently by a doubly linked list than by a linear linked list

Deleting a node given a pointer to the node.

In a linear linked list, deleting a node requires traversing the list to find the node to be deleted and its predecessor. Once these nodes have been found, the predecessor's next pointer is updated to skip over the node to be deleted. This operation takes O(n) time in the worst case, where n is the number of nodes in the list.

Smallest element of an array’s index is called its LOWER BOUND and largest array index is called its UPPER bound.