Data Structure Oral Question Bank

What is a Data Structure?

A data structure is a way of organizing 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 for specific tasks. For
example, B-trees are particularly well-suited for the implementation of
databases, while compiler implementations usually use hash tables to look
up identifiers.
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 the traversal of
nodes is nonlinear in nature. Example: Graph and Trees.

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.
.
How is an Array different from Linked List?
 The size of the arrays is fixed, and 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 on Linked Listed.
 Extra memory space for a pointer is required with each element of the
Linked list.
 Arrays have a better cache locality that can make a pretty big difference
in performance.

Prepare Declaration of Array in C (Syntax & Example)

Prepare Declaration of Pointer in C (With Example)

- Also need to explain What printf statement will display for *P & P if P is
declare as pointer?
What is Stack and where it can be used?
Stack is a linear data structure in which the order LIFO(Last In First Out) or
FILO(First In Last Out) for accessing elements. Basic operations of the stack
are: Push, Pop, Peek
Applications of Stack:
1. Infix to Postfix Conversion using Stack
2. Evaluation of Postfix Expression
3. Reverse a String using Stack
4. Implement two stacks in an array
5. Check for balanced parentheses in an expression

What is a Queue, how it is different from the stack and how is it

implemented?
The queue is a linear structure that 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.
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 + B C D
Converting between these notations:

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 comprised of two
items – the data and a reference to the next node. Types of Linked List :
1. Singly Linked List : In this type of linked list, every node stores address
or reference of the next node in the list and the last node has next
address or reference as NULL. For example 1->2->3->4->NULL
2. 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
3. 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 a doubly circular linked list.
Eg. 1->2->3->1 [The next pointer of the last node is pointing to the first]

Which data structures are used for BFS and DFS of a graph?
 Queue is used for BFS
 Stack is used for DFS. DFS can also be implemented using
recursion (Note that recursion also uses function call stack).

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.

Linked List Questions

 Linked List Insertion
 Linked List Deletion
 middle of a given linked list
 Nth node from the end of a Linked List
(Explain with example)
Tree Traversal Questions
 Inorder
 Preorder and Postoder Traversals
 Level order traversal
 Height of Binary Tree
(Explain with example)

C structures for

Stack
Queue
Linked List
Tree
Graph

Basic Definations

Variable, Pointer, constant, operator, function, structure etc.

Prepare Algorithms for

Push & Pop operation of Stack

Enqueue Dequeue operation of Queue

Prepare any one sorting and searching method with example

Prepare Infix to postfix and Infix to prefix example

Prepare all basic definations of Tree (i.e root nodes, siblings, parent
node, sub tree etc.) with example

Prepare all basic definations of Graph (i.e Source, Sink, Indegree,

Outdegree, depth, path etc.) with example

Prepare C structure declaration for employee or Student

- Need to explain C Structure writing
- Structure variable declaration
- For multiple data entry what is the logic

(Note: On the day of oral always ask students who given their oral, what are
the questions asked as some of the questions get repeated)

*****All The best! for Oral Examination of Data Structure****