Placement Preparation -DataStructures

Placement Preparation -DataStructures

Download

Q1.What pointer type is used to implement the heterogeneous linked list in C?
The answer is the void pointer. The heterogeneous linked list contains different data types
in it's nodes and we need a link, pointer, to connect them. Since we can't use ordinary
pointers for this, we use the void pointer. Void pointer is a generic pointer type, and
capable of storing pointer to any type.
Q2.What is the minimum number of queues needed to implement the priority queue?
Two. One queue is used for the actual storing of data, and the other one is used for
storing the priorities.
Q3.Which data structure is used to perform recursion?
The answer is Stack. Stack has the LIFO (Last In First Out) property; it remembers it's
‘caller’. Therefore, it knows to whom it should return when the function has to return.
On the other hand, recursion makes use of the system stack for storing the return
addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when
such equivalent iterative procedures are written explicit, stack is to be used.
Q4.What are some of the applications for the tree data structure?
1- Manipulation of the arithmetic expressions.
2- Symbol table construction.
3- Syntax analysis.
Q5. Which data strucutres algorithm used in solving the eight Queens problem?
Backtracking
Q6. n an AVL tree, at what condition the balancing is to be done?
If the "pivotal value", or the "height factor", is greater than one or less than minus one.
Q7.What is the bucket size, when the overlapping and collision occur at the same
time?
The answer is 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.
Q8.There are 8, 15, 13, and 14 nodes in four different trees. Which one of them can
form a full binary tree?
The answer is the tree with 15 nodes. In general, there are 2^n-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. Moreover, with 13 nodes you can form a complete binary tree but not a full
binary tree. Thus, the correct answer is 15.
Q9 . Consider the following list of integers:
5, 54, 125, 105, 25, 104, 20, 100, 50, 159
(a) Slightly modify the integers above so that it is appropriate to perform
a radix sort on the above list.
Solution: Radix sort only applies to integers that have the same
number of digits (or strings that have the same number of characters).
For these integers, we fill in initial 0s so that each integer has 3 digits:
005, 054, 125, 105, 025, 104, 020, 100, 050, 159
Q10 .f(n) is of the order of g(n) if there exist positive integers “a” and “b” such that
A) f(n) <= a * g(n) for all n >= b
B) f(n) <= a * g(n) for all n <= b
C) g(n) <= a * f(n) for all n >= b
D) None of the above
Q11. Adjacency matrix for a digraph is
A) unit matrix
B) symmetric
C) asymmetric matrix
D) none of the above
Q12 .Which of the following data structure may give overflow error, even though the
current number
of elements in it, is less than its size
A) simple queue
B) circular queue
C) stack
D) none of the above
Q13 .Which of the following types of expressions does not require precedence rules
for evaluation?
A) Fully parenthesized infix expression
B) Partially parenthesized infix expression
C) Both A) and B)
D) Prefix expression
Q14 If j=2, m=1, x=3, y=4. What is the value of the expression j++ = = m = = y * x
A) 0
B) 1

Download