FINAL TERM
CS301-DATA STRUCTURE
Q#1Describe the concept of lvalue variable in your own words?
Ivalue àIt means it has some memory associated with it and some value can be assigned to it.
For example we have declared an array and its name is x. It is now an array name. It is not a variable.
Now the point is if some variable is written on the LHS for an assignment statement then this becomes Ivalue variable. A memory is given to it and it can be assigned some value.
Lets take an example.
Int a , b;
We can write b= 10 that would mean b is a memory location and 10 is its value, so put 2 in the memory b.
We can write a = 15 that would mean put 15 in the memory location a.
Even we can write a= b.
But we cannot write 10 = a; that is to put at number 10 for every the value of a . Because 10 is a number and it is a constant. A constant has to remain fixed, it is not to be changed. Otherwise its value will be keep changing and it is not meaningful so that is why it is not allowed.
‘x’ is a name of array and not an lvalue. So it cannot be used on the left hand side in an assignment statement.
………………………………………….
Q#2Here 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.
ANS:
Step1:Split the array into two part.
5 3 8 9 1 7 0 2 6 4
Step 2: Sort individual part.
1 3 4 5 8 0 2 4 6 7
Step 3: Merge the two parts together
1 3 4 5 8 0 2 4 6 7
……………………………………………
Q#3 What we can conclude from the running time analysis of disjoint sets?
Following points are concluded.
ANS:
union is clearly a constant time operation.
Goal: Modify union to ensure that heights stay small
This can be proportional to n in the worst case (but not always)
Running time of find(i) is proportional to the height of the tree containing
node i.
………………………………………………….
Q#4Identify the following trees as heap and complete binary tree
Heap follows rule the parent node has key smaller than or equal to both
of its children nodes.
We know that in a binary
search tree, the value of a node is greater than the values in its left subtree and less
than the values in its right subtree. The heap has a variation to it. In heap, the value of
a node is less than the values of its left and right children. ……………………………….
So all above trees are Complete Binary Trees.
…………………………………………………………………………………………….
Q#5
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.
In some applications, it is required to frequently read and write data. In these kinds of
applications hash table might not be a good solution, AVL tree might be a good option. But bear in mind that there are no hard and fast statistics to go for hash table and then to AVL tree. You have to be a good software engineer to choose relevant data structure.
Also, hashing is very slow for any operations which require the entries to be
Sorted
At times, you do other operations of insert, delete and find but additionally, you
require the data in sorted order or the minimum or maximum value. We have
discussed it many times that we insert data in the array of hash table without any sort
order and it is scattered through the array in such a fashion that there are holes in the
array. In these circumstances, the hash table is not useful. You might be remembering
from the animation we saw earlier on in this lecture that there was no real sequence of
filling of array. Some clusters were formed because of collision but there was no
order as such. So hashing is not really useful in these circumstances.
…………………………………
Q#6
Explain the two cases in which we apply double rotation in an AVL tree.
There are two cases where we apply double rotation.
Case 2 and case 3
Right-left double rotation to fix case 2
In the above tree, we have α node as k2, which has a left child as k1. Whereas X and Y
are its left and right children. The node k2 has a right child Z. Here the newly inserted
node works as the left or right child of node Y. Due to this insertion, one level is
increased in the tree. We have applied single rotation on the link of k1 and k2. The
right side tree in the figure is the post-rotation tree. The node k1 is now at the top
while k2 comes down and node Y changes its position. Now if you see the levels of
the node, these are seen same. Have a look on the level of the α node i.e. k1 which
reflects that the difference between the left and right side levels is still 2. So the single
rotation does not work here.
Right-left double rotation to fix case 3
In case, the node is inserted in left subtree of the right child, we encounter the same
situation as discussed above. But here, we will perform right rotation at first before
going for a left rotation. Let’s discuss this symmetric case and see how we can apply
double rotation here. First we perform the right rotation.
…………………………….
Q#6
Remove the smallest element from the following array which represents a min-heap.
original min-heap 1 3 2 5 4 8 9 10 7
and show the resultant heap in the form of array as shown below,
after removal
…………………………………………………..
Q#7
How we can generate a maze .Give an algorithm.
…………………………………
Q#8
In array representation of a Heap, if parent node is present an index i then at what indexes child nodes are present.
In array representation of a Heap, if parent node is present an index i then at what indexes child nodes are present.
…………………………………………………….
Q#9
Give one example of Hashing
……………………………….
Q#10
Insertion in a linked list can be done at
front only
back only
same where in middle
all of abv
……………………………………….
Q#11
Suppose A is an array containing numbers in increasing order, but some numbers occur more than once when using a binary search for a value, the binary search always finds ____________
the first occurance of value
the 2nd occurance of value
a&b
none
…………………………………………….
Q#12
Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
1.Element in the first half of the array are less than or equal to element in second half
2.None
3.Array element from heap
4.Element in the second half of the array are less than or equal to element in first half.
……………………………………………………….
Q#13
uppose we had a hash table whose hash function is “n % 12”, if the number 35 is already in the hash table, which of the following numbers would cause a collision?
144
145
143
148
………………………………………………………………
Q#14-MARKS=5
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.
………………………………………………….
Q#15-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 10 7
and show the resultant heap in the form of array as shown below,
| | | | | | | | | |
after removal.
………………………………………………..
Q#16
In a selection sort of n elements, how many times the swap function is called to complete the execution of the algorithm?
1
n-1
n log n
N^2
…………………………………………………….
Q#17
Consider a min heap, represented by the following array:
3,4,6,7,5,10
After inserting a node with value 1.Which of the following is the updated min heap?
3,4,6,7,5,10,1.
3,4,6,7,5,1,10
3,4,6,7,5,1,10
1,4,3,5,7,10,6
…………………………………………………………….
Q#18
Which of the following statement is true about dummy node of threaded binary tree?
The left pointer of dummy node points to the itself while the right pointer points to the root of tree.
The left pointer of dummy node points to the root node of the tree while the right pointer points itself i.e. to dummy node
The left pointer of dummy node points to the root node of the tree while the right pointer is always NULL.
The right pointer of dummy node points to the itself while the left pointer is always NULL.
……………………………………………………………………….
Q#19
Which of the following statement is correct?
A Threaded Binary Tree is a binary tree in which every node that does not have a left child has a THREAD (in actual sense, a link) to its INORDER successor.
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its PREOREDR successor.
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor.
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its POSTORDER successor.
……………………………………………………………………………….
Q#20
Huffman encoding uses _________ tree to develop codes of varying lengths for the letters used in the original message.
- link list
- stack
- que
- binary tree
……………………………………….
Q#21
Consider te following array
23 15 5 12 40 10 7
After the first pass of a particular algorithm, the array looks like
5 12 23 10 7 40
Name the algorithm used
- heap sort
- selection srt
- insertion
-Buble
……………………………………………
Q#22
If there are N elements in an array then the number of maximum steps needed to find an element using Binary Search is _______ .
- N
- N^2
- nlog2n
- log2N
………………………………………
Q#23
Which of the following is NOT an implementation of Table ADT?
- sorted sequantial
- link list
- skip lisT
- stAck
By : ADEEL ABBAS
www.allvupastpapers.blogspot.com
AdeelAbbasbk@gmail.com
No comments:
Post a Comment
PLEASE COMMENT ABOUT YOUR VISIT AND MY SITE
Note: Only a member of this blog may post a comment.