Stacks

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data

structure that allows adding and removing elements in a particular order. Every time an
element is added, it goes on the top of the stack, the only element that can be removed is the
element that was at the top of the stack, just like a pile of objects.

Basic features of Stack

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO structure. (Last in First out).
3. push() function is used to insert new elements into the Stack and pop() is used to delete
an element from the stack. Both insertion and deletion are allowed at only one end of
Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be
in Underflow state if it is completely empty.

Applications of Stack
The simplest application of a stack is to reverse a word. You push a given word to stack -
letter by letter - and then pop letters from the stack.
There are other uses also like : Parsing, Expression Conversion(Infix to Postfix, Postfix to
Prefix etc) and many more.
Implementation of Stack
Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are
limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but
is not limited in size. Here we will implement Stack using array.
Position of Top Status of Stack

-1 Stack is Empty

0 Only one element in Stack

N-1 Stack is Full

N Overflow state of Stack

Queue Data Structures

Queue is also an abstract data type or a linear data structure, in which the first element is
inserted from one end called REAR(also called tail), and the deletion of exisiting element
takes place from the other end called as FRONT(also called head). This makes queue as
FIFO data structure, which means that element inserted first will also be removed first.
The process to add an element into queue is called Enqueue and the process of removal of an
element from queue is called Dequeue.

Basic features of Queue

1. Like Stack, Queue is also an ordered list of elements of similar data types.
2. Queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new
element in the queue must be removed, to remove the new element.
4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue
Queue, as the name suggests is used whenever we need to have any group of objects in an
order in which the first one coming in, also gets out first while the others wait for there turn,
like in the following scenarios :

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life, Call Center phone systems will use Queues, to hold people calling them in an
order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order
as they arrive, First come first served.
Implementation of Queue
Queue can be implemented using an Array, Stack or Linked List. The easiest way of
implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR)
of the queue points at the first index of the array (starting the index of array from 0). As we
add elements to the queue, the tail keeps on moving ahead, always pointing to the position
where the next element will be inserted, while the head remains at the first index.

When we remove element from Queue, we can follow two possible approaches (mentioned
[A] and [B] in above diagram). In [A] approach, we remove the element at head position, and
then one by one move all the other elements on position forward. In approach [B] we remove
the element from head position and then move head to the next position.
In approach [A] there is an overhead of shifting the elements one position forward every time
we remove the first element. In approach [B] there is no such overhead, but whener we move
head one position ahead, after removal of first element, the size on Queue is reduced by one
space each time.

Introduction to Linked Lists

Linked List is a linear data structure and it is very common data structure which consists of
group of nodes in a sequence which is divided in two parts. Each node consists of its own
data and the address of the next node and forms a chain. Linked Lists are used to create trees
and graphs.
Advantages of Linked Lists

 They are a dynamic in nature which allocates the memory when required.
 Insertion and deletion operations can be easily implemented.
 Stacks and queues can be easily executed.
 Linked List reduces the access time.

Disadvantages of Linked Lists

 The memory is wasted as pointers require extra memory for storage.

 No element can be accessed randomly; it has to access each node sequentially.
 Reverse Traversing is difficult in linked list.

Applications of Linked Lists

 Linked lists are used to implement stacks, queues, graphs, etc.

 Linked lists let you insert elements at the beginning and end of the list.
 In Linked Lists we don’t need to know the size in advance.

Types of Linked Lists

 Singly Linked List : Singly linked lists contain nodes which have a data part as well as
an address part i.e. next, which points to the next node in sequence of nodes. The
operations we can perform on singly linked lists are insertion, deletion and traversal.

 Doubly Linked List : In a doubly linked list, each node contains two links the first link
points to the previous node and the next link points to the next node in the sequence.

 Circular Linked List : In the circular linked list the last node of the list contains the
address of the first node and forms a circular chain.
Linear Linked List
The element can be inserted in linked list in 2 ways :

 Insertion at beginning of the list.

 Insertion at the end of the list.

We will also be adding some more useful methods like :

 Checking whether Linked List is empty or not.

 Searching any element in the Linked List
 Deleting a particular Node from the List

Insertion at the Beginning

Steps to insert a Node at beginning :

1. The first Node is the Head for any Linked List.

2. When a new Linked List is instantiated, it just has the Head, which is Null.
3. Else, the Head holds the pointer to the first Node of the List.
4. When we want to add any Node at the front, we must make the head point to it.
5. And the Next pointer of the newly added Node, must point to the previous Head, whether
it be NULL(in case of new List) or the pointer to the first Node of the List.
6. The previous Head Node is now the second Node of Linked List, because the new Node
is added at the front.

Inserting at the End

Steps to insert a Node at the end :

