Technical Round MaterialsData StructureFree Download
Data Structure
1.
What is data structure?
A data structure is a way of organizing data that considers not only
the items stored, but also their relationship to each other. Advance
knowledge about the relationship between data items allows designing of
efficient algorithms for the manipulation of data.
2.
List out the areas in which data structures are applied
extensively?
Ř Compiler Design,
Ř Operating System,
Ř Database Management System,
Ř Statistical analysis package,
Ř Numerical Analysis,
Ř Graphics,
Ř Artificial Intelligence,
Ř Simulation
3.
What are the major data structures used in the following areas :
RDBMS, Network data model & Hierarchical data model.
Ř RDBMS – Array (i.e. Array of structures)
Ř Network data model – Graph
Ř Hierarchical data model – Trees
4.
If you are using C language to implement the heterogeneous linked
list, what pointer type will you use?
The heterogeneous linked list contains different data types in its nodes
and we need a link, pointer to connect them. It is not possible to use
ordinary pointers for this. So we go for void pointer. Void pointer is
capable of storing pointer to any type as it is a generic pointer type.
5.
Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for
storing priorities.
6.
What is the data structures used to perform recursion?
Stack. Because of its LIFO (Last In First Out) property it remembers
its ‘caller’ so knows whom to return when the function has to return.
Recursion makes use of system stack for storing the return addresses of
the function calls.
Every recursive function has its equivalent iterative
(nonrecursive) function.
Even when such equivalent iterative procedures are written, explicit
stack is to be used.
7.
What are the notations used in Evaluation of Arithmetic Expressions
using prefix and postfix forms?
Polish and Reverse Polish notations.
8.
Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to
equivalent Prefix and Postfix notations.
Prefix Notation:
^  * +ABC  DE + FG
Postfix Notation:
AB + C * DE   FG + ^
9.
Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion
(d) Deletion.
Using insertion we can perform insertion sort, using selection we can
perform selection sort, using exchange we can perform the bubble sort
(and other similar sorting methods). But no sorting method can be done
just using deletion.
10.
A binary tree with 20 nodes has null branches?
21
Let us take a tree with 5 nodes (n=5)
It will have only 6 (ie,5+1) null branches. In general,
A binary tree with n nodes has exactly n+1 null nodes.
11.
What are the methods available in storing sequential files ?
Ř Straight merging,
Ř Natural merging,
Ř Polyphase sort,
Ř Distribution of Initial runs.
12.
How many different trees are possible with 10 nodes ?
1014
For example, consider a tree with 3 nodes(n=3), it will have the
maximum combination of 5 different (ie, 2^{3 } 3 = 5) trees.
i ii iii iv v
In general:
If there are n nodes, there exist 2^{n}n different trees.
13.
List out few of the Application of tree datastructure?
Ř The manipulation of Arithmetic expression,
Ř Symbol Table construction,
Ř Syntax analysis.
14.
List out few of the applications that make use of Multilinked
Structures?
Ř Sparse matrix,
Ř Index generation.
15.
In tree construction which is the suitable efficient data
structure?
(a) Array (b) Linked list (c) Stack (d) Queue (e) none
(b) Linked list
16.
What is the type of the algorithm used in solving the 8 Queens
problem?
Backtracking
17.
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.
18.
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.
19.
Traverse the given tree using Inorder, Preorder and Postorder
traversals.
Ř 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
20.
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 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, 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.
21.
In the given binary tree, using array you can store the node 4 at
which location?
At location 6
Root

LC1

RC1

LC2

RC2

LC3

RC3

LC4

RC4

where LCn means Left Child of node n and RCn means Right Child of node
n
22.
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

70^{L}

75

80

85

60

55

50

45^{R}

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 position1
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

