Data Structures Important Questions

Ques 1. What is priority queue?how can it be implemented in data structures?

Ans. A priority queue is a special type of queue in which every element is associated with a priority value.

A Priority queue can be implemented using 

• Array
• Linked List
• Binary Search Tree
• Heap Data Structure

Ques 2. Solve The Given Example OF the Infix To Postfix Conversion

(( A + B )  - C * ( D / E ))+  F

Ans. 

Scanned Symbol                        Stack                                 Postfix Expression

(                                                      (                                                 

(                                                     ( (                                                            

A                                                    ( (                                                 A

+                                                    ( ( +                                               A

B                                                    ( ( +                                              AB

)                                                      (                                                  AB+

-                                                      ( -                                               AB+

C                                                    ( -                                                AB+C

*                                                      ( - *                                            AB+C

(                                                     ( - * (                                           AB+C

D                                                    ( - * (                                          AB+CD

/                                                      ( - * ( /                                     AB+CD

E                                                     ( - * ( /                                      AB+CDE

)                                                      ( - *                                          AB+CDE/

)                                                                                                     AB+CDE/*-

+                                                       +                                           AB+CDE/*-

F                                                       +                                          AB+CDE/*-F

Postfix is -: AB+CDE/*-F+

Ques 3. What is Sparse Matrix? Describe a data structure for efficient storage of Sparse Matrix?

Ans. A Sparse Matrix is a matrix in which most elements are equal to zero.

Ques 4. What is asymptotic notation? Explain it's Types?

Ans. Asymptotic notations are mathematical notation used to describe running time of algorithm

There are three types of asymptotic notations

1. Big-O Notation -  it gives the worst-case complexity of an algorithm.
2. Omega Notation - it provides the best case complexity of an algorithm.
3. Theta Notation - it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the Average case complexity of an algorithm.

Ques 5. Define AVL Tree with suitable example.

Ans. An AVL tree is a self balancing tree in which difference between height of left node and height of right node should be equal to -1 or 0 or 1.

Ques 6. Define Data Structure. Explain it's operations and types.

Ans. What is Data Structures?

Types of data structure

Ques 7. Explain the Print algorithm in the linked list?

Ans. Printing elements during traversing of linked list.

1. SET PTR = HEAD.
2. IF PTR = = NULL
3. THEN, PRINT("LIST IS UNDERFLOW"); OTHERWISE,
4. REPEAT STEPS 5 AND 6 WHILE PTR != NULL.
5. PRINT PTR->DATA.
6. PTR = PTR->NEXT.
7. EXIT;

Ques 8. What is Sparse Matrix in brief?

Ans. A Sparse Matrix is a matrix in which most elements are equal to zero.

There are the following benefits of using the sparse matrix -

Storage - We know that a sparse matrix contains lesser non-zero elements than zero, so less memory can be used to store elements. It evaluates only the non-zero elements.

Computing time - In the case of searching in sparse matrix, we need to traverse only the non-zero elements rather than traversing all the sparse matrix elements. It saves computing time by logically designing a data structure traversing non-zero elements.

Ques 9. What is Linked List? Write down the print algorithm of linked list?

Ans. A linked list is a collection of two nodes where one node contains the data and the other node contains the address to the next pointer.

Print Algorithm

1. SET PTR = HEAD.
2. IF PTR = = NULL
3. THEN, PRINT("LIST IS UNDERFLOW"); OTHERWISE,
4. REPEAT STEPS 5 AND 6 WHILE PTR != NULL.
5. PRINT PTR->DATA.
6. PTR = PTR->NEXT.
7. EXIT;

Ques 10. Differentiate between Overflow and Underflow situation of linked list.

Ans. Overflow condition:

• Overflow condition is associated with the basic operations in the linked list like inserting an element into the list.
• We Check this condition before adding a node to the linked list.
• In the system, this condition happens when there is no vacant memory cell.

Underflow condition:

• Underflow condition is associated with the basic operations in the liked list like deleting an element from the list.

• We check this condition before deleting a node to the linked list.
• If the linked list is empty, then we can't delete anything.

Ques 11. What is Stack? Explain the primitive operation of stack.

Ans. A Stack is a kind of linear array which follows the order of last in first out(LIFO).

Operations on Stack 

Push - Adding an element onto stack in called Pushing.

Pop - Removing the top most element of stack in called popping.

Peek - Getting the value of top most element is known as peek.

Ques 12. Describe the difference between the doubly linked list and circular linked list. mention the application of each of the list.

Ans. A linked list is a collection of two nodes where one node contains the data and the other node contains the address to the next pointer.

Doubly Linked List - In doubly linked list each item is connected to the next one and previous one.

doubly linked list has 2 pointer i.e. pointer to forward node and pointer to next node.

Circular Linked List - The circular linked list have only a single pointer.

 circular linked list last node will point to first node

Ques 13. List any four difference between LIST and GRAPH.

Ans.             

 

Tree	Graph
It is a non-linear data structure	It is also a non-linear data structure.
A tree is a set of nodes and edges.	A graph is a set of vertices/nodes and edges.
n a tree, there is a unique node which is known as root.	In the graph, there is no unique node which is known as root.
a tree can have several child nodes, and in the case of binary trees, each node consists of two child nodes.	Each node can have several edges.
Trees cannot form a cycle.	Graphs can form cycles.

Ques 14. Compare the insertion and Deletion of B Tree and B+ Tree.

Ans. 

Operations	B - tree	B+ tree
Insertion	Insertion takes more time and it is not predictable sometimes.	Insertion is easier and the results are always the same
Deletion	Deletion of the internal node is very complex and the tree has to undergo a lot of transformations.	Deletion of any node is easy because all node are found at leaf.

Ques 15. What is BST? How it is different from the complete Binary Tree? Write the process of traversal of Tree?

Ans. 

Binary Search Tree - Binary Search tree allow us to maintain a sorted listed of numbers it is called binary because each node has two children. it is called search tree because it can be used to search a number in O(log(n)) time.

Properties of BST

1. All nodes of a left subtree are less than root node.
2. All roots of a right subtree are greater than the root node.

Complete Binary Tree - In complete binary tree all the levels are completely filled except possibly the lowest one, which is filled from the left. 

Properties of Complete Binary Tree

1. All the nodes must lean towards left
2. The last leaf might not have a right sibling.

There are three types of traversal

Inorder Traversal

1. Visit the all nodes in the left sub tree.
2. Visit the root node.
3. Visit the all nodes in the right sub tree.

Preorder Traversal

1. Visit the root node.
2. Visit the all nodes in the left sub tree.
3. Visit the all nodes in the right sub tree.

Postorder Traversal

1. Visit the all nodes in the left sub tree.
2. Visit the all nodes in the right sub tree.
3. Visit the root node.