CS301 Data Structure
Final Term Examination – Spring 2006
Time Allowed: 150 Minutes
Question No. 1 Marks : 2
Which of the following are primitive types?
A. Byte
B. String
C. Integer
D. Float
E. Choice (C) & (D)
Question No. 2 Marks : 15
Given the string "go go gophers". How Huffman coding is used to compress this
String?
Frequency Table
character frequency Huffman Codes
g ----------- -----------
o ----------- -----------
p ----------- -----------
h ----------- -----------
e ----------- -----------
r ----------- -----------
s ----------- -----------
Space ----------- -----------
A) Calculate Frequency of each character from given string (“go go gopher”) and fill
into the table
given above.
B) Create a Huffman tree from frequencies calculated in part ‘A’ of this question.
C) Fill the Huffman codes into the table above.
Question No. 3 Marks : 2
WWW.VUPages.Com
Connecting VU Students
Each entry in a linked list is called a _______
􀂐 None of above
Question No. 4 Marks : 5
􀂐 Link
􀂐 Node
􀂐 Data Structure
15
11
9
6 16
21
31
Write down INORDER, PREORDER, POSTORDER Traversal of above described tree.
Question No. 5 Marks : 10
array ‘BS’:
Show step by step sorting. You have to
rite only two passes that is pass 1 and pass 2.
u. There are 6 passes involved in sorting array ‘BS’. You have to
When inner loop complete its execution at once that is called one pass.
Question No. 6 Marks : 2
v a binary tree can only be done by a recursive algorithm.
􀂐 False
Question No. 7 Marks : 5
Suppose the following digits are stored in an
32,51,27,85,66,23,13,57
We apply Bubble sort algorithm to array ‘BS’.
w
Hint: In step by step sorting you have to show passes for sorting, according to algorithm
technique provided to yo
show only two passes.
Tra ersing
􀂐 True
Determine what the following recursive “mystery” function computes when given a
pointer to the root
nt key; struct bt_s *left, *right; } bt_t;
t_t *T)
;
= MFunc(T->right);
turn (N1 > N2 ? N1 : N2) + 1;
}
Question No. 8 Marks : 5
ing implementation of code find?
r find (Iter current, Iter end, T elt)
; ++current)
return current;
}
Q Marks : 10
The following array of current size re t h c
1 2 3 4 5 6 7 8 9 10 11 12
node of a binary tree.
typedef struct bt_s { i
int MFunc (b
{
int N1, N2;
if (T == NULL) return -1
N1 = MFunc(T->left);
N2
re
What is wrong with the follow
template < class Iter, class T >
Ite
{
for(; current != end
if(*current == T)
uestion No. 9
11 rep sen s a eap stru ture.
97 76 61 42 54 59 31 23 17 44 49
A. Draw a tree diagram of the heap which is shown above.
Qu Marks : 2
B. Insert a new value 86 into the heap. Draw the new heap tree when insertion is done.
estion No. 10
Stacks and queues are
􀂐 primitive data structures
􀂐 non-primitive data structures
􀂐 non-linear data structures....
􀂐 data types
Q s : 2
he constructor of the Hashtable class initializes data members and creates the
.
􀂐 True
raw an AVL Tree by following digits 1, 5, 6, 4, 18, 24 and also perform necessary rotation,
hile showing all the intermediate trees being created in the process http://ping.fm/bHTKu