Q1 Explain two dimensional array?

 A two-dimensional array is a collection of elements and each

element is identified by a pair of indices called as subscripts.
 Represents the elements of two-dimensional array as rows
and columns.
 If a two-dimensional array has m rows and n columns then
the elements are accessed using two indices I and J, where
0<=I<=m-1 and 0<=J<=n-1. Thus the expression A[I][J]
represent an element present at Ith-row and Jth-column of
the array A
 The number of rows and columns in a matrix is called as the
order of the matrix and denoted as m x n

Q2) What are the 2 ways can represent a 2

dimensional array?

 Suppose A is the array of order m x n. To store m*n number of

elements, we need m*n memory locations. The elements should be in
contiguous memory locations.
 here are two methods:
1)Row-major order
2) Column-major order

Row-major order
 Let A be the array of order m x n. In row-major order, all the
first-row elements are stored in sequential memory locations
and then all the second-row elements are stored and so on.
 Base(A) is the address of the first element.
 The memory address of any element A[I][J] can be obtained
by the formula LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
 where W is the number of words per memory location.
Example: Consider the array of order 3 x 3.

Column-major order
 Let A be the array of order m x n.
 In column-major order, all the firstcolumn elements are
stored in sequential memory locations and then all the
second-column elements are stored and so on.
 Base(A) is the address of the first element.
 The memory address of any element A[I][J] can be obtained
by the formula LOC(A[I][J]) = Base(A) + W[(I-LB) + m(J-LB)]
where W is the number of words per memory location.
Example: Consider the array of order 3 x 3.
Example: Consider the array A of order 25 x 4 with base value 2000 and one
word per memory location. Find the address of A[12][3] in row-major order
and column-major order. Solution: Given Base(A) = 2000, m = 25, n = 4 LB = 0
W = 1, I = 12, J = 3
Row-major order:
LOC(A[I][J]) = Base(A) + W[n(I-LB) + (J-LB)]
LOC(A[12][3]) = 2000 + 1[4(12-0)+(3-0)]
= 2000 + 4(12) + 3
= 2000 + 48 + 3
= 2051
Column-major order:
LOC(A[I][J]) = Base(A) + W[ (I-LB) + m(J-LB)]
LOC(A[12][3]) = 2000 + 1[(12-0)+25(3-0)]
= 2000 + 1(12 + 75)
= 2000 + 87
= 2087

Q3) What are the Applications of Arrays?

1. Arrays are used to implement other data structures such as heaps, hash
tables, queues, stacks and strings etc
2. . 2. Arrays are used to implement mathematical vectors and matrices.
3. 3. Many databases include one-dimensional arrays whose elements are
records.
Q4) What are the advantages and Disadvantages of Arrays
Advantages of arrays
1. It is used to represent multiple data items of same type by using only single
name.
2. It can be used to implement other data structures like linked lists, stacks,
queues, trees, graphs etc.
3. Two-dimensional arrays are used to represent matrices.
Disadvantages of arrays
1. We must know in advance that how many elements are to be stored in
array.
2. Array is static structure. It means that array is of fixed size. The memory
which is allocated to array cannot be increased or reduced.
3. Since array is of fixed size, if we allocate more memory than requirement
then the memory space will be wasted. If we allocate less memory than
requirement, then it will create problem.
4. The elements of array are stored in consecutive memory locations. So
insertions and deletions are very difficult and time consuming.

Q5)Define Queue?
A queue is an ordered collection of items where an item is inserted at one
end called the “rear,” and an existing item is removed at the other end,
called the “front.” Queues maintain a FIFO ordering property.

. In the queue only two operations are allowed enqueue and

dequeue.
Enqueue means to insert an item into the back of the queue,
dequeue means removing the front item.

Q6) Explain different types of Queue?

Types of queues Queue can be of four types:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Dequeue (Double Ended queue)
Q7)What are the operations on QUEUE?Explain
The queue abstract data type is defined by the following structure and
operations. The queue operations are given below.
 Queue() creates a new queue that is empty. It needs no
parameters and returns an empty queue.
 enqueue(item) adds a new item to the rear of the queue. It needs
the item and returns nothing. This operation is generally called as
push.
 dequeue() removes the front item from the queue. It needs no
parameters and returns the item. The queue is modified. This
operation is generally called as pop
 isEmpty() tests to see whether the queue is empty. It needs no
parameters and returns a Boolean value.
 size() returns the number of items in the queue. It needs no
parameters and returns an integer
Q8)Explain Memory representation of queue using array
 Let QUEUE be a linear queue.
 Two pointer variables called FRONT and REAR are maintained.
 The pointer variable FRONT contains the location of the element to be
removed and the pointer variable REAR contains location of the last
element inserted.
 The condition FRONT = NULL indicates that the queue is empty and the
condition REAR = N indicates that the queue is full.

 Q9)Explain Memory representation of queue using linked list

 Memory representation of a queue using linked list Queues are also

represented using linked lists.
 In queues an item should be inserted from rear end and an item should
be removed from the front end.
 The pointer front contains location of the first node of the linked list
and another pointer rear contains location of the last node.
Q10)Write an algorithm to insert an element in the QUEUE
 Let QUEUE be the linear array consisting of N elements.
 FRONT is the pointer that contains the location of the element
