# CS301 – Data Structures Final Term Solved Papers(Mega File)

### CS301 – Data Structures Final Term Solved Papers(Mega File)

Name of two divide and conquer algorithm (2 marks)

• Merge Sort
• Quick Sort
• Heap Sort

These three algorithms fall under ‗divide and conquer category‘.

Difference between call by value n call by reference (2 marks)

In case of call by value, a copy of object is made and placed at the time of function calling in the activation record. By using the references, we are not making the copy but send the address of the variable that function can use the original value.

Heap and two types of heap(3)

Heap is a data structure of big use and benefit. It is used in priority queue. ―The definition of heap is that it is a complete binary tree that conforms to the heap order‖. Here heap order means the min and max heap. Max heap: In max heap, each node has a value greater than the value of its left and right child nodes. Moreover, the value of the root will be largest and will become lesser at downward levels. Min heap: in a (min) heap for every node X, the key in the parent is smaller than (or equal to) the key in X. This means that the value in the parent node is less than the value on its children nodes.

Height of a tree is 5 find sum of heights (2)

Height = 5

Nodes = 2^h = 2^5 =32

Sum of Nodes = N-(h+1)= 32-(5+1) = 32-6 = 26

Here is an array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.

Suppose that we are doing a binary search for an element. Indicate any elements that will be found by examining two or fewer numbers from the array. (Marks: 5)

If there is an array of 15 elements, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15} it wants to know which elements can be discovered by examining two or fewer elements. I want assume the divide and conquer aspect of a binary search, so that leads me to think these elements will be found 1, 2, 14, 15, 7, 3 rather; 1, 2, 3, 4, 6, 8, 14, 15

1 and 15 for heads and tails

2, and 14 for next elements (following or preceding)

1/2 of 15 is either 6, or 8, from 7.5 and 1/2 of 6 = 3

1/2 8 = 4

Write one example of hashing?

Hashing can be used to store the data. Suppose we have a list of fruits. The names of Fruits are in string. The key is the name of the fruit. We will pass it to the hash Function to get the hash key.

HashCode (“apple”) = 5

We pass it to the string ―apple‖. Resultantly, it returns a number 5.

How do we carry out degeneration of Complete Binary Tree?

Degeneration of the (original) binary tree is mainly reflected by degeneration of the internal infix trees and less by degeneration of the external height of the PPbin tree.

What is a skip List?

A skip list for a set S of distinct (key, element) items is a series of lists S0, S1 , … , Sh such that

• Each list Si contains the special keys +∞ and -∞
• List S0 contains the keys of S in non-decreasing order
• Each list is a subsequence of the previous one, i.e., S0 ⊇ S1 ⊇ … ⊇ Sh
• List Sh contains only the two special keys

How we can generate a maze with the help of union

How can we generate maze? The algorithm is as follows:

• Randomly remove walls until the entrance and exit cells are in the same set.
• Removal of the wall is the same as doing a union operation.
• Do not remove a randomly chosen wall if the cells it separates are already I the same set.

Write down the C++ code to implement insertion sort algorithm.

Following is the code of the insertion sort in C++.

void insertionSort(int *arr, int N)

{

int pos, count, val;

for(count=1; count < N; count++)

{

val = arr[count];

for(pos=count-1; pos >= 0; pos–)

if (arr[pos] > val)

arr[pos+1]=arr[pos];

else break;

arr[pos+1] = val;

}

}

Q2. What is Table ADT? Discuss any two implementations of table ADT. ( Marks: 5)

The table, an abstract data type, is a collection of rows and columns of information.

• Implementation of Table
• Unsorted Sequential Array
• Sorted Sequential Array

Suppose we have the following representation for a complete Binary Search Tree, tell the Left and Right child nodes and Parent node of the node D ( Marks: 5)

A B C D E F G H I J K L M N O P Q R S T …

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 …

parent: B using formula(i/2)

left child:-H 2i=2*4=8=H

Right child:-I 2i+1=8+1=9=I

What is an Equivalent relation? Give any two examples.

A binary relation R over a set S is called an equivalence relation if it has following properties‘:

1. Reflexivity: for all element x ȟ S, x R x
2. Symmetry: for all elements x and y, x R y if and only if y R x
3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z

Example; sets of peoples ,electric circuit domain

127

7 3

24 25

20 13

2

What are the properties of equivalence class? 3marks

A binary relation R over a set S is called an equivalence relation if it has following Properties

• Reflexivity: for all element x ∈ S, x R x
• Symmetry: for all elements x and y, x R y if and only if y R x
• Transitivity: for all elements x, y and z, if x R y and y R z then x R z

How heap sort works to set a set of data. 2Marks

