Database Management System: Assignment 0

Total Marks : 20

June 11, 2024

Question 1
Look at the following truth table

A B A op B
F F T
F T F
T F F
T T F

Which binary operation has been carried out? Marks: 1 MCQ

a) ¬ A ∨ B

b) ¬ (A ∨ B)

c) ¬ (A ∧ B)

d) ¬ A ∧ B

Answer: (b)

Explanation: The last column in the truth table shows that the result of the operation
is true (or false) when A and B is both false (or any of the true).

1
Question 2
Consider the following array of seven integers:
30, 15, 10, 40, 25, 20, 12
What will be the contents of this array after the 2nd pass of bubble sort (sorting from smallest
to largest)? Marks: 1 MCQ

a) 15, 10, 30, 25, 20, 12, 40

b) 10, 12, 15, 25, 20, 30, 40

c) 10, 15, 25, 20, 12, 30, 40

d) 10, 12, 15, 20, 25, 30, 40

Answer: (c)

Explanation: According to the bubble sort algorithm.

2
Question 3
Identify the correct representation of the prefix expression of the given tree below.
Marks: 1 MCQ

a) ∗2 + 4 ∗ 6 + 8 9

b) 2 + 4 ∗ 6 ∗ 8 + 9

c) 2 4 + 6 8 9 + ∗∗

d) ∗ + 2 4 ∗ 6 + 8 9

Answer:(d)

Explanation: Prefix expression is the pre order traversal fo the tree.

3
Question 4
Consider a set X = { {a, b}, {c, d}, {e, f} }. What is the number of elements in the power set
of X?
Marks: 1 MCQ

a) 4

b) 8

c) 12

d) 16

Answer: (b)
Explanation: Number of elements in X is 3. Hence, the number of elements in its power set
is 23 . So, option (b) is correct.

4
Question 5
When an ODD decimal number is converted into a binary number, what will be the the Least
Signaficant Bit(LSB)?
Marks: 1 MCQ

a) 0

b) 1

c) either 0 or 1

d) only 11

Answer: (b)

Explanation: If any odd decimal number is divided by 2, the remainder is 1 . This re-
mainder will be the LSB of the binary equivalent. So, LSB of binary represenation of any odd
decimal number will be always 1.
So, option b) is correct.

5
Question 6
Consider the following arrays of numbers. Which one represents a min-heap?
Marks: 1 MCQ

a) 20 5 15 10 6 8 9

b) 20 10 15 5 6 8 9

c) 9 6 10 8 5 15 20

d) 5 6 10 8 9 15 20

Answer: (d)
Explanation: According to the definition of the min-heap, any parent in a complete binary
tree, must be lesser than both its children.
Hence, option (d) is correct.

6
Question 7
Consider two sets A and B. Which of the following statement is are true?
Marks: 1 MSQ

a) A - B = A ∩ B

b) A - B = A - (A ∩ B)

c) A ∩ B = A ∪ (A ∩ B)

d) A ∩ B = A ∩ (A ∩ B)

Answer: b), d)
Explanation: If we draw Venn Diagram, we shall see that the statement in option (b) and
(d) are correct.

7
Question 8
Let a given function be f: I→ I given by f (x) = x2 where I stands for the set of all integers.
Which of the following statements is/are true?
Marks: 1 MCQ

a) It is a one-one function but not onto.

b) It is an onto function but not one-one.

c) It is both one-one and onto.

d) It is neither one-one nor onto.

Answer: (d)

Explanation: By the given function, f(-1)=1 and f(1)=1. Hence it is not one-one. f(x)should
always be a positive integer but. f: I → I. Consider a negative integer in the co-domain. There
is no value of x for which f(x) can be a negative integer.

8
Question 9
Consider the following:
CSE(x): The girl x is in CSE department.
NLP(x): The girl x studies NLP.

Which of the following formula represents “Not all CSE students study NLP.”

Marks: 1 MCQ

a) ∀(x) (CSE(x) ∧ ¬NLP(x))

b) ∀(x) (¬CSE(x) → NLP(x))

c) ∃(x) (¬CSE(x) → NLP(x))

d) ∃(x) (CSE(x) ∧ ¬NLP(x))

Answer: (d)
Explanation: The first option is ∀(x) (CSE(x) ∧¬NLP(x)). This is equivalent to ∀(x)¬((CSE(x) →
NLP(x)). That means CSE girls do not study NLP.
The second option states that if the girl is not in CSE, she studies NLP.
The third option states that some not CSE girls studies NLP.
The fourth option states that not all CSE girls study NLP.
Hence, option (d) is correct.

9
Question 10
Consider the binary relation S1 = {(1, 1), (2, 2), (1, 2), (2, 1)} on the set {1, 2}. Identify the
correct statement. MSQ, Mark 1

a) S1 is reflexive.

b) S1 is symmetric.

c) S1 is not transitive.

d) S1 is antisymmetric.

Answer: a), b)
Explanation: S1 reflexive, symmetric and transitive.
S1 is not antisymmetric as both (1, 2) and (2, a1) are present in S1

10
Question 11
What is the domain of the following function if the range is the set of real numbers?
5
√
x2 − 9
MCQ, Mark 1

a) (-∞, -3) ∪ (-3, ∞)