23.
For the given graph, draw the DFS and BFS?
Ř BFS: A X G H P E M Y J
Ř DFS: A X H P E Y M J G
24.
Classify the Hashing Functions based on the various methods by
which the key value is found.
Ř Direct method,
Ř Subtraction method,
Ř ModuloDivision method,
Ř DigitExtraction method,
Ř MidSquare method,
Ř Folding method,
Ř Pseudorandom method.
25.
What are the types of Collision Resolution Techniques and the
methods used in each of the type?
Ř Open addressing (closed hashing),
The methods used include:
Overflow block,
Ř Closed addressing (open hashing)
The methods used include:
Linked list,
Binary tree…
26.
In RDBMS, what is the efficient data structure used in the internal
storage representation?
B+ tree. Because in B+ tree, all the data is stored only in leaf nodes,
that makes searching easier. This corresponds to the records that shall
be stored in leaf nodes.
27.
Draw the Btree of order 3 created by inserting the following data
arriving in sequence – 92 24 6 7 11 8 22 4 5 16 19 20 78
28.
Of the following tree structure, which is, efficient considering
space and time complexities?
(a)
Incomplete Binary Tree
(b)
Complete Binary Tree
(c)
Full Binary Tree
(b) Complete Binary Tree.
By the method of elimination:
Full binary tree loses its nature when operations of insertions and
deletions are done. For incomplete binary trees, extra storage is
required and overhead of NULL node checking takes place. So complete
binary tree is the better one since the property of complete binary
tree is maintained even after operations like additions and deletions
are done on it.
29.
What is a spanning Tree?
A spanning tree is a tree associated with a network. All the nodes of
the graph appear on the tree once. A minimum spanning tree is a
spanning tree organized so that the total edge weight between nodes is
minimized.
30.
Does the minimum spanning tree of a graph give the shortest
distance between any 2 specified nodes?
No.
Minimal spanning tree assures that the total weight of the tree is kept
at its minimum. But it doesn’t mean that the distance between
any two nodes involved in the minimumspanning tree is minimum.
31.
Convert the given graph with weighted edges to minimal spanning
tree.
the equivalent minimal spanning tree is:
32.
Which is the simplest file structure?
(a)
Sequential
(b)
Indexed
(c)
Random
(a) Sequential
33.
Whether Linked List is linear or Nonlinear data structure?
According to Access strategies Linked list is a linear one.
According to Storage Linked List is a Nonlinear one.
34.
Draw a binary Tree for the expression :
A * B  (C + D) * (P / Q)
35.
For the following COBOL code, draw the Binary tree?
01 STUDENT_REC.
02 NAME.
03 FIRST_NAME PIC X(10).
03 LAST_NAME PIC X(10).
02 YEAR_OF_STUDY.
03 FIRST_SEM PIC XX.
03 SECOND_SEM PIC XX.
1) What is data structure?
Data structure refers to the way data is organized and manipulated. It
seeks to find ways to make data access more efficient. When dealing with
the data structure, we not only focus on one piece of data but the
different set of data and how they can relate to one another in an
organized manner.
2) Differentiate between file and structure storage structure.
The key difference between both the data structure is the memory area that
is being accessed. When dealing with the structure that resides the main
memory of the computer system, this is referred to as storage structure.
When dealing with an auxiliary structure, we refer to it as file
structures.
3) When is a binary search best applied?
A binary search is an algorithm that is best applied to search a list when
the elements are already in order or sorted. The list is searched starting
in the middle, such that if that middle value is not the target search key,
it will check to see if it will continue the search on the lower half of
the list or the higher half. The split and search will then continue in the
same manner.
4) What is a linked list?
A linked list is a sequence of nodes in which each node is connected to the
node following it. This forms a chainlike link for data storage.
5) How do you reference all the elements in a onedimension array?
To reference all the elements in a one dimension array, you need to use an
indexed loop, So that, the counter runs from 0 to the array size minus one.
In this manner, You can reference all the elements in sequence by using the
loop counter as the array subscript.
6) In what areas do data structures are applied?
Data structures are essential in almost every aspect where data is
involved. In general, algorithms that involve efficient data structure is
applied in the following areas: numerical analysis, operating system, A.I.,
compiler design, database management, graphics, and statistical analysis,
to name a few.
7) What is LIFO?
LIFO is a short form of Last In First Out. It refers how data is accessed,
stored and retrieved. Using this scheme, data that was stored last should
be the one to be extracted first. This also means that in order to gain
access to the first data, all the other data that was stored before this
first data must first be retrieved and extracted.
8 ) What is a queue?
A queue is a data structure that can simulate a list or stream of data.
In this structure, new elements are inserted at one end, and existing
elements are removed from the other end.
9) What are binary trees?
A binary tree is one type of data structure that has two nodes, a left
node, and a right node. In programming, binary trees are an extension
of the linked list structures.
10) Which data structures are applied when dealing with a recursive
function?
Recursion, is a function that calls itself based on a terminating
condition, makes use of the stack. Using LIFO, a call to a recursive
function saves the return address so that it knows how to return to the
calling function after the call terminates.
11) What is a stack?
A stack is a data structure in which only the top element can be
accessed. As data is stored in the stack, each data is pushed downward,
leaving the most recently added data on top.
12) Explain Binary Search Tree
A binary search tree stores data in such a way that they can be
retrieved very efficiently. The left subtree contains nodes whose keys
are less than the node’s key value, while the right subtree contains
nodes whose keys are greater than or equal to the node’s key value.
Moreover, both subtrees are also binary search trees.
13) What are multidimensional arrays?
Multidimensional arrays make use of multiple indexes to store data. It
is useful when storing data that cannot be represented using single
dimensional indexing, such as data representation in a board game,
tables with data stored in more than one column.
14) Are linked lists considered linear or nonlinear data
structures?
It depends on where you intend to apply linked lists. If you based it
on storage, a linked list is considered nonlinear. On the other hand,
if you based it on access strategies, then a linked list is considered
linear.
15) How does dynamic memory allocation help in managing data?
Apart from being able to store simple structured data types, dynamic
memory allocation can combine separately allocated structured blocks to
form composite structures that expand and contract as needed.
16) What is FIFO?
FIFO stands for Firstin, Firstout, and is used to represent how data
is accessed in a queue. Data has been inserted into the queue list the
longest is the one that is removed first.
17) What is an ordered list?
An ordered list is a list in which each node’s position in the list is
determined by the value of its key component, so that the key values
form an increasing sequence, as the list is traversed.
18) What is merge sort?
Merge sort, is a divideandconquer approach for sorting the data. In a
sequence of data, adjacent ones are merged and sorted to create bigger
sorted lists. These sorted lists are then merged again to form an even
bigger sorted list, which continues until you have one single sorted
list.
19) Differentiate NULL and VOID
Null is a value, whereas Void is a data type identifier. A variable
that is given a Null value indicates an empty value. The void is used
to identify pointers as having no initial size.
20) What is the primary advantage of a linked list?
A linked list is an ideal data structure because it can be modified
easily. This means that editing a linked list works regardless of how
many elements are in the list.
21) What is the difference between a PUSH and a POP?
Pushing and popping applies to the way data is stored and retrieved in
a stack. A push denotes data being added to it, meaning data is being
“pushed” into the stack. On the other hand, a pop denotes data
retrieval, and in particular, refers to the topmost data being
accessed.
22) What is a linear search?
A linear search refers to the way a target key is being searched in a
sequential data structure. In this method, each element in the list is
checked and compared against the target key. The process is repeated
until found or if the end of the file has been reached.
23) How does variable declaration affect memory allocation?
The amount of memory to be allocated or reserved would depend on the
data type of the variable being declared. For example, if a variable is
declared to be of integer type, then 32 bits of memory storage will be
reserved for that variable.
24) What is the advantage of the heap over a stack?
The heap is more flexible than the stack. That’s because memory space
for the heap can be dynamically allocated and deallocated as needed.
However, the memory of the heap can at times be slower when compared to
that stack.
25) What is a postfix expression?
A postfix expression is an expression in which each operator follows
its operands. The advantage of this form is that there is no need to
group subexpressions in parentheses or to consider operator
precedence.
26) What is Data abstraction?
Data abstraction is a powerful tool for breaking down complex data
problems into manageable chunks. This is applied by initially
specifying the data objects involved and the operations to be performed
on these data objects without being overly concerned with how the data
objects will be represented and stored in memory.
27) How do you insert a new item in a binary search tree?
Assuming that the data to be inserted is a unique value (that is, not
an existing entry in the tree), check first if the tree is empty. If
it’s empty, just insert the new item in the root node. If it’s not
empty, refer to the new item’s key. If it’s smaller than the root’s
key, insert it into the root’s left subtree, otherwise, insert it into
the root’s right subtree.
28) How does a selection sort work for an array?
The selection sort is a fairly intuitive sorting algorithm, though not
necessarily efficient. In this process, the smallest element is first
located and switched with the element at subscript zero, thereby
placing the smallest element in the first position.
The smallest element remaining in the subarray is then located next to
subscripts 1 through n1 and switched with the element at subscript 1,
thereby placing the second smallest element in the second position. The
steps are repeated in the same manner till the last element.
29) How do signed and unsigned numbers affect memory?
In the case of signed numbers, the first bit is used to indicate
whether positive or negative, which leaves you with one bit short. With
unsigned numbers, you have all bits available for that number. The
effect is best seen in the number range (an unsigned 8bit number has a
range 0255, while the 8bit signed number has a range 128 to +127.
30) What is the minimum number of nodes that a binary tree can
have?
A binary tree can have a minimum of zero nodes, which occurs when the
nodes have NULL values. Furthermore, a binary tree can also have 1 or 2
nodes.
31) What are dynamic data structures?
Dynamic data structures are structures that expand and contract as a
program runs. It provides a flexible means of manipulating data because
it can adjust according to the size of the data.
32) In what data structures are pointers applied?
Pointers that are used in linked list have various applications in the
data structure. Data structures that make use of this concept include
the Stack, Queue, Linked List and Binary Tree.
33) Do all declaration statements result in a fixed reservation in
memory?
Most declarations do, with the exemption of pointers. Pointer
declaration does not allocate memory for data, but for the address of
the pointer variable. Actual memory allocation for the data comes
during runtime.
34) What are ARRAYs?
When dealing with arrays, data is stored and retrieved using an index
that refers to the element number in the data sequence. This means that
data can be accessed in any order. In programming, an array is declared
as a variable having a number of indexed elements.
35) What is the minimum number of queues needed when implementing a
priority queue?
The minimum number of queues needed in this case is two. One queue is
intended for sorting priorities while the other queue is used for
actual storage of data.
36) Which sorting algorithm is considered the fastest?
There are many types of sorting algorithms: quick sort, bubble sort,
balloon sort, radix sort, merge sort, etc. Not one can be considered
the fastest because each algorithm is designed for a particular data
structure and data set. It would depend on the data set that you would
want to sort.
37) Differentiate STACK from ARRAY.
Stack follows a LIFO pattern. It means that data access follows a
sequence wherein the last data to be stored when the first one to be
extracted. Arrays, on the other hand, does not follow a particular
order and instead can be accessed by referring to the indexed element
within the array.
38) Give a basic algorithm for searching a binary search tree.
1.
if the tree is empty, then the target is not in the tree, end search
2. if the tree is not empty, the target is in the tree
3. check if the target is in the root item
4. if a target is not in the root item, check if a target is smaller
than the root’s value
5. if a target is smaller than the root’s value, search the left
subtree
6. else, search the right subtree
39) What is a dequeue?
A dequeue is a doubleended queue. This is a structure wherein elements
can be inserted or removed from either end.
40) What is a bubble sort and how do you perform it?
A bubble sort is one sorting technique that can be applied to data
structures such as an array. It works by comparing adjacent elements
and exchanges their values if they are out of order. This method lets
the smaller values “bubble” to the top of the list, while the larger
value sinks to the bottom.
41) What are the parts of a linked list?
A linked list typically has two parts: the head and the tail. Between
the head and tail lie the actual nodes. All these nodes are linked
sequentially.
42) How does selection sort work?
Selection sort works by picking the smallest number from the list and
placing it at the front. This process is repeated for the second
position towards the end of the list. It is the simplest sort
algorithm.
43) What is a graph?
A graph is one type of data structure that contains a set of ordered
pairs. These ordered pairs are also referred to as edges or arcs and
are used to connect nodes where data can be stored and retrieved.
44) Differentiate linear from a nonlinear data structure.
The linear data structure is a structure wherein data elements are
adjacent to each other. Examples of linear data structure include
arrays, linked lists, stacks, and queues. On the other hand, a
nonlinear data structure is a structure wherein each data element can
connect to more than two adjacent data elements. Examples of nonlinear
data structure include trees and graphs.
45) What is an AVL tree?
An AVL tree is a type of binary search tree that is always in a state
of partially balanced. The balance is measured as a difference between
the heights of the subtrees from the root. This selfbalancing tree was
known to be the first data structure to be designed as such.
46) What are doubly linked lists?
Doubly linked lists are a special type of linked list wherein traversal
across the data elements can be done in both directions. This is made
possible by having two links in every node, one that links to the next
node and another one that connects to the previous node.
47) What is Huffman’s algorithm?
Huffman’s algorithm is used for creating extended binary trees that
have minimum weighted path lengths from the given weights. It makes use
of a table that contains the frequency of occurrence for each data
element.
48) What is Fibonacci search?
Fibonacci search is a search algorithm that applies to a sorted array.
It makes use of a divideandconquer approach that can significantly
reduce the time needed in order to reach the target element.
49) Briefly explain recursive algorithm.
Recursive algorithm targets a problem by dividing it into smaller,
manageable subproblems. The output of one recursion after processing
one subproblem becomes the input to the next recursive process.
50) How do you search for a target key in a linked list?
To find the target key in a linked list, you have to apply sequential
search. Each node is traversed and compared with the target key, and if
it is different, then it follows the link to the next node. This
traversal continues until either the target key is found or if the last
node is reached.
1.What is data structure?
A data structure is a way of organizing data that considers not only the
items stored, but also their relationship to each other. Advance knowledge
about the relationship between data items allows designing of efficient
algorithms for the manipulation of data.
2.Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing
priorities.
3.What are the notations used in Evaluation of Arithmetic Expressions
using prefix and postfix forms?
Polish and Reverse Polish notations.
4.List out few of the Application of tree datastructure?
i)The manipulation of Arithmetic expression
ii)Symbol Table construction
iii)Syntax analysis.
5.What is the type of the algorithm used in solving the 8 Queens
problem?
Backtracking
6.In RDBMS, what is the efficient data structure used in the internal
storage representation?
B+ tree. Because in B+ tree, all the data is stored only in leaf nodes,
that makes searching easier. This corresponds to the records that shall be
stored in leaf nodes.
7. What is a spanning Tree?
A spanning tree is a tree associated with a network. All the nodes of the
graph appear on the tree once. A minimum spanning tree is a spanning tree
organized so that the total edge weight between nodes is minimized.
8. List out the areas in which data structures are applied extensively?
Compiler Design, Operating System, Database Management System, Statistical
analysis package, Numerical Analysis, Graphics, Artificial Intelligence,
Simulation
9. Translate infix expression into its equivalent post fix expression:
(AB)*(D/E)
(AB)*(D/E) = [AB]*[DE/] = ABDE/*
10. What are priority queues?
A priority queue is a collection of elements such that each element has
been assigned a priority.
11. What is a string?
A sequential array of characters is called a string.
12. What is Brute Force algorithm?
Algorithm used to search the contents by comparing each element of array is
called Brute Force algorithm.
13. What are the limitations of arrays?
i)Arrays are of fixed size.
ii)Data elements are stored in continuous memory locations which may not be
available always.
iii)Adding and removing of elements is problematic because of shifting the
locations.
14. How can you overcome the limitations of arrays?
Limitations of arrays can be solved by using the linked list.
15. What is a linked list?
Linked list is a data structure which store same kind of data elements but
not in continuous memory locations and size is not fixed. The linked lists
are related logically.
16. What is a node?
The data element of a linked list is called a node.
17. What does node consist of?
Node consists of two fields:data field to store the element and link field
to store the address of the next node.
18. What is a queue ?
A Queue is a sequential organization of data. A queue is a first in first
out type of data structure. An element is inserted at the last position and
an element is always taken out from the first position.
19. What are the types of Collision Resolution Techniques and the
methods used in each of the type?
Open addressing (closed hashing),The methods used include:Overflow block
Closed addressing (open hashing),The methods used include:Linked
list,Binary tree
20. What are the methods available in storing sequential files ?
Straight merging, Natural merging, Polyphase sort, Distribution of Initial
runs.
21. Mention some of the problem solving strategies?
The most widely strategies are listed below
i)Divide and conquer
ii)Binary doubling strategy
iii)Dynamic programming
22. What is divide and conquer method?
The basic idea is to divide the problem into several sub problems beyond
which cannot be further subdivided. Then solve the sub problems efficiently
and join then together to get the solution for the main problem.
23. What is the need for the header?
Header of the linked list is the first element in the list and it stores
the number of elements in the list. It points to the first data element of
the list.
24. Define leaf?
In a directed tree any node which has out degree o is called a terminal
node or a leaf.
25. What are the applications of binary tree?
Binary tree is used in data processing.
26. What are the different types of traversing?
The different types of traversing are
i)Preorder traversalyields prefix from of expression.
ii)Inorder traversalyields infix form of expression.
iii)Postorder traversalyields postfix from of expression.
27. Define preorder traversal?
i)Process the root node
ii)Process the left subtree
iii)Process the right subtree
28. Define postorder traversal?
i)Process the left subtree
ii)Process the right subtree
iii)Process the root node
29. Define in order traversal?
i)Process the left subtree
ii)Process the root node
iii)Process the right subtree
30. What is meant by sorting?
Ordering the data in an increasing or decreasing fashion according to some
relationship among the data item is called sorting.
31. What's the major distinction in between Storage structure and file
structure and how?
The expression of an specific data structure inside memory of a computer
system is termed storage structure in contrast to a storage structure
expression in auxiliary memory is normally known as a file structure.
32. Stack can be described as a pointer. Explain?
Because stack will contain a head pointer which will always point to the
top of the Stack.All Stack Operations are done using Head Pointer. Hence
Stack ca be Described as a Pointer
33. What do you mean by: Syntax Error, Logical Error, Run time Error?
Syntax ErrorSyntax Error is due to lack of knowledge in a specific
language. It is due to somebody does not know how to use the features of a
language.We can know the errors at the time of compilation.
logical ErrorIt is due to the poor understanding of the requirement or
problem.
Run time ErrorThe exceptions like divide a number by 0,overflow and
underflow comes under this.
34. What is mean by dqueue?
Dqueue stands for double ended queue. It is a abstract data structure that
implements a queue for which elements can be added to front or rear and the
elements can be removed from the rear or front. It is also called headtail
linked list
35. What is AVL tree?
Avl tree is self binary tree in which balancing factor lie between the 1
to 1.It is also known as self balancing tree.
36. what is binary tree?
Binary tree is a tree which has maximum no. of childrens either 0 or 1 or
2. i.e., there is at the most 2 branches in every node.
37. What is the difference between a stack and a Queue?
Stack – Represents the collection of elements in Last In First Out order.
Operations includes testing null stack, finding the top element in the
stack, removal of top most element and adding elements on the top of the
stack.
Queue  Represents the collection of elements in First In First Out
order.Operations include testing null queue, finding the next element,
removal of elements and inserting the elements from the queue.
Insertion of elements is at the end of the queue.Deletion of elements is
from the beginning of the queue
38. What actions are performed when a function is called?
i)arguments are passed
ii)local variables are allocated and initialized
iii)transferring control to the function
39. What is precision?
Precision refers the accuracy of the decimal portion of a value. Precision
is the number of digits allowed after the decimal point.
40. What do you mean by overflow and underflow?
When new data is to be inserted into the data structure but there is no
available space i.e.free storage list is empty this situation is called
overflow.When we want to delete data from a data structure that is empty
this situation is called underflow.
1. Is it possible to find a loop in a Linked list ?
a. Possilbe at O(n)
b. Not possible
c. Possible at O(n^2) only
d. Depends on the position of loop
Solution: a. Possible at O(n)
Have two pointers say P1 and P2 pointing to the first node of the list.
Start a loop and Increment P1 once and P2 twice in each iteration. At any
point of time if P1==P2 then there is a loop in that linked list. If P2
reaches NULL (end of linked list) then no loop exists.
2. Two linked lists L1 and L2 intersects at a particular node N1 and
from there all other nodes till the end are common. The length of the
lists are not same. What are the possibilities to find N1?.
a. Solution exist for certain cases only
b. No linear solution exist
c. Linear solution is possible
d Only Nonlinear solution exist.
Solution: c. Linear solution is possible
Have two pointers say P1 pointing to the first node of L1 and P2 to that of
L2. Traverse through both the lists. If P1 reaches L1’s last node, point it
to the first node of L2 and continue traversing. Do the same thing for P2
when it reaches L2’s last node. (By doing this, we are balancing the
difference in the length between the linked lists. The shorter one will get
over soon and by redirecting to longer list’s head, it will traverse the
extra nodes also.) Finally they will Meet at the Intersection node.
3. void PrintTree (Tree T)
{
if (T != NULL)
{
PrintTree (T> Left);
PrintElement (T> Element);
PrintTree (T>Right);
}
}
The above method ‘PrintTree’ results in which of the following traversal
a Inorder
b. Preorder
c. Postorder
d. None of the above
Solution: a. Inorder
Inorder:
void PrintTree (Tree T)
{
if (T != NULL)
{
PrintTree (T> Left);
PrintElement (T> Element);
PrintTree (T>Right);
}
}
For preorder use this order
PrintElement (T> Element);
PrintTree (T> Left);
PrintTree (T>Right);
For postorder use this order
PrintTree (T> Left);
PrintTree (T>Right);
PrintElement (T> Element);
4. Given a Binary Search Tree (BST), print its values in ascending
order.
a. Perform Depth first traversal
b. Perform Breadth first traversal
c. Perform Postorder traversal
d. Perform Inorder traversal
Solution: d. Perform Inorder traversal
It is the properfy of BST and Inorder traversal.
5. Is it possible to implement a queue using Linked List ?. Enqueue
& Dequeue should be O(1).
a. Not possible to implement.
b Only Enqueue is possible at O(1).
c. Only Dequeue is possible at O(1).
d. Both Enqueue and Dequeue is possible at O(1)
Solution: d. Both Enqueue and Dequeue is possible at O(1)
Have two pointers H pointing to the Head and T pointing to the Tail of the
linked list. Perform enqueue at T and perform dequeue at H. Update the
pointers after each operations accordingly.
6. Given a Tree, is it possible to find the greatest and least among
leaves in linear time?.
a. Solution depends on the tree structure
b.Linear solution exist
c. Only Nonlinear solution exist.
d. No linear solution exist
Solution: b. Linear solution exist
Have two variables Min and Max. Perform any tree traversal.Assign the first
traversed leaf element to Min and Max for all other leaf elements check
with these variables and update it accordingly. If a current element is
< Min then update Min with that element. If it is > Min then check
with Max.
Note: If you want to find the greatest and least among all nodes perform
the checks for each node traversed.
7. Is it possible to find find the greatest and least value among the
nodes in a given BST without using any extra variables?
a. No solution exist.
b. Solution need 2 extra variables
c. Solution exist without any extra variables
d Solution need 1 extra variable
Solution:c Solution exist without any extra variables
As per BST property, the left most node should be the least one and the
rightmost node should be the greatest. In other words, the first and last
node of an Inorder traversal are the least and greatest among the nodes
respectively.
8. Is it possible to implement 2 stack in an array?
Condition: None of the stack should indicate an overflow until every slot
of an array is used.
a. Only 1 stack can be implemented for the given condition
b. Stacks can not be implemented in array
c. 2 stacks can be implemented for the given condition.
d. 2 stacks can be implemented if the given condition is applied only for 1
stack.
Solution:c. 2 stacks can be implemented for the given condition
Start 1st stack from left (1st position of an array) and 2nd from right
(last position say n). Move 1st stack towards right( i.e 1,2,3 ...n) and
2nd towards left (i.e n,n1,n2...1).
9. Given two keys K1 & K2, write an algorithm to print all the
elements between them with K1<=K2 in a BST.
a. Solution need 2 extra spaces
b. Linear solution is possible without using any extra space
c No linear solution exist
d Solution need 1 extra space
Solution:b. Linear solution is possible without using any extra space
Perform an inorder traversal. Once you find K1 print it and continue
traversal now, print all other traversed elements until you reach K2.
Note: If K1 == K2 stop once you find K1.
10. How many stacks are required to implement a Queue.
a. One
b. Two
c. Three
d. Two + one extra space.
Solution:b Two
Have two stacks S1 and S2.
For Enqueue, perform push on S1.
For Dequeue, if S2 is empty pop all the elements from S1 and push it to S2.
The last element you popped from S1 is an element to be dequeued. If S2 is
not empty, then pop the top element in it.
What is hashing technique? Describe in brief.
In general, in all searching techniques, search time is
dependent on the number of items. Sequential search, binary
search and all the search trees are totally dependent on
number of items and many key comparisons are involved.
Hashing is a technique where search time is independent of
the number of items or elements. In this technique a hash
function is used to generate an address from a key. The
hash function takes a key as input and returns the hash
value of that key which is used as an address index in the
array.
We can write hash function as follows
h(k)=a;
Where h is hash function, k is the key, a is the hash value
of the key.
While choosing a hash function we should consider some
important points.
 It should be easy to compute
 It should generate address with minimum collision.

What are different techniques for making hash function?
Explain with example.
Techniques for making hash function.
 Truncation Method
 Midsquare Method
 Folding Method
 Division Method
Truncation Method
This is the simplest method for computing address from a
key.In this method we take only a part of the key as
address.
Example:
Let us take some 8 digit keys and find addresses for them.
Let the table size is 100 and we have to take 2 rightmost
digits for getting the hash table address. Suppose the keys
are. 62394572,87135565,93457271,45393225.
So the address of above keys will be 72,65,71 and 25
respectively.
This method is easy to compute but chances of collision are
more because last two digits can be same in more than one
keys.
Midsquare Method
In this method the key is squared and some digits from the
middle of this square are taken as address.
Example:
Suppose that table size is 1000 and keys are as follows
Key

1123

2273

3139

3045

Square of key

1261129

5166529

9853321

9272025

Address

612

665

533

720

Folding Method
In this technique the key is divided into different part
where the length of each part is same as that of the
required address, except possibly the last part.
Example:
Let key is 123945234 and the table size is 1000 then we
will broke this key as follows
123945234 > 123 945 234
Now we will add these broken parts. 123+945+234=1302. The
sum is 1302, we will ignore the final carry 1, so the
address for the key 123945234 is 302.
Division Method (ModuloDivision)
In ModuloDivision method the key is divided by the table
size and the remainder is taken as the address of the hash
table.
Let the table size is n then
H (k) =k mod n
Example
Let the keys are 123, 945,234 and table size is 11 then the
address of these keys will be.
123 % 11=2
945%11=10
235%11=4
So the hash address of above keys will be 2,10,4.
Note: 
Collisions can be minimized if the table size is taken to
be a prime number.

What are different methods of collision resolution in
hashing.
A collision occurs whenever a key is mapped to an address
that is already occupied. Collision Resolution technique
provides an alternate place in hash table where this key
can be placed.
Collision Resolution technique can be classified as:
1) Open Addressing (Closed Hashing)
a) Linear Probing
b) Quadratic Probing
c) Double Hashing
2) Separate Chaining (Open Hashing)

Describe Linear Probing with an example.
In this method if address given by hash function is already
occupied, then the key will be inserted in the next empty
position in hash table. Let the table size is 7 and hash
function returns address 4 for a key then we will search
the empty location in this sequence.
4, 5, 6, 7, 0, 1, 2, 3
Example:
Let the keys are 28, 47, 20, 36, 43, 23, 25, 54 and table
size is 11 then

Describe the following term in a tree.
a) Level b) Height c) Degree.
Let’s take an example to define the above term.
Level:
Level of any node is defined as the distance of that node
from the root. The level of root node is always zero. Node
B, C, M, E are at level 1.Nodes K,G,H,I,J,F,L are at level
2.Nodes A,N,O,P,D,S are at level 3.
Height:
Height is also known as depth of the tree. The height of
root node is one. Height of a tree is equal to one more
than the largest level number of tree. The height of the
above tree is 4.
Degree:
The number of children of a node is called its degree. The
degree of node R is 4, the degree of node B is 3.The degree
of node S is 0.The degree of a tree is the maximum degree
of the node of the tree. The degree of the above given tree
is 4.

Describe binary tree and its property.
In a binary tree a node can have maximum two children, or
in other words we can say a node can have 0,1, or 2
children.
Properties of binary tree.
1) The maximum number of nodes on any level i is 2 ^{i} where i>=0.
2) The maximum number of nodes possible in a binary tree of
height h is 2^{h}1.
3) The minimum number of nodes possible in a binary tree of
height h is equal to h.
4) If a binary tree contains n nodes then its maximum
possible height is n and minimum height possible is log _{2} (n+1).
5) If n is the total no of nodes and e is the total no of
edges then e=n1.The tree must be nonempty binary tree.
6) If n_{0} is the number of nodes with no child
and n_{2} is the number of nodes with 2 children,
then n_{0}=n_{2}+1.

Describe full binary tree and complete binary tree.
Full binary tree: A binary tree is full binary tree if all
the levels have maximum number of nodes.
A full binary tree of height h has (2^{h}– 1)
nodes.
Complete binary tree:In a complete binary tree all the
levels have maximum number of nodes except possibly the
last level.
The minimum no of nodes in a complete binary tree is 2 ^{h1} and the maximum number of nodes possible is
(2^{h}– 1).Where h is the height of the tree.

Explain Extended Binary tree.
A binarytree can be converted to an extended binary tree by
adding special nodes to leaf nodes and nodes that have only
one child.Extended binary tree is also called 2tree.
In the above figure external nodes are shown by squares and
internal nodes by circles. The extended binary tree is a
strictly binary tree means each node has either 0 or 2
children. The path length of any node is the number of
edges traversed from that node to the root node. Internal
path length of a binary tree is the sum of path lengths of
all internal nodes and external path length of a binary
tree is the sum of path lengths of all external nodes.

What are different dynamic memory allocation technique
in C .
The process of allocating memory at run time is called
dynamic memory allocation. The allocation and release of
this memory space can be done with the help of some
predefined function. These functions allocate memory from a
memory area called heap and free this memory whenever not
required.
The functions that are used to allocate memory at runtime
are as follows:
 malloc()
 calloc()
 realloc()
1. malloc()
This function allocates memory dynamically.
It is generally used as:
ptr= (datatype *) malloc(specified size);
Here ptr is a pointer of type datatype ( can be int, float,
double….) and specified size is the size in bytes. The
expression (datatype *) is used to typecast the pointer
returned by malloc().
Example:
int *ptr;
ptr=(int *)malloc(4*sizeof(int));
It allocates the memory space to hold four integer values
and the address of first byte is stored in the pointer
variable ptr. The allocated memory contains garbage value.
2. calloc()
The calloc() function is used to allocate multiple blocks
of memory.
Example:
int *ptr;
ptr=(int *)calloc(4, sizeof(int));
It allocates 4 blocks of memory and each block contains 2
bytes.
3. realloc()
We can increase or decrease the memory allocated by
malloc() or calloc() function. The realloc() function is
used to change the size of the memory block. It changes the
memory block without destroying the old data.
Example:
int *ptr;
ptr=(int *)malloc(4*sizeof(int));
ptr=(int *)realloc(ptr,newsize);
This function takes two argument, first is a pointer to the
block of memory that was previously allocated by malloc()
or calloc() and second argument is the new size of memory
block.
ptr=(int *)realloc(ptr, 4*sizeof(int)); // newsize

What are the difference between malloc() and calloc()?
Following are the main difference between malloc() and
calloc().
 calloc() function takes two parameters but malloc()
function takes only one parameter.
 Memory allocated by calloc() is initialized to zero while
memory allocated by malloc() contains garbage value.

How will you free the memory that is allocated at run
time?
Memory is one of the most important resources and it is
limited. The dynamically allocated memory is not
automatically released; it will exist till the end of
program. So it is programmer’s responsibility to free the
memory after completion. The free() function is used to
release the memory that is allocated at run time.
Example:
free(ptr);
Here ptr is a pointer variable that contains the base
address of a memory block created by malloc() or calloc()
function.

What are different application of stack.
Some of the applications of stack are as follows:
 Function calls.
 Reversal of a string.
 Checking validity of an expression containing nested
parenthesis.
 Conversion of infix expression to postfix.

How will you check the validity of an expression
containing nested parentheses?
One of the applications of stack is checking validity of an
expression containing nested parenthesis. An expression
will be valid if it satisfies the two conditions.
 The total number of left parenthesis should be equal to
the total number of right parenthesis in the expression.
 For every right parenthesis there should be a left
parenthesis of the same time.
The procedure for checking validity of an expression
containing nested parenthesis:
1. First take an empty stack
2. Scan the symbols of expression from left to right.
3. If the symbol is a left parenthesis then push it on the
stack.
4. If the symbol is right parenthesis then
If the stack is empty then the expression is invalid
because Right parentheses are more
than left parenthesis.
else
Pop an element from stack.
If popped parenthesis does not match the parenthesis being
scanned then it is invalid
because of mismatched parenthesis.
5. After scanning all the symbols of expression, if stack
is empty then expression is valid else it is invalid
because left parenthesis is more than right parenthesis.

Give the example of validating the parenthesis of
expression using stack.

Describe AVL tree or height balanced binary search
tree.
An AVL tree is binary search tree (BST) where the
difference in the height of left and right subtrees of any
node can be at most one. The technique for balancing the
binary search tree was introduced by Russian Mathematicians
G. M. Adelson and E. M. Landis in 1962. The height balanced
binary search tree is called AVL tree in their honor.
Example:
For the leaf node 12, 40, 65 and 98 left and right subtrees
are empty so difference of heights of their subtrees is
zero.
For node 20 height of left subtree is 2 and height of right
subtree is 3 so difference is 1.
For node 15 height of left subtree is 1 and height of right
subtree is 0 so difference is 1.
For node 57 height of left subtree is 1 and height of right
subtree is 2 so difference is 1.
For node 78 height of left subtree is 1 and height of right
subtree is 1 so difference is 0.
Each node of an AVL tree has a balance factor, which is
defined as the difference between the heights of left
subtree and right subtree of a node.
Balance factor of a node=Height of its left subtree 
Height of its right subtree.
In AVL tree possible values for the balance factor of any
node are 1, 0, 1.

Describe Tree Rotation in AVL tree.
After insertion or deletion operation the balance factor of
the nodes in AVL tree can be changed and the tree may not
be balanced. We can balance this tree by performing tree
rotations. We know that AVL tree is binary search tree.
Rotation of the tree should be in such a way that the new
converted tree maintain the binary search tree property
with inorder traversal same as that of the original tree.
There are two types of tree rotation
 Right Rotation
 Left Rotation
Fig: Right Rotation

Give one example of Right Rotation.
Right Rotation about node 25.

What is Data Structure?
 Data structure is a group of data elements grouped
together under one name.
 These data elements are called members. They can have
different types and different lengths.
 Some of them store the data of same type while others
store different types of data.

Which data structure is used to perform recursion?
 The data structure used for recursion is Stack.
 Its LIFO property helps it remembers its 'caller'. This
helps it know the data which is to be returned when the
function has to return.
 System stack is used for storing the return addresses of
the function calls.

Does the Minimal Spanning tree of a graph give the
shortest distance between any 2 specified nodes?
 No, it doesn’t.
 It assures that the total weight of the tree is kept to
minimum.
 It doesn't imply that the distance between any two nodes
involved in the minimumspanning tree is minimum.

If you are using C language to implement the
heterogeneous linked list, what pointer type will you
use?
 A heterogeneous linked list contains different data types
in its nodes. We can not use ordinary pointer to connect
them.
 The pointer that we use in such a case is void pointer as
it is a generic pointer type and capable of storing pointer
to any type.

Differentiate between PUSH and POP?
 Pushing and popping refers to the way data is stored into
and retrieved from a stack.
 PUSH – Data being pushed/ added to the stack.
 POP  Data being retrieved from the stack, particularly
the topmost data.

When is a binary search algorithm best applied?
 It is best applied to search a list when the elements are
already in order or sorted.
 The list here is searched starting in the middle. If that
middle value is not the correct one, the lower or the upper
half is searched in the similar way.

How do you reference all the elements in a
onedimension array?
 This is done using an indexed loop.
 The counter runs from 0 to the array size minus one.
 Using the loop counter as the array subscript helps in
referencing all the elements in onedimensional array.

What is Huffman’s algorithm?
 It is used in creating extended binary trees that have
minimum weighted path lengths from the given weights.
 It makes use of a table that contains frequency of
occurrence for each data element.

What is Fibonacci search?
 It is a search algorithm that applies to a sorted array.
 It uses divideandconquer approach that reduces the time
needed to reach the target element.

Which data structure is applied when dealing with a
recursive function?
 A recursive function is a function that calls itself
based on a terminating condition.
 It uses stack.
 Using LIFO, a call to a recursive function saves the
return address. This tells the return address to the
calling function after the call terminates.

How does dynamic memory allocation help in managing
data?
 Dynamic memory allocation helps to store simple
structured data types.
 It can combine separately allocated structured blocks to
form composite structures that expand and contract as
required.

What is a bubble sort and how do you perform it?
 Bubble sort is a sorting technique which can be applied
to data structures like arrays.
 Here, the adjacent values are compared and their
positions are exchanged if they are out of order.
 The smaller value bubbles up to the top of the list,
while the larger value sinks to the bottom.

How does variable declaration affect memory allocation?
 The amount of memory to be allocated depends on the data
type of the variable.
 An integer type variable is needs 32 bits of memory
storage to be reserved.

You want to insert a new item in a binary search tree.
How would you do it?
 Let us assume that the you want to insert is unique.
 First of all, check if the tree is empty.
 If it is empty, you can insert the new item in the root
node.
 If it is not empty, refer to the new item’s key.
 If the data to be entered is smaller than the root’s key,
insert it into the root’s left subtree.
 Otherwise, insert it into the root’s right subtree.

Why is the isEmpty() member method called?
 The isEmpty() member method is called during the dequeue
process. It helps in ascertaining if there exists any item
in the queue which needs to be removed.
 This method is called by the dequeue() method before
returning the front element.

What is a queue ?
 A Queue refers to a sequential organization of data.
 It is a FIFO type data structure in which an element is
always inserted at the last position and any element is
always removed from the first position.

What is adequeue?
 A dequeue is a doubleended queue.
 The elements here can be inserted or removed from either
end.

What is a postfix expression?
 It is an expression in which each operator follows its
operands.
 Here, there is no need to group subexpressions in
parentheses or to consider operator precedence..

What is a data structure? What are the types of data
structures? Briefly explain them
The scheme of organizing related information is known as
‘data structure’.
The types of data structure are:
Lists:
A group of similar items with connectivity to the previous
or/and next data items.
Arrays:
A set of homogeneous values
Records: A set of fields, where each field consists of data
belongs to one data type.
Trees:
A data structure where the data is organized in a
hierarchical structure. This type of data structure follows
the sorted order of insertion, deletion and modification of
data items.
Tables:
Data is persisted in the form of rows and columns. These
are similar to records, where the result or manipulation of
data is reflected for the whole table.

Define a linear and non linear data structure.
Linear data structure:
A linear data structure traverses the data elements
sequentially, in which only one data element can directly
be reached. Ex: Arrays, Linked Lists
NonLinear data structure:
Every data item is attached to several other data items in
a way that is specific for reflecting relationships. The
data items are not arranged in a sequential structure. Ex: Trees, Graphs

Define in brief an array. What are the types of array
operations?
An array is a set of homogeneous elements. Every element is
referred by an index.
Arrays are used for storing the data until the application
expires in the main memory of the computer system. So that,
the elements can be accessed at any time.
The operations are:
 Adding elements
 Sorting elements
 Searching elements
 Rearranging the elements
 Performing matrix operations
 Prefix and postfix operations

What is a matrix? Explain its uses with an example
A matrix is a representation of certain rows and columns,
to persist homogeneous data. It can also be called as
doubledimensioned array.
Uses:
 To represent class hierarchy using Boolean square matrix
 For data encryption and decryption
 To represent traffic flow and plumbing in a network
 To implement graph theory of node representation

Define an algorithm. What are the properties of an
algorithm? What are the types of algorithms?
Algorithm:
A step by step process to get the solution for a well
defined problem.
Properties of an algorithm:
 Should be written in simple English
 Should be unambiguous, precise and lucid
 Should provide the correct solutions
 Should have an end point
 The output statements should follow input, process
instructions
 The initial statements should be of input statements
 Should have finite number of steps
 Every statement should be definitive
Types of algorithms:
– Simple recursive algorithms. Ex:
Searching an element in a list
– Backtracking algorithms Ex: Depthfirst
recursive search in a tree
– Divide and conquer algorithms. Ex: Quick
sort and merge sort
– Dynamic programming algorithms. Ex:
Generation of Fibonacci series
– Greedy algorithms Ex: Counting currency
– Branch and bound algorithms. Ex:
Travelling salesman (visiting each city once and minimize
the total distance travelled)
– Brute force algorithms. Ex: Finding the
best path for a travelling salesman
– Randomized algorithms. Ex. Using a
random number to choose a pivot in quick sort).

What is an iterative algorithm?
The process of attempting for solving a problem which finds
successive approximations for solution, starting from an
initial guess. The result of repeated calculations is a
sequence of approximate values for the quantities of
interest.

What is an recursive algorithm?
Recursive algorithm is a method of simplification that
divides the problem into subproblems of the same nature.
The result of one recursion is the input for the next
recursion. The repletion is in the selfsimilar fashion.
The algorithm calls itself with smaller input values and
obtains the results by simply performing the operations on
these smaller values. Generation of factorial, Fibonacci
number series are the examples of recursive algorithms.

Explain quick sort and merge sort algorithms.
Quick sort employs the ‘divide and conquer’ concept by
dividing the list of elements into two sub elements.
The process is as follows:
1. Select an element, pivot, from the list.
2. Rearrange the elements in the list, so that all elements
those are less than the pivot are arranged before the pivot
and all elements those are greater than the pivot are
arranged after the pivot. Now the pivot is in its position.
3. Sort the both sub lists – sub list of the elements which
are less than the pivot and the list of elements which are
more than the pivot recursively.
Merge Sort:
A comparison based sorting algorithm. The input order is
preserved in the sorted output.
Merge Sort algorithm is as follows:
1. The length of the list is 0 or 1, and then it is
considered as sorted.
2. Other wise, divide the unsorted list into 2 lists each
about half the size.
3. Sort each sub list recursively. Implement the step 2
until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back
into one sorted list.

What is Bubble Sort and Quick sort?
Bubble Sort:
The simplest sorting algorithm. It involves the sorting the
list in a repetitive fashion. It compares two adjacent
elements in the list, and swaps them if they are not in the
designated order. It continues until there are no swaps
needed. This is the signal for the list that is sorted. It
is also called as comparison sort as it uses comparisons.
Quick Sort:
The best sorting algorithm which implements the ‘divide and
conquer’ concept. It first divides the list into two parts
by picking an element a ’pivot’. It then arranges the
elements those are smaller than pivot into one sub list and
the elements those are greater than pivot into one sub list
by keeping the pivot in its original place.

What are the difference between a stack and a Queue?
Stack –
Represents the collection of elements in Last In First Out
order.
Operations includes testing null stack, finding the top
element in the stack, removal of top most element and
adding elements on the top of the stack.
Queue 
Represents the collection of elements in First In First Out
order.
Operations include testing null queue, finding the next
element, removal of elements and inserting the elements
from the queue.
Insertion of elements is at the end of the queue
Deletion of elements is from the beginning of the queue.

Can a stack be described as a pointer? Explain.
A stack is represented as a pointer. The reason is that, it
has a head pointer which points to the top of the stack.
The stack operations are performed using the head pointer.
Hence, the stack can be described as a pointer.

Explain the terms Base case, Recursive case, Binding
Time, RunTime Stack and Tail Recursion.
Base case:
A case in recursion, in which the answer is known when the
termination for a recursive condition is to unwind back.
Recursive Case:
A case which returns to the answer which is closer.
Runtime Stack:
A run time stack used for saving the frame stack of a
function when every recursion or every call occurs.
Tail Recursion:
It is a situation where a single recursive call is
consisted by a function, and it is the final statement to
be executed. It can be replaced by iteration.

Is it possible to insert different type of elements in
a stack? How?
Different elements can be inserted into a stack. This is
possible by implementing union / structure data type. It is
efficient to use union rather than structure, as only one
item’s memory is used at a time.

Explain in brief a linked list.
A linked list is a dynamic data structure. It consists of a
sequence of data elements and a reference to the next
record in the sequence. Stacks, queues, hash tables, linear
equations, prefix and post fix operations. The order of
linked items is different that of arrays. The insertion or
deletion operations are constant in number.

Explain the types of linked lists.
The types of linked lists are:
Singly linked list:
It has only head part and corresponding references to the
next nodes.
Doubly linked list:
A linked list which both head and tail parts, thus allowing
the traversal in bidirectional fashion. Except the first
node, the head node refers to the previous node.
Circular linked list:
A linked list whose last node has reference to the first
node.

How would you sort a linked list?
Step 1:
Compare the current node in the unsorted list with every
element in the rest of the list. If the current element is
more than any other element go to step 2 otherwise go to
step 3.
Step 2:
Position the element with higher value after the position
of the current element. Compare the next element. Go to
step1 if an element exists, else stop the process.
Step 3:
If the list is already in sorted order, insert the current
node at the end of the list. Compare the next element, if
any and go to step 1 or quit.

What is sequential search? What is the average number
of comparisons in a sequential search?
Sequential search:
Searching an element in an array, the search starts from
the first element till the last element.
The average number of comparisons in a sequential search is
(N+1)/2 where N is the size of the array. If the element is
in the 1st position, the number of comparisons will be 1
and if the element is in the last position, the number of
comparisons will be N.

What are binary search and Fibonacci search?
Binary Search:
Binary search is the process of locating an element in a
sorted list. The search starts by dividing the list into
two parts. The algorithm compares the median value. If the
search element is less than the median value, the top list
only will be searched, after finding the middle element of
that list. The process continues until the element is found
or the search in the top list is completed. The same
process is continued for the bottom list, until the element
is found or the search in the bottom list is completed. If
an element is found that must be the median value.
Fibonacci Search:
Fibonacci search is a process of searching a sorted array
by utilizing divide and conquer algorithm. Fibonacci search
examines locations whose addresses have lower dispersion.
When the search element has nonuniform access memory
storage, the Fibonacci search algorithm reduces the average
time needed for accessing a storage location.

What is the method to find the complexity of an
algorithm?
Complexity of an algorithm can be found out by analyzing
the resources like memory, processor, etc. The
computational time is also used to find the complexity of
an algorithm. The running time through which the program is
processed requires the function of the size of the input.
The complexity is measured by number of steps that has to
be executed for a particular input. The space complexity
and the time complexity are the two main methods which
allow the user to know the complexity of the algorithm and
allow user to make it more optimized.

What is the use of space complexity and time
complexity?
The space complexity defines the storage capacity for the
input data. It defines the amount of memory that is
required to run a program to completion. The complexity
like this depends on the size of the input data and the
function that is used for the input size 'n'.
The time complexity deals with the amount of time required
by a program to complete the whole process of execution.
The time complexity allows creating optimized code and
allowing user to calculate it before writing their own
functions. The time complexity can be made such that a
program can be optimized on the basis of the chosen method.

Write an algorithm to show the postfix expression with
the input given as : a b + c d +*f ? .
The postfix expression deals with the expression where the
operators are being written after their operands. The
evaluation of these operators is being done from
lefttoright. The algorithm that is used to show the input
of a b + c d +*f ? is as follows:
Stack is cleared for the use,
symbol = insert input character
while(not end of input)
{
if (symbol is an operand)
push in stack;
else
{
pop two operands from the stack;
result=op1 symbol op2;
push result in stack;
}
symbol = next input character;
}
return (pop (stack));

Write an algorithm through which the inserting and
deleting of elements can take place in circular queue?
Circular queues are very important as it allows the element
to circulate. In this queue rear end reaches the end and
the first element in the list will become the rear of that
queue. In this queue the front element can only become the
rear element if and only if front has moved forward in the
array. The algorithm that is used to represent it is as
follows:
insert(queue,n,front,rear,item)
This procedure inserts an element item into a queue.
1. If front = 1 and rear = n, or if front = rear
+ 1, then:
Write: overflow, and return
2. [find new value of rear]
If front = NULL , then : [queue initially empty.]
Set front = 1 and rear=1.
Else if rear = n, then:
Set rear=1.
Else:
Set rear = rear + 1.
[end of structure.]
3. Set queue[rear] = item. [this inserts new element.]
4.Return to the beginning.

How expression trees are gets represented in data
structure?
Expression trees are made up of operands like constants and
variable names. The nodes also contain the operators. The
tree is a binary tree on which all the binary operations
are being performed. It consists of all the nodes
consisting of two children. It is possible for a node to
consist of only one child and other operators that can be
used to evaluate the expression tree. The operator looks at
the root value that is obtained by recursive evaluation of
the subtrees. The expression tree is being handled to show
the relationship between the operator and the operand.

How can a binary tree be represented using the
rotation?
Binary tree can have rotations and it can be done by
inserting a node in the binary search tree. There is a
balancing factor that is required and it will be calculated
like height of left subtreeheight of right subtree. Each
node in this case has 0,1,1 factor value and beyond that
there will be no modification possible to be done in the
tree. If the balancing factor comes out to be either +2 or
2 then the tree becomes unbalanced. The rotation allows
the tree to be balanced and it can be done with the left
rotation and right rotation. The rotation also helps the
searching to be quite faster than using any other tree.
Using the balance factor a tree can be managed and rotation
can be applied to the whole system to adjust and balance
the tree.

What is the difference between B tree and Binary search
tree?
Binary tree consists of only fixed number of keys and
children, whereas B tree consists of variable number of
keys and children. Binary tree keys are stored in
decreasing order, whereas B tree consists of the keys and
children in nondecreasing order.
Binary tree doesn't consists of associated child properties
whereas B tree consists of keys has an association with all
the nodes with the keys that are less than or equal to the
preceding key. Binary tree doesn't have minimization factor
concept, whereas B tree has the concept of minimization
factor where each node has minimum number of allowable
children.

What is the minimization factor and time complexity of
Btree?
The minimization factor of every node consists of minimum
number of children and they should have at least n1 keys.
There are possibilities that the root node might violate
certain properties that are having fewer than n1 keys. By
seeing this every node can have at most 2n1 keys or 2n
children. The height of the n key Btree can be found out
by keeping the minimum degree n<=2, and height as h=logt
(n+1/2). The time complexity of this will be given in Big O
notation that is the amount of time required to run the
code to the completion. The upper bound of the Btee is
provided by this and the lower bound can also be the same.
So, mathematically
O(g(n))={f(n): there exists positive constants such that
0=f
f(n)=cg(n) for all n, n=n0} , we say “f is oh of g”

How does Threaded binary tree represented in Data
Structure?
Threaded binary tree consists of a node that is in the
binary tree and having no left or right child. The child
that comes in the end is also called as leaf node then if
there is no child present, it will be represented by the
null pointers. The space that is occupied by null entries
can be used to store valuable information about the node
that is consisting of the child and the root node
information. There is a special pointer that is used to
point to the higher node in the tree also called as
ancestor. These pointers are termed as threads and the
whole representation is called as threaded binary tree. The
binary tree can be represented in inorder, preorder and
postorder form. Every node in this type of tree doesn't
have a right child. This doesn't allow the recursion of the
tree.
The code that is used to show the implementation is:
struct NODE
{
struct NODE *leftchild;
int node_value;
struct NODE *rightchild;
struct NODE *thread;
}

Explain the sorting algorithm that is most suitable to
be used with single linked list?
The sorting algorithm that is most suitable with the single
link list is the simple insertion sort. This consists of an
array and link of pointers, where the pointers are pointing
to each of the element in the array. For example: l[i] = i
+ 1 for 0 < = i < n1 and l[n1] = 1.
The linear link list can be pointed by the external pointer
which initialized it to 0. To insert the nth element in the
list the traversing time gets reduced and until the list is
being sorted out completely the process doesn't end. The
array that has to be traversed x[k] to sort the element and
put them in the list. If the sorting is done then it
reduces the time of the insertion of an element and time
for searching for a particular element at proper position.

What are the standard ways in which a graph can be
traversed?
There are two standard ways through which a graph can be
traversed and these are:
1. The depthfirst traversal: allow the graph to be
traversed from a given point and then goes to the other
points. The starting position is being defined as it
doesn't consist of any root so, there is a specific point
that is chosen to begin the traversing. In this the visits
takes place at each vertex and then recursive action is
taken to visit all the vertices adjacent to the node that
is being visited. The graph can consists of cycles, but
there is always a condition that the vertex has to be
visited only once.
2. The breadthfirst traversal: allow the graph to be
traverse one level by another level. Breadthfirst visits
all the nodes from the depth 0 and it consists of a root.
The vertex that has to be visited has to be specified that
will be traversed. The length of the vertex has to be
defined to find the shortest path to the given vertex.
Breadthfirst traverse the starting vertex and then all the
vertices that is been adjacent to it.

How helpful is abstract data type of data structures?
Abstract data type allows the user to write the code
without even worrying about the type of data being used. It
is a tool that specifies the logical properties of the data
type. ADT is a type consisting set of operations that are
called as interface. This interface is the only mechanism
through which the data type can be accessed. It defines the
new type of instance that is been created by operating on
different data types. There is always some additional
information on which ADT acts upon. It specifies the
instance of the creation time.
The abstract data type can be declared as:
LIST<data type> variable name;

How to sequentially represent maxheap?
Max heap is also known as descending heap consisting of the
objects in a heap list with some keys. It is of size n and
will be of the form of complete binary tree that is also of
nodes n. In this maxheap each node is less than or equal
to the content of its parent.
It represents the sequential complete binary tree with the
formula to calculate as:
max[j] <= max[(j1)/2] for 0 <= ((j1)/2) < j
<= n1
Maxheap contains the root element as the highest element
in the heap and from there the descending elements will be
shown on the children node. It will also be traversed in an
orderly manner and will be accessed by accessing the root
first then their children nodes.

Write an algorithm to show the reverse of link list?
Link list is a data structure that is commonly used in
programming. It is the simplest form. In this each node
consists of a child node and a reference to the next node
i.e. a link to another node. In this the group of nodes
represents a sequence that helps in traversing of the node
in an easy manner. The program is given to show the
reversing of the link list:
reverse(struct node **st)
{
struct node *p, *q, *r;
p = *st;
q = NULL;
while(p != NULL)
{
r =q;
q = p;
p = p
link;
q
link = r;
}
*st = q;
}

Write an algorithm to show various operations on
ordered list and arrays
Ordered list is a container holding the sequence of
objects. In this each object is having a unique position in
a particular sequence. The operations that are being
provided and performed on the ordered list include:
FindPosition:
is used to find the position of the object in an ordered
list.
Operator[]:
is used to access the position of the object in the ordered
list.
withdraw(Position&):
is used to remove the object from a given position in an
ordered list.
InsertAfter:
is used to insert an object after some other object or on
some position in the ordered list.
InsertBefore:
is used to insert the object in an ordered list at a
defined position in an array of the ordered list.

Write a program to show the insertion and deletion of
an element in an array using the position
To insert the element or delete the element, there is a
requirement to find out the exact location as array is a
group of linear characters, so it is very important to find
the position of the element in an array before performing
the actions on them. The program explains the insertion and
deletion operations performed on an array of elements:
void insert ( int *arr, int pos, int num )
/* This inserts an element at a given position*/
{
int i ;
for ( i = MAX  1 ; i > = pos ; i )
arr[i] = arr[i  1] ;
arr[i] = num ;
// This tells about the shifting of an element to the right
} // function of the insertion ends here
void del ( int *arr, int pos )
/* This function is used to delete the element at a given
position*/
{
int i ;
for ( i = pos ; i < MAX ; i++ )
arr[i  1] = arr[i] ;
arr[i  1] = 0 ;
}

