FINALTERM EXAMINATION
Fall 2009
CS301- Data Structures
Question No: 31 ( Marks: 1 )
Describe the conditions for second case of deletion in AVL Trees.Question No: 32 ( Marks: 1 )
What is Table abstract data type.Question No: 33 ( Marks: 2 )
How we can generate a maze .Give an algorithm.Question No: 34 ( Marks: 2 )
Represent the following Binary tree using array representation.
Question No: 35 ( Marks: 3 )
What is an Equivalent relation? Give any two examples.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?Question No: 37 ( Marks: 3 )
How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ?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 | 10 | 7 |
and show the resultant heap in the form of array as shown below,
Question No: 39 ( Marks: 5 )
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.
Question No: 40 ( Marks: 10 )
a) Write C++ algorithm for Binary Searchint 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
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 When the unions are performed by height
Note: You have to show only Final tree, No need to show all steps.
FINALTERM EXAMINATION
Fall 2009
CS301- Data Structures
Question No: 31 ( Marks: 1 )
If a Binary Tree has N internal nodes what are the no. of external nodes in it.
Sol. The No. of external nodes will be N+1
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: 33 ( Marks: 2 )
How heap sort works to sort a set of data.
Question No: 34 ( Marks: 2 )
How we can apply Find operation on elements combined through Union operation.
Question No: 35 ( Marks: 3 )
How we can use concept of equivalence relations to generate a Maze.
Question No: 36 ( Marks: 3 )
Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown here:
2 4 5 7 8 1 3 6
Which statement is correct? (Note: Our selectionsort picks largest items first.)
A. The algorithm might be either selectionsort or insertionsort.
B. The algorithm might be selectionsort, but it is not insertionsort.
C. The algorithm is not selectionsort, but it might be insertionsort. (Correct)
D. The algorithm is neither selectionsort nor insertionsort.
E. None of these.
Question No: 37 ( Marks: 3 )
How many leaf and non-leaf nodes are present in a complete binary tree if its depth is 7 ?
Question No: 38 ( Marks: 5 )
If we insert a new element into an AVL tree of height 4, is one rotation sufficient to re-establish balance? Justify your answer.
Question No: 39 ( Marks: 5 )
Write down the C++ code from Selection Sort Algorithm.
Question No: 40 ( Marks: 10 )
Consider the following data:
the cat in the hat
a) Build frequency table for the above data.
b) Create a Huffman tree to determine the binary codes for each character.
c) What will be the code of each letter?
Question No: 41 ( Marks: 10 )
Suppose we have build a Skip list .Now we want to add and remove items from the list .Give Algorithms for insert (item) and delete (item) methods of the Skip List.
FINALTERM EXAMINATION
Fall 2009
CS301- Data Structures
Question No: 31 ( Marks: 1 )
In merge sort do we need to have extra memory, justify your answer in either case.
Question No: 32 ( Marks: 1 )
Where is Inorder Predecessor of a non leaf node is present in a Binary Search Tree?
Question No: 33 ( Marks: 2 )
How we can search an element in Skip List.
Question No: 34 ( Marks: 2 )
What is the drawback of using arrays to store Binary Search Trees.
Question No: 35 ( Marks: 3 )
Calculate the codes of the following characters in table below using the hoffman encoding tree,
| character | code |
| NL | |
| SP | |
| o | |
| b | |
| i | |
| r | |
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?
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: 38 ( Marks: 5 )
Give two different reasons to explain why the following binary tree is not a heap:
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.
Question No: 40 ( Marks: 10 )
A long sequence of vowels needs to be transmitted efficiently so a programmer decides to use Huffman encoding to encode the vowels. A distribution count study of typical data yielded the following frequency table.
Frequency Table
character frequency Huffman code
A 33978 _ _ _ _ _ _ _
E 20676 _ _ _ _ _ _ _
I 15814 _ _ _ _ _ _ _
O 21552 _ _ _ _ _ _ _
U 10324 _ _ _ _ _ _ _
Y 4975 _ _ _ _ _ _ _
A) Create a Huffman tree to determine the binary codes for each character.
B) Fill the codes into the table above.
C) Encode the following sequence EIYOUA
Question No: 41 ( Marks: 10 )
Consider the following tree.
a) Show that either it is a heap or not.
b) If it is a heap then what type of heap is it?
c) Add 40 in the heap and convert it in max heap.
FINALTERM EXAMINATION
Fall 2009
CS301- Data Structures (Session - 4)
Question No: 31 ( Marks: 1 )
Which is the initial step while using Huffman encoding when sending text message from one point to the other? Question No: 32 ( Marks: 1 )
What is maximum level difference between two leaf nodes in a Heap?Justify your answer as well.Question No: 33 ( Marks: 2 )
How we can apply Find operation on elements combined through Union operation.Question No: 34 ( Marks: 2 )
What is the drawback of using arrays to store Binary Search Trees.Question No: 35 ( Marks: 3 )
Give any three properties of complete binary tree. Question No: 36 ( Marks: 3 )
When Hashing is NOT suitable?Question No: 37 ( Marks: 3 )
Give any three important facts about building a heap. Question No: 38 ( Marks: 5 )
If we insert a new element into an AVL tree of height 4, is one rotation sufficient to re-establish balance? Justify your answer. Question No: 39 ( 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.
Question No: 40 ( Marks: 10 )
1. Draw a new heap that is created by inserting 82 into the following heap:
Draw a new heap that is created by inserting 82 into the following heap: 
2. Is the following a heap tree? Explain your answer briefly.
Question No: 41 ( Marks: 10 )
Delete 3 in the following array which represents a min-heap. Show process steps by drawing heap tree. |
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.