Data Structure & Algorithms Dr.

Ranjit Rajak

Array Based Practice Questions.

1. Show through appropriate data structure representa on of the following 4x4 Sparse Matrix.

0 0 11 0
12 0 0 0
0 -4 0 0
0 0 0 -25 4*4

2. Calculate the address of X[4,3] in a two dimensional array X[1-5,1-4] stored in row
major order. Assume the base address to be 1000 and that each element requires 4
words of storage.

3. Draw the vector representa on of the sparse matrix of the following matrix:

0 12 0 0

0 11 0 0

9 0 0 0

0 0 0 0 4*4

4. Suppose mul dimensional arrays A and B are declared using

A(-2:2, 2:22) and B(1:8, -5:5, -10:5)
(a) Find the length of each dimension and the number of elements in A and B.
(b) Consider the element B[3, 3, 3] in B. Find the effec ve indices E1, E2, E3 and the
address of the element, assuming Base(B) = 400 and there are w = 4 words per
memory loca on.

1
Data Structure & Algorithms Dr. Ranjit Rajak

5. Consider the alphabe zed linear array NAME in Fig. 4.23.

Name
1. Allen
2. Clark
3. Dickens
4. Edwards
5. Goodman
6. Hobbs
7. Irwin
8. Klein
9. Lewis
10. Morgan
11. Richards
12. Sco
13. Tucker
14. Walton
Fig 4.23

(a) Find the number of elements that must be moved if Brown, Johnson and Peters
are inserted into NAME at three different mes.

(b) How many elements are moved if the three names are inserted at the same me?

(c) How does the telephone company handle inser ons in a telephone directory?

6. Consider the linear arrays .

AAA(5:50), BBB(-5:10) and CCC(18).
(a) Find the number of elements in each array.
(b) Suppose Base(AAA) = 300 and w = 4 words per memory cell for AAA. Find the
address of AAA[15], AAA[35] and AAA[55].

7. Suppose a company keeps a linear array YEAR(1920:1970) such that YEAR[K] contains
the number of employees born in year K. Write a module for each of the following
tasks:
(a) To print each of the years in which no employee was born.
(b) To find the number NNN of years in which no employee was born.

2
Data Structure & Algorithms Dr. Ranjit Rajak

(c) To find the number N50 of employees who will be at least 50 years old at the end
of the year. (Assume 1984 is the current year.)
(d)To find the number NL of employees who will be at least L years old at the end of
the year. (Assume 1984 is the current year.)

8. Suppose a 10-element array A contains the values a1, a2,..., a10- Find the values in A
a er each loop.
(a) Repeat for K = 1 to 9:
Set A[K + 1] := A[K].
[End of loop.]
(b) Repeat for K = 9 to 1 by -1:
Set A[K + 1] := A[9].
[End of loор.]

Note that the index K runs from 1 to 9 in part (a) but in reverse order from 9 back to 1
in part (b)
9. Let A be an n x n square matrix array. Write a module which
(a) Finds the number NUM of nonzero elements in A
(b) Finds the SUM of the elements above the diagonal, i.e., elements A[I, J] where
I<J
(c) Finds the product PROD of the diagonal elements (a11, a22, ..., ann)

10. Consider the linear arrays XXX(-10:10), YYY(1935: 1985), ZZZ(35). (a) Find the number
of elements in each array. (b) Suppose Base(YYY) = 400 and w = 4 words per memory
cell for YYY. Find the address of YYY[1942], YYY[1977] and YYY[1988].
11. Consider the following mul dimensional arrays:

X(-5:5, 3:33) Y(3:10, 1:15, 10:20)

(a) Find the length of each dimension and the number of elements in X and Y.

(b) Suppose Base(Y) = 400 and there are w = 4 words per memory loca on. Find the
effec ve indices E1, E2, E3 and the address of Y[5, 10, 15] assuming (i) Y is stored in row-
major order and (ii) Y is stored in column-major order.

12. An array A contains 25 posi ve integers. Write a module which

