Chapter 2: Array as a Data Structure

 

One Marks Question

1. State any two limitations of an Array.(MAR-19)

Answer: The limitations of the array in the data structure are:

1. Array is Static data structure. Memory can be allocated at compile time only. Thus if after executing the program we need more space for storing additional information then we cannot allocate additional space at run time. 
2. Operations like insertion and deletion in arrays consume a lot of time. Insert a new value in its correct position, or remove it, then, for each such operation we may need to move many elements.
3. No Bound Checking- If we specify the size of array as ‘N’ then we can access elements up to‘N-1’ but in C if we try to access elements after ‘N-1’ i.e Nth element or N+1th element then we does not get any error message.
4. If the number of elements of an array is less than the allocated size of array, the memory space is wasted.

 
2. How are the elements of an array stored in memory?(APR-17) 

Answer: Array is the collection of homogeneous elements and they are stored sequentially. If you know the base address of the array then you can access any other element of the array because they are stored sequentially in the memory. Base address is nothing but the address of the first element of the array.

If our integer array A has five elements and base address is 1024 and suppose the integer is taking two bytes of space in the memory then,

address of A[0]=1024 // base address of the array

address of A[1]=1026

address of A[2]=1028

address of A[3]=1030

address of A[4]=1032

3. What is the time complexity of Quick Sort?(OCT 2018)

Answer: For an array, in which partitioning leads to unbalanced sub-arrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.

And if keep on getting unbalanced sub-arrays, then the running time is the worst case, which is O(n2)

Where as if partitioning leads to almost equal sub-arrays, then the running time is the best, with time complexity as O(n*log n).

Worst Case Time Complexity [ Big-O ]: O(n²)

Best Case Time Complexity [Big-omega]: Ω(n*log n)

Average Time Complexity [Big-theta]: Θ(n*log n)

3. Define stable sorting.(APR 2017)

Answer: If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting. A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in the sorted output as they appear in the unsorted input. 

Examples: Bubble sort, Insertion sort, Merge Sort, Counting sort

4. What is worst and best time complexity of merge sort?(MAR 2018)

Answer: Merge Sort is quite fast, we perform a single step operation to find out the middle of any sub-array, i.e. O(1). And to merge the sub-arrays, made by dividing the original array of n elements, a running time of O(n) will be required.

Hence the total time for mergeSort function will become n(log n + 1), which gives us a time complexity of O(n*log n).

Worst Case Time Complexity [ Big-O ]: O(n*log n)

Best Case Time Complexity [Big-omega]: Ω(n*log n)

Write an algorithm for binary search. Also state its complexity.

Binary search algorithm works on the principle of divide and conquer. This algorithm works with the sorted data. Binary search looks for an element to be searched in the middle first, if the element matches with the required one then it is returned as an output otherwise the whole list is considered into two parts i.e left side list and right side list.

If the element to be searched is greater than an element in the middle position then required element is searched into left side of the array otherwise element is searched on the left side of the array. This process is carried on until element from an array matches the required element.

BINARY_SEARCH(A, lower_bound, upper_bound, VAL)

Step 1: [INITIALIZE] SET BEG = lower_bound
        END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
        SET POS = MID
            PRINT POS
        Go to Step 6
        ELSE IF A[MID] > VAL
            SET END = MID - 1
        ELSE
            SET BEG = MID + 1 
        [END OF IF]
        [END OF LOOP]
Step 5: IF POS = -1
            PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
        [END OF IF]
Step 6: EXIT