Data structure

3-Marks Questions

1. How are data structure classified.

Data structure

Primitive data structure Non primitive data structure

integer
float Arrays list Files
pointer one dimensional
reference
Two dimensional linear datastructure Non linear datastructure
Stacks Tree
Multi-dimensional queues graphs
Linked list

2. Mention the various operations performed on data structure

Traversing: The process of accessing each data item exactly once to perform some
operation is called traversing.
Insertion: The process of adding a new data item into the given collection of data item is
called insertion.
Deletion: The process of removing an existing data item from the given collection of data
items is called deletion.
3.How are arrays classified?
Arrays can be classified as three types:
a. One-dimensional arrays
b. Two dimensional arrays
c. Multidimensional arrays

4.Justify the need for using arrays.

An array is a collection of homogeneous elements with unique name and the elements are
arranged one after another in adjacent memory location. The data items in an array are
called as elements. These elements are accessed by numbers called as subscripts or indices.
Since the elements are accessed using subscripts, arrays are also called as subscripted
variables.

5.Mention various operations performed on arrays. (Any three)

Traversing: The process of accessing each data item exactly once to perform some
operation is called traversing.
Insertion: The process of adding a new data item into the given collection of data item is
called insertion.
Deletion: The process of removing an existing data item from the given collection of
data items is called deletion.
Searching: The process of finding the location of a data item in the given collection of
data items is called searching.
Soring: The process of arranging the data items in ascending or descending order is
called sorting.
Merging: The process of combining the data items of two structures to form a single
structure is called merging.

6.How do you find the length of an array?

An array is an ordered collection of elements of same type and same name. Arrays can
store an element in consecutive locations with same data type.
The length of an array can be calculated as:
L=UB-LB+1
Here UB→Upper bound (Largest index).
LB→Lower bound (Smallest index).
Ex: If an array A contains an elements 10,20,30,40,50 can be represented as
A[0] A[1] A[2] A[3] A[4]
10 20 30 40 50

The length of an array L = 4 – 0 + 1 = 5

7. Explain the memory representation of one dimensional array.

Elements of array are stored in consecutive memory locations.
Let P be the location of element. Let Base(A) is an address of the element in an
array is called base address of A.
Then address of any element can be calculated as:
Loc(A[P]) = Base(A) + W(P - LB)
Here W→The number of words per memory cell.
LB→Lower bound.
Ex: int a[5]={10,20,30,40,50};

Memory representation of this array is:

1000 1001 1002 1003 1004

10 20 30 40 50
a[0] a[1] a[2] a[3] a[4]
The address of a[3] can be calculated as:
Loc(a[3])= Base(A) + W(P - LB ) =1000 + 1(3 - 0)=1003.

8. Write the memory representation arrays in 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) + J]
Where W is the number of words per memory location.
Ex: Consider the array of order 3 x 3.

[0] [1] [2]

a[0] 10 20 30
a[1] 40 50 60
a[2] 70 80 90
Row-major order:
1001 10 a[0][0]
1002 20 a[0][1]
1003 30 a[0][2]
1004 40 a[1][0]
1005 50 a[1][1]
1006 60 a[1][2]
1007 70 a[2][0]
1008 80 a[2][1]
1009 90 a[2][2]
9.Write the memory representation arrays in column-major order.
Let A be the array of order m x n. In column-major order, all the first column 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+ m(J)]
Where W is the number of words per memory location.
Ex: Consider the array of order 3 x 3.
Ex: Consider the array of order 3 x 3.

[0] [1] [2]

a[0] 10 20 30
a[1] 40 50 60
a[2] 70 80 90

Column -major order:

1001 10 a[0][0]
1002 40 a[1][0]
1003 70 a[2][0]
1004 20 a[0][1]
1005 50 a[1][1]
1006 80 a[2][1]
1007 30 a[0][2]
1008 60 a[1][2]
1009 90 a[2][2]
10. Consider the array A of order 20 x 5 with base value 1000 and one word per
memory location. Find the address of A[10][4] in row-major order and column-
major order.
Given Base(A) = 1000, m = 20, n = 5 LB = 0,W = 1, I = 10, J = 4
Row-major order: LOC(A[I][J]) = Base(A) + W[n(I) + (J-LB)]
LOC(A[10][5]) = 1000 + 1[5(10)+4]
= 1000 + 5(10) + 4
= 1000 + 50 + 4
= 1054

Column-major order: LOC(A[I][J]) = Base(A) + W[ I + m(J)]

LOC(A[10][5]) = 1000 + 1[10+20(4)]
= 1000 + 1(10 + 80)
= 1000 +90
= 1090

11. 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) Arrays are used to implement mathematical vectors and matrices.
3) Many databases include one-dimensional arrays whose elements are records.

12. What are the advantages of arrays?

a) It is used to represent multiple data items of same type by using only single name.
b) It can be used to implement other data structures like linked lists, stacks, queues,
trees, graphs etc.
c) Two-dimensional arrays are used to represent matrices.

13. What are the disadvantages of arrays?

a) We must know in advance that how many elements are to be stored in array.
b) Array is static structure. It means that array is of fixed size. The memory which is
allocated to array cannot be increased or reduced.
c) The elements of array are stored in consecutive memory locations. So,
insertions and deletions are very difficult and time consuming.

14. What is stack? Mention the types of operations performed on the stack.
A stack is an ordered collection of items where the addition of new items and the
removal of an existing item always take place at the same end called TOP.
Operations performed on the stack: Stack( ),Push( ),Pop( ),Peek( ),isEmpty( ) ,Size( )
15. Explain the memory representation of a stack using one dimensional array.
A stack is an ordered collection of items where the addition of new items and the
removal of existing items always take place at the same end called TOP.

Stack can be represented using one dimensional array. The items of stack are stored
in a sequential order from the first location of the memory block.
A pointer TOP contains the location of the top element of the stack.

The condition TOP= MAXSTK indicates the stack is full & it represents the
situation is called overflow.

The condition TOP=NULL indicates the stack is empty & it represents the
situation is called underflow.

10 20

20 20
10 10 10
Empty stack 20 will be removed first

16. Write any three applications of stacks.

1) The simplest application of a stack is to reverse a word.
2) Another application is an “undo” mechanism in text editors.
3) Conversion of decimal number into binary.

17. What is queue? Mention the various operations performed on the

queue.
A queue is an ordered collection of items where an item is inserted at one end called
“REAR” & an existing item is removed from other end called “FRONT”.
Operations performed on the queue: queue( ),enqueue( ),Dequeue( ),isEmpty( ),Size( )

18. Explain the memory representation of queue using one dimensional

array.
A queue is an ordered collection of items where an item is inserted at one end called
“REAR” & an existing item is removed from other end called “FRONT”.
The condition REAR=N indicates that the queue is full.
The condition FRONT=NULL indicates that the queue is empty.
Front Rear

10 20 30
0 1 2 3 4

19. Write any three applications of queues.

a) Simulation
b) Various features of operating system.
c) Multi-programming platform systems
d) Different type of scheduling algorithm
e) Round robin technique

20. Define the following with respect to binary tree

Root Subtree Depth
Root: Top most node in the tree is called root.
Subtree: A tree T is a tree contains a node in T & all of its descendents in T.
Depth: The length of the path to its root is called depth of tree.

21. Write an algorithm for traversal in a linear array.

Let A is a linear array with LB & UB as lower bound & upper bound.
Step 1: for LOC=LB to UB do
Process A[LOC] End For
Step 2: Exit