FINAL TERM EXAMINATION
Fall 2009
CS301- Data Structures
Time: 120 min
Marks: 75
Question
No: 1 ( Marks: 1 ) - Please choose
one
The
arguments passed to a function should match in number, type and order with the
parameters in the function definition.
► True
► False
Question
No: 2 ( Marks: 1 ) - Please choose
one
If
numbers 5, 222, 4, 48 are inserted in a queue, which one will be removed
first?
► 48
► 4
► 222
► 5
Question
No: 3 ( Marks: 1 ) - Please choose one
Suppose currentNode refers to a
node in a linked list (using the Node class with member variables called data
and nextNode). What statement changes currentNode so that it refers to the next
node?
► currentNode ++;
► currentNode = nextNode;
► currentNode += nextNode;
► currentNode = currentNode->nextNode;
Question
No: 4 ( Marks: 1 ) - Please choose
one
A
Compound Data Structure is the data structure which can have multiple
data items of same type or of different types. Which of the following can be
considered compound data structure?
► Arrays
► LinkLists
► Binary Search Trees
► All of the given options
Question
No: 5 ( Marks: 1 ) - Please choose
one
Here is a small function definition:
void
f(int i, int &k)
{
i = 1;
k = 2;
}
Suppose
that a main program has two integer variables x and y, which are given the
value 0. Then the main program calls f(x,y); What are the values of x and y
after the function f finishes?
► Both x and y are still 0.
► x is now 1, but y is still 0.
► x is still 0, but y is now 2.
► x is now 1, and y is now 2.
Question
No: 6 ( Marks: 1 ) - Please choose
one
The
difference between a binary tree and a binary search tree is that ,
► a binary search tree has two
children per node whereas a binary tree can have none, one, or two children per
node
► in binary search tree nodes are
inserted based on the values they contain
► in binary tree nodes are inserted
based on the values they contain
►
none of these
Question
No: 7 ( Marks: 1 ) - Please choose
one
Compiler
uses which one of the following to evaluate a mathematical equation,
► Binary Tree
► Binary Search Tree
► Parse Tree
► AVL Tree
Question
No: 8 ( Marks: 1 ) - Please choose
one
If there
are 56 internal nodes in a binary tree then how many external nodes this binary
tree will have?
► 54
► 55
► 56
► 57
Question
No: 9 ( Marks: 1 ) - Please choose
one
if
there are 23 external nodes in a binary tree then what will be the no. of
internal nodes in this binary tree?
► 23
► 24
► 21
► 22
Question
No: 10 ( Marks: 1 ) - Please choose
one
Which
of the following method is helpful in creating the heap at once?
► insert
► add
► update
► preculateDown (lecture #31 page 1)
Question
No: 11 ( Marks: 1 ) - Please choose
one
The
definition of Transitivity property is
► For all element x member of S, x R x
► For all elements x and y, x R y if and only if y R
x
► For all elements x, y and z, if x R
y and y R z then x R z
► For all elements w, x, y and z, if x R y and w R z
then x R z
Question
No: 12 ( Marks: 1 ) - Please choose
one
A binary tree of N nodes has _______.
► Log10 N levels
► Log2 N levels
► N / 2 levels
► N x 2 levels
Question
No: 13 ( Marks: 1 ) - Please choose
one
If there are N elements in an
array then the number of maximum steps needed to find an element using Binary
Search is _______ .
► N
► N2
► Nlog2N
► log2N
Question
No: 14 ( Marks: 1 ) - Please choose
one
Consider te following array
23
15 5 12
40 10 7
After
the first pass of a particular algorithm, the array looks like
15
5 12
23 10 7 40
Name
the algorithm used
► Heap sort
► Selection
sort
► Insertion
sort
► Bubble sort
Question No: 15 ( Marks: 1 ) - Please choose one
Question No: 15 ( Marks: 1 ) - Please choose one
If
both pointers of the node in a binary tree are NULL then it will be a/an
_______ .
► Inner node
► Leaf node
► Root node
► None of the given options
Question
No: 16 ( Marks: 1 ) - Please choose
one
By using
__________we avoid the recursive method of traversing a Tree, which makes use
of stacks and consumes a lot of memory and time.
► Binary tree only
► Threaded binary tree
► Heap data structure
► Huffman encoding
Question No: 17 ( Marks: 1 ) - Please choose one
Question No: 17 ( Marks: 1 ) - Please choose one
A
complete binary tree of height 3 has between ________ nodes.
► 8 to 14
► 8 to 15
► 8 to 16
► 8 to 17
Question
No: 18 ( Marks: 1 ) - Please choose
one
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,1,5,7,10,6
► 1,4,3,5,7,10,6 close to correct but correct ans is
1,4,3,7,5,10,6
Question
No: 19 ( Marks: 1 ) - Please choose one
Consider a min heap, represented
by the following array:
10,30,20,70,40,50,80,60
After
inserting a node with value 31.Which of the following is the updated min heap?
► 10,30,20,31,40,50,80,60,70
► 10,30,20,70,40,50,80,60,31
► 10,31,20,30,40,50,80,60,31
► 31,10,30,20,70,40,50,80,60
Question
No: 20 ( Marks: 1 ) - Please choose
one
Which one of the following
algorithms is most widely used due to its good average time,
► Bubble Sort
► Insertion Sort
► Quick Sort
► Merge Sort
Question
No: 21 ( Marks: 1 ) - Please choose
one
Which
of the following statement is correct about find(x) operation:
► A find(x) on element x is
performed by returning exactly the same node that is found.
►A
find(x) on element x is performed by returning the root of the tree containing
x.
► A find(x) on element x is performed by
returning the whole tree itself containing x.
► A find(x) on element x is
performed by returning TRUE.
Question
No: 22 ( Marks: 1 ) - Please choose
one
Which
of the following statement is NOT correct about find operation:
►It is not a requirement that a
find operation returns any specific name, just that finds on two elements
return the same answer if and only if they are in the same set.
► One idea might be to use a tree
to represent each set, since each element in a tree has the same root, thus the
root can be used to name the set.
► Initially each set contains one element.
► Initially each set contains one element and
it does not make sense to make a tree of one node only.
Question
No: 23 ( Marks: 1 ) - Please choose
one
The following are statements related to queues.
(i)
The last item to be added to a queue is the first item
to be removed False
statement
(ii) A
queue is a structure in which both ends are not used False statement
(iii) The
last element hasn’t to wait until all elements preceding it on the queue are
removed False
statement
(iv) A
queue is said to be a last-in-first-out list or LIFO data structure. False statement
Which of
the above is/are related to normal queues?
► (iii) and (ii) only
► (i), (ii) and (iv) only
► (ii) and (iv) only
► None of the given options
Question
No: 24 ( Marks: 1 ) - Please choose
one
The
maximum number of external nodes (leaves) for a binary tree of height H is _______
► 2H
► 2H +1
► 2H -1
► 2H +2
Question
No: 25 ( Marks: 1 ) - Please choose
one
In
complete binary tree the bottom level is filled from ________
► Left to right
► Right to left
► Not filled at all
► None of the given options
Question
No: 26 ( Marks: 1 ) - Please choose
one
We
are given N items to build a heap , this
can be done with _____ successive inserts.
► N-1
► N
► N+1
► N^2
Question
No: 27 ( Marks: 1 ) - Please choose
one
Suppose
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
Question
No: 28 ( Marks: 1 ) - Please choose
one
Here
is an array of ten integers:
5
3 8 9
1 7 0
2 6 4
The array after the FIRST iteration of the large
loop in a selection sort (sorting from smallest to largest).
► 0
3 8 9
1 7 5
2 6 4
► 2 6 4
0 3 8
9 1 7
5
► 2 6 4
9 1 7
0 3 8
5
► 0 3
8 2 6
4 9 1
7 5
Question
No: 29 ( Marks: 1 ) - Please choose
one
What
requirement is placed on an array, so that binary search may be used to
locate an entry? ► The array
elements must form a heap.
► The array must have at least 2
entries.
► The array must be sorted.
► The array’s size must be a power of two.
Question
No: 30 ( Marks: 1 ) - Please choose
one
In
case of deleting a node from AVL tree, rotation could be prolong to the root
node.
► Yes
► No
Question
No: 31 ( Marks: 1 )
In merge sort do we need to have
extra memory, justify your answer in either case.
Yes we need extra memory in
merge sort.
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
|
10000
|
SP
|
1111
|
o
|
001
|
b
|
0100
|
i
|
0101
|
r
|
110
|
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.
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
|
9
|
STEP8
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
|
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.
No comments:
Post a Comment