Min heap and max heap are used to sort the data. Min heap convert the data in ascending sorted order and max heap convert the in descending order.

The table, an abstract data type, is a collection of rows and columns of information.

List linked list is one choice to implement table abstract data type. For unsorted elements, the insertion at front operation will take constant time. But if the data inside the list is kept in sorted order then to insert a new element in the list, the entire linked list is traversed through to find the appropriate position for the element.

If we allow assignment to constants what will happen?

Suppose ‗a‘ has the value number 3. Now we assigned number 2 the number 3 i.e. all the number 2 will become number 3 and the result of 2 + 2 will become 6. Therefore it is not allowed.

Explain the process of Deletion in a Min-Heap

We have to write a function deleteMin(), which will find and delete the minimum number from the tree. Finding the minimum is easy; it is at the top of the heap.

Give any three characteristics of Union by Weight method.

Following are the salient characteristics of this method:

• Maintain sizes (number of nodes) of all trees, and during union.
• Make smaller tree, the sub-tree of the larger one.
• Implementation: for each root node i, instead of setting parent[i] to -1, set it to -k if tree rooted at i has k nodes.

“For smaller lists, linear insertion sort performs well, but for larger lists, quick sort is suitable to apply.” Justify why?

Since for smaller lists number of comparisons and interchange (if needed) decreases radically in insertion sort than quick sort. For larger lists, opposite occurs in both sorting techniques.

What is Disjoint Sets? Explain with an example.

Disjoint sets – Two sets are disjoint if they have no elements in common.

Example:-Suppose there are many people around you. How can we separate those who are related to each other in this gathering?

We make groups of people who are related to each other. The people in one group will say that they are related to each other. Similarly we can have many groups. So every group will say that they are related to each other with family relationship and there is no group that is related to any other group. The people in the group will say that there is not a single person in the other group who is related to them.

Give the difference between strict and complete binary tree.

A binary tree said to be a strictly binary tree if every non-leaf node in a binary has non-empty left and right sub trees. If there are left and right sub trees for each node in the binary tree as shown a complete binary tree.

A complete binary tree can be stored in an array. While storing the tree in an array we leave the first position (0th index) of the array empty. Why?

In case of having a node with left and right children, stored at position i in the array, the left child will be at position 2i and the right child will be at 2i+1 position. If the value of i is 2, the parent will be at position 2 and the left child will be at position 2i i.e. 4 .The right child will be at position 2i+1 i.e. 5. We have not started the 0th position. It is simply due to the fact if the position is 0, 2i will also become 0. So we will start from the 1st position, ignoring the 0th.

Give the effect of sorted data on Binary Search.

The binary tree is a fundamental data structure used in computer science. The binary tree is a useful data structure for rapidly storing sorted data and rapidly retrieving stored data.

Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

Draw this array after the FIRST iteration of the large loop in an insertion sort (sorting from smallest to largest). This iteration has shifted at least one item in the array!

5 3 8 9 1 7 0 2 6 4

1st step 3 5 8 9 1 7 0 2 6 4

2nd step 1 3 5 8 9 7 0 2 6 4

3rd step 1 3 5 7 8 9 0 2 6 4

4th step 0 1 3 5 7 8 9 2 6 4

5th step 0 1 2 3 5 7 8 9 6 4

6th step 0 1 2 3 5 6 7 8 9 4

7th step 0 1 2 3 4 5 6 7 8 9

Give your comment on the statement that heap uses least memory in array representation of binary trees. Justify your answer in either case.

A heap is a complete binary tree, so it is easy to be implemented using an array representation

It is a binary tree with the following properties:-

Property 1: it is a complete binary tree

Property 2: the value stored at a node is greater or equal to the values stored at the children

From property 2 the largest value of the heap is always stored at the root

Explain the following terms:

1. Collision
2. Linear Probing

Collision:

When two values hash to the same array location, this is called a collision..

Linear Probing

When there is a collision, some other location in the array is found. This is known as linear probing. In linear probing, at the time of collisions, we add one to the index and check that location. If it is also not empty, we add 2 and check that position. Suppose we keep on incrementing the array index and reach at the end of the table. We were unable to find the space and reached the last location of the array.

In the quadratic probing when a collision happens we try to find the empty location at index + 1^2. If it is filled then we add 2^2 and so on. Quadratic probing uses different formula:

1. Use F(i) = i2 (square of i) to resolve collisions
2. If hash function resolves to H and a search in cell H is inconclusive, try H + 12, H + 22, H + 32

What are different applications of Hashing?

• Compilers use hash tables to keep track of declared variables (symbol table).
• A hash table can be used for on-line spelling checkers — if misspelling detection (rather than correction) is important, an entire dictionary can be hashed and words checked in constant time.
• Game playing programs use hash tables to store seen positions, thereby saving computation time if the position is encountered again.

