Data Structure 2019 Winter Paper Solution

Q1

a ) define primitive and non-primitive data types with examples. 03

Ans:

primitive data types

• primitive-data types also called system-defined data types are data types that already defined by the system.


• primitive-data types are pre-defined in programming languages for use. 


• Examples of these data types are int, float, and characters, In some language the bool is also an example of a primitive data type.


• Primitive-data types has no additional methods.

non-primitive data types

• non-primitive data types also called user-defined data types are data types that are defined or created by the user as per the need.


• It can be a group of primitive-data types


• Primitive-data types have additional methods.


• Examples of these data types are array and string, structure, pointers, In language like c++ and java we have the classes as non-primitive data type or user-defined data types.

 

b ) Differentiate linear and non-linear data structures. 04

Ans:

[su_table]

Linear Data Structure	Non-Linear Data Structure
In a linear data structure, data elements are arranged in a linear order where each and every element is attached to its previous and next elements.	In a non-linear data structure, data elements are arranged in a hierarchical manner.
Elements are accessed in a sequential order but it is not compulsory to store all elements sequentially	Elements of non-linear data structure are accessed in a non-linear order
The implementation of these data types is easy in comparison to non-linear data structure.	The implementation of these data types is complex in comparison to the linear data structure.
There are only two ways of traversal are possible in linear data structure	There are many ways of traversal are possible in non-linear data structure
In a linear data structure, memory is not utilized in an efficient way.	In a non-linear data structure, memory is utilized in an efficient way.
Examples: Arrays, Linked lists, stack, queues	Examples: Trees and graphs

[/su_table]

 

 

c ) write algorithms for PUSH and POP stack operations. 07

Ans:

Algorithms for PUSH operation on the stack.

Start:

step 1: tack input data

step 2: check if the stack overflows then return and if not then do the next step.

step 3: Increment top by one then store data into the array.

stop

Algorithms for POP operation on the stack.

Start:

step 1: check if the stack underflow then return and if not then do the next steps.

step 2: store the data in some other variable. and decrement top by one.

step 3: return the stored data.

stop

Q2

 a ) Enlist applications of stack and queue. 03

Application of stack:

• Infix to prefix conversation.


• Evaluation of postfix expression.


• undo and redo sequence.


• In function calling and evaluation as recursion.


• finding of spans (  example spans in the stock market ).


• In the web browsers in forward and back buttons.


• stack is also useful in the traversal of trees and graphs.

Application of queue:

• In the operating system to perform some scheduled jobs in order to arrival queue is used, for example the print queue


• multiprogramming


• waiting time of customers at the call center.


• In asynchronous data transfer.


• in real-world queue simulations as lines at ticket counters.


•  queue is also used for the traversal of trees and graphs.

b )  Evaluate the following postfix expression using stack. Show each step. 04
5  3  +  6  2  /  *  3  5  *  +

1 ] 5 is pushed into the stack

2 ] Now 3 is pushed into the stack

3 ] Now as + is the operator 3 and 5 will pop out and addition operation perform on them and as finial answer 8 will be pushed into the stack

4 ] now 6 is pushed into the stack

5] now 2 is pushed into the stack

6 ] Now as / is the operator 2 and 6 will pop out and division operation perform on them and as finial answer 3 will be pushed into the stack

7 ] Now as * is the operator 3 and 8 will pop out and multiplication operation perform on them and as finial answer 24 will be pushed into the stack

8 ] Now 3 is pushed into the stack

9 ] Now 5 is pushed into the stack

10 ] Now as * is the operator 5 and 3 will pop out and multiplication operation perform on them and as finial answer 15 will be pushed into the stack

11 ] Now as + is the operator 15 and 24 will pop out and addition operation perform on them and as finial answer  39 will be pushed into the stack

12 ] Now as the finial answer we get 39

 

c ) Write a C function for insertion and deletion operation in a simple queue. 07

 

OR

c ) Write an algorithm to delete an element from circular queue. Show the steps of insertion and deletion operation in sample circular queue. 07

Algorithm to delete an element from the circular queue.

• STEP 1 START


• STEP 2 Store the element to delete.


• STEP 3 If front == -1 then Queue Underflow.


