In: Computer Science
6 C++ Questions:
19. Assuming an int is size 4 bytes, what is the size in memory of the below array:
int cards[10] = {7, 4, 7, 5, 7};
20. In the array from question 19, what is the value of the below elements:
cards[1]; cards[8];
Assume you have an array with 128 integers which is sorted from
lowest to highest.
21a. You are searching for a value which is contained in the array
using the binary search algorithm. What is the
minimum number of comparisons it will take?
21b. You are searching for a value which is contained in the array
using the linear search algorithm. What is the
maximum number of comparisons it will take?
22. True/False: in order to use the linear search algorithm on an array, the array must be sorted
23. True/False: a bubble sort on an integer array is guaranteed to do at least one swap.
24. Write a function which takes an array of ints and size of array as parameters, and returns the maximum value in the array. You do not need to demonstrate calling this function from main(). It must have the following signature:
int findMax(const int array[], int size);
19. Solution
According to the question, It is given the size of int is 4 bytes.
Then the size of the memory for the given array : int cards[10] = {7, 4, 7, 5, 7}; is
When we use fewer elements than the size specified remaining elements will set to 0 by default .
int cards[10] = {7, 4, 7, 5, 7}; // actual array is {7, 4, 7, 5, 7, 0, 0, 0, 0, 0}
Then size of the given array int cards[10] = {7, 4, 7, 5, 7}; will be = 4 bytes* 10 elements
= 40 bytes
So, 40 bytes is the size in memory for the given array.
20. Solution
The value of the below elements:
cards[1]; cards[8];
When we use fewer elements than the size specified remaining elements will set to 0 by default .
int cards[10] = {7, 4, 7, 5, 7}; // actual array is {7, 4, 7, 5, 7, 0, 0, 0, 0, 0}
Array index will start from 0.
cards[0] will be 7.
So,
cards[1] will contain value 4.
cards[8] will contain value 0.
21 a. Solution
It is given that the array contains 128 integers and elements in the array are sorted from lowest to highest.
It is also given that element to be searched is always present in the array.
When we are searching for a value which is contained in the array using the binary search algorithm.
The minimum number of comparisons it will take is 1.
When the element to be searched is the middle element or the first element compared by the algorithm.
[When Size of array is even(N is even) It is compared with either n/2 or (n+1)/2 th element]
The array the binary search algorithm will only do 1 comparison and stop executing.
So, minimum number of comparisons will be 1.
21b. Solution
It is given that the array contains 128 integers and elements in the array are sorted from lowest to highest.
It is also given that element to be searched is always present in the array.
You are searching for a value which is contained in the array using the linear search algorithm.
[ Linear search algorithm: The array is traversed sequentially and every element is checked. ]
The maximum number of comparisons it will take is 128.
When the element to be searched is the last element of the array It will compare with all 128 elements present in the array.
So, maximum number of comparisons will be 128.
22. Solution
True/False: In order to use the linear search algorithm on an array, the array must be sorted
Solution: False
No, It is not compulsory to have an array to be sorted in order to use the linear search algorithm on an array.
Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array from the starting, till the desired element or value is found.
But, there is a limitation for Binary Search Algorithm.
That is, the array or list of elements must be sorted for the binary search algorithm to work on it.
23. Solution
True/False: A bubble sort on an integer array is guaranteed to do at least one swap.
Solution: False
No, it is not true that a bubble sort on an integer array is guaranteed to do at least one swap.
Because, when the given array is already sorted, when we apply bubble sort on that array there will be no swap of the elements in the array.
So, It is not mandatory to have at least one swap.
24.
Write a function which takes an array of ints and size of array as parameters, and returns the maximum value in the array. You do not need to demonstrate calling this function from main(). It must have the following signature:
int findMax(const int array[], int size);
Solution:
int findMax(const int array[], int size){
int i;
int max = array[0]; // Initialize first element as maximum element
// Traverse array elements from second and compare every element with current max
for (i = 1; i < size; i++){
if (array[i] > max)
max = array[i];
}
return max;
}