Programming and Data Structures Test 2

Result

Programming and Data Structures Test 2

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 number of binary search trees possible with 9 distinct keys?

A
4862-4862

B
48624-48621

C
48627-48626

D
48629-48622

Solution

Data:
number of distinct keys = n = 9
Formula:
Number of binary search trees = \(^{2n}C_n \over n+1\)
Calculation:
Number of binary search trees = \(^{18}C_9\over 10\) = 4862
Question 2
2 / -0.33

A program X reads in 300 integers in the range [0..100] representing the %attendance of 300 students. It then prints the frequency of each %attendance above 25. What would be the best way for X to store the frequencies?

A
An array of 300 integers

B
An array of 100 integers

C
An array of 75 integers

D
An array of 25 integers

Solution

Output is the frequency of each%attendance above 25.
int result [75] //
To store frequencies of ages above 25. We can ignore ages below 25 so take an array of 75 numbers where a[0] corresponds to 26, a[1] corresponds to 27, …, a[74].
Hence An array of 75 integers is enough.
Question 3
2 / -0.33

If a queue is implemented using two stacks. In enqueue operation, all the elements are pushed from the first stack to the second stack. In dequeue operation pop an element from 1st stack.
Which of the following is/are true?

A
Time complexity of enqueue is O(n)

B
Time complexity of enqueue is O(1)

C
Time complexity of dequeue is O(1)

D
Time complexity of dequeue is O(n)

Solution

Enqueue:
While 1st stack is not empty, push everything from 1st to 2nd stack.
Push an element to 1st stack.
Push everything back to 1st stack.
Here time complexity will be O(n)
Dequeue:
while 1st stack is not empty then Pop an item from stack1 and return it
Here time complexity will be O(1)
Therefore option 1 and 3 are correct.
Question 4
2 / -0.33

A function f defined on stack of integer satisfies the following properties f(empty) = 0 and f (push (S, i)) = max (f(s), 0) + i for all stacks S and integer i.
After pushing integers 2, -3, 2, -1, 2 in order from bottom to top. f(s) returns the top of the stack. What is f(s)?

A
6

B
4

C
3

D
2

Solution

Initially S is empty,
∴ f(s) = 0
f(push(S, 2)) = 2
f(push(S, -3)) = max (2, 0) – 3 = -1
f(push (S, 2)) = max (-1, 0) + 2 = 2
f(push (S, -1)) = max (2, 0) – 1= 1
f(push (S, 2)) = max (1, 0) + 2 = 3
Question 5
2 / -0.33

What is the return output of the following C program segment?
char c= '2';
switch(c)
{
case '1': printf("C program, ");
case '2':
case '3': printf("Java program, ");
case '4' :
case '5': break;
default: printf("No program");
}
return 0;
}

A
Error

B
Java program, No program

C
Java program,

D
C program, Java program, No program

Solution

switch('2')
control will come to case '2'
since case '2': doesn't have break statement to will go to case '3'
In case '3': Java program, is printed
since case '3': doesn't have break statement to will go to case '4'
From case '4' to it will to case '5' break will execute and the switch will terminate.
Output: Java program,
Question 6
2 / -0.33

Which of the following is/are true with respect to stacks and queues where where front points to the index where deletion is done and the rear points to the index where insertion is done in queue?

A
Breadth first search algorithm employs queue data structure while depth first search uses stack data structure.

B
The necessary condition to detect if a circular queue of capacity (n-1) is full is (rear+1) mod n = front

C
Depth first search algorithm employs queue data structure while breadth first search uses stack data structure.

D
Time complexity of converting a fully parenthesized infix expression to postfix expression is O(n).

Solution

Concept:
The breadth-first search algorithm uses a queue data structure while the depth-first search algorithm uses a stack data structure in its implementation.
The necessary condition to detect if a circular queue of capacity (n-1) is full is (rear+1) mod n = front
The time complexity of converting a fully parenthesized infix expression to postfix expression is O(n), that is, traverse the equation
Conclusion:
Options1, 2 and 4 are correct

Question 7

2 / -0.33

Consider the following C program

main ( )

{

int N, x;

scanf (“% d”, &N);

x = 0;

while (N > 0)

{

x = x + 1 – N % 2;

N / = 2;

}

printf(“% d”, x)

}

What is the sum of the smallest three values of N for which the value printed is 5?

163-163

1634-1631

1637-1636

1639-1632

Solution

Take N = 32

N = 32	while (TRUE) x = 0 + 1 – 0
N = 16	while (TRUE) x = 1 + 1 – 0
N = 8	while (TRUE) x = 2 + 1 – 0
N = 4	while (TRUE) x = 3 + 1 – 0
N = 2	while (TRUE) x = 4 + 1 – 0
N = 1	while (TRUE) x = 5 + 1 – 1 = 5
N = 0	while (FALSE)

Output will be same for 65 and 66 as well.

For N = 32 it will print '5'

For N = 65 it will print '5'

For N = 66 it will print '5'

Hence, the sum of smallest three values of N = 32 + 65 + 66 = 163

Question 8
2 / -0.33

The following postfix expression with single digit operands in evaluated using a stack
4 2 5 ^ * 14 7 / - 7 5 * +
Note that ^ is exponentiation operator, * is multiplication operator, / is division operator, + is addition operator and – is subtraction operator

A
161-161

B
1614-1611

C
1617-1616

D
1619-1612

Solution

4 2 5 ^ * 14 7 / - 7 5 * +
Push: 9, 2 and 5
4
2
5

Pop: 2 and 5
Perform operation: 2 ^ 5 = 32
Push: 32
4
32

Pop: 32 and 4
Perform operation: 4 × 32 = 128
Push: 128
Also push: 14 and 7
128
14
7

Pop: 7 and 14
Perform operation: 14 ÷ 7 = 2
Push: 2
128
2

Pop: 128 and 2
Perform operation: 128 - 2 = 126
Push: 126
Also push: 7 and 5
126
7
5

Pop: 5 and 7
Perform operation: 7 × 5 = 35
Push: 35
126
35

Pop: 35 and 126
Perform operation: 126 + 35 = 161
Push: 161
161

After evaluating: 161 is present onto the stack
Hence 161 is the answer for the given postfix operation.

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Programming and Data Structures Test 2

Result

Programming and Data Structures Test 2

Score

-

Rank

-

SHARING IS CARING

Question 1

4862-4862

48624-48621

48627-48626

48629-48622

Solution

Question 2

An array of 300 integers

An array of 100 integers

An array of 75 integers

An array of 25 integers

Solution

Question 3

Time complexity of enqueue is O(n)

Time complexity of enqueue is O(1)

Time complexity of dequeue is O(1)

​Time complexity of dequeue is O(n)

Solution

Question 4

6

4

3

2

Solution

Question 5

Error

Java program, No program

Java program,

C program, Java program, No program

Solution

Question 6

Breadth first search algorithm employs queue data structure while depth first search uses stack data structure.

The necessary condition to detect if a circular queue of capacity (n-1) is full is (rear+1) mod n = front

Depth first search algorithm employs queue data structure while breadth first search uses stack data structure.

Time complexity of converting a fully parenthesized infix expression to postfix expression is O(n).

Solution

Question 7

163-163

1634-1631

1637-1636

1639-1632

Solution

Question 8

161-161

1614-1611

1617-1616

1619-1612

Solution

User

Question Analysis

My Perfomance

Score

-

Rank

-

Results Announcement on: coming Monday

Stay Tuned: We’ll update you on your result via email or SMS.

Time complexity of dequeue is O(n)