- What are the methods available in storing sequential files ?
Ø
Straight merging,
Ø
Natural merging,
Ø
Polyphase sort,
Ø
Distribution of Initial runs.
- List out few of the Application of tree data-structure?
Ø
The manipulation of Arithmetic expression,
Ø
Symbol Table construction,
Ø
Syntax analysis.
- List out few of the applications that make use of Multilinked Structures?
Ø
Sparse matrix,
Ø
Index generation.
- In tree construction which is the suitable efficient data structure?
(a)
Array (b) Linked list (c) Stack (d) Queue (e) none
(b)
Linked list
- What is the type of the algorithm used in
solving the 8
Backtracking
- In an AVL tree, at what condition the balancing is to be done?
If the ‘pivotal value’ (or the
‘Height factor’) is greater than 1 or less than –1.
- What is the bucket size, when the overlapping and collision occur at same time?
One.
If there is only one entry possible in the bucket, when the collision occurs,
there is no way to accommodate the colliding value. This results in the
overlapping of values.
- There are 8, 15, 13, 14 nodes were there in 4 different trees. Which of them could have formed a full binary tree?
15.
In general:
There
are 2n-1 nodes in a full
binary tree.
By the method of elimination:
Full binary
trees contain odd number of nodes. So
there cannot be full binary trees with 8 or 14 nodes, so rejected. With 13
nodes you can form a complete binary
tree but not a full binary tree. So the correct answer is 15.
Note:
Full and Complete binary trees are
different. All full binary trees are
complete binary trees but not vice versa.
- Sort the given values using Quick Sort?
|
65
|
70
|
75
|
80
|
85
|
60
|
55
|
50
|
45
|
Sorting takes place from the pivot
value, which is the first value of the given elements, this is marked bold. The
values at the left pointer and right pointer are indicated using L
and R respectively.
|
65
|
70L
|
75
|
80
|
85
|
60
|
55
|
50
|
45R
|
Since pivot is
not yet changed the same process is continued after interchanging the values at
L and R positions
|
65
|
45
|
75
L
|
80
|
85
|
60
|
55
|
50
R
|
70
|
|
65
|
45
|
50
|
80
L
|
85
|
60
|
55
R
|
75
|
70
|
|
65
|
45
|
50
|
55
|
85
L
|
60
R
|
80
|
75
|
70
|
|
65
|
45
|
50
|
55
|
60
R
|
85
L
|
80
|
75
|
70
|
When the L and
R pointers cross each other the pivot value is interchanged with the value at
right pointer. If the pivot is changed it means that the pivot has occupied its
original position in the sorted order (shown in bold italics) and hence two
different arrays are formed, one from start of the original array to the pivot
position-1 and the other from pivot position+1 to end.
|
60 L
|
45
|
50
|
55
R
|
65
|
85 L
|
80
|
75
|
70
R
|
|
55 L
|
45
|
50
R
|
60
|
65
|
70 R
|
80
L
|
75
|
85
|
|
50 L
|
45
R
|
55
|
60
|
65
|
70
|
80
L
|
75
R
|
85
|
In the next
pass we get the sorted form of the array.
|
45
|
50
|
55
|
60
|
65
|
70
|
75
|
80
|
85
|
No comments:
Post a Comment