• STEP 4 Element deleted from queue is cqueue_arr[front].


• STEP 5 if (front==rear) then front= -1; rear= -1; else goto step 6.


• STEP 6 if (front == MAX - 1) then front= 0 else goto step 7.


• STEP 7 front = front + 1.


• STEP 8 STOP

Q3

(a) Describe the advantages of linked list over array. 03

Ans:

Linked List is considered a data structure for which size is not fixed and memory is allocated from the heap as when needed.

whenever we need more nodes in Linked List, We can increase the size of Linked List Dynamically that not possible in the case of arrays.

Linked list's elements are non-contiguous in memory so we can create a linked list even contiguous memory block is not available.

Insertion and deletion become easy in linked lists rather than array.

(b) Write an algorithm to insert a node at the last position in doubly linked list. 04

• STEP 1 START


• STEP 2 creat Newnode and data to be store in node


• STEP 3 Assign data in node and  Newnode -> next and Newnode -> previous to NULL


• STEP 4  if( head == NULL) Then head = node; goto step no 9 else goto step 5


• STEP 5 temp = head;


• STEP 6  Repeat step no 7 until temp->next != NULL


• STEP 7  temp = temp -> next;


• STEP 8  temp->next = Newnode; Newnode-> previous = temp;  goto step no 9


• STEP 9 STOP

(c) Write an algorithm to print the singly linked list in reverse order using stack. 07

• STEP 1 START


• STEP 2  Creat Stack


• STEP 3  Temp = head


• STEP 4  Repeat step no 5 until temp != NULL


• STEP 5  Push Temp->data into stack then Temp=Temp->next;


• STEP 6  Repeat step no 7 until Stack is not emty


• STEP 7  pop out the element at top and print the element


• STEP 8  Delete the stack


• STEP 9  STOP

OR

Q.3

(a) Describe the following terms with respect to binary tree:  03
           (1) depth of tree (2) balanced tree (3) complete tree  

ANS:

 (1) Depth of tree:

     The number of edges from the root node to the leaf node of the tree is called as the Depth of the Tree

(2) Balanced tree

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

(3) Complete tree 

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

(b) Construct the binary tree for the following tree traversals. 04
      Inorder: B F G H P R S T W Y Z
      Preorder: P F B H G S R Y T W Z

Ans:

(c) Write an algorithm to insert a node into binary search tree. 07

STEP 1 START

STEP 2 Create a new BST node and assign values to it.

 STEP 3 insert(node, key)

i) If ( root == NULL ) return the new node to the calling function.

ii) if ( root->data  <= key ) call the insert function with root -> right and assign the return value in

root ->right.

root->right = insert(root->right,key)

iii) if ( root->data > key ) call the insert function with root->left and assign the return value in root->left.

root->left = insert(root->left,key)

STEP 4 return the original root pointer to the calling function.

STEP 5 STOP

 Q.4

(a) Prove that a binary tree with 20 nodes have 21 null branches. 03

In a binary tree, each node has at most two children, and each node except the root node has a unique parent.

• If a node contains one child, that means the node contains one null link.

• If a node contains no child, that means the node contains two null links.

• The parent node of a node cannot be null.

Thus, each node in a binary tree has two outgoing links.

Since, each node, except the root node, in a binary tree has a unique parent.

So, the number of links to the parent of each node, except root, in a binary of N nodes has 2N links.

Since, each node, except the root node, in a binary tree has a unique parent.

So, the number of links to the parent of each node, except root, in a binary of N nodes is N -1 nodes

therefore, the links that represent null are 2N - ( N - 1 ) = N + 1

Hence, there are 21 null links in a binary tree of 20  nodes

(b) Write a recursive algorithm for preorder traversal of binary tree. 04

STEP 1 START

STEP 2 preorder ( root )

• if( root == NULL ) then return


• else do next three-steps

1.  print the data at the root node


2. call the preorder function with the left node of root node   preorder( root->left )


3. call the preorder function with the right node of root node   preorder( root->right )

STEP 3 STOP

(c) Describe Prim’s minimum spanning tree algorithm with an example. 07

        visit        

OR

Q.4