1. If the Linked List is empty then we simply, add the new Node as the Head of the Linked
List.
2. If the Linked List is not empty then we find the last node, and make it' next to the new
Node, hence making the new node the last Node.

Searching for an Element in the List

In searching we do not have to do much, we just need to traverse like we did while getting the
last node, in this case we will also compare the data of the Node. If we get the Node with the
same data, we will return it, otherwise we will make our pointer point the next Node, and so
on.
Deleting a Node from the List
Deleting a node can be done in many ways, like we first search the Node with data which we
want to delete and then we delete it. In our approach, we will define a method which will take
the data to be deleted as argument, will use the search method to locate it and will then
remove the Node from the List.
To remove any Node from the list, we need to do the following :
 If the Node to be deleted is the first node, then simply set the Next pointer of the Head to
point to the next element from the Node to be deleted.
 If the Node is in the middle somewhere, then find the Node before it, and make the Node
before it point to the Node next to it.

Circular Linked List

Circular Linked List is little more complicated linked data structure. In the circular linked list
we can insert elements anywhere in the list whereas in the array we cannot insert element
anywhere in the list because it is in the contiguous memory. In the circular linked list the
previous element stores the address of the next element and the last element stores the
address of the starting element. The elements points to each other in a circular way which
forms a circular chain. The circular linked list has a dynamic size which means the memory
can be allocated when it is required.

Application of Circular Linked List

 The real life application where the circular linked list is used is our Personal Computers,
where multiple applications are running. All the running applications are kept in a
circular linked list and the OS gives a fixed time slot to all for running. The Operating
System keeps on iterating over the linked list until all the applications are completed.
 Another example can be Multiplayer games. All the Players are kept in a Circular Linked
List and the pointer keeps on moving forward as a player's chance ends.
 Circular Linked List can also be used to create Circular Queue. In a Queue we have to
keep two pointers, FRONT and REAR in memory all the time, where as in Circular
Linked List, only one pointer is required.

Implementing Circular Linked List

Implementing a circular linked list is very easy and almost similar to linear linked list
implementation, with the only difference being that, in circular linked list the last Node will
have it's next point to the Head of the List. In Linear linked list the last Node simply holds
NULL in it's next pointer.
Array Linked List

Define Array is a collection of elements Linked list is an ordered collection

having same data type with of elements which are connected by
common name. links/pointers.

Access In array, elements can be accessed In linked list, elements can’t be

using index/subscript value, i.e. accessed randomly but can be
elements can be randomly accessed accessed only sequentiallyand
like arr[0], arr[3], etc. So array accessing element takes 0(n) time.
provides fast and random access.

Memory In array, elements are stored In linked list, elements can be

Structure in consecutive manner in memory. stored at any available place as
address of node is stored in
previous node.

Insertion & Insertion & deletion takes more Insertion & deletion are fast & easy
Deletion time in array as elements are stored in linked list as only value of
in consecutive memory locations. pointer is needed to change.

Memory In array, memory is allocated at In linked list, memory is allocated

Allocation compile time i.e. Static Memory at run time i.e.Dynamic Memory
Allocation. Allocation.

Types Array can be single dimensional, Linked list can

two dimension be singly, doubly or circularlinked
ormultidimensional. list.

Dependency In array, each element is In Linked list, location or address

independent, no connection with of elements is stored in the link part
previous element or with its of previous element/node.
location.

Extra Space In array, no pointers are used like In linked list, adjacency between
linked list so no need of extra space the elements are maintained using
in memory for pointer. pointers or links, so pointers are
used and for that extra memory
space is needed.
 Figure

Dynamic memory allocation in C:

The process of allocating memory during program execution is called dynamic memory
allocation.

Dynamic memory allocation functions in C:

C language offers 4 dynamic memory allocation functions. They are,

1. malloc()
2. calloc()
3. realloc()
4. free()

S.no Function Syntax

1 malloc () malloc (number *sizeof(int));

2 calloc () calloc (number, sizeof(int));

3 realloc () realloc (pointer_name, number * sizeof(int));

4 free () free (pointer_name);

1. malloc() function in C:

 malloc () function is used to allocate space in memory during the execution of the
program.
 malloc () does not initialize the memory allocated during execution. It carries garbage
value.
 malloc () function returns null pointer if it couldn’t able to allocate requested amount
of memory.

Example program for malloc() function in C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
char *mem_allocation;
/* memory is allocated dynamically */
mem_allocation = malloc( 20 * sizeof(char) );
if(mem_allocation== NULL )
{
printf("Couldn't able to allocate requested memory\n");
}
else
{
strcpy( mem_allocation,"fresh2refresh.com");
}
printf("Dynamically allocated memory content : " \
"%s\n", mem_allocation );
free(mem_allocation);
}
Output:
Dynamically allocated memory content : fresh2refresh.com

