Data Structures Part – 1

Probable Marks in board exam: 17
Above probable marks means : In board exam questions asked form this chapter are nearly for 17 marks out of 50 Marks.

Scope of the Syllabus

• Introduction to data structures.
• Data structure operations.
• Algorithmic notations.
• Control structures.
• Arrays-Representation in memory, Traversing, Deleting, Sorting, Binary search in an array, Pointer arrays, Records in memory using array.
• Linked list – Representation in memory
• Trees, Binary trees – Representing binary tree in memory.

INTRODUCTION TO DATA STRUCTURES

Q.1 Define the following terms :

(i) Data:
Ans. Data are simply values or set of values.

(ii) Group items :
Ans. Data items which are divided into subitems are called as group items. e.g. Date may be divided into three subitems – day, month and year. So Date becomes group item.

(iii) Elementary items :
Ans. Data items which are not divided into subitems are called as elementary items. e.g. pincode number cannot be divided into subitems. So it is elementary item.

(iv) Entity :
Ans. An entity is something that has certain attributes or properties which may be assigned values.
The values themselves may be numeric or non-numeric.

e.g. A Bio-data sheet mainly contains :

  Asked in Board Exam   (March 2005, 2009,2016; Oct. 2007,2014)     Important  

(v) Field: Field is a single elementary unit of information representing an attribute of an entity.

  Asked in Board Exam   (March 2005, 2009,2016; Oct. 2007,2014)     Important  

(vi) Record: Record is a collection of field values of a given entity.

  Asked in Board Exam   (March 2005, 2009,2016; Oct. 2007,2014)     Important  

(vii) File : File is the collection of records of the entities in a given entity set.

---

Q. 2 What is a data structure ?

  Asked in Board Exam   (Mar. 2006,2015; Oct. 2002, 2004)     Important  

Ans : i) Data may be organized in many different ways. Data structure is the way: in which different data elements are logically related.

ii) Collection of data elements forming an organisation characterized by the accessing functions is called data structure.

iii) The data structure should be simple and it should show the relationship between data elements.

iv) Types:
(i) Linear data structure (ii) Non-linear data structure.

In linear data structure, data elements are stored in consecutive memory locations or by using linked representation. e.g. arrays, linked list.

In non-linear data structures, the linear order cannot be maintained between data elements Generally data elements have hierarchical relationship between them. e.g. trees

v) Computer language provides different data structures like arrays, stack, queue, tree etc.

---

Data Structure Operations

Q. 3 Explain in brief any six data structure operations.

  Asked in Board Exam   (Oct. 2002,04,06,12,15; Mar. 2002,06,12)    Important  

Ans. : The data appearing in data structures are processed by means of certain operations like :
(i) Traversing :

Accessing, each record or element exactly once, so that it can be processed is called traversing.
For e.g: multiplying each element of an array by 6.

(ii) Inserting :
Adding a new record to the existing structure is called as inserting.

(iii) Deleting :
Removing a record from the existing structure is called as deleting.

(iv) Searching :
Finding the location of a record with given key values or finding the locations of all records which satisfy one or more conditions is called as searching.

(v) Sorting :
Arranging records in some logical order is called as sorting.

(vi) Merging :
Merging means combining the records in two different sorted files into a single sorted file.

Algorithmic Notation

Q. 4. What is an algorithm?

Ans. :
i) An algorithm is a finite step by step list of well-defined instructions for solving a particular problem.

ii) An algorithm consists of two parts :
(a) First part is a paragraph which tells the purpose of algorithm. In this part, we define variables in algorithm and lists the input data.

(b) The second part of algorithm consists of steps in algorithm that are executed one after the another, generally beginning with step 1, unless stated otherwise. The control
can be transferred to step n, by the statement “go to step n”.
The algorithm is completed, when the statement ‘Exit’ or ‘Stop’ is encountered.

iii) e.g. Algorithm to find largest element in array.
Largest [DATA, N, MAX]
Here, DATA is a linear array with N elements. This algorithm finds the largest element
MAX of DATA.

Step 1: [Initialize counter]
	set k: = 1 and Max: = DATA [1]

Step 2: [Compare and Update]
	If MAX < DATA [k + 1],
	then : MAX: = DATA [k + 1]
	[End of If structure]

Step 3: [Increment counter] set k: = k + 1

Step 4: [Test counter] If k < N, then : go to step 2
	[End of If structure]

Step 5: Write MAX

Step 6: Exit

---

Q.5 Describe sequence logic or sequential flow.

Ans :
i) In the sequence logic, modules are executed sequentially, one after the another.

ii) The Sequence may be present explicitly by means of numbered step or by the order in which modules are written.

iii) In short in sequential logic or sequential flow, modules of an algorithm are executed one after the another.

---

Q.6 Describe conditional flow or selection logic.

Ans : Selection logic uses number of conditions, which cause selection of one out of several alternative modules. The structure which implement this type of logic is known as selection logic, or conditional structure:

There are three types of conditional structures :

(i) Single alternative :
This has the form :

If condition, then :
   [module A]
[End of If structure]

The logic of this structure is as follows : If condition is satisfied (true) then module A, which consists of number of statements, is executed. Otherwise, module A is skipped and next module of algorithm is executed.

ii) Double alternative :
This structure has the form :

If condition, then :
     [module A]
Else :
    [module B]

[End of If structure]

The logic of this structure is as follows
If the condition is satisfied, then module A will be executed otherwise module B will be executed.

(iii) Multiple alternative :
This structure has the form :

    If condition (1), then :
     [module A1]

    else if condition (2), then :
     [module A2]

    else if condition (n), then :
     [module An]

    else :
     [module B]

    [End of If structure] 
  

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 condition is satisfied, then the module, which follows last Else statement will be executed.

---

Q. 7 Describe logic of Repeat-For loop.

Ans. : The repeat-for loop has the form :

Repeat for K=R ToS by T:
      [module]
[End of For loop] 

Here, K is called index variable, R and S are initial and final values of K and T is increment.
The logic of this structure is as follows :

At first, the body of loop i.e. module will be executed with K = R and then with K = R + T, then with K = R + 2T and so on, until K <= S. The loop ends when K > S. If T is negative then K decreases in value and loop ends when K < S.

---

Click on DOWNLOAD and Data Structures Part - 1 pdf will start downloading.

Important Links

Data Structures Part - 1

Data Structures Part - 2

Data Structures Part - 3

Data Structures Part - 4

Data Structures Part - 5

Data Structures Part - 6

Data Structures Part - 7

Data Structures Part - MCQ