(a) Show the resultant BST after applying following operations in sequence on given tree. 03

       a) Delete 8 b) Insert 9 c) Delete 7

ANS:

(b) Enlist and describe different ways for representing graph data structure with example. 04

The following two are the most commonly used representations of a graph.
1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix:
Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Adjacency List:
An array of lists is used. The size of the array is equal to the number of vertices. Let the array be an array[]. An entry array[i] represents the list of vertices adjacent to the I th vertex. This representation can also be used to represent a weighted graph. The weights of edges can be represented as lists of pairs. Following is the adjacency list representation of the above graph.

(c) Show the steps of BFS and DFS traversal for following graph starting from vertex 2. Consider adjacency list is sorted in ascending order. 07

Ans:

Adjacency list:

0 -> 6 -> 7

1 -> 6 -> 4

2 -> 0 -> 1 -> 8

3 -> 4 -> 5

4

5 -> 4

6 -> 3 -> 4

7 -> 3 -> 6

8 -> 0 -> 7

BFS traversal :

In BFS traversal we traverse vertex using a queue, fist 2 goes to queue and got printed now while dequeue the 2 the vertex connected to vertex 2 gets enqueued so from the adjacency we can find that the vertex  0, 1 and 8 goes to the queue and we make visited them for future traversal. so now

queue :  0 1 8

BFS: 2

Now 0 gets printed and while dequeue the vertex 0 the vertex 6 and 7 are enqueued in queue and we make them visited. so now

queue :  1 8 6 7

BFS : 2 0

Now 1 gets printed and while dequeue the vertex 1 only vertex 4 enqueued in queue, vertex 6 is not enqueued because that already visited and we make vertex 4 as visited. so now

queue :  8 6 7 4

BFS : 2 0 1

Now 8 get printed from the queue and while dequeue the vertex 8, no vertex are enqueued in queue because all vertex of 8 are already visited. so now

queue : 6 7 4

BFS : 2 0 1 8

Now 6  get printed from the queue and while dequeue the vertex 6 only vertex 3 enqueue in queue, vertex 3 is not enqueued because that already visited and we make vertex 3  as visited. so now

queue :  7 4 3

BFS : 2 0 1 8 6

Now 7 get printed from the queue and while dequeue the vertex 7, no vertex are enqueued in queue because all vertex of 7 are already visited. so now

queue:  4 3

BFS : 2 0 1 8 6 7

Now 4 get printed from the queue and while dequeue the vertex 4, no vertex are enqueued in queue because vertex 4 has no edges. so now

queue:  3

BFS : 2 0 1 8 6 7 4

Now 3 get printed from the queue and while dequeue the vertex 3, vertex 5 is enqueued in queue. so now

queue:  5

BFS : 2 0 1 8 6 7 4 3

Now 5 get printed from the queue and while dequeue the vertex 5, no vertex are enqueued in queue because all vertex of 5 are already visited. so now

queue:

BFS : 2 0 1 8 6 7 4 3 5

Now queue is in underflow condition and it is the end of our traversal so finally we get BFS traversal as 2 0 1 8 6 7 4 3 5

DFS: 2  0  6  3  4  5  7  1  8

Q.5

(a) Write an algorithm for linear searching. 03

ANS:

Linear Search ( Array A, Value x)

STEP 1 START
STEP 2 Set i to 1
STEP 3 if i > n then go to step 8
STEP 4 if A[ i ] = x then go to step 7
STEP 5 Set i to i + 1
STEP 6 Go to Step 3
STEP 7 Print Element x Found at index i and go to step 9
STEP 8 Print element not found
STEP 9 STOP

(b) Describe the indexing structure for index file. 04

(c) Write an algorithm for merge sort. Show the steps of its working with sample data. 07

•  START


•  MargSort ( arr [  ], start, end )
  
  
  
  •   if end > start
  
  
  
  

• 
  
  
  
  • Find the middle index of the array to divide the array into two parts: middle = (start + end )/2
  
  
  
  

• 
  
  
  
  • Call MargeSort for the first half :
    
    
    
    • Call MargeSort ( arr, start, middle)
    
    
    
    
  
  
  
  

