Data Structures book chapter 3 exercise solutions
1. What are arrays and why are they needed?
Arrays are the most important and brilliant piece of development in software area.
They are grouped into data structures and its use and implications is very high in programming languages.
So what are arrays, Array is also a type of variable just like int, char, float, etc.. but with some changes. Here array has a structure, data structure with a collection of data elements in a structured way of storing it. It holds similar type of data elements.
Why are they needed, consider this example. there are 20 students whose marks is to be scanned and printed. So in terms of programming language, we need at least 20 variables to hold 20 students marks, 20 statements or ( 1 statement with 20 variables ) for getting input, 20 print statements for printing marks. Therefore it is really manual, tedious, highly taxing and error prone process. Since this was only 20 students, consider 200, 2000, 20000 or 200000 students data entry job. It is exponentially not possible. There was a urgent need to develop some kind of data structure that can hold large collection of data in one variable. Therefore arrays are needed in every aspect of programming.
It is all about data management, data organisation.
2. How is an array represented in the memory?
1st element | 2nd element | 3rd element | ...... n elements
The array is stored in memory in a consecutive, sequential pattern with a base address as the stating point of array and index variable for iteration, traversing the array until end of array is reached.
Every element of array is accessed by an index variable. so if array named john is there with a size n = 10, then john[2], john[5] , etc.. will access the 3rd and 6th element of array respectively.
There is a formula for calculation of address of any element of array from base address and index.
Address of an element (k) = BA + s ( i )
where k = any no of element
BA = base address
s = size of variable that array holds
i = index of element whose address is being calculated.
example- > consider this array A -> { 10, 20, 40, 60, 66};
consider BA = 1000, s = 2 bytes for int type variable, i = 4 i.e we need address for the 5th element in array.
therefore
k = 1000 + 2 ( 4 )
= 1000 + 8
k = 1008
3. How is a two-dimensional array represented in the memory?
Two dimensional array is array of arrays, it contains rows and columns.
example of 2d array is A -> { {22,55,33,44} , {55,77,33,11} , {66,77,88,99} };
2D array incorporate Mathematics formulas and concepts like Matrices, grids, tables into computer programs.
In memory it is either stored in row order form or column order form.
In row order form, Row by row elements are stored first.
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3).
In Column order form
(0,0) (1,0) (2,0) (3,0) (0,1) (1,1) (2,1) (3,1) (0,2) (1,2) (2,2) (3,2)
Similar to 1D array, 2D array keeps track of base address only for address of elements.
If the array elements are stored in column major order,
Address(A[I][J]) = Base_Address + w{M ( J – 1) + (I – 1)}
And if the array elements are stored in row major order,
Address(A[I][J]) = Base_Address + w{N ( I – 1) + (J – 1)}
where w is the number of bytes required to store one element,
N is the number of columns,
M is the number of rows,
I and J are the subscripts of the array element.
4. What is the use of multi-dimensional arrays?
The use of multi dimensional arrays is quite amazing as it opens up whole lot of possibilities, Examples include Spreadsheets that contains multiple pages of rows and columns, Data processing and manipulation in Excel software, Database management systems, Archive projects, etc...
Computer modelling
Analysis of 3D spatial data like texture of earth,
Mapping spatial information of earth
Simulation
Plotting and simulation 2D data over time
Network topology
5. Explain sparse matrix.
Sparse matrix is a matrix which has many zero elements. In order to properly utilise memory, specialised algorithms and data structures that relies on sparse matrix structure is used. If we apply the standard operations of matrix to sparse matrix then whole process would be slow down and efficiency drops, Large amount of memory will be used up. Therefore, Sparse matrix can be compressed down for storage for saving space.
Two types of sparse matrix -> Upper triangular matrix and lower triangular matrix.
8. For an array declared as int arr[50] , calculate the address of arr[35] , if Base(arr) = 1000 and w = 2
int arr[50]
address = 1000 + 2( 36 )
= 1072
9. Consider a two-dimensional array Marks[10][5] having its base address as 2000 and the number of bytes per element of the array is 2. Now, compute the address of the element, Marks[8][5] , assuming that the elements are stored in row major order.
Marks [ 8 ] [ 5 ] = 2000 + 2 * ( 5 * ( 8 -1 ) + ( 5 - 1) )
= 2048
10. How are arrays related to pointers?
Arrays are directly related to pointers since arrays and pointers are both related to address of element. Pointers store address of a element and array also represent address of the element.
the array name is the address of element stored inside that data structure.
Example int arry[] = {1,2,34,45,5,6,66,6,6,6}
the name arry references to the base address of arry[0] i.e 1st element of array and from there each array element can be accessed using this base address.
int arry[] = {2,4,34,3,44,5,543};
int *pttr;
pttr = arry;
then , pttr will contain the base address of array. therefore pttr and &arr[0] are same. and pttr++ will point to next element in array and so on.
it is ok to write pttr = arry , but it is not valid to write arry = pttr because arry is a integer constant which is just a address, not a variable.
11. Briefly explain the concept of array of pointers.
We can have pointers in a array, so called array of pointers. It is an array that stores a whole lot of continuous pointers. Each pointer can have address of different variables.
int *ptr[10]
int *ptr[10];
int p = 1, q = 2, r = 3, s = 4, t = 5;
ptr[0] = &p;
ptr[1] = &q;
ptr[2] = &r;
ptr[3] = &s;
ptr[4] = &t;
therefore , *ptr[3] = 4 , since ptr[3] contains address of variable s.
int main()
{
int arr1[]={1,2,3,4,5};
int arr2[]={0,2,4,6,8};
int arr3[]={1,3,5,7,9};
int *parr[3] = {arr1, arr2, arr3};
int i;
for(i = 0;i<3;i++)
printf(«%d», *parr[i]);
return 0;
}
OUTPUT
1 0 1
12. How can one-dimensional arrays be used for inter- function communication?
One dimensional arrays can be used for inter - function communication in three major ways.
1. By passing individual element to function
2. By passing base address of array to function
3. By Passing the entire array
in these way, inter- function communication is achieved.
1. In this method, individual element is passed as parameter to function.
Calling function
main()
{
int arr[5] = {1,2,121,212,4}
fun( arr[4] )
}
void fun( int b )
{
printf("%d", b)
}
2. 2nd method is passing address
Calling function
main()
{
int arr[5] = {1,2,121,212,4}
fun( &arr[4] )
}
void fun( int *b )
{
printf("%d", *b)
}
14. Consider the array given below:
Name[0 ] Adam
Name[1] Charles
Name[2] Dicken
Name[3] Esha
Name[4] Georgia
Name[5] Hillary
Name[6] Mishael
(a) How many elements would be moved if the
name Andrew has to be added in it?
Ans 6
15. What happens when an array is initialized with
(a) fewer initializers as compared to its size?
Remaining elements are assigned value 0
(b) more initializers as compared to its size?
More values will be discarded and may be error will raise
Multiple-choice Questions
1. If an array is declared as arr[] = {1,3,5,7,9};
then what is the value of sizeof(arr[3]) ?
(a) 1
(b) 2
(c) 3
(d) 8
2
2. If an array is declared as arr[] = {1,3,5,7,9};
then what is the value of arr[3] ?
(a) 1
(b) 7
(c) 9
(d) 5
7
3. If an array is declared as double arr[50]; how
many bytes will be allocated to it?
(a) 50
(b) 100
(c) 200
(d) 400
400
4. If an array is declared as int arr[50] , how many
elements can it hold?
(a) 49
(b) 50
(c) 51
(d) 0
50
5. If an array is declared as int arr[5][5] , how
many elements can it store?
(a) 5
(b) 25
(c) 10
(d) 0
25
6. Given an integer array arr[] ; the i th element can
be accessed by writing
(a) *(arr+i)
(b) *(i + arr)
(c) arr[i]
(d) All of these
d All of these
True or False
1. An array is used to refer multiple memory locations
having the same name. True
2. An array name can be used as a pointer. True
3. A loop is used to access all the elements of an
array. True
4. An array stores all its data elements in non-
consecutive memory locations. False , Array stores elements in sequential fashion
5. Lower bound is the index of the last element in
an array. False , it stores the starting element index i.e 0
6. Merged array contains contents of the first array
followed by the contents of the second array. True
7. It is possible to pass an entire array as a function
argument. True
8. arr[i] is equivalent to writing *(arr+i) . True
9. Array name is equivalent to the address of its last
element. False, array name is equivalent to writing address of first element
10. mat[i][j] is equivalent to *(*(mat + i) + j) . True
11. An array contains elements of the same data type True .
12. When an array is passed to a function, C passes
the value for each element. False , it passes the base address of array
13. A two-dimensional array contains data of two
different types. False , it can contain int or char only
14. The maximum number of dimensions that an array
can have is 4. False, theoretically it can have n dimensions, but 3 dimensions are used at most.
15. By default, the first subscript of the array is zero. True
Fill in the Blanks
1. Each array element is accessed using a ______ subscript .
2. The elements of an array are stored in ______consecutive
memory locations.
3. An n-dimensional array contains ______n * n
subscripts.
4. Name of the array acts as a ______.base address
5. Declaring an array means specifying the ______data type ,
name ______, and ___size ___.
6. ___array name ___ is the address of the first element in the
array.
7. Length of an array is given by the number of
___size - 1___.
8. A multi-dimensional array, in simple terms, is an
___n * n matrix___.
9. An expression that evaluates to an __________
value may be used as an index.
10. arr[3] = 10; initializes the _____fourth 4th _____ element
of the array with value 10.
Programming exercises
1. Consider an array MARKS[20][5] which stores the
marks obtained by 20 students in 5 subjects. Now
write a program to
(a) find the average marks obtained in each
subject.
(b) find the average marks obtained by every
student.
(c) find the number of students who have scored
below 50 in their average.
(d) display the scores obtained by every student.
#include <stdio.h>
int main()
{
int marks[20][5], n, s,i,j, total=0, count=0;
float average = 0.0;
printf("\nStudents Marks data entry and processing program ");
printf("\nEnter no of Students and no of subjects : ");
scanf("%d %d", &n, &s);
for(i=0; i< n; i++){
printf("\nEnter Student %d Marks", (i+1) );
for(j=0; j < s; j++){
printf("\nEnter Subject %d Marks: ", (j + 1 ) );
scanf("%d", &marks[i][j] );
}
}
average = 0;
//Average of each subject per Student
for(i = 0; i < n ; i++){
total = 0;
for(j = 0; j < s; j++ ){
total = total + marks[j][i];
}
average = total / n;
printf("\n\nAverage of Subject %d is : %f", i+1 , average);
}
// Average of Students per subject
average = 0;
for(i = 0; i < n ; i++){
total = 0;
for( j=0; j < s; j++ ){
total = total + marks[i][j];
}
average = total / s;
printf("\n\nAverage of Student %d is : %f", i+1 , average);
// Finding number of students who scored below 50 in average
if( average < 50 ){
count++;
}
}
printf("\n\nNo of Students who got below 50 on onaverage are : %d", count);
// Displaying the 2D matrix
for(i = 0; i < n ; i++){
printf("\n\nStudent %d Marks ", i+1 );
for(j = 0; j < s; j++ ){
printf("\nSubject %d Marks : %d", j+1 , marks[i][j] );
}
}
return 0;
}
Comments
Post a Comment