You can download Data Structures Part – 3 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. 16 What is deleting ? Write an algorithm for deletion of an element from an array.
Ans :
i) Deleting means removing an element from the existing elements of an array.
ii) Deletion at the end of an array is easier. But, if to delete an element from mid of array. then to move the elements of array one location upward.
iii) Algorithm : DELETE (LA, N, K, ITEM)
Here LA is a linear array with N elements and K is . a positive be Mean integer, 2 such that K = N. This algorithm deletes Kth element from LA and assigns it i M. to variable ITEM
Step 1: Set ITEM := LA[K] Step 2: Repeat For J = K to N - 1: [Move (J + 1)ˢᵗ element backward] Set LA[J] := LA[J + 1] [End of loop] Step 3: [Reset number Nof elements in [LA] Set N := N - 1 Step 4: Exit
Q.17 Suppose a company keeps a linear array year, such that year [K] contains number of employees in year K. Write a module for each of the following tasks
(a) To print each of the years in which no employee was born.
(b) To find the number N of years in which no employee was born.
(c) To find the number NL of employees, who will be atleast L years old at the end of year 1984.
Linear array year contain elements from 1920 to 1970.
Ans :
(a) To print each of the years in which no employee was born.
1. Repeat for K := 1920 to 1970: if year [K] = 0, then: write : K [End of If structure] [End of loop] 2. Exit
(b) To find number N of years, in which no employee was born.
1. Set N := 0 2. Repeat for K = 1920 To 1970 : If year [K] = 0, then: N := N+1 [End of If structure] [End of loop] 3. Write : N 4. Exit
(c) To find number of employees NL, who will be at least L years old at the end of year 1984 we want the number of employees born in ye ar 1984-L, or earlier.
1. Set NL = 0 2. Set X := 1984 - L 3. Repeat For K = 1920 To X : Set NL := NL + year [K] [End of loop] 4. Write : NL 5. Exit
Q. 18 Explain Bubble sort algorithm with suitable example.
Ans:
Algorithm :
Bubble Sort (DATA, N)
Here DATA is a linear array with N elements. This algorithm sorts elements of DATA in
ascending order.
Step 1: Repeat steps 2 and 3 for K :=1 To N-1: Step 2: Set Ptr := 1 Step 3: Repeat While Ptr <= N-K: (a) If DATA [Ptr] > DATA [Ptr + 1], then interchange DATA [Ptr] and DATA [Ptr + 1] [End of lf structure] (b) [increment pointer] Set ptr = pir+1 [End of inner loop] [End of outer loop] Step 4: Exit
Explanation :
Suppose DATA is an array of N elements. Sorting these elements in ascending order means arranging the elements such that :
DATA [1] < = DATA [2] <= …. <= DATA [N] In Bubble sort, compare DATA[1] with DATA[2]} and exchange them it DATA[1] > DATA[2].
Next DATA[2] is compare with DATA[3]. They are exchanged if necessary. This process is
repeated till DATA [N – 1] is compared with DATA[N].
One makes N – 1 comparisons, this is called a pass.
After the first pass the largest element is sink to the last position.
During the next pass, compare elements upto the last but one and second largest element
moves to the (N – 1)ˢᵗ position.
After N- 1 passes, all elements are sorted.
Pass 4:
In this way after complete execution of this algorithm, the array gets sorted in ascending order as follows :
Q. 19 What do you understand by the term searching ? Which are the different types of searching algorithms? Explain the linear searching algorithm.
Ans :
Searching : Searching means to find out particular element from a given list of elements or
check whether required element is present or not in an array. There are two types of searching algorithms as follows :
(1) Linear search
(2) Binary search
Linear searching algorithm :
In linear search the given element is compared with each element of list one by one.
For algorithm, refer to Q. No. 20.
Q. 20 Write an algorithm for linear search technique with suitable example.
Ans :
Algorithm Linear Search
LINEAR(DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements and ITEM is given element. This algorithm finds the location LOC of ITEM in DATA or sets LOC = 0, if search is unsuccessful.
Step 1: [Insert ITEM at the end of DATA]
Set DATA [N + 1] := ITEM
Step 2: [Initialize counter]
Set LOC = 1
Step 3: [Search for item]
Repeat While DATA [LOC] ≠ ITEM :
Set LOC := LOC + 1
[End of loop]
Step 4: If LOC = N +1, then:
Set LOC = 0
Step 5: Exit
For example; Given DATA array with following 5 elements
11 22 33 44 55 Suppose ITEM = 33
Step 1: Set DATA [6] = 33, - List becomes
11 22 33 44 55 33
Step 2; LOC = 1
Step 3: Since DATA [1] = 11 ≠ 33 LOC = 2
Since DATA [2] = 22 ≠ 33 . LOC = 3
Here DATA [3] = 33 = 33 = ITEM
Step 4: Hence ITEM = 33 found at position, LOC = 3.
Q. 21 Write an algorithm for binary search technique with example.
Ans :
Binary search is used to search an element from sorted array.
Algorithm : Binary search
Binary (DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB. ITEM is given element. BEG denotes beginning, MID denotes middle and END denotes end location of DATA.
This algorithm finds the location LOC of ITEM in DATA or sets LOC = NULL,
search is unsuccessful.
Step 1: [Initialize Variables] Set BEG : = LB, END = UB and MID := INT ((BEG + END)/2) Step 2: Repeat steps 3 and 4 while BEG = END AND DATA[MID] ≠ ITEM Step 3: If ITEM < DATA[MID], then : set END := MID - 1 Else : Set BEG := MID + 1 [End of If structure] Step 4: Set MID := INT ((BEG + END)/2) [End of step 2 loop] Step 5: If DATA[MID] = ITEM, then : set LOC := MID Else : LOC := NULL [End of If structure] Step 6: Exit e.g. Given DATA be the following sorted 13 element array : 11 22 30 33 40 44 55 60 66 77 80 88 99 Suppose ITEM = 40 Step 1: Initially BEG = 1 and END = 13 Hence MID = INT[(1 + 13)/2] = 7 and so DATA[MID] = DATA [7] = 55 Step 2: Since 40 < 55, END has its value changed by END = MID - 1 = 7 - 1 = 6 Hence MID = INT [(1 + 6)/2] =3 and so DATA[MID] = DATA[3] = 30 Step 3: Since 40 > 30, BEG has its value changed by BEG = MID + 1 = 3 + 1 = 4 Hence MID = INT [(4 + 6)/2] = 5 and so DATA[MID] = DATA[5] = 40 Found ITEM in location LOC = MID = 5
Click on DOWNLOAD and Data Structures Part – 3 pdf will start downloading.
-
Can I download Data Structures Part – 3 PDF Free ?
Yes, you can download all TPS Computer Science 12th Pdf for free. Only you need to click on download button and wait for 30 seconds. Your download will start automatically.
-
Unable to download the pdf ?
Please click on the download button and wait for 30 seconds for the downloading link to be generated. After that check your downloads you will get your pdf.
-
Why I am seeing count down timer after clicking on download button ?
Please wait for it to complete and then you will able to download it. You are seeing count down timer for downloading link to be generated.