• 
  
  
  
  • Call MargeSort for the second half :
    
    
    
    • Call MargeSort ( arr, middle + 1, end)
    
    
    
    
  
  
  
  

• 
  
  
  
  • Now marge that two-part sorted
    
    
    
    • Call marge ( arr,  start, middle, end )
    
    
    
    
  
  
  
  

• marge ( arr,  start, middle, end )

• 
  
  
  
  • Set I, j, k to 0
  
  
  • set LLarray ( length of left array) to middle - start + 1 and LRarray ( length of right array)  to end - middle
  
  
  • creat array L[ LLarray ]  and  R[ LRarray ]
  
  
  
  

• 
  
  
  
  • Copy data to temp arrays L[ ] and R[ ]
    
    
    
    • 
      
      
      
      • Until i < LLarray repeat next two  steps
        
        
        
        • L[ i ] = arr[ i + start ]
        
        
        • i++
        
        
        
        
      
      
      • Until j < LRarray repeat next two  steps
        
        
        
        • R[ j ] = arr[ middle + 1 + j ]
        
        
        • j++
        
        
        
        
      
      
      
      
    
    
    
    
  
  
  
  

• 
  
  
  
  • Set i, j to 0 and k to start
  
  
  
  

• 
  
  
  
  • Merge the temp arrays back into arr[  ] with sorting
    
    
    
    • Until i < LLarray && j < LRarray repeat next steps
      
      
      
      • if ( L[ i ] <= R[ j ] ) then do arr[ i ] = L[ i ] and i++;
      
      
      • else  do arr[ j ] = R[ j ] and j++
      
      
      • k++
      
      
      
      
    
    
    
    
  
  
  
  

• 
  
  
  
  • 
    
    
    
    • copy the  remaining element of L[ ] if there any element is present
    
    
    • Until i < LLarray repeat next steps
      
      
      
      • arr[ k ] = L[ i ]
      
      
      • i++ and k++
      
      
      
      
    
    
    • copy the  remaining element of R[ ] if there any element is present
    
    
    • Until j < LRarray repeat next steps
      
      
      
      • arr[ k ] = R[ i ]
      
      
      • j++ and k++
      
      
      
      
    
    
    
    
  
  
  
  

 

OR

Q.5

(a) Define hash function. Describe any two hash methods with example. 03

Ans:

Hash function is a function which is applied on a key by which it produces an integer, which can be used as an address of hash table. Hence one can use the same hash function for accessing the data from the hash table. In this the integer returned by the hash function is called hash key.

Types of hash function

1. Division method

In this the hash function is dependent upon the remainder of a division. For example:-if the record 52,68,99,84 is to be placed in a hash table and let us take the table size is 10.

Then:

h(key)=record% table size.
2=52%10
8=68%10
9=99%10
4=84%10

2. Mid square method

In this method firstly key is squared and then mid part of the result is taken as the index. For example: consider that if we want to place a record of 3101 and the size of table is 1000. So 3101*3101=9616201 i.e. h (3101) = 162 (middle 3 digit)

(b) Write an algorithm for binary searching. 04

• START


• binarySearch(arr[ ], start, end, x)
  
  
  
  • if( start >= end ) then do next steps else return -1
  
  
  • find the middle element of array m = ( start + end )/2
  
  
  • if ( arr[ m ] = x ) return m
  
  
  • if (arr[ m ] < x ) then call binarySearch( arr[  ], start, m-1, x)
  
  
  • if (arr[ m ] > x ) then call binarySearch( arr[  ], m+1, end, x)
  
  
  
  


• STOP

(c) Apply bubble sort on following data and show all steps. 07
       123, 34, 65, 105, 27, 79, 12, 10, 125, 156