2. calloc() function in C:

 calloc () function is also like malloc () function. But calloc () initializes the allocated
memory to zero. But, malloc() doesn’t.

Example program for calloc() function in C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
char *mem_allocation;
/* memory is allocated dynamically */
mem_allocation = calloc( 20, sizeof(char) );
if(mem_allocation== NULL )
{
printf("Couldn't able to allocate requested memory\n");
}
else
{
strcpy( mem_allocation,"fresh2refresh.com");
}
printf("Dynamically allocated memory content : " \
"%s\n", mem_allocation );
free(mem_allocation);
}
Output:
Dynamically allocated memory content : fresh2refresh.com

3. realloc() function in C:

 realloc () function modifies the allocated memory size by malloc () and calloc ()
functions to new size.
  If enough space doesn’t exist in memory of current block to extend, new block is
allocated for the full size of reallocation, then copies the existing data to new block
and then frees the old block.

4. free() function in C:

 free () function frees the allocated memory by malloc (), calloc (), realloc () functions
and returns the memory to the system.

Example program for realloc() and free() functions in C:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
char *mem_allocation;
/* memory is allocated dynamically */
mem_allocation = malloc( 20 * sizeof(char) );
if(mem_allocation == NULL )
{
printf("Couldn't able to allocate requested memory\n");
}
else
{
strcpy( mem_allocation,"fresh2refresh.com");
}
printf("Dynamically allocated memory content : " \
"%s\n", mem_allocation );
mem_allocation=realloc(mem_allocation,100*sizeof(char));
if(mem_allocation == NULL )
{
printf("Couldn't able to allocate requested memory\n");
}
else
{
strcpy(mem_allocation,"space is extended upto " \
"100 characters");
}
printf("Resized memory : %s\n", mem_allocation );
free(mem_allocation);
}
Output:
Dynamically allocated memory content : fresh2refresh.com
Resized memory : space is extended upto 100 characters

Difference between static memory allocation and dynamic memory allocation in C:

S.no Static memory allocation Dynamic memory allocation

1 In static memory allocation, memory is allocated In dynamic memory allocation,

while writing the C program. Actually, user memory is allocated while executing
requested memory will be allocated at compile the program. That means at run time.
time.
 2 Memory size can’t be modified while execution. Memory size can be modified while
Example: array execution.
Example: Linked list

Difference between malloc() and calloc() functions in C:

S.no malloc() calloc()

1 It allocates only single block of requested It allocates multiple blocks of requested

memory memory

2 int *ptr;ptr = malloc( 20 * sizeof(int) );For int *ptr;Ptr = calloc( 20, 20 * sizeof(int)
the above, 20*4 bytes of memory only );For the above, 20 blocks of memory
allocated in one block. will be created and each contains 20*4
Total = 80 bytes bytes of memory.
Total = 1600 bytes

3 malloc () doesn’t initializes the allocated calloc () initializes the allocated memory
memory. It contains garbage values to zero

4 type cast must be done since this function Same as malloc () function int *ptr;ptr =
returns void pointer int *ptr;ptr = (int*)calloc( 20, 20 * sizeof(int) );
(int*)malloc(sizeof(int)*20 );

TYPES OF DATA STRUCTURES

A data structure is a structured set of variables associated with one another in different ways,
cooperatively defining components in the system and capable of being operated upon in the
program. Following operations are done on data structures:
1. Data organization or clubbing
2. Accessing technique
3. Manipulating selections for information.

Data structures are the basis of programming tools and the choice of data structures should
provide the following:
1. The data structures should satisfactorily represent the relationship between data
elements.
2. The data structures should be easy so that the programmer can easily process the data.

Data structures have been classified in several ways.

Linear
In linear data structures, values are arranged in linear fashion. Arrays, linked lists, stacks and
queues are examples of linear data structures in which values are stored in a sequence.
Non-Linear
This type is opposite to linear. The data values in this structure are not arranged in order.
Tree, graph, table and sets are examples of non-linear data structures.
Homogenous
In this type of data structures, values of the same types of data are stored, as in an array.
Non-homogenous
In this type of data structures, data values of different types are grouped, as in structures and
classes.
Dynamic
In dynamic data structures such as references and pointers, size and memory locations can be
changed during program execution.
Static
Static keyword in C is used to initialize the variable to 0 (NULL). The value of a static
variable remains in the memory throughout the program. Value of static variable persists.

Question and Answers

1. What are circular queues? Write down routines for inserting and deleting elements from a
circular queue implemented using arrays.

Circular queue: Static queues have a very big drawback that once the queue is FULL,
even though we delete few elements from the "front" and relieve some occupied space, we
are not able to add anymore elements as the "rear" has already reached the Queue's rear most
position. The solution lies in a queue in which the moment "rear" reaches its end; the "first"
element will become the queue's new "rear". This type of queue is known as circular queue
having a structure like this in which, once the Queue is full the "First" element of the Queue
becomes the "Rear" most element, if and only if the "Front" has moved forward;

