Programming and Data Structures Test 1

Result

Programming and Data Structures Test 1

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
2 / -0.33

What is the maximum height of any AVL tree with 20 nodes?
NOTE: Height of tree with single node is 0.

A
5-5

B
54-51

C
57-56

D
59-52

Solution

Concepts:
An AVL tree is a self-balancing binary search tree.
In an AVL tree, the heights of the two-child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
Formula:
N(H) = N(H-1) + N(H-2) + 1
where H is height and N(H) is the minimum number of nodes in the AVL tree.
Calculation:
Base conditions: N(0) = 1, N(1) = 2
N(2) = N(1) + N(0) + 1
∴ N(2) = 2 + 1 + 1 = 4
N(3) = N(2) + N(1) + 1
∴ N(3) = 4 + 2 + 1 = 7
N(4) = N(3) + N(2) + 1
∴ N(4) = 7 + 4 + 1 = 12
N(5) = N(4) + N(3) + 1
∴ N(5) = 12 + 7 + 1 = 20
Therefore the maximum height of any AVL tree with 20 nodes is 5.
Question 2
2 / -0.33

Which one of the choices given below would be printed when the following program is executed?
#include<stdio.h>
struct node {
int i;
char *s;
}tb[] = {1, "poor", 10, "average", 3, "good", 4, "very good", 5, "excellent"};
int main()
{
struct node *p = tb;
printf("%s", (++p+2)-> s);
return 0;
}

A
excellent

B
very good

C
good

D
average

Solution

Assume block 1 is placed at address location 1000:
tb:
Block
i
s
block 1 (1000)
1
poor
block 2 (1016)
2
average
block 3 (1032)
3
good
block 4 (1048)
4
very good
block 5 (1060)
5
excellent

Size of block = 16 byte (might vary depending upon the system)
*p = tb = 1000
(++p+2)-> s = (100 + 3 × size of block) -> s = 1048 -> s = very good
Output: very good
Question 3
2 / -0.33

Consider a binary tree which consist of 255 nodes. Height of a tree is 1 if it consists of single node. What is the minimum height of the tree?

A
6

B
7

C
8

D
9

Solution

If n is number of nodes and h is minimum height of in a binary search tree, then
2h – 1 = n (height of the root node is 1)
2h – 1 = 255
2h= 256
∴2h= 28
∴ h = 8
In a full binary tree number of nodes is 255 then the height of the tree = 8
Question 4
2 / -0.33

What is the output of the below given code
#include<stdio.h>
#include<string.h>
int main()
{
char s1[] = "TESTBOOk";
char s2[] = "TESTBOOK";
printf("%d",strcmp(s1,s2));
return 0;
}

A
-1

B
0

C
1

D
32

Solution

strcmp(s1,s2)
Return value
s1 is less than s2
-1
s1 and s2 are equal
0
s1 is greater than s2
1

s1
T
E
S
T
B
O
O
k
s2
T
E
S
T
B
O
O
K
return
0
0
0
0
0
0
0
1

In s1 ‘k’ is having an ASCII value of 107 and In s2 ‘K’ is having an ASCII value of 75
Therefore, s1 is greater than s2 and hence the output is 1.
Important Points:
32 is not the answer.
Kindly execute the code and see the result
Also, specify which application software one has used if getting the different result from the given answer.
Question 5
2 / -0.33

Consider the following C program:
#include <stdio.h>
int main ( )
{
int A[ ] = {4, 3, 2, 1, 5, 6, 7, 9, 10, 11, 12, 0 }, *ptr = A + 6;
printf (“ % d \n”, 3[ptr]);
return 0;
}
The number that will be displayed on execution of the program is _________.

A
11-11

B
114-111

C
117-116

D
119-112

Solution

Assume, starting array address is 100 and each integer of 2 bytes.
Address
100
102
104
106
108
110
112
114
116
118
120
122
Index
0
1
2
3
4
5
6
7
8
9
10
11
Element
4
3
2
1
5
6
7
9
10
11
12
0

ptr

3[ptr]

ptr = A + 6× sizeof(int) = 100 + 6 × 2 = 112
3[ptr] = ptr[3] = * (ptr + 3× sizeof(int)) = *(112 + 3 × 2) = *( 118) = 11
The number that will be displayed on execution of the program is 11

Question 6

2 / -0.33

Consider the following C program:

#include <stdio.h>

int swap (int *p, int *q)

{

*p = 3*(*p) + (*q);

return *p;

}

int main ( )

{

int a = 12, b = 21;

a = swap(&b, &a);

b = swap(&a, &b);

printf("%d\n", b);

}

The value printed by the program is _________.

300-300

3004-3001

3007-3006

3009-3002

Solution

Integer	a	b
Value	12	21
address	100	200

main()

swap(int *p, int *q)

a = swap(200, 100)

∴ a = 75

*p = 21 and *q = 12

*p = 3 × (21) + (12) = 75

return 75

(*p = b = 54)

b = swap(100, 200)

∴ b = 300

printf ("%d\n", b); // output 300

*p = 75 and *q = 75

*p = 3 × (75) + (75) = 300

