1. Array

 

Array

An array is a data structure that stores collection of elements of same type stored at a contiguous memory locations and can be accessed using an index.

Declaring and Initializing an array in C

• dataType arrayName[arraySize];
  arrayName = {value1,value2, ..., valueN};
• dataType arrayName[arraySize] = {value1,value2, ..., valueN};
• dataType arrayName[] = {value1,value2, ..., valueN};
• In C, default value of the elements in an array is undefined or garbage. When an array is declared, the memory is allocated for the elements of the array, but the values of those elements are not initialized.
• It is important to note that some programming languages like Java, automatically initializes the elements of an array to a default value if no initial values are specified.
• In C, we cannot change the size of the array once it has been declared.

1. How can we initialize an array in C language?
1. int arr[2] = (10, 20);
2. int arr(2) = {10, 20};
3. int arr[2] = {10, 20};
4. int arr(2) = (10, 20);

iii. int arr[2] = {10, 20};

Advantages of array

• Efficient storage and retrieval: Array store elements in contiguous memory locations, which makes it easy to retrieve elements using their index. So very efficient with large amounts of data.
• Random access (fast access): Arrays allow access to individual elements using their index, which means that accessing any element of the array takes the same amount of time.
• Easy to sort and search: Arrays can be easily sorted and searched using algorithms like binary search, which can be more efficient that searching through unsorted data.
• Flexibility: Arrays can be used to represent a wide-variety of data structures, including stacks, queues etc.
• Easy to use: Arrays are a simple and easy-to-use data structure that can be easily understood by programmers of all skill levels.

Disadvantages of array

• Fixed size: In most programming languages, arrays have a fixed size that cannot be changed once they are created. This can make it difficult to work with data structures that need to grow or shrink dynamically. It can cause internal or external fragmentation.
• No built-in support for insertion or deletion: Inserting or deleting an element in an array can be time-consuming and rrequire shifting all the elements after the insertion or deletion point.
• Homogeneous elements: Arrays can only store elements of the same type, which can be limiting for many requirements.
• Poor performance for some operations: Some operations, such as searching or inserting elements in a sorted array, can have poor performance compared to other data structures like hash tables or binary search trees.

1. Which of the following is the disadvantage of the array?
1. Stack and Queue data structures can be implemented through an array.
2. Index of the first element in an array can be negative.
3. Wastage of memory if the elements inserted in an array are lesser than the allocated size.
4. Elements can be accessed sequentially.

iii. Wastage of memory if the elements inserted in an array are lesser than the allocated size.

2. What is the time complexity for inserting/deleting at the beginning of the array?
1. O(nlogn)
2. O(1)
3. O(n)
4. O(logn)

iii. O(n)

3. Which of the following operations is not O(1) for an array of sorted data. You may assume that array elements are distinct.
1. Find the i^th largest element.
2. Delete an element.
3. Find the i^th smallest element.
4. All of the above.

ii. Delete an element.

4. What is the output of the following Java Code?
public class Array {
    static public void main(String args[]) {
        int[] arr = { 1, 2, 3, 4, 5 };
        System.out.println(arr[5]);
    }
}
1. 4
2. 5
3. ArrayIndexOutOfBoundsException
4. InvalidInputException

iii. ArrayIndexOutOfBoundsException

5. What is the output of the following C Code?
#include <stdio.h>
int main()
{
    int arr[5] = {10, 20, 30, 40, 50};
    return 0;
}
1. Garbage value
2. 10
3. 50
4. None of the above

i. Garbage value

Indexing in Array

1. 0 (zero-based indexing): The first element of the array is indexed by subscript of 0.
2. 1 (one-based indexing): The first element of the array is indexed by subscript of 1.
3. n (n-based indexing): The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like enumerations, or characters may be used as an array index.

1. Assuming int is of 4 bytes, what is the size of int arr[15]?
1. 15
2. 56
3. 60
4. 64

iii. 60

Size of an array

Number of elements in an array = Upper bound - Lower bound + 1
where, Upper bound is the index of last element of the array,
and Lower bound is the index of the first element of the array.

Size of array = Number of elements * Size of each element in bytes

Address of arr[k] = B + W * (k - Lower Bound)
where, B is the base address of the array or address of first element,
and W is the size of each element in bytes

1. Let the base address of the first element of the array is 250 and each element of the array occupies 3 bytes in the memory, then address of fifth element of a one-dimensional array a[10].

Base address, B = 250 byte
Index of fifth element, k = 4
Size of each element, W = 3 bytes
Address of arr[4] = 250 + 3*4 = 262 byte

2. An array has been declared as array[-6 .... 6] of elements where every element takes 4 bytes, if the base address of the array is 3500, find the address of array[0].

Base address, B = 3500 byte
Index of 0, k = 6
Size of each element, W = 4 bytes
Address of arr[6] = 3500 + 4*6 = 3524 byte

3. A program P reads in 500 integers in the range [0 ... 100] experimenting the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?
1. An array of 50 numbers.
2. An array of 100 numbers.
3. An array of 500 numbers.
4. A dynamically allocated array of 550 numbers.

i. An array of 50 numbers.