2.Write down any four application of a stack

(i) Conversion of infix to postfix form

(ii) Reversing of a line.

(iii) Removal of recursion

(iv) Evaluating postfix expression

3. Complexity of an Algorithm

An algorithm is a sequence of steps to solve a problem; there may be more than one
algorithm to solve a problem. The choice of a particular algorithm depends upon following
consideration:-

1) Time Complexity

2) Space Complexity

Time Complexity:- The time complexity of an algorithm is the amount of time it needs to run
to completion. Some of the reasons for studying time complexity are:-

 We may be interested to know in advance whether the program will provide a satisfactory
real time response.
 There may be several possible solutions with different time requirement.
Space Complexity:- The space complexity of an algorithm is the amount of memory it needs
to run to completion. Some of the reasons to study space complexity are: -

 There may be several possible solutions with in different space requirement.

 To estimate the size of the largest problem that a program can solve.

4.STACK:
 A stack is one of the most commonly used data structure. A stack is also called a Last-In-
First-Out (LIFO) system, is a linear list in which insertion or deletion can take place only at
one end called the top. This structure operates in the same way as the stack of trays If we
want to place another tray, it can be placed only at the top. Similarly, if we want to remove a
tray from stack of trays, it can only be removed from the top. The insertion and deletion
operations in stack terminology are known as PUSH and POP operation

5.Implementation of Stack

Stacks can be implemented in the following 2 ways:

a) Arrays

b) Linked List

a) Arrays:- To implement a stack we need a variable called top, that holds the index of the top
element of stack and an array to hold the element of the stack.

b) Linked List:- A stack represented using a linked list is known as linked stack.

The array based representation of stack suffers from following limitations.

 Size of stack must be known in advance

 Overflow condition might occur.
The linked representation allows a stack to grow to a limit of the computer’s memory.

6.Application of Queue

(i) Queue is used in time sharing system in which programs with the same priority form a
queue while waiting to be executed.

(ii) Queue is used for performing level order traversal of a binary tree and for performing
breadth first search at a graph.

(ii) Used in simulation related problem.

(iii) When jobs are submitted to a networked printer, they are arranged in order of arrival, ie.
Jobs are placed in a queue.

7.Height Balanced Tree (AVL Tree)

An AVL tree is a binary search tree in which the height of the left and right subtree of the
root differ by at most 1 and in which the left and right subtrees are again AVL trees.

8.Common uses of tree.

1. Manipulate hierarchical data.
2. Make information easy to search.
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms

9.What is a header node in linked list?

Header node is a pointer variable of the structure type. This node contains the address of the
first node of the linked list. If this node contains NULL, then this shows that linked list is
empty. Header node is needed to keep track of the node of the linked list. This is a start node
for traversing, displaying, insertion, deletion.

10.Explain an efficient way of storing a sparse matrix in memory. Write a module to find the
transpose of a sparse matrix stored in this way.

A matrix in which number of zero entries are much higher than the number of non
zero entries is called sparse matrix. The natural method of representing matrices in memory
as two-dimensional arrays may not be suitable for sparse matrices.

One may save space by storing only nonzero entries. For example matrix A (3*3 matrix)
represented below

020

500

069

can be written in sparse matrix form as:

334

122

215

326

339

where first row represent the dimension of matrix and last column tells the number of non
zero values; second row onwards it is giving the position and value of non zero number.

11.Sorting

Sorting is a technique to rearrange the elements of a list in ascending or descending order,

which can be numerical, lexicographical, or any user-defined order. Sorting is a process
through which the data is arranged in ascending or descending order.

12.What is sequential search? What is the average number of comparisons in a sequential

search?

Sequential search: Searching an element in an array, the search starts from the first element
till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size of
the array. If the element is in the 1st position, the number of comparisons will be 1 and if the
element is in the last position, the number of comparisons will be N.

13.What is a Binary Search Tree (BST)?

A binary search tree B is a binary tree each node of which satisfies the following conditions:
1. The value of the left-subtree of ‘x’ is less than the value at ‘x’
2. The value of the right-subtree of ‘x’ is greater than value at ‘x’
3. the left-subtree and right-subtree of binary search tree are again binary search tree.

14.Write down any four application of a stack

(i) Conversion of infix to postfix form
(ii) Reversing of a line.
(iii) Removal of recursion
(iv) Evaluating post fix expression

