Cs301
Subjective solved questions
Question No: 27 (Marks: 2)
Give the difference between strict and complete binary tree.
Ans: A tree is a strictly binary tree if its each leaf node has non-empty left and right sub
trees, and If there are left and right sub-trees for each node in a binary tree is known as
Complete binary tree.
Question No: 28 (Marks: 2)
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?
Ans: Because we need a pointer in an array to point a position of node of tree. parent
node and the children nodes. In case of having a node with left and right children,
stored at position i in the array, the left 2i and the right child will be at 2i+1 position. If
the value Share your feedback/comments at pak.nchd@gmail.com to improve file|| Back
to TOP || File Version v3.2.0 published for Final Term
Of i 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
.
Question No: 29 (Marks: 2 )
Give any three characteristics of Union by Weight method.
Ans:
1. This is also calles union by size.
2. Maintain sizes (number of nodes) of all trees, and during union.
3. Make smaller tree, the subtree of the larger one.
4. for each root node i, instead of setting parent[i] to -1, set it
to -k if tree rooted at i has k nodes.
Question No: 35 ( Marks: 5 )Explain the following terms:
1. Collision
2. Linear Probing
3. Quadratic Probing
Ans:
Collision:
it takes place when two or more keys (data items) produce the same index.
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.
Quadratic Probing
In the quadratic probing when a collision happens we try to find the empty location at
index + 12. If it is filled then we add 22 and so on.
Quadratic probing uses different formula:
1. Use F(i) = i (square of i) to resolve collisions
2. If hash function resolves to H and a search in cell H is inconclusive, try
H + 1 rse to power 2 , H + 22, H + 32
Question No: 37 (Marks: 3 )
Suppose that we have implemented a priority queue by storing the items in a heap.
We are now executing a reheapification downward and the out-of-place node has
priority of 42. The node’s parent has a priority of 72, the left child has priority 52
and the node’s right child has priority 62. Which statement best describes the status
of the reheapification.
A. The reheapification is done.
B. The next step will swap the out-of-place node with its parent.
C. The next step will swap the out-of-place node with its left child.
D. The next step will swap the out-of-place node with its right child.
E. None of these
Question No: 31 ( Marks: 1 )
Describe the conditions for second case of deletion in AVL Trees.
Answer:
The node to be deleted has either left child (subtree) or right child (subtree). In this case
we bypass the node in such a way that we find the inorder successor of this node and
then link the parent of the node to be deleted to this successor node.Thus the node was
deleted.
Question No: 32 (Marks: 1 )
What is Table abstract data type?
Answer:
An abstract data structure is a mathematical model for a certain class of data structures
That have similar behavior; or for certain data types of one or more programming
Languages that have similar semantics.
Question No: 33 ( Marks: 2 )
How we can generate a maze .Give an algorithm.
Answer:
A maze can be generated by starting with a predetermined arrangement of cells (most
commonly a rectangular grid but other arrangements are possible) with wall sites
between them. This predetermined arrangement can be considered as a connected graph
with the edges representing possible wall sites and the nodes representing cells.
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 in
the same set.
Question No: 35 (Marks: 3 )
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
Question No: 35 (Marks: 3)
"For smaller lists, linear insertion sort performs well, but for larger lists, quick sort
is suitable to apply." Justify why?
Ans:
Quicksort sorts by employing a divide and conquer strategy to divide a list into two
sublists.Full example of Quicksort on a random set of numbers. The boxed element is the
pivot. It is always chosen as the last element of the partition. The steps are:
1.Pick an element, called a pivot, from the list.
2.Reorder the list so that all elements which are less than the pivot come before the pivot
and so that all elements greater than the pivot come after it (equal values can go either
way). After this partitioning, the pivot is in its final position. This is called the partition
operation.
3.Recursively sort the sub-list of lesser elements and the sub-list of greater elements
OR
Some divide-and-conquer algorithms such as quick sort and merge sort sort by
recursively dividing the list into smaller sublists which are then sorted.
A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, as insertion sort outperforms these more complex
algorithms. The size of list for which insertion sort has the advantage varies by
environment and implementation, but is typically between eight and twenty
elements.
quicksort is significantly faster in practice than other (nlogn) algorithms, because
its inner loop can be efficiently implemented on most architectures, and in most
real-world data, it is possible to make design choices which minimize the
probability of requiring quadratic time. Additionally, quicksort tends to make
excellent usage of the memory hierarchy, taking perfect advantage of virtual
memory and available caches.
Question No: 37 (Marks: 3)
How many leaf and non-leaf nodes are present in a complete binary tree if its depth
is 7?
Ans:
We know that the total number of nodes (leaf and non-leaf) of a complete binary tree
of depth d is equal to 2d+1 – 1.
It can be calculated as
27=14 nodes.
Question No: 31 (Marks: 3 )
In merge sort do we need to have extra memory, justify your answer in either case.
Ans:
Merge sort requires additional memory proportional to the size of the input for
scratch space, but, unlike heap sort, merge sort is stable, meaning that "equal"
elements are ordered the same once sorting is complete.
Merge sort works using the principle that if you have two sorted lists, you can
merge them together to form another sorted list. Consequently, sorting a large list
can be thought of as a problem of sorting two smaller lists and then merging those
two lists together.
Question No: 32 (Marks: 1 )
Where Inorder Predecessor of a non leaf node is is present in a Binary Search Tree?
Ans:
Inorder Predecessor of a non leaf node is present at rightmost child of left sub tree
Present in a Binary Search Tree.
Question No: 33 (Marks: 2 )
How we can search an element in Skip List.
Ans:
skip list can be used as the underlying storage for a sorted set data structure. But, skip
list can be directly used to implement some operations that are not efficient on a typical
sorted set:
Find the element in the set that is closest to some given value, in O(log N) time.
Find the k-th largest element in the set, in O(log N) time. Requires a
simple augmentation of the the skip list with partial counts. Count the number of elements in the set whose values fall into a given range, in
O(log N) time. Also requires a simple augmentation of the skip list.
Question No: 34 ( Marks: 2 )
What is the drawback of using arrays to store Binary Search Trees.
Ans:
We used the binary search algorithm to find data stored in an array. This method is very
effective as each iteration reduced the number of items to search by one-half. However
since data was stored in an array insertions and deletions were not efficient. Binary
search trees store data in nodes that are linked in a tree-like fashion. For randomly
inserted data search time is O(lg n). Worst-case behavior occurs when ordered data is
inserted. In this case the search time is O(n)
Question No: 34 ( Marks: 5 )
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
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 …
Solution:
parent: B using formula(i/2)
left child:H 2i=2*4=8=H
right child:I 2i+1=8+1=9=I
Question No: 32 ( Marks: 1 )
What is meant by Symmetry in equivalence relations?
Sol. Symmetry in equivalence relations mean for all elements x and y, x R y if and only
if y R x.
Question No: 39 ( Marks: 5 )
Here is an array of ten integers:
5 3 8 9 1 7 0 2 6 4
Sort the array by using selection sort algorithm and show content of array after
each step.
5 3 8 9 1 7 0 2 6 4
STEP
1
0 3 8 9 1 7 5 2 6 4
STEP
2
0 1 8 9 3 7 5 2 6 4
STEP3 0 1 2 9 3 7 5 8 6 4
STEP
4
0 1 2 3 9 7 5 8 6 4
STEP5 0 1 2 3 4 7 5 8 6 9
STEP6 0 1 2 3 4 5 7 8 6 9
STEP
7
0 1 2 3 4 5 6 8 7 9STEP8 0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
Other Uses of Binary Trees
Huffman Encoding
Data compression plays a significant role in computer networks.
To transmit data to its destination faster, it is necessary to either increase the data
rate of the transmission media or to simply send less data.
Improvements with regard to the transmission media has led to increase in the
rate.
The other options is to send less data by means of data compression.
Compression methods are used for text, images, voice and other types of data
(space probes).
Huffman code is method for the compression for standard text documents.
It makes use of a binary tree to develop codes of varying lengths for the letters
used in the original message.
Huffman code is also part of the JPEG image compression scheme.
The algorithm was introduced by David Huffman in 1952 as part of a course
assignment at MIT.
List all the letters used, including the "space" character, along with the frequency
with which they occur in the message.
Consider each of these (character,frequency) pairs to be nodes; they are actually
leaf nodes, as we will see.
Pick the two nodes with the lowest frequency, and if there is a tie, pick randomly
amongst those with equal frequencies.
Make a new node out of these two, and make the two nodes its children.
This new node is assigned the sum of the frequencies of its children.
Continue the process of combining the two nodes of lowest frequency until only
one node, the root, remains.
Properties of Binary Tree
Property: A binary tree with N internal nodes has 2N links: N-1 links to internal nodes
and N+1 links to external nodes.
• In every rooted tree, each node, except the root, has a unique parent.
• Every link connects a node to its parent, so there are N-1 links connecting
internal nodes.
• Similarly, each of the N+1 external nodes has one link to its parent.
• Thus N-1+N+1=2N links.
•
Threaded Binary Trees In many applications binary tree traversals are carried out repeatedly.
The overhead of stack operations during recursive calls can be costly.
The same would true if we use a non-recursive but stack-driven traversal
procedure
It would be useful to modify the tree data structure which represents the binary
tree so as to speed up, say, the inorder traversal process: make it "stack-free".
Oddly, most of the pointer fields in our representation of binary trees are NULL!
Since every node (except the root) is pointed to, there are only N-1 non-NULL
pointers out of a possible 2N (for an N node tree), so that N+1 pointers are
NULL.
Complete Binary Tree
A complete binary tree is a tree that is completely filled, with the possible
exception of the bottom level.
The bottom level is filled from left to right.
Different definition of complete binary tree than an earlier definition we had.
The earlier definition could be called a perfect binary tree.
Heap
A heap is a complete binary tree that conforms to the heap order.
The heap order property: in a (min) heap, for every node X, the key in the parent
is smaller than (or equal to) the key in X.
Or, the parent node has key smaller than or equal to both of its children nodes.
Analogously, we can define a max-heap, where the parent has a key larger than
the its two children.
Thus the largest key would be in the root.
Example Hash Functions
If the keys are integers then key%T is generally a good hash function, unless
the data has some undesirable features.
For example, if T = 10 and all keys end in zeros, then key%T = 0 for all keys.
In general, to avoid situations like this, T should be a prime number.
Collision
When two values hash to the same array location, this is called a collision
Collisions are normally treated as “first come, first served”—the first value that
hashes to the location gets it
We have to find something to do with the second and subsequent values that hash
to this same location.
Solution for Handling collisions
Solution #1: Search from there for an empty location• Can stop searching when we find the value or an empty location.
• Search must be wrap-around at the end.
•
Solution #2: Use a second hash function.and a third, and a fourth, and
a fifth,
Solution #3: Use the array location as the header of a linked list of values that
hash to this location
Linear Probing
The collision resolution strategy is called linear probing because it scans the
array sequentially (with wrap around) in search of an empty cell.
Clustering
One problem with linear probing technique is the tendency to form “clusters”.
A cluster is a group of items not containing any open slots
The bigger a cluster gets, the more likely it is that new values will hash into the
cluster, and make it ever bigger.
Clusters cause efficiency to degrade.
Question No: 31 ( Marks: 1 )
Describe the conditions for second case of deletion in AVL Trees.
Answer:
The node to be deleted has either left child (subtree) or right child (subtree). In this case
we bypass the node in such a way that we find the inorder successor of this node and then
link the parent of the node to be deleted to this successor node.Thus the node was deleted.
Question No: 32 ( Marks: 1 )
What is Table abstract data type.
Answer:
An abstract data structure is a mathematical model for a certain class of data structures
that have similar behavior; or for certain data types of one or more programming
languages that have similar semantics.
Question No: 33 ( Marks: 2 )
How we can generate a maze .Give an algorithm.
Answer:
A maze can be generated by starting with a predetermined arrangement of cells (most
commonly a rectangular grid but other arrangements are possible) with wall sites between
them. This predetermined arrangement can be considered as a connected graph with the
edges representing possible wall sites and the nodes representing cells.
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 in
the same set.
Question No: 34 ( Marks: 2 )
Represent the following Binary tree using array representation.
A B C D E
0 1 2 3 4 5 6 7
Question No: 35 ( Marks: 3 )
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
Question No: 36 ( Marks: 3 )
"For smaller lists, linear insertion sort performs well, but for larger lists, quick sort
is suitable to apply." Justify why?
Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-
lists.
Full example of quicksort on a random set of numbers. The boxed element is the pivot. It
is always chosen as the last element of the partition.The steps are:1.Pick an element, called a pivot, from the list.
2.Reorder the list so that all elements which are less than the pivot come before the pivot
and so that all elements greater than the pivot come after it (equal values can go either
way). After this partitioning, the pivot is in its final position. This is called the partition
operation.
3.Recursively sort the sub-list of lesser elements and the sub-list of greater elements
Question No: 37 ( Marks: 3 )
How many leaf and non-leaf nodes are present in a complete binary tree if its depth
is 7?
We know that the total number of nodes (leaf and non-leaf) of a complete binary tree
of depth d is equal to 2d+1 – 1.
It can be calculated as
27
=14 nodes
Question No: 38 ( Marks: 5 )
Remove the smallest element from the following array which represents a min-heap.
original min-heap 1 3 2 5 4 8 9 1
0
7
and show the resultant heap in the form of array as shown below,
after removal 2 3 8 5 4 9 1
0
7
Question No: 40 ( Marks: 10 )
a) 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;
}return 0; // not found
Example
int binarySearch(int sortedArray[], int first, int last, int key) {
// function:
// Searches sortedArray[first]..sortedArray[last] for key.
// returns: index of the matching element if it finds key,
// otherwise -(index where it could be inserted)-1.
// parameters:
// sortedArray in array of sorted (ascending) values.
// first, last in lower and upper subscript bounds
// key in value to search for.
// returns:
// index of key, or -insertion_position -1 if key is not
// in the array. This value can easily be
// transformed into the position to insert it.
while (first <= last) {
int mid = (first + last) / 2; // compute mid point.
if (key > sortedArray[mid])
first = mid + 1; // repeat search in top half.
else if (key < sortedArray[mid])
last = mid - 1; // repeat search in bottom half.
else
return mid; // found it. return position /////
}
return -(first + 1); // failed to find key
}
b) 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.
Question No: 41 ( Marks: 10 )
Show the result of following sequence of instructions
Union(1,2)
Union(3,4)
Union(3,5)
Union(1,7)
Union(3,6)
Union(8,9)
Union(1,8)
Union(3,10)
Union(3,11)
Union(3,12)
Union(3,13)
Union(14,15)
Union(16,17)
Union(14,16)
Union(1,3)
Union(1,14)
When the unions are performed by height
Note: You have to show only Final tree, No need to show all steps. Cs301
Subjective solved questions
Final term
By
MEHRAN ALI SHAH
Mehranali1991@gmail.com
8
1
6
9
1
7 2
1
3
1
2
3
4
5
1
1
1
0
6
1
7
1
4
1
5
0 comments: