SY

Corporate Office (Delhi): 44-A/1 Kalu Sarai (Sarvapriya Vihar), New Delhi-16, Ph: 011-45124612, 9958995830
Visit us at: www.madeeasy.in | E-mail us at: info@madeeasy.in

Delhi | Hyderabad | Noida | Bhopal | Jaipur | Lucknow | Indore | Pune | Bhubaneswar | Kolkata | Patna
EA
Lockdown Period
Open Practice Test Series
(Also useful for Other Exams)
E

CS & IT : COMPUTER SCIENCE & IT

AD

TEST No. -08 | PROGRAMMING AND DATA STRUCTURES

Read the following instructions carefully

1. This question paper contains 33 MCQ’s & NAQ’s. Bifurcation of the questions are given below:
M

17 to 28

29 to 33

2. Choose the closest numerical answer among the choices given.

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Multiple Choice Questions : Q.1 to Q.10 carry 1 mark each

Q.1 In a doubly linked list organization, insertion of a record in end involves modification of ____ for existing
list.
(a) one pointer (b) two pointer
(c) multiple pointer (d) no pointer

1. (a)
Consider the following doubly linked list
Head /° a 200 100 b 300 200 c 400 300 d 500 400 e /° 500 /°
100 200 300 400 500 600

After the insertion, only one pointer that is the next of node ‘e’ is modified to 600.
Two more pointers are added in the list, but in the existing list only one pointer is modified.

SY
Q.2 The minimum size that an array may require to store a binary tree with ‘n’ nodes is _______.
⎡ log (n +1)
⎤⎥
(a) 2 ⎢ 2 −1 (b) 2n – 1
(c) 2n – n + 1 (d) n + 1

2. (a) EA
In case of full or complete binary tree,
Minimum height (hmin) = ⎡log2 (n + 1)⎤

Hence, last element will be stored at 2hmin − 1

⎡ log2 (n +1)⎥⎤
Minimum size = 2 ⎢ − 1.
E
AD
M

2 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.3 Which of the following permutations can be obtained in the output (in the same order) using a stack
assuming that the input is the sequence 5, 7, 8, 4, 6 in that order?
(a) 6, 8, 4, 7, 5 (b) 6, 4, 5, 7, 8
(c) 6, 4, 7, 8, 5 (d) 7, 8, 4, 6, 5

3. (d)
6
4
(a) 6, 8, 4, 7, 5 8
7
5

After popping element 6, only 4 can be popped, hence this permutation is not possible.

SY
4
(b) 6, 4, 5, 7, 8 8
7
5

After performing pop operation on element 6, 4 now only element 8 can be popped.

(c) 6, 4, 7, 8, 5
EA 6
4
8
7
5

After 6, 4 elements are popped, now element 7 can only be popped iff 8 has already been popped.
E

(d) 7, 8, 4, 6, 5 pop (7) pop (8) pop (4) pop (6) pop (5)
7 8 4 6
5 5 5 5 5
AD
M

3 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.4 Suppose you are given an implementation of a queue of integers. The operations that can be performed on
the queue are:
1. is_empty (Q): return true if the queue is empty, false otherwise.
2. delete (Q): deletes the elements at the front of the queue and return its value.
3. insert (Q, i): inserts the integer i at the rear of the queues.
Consider the following function:
void f(Queue Q)
{
int i;
if (! is empty ( ) )
{
_______

SY
}
}
The following function must perform the operation that it must reverse the elements of queue (Q). Which of
the following options can be filled in the blank to perform the above operation.
(a) f(Q) (b) i = delete (Q)
insert (Q, i) f(Q)
i = delete (Q)
(c) i = delete (Q)
EA insert (Q, i)
(d) f(Q)
insert (Q, i) i = delete (Q)
f(Q) insert (Q, i)

4. (b)

4 5 8 1
E

f(4)

i=4 f(5) insert (4)

AD

i=5 f(8) insert (5)

i=8 f(1) insert (8)

i=1 empty insert (1)