10. Array is made up of similar data structure that exists in any language. Array is set of
similar data types. Array is the collection of similar elements. These similar elements
could be all int or all float or all char etc. Array of char is known as string. All
elements of the given array must be of same type. Array is finite ordered set of
homogeneous elements. The number of elements in the array is prespecified.
For example. Ordinary variable: - int a
Array: - inta[10]
An ordinary variable of a simple data type can store a single element only
Representation of Array in memory
Let a be a 2 dimensional m x n array
Col 0 Col 1 Col 2
Row 0 a00 a01 a02
Row 1 a10 a11 a12
Row 2 a20 a21 a22
Though a is pictured as a rectangular pattern with in row and n column it is represented in
memory by a row of m x n elements. Sequential memory locations the element can be stored
in row major order.
Column major order:- the elements are stored column by column ie m elements of the 1st
column is stored in first m locations, elements of the 2nd column are stored in next m
location and so on..
a00
a10
a20
a01
a11
a21
a01
a11
a22
Row major order:-
The elements are stored row by row ie. N elements of the 1st row are stored in 1st n location,
elements of 2nd row are stored in next n location, and so on
a00
a01
a02
a10
a11
a12
a20
a21
a22

11. Height Balanced Tree (AVL Tree)

An AVL tree is a binary search tree in which the height of the left and right subtree of the
root differ by at most 1 and in which the left and right subtrees are again AVL trees. With
each node of an AVL tree is associated with a balanced factor that is left high, equal or right
high, according, respectively, as the left subtrees has height greater than, equal to, or less
than that of the right subtree.
Definition for Preorder:
Preorder traversal of a node performs the operation first on the node itself, then on its
left descendants, and finally on its right descendants. In other words, a node is always visited
before any of its children.

Pseudocode

Create the stack

Push the root node on the stack
While the stack is not empty
Pop a node
If the node is not null
Print its value
Push the node’s right child on the stack
Push the node’s left child on the stack

Inorder:
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Binary Trees
Introduction
We extend the concept of linked data structures
to structure containing nodes with more than
one self-referenced field. A binary tree is made
of nodes, where each node contains a "left"
reference, a "right" reference, and a data
element. The topmost node in the tree is called
the root.

Every node (excluding a root) in a tree is

connected by a directed edge from exactly one
other node. This node is called a parent. On the
other hand, each node can be connected to
arbitrary number of nodes, called children.
Nodes with no children are called leaves, or
external nodes. Nodes which are not leaves are
called internal nodes. Nodes with the same
parent are called siblings.
More tree terminology:
The depth of a node is the number of edges from the root to the node.
The height of a node is the number of edges from the node to the deepest leaf.
The height of a tree is a height of the root.
A full binary tree.is a binary tree in which each node has exactly zero or two children.
A complete binary tree is a binary tree, which is completely filled, with the possible
exception of the bottom level, which is filled from left to right.
A complete binary tree is very special tree, it provides the best possible ratio between the
number of nodes and the height.

Advantages of trees
Trees are so useful and frequently used, because they have some very serious advantages:
Trees reflect structural relationships in the data
Trees are used to represent hierarchies
Trees provide an efficient insertion and searching
Trees are very flexible data, allowing to move subtrees around with minumum effort.

Traversals
A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data
structure, there is no unique traversal. We will consider several traversal algorithms with we
group in the following two kinds
depth-first traversal
breadth-first traversal

There are three different types of depth-first traversals, :

PreOrder traversal - visit the parent first and then left and right children;
InOrder traversal - visit the left child, then the parent and the right child;
PostOrder traversal - visit left child, then the right child and then the parent;
There is only one kind of breadth-first traversal--the level order traversal. This traversal
visits nodes by levels from top to bottom and from left to right.

As an example consider the following tree

and its four traversals:

PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2

In the next picture we demonstarte the order of node visitation. Number 1 denote the first
node in a particular traversal and 7 denote the last node.
 Describe the following term in a tree.
a) Level b) Height c) Degree.
Let’s take an example to define the above term.

Level:
Level of any node is defined as the distance of that node from the root. The level of root
node is always zero. Node B, C, M, E are at level 1.Nodes K,G,H,I,J,F,L are at level
2.Nodes A,N,O,P,D,S are at level 3.
Height:
Height is also known as depth of the tree. The height of root node is one. Height of a tree
is equal to one more than the largest level number of tree. The height of the above tree is
4.
Degree:
The number of children of a node is called its degree. The degree of node R is 4, the
degree of node B is 3.The degree of node S is 0.The degree of a tree is the maximum
degree of the node of the tree. The degree of the above given tree is 4.

Describe binary tree and its property.

In a binary tree a node can have maximum two children, or in other words we can say a
node can have 0,1, or 2 children.
Properties of binary tree.
1) The maximum number of nodes on any level i is 2i where i>=0.
2) The maximum number of nodes possible in a binary tree of height h is 2h-1.
3) The minimum number of nodes possible in a binary tree of height h is equal to h.
4) If a binary tree contains n nodes then its maximum possible height is n and minimum
height possible is log2 (n+1).
5) If n is the total no of nodes and e is the total no of edges then e=n-1.The tree must be
non-empty binary tree.
6) If n0 is the number of nodes with no child and n2 is the number of nodes with 2
children, then n0=n2+1.