Write an algorithm to show the procedure of insertion
into a Btree?
The procedure or the algorithm to insert an element into a
Btree is as follows:
1. There is a search function that is applied to find the
place where there is any new record to be present. When
there is any key inserted then there is a sorting function
that works to put the elements in the sorted order.
2. Then a particular node is selected and checked that is
there any way to insert the new record. If there is any way
to insert the new record then an appropriate pointer being
given that remains one more than number of records.
3. If the node overflows due to the increase in the size of
the node and upper bound, then there is a splitting being
done to decrease the size of that particular node.
4. The split will occur till all the records are not
accommodated properly at their place. There can be a way to
split the root as well to create the provision for the new
record data.

Write an algorithm that counts number of nodes in the
circular linked list
Circular linked list is a list in which the insertion and
deletion can be done in two ways. There is a provision to
count the number of nodes just by keeping a count variable
to count the data that is being inserted in the circular
list. The algorithm is given to show the count of the nodes
in the circular linked list.
Keep a circular header list in memory.
Keep a count to traverse the whole list and to keep a count
of the data element
set COUNT: = 0
1. Set PTR: = LINK [START]. {Initializes the pointer PTR}
2. Repeat steps 3, 4, 5 while PTR = START;
3. COUNT = COUNT + 1
4. Set PTR = LINK [PTR]. [PTR now points to next node]
[End of step 2 loop]
5. Exit

