Data Structures Important Questions Part - 2

Ques 1. Write an algorithm/ Program in C of the following with suitable example.

Ans. Insertion Sort

Algorithm 

1. INSERTION(A, N)    

2. Repeat Steps 3 to 5 for I = 1 to N;

3. Set KEY = A[I] and J = I-1.

4. Repeat while KEY < A[J] and j >= 0

      (a) Set A[J + 1] = A[J]                     

      (b) Set J = J-1.                                 

    [end of loop] 

5. Set A[J+1] = KEY; 

6. Return

C Program 

Selection Sort :

Algorithm

SMALLEST(A, I, N, POS)

1. Set Min = A[I], Set POS = I     [Initialize Pointers]

2. Repeat For J = I+1 To N;

IF A[J] < MIN, Then : Set MIN = A[J] and POS = J;

[End of loop]

3. Return

SELECTION SORT(A, N)

1. Repeat Step 2 and 3 for I =0 to N-1;

2. Call SMALLEST(A, I, N, POS)

3. Swap A[I] with A[POS]

Exit

C Program

Ques 2. Explain in brief the breadth first search technique with an algorithm.

Ans. Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. We can consider any node as a root node and we need to guarantee that no node is processed more than more once.

Applications Of Breadth First Search

1. BFS can be used to find the neighboring locations from a given source location.
2. BFS is used to determine the shortest path and minimum spanning tree.

Algorithm

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and

 set their STATUS = 2 (Waiting state)

[END OF LOOP]

Step 6: EXIT

Example of Breadth First Search Algorithm

In the above graph, minimum path 'P' can be found by using the BFS that will start from Node A and end at Node E. The algorithm uses two queues, namely QUEUE1 and QUEUE2. 

QUEUE1 holds all the nodes that are to be processed, while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.

Now, let's start examining the graph starting from Node A.

Step 1 - First, add A to queue1 and NULL to queue2.

QUEUE 1 = { A }

QUEUE 2 = { NULL }

Step 2 - Now, delete node A from queue1 and add it into queue2. Insert all neighbors of node A to queue1.

QUEUE 1 = {B, D}

QUEUE 2 = { A }

Step 3 - Now, delete node B from queue1 and add it into queue2. Insert all neighbors of node B to queue1.

QUEUE 1 = {D, C, F}

QUEUE 2 = {A, B}

Step 4 - Now, delete node D from queue1 and add it into queue2. Insert all neighbors of node D to queue1. The only neighbor of Node D is F since it is already inserted, so it will not be inserted again.

QUEUE 1 = {C, F}

QUEUE 2 = {A, B, D}

Step 5 - Delete node C from queue1 and add it into queue2. Insert all neighbors of node C to queue1.

QUEUE 1 = {F, E, G}

QUEUE 2 = {A, B, D, C}

Step 6 - Delete node F from queue1 and add it into queue2. Insert all neighbors of node F to queue1. Since all the neighbors of node F are already present, we will not insert them again.

QUEUE 1 = {E, G}

QUEUE 2 = {A, B, D, C, F}

Step 6 - Delete node E from queue1. Since all of its neighbors have already been added, so we will not insert them again. Now, all the nodes are visited, and the target node E is encountered into queue2.

QUEUE 1 = {G}

QUEUE 2 = {A, B, D, C, F, E}

Ques 4. What is hashing? Explain the following types of hashing with suitable examples.

Mid - Square hashing

Division reminder hashing

direct hashing

Ans. Hashing is the process of transforming any key or string of character into another value.

the most useful use of hashing is the implementation of hash tables.

Mid - Square hashing - In Mid- square hashing method unique keys are generated. in this method a seed value is taken and it is squared. then some digit from the middle are extracted. these extracted digit form a number which is taken as new seed.

Division remainder hashing - In this method key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record.

direct hashing - Hashing in data structure uses hash tables to store given value-pairs

Ques 5. What is Stack? write its algorithm and operations.

Ans. A Stack is kind of linear array which follows the order Last in First out (LIFO). 

Operations on Stack:

