How do you find the height of a node in a tree?
Ans:
The height
of the node equals the number of edges in the longest path to the leaf from the
node, where the depth of a leaf node is 0.
Explain
the max heap Data Structure.
Ans: It is a
type of heap data structure where the value of the root node is greater than or
equal to either of its child nodes.
Explain
the jagged array.
Ans: It is
an array whose elements themselves are arrays and may be of different
dimensions and sizes.
List some
applications of multilinked structures?
Ans: Sparse
matrix, Index generation
Name the
ways to determine whether a linked list has a loop.
Ans: Using
hashing, Using the visited nodes method (with or without modifying the basic
linked list data structure), Floyd’s cycle-finding algorithm
Do
dynamic memory allocations help in managing data? How?
Ans: Dynamic
memory allocation stores simple structured data types at runtime. It has the
ability to combine separately allocated structured blocks to form composite
structures that expand and contract as needed, thus helping manage data of data
blocks of arbitrary size, in arbitrary order.
Differentiate
NULL and VOID
Ans: Null is
a value, whereas Void is a data type identifier
Null
indicates an empty value for a variable, whereas void indicates pointers that
have no initial size
Null means
it never existed; Void means it existed but is not in effect.
What is
an AVL tree?
Ans: An AVL
(Adelson, Velskii, and Landi) tree is a height balancing binary search tree in
which the difference of heights of the left and right subtrees of any node is
less than or equal to one. This controls the height of the binary search tree
by not letting it get skewed. This is used when working with a large data set,
with continual pruning through insertion and deletion of data.
What are
the advantages of binary search over a linear search?
Ans: A
binary search is more efficient than a linear search because we perform fewer
comparisons. With linear search, we can only eliminate one element per
comparison each time we fail to find the value we are looking for, but with the
binary search, we eliminate half the set with each comparison.
Binary
search runs in O(log n) time compared to linear search’s O(n) time. This means
that the more of the elements present in the search array, the faster is binary
search compared to a linear search.
What are
the differences between the B tree and the B+ tree?
Ans: The B
tree is a self-balancing m-way tree, with m defining the tree's order.
Depending on the number of m, Btree is an extension of the Binary Search tree
in which a node can have more than one key and more than two children. The data
is provided in the B tree in a sorted manner, with lower values on the left
subtree and higher values on the right subtree.
The B+ tree
is an advanced self-balanced tree since every path from the tree's root to its
leaf is the same length. The fact that all leaf nodes are the same length
indicates that they all occur at the same level. Specific leaf nodes can’t
appear at the third level, while others appear at the second level.
What are
Binary trees?
Ans: A
binary tree is a tree data structure made up of nodes, each of which has two
offspring, known as the left and right nodes. The tree begins with a single
node called the root.
Each node in
the tree carries the following information:
Data
A pointing
device indicates the left kid.
An arrow
pointing to the correct child
List the
types of trees?
Ans: Data
structure interview questions like this are very common and frequently asked
The General
Tree
A tree is
referred to as a generic tree if its hierarchy is not constrained. In the
General Tree, each node can have an endless number of offspring, and all other
trees are subsets of the tree.
The Binary
Tree
The binary
tree is a type of tree in which each parent has at least two offspring. The
children are referred to as the left and right youngsters. This tree is more
popular than most others. When specific limitations and features are given to a
Binary tree, various trees such as AVL tree, BST (Binary Search Tree), RBT
tree, and so on are also utilized.
Tree of
Binary Search
Binary
Search Tree (BST) is a binary tree extension that includes numerous optional
constraints. In BST, a node's left child value should be less than or equal to
the parent value, while the correct child value should always be higher than or
equal to the parent's value.
The AVL Tree
The AVL tree
is a self-balancing binary search tree. The term AVL is given in honor of the
inventors Adelson-Velshi and Landis. This was the first tree to achieve dynamic
equilibrium. Each node in the AVL tree is assigned a balancing factor based on
whether the tree is balanced or not. The node kids have a maximum height of one
AVL vine.
Red and
Black Tree
Red-black
trees are another type of auto-balancing tree. The red-black term is derived
from the qualities of the red-black tree, which has either red or black painted
on each node. It helps to keep the forest in balance. Even though this tree is
not perfectly balanced, the searching process takes just O (log n) time.
The N-ary
Tree
In this sort
of tree with a node, N is the maximum number of children. A binary tree is a
two-year tree since each binary tree node has no more than two offspring. A
full N-ary tree is one in which the children of each node are either 0 or N.
What are
the applications of graph Data Structure?
Ans:
Transport grids where stations are represented as vertices and routes as the
edges of the graph
Utility
graphs of power or water, where vertices are connection points and edge the
wires or pipes connecting them
Social
network graphs to determine the flow of information and hotspots (edges and
vertices)
Neural
networks where vertices represent neurons and edge the synapses between them.
Define
the graph Data Structure?
Ans: It is a
type of non-linear data structure that consists of vertices or nodes connected
by edges or arcs to enable storage or retrieval of data. Edges may be directed
or undirected.
What are
some examples of divide and conquer algorithms?
Ans:
Quicksort is the name of a sorting algorithm. The method selects a pivot
element and rearranges the array elements so that all items less than the pivot
chosen element go to the left side of the pivot and all elements more significant
than the pivot element move to the right side.
Merge Sort
is a sorting algorithm as well. The algorithm divides the array into two
halves, sorts them recursively, and then combines the two sorted halves. The
goal of points that are closest together is to identify the nearest pair of
points in an x-y plane collection of points. The issue may be solved in O(n2)
time by computing the distances between each pair of locations and comparing
them to determine the shortest distance.
How does
the Selection sort work?
Ans:
Selection sort works by repeatedly picking the smallest number in ascending
order from the list and placing it at the beginning. This process is repeated
moving toward the end of the list or sorted subarray.
Scan all
items and find the smallest. Switch over the position as the first item. Repeat
the selection sort on the remaining N-1 items. We always iterate forward (i
from 0 to N-1) and swap with the smallest element (always i).
Time
complexity: best case O(n2); worst O(n2)
Space
complexity: worst O(1)
What is
the merge sort? How does it work?
Ans: Merge
sort is a divide-and-conquer algorithm for sorting the data. It works by
merging and sorting adjacent data to create bigger sorted lists, which are then
merged recursively to form even bigger sorted lists until you have one single
sorted list.
Which
sorting algorithm is considered the fastest? Why?
Ans: A
single sorting algorithm can’t be considered best, as each algorithm is
designed for a particular data structure and data set. However, the QuickSort
algorithm is generally considered the fastest because it has the best
performance for most inputs.
Its
advantages over other sorting algorithms include the following:
Cache-efficient:
It linearly scans and linearly partitions the input. This means we can make the
most of every cache load.
Can skip
some swaps: As QuickSort is slightly sensitive to input that is in the right
order, it can skip some swaps.
Efficient
even in worst-case input sets, as the order is generally random.
Easy
adaption to already- or mostly-sorted inputs.
When speed
takes priority over stability.
Where can
stack Data Structure be used?
Ans:
Expression evaluation
Backtracking
Memory
management
Function
calling and return
What is a
Dequeue?
Ans: It is a
double-ended queue, or a data structure, where the elements can be inserted or
deleted at both ends (FRONT and REAR).
What is a
postfix expression?
Ans: A
postfix expression is made up of operators and operands, with the operator
coming after the operands. That is, in a postfix expression, the operator comes
after the operands. Likewise, what is the proper postfix form? The correct
postfix phrase is A B + C *.
What is a
queue Data Structure?
Ans: In this
type of data structure interview questions, you can also discuss your
experience and situations using queue. A queue is an abstract data type that
specifies a linear data structure or an ordered list, using the First In First Out (FIFO) operation
to access elements. Insert operations can be performed only at one end called
REAR and delete operations can be performed only at the other end called FRONT.
What is a
queue Data Structure?
Ans: In this
type of data structure interview questions, you can also discuss your
experience and situations using queue. A queue is an abstract data type that
specifies a linear data structure or an ordered list, using the First In First Out (FIFO) operation
to access elements. Insert operations can be performed only at one end called
REAR and delete operations can be performed only at the other end called FRONT.
What are
dynamic Data Structures? Name a few.
Ans: They
are collections of data in memory that expand and contract to grow or shrink in
size as a program runs. This enables the programmer to control exactly how much
memory is to be utilized.
Examples are
the dynamic array, linked list, stack, queue, and heap.
What is a
doubly-linked list? Give some examples.
Ans: It is a
complex type (double-ended LL) of a linked list in which a node has two links,
one that connects to the next node in the sequence and another that connects to
the previous node. This allows traversal across the data elements in both
directions.
Examples
include:
A music
playlist with next and previous navigation buttons
The browser
cache with BACK-FORWARD visited pages
The undo and
redo functionality on a browser, where you can reverse the node to get to the
previous page.
Are
linked lists considered linear or non-linear Data Structures?
Ans: Linked
lists are considered both linear and non-linear data structures depending upon
the application they are used for. When used for access strategies, it is
considered as a linear data-structure. When used for data storage, it is
considered a non-linear data structure.
How are
the elements of a 2D array stored in the memory?
Ans:
Row-Major
Order: -In row-major ordering, all of the rows of a 2D array are stored in
memory in a contiguous manner.
First, the
first row of the array is entirely stored in memory, followed by the second row
of the array, and so on until the final row.
Column-Major
Order: In column-major ordering, all of the columns of a 2D array are stored in
memory in the same order. The first column of the array is entirely saved in
memory, followed by the second row of the array, and so on until the last
column of the array is wholly recorded in memory.
Describe
the types of Data Structures?
Ans: The
following are the types of data structures:
Lists: A
collection of related things linked to the previous or/and following data
items.
Arrays: A
collection of values that are all the same.
Records: A
collection of fields, each of which contains data from a single data type.
Trees: A
data structure that organizes data in a hierarchical framework. This form of
data structure follows the ordered order of data item insertion, deletion, and
modification.
Tables: The
data is saved in the form of rows and columns. These are comparable to records
in that the outcome or alteration of data is mirrored across the whole table.
List the
area of applications of Data Structure.
Ans: Data
structures are applied extensively in the following areas of computer science:
Compiler
Design,
Operating
System,
Database
Management System,
Statistical
analysis package,
Numerical
Analysis,
Graphics,
Artificial
Intelligence,
Simulation
What is
the difference between file structure and storage structure?
Ans:
Difference between file structure and storage structure:
The main
difference between file structure and storage structure is based on memory area
that is being accessed.
Storage
structure: It is the representation of the data structure in the computer
memory.
File
structure: It is the representation of the storage structure in the auxiliary
memory.
Which
data structure is used to perform recursion?
Ans: Stack
data structure is used in recursion due to its last in first out nature.
Operating system maintains the stack in order to save the iteration variables
at each function call.
Write the
stack overflow condition.
Ans:
Overflow occurs when top = Maxsize-1
Write the
postfix form of the expression: (A + B) * (C - D)
Ans: AB+CD-*
Write the
syntax in C to create a node in the singly linked list.
Ans: struct
node
{
int data;
struct node *next;
};
struct node
*head, *ptr;
ptr =
(struct node *)malloc(sizeof(struct node));
If you
are using C language to implement the heterogeneous linked list, what pointer
type should be used?
Ans: The
heterogeneous linked list contains different data types, so it is not possible
to use ordinary pointers for this. For this purpose, you have to use a generic
pointer type like void pointer because the void pointer is capable of storing a
pointer to any type.
What are
the drawbacks of array implementation of Queue?
Ans:
Memory
Wastage: The space of the array, which is used to store queue elements, can
never be reused to store the elements of that queue because the elements can
only be inserted at front end and the value of front might be so high so that,
all the space before that, can never be filled.
Array Size:
There might be situations in which, we may need to extend the queue to insert
more elements if we use an array to implement queue, It will almost be
impossible to extend the array size, therefore deciding the correct array size
is always a problem in array implementation of queue.
State the
properties of B Tree.
Ans: A B
tree of order m contains all the properties of an M way tree. In addition, it
contains the following properties.
Every node
in a B-Tree contains at most m children.
Every node
in a B-Tree except the root node and the leaf node contain at least m/2
children.
The root
nodes must have at least 2 nodes.
All leaf
nodes must be at the same level.
List some
applications of Tree-data structure?
Ans:
Applications of Tree- data structure:
The
manipulation of Arithmetic expression,
Symbol Table
construction,
Syntax
analysis
Hierarchal
data model
Differentiate
among cycle, path, and circuit?
Ans:
Path: A Path
is the sequence of adjacent vertices connected by the edges with no
restrictions.
Cycle: A
Cycle can be defined as the closed path where the initial vertex is identical
to the end vertex. Any vertex in the path can not be visited twice
Circuit: A
Circuit can be defined as the closed path where the intial vertex is identical
to the end vertex. Any vertex may be repeated.
Which
data structures are used in BFS and DFS algorithm?
Ans:
In BFS algorithm,
Queue data structure is used.
In DFS
algorithm, Stack data structure is used.
What are
Infix, prefix, Postfix notations?
Ans:
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
What is
the difference between an Array and Stack?
Ans:
Stack Data
Structure:
The size of
the stack keeps on changing as we insert and delete the element
The stack
can store elements of different data types
Array Data
Structure:
The size of
the array is fixed at the time of declaration itself
Array stores
elements of similar data type
When can
you tell that a Memory Leak will occur?
Ans:
A memory
leak occurs when a program does not free a block of memory allocated
dynamically.
Convert the
below-given expression to its equivalent Prefix And Postfix notations.
((A + B) * C
- (D - E) ^ (F + G))
Ans:
Prefix
Notation: ^ * +ABC DE + FG
postfix
Notation: AB + C * DE FG + ^
What are
the resources of algorithm analysis?
Ans. An
algorithm can be analysed using two resources.
Time, Space
Both are the
criteria used to analyse the algorithm.
The time is
measured by the no. of processes and space is measured by the CPU memory needed
by the algorithm.
What is
the difference between the algorithm and flowchart?
Ans: An
algorithm is a step-by-step representation of a given problem or a program. A
flowchart is a graphical representation of the sequence of operations or a
program.
What do
you mean by pseudocode?
Ans:
Pseudocode is an informal way such as everyday English that helps the
programmer to develop algorithms.
What do
you mean by memory allocation?
Ans.
Memory
allocation is of two types:
Static
memory allocation: it is also called compile-time allocation using arrays
Dynamic
memory allocation: it is also called run time allocation using pointers.
Explain
traversing of a binary tree with example expression is :(p+q)*(4-3)
Ans.
Inorder: p+q*4-3
Preorder: *+pq-43
Postorder: pq+43-*
What do
you mean by AVL rotation?
Ans. To make
itself balanced an AVL tree may perform four kinds of rotations.
Left
rotation
Right
rotation
Left-right
rotation
Right-left
rotation
What do
you mean by external sorting?
Ans.
External sorting is applied to the huge amount of data that can not be in the
memory all at a time.
What do
you mean by internal sorting?
Ans. When all the data that is to be sorted can be accommodated at a time in memory then internal sort methods such as bubble sort, merge sort, heap sort, etc are used.