1 8 5 4
M

Hence the above function changes the queue in the reverse order.

4 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.5 Which of the following is correct output for the program code given below?
code given below?
main ( )
{
void fun ( );
fun( );
fun ( );
}
void fun ( );
{
static int i = 1;
auto int j = 5;

SY
printf (“%d”, (i++));
printf (“%d”, (j++));
}
(a) 1 5 2 6 3 7 (b) 2 6 3 7 4 8
(c) 1 5 6 1 7 1 (d) 1 5 2 5 3 5

5. (d)
EA
An object whose storage class is auto, is reinitialized at every function call whereas an object whose
storage class static persist its value between different function calls.
When the function fun ( ) is called for the first time, value of i and j are printed and sequentially incremented.
During the second function call, i retains its incremented value whereas j is reinitialized, hence i will print
2 and j will print 5 again. The same will happen at third function call, i will print 3 and j will print 5.

Q.6 Consider the following program.

main ( )
E

{
int i, j;
int A[m] [n] = {{1, 2, 3} {4, 5, 6}}
AD

for (i = 0; i < n; i ++)

for (j = 0; j < m; j ++)
print f(“%d”, ∗ (A[j] + i));
}
For the output printed by the above program.
(a) 1 2 3 4 5 6 (b) 1 4 2 5 3 6
M

(c) 4 5 6 7 8 9 (d) 4 5 6 4 5 6

6. (b)
Here m represent the number of rows and n represents the number of column.
m = 2, n = 3
∗ (A[0] + 0) = A[0][0] = 1
∗ (A[1] + 0) = A[1][0] = 4
Similarly it will access all the element.
∴ 1 4 2 5 3 6 is the output printed by the program.

5 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.7 Which of the following statements is correct:

(a) Void pointers can be used for dereferencing.
(b) Arithmetic operations can be applied on void pointers.
(c) The default value of extern storage class is garbage value.
(d) A particular extern variable can be declared many times, but canbe initialized at only 1 time.

7. (d)
• Void pointers can’t be used for dereferencing because each variable type takes different amount of
memory.
• Since compiler can not know, after how many bytes is the next variables located, hence arithmetic
operations can’t be performed.
• Default value of extern storage class is 0.

SY
Q.8 The following C function takes a singly linked list as input argument. It prints its elements from the end
using with the help of some other data structure. Some part of the code is left blank.
typdef struct node
{
int value;
struct node ∗ next;
}
Node;
EA
void printlist (node ∗ head)
{
if (! head) return;
________
}
E
Choose the correct alternative to replace the blank line.
(a) printf (“%d”, head → data); (b) while (node! = Null)
printlist (head → next); { Node = Node → next
printf(“%d”, node → data);
AD

}
(c) printlist (head → next); (d) None of these
printf(“%d”, head → data);

8. (c)
Applying recursion, traverse the linked list till the last element, hence at every step, the element of the
M

linked list will be stored in the stack. While coming back, print the elements, hence the elements will be
start printing from the end.
if (!head) return;
printlist (head → next);
printf(“%d”, head → data);

6 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.9 Consider M1 and M2 be two complete binary tree which satisfy max-heap property, each of size ‘n’. What
is the time complexity to combine both M1 and M2 such that combine tree will be min heap tree?
(a) O (n log n) (b) O (n)
(c) O (n )2 (d) O (n2 log n)

9. (b)
Copy both M1 and M2’s element in new array of size 2n, then apply Build heap method to make min heap
tree which take O (2n) ≅ O(n) time.

Q.10 Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’.
What is the expected number of colliding pairs of elements, if we used simple uniform hashing?
(a) Θ(n2) (b) Θ(m2)
(c) Θ(n /m)
2 (d) Θ(n3/m2)

SY
10. (c)
Let Xi, j be an indicator random variable equal to 1 if element i and j collide and equal to 0 otherwise.
Simple uniform hashing is used i.e., the probability of element i-hashing to slots K is 1/m. Therefore the
probability that i and j both hashed to same slot Pr (Xi, j) = 1/m. Hence expected [Xi, j] = 1/m.

