|
FINALTERM EXAMINATION
FALL 2006
CS301 - DATA STRUCTURES (Session - 1 )
Marks: 75
Time: 120min
StudentID/LoginID: ______________________________
Student Name: ______________________________
Center Name/Code: ______________________________
Exam Date: Saturday, February 03, 2007
1. Attempt all questions.
2. Do not ask any questions about the contents of this examination from anyone.
a. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.
b. If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.
c. Write all steps, missing steps may lead to deduction of marks.
d. All coding questions should be answered using the C ++ syntax.
You are allowed to use the Dev-C++ compiler to write and test your code. If you do so please remember to copy and paste your code into the examination solution area. (Do NOT share your code)
**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.
For Teacher's use only
Question 1 2 3 4 5 6 7 8 9 10 Total
Marks
Question 11
Marks
Question No: 1 ( Marks: 10 )
Draw AVL Tree by following digits 15, 4, 13, 6, 17, 2, 11 and also perform necessary rotation, while showing all the intermediate trees being created in the process. In each stage, the AVL transformation should be conducted at a discrepancy that is farthest from the root.
Question No: 2 ( Marks: 10 )
Some operations are given. Show the output of the given operations step by step in form of array.
Enqueue(13);
Enqueue(35);
Enqueue(11);
Enqueue(39);
Enqueue(9);
N = RemoveMin();
Enqueue( 51);
N = RemoveMin();
Enqueue(15);
Question No: 3 ( Marks: 15 )
The frequency table for letters A, B, C, D and E is given
Frequency Table
Character Frequency Huffman Code
A 8
B 12
C 49
D 20
E 11
A) Create a Huffman tree to determine the binary codes for each character. (10)
B) Fill the codes into the table above. (2.5)
C) Encode the following sequence ABCDE. (2.5)
Question No: 4 ( Marks: 10 )
Following array is given which represents a min-heap. Insert 4 in the following array and convert it into a min-heap again. Show process steps by drawing heap trees.
33 55 99 66 88 120 110 122 180
Question No: 5 ( Marks: 10 )
Write down the C++ code to implement Bubble Sort Algorithm.
Question No: 6 ( Marks: 10 )
Create a hash table using hash table of size 10 i.e. (0-9). Insert the following values in the hash table
79, 76, 75, 56, 53, 47, 48, 63, 90 and 59.
If there is any collision then insert a node in front of collision node to put the value in table e.g.
You are required to give answer in table form as shown above.
Question No: 7 ( Marks: 2 ) - Please choose one
Which one is not Divide and Conquer algorithm?
►
merge sort
►
quick sort
►
heap sort
►
none of the above
Question No: 8 ( Marks: 2 ) - Please choose one
Hash tables are very good if there are many insertions and deletions.
►
True
►
False
Question No: 9 ( Marks: 2 ) - Please choose one
A table ts always a two dimensional array of same data type
►
True
►
False
Question No: 10 ( Marks: 2 ) - Please choose one
When there is a collision, we try to find some other place in our array. This approach is called
►
open addressing
►
closed hashing
►
open addressing & closed hashing
►
none of the above
Question No: 11 ( Marks: 2 ) - Please choose one
___________ is/are called nlog2n algorithm(s).
►
merge sort
►
quick sort
►
heap sort
►
all of the above
http://ping.fm/IWWH2
FALL 2006
CS301 - DATA STRUCTURES (Session - 1 )
Marks: 75
Time: 120min
StudentID/LoginID: ______________________________
Student Name: ______________________________
Center Name/Code: ______________________________
Exam Date: Saturday, February 03, 2007
1. Attempt all questions.
2. Do not ask any questions about the contents of this examination from anyone.
a. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.
b. If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.
c. Write all steps, missing steps may lead to deduction of marks.
d. All coding questions should be answered using the C ++ syntax.
You are allowed to use the Dev-C++ compiler to write and test your code. If you do so please remember to copy and paste your code into the examination solution area. (Do NOT share your code)
**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.
For Teacher's use only
Question 1 2 3 4 5 6 7 8 9 10 Total
Marks
Question 11
Marks
Question No: 1 ( Marks: 10 )
Draw AVL Tree by following digits 15, 4, 13, 6, 17, 2, 11 and also perform necessary rotation, while showing all the intermediate trees being created in the process. In each stage, the AVL transformation should be conducted at a discrepancy that is farthest from the root.
Question No: 2 ( Marks: 10 )
Some operations are given. Show the output of the given operations step by step in form of array.
Enqueue(13);
Enqueue(35);
Enqueue(11);
Enqueue(39);
Enqueue(9);
N = RemoveMin();
Enqueue( 51);
N = RemoveMin();
Enqueue(15);
Question No: 3 ( Marks: 15 )
The frequency table for letters A, B, C, D and E is given
Frequency Table
Character Frequency Huffman Code
A 8
B 12
C 49
D 20
E 11
A) Create a Huffman tree to determine the binary codes for each character. (10)
B) Fill the codes into the table above. (2.5)
C) Encode the following sequence ABCDE. (2.5)
Question No: 4 ( Marks: 10 )
Following array is given which represents a min-heap. Insert 4 in the following array and convert it into a min-heap again. Show process steps by drawing heap trees.
33 55 99 66 88 120 110 122 180
Question No: 5 ( Marks: 10 )
Write down the C++ code to implement Bubble Sort Algorithm.
Question No: 6 ( Marks: 10 )
Create a hash table using hash table of size 10 i.e. (0-9). Insert the following values in the hash table
79, 76, 75, 56, 53, 47, 48, 63, 90 and 59.
If there is any collision then insert a node in front of collision node to put the value in table e.g.
You are required to give answer in table form as shown above.
Question No: 7 ( Marks: 2 ) - Please choose one
Which one is not Divide and Conquer algorithm?
►
merge sort
►
quick sort
►
heap sort
►
none of the above
Question No: 8 ( Marks: 2 ) - Please choose one
Hash tables are very good if there are many insertions and deletions.
►
True
►
False
Question No: 9 ( Marks: 2 ) - Please choose one
A table ts always a two dimensional array of same data type
►
True
►
False
Question No: 10 ( Marks: 2 ) - Please choose one
When there is a collision, we try to find some other place in our array. This approach is called
►
open addressing
►
closed hashing
►
open addressing & closed hashing
►
none of the above
Question No: 11 ( Marks: 2 ) - Please choose one
___________ is/are called nlog2n algorithm(s).
►
merge sort
►
quick sort
►
heap sort
►
all of the above
http://ping.fm/IWWH2