Data Structure VIVA Questions

1. What is a Data Structure?

A data structure is a way of organizing the data so that the data can be used efficiently.
Different kinds of data structures are suited to different kinds of applications, and some are
highly specialized to specific tasks. For example, B-trees are particularly well-suited for
implementation of databases, while compiler implementations usually use hash tables to look
up identifiers.
2. What are linear and non linear data Structures?

Linear: A data structure is said to be linear if its elements form a sequence or a linear list.
Examples: Array. Linked List, Stacks and Queues

Non-Linear: A data structure is said to be non-linear if traversal of nodes is nonlinear in

nature. Example: Graph and Trees.

3. What are the various operations that can be performed on different Data Structures?

Insertion − Add a new data item in the given collection of data items.

Deletion − Delete an existing data item from the given collection of data items.

Traversal − Access each data item exactly once so that it can be processed.

Searching − Find out the location of the data item if it exists in the given collection of data
items.

Sorting − Arranging the data items in some order i.e. in ascending or descending order in
case of numerical data and in dictionary order in case of alphanumeric data.

4. How is an Array different from Linked List?

The size of the arrays is fixed, Linked Lists are Dynamic in size.

Inserting and deleting a new element in an array of elements is expensive, Whereas both
insertion and deletion can easily be done in Linked Lists.

Random access is not allowed in Linked Listed.

Extra memory space for a pointer is required with each element of the Linked list.

Arrays have better cache locality that can make a pretty big difference in performance.
5. 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: Depth-first 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, Dijkshtra’s shortest path algo, Prim’s Algo
– 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).

6. What is Stack and where it can be used?

Stack is a linear data structure which the order LIFO(Last In First Out) or FILO(First In Last
Out) for accessing elements. Basic operations of stack are : Push, Pop , Peek

Applications of Stack:

Infix to Postfix Conversion using Stack

Evaluation of Postfix Expression

Reverse a String using Stack

Implement two stacks in an array

Check for balanced parentheses in an expression

7. What is a Queue, how it is different from stack and how is it implemented?

 Queue is a linear structure which follows the order is First In First Out (FIFO) to access
elements. Mainly the following are basic operations on
queue: Enqueue, Dequeue, Front, Rear
The difference between stacks and queues is in removing. In a stack we remove the item the
most recently added; in a queue, we remove the item the least recently added. Both Queues
and Stacks can be implemented using Arrays and Linked Lists.

8. What are Infix, prefix, Postfix notations?

Infix notation: X + Y – Operators are written in-between their operands. This is the usual
way we write expressions. An expression such as

A*(B+C)/D

Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after
their operands. The infix expression given above is equivalent to

A B C + * D/

Prefix notation (also known as “Polish notation”): + X Y Operators are written before their
operands. The expressions given above are equivalent to