Push -: Adding an element onto a stack is called pushing.

Pop -: Removing the top most element from the stack is called popping.

peek-: getting the value of top most element is called peek.

PUSH Algorithm

PUSH(STACK, TOP, MAX, DATA)

1. If TOP = MAX
2. then: print("STACK OVERFLOW") ELSE,
3. Set TOP = TOP+1.
4. Set STACK[TOP] = DATA.
5. Return.

  POP Algorithm

POP(STACK, TOP, DATA)

1. IF TOP=0, then: print("STACK UNDERFLOW). ELSE,
2. Set DATA = STACK[TOP]
3. Set TOP = TOP-1.
4. Return.

Ques 6. Differentiate between BFS and DFS searching technique.

Ans. 

Breadth First Search	Depth First Search
BFS Uses queue Data Structure for finding the shortest path	DFS uses stack Data Structure
It works on the concept of FIFO	It works on the concept of LIFO
BFS requires more memory	DFS requires less memory
BFS is slow as compared to DFS	DFS is fast as compared to BFS
BFS does not use the backtracking concept	DFS uses backtracking concept to traverses all the unvisited nodes
When the target is close to the source BFS is preferable	When the target is far from the source DFS performs better

Ques 7. Convert Postfix to infix.

abc-+de-fg-h+/*

Ans. (a+b-c)*(d-e)/(f+g-h)

Ques 8. What is Array with example? Write it's algorithm and operations.

Ans. An array is a collection of element of similar data type.

e.g - Int A = 2, 3, 5, 3, 8, 13 

Array

Operations on array

Ques 9. Explain queue with it's operation and algorithms.

Ans. A queue is a kind of linear array which follows the order of First in first out (FIFO).

In queue Insertion can only take place through one end called as REAR. and deletion can only take place through one end called as FRONT.

Operations on queue

Enqueue- Adding element to the queue is called enqueue.

Dequeue- Removing element from queue is called dequeue.

Algorithm of Enqueue

ENQUEUE(Q, M, F, R, ITEM)

1. IF REAR = MAX-1

Write Overflow [End of IF]

2. IF FRONT = -1 AND REAR = -1

SET FRONT = REAR = 0

ELSE SET REAR = REAR +1

3. SET QUEUE[REAR] = ITEM

4. EXIT

Algorithm of Dequeue

DEQUEUE(Q, M, R, F)

1. IF FRONT>REAR OR FRONT = -1

Write Underflow

2. SET QUEUE[FRONT] = ITEM

3. SET FRONT = FRONT +1

4. EXIT

Ques 10. Explain Bubble Sort with it's example and algorithm.

Ans. Bubble Sort is a simple sorting algorithm that compares two adjacent element and swaps them until they are sorted.

Bubble Sort is preferred where complexity does not matter.

Algorithm

BUBBLE(A, N)

1. REPEAT STEPS 2 AND 3 WHILE I =1 TO <N-1

2. SET PTR =1

3. REPEAT WHILE PTR<=N-I:

      (a) IF DATA[PTR] > DATA[PTR+1], THEN:

              SWAP(DATA[PTR], DATA[PTR+1]

      (b) SET PTR = PTR + 1

4. EXIT

Ques 13. What is BST? How it is different from the Binary Tree? Write an algorithm for PREORDER, INORDER AND POSTORDER 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.

PREORDER 

1. REPEAT STEPS 2 TO 4 WHILE TREE =! NULL

2. WRITE ROOT->DATA

3. PREORDER(ROOT->LEFT)

4. PREORDER(ROOT->RIGHT)

5. END

INORDER 

1. REPEAT STEPS 2 TO 4 WHILE TREE =! NULL

2. INORDER(ROOT->LEFT)

3. WRITE ROOT->DATA

4. INORDER(ROOT->RIGHT)

5. END

POSTORDER

1. REPEAT STEPS 2 TO 4 WHILE TREE =! NULL

2. POSTORDER(ROOT->LEFT)

3. POSTORDER(ROOT->RIGHT)

4. WRITE ROOT->DATA

5. END