## DOEACC A LEVEL A6-R4 DATA STRUCTURE THROUGH C++ QUESTION PAPERS

DOEACC A LEVEL A6-R3/R4 DATA STRUCTURE THROUGH ‘C’ LANGUAGE/’C++’ NOTE: 1. There are TWO PARTS in this Module/Paper. PART ONE contains FOUR questions and PART TWO contains SIX questions. 2. PART ONE is to be answered in the TEAR-OFF ANSWER SHEET only, attached to the question paper, as per the instructions contained therein. PART ONE is NOT to be answered in the answer book. 3. Maximum time allotted for PART ONE is ONE…

Read more...## Search – Indexed Sequential Search

are closed

Indexed Sequential Search: In this searching technique, first of all an index file is created that contains references to a group of records, once an index is obtained, the partial searching takes less time since it is to be located in the group/bucket specified by the index. The program given below creates an index file for the employee records by grouping the records and then locates the required key by…

Read more...## Sorting on multiple keys

are closed

Sorting on multiple keys The sorting algorithm may be applied on multiple keys such that if first field contains duplicate values, then sorting is done on a secondary field and so on. However, if the first field contains unique values, then sorting is not applied on secondary field. Say for example: The input for the combination {studentname, feeamt} { (xyz,3000), (abc,1000), (xyz, 1000), (abc,3000)}; will result in the following output:…

Read more...## Sorting – Address Calculation Sort (Hashing)

are closed

Sorting – Address Calculation Sort (Hashing) In this method a function f is applied to each key. The result of this function determines into which of the several subfiles the record is to be placed. The function should have the property that: if x <= y , f (x) <= f (y), Such a function is called order preserving. An item is placed into a subfile in correct sequence by…

Read more...## Sorting – Quick Sort (Partition Exchange Sort)

are closed

Sorting – Quick Sort (Partition Exchange Sort) Suppose x be an array, n is the number of elements. Choose an element from a specific position within the array. Array x is partitioned so that y is placed into position j, and the following conditions hold: 1) Each of the elements in position 0 through (j-1) is less than or equal to y. 2) Each of the elements in position (j+1)…

Read more...## Sorting – Merge Sort

are closed

Sorting – Merge Sort Merging:- Merging is the process of combining two or more sorted files into a third sorted file. An example of a routine that accepts two sorted arrays a and b of n1 and n2 elements respectively and merges them into a third array c containing n3 (n1+n2) elements. Steps for Merge Sort: Divide the file n subfiles of size 1 and merge adjacent pair of files….

Read more...## Sorting – Radix Sort

are closed

Sorting – Radix Sort Radix Sort sorts the number in scans equal to the number of digits of maximum number. eg. 45, 3, 235, 89, 150, then maximum scans = 3. Thus radix sort operates three times. Radix sort uses 10 queues to sort the given numbers. Begin with least significant digit, ending with most significant digit. Fetch a number from the array and place it in one of the…

Read more...## Sorting – Straight Selection Sort

are closed

Sorting – Straight Selection Sort Begin from the first element, taking i=0 to n-1. Find the minimum number in the first scan. Interchange ith element with the minimum number. Start searching minimum element again from i+1 to n. The number of scans is equal to the number of elements. Stop scan when the last element remains to be replaced with min. Display the output which is now sorted. Example: Though…

Read more...## Sorting – General Selection Sort

are closed

Sorting – General Selection Sort Steps: Fetch the numbers to be sorted in an array. Push these numbers one by one to a priority queue. (Any priority-lower or higher may be considered). Case 1: Lower values with high priority for ascending order. Case 2: Higher values with high priority for descending order. 3. Pop all the elements from the priority queue to the array one by one. 4. Display the…

Read more...## Sorting – Insertion sort

are closed

Insertion Sort Sorts a set of records by comparing the next record with all the previous elements. Compare next element with previous. If next element is smaller than previous element, then swap both the elements. i.e. if(arr[j]>arr[i]) swap(arr[j],arr[i); Example: The loop may be written as follows: for I = 2 to n for j = I-1 to >=1 if(arr[I] < arr[j]) swap(arr[i],arr[j]); Insertion sort is considered best if most of…

Read more...
are closed