DS Interview Questions & Answers

Best DS Interview Questions and Answers

Dear Readers, Welcome to DS Interview Questions and Answers have been designed specially to get you acquainted with the nature of questions you may encounter during your Job interview for the subject of DS. These DS Questions are very important for campus placement test and job interviews. As per my experience good interviewers hardly plan to ask any particular questions during your Job interview and these model questions are asked in the online technical test and interview of many IT companies. 

1. Define Data Structures

Data Structures is defined as the way of organizing all data items that consider not only the elements stored but also stores the relationship between the elements.

2. Define primary data structures

Primary data structures are the basic data structures that directly operate upon the machine instructions. All the basic constants (integers, floating-point numbers, character constants, string constants) and pointers are considered as primary data structures.

 

3. Define static data structures

A data structure formed when the number of data items are known in advance is referred as static data structure or fixed size data structure.

 

4. List some of the static data structures in C

Some of the static data structures in C are arrays, pointers, structures etc.

 

5. Define dynamic data structures

A data structure formed when the number of data items are not known in advance is known as dynamic data structure or variable size data structure.

 

6. List some of the dynamic data structures in C

Some of the dynamic data structures in C are linked lists, stacks, queues, trees etc.

 

7. Define linear data structures

Linear data structures are data structures having a linear relationship between its adjacent elements. Eg) Linked lists

 

8. Define non-linear data structures

Non-linear data structures are data structures that don’t have a linear relationship between its adjacent elements but have a hierarchical relationship between the elements. 

Eg: Trees and Graphs

 

9. Why we need cursor implementation of linked lists?

Many languages such as BASIC and FORTRAN do not support pointers. If linked lists are required and pointers are not available, then an alternative implementation must be used known as cursor implementation.

 

10. State the different types of linked lists

The different types of linked list include singly linked list, doubly linked list and circular linked list.

 

11. List the basic operations carried out in a linked list

The basic operations carried out in a linked list include:

• Creation of a list

• Insertion of a node

• Deletion of a node

• Modification of a node

• Traversal of the list

 

12. List out the advantages of using a linked list

• It is not necessary to specify the number of elements in a linked list during its declaration

• Linked list can grow and shrink in size depending upon the insertion and deletion that occurs in the list

• Insertions and deletions at any place in a list can be handled easily and efficiently

• A linked list does not waste any memory space

 

13. List out the disadvantages of using a linked list

• Searching a particular element in a list is difficult and time consuming

• A linked list will use more storage space than an array to store the same number of elements

 

14. List out the applications of a linked list

Some of the important applications of linked lists are manipulation of polynomials, sparse matrices, stacks and queues.

 

16. Define a stack

Stack is an ordered collection of elements in which insertions and deletions are restricted to one end. The end from which elements are added and/or removed is referred to as top of the stack. Stacks are also referred as piles, push-down lists and last-in-first-out (LIFO) lists.

 

17. List out the basic operations that can be performed on a stack 

The basic operations that can be performed on a stack are 

• Push operation

• Pop operation

• Peek operation

• Empty check

• Fully occupied check

 

18. State the different ways of representing expressions

The different ways of representing expressions are

• Infix Notation

• Prefix Notation

• Postfix Notation

 

19. State the advantages of using infix notations

• It is the mathematical way of representing the expression

• It is easier to see visually which operation is done from first to last

 

20. State the advantages of using postfix notations

• Need not worry about the rules of precedence

• Need not worry about the rules for right to left associativity

• Need not need parenthesis to override the above rules

 

21. State the rules to be followed during infix to postfix conversions

• Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized

• Move the operators one by one to their right, such that each operator replaces their corresponding right parenthesis

• The part of the expression, which has been converted into postfix is to be treated as single operand

• Once the expression is converted into postfix form, remove all parenthesis

 

22. State the rules to be followed during infix to prefix conversions

• Fully parenthesize the expression starting from left to right. During parenthesizing, the operators having higher precedence are first parenthesized

• Move the operators one by one to their left, such that each operator replaces their corresponding left  parenthesis

• The part of the expression, which has been converted into prefix is to be treated as single operand

• Once the expression is converted into prefix form, remove all parenthesis

 

23. State the difference between stacks and linked lists

The difference between stacks and linked lists is that insertions and deletions may occur anywhere in a linked list, but only at the top of the stack

 

24. Mention the advantages of representing stacks using linked lists than arrays

• It is not necessary to specify the number of elements to be stored in a stack during its declaration, since memory is allocated dynamically at run time when an element is added to the stack

• Insertions and deletions can be handled easily and efficiently

• Linked list representation of stacks can grow and shrink in size without wasting memory space, depending upon the insertion and deletion that occurs in the list

• Multiple stacks can be represented efficiently using a chain for each stack

 

25. Define a queue

Queue is an ordered collection of elements in which insertions are restricted to one end called the rear end and deletions are restricted to other end called the front end. Queues are also referred as First-In-First-Out (FIFO) Lists.

 

26. Define a priority queue

Priority queue is a collection of elements, each containing a key referred as the priority for that element. Elements can be inserted in any order (i.e., of alternating priority), but are arranged in order of their priority value in the queue. The elements are deleted from the queue in the order of their priority (i.e., the elements with the highest priority is deleted first). The elements with the same priority are given equal importance and processed accordingly.

 

