datastructures aptitude-part2

[abeetha.m]

1. [/i]What are the methods available in storing
sequential files ?[/i]


Ø
Straight merging,


Ø
Natural merging,


Ø
Polyphase sort,


Ø
Distribution of Initial runs.


[/i]


2. [/i]How many different trees are possible with
10 nodes ?[/i]


1014


For example, consider a tree with 3
nodes(n=3), it will have the maximum combination of 5 different (ie, 2³ -
3 = 5) trees.

	[img]file:///C:%5CDOCUME%7E1%5CADMINI%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtml1%5C02%5Cclip_image001.gif[/img]

i
ii
iii iv v








In general:


If
there are n[/b] nodes, there exist 2ⁿ-n[/b] different trees. [/i]





3. [/i]List out few of the Application of tree
data-structure?[/i]


Ø
The manipulation of Arithmetic expression,


Ø
Symbol Table construction,


Ø
Syntax analysis.


[/i]


4. [/i]List out few of the applications that make
use of Multilinked Structures?[/i]


Ø
Sparse matrix,


Ø
Index generation.





5. [/i]In tree construction which is the suitable
efficient data structure?[/i]


(a)
Array (b) Linked list (c) Stack (d) Queue (e) none[/i]





(b)
Linked list





6. [/i]What is the type of the algorithm used in
solving the 8 Queens problem?[/i]


Backtracking





7. [/i]In an AVL tree, at what condition the
balancing is to be done?[/i]


If the ‘pivotal value’ (or the
‘Height factor’) is greater than 1 or less than –1.





8. [/i]What is the bucket size, when the
overlapping and collision occur at same time?[/i]


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.





9. [/i]Traverse the given tree using Inorder,
Preorder and Postorder traversals.[/i]

	[img]file:///C:%5CDOCUME%7E1%5CADMINI%7E1%5CLOCALS%7E1%5CTemp%5Cmsohtml1%5C02%5Cclip_image002.gif[/img]

Ø
Inorder : D
H B E A F C I G J


Ø
Preorder: A
B D H E C F G I J


Ø
Postorder: H
D E B F I J G C A





10. [/i]There are 8, 15, 13, 14 nodes were there in
4 different trees. Which of them could have formed a full binary tree?[/i]


15.


In general:


There
are 2ⁿ-1[/b] nodes in a full
binary tree.[/i]


By the method of elimination:[/i]


Full binary
trees contain odd[/i] 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[/i] binary
tree but not a full binary tree. So the correct answer is 15.[/i]


Note[/i][/b]:[/i]


Full and Complete binary trees are
different. All full binary trees are
complete binary trees but not vice versa. [/i]

[ari_laxmi]

answers:
1) distribution of intial runs
2)1004
3)syntax analysis
4)sparse matrix
5)stack

[sowmya571]

HELLO



5. [/i]In tree construction which is the suitable
efficient data structure?[/i]








(a)
Array (b) Linked list (c) Stack (d) Queue (e) none[/i]


(b)
Linked list