Data Structure

Q. 1: Define the following terms.

Ans : 1) Data : Data are simply values or set of values
2) Group Items : Items that are divided into subitems is called group items.
e.g. Date may be divided into three subitems
Date
Day Month Year

3) Elementary items : Items which are not divided into subitems are called a
elementary items.
e.g. Pincode number cannot be divided into subitems.
4) Entity : An entity is something that has certain attributes or
properties which may be assingned values.
Bio -Data
Name Age Address Education
Amar 25 Delhi B.A.
Nisha 30 Nagpur [Link].

5) Field : Field is a single elementary item of information an attribute of

an entity.
6) Record : Record is collection of field values of a given entity.
7) File : File is a collection of records in a given entity set.

Q. 2: What is data structure ?

Ans : i) Data may be organised in many different ways. It is way in which data elements are logically
related.
ii) Data stucture is defined as collection of elements forming an organization characterrised by
accessing function.
iii) Types of data structure
1) Linear data structure : In this case data are stored in consecutive memory location by using
linked allocation method.
2) Non-Linear data structure : In this case linear order can not be maintained between data
elements. Data elements hirarchical relationship between them.
3) Computer languages provides different data structure like queue,stack,array and tree etc.

1..
Q. 3 : What are the different data structure operations :
Ans : 1) Traversing : Accessing each record or element exactly once, so that it can be
processed is called traversing.
2) Inserting : Adding new record to the existing data structure is called inserting.
3) Deleting : Removing a record from the existing data structure is called deleting.
4) Searching : Finding the location of record with given values is called searching.
5) Sorting : Arranging records in some logical order is called sorting.
i.e Ascending or descending
6) Merging : Merging means combining the records in two different files to form
a single file.

Q. 4 : Explain the following terms .

Ans : 1) Sequence logic or sequential flow :

>
i) In theis logic modules can be executed one after another.
Module A
ii)The sequence may be present by means of numberd step.

>
Module A

>
Module A

>
2) Conditional Flow or Selection logic :
i) This logic depends on condition.
ii) Select one out of several alternative module.
>

iii) There are three types of condition logic : if No

condition >
i) Single alternative : ?
This has the form
If (condition) Yes
>

>

module A Module A
End of if structure
If a condition is satisfied then module A will
>

>
execute, otherwise module A will skipped.
>

2..
 ii) Double alternative :
If (condition)

>
module A if
else condition >
?
module B

>
( End of If statement) Yes

>
If a condition is satisfied then module A
Module A Module A
will execute, otherwise module B will
execute.

>

>
>

>
iii) Multiple alternatives :
If(condition 1) , then :
module A
else if (condition 2) , then :
module 2
.
.
.
elseif (contition n), then :
module An
else
module B
( End of if statement)

The logic of this structure allows only one module to be executed. The module following
the condition which is satisfied the condition will be executed. If no conditionis satisfied then
the module which follows last else statetment will execute.

>
>

3) Repetative flow OR Iteration Logic :

No
Here certain module is executed repeatedly condition >
until condition satisfy. ?
Yes
>

>
>

module
> >

>
>
3..
Q. 5 : What is linear array ?
Ans : 1) A linear array is group or set of finite elements having same type of data i.e homogeneous.
2) All the elements in a array are stored on consecutive memory location.
3) The number of elements in a array is called length of the array.
4) The first element of array is called lower bound and last element of array is called
upper bound.

Q. 6 : Waht is traversing of an array ? Give the algorithm for traversing of an array .

Ans : Algorithm :
Suppose LA is the linear array.
The first element is lower bound i.e LB and the last element is upper bound i.e. UB.
Step 1 : Initialize counter set k = LB
Step 2 : Repeat step 3 and 4 while k < = UB
Step 3 : Visit element
Step 4 : Increment counter set k=k+1
step 5 : Exit