⎡n n ⎤
The E [number of collision pairs] = E ⎢ ∑ ∑ X i,j ⎥
EA
⎣⎢ i =1 j = i +1
n n
⎦⎥
n n
= ∑ ∑ E[X i,j ] = ∑ ∑ 1/m
i =1 j = i +1 i =1 j = i +1

n(n + 1)
= = Θ(n2 / m)
2m
E

Numerical Data Type Questions : Q. 11 to Q. 16 carry 1 mark each

Q.11 The maximum possible height of BFS tree, if BSF is run on a complete bipartite graph km,n, where m ≥ 1,
n ≥ 1 with starting vertex ‘S’ is _______.
AD

11. (2)

Since bipartite graph can be grouped into 2 group of vertices i.e., k3, 3.
A C E
M

B D F

Take start vertex is A.

A
1

2 B C D

E F

Max height of above BFS traversal is 2.

7 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.12 A 4-ary i.e., either has 0 children or has 4 children tree has 20 leaf nodes. Then the total number of nodes
in the tree are ________.

12. (27)

nm − 1
The total number of nodes = .
n −1
where, m is number of leaf nodes and n be ary of the tree.
Hence, substituting the values,

20 × 4 − 1 80 − 1 79
Number of nodes = = = = 26.3
4 −1 3 3
≈ 27 nodes

SY
Q.13 Consider the following program segment
int main ( )
{
char ∗ str = “GATECS”;
printf (“%d”, madeeasy (str));
return 0;
}
int madeeasy (int ∗ p1)
EA
{
int ∗ p2 = p1;
while (∗++p1);
return (p1 – p2);
}
E
The output of the above program will be ______. Assume that the object of data type int occupies 2 bytes.

13. (3)
AD

G A T E C S /°
1000 1001 1002 1003 1004 1005 1006

str

G A T E C S /°
1000 1001 1002 1003 1004 1005 1006
M

p1
p2

G A T E C S /°
1000 1001 1002 1003 1004 1005 1006

p1

G A T E C S /°
1000 1001 1002 1003 1004 1005 1006

p2 p1

Address of p1 − Address of p2 6
= = 3.
Size 2

8 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.14 The number of min heap trees are possible with 15 elements such that every leaf node must be greater
than all non-leaf nodes of the tree are ________.

14. (1935360)

a ⇒ Allways root is smaller (1 choice)

⇒ b and c are smaller than

b c
d e f g h i j k l m n o (2 choice)

e g ⇒ d, e, f, g are smaller than

d f
h i j k l m n o (4! = 24 choice)

j m n o ⇒ h i j k l m n o are greater than

SY
h i k l
non leaf node (8! = 40320 choice)

∴ All possibility = 40320 × 24 × 2 × 1

= 1935360