return 300

Important Point:

Run the code to verify the answer

Question 7
2 / -0.33

Carefully observe the below given queue
REAR
22
57
96
68
19
15
28
FRONT

How many dequeue operations needed to delete the largest element from the queue?

A
1

B
3

C
5

D
7

Solution

Deletion takes place at the FRONT of the queue.
96 is the largest element in the given queue.
1^st deque operation:
REAR
22
57
96
68
19
15
FRONT

28 is deleted
2^nd deque operation:
REAR
22
57
96
68
19
FRONT

15 is deleted
3^rd operation:
REAR
22
57
96
68
FRONT

19 is deleted
4^th operation:
REAR
22
57
96
FRONT

68 is deleted
5^th operation:
REAR
22
57
FRONT

96 is deleted
Therefore, the number of deque operation needed to delete 96 is 5.
Question 8
2 / -0.33

Consider a two dimensional array X[-10…5, 7….15] in which staring location is at 250. If every data of given array takes 4 byte of space and store in column major order, then what will be the location of A[2][10]

A
490-490

B
4904-4901

C
4907-4906

D
4909-4902

Solution

Concepts:
Range of given array: [-10...5,7......15]
Old location (Given): A[2][10]
A[-10][7] = 250
Number of rows: 5 – (–10) + 1= 16
Number of columns: 15 – 7 + 1 = 9
Array size: A_{16 x 9}
New range: [0 ...15, 0 ... 8]
New location: A[2 + 10][10 -7] = A[12][3]
Size of data = 4
A[0][0] = 250
Formula:
column major order:
A[m][n] = A[0][0] + (16n + m) × Size of cell
Calculation:
A[12][3] = 250 + (16 × 3 + 12) × 4
A[12][3] = 250 + 60 × 4
A[12][3] = 490
Old location of A[-10][7] = New location of A[12][3] = 490
Question 9
2 / -0.33

Which of the following statement is/are not true?
I. First-in-first out types of computations are efficiently supported by stacks.
II. Implementing queues on a linear array with two indices is more efficient then implementing queues on a circular array.
III. The best data structure to check whether an arithmetic expression has balanced parenthesis is a queue.

A
Only I

B
Only I and III

C
Only II and III

D
I, II and III
Solution
- First-in-first out types of computations are efficiently supported by queue while first-in-last out types of computations are efficiently supported by stacks.
- Implementing queues on a linear array with two indices is less efficient then implementing queues on a circular array.
- The best data structure to check whether an arithmetic expression has balanced parenthesis is a stack.
Statement I, II and III is false, that is, not true.
Question 10
2 / -0.33

What is the postfix expression corresponding to the infix expression?
x – y + z ^ a × b ^ c / d + e
In the above expression, ^ is exponentiation operator, × is multiplication operator, / is division operator, + is addition operator and – is subtraction operator also ×, + and – are left associative wile ^ is right associative.

A
x y – a x ^ c b ^ × / d + e +

B
x y - z a ^ b c ^ × / d + e +

C
x y - z a ^ b c ^ × d / + e +

D
x y - z a ^ c b ^ × d / + e +

Solution

x – y + z ^ a × b ^ c / d + e
x – y + z ^ a × (b c ^) / d + e
x – y + (z a ^) × (b c ^) / d + e
x – y + ((z a ^) (b c ^) ×) / d + e
x – y + (((z a ^) (b c ^) ×) d /) + e
(x y -) + (((z a ^) (b c ^) ×) d /) + e
((x y -) (((z a ^) (b c ^) ×) d /) +) + e
((x y -) (((z a ^) (b c ^) ×) d /) +) e +
x y - z a ^ b c ^ × d / + e +
Important points:
Bracket is used just to avoid confusion and hence it is not included in the answer:
Question 11
2 / -0.33

Consider the following C program:
#include<stdio.h>
#include<string.h>
int main()
{
    char *t = "GATECSITtwenty-20";
    char *p = t;
    printf("%d", (int)strlen(p + 3[p]-4[p] + 1));
    return 0;
}
The output of the above code is ____.

A
14-14

B
144-141

C
147-146

D
149-142

Solution

Character
G
A
T
E
C
S
I
T
t
w
e
n
t
y
-
2
0
\0
Address
100
101
102
103

116

3[p] = p[3] = ‘E’
4[p] = p[4] = ‘C’
ASCII of A = x
∴ ASCII of ‘E’ = x + 4
∴ ASCII of ‘C’ = x + 2
p + 3[p] - 4[p] + 1 = x + 4 – (x + 2) + 1 = p + 3
Output of strlen(ECSITtwenty-20)) = 14

Question 12

2 / -0.33

Consider the following C program:

#include <stdio.h>

int main () {

float s = 0.0, m = 1.0, n = 2.0;

while (n/m>= 0.03125) {

m = m + m;

s= s + n/m;

printf(" % .4f \n", s); //line 7

}

return 0;

}

The number of times line 7 will be executed is _______.

7-7

74-71

77-76

79-72

Solution

While () loop condition

Iteration Number

Inside while() loop

n = 2. 0, m= 1.0

