BPUT Data Structure 2021-22

Part- III (16*2) Only Long Answer

3) Write algorithm for Insertion and Bubble sort? Illustrate the insertion sort algorithm
and bubble sort algorithm on input [30,20,10,60,70,40]. [16]
4) Write the non-recursive preorder traversal algorithm? What is the output obtained
after preorder, inorder and postorder traversal of the following tree. [16]

5) What is AVL tree? Find the complexity of insertion, deletion and searching in AVL
tree. Construct AVL tree for the following sequence of numbers- 50, 20, 60, 10, 8, 15,
32, 46, 11, 48. [16]
6) What is Quicksort? Write an algorithm to perform Quicksort with an example.
Compare its complexity with bubble sort. [16]

Part II
Answer Any Eight out of Twelve (6*8)
a) Define hashing? What are the properties of a good hash function? With necessary example
explain any one hashing techniques.
b) Write an algorithm for evaluating a postfix expression and evaluate the following postfix
expression using the algorithm AB+ CD / AD - EA^ + * where A=2, B=7, C=9, D=J, E=5.
c) Give an algorithm to perform binary search. Using the algorithm, search for
elements 23 and 47 in the given set of elements [12, 23, 27, 35, 39, 42, 50].
d) Design an algorithm for selection sort? Illustrate the working of selection sort
on the following array with seven elements [30, 45, 25, 32, 55, 60, 49].
e) Explain Merge Sort algorithm / pseudocode with the help of an example? Mention the
best case and worst case time complexity of Merge sort algorithm?
f) Write an algorithm to insert an element into a Heap? Derive the complexity of a Heap
sort.
g) List out the difference between doubly linked list and singly linked list? Explain with
example of following with doubly linked list.
i) Insert node in the beginning.
ii) Delete the node with given value.
h) How can you reverse 3 sting using stack? Give one example and show how you can
reverse a given string using stack.
i) What is stack? What are the basic operations associated with stack? Convert
following arithmetic infix expression into postfix using stack: a*(b+c)+(b/d)*a+z*u
j) With a suitable example, explain how polynomials are added using linked lists.
k) Create max heap for the following elements 33, 14, 65, 02, 76, 69, 59, 85, 47, 99, 98.
l) Write the algorithm for Prim’s and Kruskal’ Minimum Spanning Tree and explain with
 example?

Part I (2*10)

(Q1) Answer the following Questions:

a) What do you understand by the complexity of an algorithm?

b) Differentiate between DFS and BFS?
c) What are the applications of a linked list?
d) Define Big Oh, Big Omega and Big Theta Notations.
e) Differentiate between abstract and concrete data structure.
f) Write a recursive algorithm to perform preorder traversal.
g) What is a Priority Queue?
h) What is a Binary Search Tree (BST)?
i) Explain the concept of DEQUEUE?
j) Differentiate between Graph and Tree?

ANSWERS
Part- III (16*2) Only Long Answer
3) Write algorithm for Insertion and Bubble sort? Illustrate the insertion sort algorithm
and bubble sort algorithm on input [30,20,10,60,70,40].
(ANS)- Algorithm for Insertion Sort-Both the selection and bubble sorts
exchange elements. But insertion sort does not exchange elements. In
insertion sort the element is inserted at an appropriate place similar to
card insertion. Here the list is divided into two parts sorted and unsorted
sub-lists. In each pass, the first element of unsorted sub list is picked up
and moved into the sorted sub list by inserting it in suitable position.
Suppose we have ‘n’ elements, we need n-1 passes to sort the
elements.
Insertion sort works this way:

It works the way you might sort a hand of playing cards:

1. We start with an empty left hand [sorted array] and the cards face down
on the table [unsorted array].
2. Then remove one card [key] at a time from the table [unsorted array],
and insert it into the correct position in the left hand [sorted array].
3. To find the correct position for the card, we compare it with each of the
cards already in the hand, from right to left.

INSERTION_SORT (A)

1. FOR j ← 2 TO length[A]
2. DO key ← A[j]
3. {Put A[j] into the sorted sequence A[1 . . j − 1]}
 4. i←j−1
5. WHILE i > 0 and A[i] > key
6. DO A[i +1] ← A[i]
7. i←i−1
8. A[i + 1] ← key

Example: Following figure (from CLRS) shows the operation of

INSERTION-SORT on the array A= (5, 2, 4, 6, 1, 3). Each part
shows what happens for a particular iteration with the value
of j indicated. j indexes the "current card" being inserted into the hand.

Read the figure row by row. Elements to the left of A[j] that are greater
than A[j] move one position to the right, and A[j] moves into the
evacuated position.
Ex:- A list of unsorted elements are: 78 23 45 8 32 36 . The results of
insertion sort for each pass is as follows:-

Algorithm for Bubble sort-In bubble sort method the list is divided into
two sub-lists sorted and unsorted. The smallest element is bubbled
from unsorted sub-list. After moving the smallest element the
imaginary wall moves one element ahead. The bubble sort was
originally written to bubble up the highest element in the list. But there
 is no difference whether highest / lowest element is bubbled. This
method is easy to understand but time consuming. In this type, two
successive elements are compared and swapping is done. Thus, step-
by-step entire array elements are checked. Given a list of ‘n’ elements
the bubble sort requires up to n-1 passes to sort the data.

Algorithm for Bubble Sort: Bubble_Sort ( A [ ] , N )

Step 1 : Repeat For P = 1 to N 1 Begin
Step 2: Repeat For J = 1 to N – P Begin
Step 3 : If ( A [ J ] < A [ J – 1 ] )
Swap ( A [ J ] , A [ J – 1 ] )End For End For
Step 4 : Exit
Example:

Ex:- A list of unsorted elements are: 10 47

12 54 19 23 (Bubble up for highest value

shown here)