6. What are different dynamic memory allocation technique in C .

The process of allocating memory at run time is called dynamic memory allocation. The
allocation and release of this memory space can be done with the help of some
predefined function. These functions allocate memory from a memory area called heap
and free this memory whenever not required. The functions that are used to allocate
memory at runtime are as follows:
- malloc()
- calloc()
- realloc()
1. malloc()
This function allocates memory dynamically. It is generally used as:
ptr= (datatype *) malloc(specified size);
Here ptr is a pointer of type datatype ( can be int, float, double….) and specified size is
the size in bytes. The expression (datatype *) is used to typecast the pointer returned by
malloc().
Example:
int *ptr;
ptr=(int *)malloc(4*sizeof(int));
It allocates the memory space to hold four integer values and the address of first byte is
stored in the pointer variable ptr. The allocated memory contains garbage value.
2. calloc()
The calloc() function is used to allocate multiple blocks of memory.
Example:
int *ptr;
ptr=(int *)calloc(4, sizeof(int));
It allocates 4 blocks of memory and each block contains 2 bytes.
3. realloc()
We can increase or decrease the memory allocated by malloc() or calloc() function. The
realloc() function is used to change the size of the memory block. It changes the memory
block without destroying the old data.
Example:
int *ptr;
ptr=(int *)malloc(4*sizeof(int));
ptr=(int *)realloc(ptr,newsize);
This function takes two argument, first is a pointer to the block of memory that was
previously allocated by malloc() or calloc() and second argument is the new size of
memory block.
ptr=(int *)realloc(ptr, 4*sizeof(int)); // newsize
What are the difference between malloc() and calloc()?
Following are the main difference between malloc() and calloc().
- calloc() function takes two parameters but malloc() function takes only one parameter.
- Memory allocated by calloc() is initialized to zero while memory allocated by malloc()
contains garbage value.

7. How will you free the memory that is allocated at run time?
Memory is one of the most important resources and it is limited. The dynamically
allocated memory is not automatically released; it will exist till the end of program. So it
is programmer’s responsibility to free the memory after completion. The free() function
is used to release the memory that is allocated at run time.
Example:
free(ptr);
Here ptr is a pointer variable that contains the base address of a memory block created
by malloc() or calloc() function.

8. What are different application of stack.

Some of the applications of stack are as follows:
- Function calls.
- Reversal of a string.
- Checking validity of an expression containing nested parenthesis.
- Conversion of infix expression to postfix.

9. Describe AVL tree or height balanced binary search tree.

An AVL tree is binary search tree (BST) where the difference in the height of left and
right subtrees of any node can be at most one. The technique for balancing the binary
search tree was introduced by Russian Mathematicians G. M. Adelson and E. M. Landis
in 1962. The height balanced binary search tree is called AVL tree in their honor.
Example:

For the leaf node 12, 40, 65 and 98 left and right subtrees are empty so difference of
heights of their subtrees is zero.
For node 20 height of left subtree is 2 and height of right subtree is 3 so difference is 1.
For node 15 height of left subtree is 1 and height of right subtree is 0 so difference is 1.
For node 57 height of left subtree is 1 and height of right subtree is 2 so difference is 1.
For node 78 height of left subtree is 1 and height of right subtree is 1 so difference is 0.
Each node of an AVL tree has a balance factor, which is defined as the difference
between the heights of left subtree and right subtree of a node.
Balance factor of a node=Height of its left subtree - Height of its right subtree.
In AVL tree possible values for the balance factor of any node are -1, 0, 1.

10. What is Data Structure?

- Data structure is a group of data elements grouped together under one name.
- These data elements are called members. They can have different types and different
lengths.
- Some of them store the data of same type while others store different types of data.

11. Which data structure is used to perform recursion?

- The data structure used for recursion is Stack.
- Its LIFO property helps it remembers its 'caller'. This helps it know the data which is to
be returned when the function has to return.
- System stack is used for storing the return addresses of the function calls.

12. Differentiate between PUSH and POP?

- Pushing and popping refers to the way data is stored into and retrieved from a stack.
- PUSH – Data being pushed/ added to the stack.
- POP - Data being retrieved from the stack, particularly the topmost data.

13. When is a binary search algorithm best applied?

- It is best applied to search a list when the elements are already in order or sorted.
- The list here is searched starting in the middle. If that middle value is not the correct
one, the lower or the upper half is searched in the similar way.

14. What is a bubble sort and how do you perform it?