For the 1st iteration:
123 34 65 105 27 79 12 10 125 156 - (123 > 34) so 123 and 34 get swapped this time
34 123 65 105 27 79 12 10 125 156 - (123 > 65) so 123 and 65 get swapped this time
34 65 123 105 27 79 12 10 125 156 - (123 > 105) so 123 and 105 get swapped this time
34 65 105 123 27 79 12 10 125 156 - (123 > 27) so 123 and 27 get swapped this time
34 65 105 27 123 79 12 10 125 156 - (123 > 79) so 123 and 79 get swapped this time
34 65 105 27 79 123 12 10 125 156 - (123 > 12) so 123 and 12 get swapped this time
34 65 105 27 79 12 123 10 125 156 - (123 > 10) so 123 and 10 get swapped this time
34 65 105 27 79 12 10 123 125 156 - (123 < 125) No swap in array
34 65 105 27 79 12 10 123 125 156 - (125 < 156) No swap in array

For the 2nd iteration:
34 65 105 27 79 12 10 123 125 156 - (34 < 65) No swap in array
34 65 105 27 79 12 10 123 125 156 - (65 < 105) No swap in array
34 65 105 27 79 12 10 123 125 156 - (105 > 27) so 105 and 27 get swapped this time
34 65 27 105 79 12 10 123 125 156 - (105 > 79) so 105 and 79 get swapped this time
34 65 27 79 105 12 10 123 125 156 - (105 > 12) so 105 and 12 get swapped this time
34 65 27 79 12 105 10 123 125 156 - (105 > 10) so 105 and 10 get swapped this time
34 65 27 79 12 10 105 123 125 156 - (105 < 123) No swap in array
34 65 27 79 12 10 105 123 125 156 - (123 < 125) No swap in array

For the 3rd iteration:
34 65 27 79 12 10 105 123 125 156 - (34 < 65) No swap in array
34 65 27 79 12 10 105 123 125 156 - (65 > 27) so 65 and 27 get swapped this time
34 27 65 79 12 10 105 123 125 156 - (65 < 79) No swap in array
34 27 65 79 12 10 105 123 125 156 - (79 > 12) so 79 and 12 get swapped this time
34 27 65 12 79 10 105 123 125 156 - (79 > 10) so 79 and 10 get swapped this time
34 27 65 12 10 79 105 123 125 156 - (79 < 105) No swap in array
34 27 65 12 10 79 105 123 125 156 - (105 < 123) No swap in array

For the 4rd iteration:
34 27 65 12 10 79 105 123 125 156 - (34 > 27) so 34 and 27 get swapped this time
27 34 65 12 10 79 105 123 125 156 - (34 < 65) No swap in array
27 34 65 12 10 79 105 123 125 156 - (65 > 12) so 65 and 12 get swapped this time
27 34 12 65 10 79 105 123 125 156 - (65 > 10) so 65 and 10 get swapped this time
27 34 12 10 65 79 105 123 125 156 - (65 < 79) No swap in array
27 34 12 10 65 79 105 123 125 156 - (79 < 105) No swap in array

For the 5rd iteration:
27 34 12 10 65 79 105 123 125 156 - (27 < 34) No swap in array
27 34 12 10 65 79 105 123 125 156 - (34 > 12) so 34 and 12 get swapped this time
27 12 34 10 65 79 105 123 125 156 - (34 > 10) so 34 and 10 get swapped this time
27 12 10 34 65 79 105 123 125 156 - (34 < 65) No swap in array
27 12 10 34 65 79 105 123 125 156 - (65 < 79) No swap in array

For the 6rd iteration:
27 12 10 34 65 79 105 123 125 156 - (27 > 12) so 27 and 12 get swapped this time
12 27 10 34 65 79 105 123 125 156 - (27 > 10) so 27 and 10 get swapped this time
12 10 27 34 65 79 105 123 125 156 - (27 < 34) No swap in array
12 10 27 34 65 79 105 123 125 156 - (34 < 65) No swap in array

For the 7rd iteration:
12 10 27 34 65 79 105 123 125 156 - (12 > 10) so 12 and 10 get swapped this time
10 12 27 34 65 79 105 123 125 156 - (12 < 27) No swap in array
10 12 27 34 65 79 105 123 125 156 - (27 < 34) No swap in array

For the 8rd iteration:
10 12 27 34 65 79 105 123 125 156 - (10 < 12) No swap in array
10 12 27 34 65 79 105 123 125 156 - (12 < 27) No swap in array

no swap in any iteration so flag become true and we get your sorted array.
Sorted array:
10 12 27 34 65 79 105 123 125 156

*************