DATA STRUCTURES VIVA QUESTIONS

1Q) What is a Data Structure?

Ans) A
Data Structure
is a data object together with the relationships that exists among theinstances & among the individual
elements that compose an instance.
2Q) Types of Data Structures and give examples?
Ans) There are two types of Data Structures:1.

Linear Data Structures:

A data structure is said to be linear if the elements form asequence. It is sequential and continues in
nature i.e. access the data in sequentialmanner.In linear data structure we can not insert an item in middle
place and it maintains a linearrelationship between its elementsegs: Array, Linked list, Stack, Queue,
Dequeue etc.2.

Non Linear Data Structures:

A data structure is said to be non-linear if elements do notform a sequence. (Not sequential).
It does not maintain any linear relationship between their elements. Every data item is attached toseveral other data items in a
way that is specific for reflecting relationships. The data items arenot arranged in a sequential structure.
egs: Trees, Graphs.
[A data structure is linear if every item is related with next and previous item and it is nonlinear if it is attach with
many of the items in specific ways to reflect relationship.]3Q) What is a Singly Linked List?
Ans) Singly Linked List is a Sequence of dynamically allocated Storage elements, eachelement of which
contains a pointer to its successor. A pointer to the first element of thelist is called as head and a pointer
to the last element of the list is called as tail used tokeep track of the list elements.
4Q) What is Doubly Linked List?
Ans) In Doubly Linked List each element contains two pointers: One Pointer points to itssuccessor and
another to its predecessor (previous element).It is also called as two waylinked list (traversing can be
done in both directions).

ADDownload to read ad-free.

5Q) Differentiate Array and Linked List?

Ans)
STACKS: (LIFO DATA STRUCTURE)
6Q) What is a Stack? (LIFO Data Structure)
Ans) Stack is an ordered collection of items into which items can be inserted and deleted from
only one end called as “Top” of the
Stack. It is also called as LIFO list.(Last In FirstOut).
7Q) What is Stack Underflow?
Ans) Is Stack is empty and POP operation is performed it is not possible to delete the items.This situation
is called Stack Underflow.
8Q) What is Stack Overflow?
Ans) If Stack is full and PUSH operation is performed it is not possible to insert or Push thenew items
into the stack. This situation is called Stack Overflow.
9Q) What are the Applications of Stack?
Ans) i) Stacks are used to convert Infix expression into Postfix.ii) Stacks are used to Evaluate Postfix
Expression.iii) Stacks are used in recursion etc.
10Q) What is the use of Postfix expressions?
Ans) Postfix Expressions are easy to evaluate as postfix expressions does not make use ofoperator
precedence not does it require the use of parenthesis.
Array Linked List
1.Size of the array is fixed 1.Size of the linked list is not fixed2. Memory is allocated Statically
(or)Dynamically (at run time).(If the memory is allocated for an arrayStatically(at compile time) it is
called StaticArray and if memory is allocated at runtime (dynamically)using operator new it iscalled
Dynamic Array)2. Memory is allocated dynamically (atruntime).3.Memory wastage will be there if all
thearray positions are not utilized3.Memory is not wasted as only Requiredmemory is allocated

ADDownload to read ad-free.

QUEUES: (FIFO DATA STRUCTURE)

11Q) What is a Queue?
Ans) It is an ordered collection of items into which items can be inserted from one end calledas REAR
end and items are deleted from other end called as FRONT end of the Queue. Itis also called as FIRST IN
FIRST OUT (FIFO) LIST).
12Q) What are the applications of Queues?
Ans) i) Queues are used in Breadth First Traversal of a Tree.ii) Queues are used in implementation of
Scheduling algorithms of Operating Systems.
13Q) What is a Circular Queue?
Ans) In Circular Queue, the first position of the array is kept behind the last position of thearray.
14Q) Differentiate Linear Queue and Circular Queue?
Ans) In Linear Queue once the queue is full and the deletion is performed, even if first positionis
free(vacant) it is not possible to insert the item in that position whereas in CircularQueue it is possible
since the first position is kept behind the last position.
15Q) What is Dequeue? (Double Ended Queue)
Ans) In Double Ended Queue insertion and deletion are possible from both the ends.
TREES:

16Q) What is a Tree?

Ans) Tree is a finite non-empty set of nodes with the following properties:i)

A designated node of the set is called as root of the tree andii)

The remaining nodes are partitioned into n>=0 subsets, each of which is a tree.
Degree of a node:
The number of sub trees attached to a node is called degree of that node andthe maximum degree of any node in a tree is
called
degree of that tree.

[Note: In a general tree degree of a node is not fixed]

Nodes that have degree zero are called
Leaf or Terminal Nodes
. Consequently, the other nodesare referred to as
Non-Terminals.
The
Level of a node
is defined by letting the root be at level o or 1.The
height or depth of a tree
is defined to be the maximum level of any node in the tree.

Data Structures VIVA Questions :-

1. What is data structure?
The logical and mathematical model of a particular organization of data is called data structure.
There are two types of data structure
1. Linear
2. Nonlinear
2. What are the goals of Data Structure?
 It must rich enough in structure to reflect the actual relationship of data in real world.
 The structure should be simple enough for efficient processing of data.
3. What does abstract Data Type Mean?
Data type is a collection of values and a set of operations on these values. Abstract data type
refer to the mathematical concept that define the data type.It is a useful tool for specifying the
logical properties of a data type.ADT consists of two parts
1. Values definition
2. Operation definition
4. What is the difference between a Stack and an Array?
 Stack is a ordered collection of items
 Stack is a dynamic object whose size is constantly changing as items are pushed and
popped .
 Stack may contain different data types
 Stack is declared as a structure containing an array to hold the element of the stack, and
an integer to indicate the current stack top within the array.
ARRAY
 Array is an ordered collection of items
 Array is a static object i.e. no of item is fixed and is assigned by the declaration of the
array
 It contains same data types.
 Array can be home of a stack i.e. array can be declared large enough for maximum size
of the stack.
5. What do you mean by recursive definition?
The definition which defines an object in terms of simpler cases of itself is called recursive
definition.
6. What is sequential search?
In sequential search each item in the array is compared with the item being searched until a
match occurs. It is applicable to a table organized either as an array or as a linked list.
7. What actions are performed when a function is called?
When a function is called
1. arguments are passed
2. local variables are allocated and initialized
3. transferring control to the function
8. What actions are performed when a function returns?
 Return address is retrieved
 Function’s data area is freed
 Branch is taken to the return address
9. What is a linked list?
A linked list is a linear collection of data elements, called nodes, where the linear order is given
by pointers. Each node has two parts first part contain the information of the element second part
contains the address of the next node in the list.
10. What are the advantages of linked list over array (static data structure)?
The disadvantages of array are
 unlike linked list it is expensive to insert and delete elements in the array
 One can’t double or triple the size of array as it occupies block of memory space.
In linked list
  each element in list contains a field, called a link or pointer which contains the address of
the next element
 Successive element’s need not occupy adjacent space in memory.
11. Can we apply binary search algorithm to a sorted linked list, why?
No we cannot apply binary search algorithm to a sorted linked list, since there is no way of
indexing the middle element in the list. This is the drawback in using linked list as a data
structure.
12. What do you mean by free pool?
Pool is a list consisting of unused memory cells which has its own pointer.
13. What do you mean by garbage collection?
It is a technique in which the operating system periodically collects all the deleted space onto the
free storage list.It takes place when there is minimum amount of space left in storage list or when
“CPU” is ideal.The alternate method to this is to immediately reinsert the space into free storage
list which is time consuming.
14. 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.
15. What are the disadvantages array implementations of linked list?
1. The no of nodes needed can’t be predicted when the program is written.
2. The no of nodes declared must remain allocated throughout its execution
16. What is a queue?
A queue is an ordered collection of items from which items may be deleted at one end (front end)
and items inserted at the other end (rear end).It obeys FIFO rule there is no limit to the number of
elements a queue contains.
17. What is a priority queue?
The priority queue is a data structure in which the intrinsic ordering of the elements (numeric or
alphabetic)
Determines the result of its basic operation. It is of two types
 Ascending priority queue- Here smallest item can be removed (insertion is arbitrary)
 Descending priority queue- Here largest item can be removed (insertion is arbitrary)