b) (-∞, 3) ∪ (3, ∞)

c) (3, ∞) ∪ (-∞, -3)

d) (-3, 3)

Answer: c)
Explanation: The denominator is positive if x is not between -3 and +3. Hence, (c) is
correct.

11
Question 12
How many functions are there from the set {1, 2, 3} to the set {a, b}?
MCQ, Mark 1

a) 9

b) 8

c) 6

d) 5

Answer: b)
Explanation: The element “1” can be mapped to any of the two elements in the range.
Similarly, the element “2” or “3” can be mapped to any of the two elements in the range.
Hence, (b) is the correct option.

12
Question 13
If U is the set of integers excluding zero, V is the set of even integers, and D is the set of odd
integers, which of the following statement(s) is (are) true. Note: Here E denotes complement
over the expression E. U is the Universal set
MSQ, Mark 1

a) V ∪ D = U

b) U - V = D

c) V̄ = D

d) V - D = {0}

Answer: b), c)
Explanation: Follow the definition of universal set and difference operation.

13
Question 14
Suppose that A and B are two sets. Which of the following is always equivalent to A ∩ B
MSQ, Mark 1

a) (A − B) ∪ (B − A) ∪ (A ∩ B)

b) (A − B) ∪ (B − A)

c) A − (A − B)

d) B − (B − A)

Answer: c), d)
Explanation: As per the properties set operations, options (c) and (d) are correct.

14
Question 15
Consider the following function from {a,b,c,d} to {1,2,3,4,5}.
{(a,2), (b,1), (c,3), (d,4)}
Which of the following is true about the function?
MCQ, Mark 1

a) The function is bijective

b) The function is injective, but not surjective

c) The function is surjective, but not injective

d) The function is neither injective nor surjective

Answer: b)
Explanation: The function is one to one but not onto. Hence, option (b) is correct.

15
Question 16
Numbers 1, 2, 3, 4 are pushed into a stack in that order but these four PUSH operations are
intermixed with POP operations as well. Whenever a number is popped, it is printed. Which
of the following permutation can be printed by such PUSH and POP operations?
MCQ, Mark 1

a) 3, 4, 1, 2

b) 1, 4, 2, 3

c) 4, 2, 3, 1

d) 3, 2, 4, 1

Answer: d)
Explanation: If 3 is printed first, 1, 2 are in the stack. Next, 4 is pushed and popped. But
1 cannot be popped now. Hence (a) is not possible.
1 is pushed and popped. Then, 4 is printed. So, 2, 3 are in the stack. 2 cannot be popped
now. Hence (b) is not possible.
If 4 is printed first, 1, 2, 3 are in the stack. 2 cannot be popped now. Hence (c) is not possible.
If 3 is printed first, 1, 2 are in the stack. Next, 2 is popped. Then, 4 is pushed and popped.
Lastly, 1 is popped. Hence (d) is the correct option.

16
Question 17
Which one of the following is the most appropriate logical formula to represent the statement?
“Red and Yellow cars are beautiful”.
The following notations are used:
R(x): x is a Red car
Y(x): x is a Yellow car
B(x): x is beauiful
Note: ∀x denotes for all x. ∃x denotes for some x (atleast 1).→ denotes implication. ∨ and ∧
denotes OR and AND operation respectively.
MCQ, Mark 1

a) ∃x(R(x) ∨ Y(x)) → B(x)

b) ∃x(R(x) ∧ Y(x)) → B(x)

c) ∀x(R(x) ∨ Y(x)) → B(x)

d) ∀x(R(x) ∧ Y(x)) → B(x)

Answer: c)
Explanation: This statement can be expressed as
For all x, if x is either a red car or yellow car then the car x is beautiful.
Hence, option (c) is correct.

17
Question 18
Consider a B+-tree of order 5. What is the minimum number of children a root node can have,
considering it is not the only node in the tree?
MCQ, Mark 1

a) 5

b) 6

c) 2

d) 1

Answer: c)
Explanation: As per the construction rule of B+ tree, option (c) is correct.

18
Question 19
A hash table with length of 10 elements use open addressing with hash function h(k)=k mod
10, and linear probing. the table shows the state after insertion of 6 values. Identify a possible
order in which the key values could have been inserted in the table.

0
1
2 22
3 43
4 14
5 62
6 96
7 103
8
9
MCQ, Mark 1

a) 96, 22, 14, 62, 43, 103

b) 14, 22, 43, 62, 103, 96

c) 22, 96, 43, 103, 14, 62

d) 96, 14, 22, 43, 62, 103

Answer: d)
Explanation: In option a), 96 is placed at 6th index in the hash table. 22 is placed at 2nd
index. 14 is placed at 4th index.When 62 is going to be placed in 2nd index, there is a collision.
Therefore, 62 is placed at 3rd index.Hence, option (a) is not correct.
In a similar way, we can check for other options as well. We shall see that option (d) is correct.

19
Question 20
How many comparisons does it take to find the element 10 in the sorted array A = {10,15,17,19,20}
using binary search? MCQ, Mark 1

a) 2

b) 3

c) 5

d) 6

Answer: a)
Explanation: Using binary search technique:
First comparison with mid = 17
Second comparison with mid = 10 (this is the key).
Hence, option (a) is correct.

20