to be deleted and REAR contains the location of the inserted
element.
 ITEM is the element to be inserted
Step 1: If REAR = N-1 Then [Check for overflow]
PRINT “Overflow”
Exit
Step 2: If FRONT = NULL Then [Check whether QUEUE is empty]
FRONT = 0 REAR = 0
Else REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

Q11) Write an algorithm to delete an element in the QUEUE

 Let QUEUE is the linear array consisting of N elements.
 FRONT is the pointer that contains the location of the element
to be deleted and REAR contains the location of the inserted
element.
 This algorithm deletes the element at FRONT position
.

Step 1: If FRONT = NULL Then [Check whether QUEUE is empty]

PRINT “Underflow”
Exit
Step 2 : ITEM = QUEUE[FRONT]
Step 3: If FRONT = REAR Then [If QUEUE has only one element]
FRONT = NULL
REAR = NULL
Else
FRONT = FRONT + 1 [Increment FRONT pointer]
Step 3: Return

Q12) Write any five applications of QUEUE

 Simulation
 Various features of operating system. [Operating systems often
maintain a queue of processes that are ready to execute or that are waiting
for a particular event to occur.]
 Multi-programming platform systems
 Different type of scheduling algorithm
 Round robin technique or Algorithm
 Printer server routines
 Various applications software is also based on queue data structure
 Operating systems often maintain a queue of processes that are
ready to execute or that are waiting for a particular event to occur

Q13) Define Linked List?

 A linked list is a linear collection of data elements called nodes
and the linear order is given by means of pointers.
 Each node contains two parts fields: the data and a reference to
the next node.
 The first part contains the information.
 The second part contains the address of the next node in the list.
This is also called the link field.

 The above picture is linked list with 4 with nodes, each node is
containing two parts.
 The left part of the node represents the information part of the
node and the right part represents the next pointer field that
contains the address of the next node.
 A pointer START gives the location of the first node.
 This pointer is also represented as HEAD.
 The link field of the last node contains NULL
Q13) What are the different types of Linked List?Explain
There are three types of linked lists.
 1.Singly linked list (SLL)
 2. Doubly linked list (DLL)
 3.Circular linked list (CLL)

 1.Singly linked list

 A singly linked list contains two fields in each node – the

data field and link field.

 The data field contains the data of that node while the link
field contains address of the next node.

 Since there is only one link field in each node, the linked list
is called as singly linked list.

 2. Circular linked lists

 In circular lists, if the link field of the last node contains
the address of the first node first node, such a linked list is
called as circular linked list.

 Doubly linked lists:

 It is a linked list in which each node is points both to the
next node and also to the previous node.
 In doubly linked list each node contains three parts –
FORW, BACK and INFO.
 BACK: It is a pointer field containing the address of the
previous node.
 FORW: It is a pointer field that contains the address of the
next node.
 INFO: It contains the actual data.

 In the first node, if BACK contains NULL, it indicates that it is the first node
in the list.
 The node in which FORW contains NULL indicates that the node is the last
node in the linked list.

Q14) What are the different operations on linked list?

The operations that are performed on linked lists are
1. Creating a linked list
2. Traversing a linked list
3. Inserting an item into a linked list
4. Deleting an item from the linked list
5. Searching an item in the linked list
6. Merging two or more linked lists
Q15) What is mean by a non- linear data structure?

 A non-linear data structure is a data structure in which a

data item is connected to several other data items, so that
a given data item has the possibility to reach one-or-more
data items.
 The data items in a non-linear data structure represent
hierarchical relationship
 Each data item is called a node
 Examples of non-linear datastructures are Graphs and
Trees.

Q16) What is a tree?

A tree is a data structure consisting of nodes organized as
a hierarchy .

Q17) Define nodes, root node leaf nodes,depth,height

and degree?
Nodes:- A node is a structure which may contain a value, a
condition, or represent a separate data structure
Root node:- The topmost node in a tree is called the
root node.
Leaf nodes:- Nodes that do not have any children are
called leaf nodes. They are also referred to as terminal
nodes.
Depth:- The depth of a node is the length of the path to its
root (i.e., its root path).
Height :- The height of a node is the length of the longest
downward path to a leaf from that node.
Degree:- The number of subtrees of a node is called
the degree of the node

Q18)What is a binary tree?

 A binary tree is a tree in which each node has at most two
descendants
 A binary tree consists of .
 node (called the root node) and
 left and right sub-t


 Q19)Define a complete tree?
 Tree in which each leaf is at the same distance from the
root. i.e. all the nodes have maximum two subtrees.
 Q20)Define a graph ? and its type?
A graph is a collection of nodes called vertices, and the
connections between them, called edges

 Undirected and directed graphs

 When the edges in a graph have a direction, the graph is
called a directed graph or digraph, and the edges are
called directed edges or arcs.
Neighbors and adjacency:-
A vertex that is the end point of an edge is called a neighbor of the vertex,
that is its starting-point.
The first vertex is said to be adjacent to the second.
The following diagram shows a graph with 5 vertices and 7 edges. The edges
between A and D and B and C are pairs that make a bidirectional connection,
represented here by a double-headed arrow