Data may be organized in many different ways. Data structure is the way in which ) Gilferent data elements are lopically related. 4) Collection of data elements forming an organisation characterized by the accessing functions is called data structure. ii) ‘The data structure should be simple and it should show the relationship between data elements is) Types (Linear data structure ~ (i) Nomlinear 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. eg. trees - Computer language provides different data strictures like arrays, stack, queue, tree etc. Data Structure Operations » Q3) Explain in brief any six data structure operations. (Oct. 2002,04,06,12,15; Mar. 2002,06,12, July 2017, 19, Ma Jans: (The data appearing in data structures are processed by means of certain (@) Traversings OT Accessing each record or elemient exactly once, so that it can be processed is called as SPT operations like: ) traversing For eg, multiplying each element of an array by 6. @ Inserting : ~ Adding a new record to the existing structure is called as inserting, © scanned with OKEN ScannerData Structures Removing a record from the existing structure is called as deleting. 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. Sorting: Arranging records in some logical order is called as sorting, Merging means combining the records in two different sorted files into a single sorted © Scanned with OKEN ScannerExplain Bubble sort algorithm with s [ARSED Algorithm — Bubble Sort (DATA, N) Here DATA isa linear array with N elements. This algorithm sorts elements of DATA in ascending order. * Step: Repeat steps 2and 3 for Ki=1 TON -1 4 Step 2: Set P= Step 3: Repeat While Pure N-K: “(af DATA [Ptr] > DATA [Ptr +1], then interchange DATA [Ptr] and DATA [Ptr +1] [End of If structure] rement pointer] Set pes ptr +1 [End of inne oop] [End of outer loop step 4: Exit X Beplanation: . b) Suppose DATA is an array of N elements. S ‘means arranging the elements such that DATA [1] <=DATA [2] < DATA IN] In Bubble sort, compare DATA(1} DATA[1] > DATA(2} Next DATA(2] is compa is repeated till DATA[N. One makes N ~1 compa orting these elements in ascending ore" DATA(2] and exchange them if re with DATA(3}. They are exchanged if necessary. This proc ] is compared with DATAIN]. ns, this i called a pass. Alter 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 la element moves to the (N ~ 1} position, Alter N— 1 passes all elements are sorted. © scanned with OKEN ScannerWrite an algorithm for binary search technique with examp|q(@ Sooo EME] "ss. Binary search is used to search an clement 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 clement, BEG denies beginning, MID denoted middle and ENDY denotes end location of DATA. This algorithm finds the loation LOC of ITEM in DATA or sets LOC = NULL, if search is unsuccessful. ‘Step 1: [Initialize Variables] Set BEG: = LB, END = UB and MID:=INT ((BEG +END)/2) Repeat steps Sand 4 while BEG = END AND DATA[MID] ITEM. Step 3: IFITEM < DATAIMID], then set END:=MID-1 Step Else: 4 ‘Set BEG:= MID +1 [End of lfstructure] ‘*Step.4: Set MID:= INT ((BEG + END)/2) [End of step 2 loop] ‘*Step5: If DATA[MID] = ITEM, then: set LOC:= MID Else LOC :=NULL [End of If structure] SStep6: Exit ‘Qes: Given DATA be the folowing sorted 18 element aay nm 39 33 «40 OS © 6 7 0 8 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 © Scanned with OKEN Scannerthis algorithm the array gets sorted in asc, onder grat] [5] pararz [2] [| paTals) paral [8] patals) [55 Ai — i ch are the different Fa War yon een ay ea Wich ae i ad ‘atgritns ? Expr Ud PLU MOM eUI i riven list of elem + ing Searching means f0 find Out particular element froma given : cing algorithms 3 OWS (a) Linear search @) Binary search Linear searching algorithm: element of list one by on Te tea search te given clement is cSmpared with each For algorithm, refer to Q. No. 21 [WAT Write an algorithm for Jnear search technique with st ‘Algorithm Linear Search LINEAR(OATA,N, ITEM, LOO) Here DATA isa linear array with N element ‘is ‘element Ss = seca ey oe a Step 1: _ [Insert ITEM at the end of DATA] ‘Set DATA [N + 1] := ITEM : Step 2: [Intlize counter] Set LOC :=1 step 3: [Search for ter] Repeat While DATA [LOC]# ITEM : Set LOC := LOC +1 [End of oop] eStep 4: IFLOC=N+1, ther Set LOC:=0 steps: Exit @fForexample: Given DATA array wit . ee following elements Suppose ITEM =33 a © scanned with OKEN Scanner(Q.22)) Write an algorithm for binary search technique with exampl{@QS20Q00000ENE) "ARS. Binary search is used to search an element fom 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 clement. BEG denotes bepinning, MID denoted middle and END denotes end location of DATA. This algorithm finds: the location LOC of ITEM in DATA or sets LOC = NULL, ifsearch is unsuccessfl. Step 1: [niilize Variables} Set BEG: = LB, END Step 2: Repeat steps 3 and 4 ‘while BEG = END AND DATA[MID] ITEM Step 3: IfITEM < DATAIMID}, then. set END:=MID-1 Else: Set BEG :=MID +1 {End of structure] Step.4: Set MID:=INT ((BEG + END)/2) [End of step 2100p] Step 5: If DATA[MID] =ITEM, then set LOC = MID Else LOC = NULL [End of I structure] Step 6: Exit Qe: Given DATA be the following sorted 13 clement array ‘i 3 8 06 7 0 8 8 Suppose ITEM +Step 1: Initlly BEG = 1 and ENI SS "Hence MID = INTI(1 + 13)/2]=7 © and so DATAIMID] = DATA [7] =55 1B and MID := INT ((BEG + END)/2) © scanned with OKEN Scanner‘TPS Computer Science -1 218 Linear Search Binary Search Binary Search Linear search performs on unsorted list of elements as well as sorted list. For binary search, the elements in array are stored in alphabetically or numerically in sorted manner. 2. Compare the desired element with all elements in an array until the match is found ‘Compare the value of midpoint with desired value. Ifthe value is greater than midpoint value, the first half is checked, otherwise second half is checked until search is successful or intervals empty. 3. Insertion of an element in an array can bbe performed very efficiently when ‘An inseion of a new element requires that many elements be array is not ordered. physically moved to preserved order. ‘4 For large size of array, time required For large size of array, comparatively for this search is very large. time required is les, 5. Time complexity is as follows worst case: N comparison Best case : 1 comparison Time complexity as follows worst case : log, N comparison Best case: comparison Q.25 What are pointer arays? ‘Ans: the memory address of other variable. tan ae ‘An array is called pointer array, ifeach element of that array isa pointer. ‘The variable is called as pointer variable, if it points to another variable ie. it contains ii) Consider an organization, which divides its employee list into four groups, depending on certain conditions. Following figure shows the list of 4 groups. There are 15 employes and groups contain 2, 5,4 and 4 employes respectively as e Group] Group? | Group3| Group 4 Deepak | Swapnil_| Rajdeep | Yashwant Nitin | Amit__| Amol _| Chintamani ~~ | vivek | Yogesh | Kishore = Ravi__| Shekhar = [Omprakash | = fy) 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 lst of employees in all four groups ‘sequentially, while the second array is Group array, which 2 pointer array, which ‘contains the starting address of each group in the Employee array, respectively. © Scanned with OKEN Scanner