Q. 7 : What is inserting ? Write algorithm for inserting element into linear array.
Ans : Algorithm
INSERT(A , N , K , Item)
Here A- is Linear array
N - Number of elements of array
K- is positive integer such that K<N
Item - is to be inserted at K position
Step 1 : Initialize counter Set J=N
Step 2 : Repeat step 3 and 4 while J>=K
Step 3 : Move element forward Set A [ J + 1 ] = A[ J ]
Step 4 : Decrement counter Set J=J-1
Step 5 : Insert the element Set A [ K ] = Item
Step 6 : Reset N Set N=N+1
Step 7 : Exit

4..
Q. 8 : What is deleting ? Write algorithm for deleting elemet into linear array.
Ans : Algorithm
DELETE(A , N , K , Item)
Here A- is Linear array
N - Number of elements of array
K- is positive integer such that K = N
Item - is to be deleted from A at K position
Step 1 : item = a [ K ]
Step 2 : Repeat for J = K to N - 1
Move [ J + 1 ] element backward
set A [J ] = A[ J + 1 ]
Step 3 : Reset N Set N=N-1
Step 7 : Exit
Q. 9 : Write algorithm for linear search.
Ans : Linear ( A , N , Ietm , LOC)
Here A- is Linear aray
N- is number of elements in array
Item : the elemenet is to be find out.
LOC - means the location of search item
Step 1 : Insert item at the end of the A. Set A [ N + 1 ] = Item
Step 2 : Initialize Counter Set LOC = 1
Step 3 : Search for item
Repeat while A [ LOC ] item Set LOC = LOC + 1
End of Loop
Step 4 : If LOC = N + 1
then Set LOC = 0
Sep 5 : Exit

5..
Ex. Given A array with five elements.

11 22 33 44 55

Item to be find out is 33

Step 1 : set A(6) = 33

Step 2 : LOC = 1

Srep 3 : Since A[1]= 11 ‘Š 33 so LOC =2

Since A[2] 22 ‘Š 33 so LOC=3

Here a[ 3 ] = 33 = 33 i.e. Item

Step 4 : Hence Item 33 is found at the LOC = 3

Q. 10 : Write algorithm for binary search.

Ans : Linear ( A , LB , UB Item , LOC )
Here A- is sorted array
LB - Lower Bound
UB - Upper Bound
Item - is searched item
BEG denotes begining MID denoted middle and END denotes end.
LOC - Location of the searched item
Step 1 : Intialize variable
Set BEG = LB , END = UB and MID = (( BEG + END ) /2)
Step 2 : Repeat step 3 an 4
while BEG = END and A [ MID ] Item
Step 3 : if Item < A [ MID ] then
set END = MID - 1
Else
BEG = MID + 1
Step 4 : Set MID = (( BEG + END ) /2)
Step 5 : if A [MID ] = Item
Set LOC = MID
Else
LOC =NULL
Step 6 : Exit

6..
Q. 11 : Write algorithm for bubble sort.
Ans : Algorithm
Bubble Sort ( A , N )
Here A- is Linear array
N- Number of elements in array.
The algorithm sort the given element in ascending order.
Step 1 : Repeat step 3 and 4 K = 1 to N - 1
Step 2 : Set P =1
Step 3 : Repeat while P <= N - K
if A[ P ] > A [ P + 1 ] then Interchange
Increment pointer
Set P=P+ 1
Step 4 : Exit

Q. 12 : Write difference between Linear search and Binary Search

Ans :
Linear Search Binary Search
1. Linear search performs on unsorted list of 1. For binary search, the elements in array
elements as well as sorted list. are sorted in alphabetically or numerically
in sorted manner.
2. Compare the desired elements with all elements 2. Commpare the value of midpoint with
in an array until the match is found. desired [Link] the value is greater than
3. Insertion of an elements in an arry can be per midpoint value the first half is checked,
formed very efficiently array is not ordered. otherwise second half is checked until
4. For large size of array, time required for this search is successful or interval is empty.
search is very large. [Link] insertion of a new element requires that
5. Time complexity is as follows: many elements be physically moved to
worst case: N comparison preserved order.
4. For large size of array,comparatively time
required is less.
5. Time complexity is as follows:
worst case: log2 N comparison