Give your comments on the statement: “Efficiently developed data structures decrease programming effort”

Reduces programming effort by providing useful data structures and algorithms so you don’t have to write them yourself.

Increases performance by providing high-performance implementations of useful data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be easily tuned by switching implementations.

When Hashing is NOT suitable?

Hash tables are not so good if there are many insertions and deletions, or if table traversals are needed — in this case, AVL trees are better.

Heapify the elements of the following array (reading from left to right ) into a Min Heap and show that Min Heap contents in the form of array as shown below, original array 6 5 3 9 1 2 10 8 –

Min heap

Heapified array 1 5 2 8 6 3 10 9

8 6

5

3 10

2

1

9

Here is an array of ten integers:

5 3 8 9 1 7 0 2 6 4

Show the first three merging steps for Merge sort on this array.

5 3 8 9 1 7 0 2 6 4

1st step 5 3 8 9 1 7 0 2 6 4

2nd step 3 5 8 9 1 7 0 2 4 6

3rd step 3 5 8 9 1 7 0 2 4 6

4th step 1 3 8 5 9 2 6 7 0 4

5th step 1 3 8 5 9 2 6 7 0 4

6th step 1 2 3 6 7 8 0 5 4 9

Consider the following Min Heap apply operation delMin on it and show the resultant Heap,

It is clear from the definition of min-heap that it should be in the root of the tree. So finding the minimum is very easy. Here node 5 is operational node that has to be deleted.

Which implementation of disjoint set is better with respect space and why?

An array that is a single dimensional structure and seems better with respect to space. Suppose we have 1000 set members i.e. names of people. If we make a Boolean matrix for 1000 items, its size will be 1000 x 1000. Thus we need 1000000 locations for Boolean items, its size will be 1000 x 1000. Thus we need 1000000 locations for Boolean values. In case of an array the number of location will be 1000. Thus this use of array i.e. tree like structure is better then two dimensional arrays in term of space to keep disjoint sets and doing union and find operation.

The table, an abstract data type, is a collection of rows and columns of information.

6

7 9

8 12 13

6 9

8 7 1

2

1

3

Implementation of Table

Unsorted Sequential Array

Sorted Sequential Array

Suppose the following numbers are stored in an array „BS: 32,51,27,85,66,23,13,57

We apply Bubble sort to array „BS. Show step by step sorting. You have to write only two passes that is passing 1 and pass 2.

Hint; while concern step by step sorting there are 6 passes involved to sort array nums. You have to show all passes

Pass one:-

32 51 27 85 66 23 13 57

Step1 32 51 27 85 66 23 13 57

Step2 32 27 51 85 66 23 13 57

Step3 32 27 51 66 85 23 13 57

Step4 32 27 51 66 23 85 13 57

Step5 32 27 51 66 23 13 85 57

Step6 32 27 51 66 23 13 57 85

Pass two:-

32 27 51 66 23 13 57 85

Step1 32 27 51 66 23 13 57 85

Step2 27 32 51 66 23 13 57 85

Step3 32 27 66 23 66 13 57 85

Step4 32 27 66 23 13 66 57 85

Step5 32 27 66 23 13 57 66 85

Step6 32 27 66 23 13 57 66 85

Question No: 36 ( Marks: 5 )

Give two different reasons to explain why the following binary tree is not a heap:

Above array is not min heap or max heap because every parent node has not minimum or maximum value. In max heap, each parent node has a value greater than the value of its left and right child nodes. In min heap, each parent node has a value less than the value of its left and right child nodes.

Describe the conditions for second case of deletion in AVL Trees.

This is the case where the parent of the deleted node had a balance of 1 and the node was deleted in the parent‘s left sub tree.

How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7?

Leaf Node = 2^d = 2^7 = 128

Non leaf Nodes = 2^d -1 = (2^7) -1 = 128 – 1 = 127

Write C++ algorithm for Binary Search

int isPresent(int *arr, int val, int N)