/*A+BCD

9. What is a Linked List and What are its types?

A linked list is a linear data structure (like arrays) where each element is a separate object.
Each element (that is node) of a list is comprising of two items – the data and a reference to
the next node.Types of Linked List :

Singly Linked List : In this type of linked list, every node stores address or reference of next
node in list and the last node has next address or reference as NULL. For example 1->2->3-
>4->NULL

Doubly Linked List : Here, here are two references associated with each node, One of the
reference points to the next node and one to the previous node. Eg. NULL<-1<->2<->3-
>NULL

Circular Linked List : Circular linked list is a linked list where all nodes are connected to
form a circle. There is no NULL at the end. A circular linked list can be a singly circular
linked list or doubly circular linked list. Eg. 1->2->3->1 [The next pointer of last node is
pointing to the first]

10. Which data structures are used for BFS and DFS of a graph?
 Queue is used for BFS

Stack is used for DFS.

11. How to check if a given Binary Tree is BST or not?

If inorder traversal of a binary tree is sorted, then the binary tree is BST. The idea is to
simply do inorder traversal and while traversing keep track of previous key value. If current
key value is greater, then continue, else return false.
12. What are the disadvantages array implementations of linked list?
Ans:
i) The no of nodes needed can’t be predicted when the program is written.
ii) The no of nodes declared must remain allocated throughout its execution
13. What is a queue?
Ans: 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.
14. What is a priority queue?
Ans: 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
i) Ascending priority queue- Here smallest item can be removed (insertion is arbitrary)
ii) Descending priority queue- Here largest item can be removed (insertion is arbitrary)
15. What are the disadvantages of sequential storage?
Ans:
i) Fixed amount of storage remains allocated to the data structure even if it contains less
element.
ii) No more than fixed amount of storage is allocated causing overflow
16. What are the disadvantages of representing a stack or queue by a linked list?
Ans:
i) A node in a linked list (info and next field) occupies more storage than a corresponding
element in an array.
ii) Additional time spent in managing the available list.
17. Which data structure is used to perform recursion?

Stack is used to perform recursion because of its LIFO (Last In First Out) property. It knows
whom to return when the function has to return.

18. What are some areas of application of data structure?

Some uses of a good data structure include:

In designing algorithms that are highly efficient.

 For managing large internet indexing services and databases with huge information.

19. What are the types of data structure?

The major types of data structure include the following:

An array: This is the number of identical elements arranged in a certain order.

A linked list: A linked list can simply be referred to as a list. Any type of data elements is
linearly collected in a linked list. The data elements are called nodes and each node has a
value pointing to the next node in the same linked list.

A class: A data structure with data fields such as a record is known as a class.

Stack: This works on the principle of first in, last out. This implies that the element that is
stored in a stack last will be retrieved first, and vice versa.

Queue: A queue works directly opposite a stack. It works on first in, first out. The element
that is inserted first will be removed first.

Linked list: Data are stored in a linked list linearly.

Trees: Non-linear data storage is used.

Graph: Non-linear data storage is used.

20. What are linear and non-linear data structures?

A linear data structure involves the arrangement of values in a linearly. Some typical
examples of a linear data structure are lists, queues, stacks, and arrays.

In a non-linear data structure, the elements are not stored in a sequence. Graphs and tree are
some examples of a non-linear data structure.

21. What factors determine the choice of data structure for a program?

If you are a programmer and want to choose a data structure for your program, consider
these factors:

The size of the data.

The size of the storage.

The data dynamics, such as changing or editing the data.

The speed of data use

22. What is the difference between a data type and data structure?

In computing, a data type is a group of data values with characteristics that are already
defined. Some data types are floats, characters, integer, and string. These are called primitive
data types. A data structure, on the other hand, is a grouping of data for easy organization and
accessibility. Tables, Array stacks, structs, queues, classes, files, and lists are some data
structure.

23. What are data structure operations?

There are four operations that can be performed on a data structure. They are:

Traversing

Insertion

Searching

Deletion

Each of these operations can be performed with ease if you have a good knowledge of data
structures.

24. 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.

25. 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.

26. 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
27. 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.

28. What are the disadvantages of linear list?

i) We cannot reach any of the nodes that precede node (p)
ii) If a list is traversed, the external pointer to the list must be persevered in order to reference
the list again

29. 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
30. What are the disadvantages of circular list?
i) We can’t traverse the list backward
ii) If a pointer to a node is given we cannot delete the node
31. Define double linked list?
It is a collection of data elements called nodes, where each node is divided into three parts
i) An info field that contains the information stored in the node
ii) Left field that contain pointer to node on left side
iii) Right field that contain pointer to node on right side

32. Parenthesis is never required in Postfix or Prefix expressions, why?

Ans: 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

33. 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
34. Minimum number of queues needed to implement the priority queue?
Ans: Two. One queue is used for actual storing of data and another for storing priorities.
35. 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.
36. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and
Postfix notations.
Ans: Prefix Notation:
^ – * +ABC – DE + FG
Postfix Notation:
AB + C * DE – – FG + ^

37. List out few of the Application of tree data-structure?

The manipulation of Arithmetic expression,

Symbol Table construction,
Syntax analysis.
38. List out few of the applications that make use of Multilinked Structures?
Ans: Sparse matrix, Index generation.
39. In tree construction which is the suitable efficient data structure?
(A) Array (b) Linked list (c) Stack (d) Queue (e) none
Ans: (b) Linked list

40. What is linear search?

Linear search is the simplest form of search. It searches for the element sequentially starting
from the first element. This search has a disadvantage if the element is located at the end.
Advantage lies in the simplicity of the search. Also it is most useful when the elements are
arranged in a random order.

41. What is binary search?

Binary search is most useful when the list is sorted. In binary search, element present in the
middle of the list is determined. If the key (number to search) is smaller than the middle element,
the binary search is done on the first half. If the key (number to search) is greater than the middle
element, the binary search is done on the second half (right). The first and the last half are again
divided into two by determining the middle element.

42. Explain the bubble sort algorithm.

Bubble sort algorithm is used for sorting a list. It makes use of a temporary variable for
swapping. It compares two numbers at a time and swaps them if they are in wrong order. This
process is repeated until no swapping is needed. The algorithm is very inefficient if the list is
long.

E.g. List: - 7 4 5 3
1. 7 and 4 are compared
46.What is hashing technique? Describe in brief.
2. Since 4 < 7, 4 is stored in a temporary variable.

3. the content of 7 is now stored in the variable which was holding 4

4. Now, the content of temporary variable and the variable previously holding 7 are swapped.

43. What is quick sort?

Quick sort is one the fastest sorting algorithm used for sorting a list. A pivot point is chosen.
Remaining elements are portioned or divided such that elements less than the pivot point are
in left and those greater than the pivot are on the right. Now, the elements on the left and
right can be recursively sorted by repeating the algorithm.

44. Describe stack operation.

Stack is a data structure that follows Last in First out strategy.

Stack Operations:-
Push – Pushes (inserts) the element in the stack. The location is specified by the pointer.
Pop – Pulls (removes) the element out of the stack. The location is specified by the pointer
Swap: - the two top most elements of the stack can be swapped
Peek: - Returns the top element on the stack but does not remove it from the stack
Rotate:- the topmost (n) items can be moved on the stack in a rotating fashion
A stack has a fixed location in the memory. When a data element is pushed in the stack, the
pointer points to the current element

45. Describe queue operation.

Queue is a data structure that follows First in First out strategy.

Queue Operations:
Push – Inserts the element in the queue at the end.
Pop – removes the element out of the queue from the front
Size – Returns the size of the queue
Front – Returns the first element of the queue.
Empty – to find if the queue is empty.

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.

47. What are different techniques for making hash function? Explain with example.
48. What are different methods of collision resolution in hashing?
49. Describe binary tree and its property.
50. 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 minimum-
spanning tree is minimum
51. 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.
52. 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.

53. 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 non-decreasing 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.