7..
Q. 13 : What is pointer array ?
Ans : 1) An array is called pointer array , if each element of that array is a pointer.
2) The variable is called as pointer variable , i.e it contains the address of the another variable.

Group 1 Group 2 Group 3 Group 4

Rani Ramesh Sagar Dilip

Ashish Priya Rupali Rita

Megha Devaand Yogesh

Mahesh Deepak

Ram

1 Rani <
2 Ashish
Group 1
3 Megha

4 Ramesh <
Group - Pointer array
5 Priya
Group 2
6 Devaand 1 1

7 Mahesh 4 2

8 Sagar < 8 3

9 Rupali 13 4

Group 3 10 Yogesh

11 Deepak

12 Ram

13 Dilip <
Group 4
14 Rita

3) Each element of group array is pointer, which holds the starting address of different groups.
Hence it is called as pointer array.

8..
Q.14 : What is record ?
Ans. : i) A record is collection of relative data items, each of which is called as field or attribute.
ii) Collection of records is known as files. Collection of data is frequently organized into a
hierarchy of fields, records and files.
iii) A records may contain non-homogneous data i.e. data iteams of record need not to be of
same data type. In a record, natural ordering of elements is not possible. The elements record
can be described by level number.
iv) e.g. An organization keeps records of its [Link] contains following data items.
Nams, Sex, Salary, Birthday, Address.
Name is group item consisting of First name, Middle name and Last name. Also, Birthdate and
address are group items.
The structure of this record is shown in figure below:
1. Employee
2. Name
3. First name
3. Middle name
3. Last name
2. Sex
2. Salary
2. Birth date
3. Date
3. Month
3. Year
2. Address
3. City
3. Pincode
v) The number to the left of each variable indicates level number.
vi) Employee (30)
This indicates a file of 30 records.
Q. 15 : What is a record ? How it differs from a linear array ?
Ans.: A record is collection of fields or attributes i.e. relative data items. Collection of data is
frequency orgnized into hierarchy of fields i.e. records.A file is nothing but Collection of records.

9..
 Difference between records and linear arrays :
i) A records is a collection of fields, while an array is list of homogeneous data elements.
ii) A record may contain non-homogeneous data.
iii) In a record, nature ordering of elements is not possible. Array elements can be naturally
ordered.
iv) Elements of record are referenced by level number, while those of array can be referenced
by an index set consisting of n consecutive numbers.

Q. 16 : Show representation of records in memory considering suitable example of three

records and three fields.
Ans. : 1) Records contain non-homogeneous data, so it cannot be stored in array.
2) But in entire file of records, all data elements belonging to the same identifier will be of same
type. So a file may be stored in memory as collection of arrays.
3) One array for each of data items. All the arrays should be parallel.
4) For e.g.
A student file consisting three records and three fields.
Name Address Phone
Lokesh 11, J.M. Road 5662000
Jayesh 24, M.G. Road 4240020
Anushka 10, Sahkarnagar 4261900

Following figure show of above file in three parallel array Name, Address and Phone :

Name Address Phone

Lokesh 11, J.M. Road 5662000
Jayesh 24, M.G. Road 4240020
Anushka 10, Sahkarnagar 4261900

Q. 17 : What are linked lists ? Show a liked list with suitable example having six nodes with a
properly labelled diagram.
OR
With suitable example, show labelled diagram for link between two nodes having the
information part and next pointer field.
Ans. : i) A Linked list is a linkear collection of data elements, called nodes, where the linear order is
maintained with the help of pointers.

10..
 ii) Linked list is also called as one-way list.
iii) Each node in the linked list is divided into two parts. First part is called as INFO part,
which contain the information about the elements or actual elements and second part is
called as LINK part, which is next pointers fields i.e. it contains the address of next node in the
list.

START
10
INFO LINK NULL POINTER

>
>

>
> A 13 > B 19 > C 14 > D 12 > E 18 > F X
10 13 19 14 12 18

