Data Structures Part – 4 | Kinnari Prakashan TPS

You can download Data Structures Part – 4 tps computer science class 12th pdf for free by click on download button given below.

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.

Q. 22 Explain the advantages of binary search algorithm with a suitable example. State any two disadvantages or limitations of binary search.

  Asked in Board Exam   (March 2007; Oct. 2003)     Important  

Ans : Advantages of binary search algorithm :

(1) Binary search algorithm is efficient as the search scope gets reduced to half the size of the array, with each iteration.

(2) The number of comparisons required are approximately equal to log2, n which are less than linear search.

(3) For example :
Given array data with 7-sorted elements :

11     22     30     33     40     44     55
	Suppose ITEM = 40

Step I: Initially BEG = 1 and END =7
	MID = (BEG + END) /2=(1+7)/2=4
	DATA [MID] = DATA [4] = 33

Step II: Since 33 < 40, BEG is changed as BEG = MID+1=4+1=5
	MID =(5+7)/2=6
	DATA [MID] = DATA [6] = 44

Step III: Since 44 > 40, END has its value changed by END = MID - 1 = 6 - 1 = 5


MID =(5+5)/2 = 5

DATA [MID] = DATA [5] = 40

ITEM found at location 5 in array. 

In above example, only two comparisons are required because at each iteration MID is calculated, only one half is checked.

In the same example, for linear search, 5 comparison are required.

Disadvantages :
1) The given list must be sorted.
2) The access of list must be random means the middle element can be accessed.
3) At each iteration, middle entry calculation is required.

---

Q 23. Write difference between Linear search and Binary search.

Ans : Linear Search

1. Linear search performs on unsorted list of elements as well as sorted list.

2. Compare the desired element with all elements in an array until the match is found.

3. Insertion of an element in an array can be performed very efficiently when array is not ordered.

4. For large size of array, time required for this search is very large.

5. Time complexity is as follows :
worst case : N comparison
Best Case : 1 comparison

Binary search

1. For binary search, the elements in array are stored in alphabetically or numerically in some manner.

2. Compare the value of midpoint with desire value. If the value is greater than midpoint value.the first half is checked, otherwise second half checked until search is successful or interval empty.

3. An insertion of a new element requires that many elements be physically moved to preserved order.

4. For large size of array, comparatively time required is less.

5. Time complexity as follows :
worst case : log, N comparison
Best case : 1 comparison

---

Q. 24 What are pointer arrays ?

  Asked in Board Exam   (Oct. 2003,06; Mar. 2011, 21)     Important  

Ans:

i) An array is called pointer array, if each element of that array is a pointer.

ii) The variable is called as pointer variable, if it points to ariother variable i.e. it contains memory address of other variable.

iii) Consider an organization, which divides its employee lisit into four groups, depending certain conditions. Following figure shows the list of 4 groups. There are 15 employes groups contain 2, 5, 4 and 4 employes respectively as

iv) If these groups are to be represented in memory, the most efficient way is to use 2 arrays.
The first is Employee array, which contains list of employees in all four groups sequentially, while the second array is Group array, which is a pointer array, which contains the starting address of each group in the Employee array, respectively.

v) It is shown in figure :

vi) Each element of Group array is a pointer, which holds the starting addresses of different groups. Hence,it is called as pointer array.

---

Q. 25 What is a record ?

  Asked in Board Exam   (March-2011)     Important  

Ans :
i) A record is a 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 record may contain non-homogeneous data i.e. data items of record need not to be of same data type. In a record, natural ordering of elements is not possible. The elements in record can be described by level number.

iv) e.g. An organization keeps records of its Employees. It contains following, data items-Name, gender, Salary, Birthday, Address.

Name is group item consisting of First name, Middle name and Last name. Also, Birth date
and Address are group items,

The structure of this record is shown in figure below.

1. Employee
   • Name
     • First Name
     • Middle Name
     • Last Name
   • Sex
   • Salary
   • Birth date
     • Date
     • Month
     • year
   • Address
     • City
     • Pincode

v) The number to the left of each variable indicates level number.
vi) Employee (30)
vii) This indicates a file of 30 records.

viii) To access first name of 3^rd employee, we should write Employee (3).Name.First name. In this way, we can access variables in records.

---

Q. 26 What is a record ? How it differs from a linear array ?

  Asked in Board Exam   (March 2002, 05, 07, 08,14,16; Oct.2010,11)     Important  

Ans : A record is a collection of fields or attributes i.e. relative data items.

Collection of data is frequently organized into hierarchy of fields i.e. records. A file is nothing
but collection of records.

Difference between records and linear arrays :

(i) A record is a collection of fields, while an array is list of homogeneous data elements.

(ii) A record may contain non-homogeneous data i.e. data elements may be of different data types.
An array always contains homogeneous data.

(iii) In a record, netural 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. 27 How records are represented in memory using array ?

  Asked in Board Exam  (Oct. 2002, March 2004)     Important  

Ans: i) Consider a record, whose structure is given below.

1. Employee
   • Name
     • First Name
     • Last Name
   • Sex
   • Address
     • City
     • Pincode
   • Phone Number

ii) To represent this record in memory, linear arrays are used.

iii) One separate linear array is used for each elementary item of record such as First name, Last name, gender, City, Pincode, Phone no.
Following figure shows representation of above record using parallel linear arrays.

iv) The records are stored in memory using parallel linear arrays, such that for an index K of all records, First name [K], Last name [K], Gender [K], …. belong to the same record in a file.(ie. K^th record in the file)

---

Q. 28 Show representation of records in memory considering suitable example of three records and three fields.

  Asked in Board Exam   (Mar. 2003,11,13; Oct.2011,13)     Important  

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 item. All the arrays should be parallel.

4) For eg.
A student file consisting three records and three fields.

Name      Address             Phone
Lokesh    11, J.M. Road       5662000 

---

Click on DOWNLOAD and Data Structures Part – 4 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