Q.15 Consider the following program along with push and pop operations on stack which can contain atmost 8
EA
element at a time:
void main ( )
{ stack S;
int num;
printf (“enter the input”);
scanf (“%d”, & num);
while (num! = 0)
{
E

if (!full (S))
{
push (S, num %2);
AD

num = num / 2;
}
else
{
printf (“stack overflow”);
exit (0);
M

}
}
The value 156 is given as input to the program then value present in stack from top to bottom will be ____.

15. (10011100)
The given program compute the binary value of decimal number 156.
Hence, the output received will be 10011100.

9 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.16 The output of following program is ________.

# include <stdio.h>
int main( )
{
static int a[ ] = {90, 98, 99, 96, 84, 70};
static int ∗p[ ] = {a+2, a+1, a, a+3, a+4, a+5};
static int ∗∗ S = {p+4, p+5, p+1, p, p+2, p+3};
int ∗∗∗ ptr; ptr = S + 2;
printf(“%d ”, ∗∗∗(ptr + 3) – ∗∗(p + 1));
}

16. (–2)

SY
a 90 98 99 96 84 70
a+0 a+1 a+2 a+3 a+4 a+5

p a+2 a+1 a a+3 a+4 a+5

p+0 p+1 p+2 p+3 p+4 p+5

S p+4 p+5 p+1 p p+2 p+3

EA
S+0

Ptr S + 2
S+1 S+2 S+3 S+4 S+5

∗∗∗ (ptr + 3) – ∗∗(p + 3) = (∗(∗(∗(S + 3 + 2)))) – (∗ (∗(p + 1)))

= (∗(∗(p + 3))) – (∗(a + 1))
= 96 – 98 = –2

Multiple Choice Questions : Q.17 to Q.28 carry 2 marks each

E

Q.17 Consider the following statement:

S1: Merge sort on linked list take O(n log n) time to sort input of length n.
AD

S2: Merge sort on linked list give better space complexity then on array.
S3: Inplace merge sort on array will take O(n2) time.
Which of the following is correct?
(a) only S1 (b) only S1 and S2
(c) S1, S2 and S3 (d) None of these

17. (c)
M

• Merge sort on linked list take O(n log n) time to sort input of length n.
• Merge sort on linked list give better space complexity then on array.
• Inplace merge sort on array will take O(n2) time.

10 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.18 Consider the following C program segment:

# include <stdio.h>
main( )
{
static char ∗s[ ] = {“madeeasy”, “online”, “test”, “series”};
char ∗∗ptr[ ] = {s + 3, s + 2, s + 1, s}, ∗∗∗ p;
p = ptr;
++p;
Printf(“%s”, ∗ – – ∗++p + 3)
}
What will be printed by the program?
(a) line (b) ies

SY
(c) test (d) eeasy

18. (d)
In this problem we have an array of char pointers pointing to start of 4 strings i.e.,

m a d e e a s y o n l i n e t e s t s e r i e s

s s+0 s+1 s+2 s+3

EA
We have ptr which is pointer to a pointer of type char and a variable p which is a pointer to a pointer of type
char.

ptr s+3 s+2 s+1 s

ptr + 0 ptr + 1 ptr + 2 ptr + 3

p = ptr; p ptr
E

++p; p ptr+1
Printf(“%s”, ∗ – – ∗ ++ p + 3);
AD

In printf statement the expression is evaluated ∗++p cause gets value (s+1) then now pre-decrement is
executed and we get (s+1) – 1 = s. The indirection pointer now gets the value from the array of s and add
3 to the starting address. The string is printed starting from this position. Thus, the output is ‘eeasy’.
M

11 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.19 Consider the following code on binary tree where p and q are two given nodes of that tree.
Struct node
{
int data;
struct node ∗ left;
struct node ∗ right;
}
typedef node NODE;
NODE find (NODE root, NODE p, NODE q)
{
if (!root)
return NULL;

SY
if (root == p ⎪⎪ root == q)
return root;
else
{
NODE l = find (root → left, p, q);
NODE r = find (root → right, p, q);
if (l && r)
return root;
EA
else if (l)
return l;
else if (r)
return r;
else if (l = r = NULL)
E
return NULL;
}
}
AD

The value returned by the function “find” when a pointer to the root of a non-empty tree is passed as
argument is
(a) The lowest common ancestor of two node.
(b) The highest common ancestor of two nodes.
(c) The largest common successor of two nodes.
(d) Node of these
M

12 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

19. (a)
Let’s traverse the code on the given tree.

B C

D E H I

F G

Let ‘p’ be D and ‘q’ be E.

Find (A, D, E) ⇒ Output ⇒ B

SY
λ= B λ= Find (B, D, E) r = Find (C, D, E) r = NULL

λ= D λ= E λ= NULL r = NULL
λ= Find (D, D, E) r = Find (E, D, E) λ= Find (H, D, E) r = Find (I, D, E)
λ=
λ= r = N

LL r=

LL
= NU NU
NU
λ= r LL
r=
ULL

λ=
EA
λ= Find (NULL, D, E) r = Find (NULL, D, E) λ= Find (NULL, D, E)

Consider nodes ‘D’ and ‘E’, they have two ancestors node ‘A’ and node ‘B’. ‘B’ is the lowest common
r = Find (NULL, D, E)

ancestor and that is the output.

Hence, the value returned by the function is lowest common ancestor of two nodes.
E
AD
M

13 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.20 Consider the following program implemented on tree T where T is

2

1 3

typedef struct tnode {

int key ;
struct tnode ∗ left, ∗ right ;
} ∗ Node ;
Void search (Node node)
{
struct node ∗ ptr, ∗q;
if (node == Null) return;
search (node → left);

SY
search (node → right);
ptr = node → right;
node → right = new Node (node → data);
node → right → right = ptr;
} EA
If the root of the above tree is passed to the above function, what is the level order traversal of output tree
produced by above function?
Note: newNode is a function which creates new node.
(a) 2 2 1 1 3 3 (b) 2 2 3 3 1 1
(c) 2 1 2 1 3 3 (d) 2 1 2 1 2 3

20. (c)

2
E

1 2
AD

1 3

This will be the tree after execution of above code.

The level order traversal of the tree will be 2, 1, 2, 1, 3, 3.
M

14 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.21 Consider the AVL tree ‘T’ in which left subtree contain quarter of the maximum number of nodes possible
in the balanced AVL tree of height ‘h’ and right subtree consist of one fifth of the maximum number of
nodes possible in AVL tree of height ‘h’.
Assume that tree ‘T’ may or may not be height balanced at present. What is the total maximum possible
number of nodes in ‘T’.

(a)
20
(
7 h +1
2 −1 −1) (b) (
9 h +1
20
2 −1 +1 )
(c) (
7 h +1
30
2 +1 ) (d) (
9 h +1
30
2 +1 −1 )
21. (b)

SY
h+1
2 –1 1 h+1
4 (2 –1)
5

⎛ 2h +1 − 1⎞ 1 h +1
( )
Total = ⎜
⎝ 4 ⎠ 5
EA⎟ + 2 −1 +1

=
20
(
9 h +1
2 −1 +1 )
⎛ m⎞
Q.22 Consider the following function that comutes the value of ⎜ ⎟ correctly for all legal values m and n (m ≥ 1,
⎝n⎠
E

n ≥ 0) 0 and m > n)
int func (int m, int n)
{
AD

if [(n == 0) ⎪⎪ (m == n) return 1;
else return (E);
}
In the function, which of the following is the correct expression for E?
(a) func (m – 1, n) + func (m – 1, n – 1) (b) func (m – 1, n + 1) + func (m – 1, n)
(c) func (m, n) + func (m, n – 1) (d) None of these
M

22. (a)
Take m = 4 and n = 2
6
func (4, 2)

3 3
func (3, 2) func (3, 1)

1 2 2 1
func (2, 2) func (2, 1) func (2, 1) func (2, 0)

1 func (1, 1) func (1, 0) func (1, 1) func (1, 0)

1 1 1 1
So, correct vaue of E is func (m – n, n) + func (m – 1, n – 1).

15 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.23 What is the average number of probs requires when inserting an element into an open-address hash table
with load factor α (assume uniform hashing)?
1 1
(a) (b)
1− α 1+ α
1 2
(c) (d)
α 2−α

23. (a)
An element is inserted only if there is blank place in the table, and thus α < 1. Inserting a key requires an
unsuccessfuls search followed by placement of the key in the first empty slot found.
Thus, expected number of probes is [1 / 1 – α].

Q.24 What will be the output of the following C program:

SY
# include <stdio.h>
void print 1 (void)
{
static int x = 10;
x+ = 5;
printf (“%d”, x);
}
Void print 2 (void)
EA
{
static int x;
x = 10;
x+ = 5;
print f (“%d”, x);
E

}
int main ( )
{
AD

print 1( ); print 1( ); print 2( ); print 2 ( );

return 0;
}
(a) 15, 20, 25, 30 (b) 15, 20, 15, 20
(c) 15, 15, 15, 15 (d) None of these

24. (d)
M

• print 1( ): x = 10 + 5 = 15; since the variable is of static storage class, hence it will retain its value
between different function calls.
• print 1( ): x = 15 + 5 = 20; since it has retained its value 15.
• print 2( ): x is defined again inside the function and hence will print, x = x + 5 = 10 + 5 = 15. Again
when the function will be called, x = 10 + 5 = 15. Here second time also x = 10 will be there because
it is not initialized at the time of definition.
Hence output 15, 20, 15, 15.

16 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.25 Consider a linked list of length n is implemented using a circular array P[0, n – 1], two variables first and
last are used to point the first and last element of the list present in array respectively i.e., first = P and last
= (P + x) mod n, where x is the size of linked list.
Consider the following operations:
S1: Delete kth element in linked list.
S2: Reverse the elements of linked list.
Which of the following represent the time complexity of above two operations respectively?
(a) O(n), O(n) (b) O(n), O(1)
(c) O(1), O(1) (d) O(1), O(n)

25. (b)
Operation 1

SY
• Search kth element in array take O(1) time.
• Delete take O(1) time
• Shift all element to left if space is there O(n)
Total time = O(1) + O(1) + O(n) = O(n)
Operation 2
• Take constant time just change first = (P – x)mod n last = P.
EA
Q.26 Consider the following program segment:
# include <stdio.h>
int main ( )
{
char string1 [15] = “GATE, 2017”;
char string2 [15] = “GATE, 2017”;
if (string1 == string2)
E

printf (“Two strings are equal ”);

else
printf (“Two strings are unequal”);
AD

return 0;
}
Which of the following is correct?
(a) Two strings are equal (b) Two strings are unequal
(c) Compilation error (d) Run time error
M

26. (b)
By comparing string1 and string2, we are not comparing the actual data of the string, instead the starting
address of both strings will be compared.
Hence, it will print “Two strings are unequal”.
To compare the actual data of the strings,
if (∗ string1 == ∗ string2)
then will get the output: “Two strings are equal”.

17 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.27 Consider the following program:

int foo (struct node ∗ tree)
{
if (tree == 0)
return 0;
int  h = ht (tree → left);
int rh = ht (tree → right);
int  d = foo (tree → left);
int rd = foo (tree → right);
return max ( h + rh + 1, max ( d, rd));
}
int ht (struct node ∗ node)

SY
{
if (node == Null)
return 0;
return 1 + max (ht (node → left), ht (node → right));
}
The value returned by foo when a pointer to the root of a binary tree is passed as its argument is
EA
(a) Number of leaf nodes in the tree
(b) Difference in the number of nodes in left and right
(c) Depth of the tree
(d) Diameter (maximum number of nodes on the longest path between two leaf nodes) of the tree

27. (d)
Consider the following tree,
A
E

B C

D
AD

The diameter of the tree will be 4, consider from node ‘D’ to ‘C’.
Hence, it calculate the diameter of the tree.

Q.28 Let P be the singly linked list. What will be the complexity of the best known algorithm to check whether
the linked list is palindrome or not?
(a) O(n2) (b) O(n log n)
(c) O(n) (d) O(log n)
M

28. (c)
The algorithm that can be applied:
• Find the middle element of the list.
• Reverse the elements of the list from the middle element till the end.
• Compare the two halves of the list.
The above algorithm will take O(n) time complexity.

18 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Numerical Data Type Questions : Q.29 to Q.33 carry 2 marks each

Q.29 Consider a binary tree whose pre-order and in-order traversals are CBAFDEHGJI AND ABCDEFGHIJ.
What will be the minimum number of rotations to convert the tree into an AVL tree?

29. (1)
Constructing BST with the help of pre-order and in-order traversals:
Pre-order: CBAFDEHGJI
In-order: ABCDEFGHIJ

B F

SY
A D H

E G J

The tree become unbalanced at the root node. Hence applying RR rotation, we get

C
EA F

B F C H

A D H B D G J
E
G J A E I
E

Hence after 1 rotation the tree travers into an AVL tree.

AD

Q.30 What is the output of the following program?

# include <stdio.h>
# define MUL (a, b) a ∗ b
# define pow (a) a ∗ a
int main ( )
M

{
int a = 3;
int b = 2;
printf (“%”, MUL (MUL (a+1, b), pow (b + 1)));
return 0;
}

30. (10)
MUL (MUL (a + 1, b), pow (b + 1))
MUL ([a + 1 ∗ b], [b + 1 ∗ b + 1])
⇒ a+1∗b∗b+1∗b+1
⇒ 3+1∗2∗2+1∗2+1
⇒ 3 + 4 + 2 + 1 = 10

19 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.31 Consider an efficient implementation of a data structure STACK-MAX that support an operation “max( )”
that reports the current maximum among all elements in the stack. Normal stack operations i.e., push,
pop are also to be supported.
The size of above data structure after performing following operation push (5), push (6), push (7), pop,
max, push (6), push (8), pop, pop, max, push (5) is ________ (in bytes). Assume that an integer can be
stored in 4 bytes.

31. (24)
Implement the stack where each entity stores two values:
1. Value = Current number.
2. CurMax = maximum of current number and numbers below the current number.
To implement:

SY
Push: If stack size is 0, add an entry with value = current number and curmax = current. If stack size >0
add an entry with value = current number and curmax = max (current number, curmax of top value on
stack).
Pop: Same as normal stack.
Max: Return curmax of top entry on stack.
Every entry will be of 8 B. EA
After all the operation 24 B are needed.

5 6
8 8 Max = 6
6 6
7 7 Max = 6
6 6
5 5
E

Value Curmax
AD
M

20 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY

 Delhi | Noida | Bhopal | Hyderabad | Jaipur | Indore
Lucknow | Pune | Bhubaneswar | Kolkata | Patna GTOCS17

Q.32 The number of ways in which the numbers 1, 2, 3, 4, 5 can be inserted into binary heap. Such that resulted
binary heap is max heap ________.

32. (8)
Number max heap with n node is given by
f(0) = 1
f(1) = 1
⎛ n − 1⎞
f(n) = ⎜ ⎟ f(L) f(R)
⎝ L ⎠
where L = Number of left subtree nodes
R = Number right subtree nodes.
Max heap structure like

SY
5

So, L = 3, R = 1 EA
⎛ 1⎞
f(2) = ⎜ ⎟ f(1) f(0) = 1
⎝ 1⎠

⎛2⎞
f(3) = ⎜ ⎟ f(1) f(1) = 2
⎝ 1⎠

⎛3⎞
f(4) = ⎜ ⎟ f(2) f(1) = 3
⎝2⎠
E

⎛4⎞
f(5) = ⎜ ⎟ f(3) f(1) = 4 × 2 = 8
⎝3⎠
AD

Q.33 A priority queue containing characters [A – Z] is implemented as a heap stored in an array. The precondition
states that this priority queue can not contain duplicate elements. The priority queue can hold 10 elements,
as shown in the figure. The number of values that might be stored in array position 7 - 9 so that properties
of heap are satisfied is _____.
Z F J E B G H
0 1 2 3 4 5 6 7 8 9
M

33. (3)
Constructing the heap:
Z
F J

E B G H

Sinse, Z is at the root of the heap, hence it can be considered as a max heap.
The left child that is ‘F’ is the parent of the subtree whose root is ‘F’. Hence the values of the subtree can’t
be greater than ‘F’. Now element ‘E’ and ‘B’, have already been inserted and no duplicacy is allowed.
Hence, only three elements ‘A’ ‘C’ and ‘D’ can be inserted into the heap.

„„„„

21 • PDS (Basic Level) www.madeeasy.in © Copyright : MADE EASY