Why Boundary Tag Representation is used?
Boundary tag representation is used to show the memory
management using the data structures. The memory is
allocated from a large area where there is free memory
available. Memory management allows the use of segment and
process of allocation of resources. This allows the
reservation of block of 'n' bytes of memory and a space
that is larger than the space of the system. Some tasks are
performed like identifying and merging of free segments
that has to be released. The process of identification is
simpler as it only allows the location of the preceding
segment to be located and used. The identification is done
to find out the neighbors using the “used/free” flags that
are kept with the location. There has to be kept some
information regarding the processes and the resources that
has been allocated to the data element. It allows the
finding of the segment that is to find both the segments
(start and end) to be used as a part of boundary tag.

What does Simulation of queues mean?
Simulation is a process of forming and abstract model of
the real world situation. It allows understanding the
effect of modification and all the situations that are
relation to the queues like its properties. It allows the
arrangement of the simulation program in a systematic way
so that events can occur on regular basis. This allows the
transaction to be done on time, for example suppose there
is a person p1 submitting a bill and there has to be a
period of time that will be take to process his request. If
there is any free window then the person can submit the
bill and spend less time in the queue. If there is no free
availability then there will be a queue. The person has the
option to choose the shortest queue to get his work done
quickly, but he has to wait until all the previous
transactions are processed. This is the way simulation of
the queue works.

Source: Contents are provided by Technicalsymposium Google Group Members.
Disclaimer: All the above contents are provided by technicalsymposium.com Google Group members.
Further, this content is not intended to be used for commercial purpose. Technicalsymposium.com is not liable/responsible for any copyright issues.