edited by
29,549 views
45 votes
45 votes

Let $A$ be a two dimensional array declared as follows:

A: array [1 …. 10] [1 ….. 15] of integer;

Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location $100$, what is the address of the element $A[i][j]$?

  1. $15i+j+84$

  2. $15j+i+84$

  3. $10i+j+89$

  4. $10j+i+89$

edited by

8 Answers

Best answer
38 votes
38 votes

$A [ LB_1\ldots UB_1,LB_2\ldots UB_2]$

$BA =$ Base address.

$C =$ size of each element.

Row major order.

$Loc(a[i][j]) = BA + [(i-LB_1) (UB_2-LB_2 + 1) + (j - LB_2)] * C$.

Column Major order

$Loc(a[i][j]) = BA + [ (j-LB_2) (UB_1-LB_1+ 1) + (i - LB_1) ] * C$.

Substituting the values.

Answer is A.

edited by
34 votes
34 votes

In this question, it is asked that A[i][j] is how many memory blocks far from memory location 100 (i.e base address of array). Now to reach 'ith' row we have to pass through i-1 rows each of which contains 15 elements. After that to reach jth column (of ith row) we have to pass through j-1 elements. 

Address of A[i][j] = base_address of A + [(i-1)*15 + (j-1)]*1

= 100 + 15i -15 + j - 1

=15i + j + 84

A is the answer. 

16 votes
16 votes

Let Array be : A[m][n]

Type 1 :

The array indices started with 1 and it is in Row major order :

Base Address + Size * [ (i-1)*n + (j-1) ]

The array indices started with 0 and it is in Row major order

Base Address + Size * [ i*n + j ]

Type 2 :

The array indices started with 1 and it is in Column major order :

Base Address + Size * [ (j-1)*m + (i-1) ]

The array indices started with 0 and it is in Column major order

Base Address + Size * [ j*m + i ]

8 votes
8 votes

$\color{blue}{\underline{\text{Most Easy Solution to this problem and applicable to all such problems:}}}$

$\color{blue}{\underline{\text{Explanation:}}}$

$\mathbf{\color{red}{Row\;Major\;Order:}}$

Let's convert the above arrays to indices which starts from $\mathbf{0}$.

$\therefore[1\dots10][1\dots15]\equiv[0\dots9][0\dots14]$

Now, we need to find the position of $\mathbf{\left (i,j\right)^{th}}$ element.

$\because$ We subtracted $\mathbf{1}$ from the above given arrays to make their starting indices $\mathbf{0}$.

$\therefore \mathbf{ \left (i, j\right) } \equiv \mathbf{\left(i-1,j-1\right)}$.

Now,

$\therefore\mathbf{Address} = \mathrm{\underset{Base\;address}{100} + \underset{No.\;of\;rows}{(i-1)}\times\underset{\text{No. of columns in each row.}}{15}+\underset{\text{Number of cols. we need to traverse after rows}}{j-1} \\= 100+15\times i-15+j-1 \\=84+15\times i+j \\= 15i+j+84 }$

$\therefore\;\mathbf{15i+j+84}$ is the required answer. Hence, $\mathbf{Option-A}$ is corect.


$\color{red}{\mathbf{Column\;Major\;Order:}}$

$\color{red}{\mathbf{\underline{Swap\;column\;to\;rows\;and\;rows\;to\;columns:}}}$

Let's convert the above arrays to indices which starts from $\mathbf{0}$.

$\therefore[1\dots10][1\dots15]\equiv[0\dots9][0\dots14]$

On Swapping column to rows and rows to column:

$[0\dots14][0\dots9]$

Now, we need to find the position of $\mathbf{\left (i,j\right)^{th}}$ element.

$\because$ We subtracted $\mathbf{1}$ from the above given arrays to make their starting indices $\mathbf{0}$.

$\therefore \mathbf{ \left (i, j\right) } \equiv \mathbf{\left(i-1,j-1\right)}$.

On swapping:

$\mathbf{(j-1,i-1)}$

Now,

$\therefore\mathbf{Address} = \mathrm{\underset{Base\;address}{100} + \underset{No.\;of\;rows}{(j-1)}\times\underset{\text{No. of columns in each row.}}{10}+\underset{\text{Number of cols. we need to traverse after rows}}{i-1} \\= 100+10\times j+i-1 \\=89+10\times j+i \\= 10j+i+89}$

$\therefore\;\mathbf{10j+i+89}$ is the required answer.

$\therefore \mathbf{D}$ is the correct option in case of $\mathbf{Column\;Major\;Order}$.

 

edited by
Answer:

Related questions

24 votes
24 votes
1 answer
1
Kathleen asked Sep 25, 2014
8,972 views
A multiplexer with a $4-bit$ data select input is a$4:1$ multiplexer$2:1$ multiplexer$16:1$ multiplexer$8:1$ multiplexer
29 votes
29 votes
11 answers
2
Kathleen asked Sep 25, 2014
14,544 views
A complete $n$-ary tree is one in which every node has $0$ or $n$ sons. If $x$ is the number of internal nodes of a complete $n$-ary tree, the number of leaves in it is g...
22 votes
22 votes
3 answers
4
Kathleen asked Sep 25, 2014
9,069 views
Which of the following operations is commutative but not associative?ANDORNANDEXOR