(a) Finds all pairs of elements whose sum is 25.

(b) Finds the number EVNUM of elements of A which are even, and the number ODNUM
of elements of A which are odd.

3
Data Structure & Algorithms Dr. Ranjit Rajak

13. Suppose A is a linear array with n numeric values. Write a procedure

MEAN(A, N, AVE)
which finds the average AVE of the values in A. The arithme c mean or average x of
the values x1, x2, ..., Xn is defined by

x̄ = x + x2 +...+xn
n

Practice Question Based On Stack

1. Explain underflow and overflow condi on of the STACK with proper example.

2. Convert infix to pos ix without using STACK.

i. (A-B) * (D/E)
ii. (A+B/D) / (E-F)+G
iii. A*B- (C+D) / (E-F) +G/H
iv. (X+Y-Z)/(H+K)*S
v. J-K/G^H+(N+M)
vi. A*(B-C)/D+E*F

3. Evaluate the following pos ix expressions for the provided data.

i. ab^c+d/e + where a = 5, b = 3, c = d = 2, e = 9
ii. abcde+* +- where a = 12, b= 4, c = 7, d = 5, e = 2
iii. ab + cd* + e* where a = 2, b = 6, c = 3, d = 5, e = 9

4. The efficient method used in evalua ng a polynomial of the form

Pn(x) = ao rn + a1xn-1 + a2 x n-2 + ··· + an-1x + an
is by nes ng using Horner's rule, as shown below:
Pn(x)=( ... (((aox+a1)x + a2)x+ ... +an-1) ··· )x + an
Show how this can be carried out using a stack.
5. Consider the following arithme c expression in pos ix nota on:
752+*415-/-
(a) Find the value of the expression.
(b) Find the equivalent prefix form of the above expression.
(c) Find the value of the expression from its prefix nota on.
6. Convert the following infix expression into pos ix expression.
(i) (A-B) *X+ Y/ (F - C* E) + D
(ii) X and Y OR NOT (A> B)

4
Data Structure & Algorithms Dr. Ranjit Rajak

7. Convert A + (B * C- (D/E -F * G) * H) into pos ix form showing stack status a er

every step in tabular form.

8. There is a varia on in the original Euclid's algorithm for compu ng the greatest
common divisor of two integers M and N. According to the modified Euclid's
algorithm,

GCD(M-N, N) if M≥N
GCD(M, N) = M if N =0

GCD(M, N-M) if N>M

Using only a stack, write a procedure to compute the GCD as per the modified
Euclid's method.

9. Consider the following stack of characters, where STACK is allocated N = 8 memory

cells
STACK A, C, D, F, K,___,___,___
(For stack nota onal as the convenience, we use "___" to denote an empty memory
cell.) Describe the following opera ons take place:
(a) POP(STACK, ITEM) (e) POP(STACK, ITEM)
(b) POP(STACK, ITEM) (f) PUSH(STACK, R)
(c) PUSH(STACK, L) (g) PUSH(STACK, S)
(d) PUSH(STACK, P) (h) POP(STACK, ITEМ)

10. Consider the data in Problem 9. (a) When will overflow occur? (b) When will C be
deleted before D?

11. Consider the following stack where STACK is allocated N = 4 memory cells:
STACK: AAA, BBB, ___,___.
Describe the stack as the following opera ons take place:
(a) POP(STACK, ITEM) (b) POP(STACK, ITEM)
(c) PUSH(STACK, EEE) (d) POP(STACK, ITEM)
(e) POP(STACK, ITEМ) (f) PUSH(STACK, GGG)

12. Suppose the following stack of integers is in memory where STACK is allocated N = 6
memory cells:

5
Data Structure & Algorithms Dr. Ranjit Rajak

TOP =3 STACK: 5, 2,3,__,__,___