a) The above figure shows a liked list having six nodes.

b) The left part of the node is the Info part, which contains information of elements, while the
right part is Link part, which of next pointers field i.e. it points to next node.
c) An arrow is drawn from link part of one node to the next node to next list.
d) The address of the list is stored in start or Name of the list
e) The Link part of last node is null pointer i.e. it contains nothing.
f) To trace the linked list, we just requir the address of start or Name.

Q. 18 : What are the advantages of linked list over linear array.

OR
Explain the diference between linked list and linear array.
Ans :

ARRAY LINKED LIST

1) To store element consecutive memory 1) To store element consecutive memory
location is required. location is not required.
2) It cannot be easily extended. 2) It can be easily extended.
3) Insert an element is very complecated. 3) Element can be inserted easily
4) Deletion of an element is very complecated. 4) Element can be easily deleted .
5) It is very dificult to implemeted and 5) It can be easily implemeted and maintained.
maintained.

11..
Q. 18 : How linked lists are represent in memory ? OR
With suitable diagram show the representation of linked in memory.
Ans : 1) Linked list can be represented in memory by using two arrays respectively known as INFO
and LINK.
2) The list also requires a varible Name or Start wnich contain address of first node.

A 9 B 4 C 1 D 6 E

INFO LINK
5 D 6
1
2
3
4 C 1
> 5 A 9
6 E
7
8
9 B 4

Q. 19 : Explain stack and queue with suitable example. OR

Explain LIFO and FIFO system with suitable example.

Ans : LIFO system OR Stack

1) LIFO stands for Last In First Out system.

2) In this system the element which is inserted last will be deleted first.

3) It is a linear system in which insertion and deletion taking place from one end only i.e.
top of the list.

4) The insertion operation is referred as PUSH and deletion operation is referred as

POP.

5) Ex. Stack of dishes

12..
 FIFO system OR Queue

1) FIFO stands for First In First Out system.

2) In this system the element which is inserted first will be deleted first.

3) It is a linear system in which insertion taking place from one end called rare end and
deletion taking place from another end called front end.

4) Ex. A Queue for tickets in a cinema hall.

Q. 20 : What is tree ?

Ans : 1) Tree is hierarchical or Non linear data structure which consists of finite set of one or
more nodes.
A
Define the following terms.

1) Root : B C

The first node of the tree or the node

D E F G H
which has no parent is called as root node.
I J K
In the given figure “A” is the root node.

2) Leaf :

The node having no child or children. Such node have degree zero. This node is also
called as terminal node.

In the given fig. D, I, F, J, K are leaf node.

3) Child :

The node which is reachable from another node is called child.

In the given fig. B and C are th child of A. D and E are child of B.

4) Sibling :

Children of the same parent is called sibling.

In the given fig. the nodes D and E are the child of B so D and E are sibling.

5) Level of tree :

1) Each node in a tree is assigned a level number. Level 0

A
2) Generally the level number of root node is zero .
Level 2
B C
3) The level number of child node is one
F G Level 1
D E
more than the level number of its parent.

13..
6) Depth or Height of tree:

1) It is defined as maximum level of any node in a tree.

2) If root is level zero then depth or height of tree is equal to

1 + largest level number.

7) Degree of Node :

1) The maximum number of nodes attached with that perticular node.

NODE DEGREE

A 3 A

B 2 B C

C 3 D F G G
E
D,E,F,G 0

7) Degree of a tree :

1) The degree of a tree is the maximum degree of the node in tree.

Node Degree

A 2 A

B 2 B C
C 3 F G
D E G
D, E, F, G, H 0

The tree has degree 3

8) Complete Binary Tree

If all leaf nodes of a binary tree have same level number and every non leaf node
has non empty left and right subtree then the tree is called complete binary tree.

9) Extended binary tree or 2 tree

1) A binary tree T is said to be a 2 tree or an extended binary tree if each node N has
either 0 or 2 children.