- Bubble sort is a sorting technique which can be applied to data structures like arrays.
- Here, the adjacent values are compared and their positions are exchanged if they are
out of order.
- The smaller value bubbles up to the top of the list, while the larger value sinks to the
bottom.

15. You want to insert a new item in a binary search tree. How would you do it?
- Let us assume that the you want to insert is unique.
- First of all, check if the tree is empty.
- If it is empty, you can insert the new item in the root node.
- If it is not empty, refer to the new item’s key.
- If the data to be entered is smaller than the root’s key, insert it into the root’s left
subtree.
- Otherwise, insert it into the root’s right subtree.

16. What is a queue ?

- A Queue refers to a sequential organization of data.
- It is a FIFO type data structure in which an element is always inserted at the last
position and any element is always removed from the first position.

17. What is a dequeue?

- A dequeue is a double-ended queue.
- The elements here can be inserted or removed from either end.

18. What is a postfix expression?

- It is an expression in which each operator follows its operands.
- Here, there is no need to group sub-expressions in parentheses or to consider operator
precedence..

19. What is a data structure? What are the types of data structures? Briefly explain
them
The scheme of organizing related information is known as ‘data structure’. The types of
data structure are:
Lists: A group of similar items with connectivity to the previous or/and next data items.
Arrays: A set of homogeneous values
Records: A set of fields, where each field consists of data belongs to one data type.
Trees: A data structure where the data is organized in a hierarchical structure. This type
of data structure follows the sorted order of insertion, deletion and modification of data
items.
Tables: Data is persisted in the form of rows and columns. These are similar to records,
where the result or manipulation of data is reflected for the whole table.
20. Define a linear and non linear data structure.
Linear data structure: A linear data structure traverses the data elements sequentially,
in which only one data element can directly be reached. Ex: Arrays, Linked Lists
Non-Linear data structure: Every data item is attached to several other data items in a
way that is specific for reflecting relationships. The data items are not arranged in a
sequential structure. Ex: Trees, Graphs

21. Define in brief an array. What are the types of array operations?
An array is a set of homogeneous elements. Every element is referred by an index.
Arrays are used for storing the data until the application expires in the main memory of
the computer system. So that, the elements can be accessed at any time. The operations
are:
- Adding elements
- Sorting elements
- Searching elements
- Re-arranging the elements
- Performing matrix operations
- Pre-fix and post-fix operations

22. What is a matrix? Explain its uses with an example

A matrix is a representation of certain rows and columns, to persist homogeneous data. It
can also be called as double-dimensioned array.
Uses:
- To represent class hierarchy using Boolean square matrix
- For data encryption and decryption
- To represent traffic flow and plumbing in a network
- To implement graph theory of node representation

23. Explain merge sort algorithms.

Merge Sort: A comparison based sorting algorithm. The input order is preserved in the
sorted output.
Merge Sort algorithm is as follows:
1. The length of the list is 0 or 1, and then it is considered as sorted.
2. Other wise, divide the unsorted list into 2 lists each about half the size.
3. Sort each sub list recursively. Implement the step 2 until the two sub lists are sorted.
4. As a final step, combine (merge) both the lists back into one sorted list.

24. What is Bubble Sort and Quick sort?

Bubble Sort: The simplest sorting algorithm. It involves the sorting the list in a
repetitive fashion. It compares two adjacent elements in the list, and swaps them if they
are not in the designated order. It continues until there are no swaps needed. This is the
signal for the list that is sorted. It is also called as comparison sort as it uses
comparisons.
Quick Sort: The best sorting algorithm which implements the ‘divide and conquer’
concept. It first divides the list into two parts by picking an element a ’pivot’. It then
arranges the elements those are smaller than pivot into one sub list and the elements
those are greater than pivot into one sub list by keeping the pivot in its original place.

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

26. Explain in brief a linked list.

A linked list is a dynamic data structure. It consists of a sequence of data elements and a
reference to the next record in the sequence. Stacks, queues, hash tables, linear
equations, prefix and post fix operations. The order of linked items is different that of
arrays. The insertion or deletion operations are constant in number.

27. Explain the types of linked lists.

The types of linked lists are:
Singly linked list: It has only head part and corresponding references to the next nodes.
Doubly linked list: A linked list which both head and tail parts, thus allowing the
traversal in bi-directional fashion. Except the first node, the head node refers to the
previous node.
Circular linked list: A linked list whose last node has reference to the first node.

28. What is sequential search? What is the average number of comparisons in a

sequential search?
Sequential search: Searching an element in an array, the search starts from the first
element till the last element.
The average number of comparisons in a sequential search is (N+1)/2 where N is the size
of the array. If the element is in the 1st position, the number of comparisons will be 1
and if the element is in the last position, the number of comparisons will be N.

29. What are binary search ?