27. State the difference between queues and linked lists

The difference between queues and linked lists is that insertions and deletions may occur anywhere in the linked list, but in queues insertions can be made only in the rear end and deletions can be made only in the front end.

 

28. Define a Deque

Deque (Double-Ended Queue) is another form of a queue in which insertions and deletions are made at both the front and rear ends of the queue. There are two variations of a deque, namely, input restricted deque and output restricted deque. The input restricted deque allows insertion at one end (it can be either front or rear) only. The output restricted deque allows deletion at one end (it can be either front or rear) only.

 

29. Why you need a data structure?

A data structure helps you to understand the relationship of one data element with the other and organize it within the memory. Sometimes the organization might be simple and can be very clearly visioned. Eg) List of names of months in a year –Linear Data Structure, List of historical places in the world- Non-Linear Data Structure. A data structure helps you to analyze the data, store it and organize it in a logical and mathematical manner.

 

30. What are the objectives of studying data structures?

• To identify and create useful mathematical entities and operations to determine what classes of problems can be solved using these entities and operations

• To determine the representation of these abstract entities and to implement the abstract operations on these concrete representation

 

31. What is a Stack? Explain with example?

• Definition of Stack

• Operations of Stack: PUSH and POP

• Example

 

32. Write the algorithm for converting infix expression to postfix expression?

• Definition of Expression

• Types of expression

• Algorithm for infix to postfix expression

• Example

 

33. What is a Queue? Explain its operation with example?

• Definition of Queue

• Operations of Queue: insert and remove

• Example

 

34. Explain the applications of stack?

• Evaluating arithmetic expression

• Balancing the symbols

• Function calls

 

35. Write an algorithm for inserting and deleting an element from doubly linked list? Explain linear linked implementation of Stack and Queue?

• Introduction to Doubly linked list

• Operations: insertion and deletion with algorithm

• Linked list implementation of Stack

• Linked list implementation of Queue

 

36. What are the different binary tree traversal techniques?

• Preorder traversal

• Inorder traversal

• Postorder traversal

• Levelorder traversal

 

37. What are the tasks performed while traversing a binary tree?

• Visiting a node

• Traverse the left sub-tree

• Traverse the right sub-tree

 

38. What are the tasks performed during preorder traversal?

• Process the root node

• Traverse the left sub-tree

• Traverse the right sub-tree

 

39. What are the tasks performed during inorder traversal?

• Traverse the left sub-tree

• Process the root node

• Traverse the right sub-tree

 

40. What are the tasks performed during postorder traversal?

• Traverse the left sub-tree

• Traverse the right sub-tree

• Process the root node

 

41. State the merits of linear representation of binary trees.

• Storage method is easy and can be easily implemented in arrays

• When the location of a parent/child node is known, other one can be determined easily

• It requires static memory allocation so it is easily implemented in all programming language

 

42. State the demerit of linear representation of binary trees.

Insertions and deletions in a node take an excessive amount of processing time due to data movement up and down the array.

 

43. State the merit of linked representation of binary trees.

Insertions and deletions in a node involve no data movement except the rearrangement of pointers, hence less processing time.

 

44. State the demerits of linked representation of binary trees.

• Given a node structure, it is difficult to determine its parent node

• Memory spaces are wasted for storing null pointers for the nodes, which have one or no sub-trees 

• It requires dynamic memory allocation, which is not possible in some programming language

 

45. Define a binary search tree

A binary search tree is a special binary tree, which is either empty or it should satisfy the following characteristics:

• Every node has a value and no two nodes should have the same value i.e) the values in the binary search tree are distinct

• The values in any left sub-tree is less than the value of its parent node

• The values in any right sub-tree is greater than the value of its parent node

• The left and right sub-trees of each node are again binary search trees

 

46. What do you mean by general trees?

General tree is a tree with nodes having any number of children.

 

47. What is the use of threaded binary tree?

In threaded binary tree, the NULL pointers are replaced by some addresses. The left pointer of the node points to its predecessor and the right pointer of the node points to its successor. 

 

48. What is an expression tree?

An expression tree is a tree which is build from infix or prefix or postfix expression. Generally, in such a tree, the leaves are operands and other nodes are operators.

 

49. Define right-in threaded tree

Right-in threaded binary tree is defined as one in which threads replace NULL pointers in nodes with empty right sub-trees.

 

50. Define left-in threaded tree

Left-in threaded binary tree is defined as one in which each NULL pointers is altered to contain a thread to that node’s inorder predecessor. 

 

51. What is a binary search tree? Explain with example?

• Definition of binary search tree

• Operations of binary search tree: Insertion and Deletion

• Example

 

52. Explain binary tree traversals?

• Definition of tree traversal

• Types of traversals

• Example

 

53. What is a threaded binary tree? Explain its operation with example?

• Definition of threaded binary tree

• Operations of threaded binary tree: insertion

• Example

 

54. Explain the expression trees?

• Procedure to construct expression tree

• Example

 

55. Write the procedure to convert general tree to binary tree. 

• Steps 

• Example