18. What are the disadvantages of sequential storage?
1.Fixed amount of storage remains allocated to the data structure even if it contains less element.
2.No more than fixed amount of storage is allocated causing overflow
19. What are the disadvantages of representing a stack or queue by a linked list?
1. A node in a linked list (info and next field) occupies more storage than a
corresponding element in an array.
2. Additional time spent in managing the available list.
20. What is dangling pointer and how to avoid it?
After a call to free(p) makes a subsequent reference to *p illegal, i.e. though the storage to p is
freed but the value of p(address) remain unchanged .so the object at that address may be used as
the value of *p (i.e. there is no way to detect the illegality).Here p is called dangling pointer.
To avoid this it is better to set p to NULL after executing free(p).The null pointer value doesn’t
reference a storage location it is a pointer that doesn’t point to anything.
21. What are the disadvantages of linear list?
1. We cannot reach any of the nodes that precede node (p)
2. If a list is traversed, the external pointer to the list must be persevered in order to
reference the list again
22. Define circular list?
In linear list the next field of the last node contain a null pointer, when a next field in the last
node contain a pointer back to the first node it is called circular list.
Advantages – From any point in the list it is possible to reach at any other point
23. What are the disadvantages of circular list?
1. We can’t traverse the list backward
2. If a pointer to a node is given we cannot delete the node
24. Define double linked list?
It is a collection of data elements called nodes, where each node is divided into three parts
1. An info field that contains the information stored in the node
2. Left field that contain pointer to node on left side
3. Right field that contain pointer to node on right side
25. Is it necessary to sort a file before searching a particular item ?
If less work is involved in searching a element than to sort and then extract, then we don’t go for
sort
If frequent use of the file is required for the purpose of retrieving specific element, it is more
efficient to sort the file.Thus it depends on situation.
26. What are the issues that hamper the efficiency in sorting a file?
The issues are
1. Length of time required by the programmer in coding a particular sorting program
2. Amount of machine time necessary for running the particular program
3. The amount of space necessary for the particular program .
27. Calculate the efficiency of sequential search?
The number of comparisons depends on where the record with the argument key appears in the
table
1. If it appears at first position then one comparison
2. If it appears at last position then n comparisons
3. Average=(n+1)/2 comparisons
4. Unsuccessful search n comparisons
5. Number of comparisons in any case is O (n).
28. Is any implicit arguments are passed to a function when it is called?
Yes there is a set of implicit arguments that contain information necessary for the function to
execute and return correctly. One of them is return address which is stored within the function’s
data area, at the time of returning to calling program the address is retrieved and the function
branches to that location.
29. Parenthesis is never required in Postfix or Prefix expressions, why?
Parenthesis is not required because the order of the operators in the postfix /prefix expressions
determines the actual order of operations in evaluating the expression
30. 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
31. What are the major data structures used in the following areas : network data model &
Hierarchical data model?
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees
32. 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.
33. 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.
34. 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 (non-recursive) function. Even when such
equivalent iterative procedures are written, explicit stack is to be used.

35. What are the notations used in Evaluation of Arithmetic Expressions using prefix and
postfix forms?
Polish and Reverse Polish notations.
36. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and
Postfix notations?
1.Prefix Notation:
^ – * +ABC – DE + FG
2.Postfix Notation:
AB + C * DE – – FG + ^
37. 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.
38. List out few of the Application of tree data-structure?
The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis.
39. List out few of the applications that make use of Multilinked Structures?
Sparse matrix, Index generation.
40. in tree construction which is the suitable efficient data structure?
(A) Array (b) Linked list (c) Stack (d) Queue (e) none
(b) Linked list
41. What is the type of the algorithm used in solving the 8 Queens problem?
Backtracking
42. 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.
43. 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.
45. One of the following tree structures, 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 property of complete binary tree is maintained even after operations like additions and
deletions are done on it.
46. 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.
47. 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 minimum-spanning tree is
minimum.
48. Whether Linked List is linear or Non-linear data structure?
According to Storage Linked List is a Non-linear one.