Binary Search: Binary search is the process of locating an element in a sorted list. The
search starts by dividing the list into two parts. The algorithm compares the median
value. If the search element is less than the median value, the top list only will be
searched, after finding the middle element of that list. The process continues until the
element is found or the search in the top list is completed. The same process is continued
for the bottom list, until the element is found or the search in the bottom list is
completed. If an element is found that must be the median value.

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

The manipulation of Arithmetic expression, Symbol Table construction, Syntax analysis.

31. Whether Linked List is linear or Non-linear data structure?

According to Access strategies Linked list is a linear one. According to Storage Linked List is
a Non-linear one.

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

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

34. What is the difference between ARRAY and STACK?

STACK follows LIFO. Thus the item that is first entered would be the last removed.

In array the items can be entered or removed in any order. Basically each member access is
done using index. No strict order is to be followed here to remove a particular element.

35. What is Data Structure?

A data structure is a group of data elements grouped together under one name. These data
elements, known as members, can have different types and different lengths. Some are used
to store the data of same type and some are used to store different types of data.

36. Why do we Use a Multidimensional Array?

A multidimensional array can be useful to organize subgroups of data within an array. In
addition to organizing data stored in elements of an array, a multidimensional array can store
memory addresses of data in a pointer array and an array of pointers.
Multidimensional arrays are used to store information in a matrix form.
e.g. a railway timetable, schedule cannot be stored as a single dimensional array.
One can use a 3-D array for storing height, width and length of each room on each floor of a
building.

37. What method is used to place a value onto the top of a stack?
push() method, Push is the direction that data is being added to the stack. push() member
method places a value onto the top of a stack.

38. What method removes the value from the top of a stack?
The pop() member method removes the value from the top of a stack, which is then returned
by the pop() member method to the statement that calls the pop() member method.

39. What is a queue ?

A Queue is a sequential organization of data. A queue is a first in first out type of data
structure. An element is inserted at the last position and an element is always taken out from
the first position.

40. Which process places data at the back of the queue?

Enqueue is the process that places data at the back of the queue.

41. What does each entry in the Link List called?

Each entry in a linked list is called a node. Think of a node as an entry that has three sub
entries. One sub entry contains the data, which may be one attribute or many attributes.
Another points to the previous node, and the last points to the next node. When you enter a
new item on a linked list, you allocate the new node and then set the pointers to previous and
next nodes.

42. What is Linked List ?

Linked List is one of the fundamental data structures. It consists of a sequence of? nodes,
each containing arbitrary data fields and one or two (”links”) pointing to the next and/or
previous nodes. A linked list is a self-referential datatype because it contains a pointer or link
to another data of the same type. Linked lists permit insertion and removal of nodes at any
point in the list in constant time, but do not allow random access.
43. What are circular queues? Write down routines for inserting and deleting elements
from a circular queue implemented using arrays.
Circular queue: Static queues have a very big drawback that once the queue is FULL, even
though we delete few elements from the "front" and relieve some occupied space, we are not
able to add anymore elements as the "rear" has already reached the Queue's rear most
position. The solution lies in a queue in which the moment "rear" reaches its end; the "first"
element will become the queue's new "rear". This type of queue is known as circular queue
having a structure like this in which, once the Queue is full the "First" element of the Queue
becomes the "Rear" most element, if and only if the "Front" has moved forward;

44. What is a Binary Search Tree (BST)?

A binary search tree B is a binary tree each node of which satisfies the following conditions:
The value of the left-subtree of ‘x’ is less than the value at ‘x’
The value of the right-subtree of ‘x’ is greater than value at ‘x’
the left-subtree and right-subtree of binary search tree are again binary search tree.

45. Application of Queue

(i) Queue is used in time sharing system in which programs with the same priority form a
queue while waiting to be executed.
(ii) Queue is used for performing level order traversal of a binary tree and for performing
breadth first search at a graph.
(ii) Used in simulation related problem.
(iii) When jobs are submitted to a networked printer, they are arranged in order of arrival, ie.
Jobs are placed in a queue.

46. Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:
Trees reflect structural relationships in the data
Trees are used to represent hierarchies
Trees provide an efficient insertion and searching
Trees are very flexible data, allowing to move subtrees around with minimum effort

Following are the common uses of tree.

1. Manipulate hierarchical data.

2. Make information easy to search (see tree traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms
11.What is a header node in linked list?
Header node is a pointer variable of the structure type. This node contains the address of the
first node of the linked list. If this node contains NULL, then this shows that linked list is
empty. Header node is needed to keep track of the node of the linked list. This is a start node
for traversing, displaying, insertion, deletion.

What is a Node?
An individual part of a larger data structure
Nodes are a basic data structure which contain data and one or more links to other nodes.
Nodes can be used to represent a tree structure or a linked list. In such structures where nodes
are used, it is possible to traverse from one node to another node.