Find the output of the following program segment:
(i) Call POP(STACK, ITEMA).
Call POP(STACK, ITEMB).
Call PUSH(STACK, ITEMB + 2).
Call PUSH(STACK, 8).
Call PUSH(STACK, ITEMA + ITEMB).
(ii) Repeat while TOP ≠ 0:
Call POP(STACK, ITEМ).
Write: ITЕМ.
[End of looр.]
13. Translate, by inspec on and hand, each infix expression into its equivalent pos ix
expression
(a) (A-B)/((D + E) * F)
(b) ((A+B)/D) ↑ ((E - F) * G)

14. Let J and K be integers and suppose Q(J, K) is recursively defined by

5 if J<k
Q(J, K) =

Q(J-K,K+2)+J if J>-= K

Find Q(2,7) , Q(5,3) and Q(15,2).

15. Let A and B be nonnega ve integers. Suppose a func on GCD is recursively defined
as follows:
GCD(B, A) if A < B
GCD(A, B) = A if B = 0
GCD(B, MOD(A, B)) otherwise

(Here MOD(A, B), read "A modulo B," denotes the remainder when A is divided by B.)
(a) Find GCD(6, 15), GCD(20, 28) and GCD(540, 168). (b) What does this func on do?

16. Let N be an integer and suppose H(N) is recursively defined by

[3*N if N<5
H(N) =

2* H(N-5) +7 otherwise

a) Find the base criteria of H and (b) find H(2), H(8) and H(24).

6
Data Structure & Algorithms Dr. Ranjit Rajak

17. Let M and N be integers and suppose F(M, N) is recursively defined by

1 if M = 0 or M ≥ N ≥ 1
F(M,N)=

F(M-1, N) + F(M-1, N-1) otherwise

(a) Find (4, 2), F(1, 5) and F(2, 4). (b) When is F(M, N) undefined?

18. Let A be an integer array with N elements. Suppose X is an integer

func on defined by

33 0 if K = 0
22
X(K) = X(A, N, 11 K) = X(K-1)+ A(K) if 0<K≤N

X(K-1) if K>N

Find X(5) for each of the following arrays:

(a) N= 8, A: 3, 7,-2, 5, 6, -4, 2, 7 (b) N = 3, A: 2, 7,-4

What does this func on do?

19. Consider the stacks shown below:

Ini al State Final State

S1 S2 S2
Top 33
22
11
Top 3 Top 3
2 2
1 1

Write a procedure that performs a series of push and pop opera ons on S1 and S2; so
that the stack S₂ is transformed from its ini al state to its final state.

20. Consider the following stack, where STACK is allocated N = 6 memory cells:

STACK: AAA, DDD, EEE, FFF, GGG,____

7
Data Structure & Algorithms Dr. Ranjit Rajak

Describe the stack as the following opera ons take place: (a) PUSH(STACK, KKK), (b)
POP(STACK, ITEM), (c) PUSH(STACK, LLL), (d) PUSH(STACK, SSS), (e) POP(STACK, ITEM) and
(f) PUSH(STACK, TTT).

21. Suppose STACK is allocated N = 6 memory cells and ini ally STACK is empty, or, in
other words, TOP = 0. Find the output of the following module:
1. Set AAA :=2 and BBB := 5.
2. Call PUSH(STACK, AAA).
Call PUSH(STACK, 4).
Call PUSH(STACK, BBB + 2).
Call PUSH(STACК, 9).
Call PUSH(STACK, AAA + BBB).

3. Repeat while TOP ≠0:

Call POP(STACK, ITEM).
Write: ITЕМ.
[End of looр.]
4. Return.
22. Consider the following stack of city names:
(a) STACK: London, Berlin, Rome, Paris,______,_____
Describe the stack as the following opera ons take place:
(i) PUSH(STACK, Athens),
(ii) POP(STACK, ITEM)
(iii) POP(STACK, ITEM)
(iv) PUSH(STACK, Madrid)
(v) PUSH(STACK, Moscow)
(vi) POP(STACK, ITEM)

23. Write an algorithm to evaluate an arithme c expression using stack and show how
the expression 3*(5 - 3) will be evaluate.