n/m = 2.0 > = 0.03125 (TRUE)

1^st iteration

m = 2.000000

s = 1.0000 (printed)

n = 2. 0, m = 2.0

n/m = 1.0 > = 0.03125 (TRUE)

2^nd iteration

m = 4.000000

s = 1.5000 (printed)

n = 2. 0, m = 4.0

n/m = 0.5 > 0.03125 (TRUE)

3^rd iteration

m = 8.000000

s = 1.7500 (printed)

n = 2. 0, m = 8.0

n/m = 0.25 > = 0.03125 (TRUE)

4^th iteration

m = 16.000000

s = 1.8750 (printed)

n = 2. 0, m = 16.0

n/m = 0.125 > = 0.03125 (TRUE)

5^th iteration

m = 32.000000

s = 1.9375 (printed)

n = 2. 0, m = 32.0

n/m = 0.0.625 >= 0.03125 (TRUE)

6^th iteration

m = 64.000000

s = 1.9688 (printed)

n = 2. 0, m = 64.0

n/m = 0.03125 >= 0.03125 (TRUE)

7^th iteration

m = 128.000000

s = 1.9844 (printed)

n = 2. 0, m = 128.0

n/m = 0.03125 >= 0.015625 (FALSE)

while loop terminated

Therefore, number of times line 7 will be executed is 7.

Question 13
2 / -0.33

Consider the below given code?
#include <stdio.h>
int main()
{
int ary[ ] = {1, 3, 5, 7, 9, 11};
int k, count = 0, *p = ary + 4;
for (k = 0; k < 6; k++)
count = count + (*p - k) - *(p - k);
printf ("%d \n",count);
return 0;
}
What is the value printed after the code execution?

A
14-14

B
144-141

C
147-146

D
149-142

Solution

Iterating the for loop:
i
count
0
0
1
1
2
3
3
6
4
10
5
14

Therefore, the value of count printed is 14
Important Point:
Run the code to verify the answer

Question 14

2 / -0.33

What is the output in a 32 bit machine with 32 bit compiler?

#include<stdio.h>

rer(int **ptr2,int **ptr1)

{

int*ii;

ii=*ptr2;

*ptr2=*ptr1;

*ptr1=ii;

**ptr1 *= **ptr2;

**ptr2 += **ptr1;

}

void main( )

{

int var1=5, var2=10;

int *ptr1=&var1, *ptr2=&var2;

rer(&ptr1, &ptr2);

printf(“%d %d “,var2, var1);

}

60 70

50 50

50 60

60 50

Solution

Concept –

void main()	Suppose var1 address 1000	var2 address 2000
int var1=5, var2=10;	var1 = 5	var2 = 10
int ptr1=&var1, ptr2=&var2;	ptr1 = 1000 (pointer storing address of var1)	ptr2 = 2000 (pointer storing address of var2)
rer(&ptr1,, &ptr2);	Call to the function describes in table below

rer(int ptr2,int ptr1)	ii	ptr2	ptr1	var1	var2
int* ii;	-	1000	2000	5	10
ii = *ptr2;	1000	1000	2000	5	10
ptr2 = ptr1;	2000	2000	2000	5	10
*ptr1 = ii;	2000	2000	1000	5	10
*ptr1 = **ptr2	2000	2000	1000	5× 10 = 50	10
ptr2 += ptr1;	2000	2000	1000	50	60

Hence, printf(“%d %d “,var2, var1); will print 60 and 50.

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Block	i	s
block 1 (1000)	1	poor
block 2 (1016)	2	average
block 3 (1032)	3	good
block 4 (1048)	4	very good
block 5 (1060)	5	excellent

strcmp(s1,s2)	Return value
s1 is less than s2	-1
s1 and s2 are equal	0
s1 is greater than s2	1

Address	100	102	104	106	108	110	112	114	116	118	120	122
Index	0	1	2	3	4	5	6	7	8	9	10	11
Element	4	3	2	1	5	6	7	9	10	11	12	0
							ptr			3[ptr]

i	count
0	0
1	1
2	3
3	6
4	10
5	14

Programming and Data Structures Test 1

Result

Programming and Data Structures Test 1

Score

-

Rank

-

SHARING IS CARING

Question 1

5-5

54-51

57-56

59-52

Solution

Question 2

excellent

very good

good

average

Solution

Question 3

6

7

8

9

Solution

Question 4

-1

0

1

32

Solution

Question 5

11-11

114-111

117-116

119-112

Solution

Question 6

300-300

3004-3001

3007-3006

3009-3002

Solution

Question 7

1

3

5

7

Solution

Question 8

490-490

4904-4901

4907-4906

4909-4902

Solution

Question 9

Only I

Only I and III

Only II and III

I, II and III

Solution

Question 10

x y – a x ^ c b ^ × / d + e +

x y - z a ^ b c ^ × / d + e +

x y - z a ^ b c ^ × d / + e +

x y - z a ^ c b ^ × d / + e +

Solution

Question 11

14-14

144-141

147-146

149-142

Solution

Question 12

7-7

74-71

77-76

79-72

Solution