2) A node with 2 children are called internal nodes and the node with 0 children are
called external node.

14..
 MCQ’s
1) An array is a collection of ________data element.
a) Homogeneous b) Non-homogeneous c) Linear d) Non - linear
Ans : a) Homogeneous
2) A record is collection of ______ data elemets.
a) Homogeneous b) Non-homogeneous c) Linear d) Non - linear
Ans : b) Non-homogeneous
3) Tree is ______ data structure.
a) a) Homogeneous b) Non-homogeneous c) Linear d) Non - linear
Ans : d) Non - linear
4) Linked list is ______ data structure.
a) Homogeneous b) Non-homogeneous c) Linear d) Non - linear
Ans : c) Linear
5) The principle of stack is ______.
a) FIFO b) LIFO c) FILO d) LOFI
Ans : b) LIFO
6) The principle of queue is ______.
a) FIFO b) LIFO c) FILO d) LOFI
Ans : a) FIFO
7) A record is a collection of ______.
a) Fields b) Files c) Arrays d) Maps
Ans : a) Fields
8) Maximum number of nodes in a binary tree with depth ‘n’ are
a) 2n b) n c) Log2n d) 2n-1
Ans : d) 2n-1
9) Accessing the elements of records in an array only once is called _____.
a) Searching b) Sorting c) Traversing d) Deleting
Ans : c) Traversing
10) Finding the location of given elemnts is called as _____.
a) Searching b) Sorting c) Traversing d) Deleting
Ans : a) Searching
11) Data items that are divided into subitems is called as ____
a) Group Items b) Elementary Items c) Nodes d) None
Ans : a) Group Items
12) 11) Data items that are not divided into subitems is called as ____
a) Group Items b) Elementary Items c) Nodes d) None
Ans : b) Elementary Items
13) The time required to execute bubble sort algorithm having ‘n’ inputs items is directly proportional to
______
a) n2 b) n c) Log2n d) Logen2
Ans : a) n2
14) Maximum number of nodes in a binary tree with depth 5 are
a) 5 b) 31 c) 32 d) 25
Ans : b) 31
15) Maximum number of nodes in a binary tree with depth 6 are
a) 64 b) 63 c) 65 d) 36
Ans : b) 63
15..
16) Maximum number of nodes in a binary tree with depth 4 are
a) 4 b) 15 c) 16 d) 5
Ans : b) 15
17) In _____ data strcture an elemets may be inserted or deleted only at one end called top.
a) Queue b) Array c) Tree d) Stack
Ans : d) Stack
18) To arrange the given elemnts in some logical order is called as____
a) Searching b) Sorting d) Combining d) Deleting
Ans : b) Sorting
19) The most efficient search algotithm is _____
a) Binary search b) REverse search
c) Linear search d) Pointer search
Ans : a) Binary search
20) ______ data structure does not require contiguous memory location.
a) Array b) String c) Pointer array d) Linked List
Ans : d) Linked List
21) Tree is a ___________collection of nodes.
a) Hierarchical b) Linear c) Relational d) Graphical
Ans : a) Hierarchical
22) ______ is very useful in situation when data is to be stored and retrived in reverse order.
a) Stack b) Queue c) Linked List d) Tree
Ans : a) Stack
23) _____is the operation of rearranging the elements of an array either in increasing or decreasing
order.
a) Sorting b) Searching c) DMS d) DBMS
Ans : a) Sorting
24) Sorted list is essential requirement for _______ process of an array.
a) Linear search b) Binary search c) Traversing d) Insertion
Ans : b) Binary search
25) Maximum number of nodes of symmetric binary tree with depth 7 are
a) 125 b) 127 c) 128 d) 124
Ans : b) 127
26) _____is the only non linear data structure from the following.
a) Array b) Stack c) Tree d) Linked List
Ans : c) Tree
27) The number of comparisons required for bubble sortingof an array of n elements is _____
a) n(n-1)/2 b) n/2 c) Log2n d) Log10n
Ans : a) n(n-1)/2

16..