{

int low = 0;

int high = N – 1;

int mid;

while ( low <= high )

{

mid = ( low + high )/2;

if (arr[mid] == val)

return 1; // found!

else if (arr[mid] < val)

low = mid + 1;

else

high = mid – 1;

}

Consider the following array of values; show how the binary search algorithm would find the value -5. Clearly show/explain your work; that is, show the values of start, end, etc. for each step of the algorithm.

Value < mid

Value = -5

Mid=(0+8)/2=4

Low=0

High=mid -1=4-1

-15 -5 0 7 13 16 27 30 42

0 1 2 3 4 5 6 7 8

low high mid

Starting from the low which is -15.now compare the -5 form the next index which is at position 1.

-15 -5 0 7 13 16 27 30 42

0 1 2 3 4 5 6 7 8

low high mid

-15 -5 0 7 13 16 27 30 42

0 1 2 3 4 5 6 7 8

low high mid

If we inset a new element into an AVL tree of height 4, is one rotation sufficient to re-establish balance? Justify your answer.

No, one rotation is not always sufficient to re-establish balance. For example, consider the insertion of the shaded node in the following AVL tree: Though the original tree was balanced, more than one rotation is needed to restore balance following the insertion. This can be seen by an exhaustive enumeration of the rotation possibilities. The problem asks for a tree of height 4, so we can extend the above example into a larger tree:

Write down the C++ code from Selection Sort Algorithm.

void selectionSort(int *arr, int N)

{

int posmin, count, tmp ;

for (count=0;count<N;count++)

{

posmin = findIndexMin(arr, count, N) ;

tmp=arr[posmin] ;

arr[posmin]=arr[count] ;

arr[count]=tmp ;

}

}

int findIndexMin (int *arr, int start, int N)

{

int posmin=start ;

int index ;

for(index=start; index < N; index++)

if (arr[index]<arr[posmin])

posmin=index ;

return posmin ;

}

3 important characteristics of skip list.

Search and update require linear time

Fast Searching of Sorted Chain

Provide alternative to BST (binary search trees) and related tree structures.

Balancing can be expensive.

Relatively recent data structure: Bill Pugh proposed it in 1990

Drawback of using array to store BST.

The drawback of using is the limitations that array being of fixed size can only store a fixed number of elements. Therefore, no more elements can be stored after the size of the array is reached.

class Node {

public:

int get() { return object; }; // returns the value of the element

void set(int object) { this->object = object; }; // set the value of the element

Node* getNext() { return nextNode; }; // get the address of the next node

void setNext(Node* nextNode) // set the address of the next node

{ this->nextNode = nextNode; };

Node* getPrev() { return prevNode; }; // get the address of the prev node

void setPrev(Node* prevNode) // set the address of the prev node

{ this->prevNode = prevNode; };

private:

int object; // it stores the actual value of the element

Node* nextNode; // this points to the next node

Node* prevNode; // this points to the previous node

};

What you conclude from the running time analysis of disjoint sets.

We conclude that:

• union is clearly a constant time operation
• Running time of find(i) is proportional to the height of the tree containing node i.
• This can be proportional to n in the worst case (but not always).
• Goal: Modify union to ensure that heights stay small

What is c++ template.

A template is a function or class that is written with a generic data type. When a programmer uses this function or class the generic data type is replaced with the data type needed to be used in the template function or in the template class. We only give the data type of our choice while calling a template function or creating an object of the template class. The compiler automatically creates a version of that function or class with that specified data type.

Explain and write the code for union and find operation of parent array in disjoint sets.

Find ( i )

This loop is used to find the parent of an element or the name of the set that contains that element.

// traverse to the root (-1)

for(j=i; parent[j] >= 0; j=parent[j])

;

return j;

Union ( i, j )

Now let‘s see the code for the function of union. Here we pass two elements to the function union. The union

finds the roots of i and j. If i and j are disjoint sets, it will merge them. Following is the code of this function.

root_i = find(i);

root_j = find(j);

if (root_i != root_j)

parent[root_j] = root_i;

In the code, we see that at first it finds the root of tree in which i exists by the find(i) method and similarly finds the root of the set containing j by find(j). Then there is a check in if statement to see whether these sets (roots) are same or not. If these are not the same, it merges them in such a fashion that the root i is set as the parent of root j. Thus, in the array where the value of root j exists, the value of root i becomes there.

Write the code of the perculateDown() function and also comment it.

template <class eType>

void Heap<eType>::percolateDown( int hole )

{

int child;

eType tmp = array[ hole ];

for( ; hole * 2 <= currentSize; hole = child )

{

child = hole * 2;

if( child != currentSize && array[child+1] < array[ child ] )

child++; // right child is smaller

if( array[ child ] < tmp )

array[ hole ] = array[ child ];

else break;

}

array[ hole ] = tmp;

}

For smaller list linear insertion sort is perform well but for large list Quick sort suitable to apply/justify why????????

Since for smaller lists number of comparisons and interchange (if needed) decreases radically in insertion sort than quick sort. For larger lists, opposite occurs in both sorting techniques.

Write the applications of heap.

The stack and heap are used in function calls. When we allocate memory dynamically in our programs, it is allocated from the heap. The use of priority queue with the help of heap is a major application. The priority queue is itself a major data structure, much-used in operating systems. Similarly priority queue data structure is used in network devices especially in routers. Heap data structure is also employed in sorting algorithms.

Write the application of binary search tree