Sri Balaji Shiksha Samiti,

Jaipur 4. Consider the relation R(P, Q, S, T, X, Y, Z, W)

with the following functional dependencies
Manthan - 2k24
PQ → X ; P → YX ; Q → Y ; Y → ZW
HACKATHON QUIZ
Each answer has 1 point Consider the decomposition of the relation R
1.Consider the following ER diagram into the constituent relations according to the
following two decomposition schemes D1: R =
[(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)] D2: R = [(P,
Q, S); (T, X); (Q, Y); (Y, Z, W)] Which one of the
following options is correct?

Which of the following is a correct attribute set (a) D1 is a lossless decomposition, but D2 is a
for one of the tables for the minimum number lossy decomposition.
of tables needed to represent M, N, P, R1 and (b) D1 is a lossy decomposition, but D2 is a
R2 lossless decomposition.
(a) {M1, M2, M3, P1} (c) Both D1 and D2 are lossless
(b) {M1, P1, N1, N2} decompositions.

(c) {M1, P1, N1} (d) Both D1 and D2 are lossy decompositions.

(d) {M1, P1}

2. A prime attribute of a relation scheme R is an 5.Consider the following four relational

attribute that appears schemas. For each schema, all non-trivial
functional dependencies are listed. The
(a) in all candidate keys of R. underlined attributes are the respective primary
keys.
(b) in some candidate key of R.
Schema I:
(c) in a foreign key of R.
Registration (rollno, courses) Field 'courses' is a
(d) only in the primary key of R.
set-valued attribute containing the set of
courses a student has registered for. Non-trivial
functional dependency: rollno → courses
3. Consider an Entity-Relationship (ER) model
in which entity sets E1 and E2 are connected by Schema II:
an m: n relationship R12 . E1 and E3 are
Registration (rollno, courseid, email) Non-
connected by a 1: n (1 on the side of E1 and n
trivial functional dependencies: rollno,
on the side of E3) relationship R13.
courseid → email email → rollno
E1 has two single-valued attributes a11 and
Schema III:
a12 of which a11 is the key attribute. E2 has two
single valued attributes a21 and a22 of which Registration (rollno, courseid, marks, grade)
a21 is the key attribute. E3 has two single Non-trivial functional dependencies: rollno,
valued attributes a31 and a32 of which a31 is courseid → marks, grade marks → grade
the key attribute. The relationships do not have
any attributes. Schema IV:

If a relational model is derived from the above Registration (rollno, courseid, credit) Non-trivial
ER model, then the minimum number of functional dependencies: rollno, courseid →
relations that would be generated if all the credit courseid → credit Which one of the
relations are in 3 NF is__________.
relational schemas above is in 3 NF but not in (b) D1 is a lossy decomposition, but D2 is a
BCNF? lossless decomposition.

(a) Schema I (c) Both D1 and D2 are lossless

decompositions.
(b) Schema II
(d) Both D1 and D2 are lossy decompositions.
(c) Schema III
8. Let Ri,(z) and Wi (z) denote read and write
(d) Schema IV
operations on a data element z by a transaction
6. A database of research articles in a journal Ti, respectively. Consider the schedule S with
uses the following schema. four transactions.

(VOLUME, NUMBER, STARTPAGE, ENDPAGE, S: R4(x)R2(x) R3(x) R1(y) W1(y) W2(x) W3(y) R4(y)
TITLE, YEAR, PRICE) Which one of the following serial schedules is
conflict equivalent to S ?
The primary key is (VOLUME, NUMBER,
STARTPAGE, ENDPAGE) and the following (a) T1 → T3 → T4 → T2
functional dependencies exist in the schema.
(b) T1 → T4 → T3 → T2
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) →
(c) T4 → T1 → T3 → T2
TITLE
(d) T3 → T1 → T4 → T2
(VOLUME, NUMBER) → YEAR
9. Consider the following directed graph:
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) →
PRICE

The database is redesigned to use the following

schemas.

(VOLUME, NUMBER, STARTPAGE, ENDPAGE,

TITLE, PRICE)
The number of different topological ordering of
(VOLUME, NUMBER, YEAR) the vertices of the graph is
Which is the weakest normal form that the new Consider the following three relations in a
database satisfies, but the old one does not? relational database.
(a) 1 NF (b) 2 NF (c) 3 NF (d) BCNF Employee (eId, Name), Brand(bId, bName),
7. Consider the relation R(P, Q, S, T, X, Y, Z, W) Own(eId, bId )
with the following functional dependencies 10.Which of the following relational algebra
PQ → X ; P → YX ; Q → Y ; Y → ZW expressions return the set of eIds who own all
the brands?
Consider the decomposition of the relation R
into the constituent relations according to the (a) ΠeId (ΠeId, bId (Own) / ΠbId (Brand))
following two decomposition schemes (b) ΠeId (Own) – ΠeId ((ΠeId (Own) × ΠbId
D1: R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)] (Brand)) – Π eId, bId (Own))

D2: R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)] (c) ΠeId (ΠeId, bId (Own)/ΠbId (Own))

Which one of the following options is correct? (d) Π_eld ((ΠeId (Own)×ΠbId (Own))/Π_bld
(Brand)).
(a) D1 is a lossless decomposition, but D2 is a
lossy decomposition.
11. Consider the following relation A, B and C: (b) Employee numbers of only those employees
whose age is more than the age of exactly one
other employee

(c) Employee numbers of all employees whose

age is not the minimum

(d) Employee numbers of all employees whose

age is the minimum

13. A relation r(A, B) in a relational database has

1200 tuples. The attribute A has integer values
ranging from 6 to 20 , and the attribute B has
integer values ranging from 1 to 20 . Assume
that the attributes A and B are independently
distributed.

The estimated number of tuples in the output of

σ (A>10) V (B = 18) (r) is________

14. With reference to the B+ tree index of order

1 shown below, the minimum number of nodes
How many tuples does the result of the (including the Root node) that must be fetched
following relational algebra expression contain? in order to satisfy the following query: "Get all
Assume that the schema of A∪ B is the same as records with a search key greater than or equal
that of A. to 7 and less than 15'' is?

(a) 7

(b) 4

(c) 5

(d) 9

12. The following relation records the age of 500

employees of a company, where empNo 15. Consider a database of fixed-length
{indicating the employee number} is the key: records, stored as an ordered file. The database
has 25,000 records, with each record being 100
empAge(empNo, age)
bytes, of which the primary key occupies 15
Consider the following relational algebra bytes. The data file is block-aligned in that each
expression: data record is fully contained within a block.
The database is indexed by a primary index file,
∏empNo.(empAge ⋈(age > age1) ρ empNo1, which is also stored as a block-aligned ordered
age1) (empAge)) file. The figure below depicts this indexing
What does the above expression generate? scheme.

(a) Employee numbers of only those employees

whose age is the maximum
 char b = 'x’;

char c = (a & b) + '*’;

char d = (a | b) - '-’;

char e = (a ^ b) + '+’;

printf("%c %c %c\n", c, d, e);

return 0; }

ASCII encoding for relevant characters is given

below

Suppose the block size of the file system is

1024 bytes, and a pointer to a block occupies 5
bytes. The system uses binary search on the
index file to search for a record with a given key.
You may assume that a binary search on an (a) z K S
index file of b blocks takes [log2 b] block
accesses in the worst case. Given a key, the (b) 122 75 83
number of block accesses required to identify (c) * – +
the block in the data file that may contain a
record with the key. in the worst case, is _____. (d) P x +

18. Consider the following C program

16. Consider a file of 16384 records. Each #include<stdio.h>

record is 32 bytes long and its key field is of size int main ( ) {
6 bytes. The file is ordered on a non-key field,
and the file organization is unspanned. The file int m=10 int n, n1;
is stored in a file system with block size 1024
n=++m ;
bytes, and the size of a block pointer is 10
bytes. If the secondary index is built on the key n1=m++;
field of the file, and a multilevel index scheme is
n– –; – –n1 ;
used to store the secondary index, the number
of first-level and second-level blocks in the n–=n1;
multilevel index are respectively-
printf( ("%d", n) return 0 ; }
(a) 8 and 0 (b) 128 and 6 (c) 256 and 4 (d) 512
and 5 The output of the program is___________

17.What is printed by the following ANSI C

program? 19. The following function computes the
#include<stdio.h> maximum value contained in an integer array p[
] of size n(n  1).
int main(int argc, char *argv[]){
int max ( int * p, int n )
char a = 'P’;
{ int a = 0, b = n – 1;
while (_______ ) The value returned when we call fun with the
input 240 is:
{ if(p[a] ≤ p[b]){a = a + 1;}
(a) 4
else { b = b – 1;}
(b) 5
} return p[a]; }
(c) 6
The missing loop condition is
(d) 40
(a) a !=n

(b) b != 0
22. Consider the following pseudo code. What
(c) b>(a+1)
is the total number of multiplications to be
(d) b !=a performed?

20. Choose the correct option to fill ?1 and ?2 D=2

so that the program below prints an input string
for i = 1 to n do
in reverse order. Assume that the input string is
terminated by a newline character for j = i to n do

void reverse(void) { for k = j + 1 to n do

int c; D=D * 3

if (?1) reverse(); (a) Half of the product of the 3 consecutive

integers.
?2
(b) One-third of the product of the 3
}
consecutive integers.
main() {
(c) One-sixth of the product of the 3
printf (“Enter Text”) ; consecutive integers.

printf (“\n”); (d) None of the above

reverse(); printf (“\n”); } 23. The output of executing the following C

program is___________.
(a) ? 1 is (getchar () ! = ‘\n’) ? 2 is getchar (c);
#include<studio.h>
(b) ? 1 is (c = getchar ()) ! = ‘\n’) ? 2 is getchar (c)
int total (int v){
(c) ? 1 is (c ! = ‘\n’) ? 2 is putchar (c);
static int count = 0;
(d) ? 1 is ((c = getchar ()) ! = ‘\n’) ? 2 is putchar
(c); while (v){

count += v&1;

21.Consider the following C code. Assume that v >>= 1;

unsigned long int type length is 64 bits.
}
unsigned long int fun (unsigned long int n) {
return count;
unsigned long int i, j=0, sum=0;
}
for (i=n ; i>1 ; i=i / 2) j++;
void main()
for ( ; j>1 ; j = j / 2) sum++;
{
return sum; }
static int x=0; (a) 312213444

int i=5; (b) 312111222

for( ; i>0; i– –){ (c) 3122134

x = x+ total (i); } (d) 3121112

printf (‘’%d\n‘’, x); } 26. What is the value printed by the following C
program?

#include < stdio.h>

24. Consider the following C program:
int f(int *a, int n){
#include<stdio.h>
if (n <= 0) return 0;
int r ( ){
else if (*a % 2 == 0)
static int num = 7;
return *a + f(a + 1, n-1);
return num – –;
else return *a - f(a + 1, n -1);
}
}
int main( ){
int main () {
for (r ( ); r( ); r( ))
int a[] = {12, 7,13.4.11,6);
printf (“%d”, r( ));
printf(<,%d’, f(a, 6));
return 0; }
return 0;
Which one of the following values will be
displayed on execution of the programs? }

(a) 41 (a) –9

(b) 52 (b) 5

(c) 63 (c) 15

(d) 630 (d) 19

25.What will be the output of the following C Common Data for next two questions:
program?
Consider the following C program that attempts
void count (int n ) { to

static int d=1; locate an element x in an array Y[] using binary

printf ("%d", n); search. The program is erroneous.

printf ("%d", d); 1. f( int Y[10], int x){

d++; 2. int i, j, k;

if (n>1) count (n – 1); 3. i=0 ; j=9;

printf ("%d", d); } 4. do {

void main(){ 5. k = (i + j) / 2;

count (3); } 6. if (Y[K]<x) i = k; else j = k;

7. } while ((Y[k] !=x) &&(i<j)); (d) SLLdel is O(n) and DLLdel is O(1)

8. if (Y[k]==x)
31. What is the worst case time complexity of
printf("x is in the array ") ;
inserting n elements into an empty linked list, if
9. else the linked list needs to be maintained in sorted
order?
printf ("x is not in the array");
(a) Ѳ(n)
10. }
(b) Ѳ(n log n)
27.On which of the following contents of Y and x
does (c) Ѳ(n2)

the program fail? (d) Ѳ(1)

(a) Y is [1 2 3 4 5 6 7 8 9 10] and x < 10 32. Consider the problem of reversing a singly
linked
(b) Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

(c) Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

(d) Y is [2 4 6 8 10 12 14 16 18 20] and 2 < x < 20 list. To take an example, given the linked list
and x is even below,the reversed linked list should look like

28.The correction needed in the program to

make it work
Which one of the following statements is TRUE
properly is about the time complexity of algorithms that
(a) change line 6 to: if (Y[k] < x) i = k + 1; elsej = k solve the above problem in O(1) space?
– 1; (a) The best algorithm for the problem takes
(b) change line 6 to: if (Y[k] < x) i = k - 1; else j = k Ѳ(n) time in the worst case.
+ 1; (b) The best algorithm for the problem takes Ѳ(n
(c) change line 6 to: if (Y[k] < x) i = k; else j = k; log n) time in the worst case.

(d) change line 7 to: while ((Y[k] = = x) &&(i < j)); (c) The best algorithm for the problem takes
Ѳ(n2) time in the worst case.

30. Let SLLdel be a function that deletes a node (d) It is not possible to reverse a singly linked
in a singly-linked list given a pointer to the node list in O(1) space.
and a pointer to the head of the list. Similarly, 34. Suppose, a stack implementation supports
let DLLdel be another function that deletes a an instruction REVERSE, which reverses the
node in a doubly order of elements on the stack, in addition to
Let n denote the number of nodes in each of the the PUSH and POP instructions. Which one of
linked lists. Which one of the following choices the following statements is TRUE (with respect
is TRUE about the worst-case time complexity to this modified stack)?
of SLLdel and DLLdel? (a) A queue cannot be implemented using this
(a) SLLdel is O(1) and DLLdel is O(n) stack.

(b) Both SLLdel and DLLdel are O(log(n)) (b) A queue can be implemented where
ENQUEUE takes a single instruction and
(c) Both SLLdel and DLLdel are O(1) DEQUEUE takes sequence of two instructions.
(c) A queue can be implemented where 5. First, the 3rd least significant bit is
ENQUEUE takes a sequence of three used to divide the keys into left and right
instructions and subtrees.

DEQUEUE takes a single instruction 6. To resolve more collisions, each node

of the binary tree is further sub-divided
(d) A queue can be implemented where both
into left and right subtrees based on the
ENQUEUE and DEQUEUE take a single
4th least significant bit.
instruction each.
7. A split is done only if it is needed, i.e.,
35. Consider the following array of elements
only when there is a collision.
〈89,19,50,17,12,15,2,5,7,11,6,9,100〉.
Consider the following state of the hash table.
The minimum number of interchanges needed
to

convert it into a max-heap is

(a) 4 (b) 5

(c) 2 (d) 3 Which of the following sequences of key

insertions

37. Which one of the following sequences when can cause the above state of the hash table
stored (assume

in an array at locations the keys are in decimal notation)?

A[1], . . . , A[10] forms a max-heap? (a) 5, 9, 4, 13, 10, 7

(a) 23, 17, 10, 6, 13, 14, 1, 5, 7, 12 (b) 9, 5, 10, 6, 7, 1

(b) 23, 17, 14, 7, 13, 10, 1 ,5, 6, 12 (c) 10, 9, 6, 7, 5, 13

(c) 23, 17, 14, 6, 13, 10, 1, 5, 7, 15 (d) 9, 5, 13, 6, 10, 14

(d) 23, 14, 17, 1, 10, 13, 16, 12, 7, 5

40. Consider a hash table with 9 slots. The hash
function is h(k) = k mod 9. The collisions are
38. A binary tree T has 20 leaves. The number of
resolved by chaining. The following 9 keys are
nodes in T having two children is ______
inserted in the
39. Consider a dynamic hashing approach for
order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The
4-bit integer keys:
maximum, minimum, and average chain
1. There is a main hash table of size 4 lengths in the hash table, respectively, are

2. The 2 least significant bits of a key is (a) 3, 0, and 1 (b) 3, 3 and 3

used to index into the main hash table.
(c) 4, 0 and 1 (d) 3, 0, and 2
3. Initially, the main hash table entries
41. Consider the following C function
are empty.
int fun1 (int n)
4. Thereafter, when more keys are
hashed into it, to resolve collisions, the {
set of all keys corresponding to a main
int i, j, k, p, q = 0;
hash table entry is organized as a binary
tree that grows on demand. for (i = 1; i < n; ++i)
 {

p = 0;

for (j = n; j > 1; j = j /2)

++p; 44. Consider the following graph:

for (k =1; k < p; k = k*2)

++q;

return q;

Which one of the following most closely

approximates the return value of the function

fun1? Which one of the following is NOT the sequence
(a) n3 of edges added to the minimum spanning tree
using Kruskal’s algorithm?
(b) n(log n)2
(a) (b, e) (e, f) (a, c) (b, c) (f, g) (c, d)
(c) n log n
(b) (b, e) (e, f) (a, c) (f, g) (b, c) (c, d)
(d) n log (log n)
(c) (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)
42. There are n unsorted arrays: A1, A2,..., An.
(d) (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)
Assume that n is odd. Each of A1, A2, ..., An
contains n distinct elements. There are no 45. Let G be a simple undirected graph. Let TD
common elements between any two arrays. The be a depth first search tree of G. Let TB be a
worst-case time complexity of computing the breadth first search tree of G. Consider the
median of the medians of A1, A2, ..., An is following statements:
(a) O(n log n) (b) O(n2) I: No edge of G is a cross edge with respect to
TD. (A cross edge in G is between two nodes
(c) O(n) (d)  (n2logn)
neither of which is an ancestor of the other in
43. Consider the Quicksort algorithm. Suppose TD).
there is a procedure for finding a pivot element
II: For every edge (u, υ) of G, if u is at depth i and
which splits the list into two sub-lists each of
υ is at depth j in TB, then |i –j| = 1.
which contains at least one-fifth of the
elements. Let T(n) be the number of Which of the statements above must
comparisons required to sort n elements. Then necessarily be true?
(a) T(n) ≤ 2T (n / 5) + n (a) I only (b) II only
(b) T(n) ≤ T (n/5) + T (4n/5) + n (c) Both I and II (d) Neither I nor II
(c) T(n) ≤ 2T (4n/5) + n 46. Consdier the directed graph given below:
(d) T(n) ≤ 2T (n/2) + n
Which of one the following is TRUE? X[1] = 1; Y[1] = 2; Z[1] = 3;

(a) The graph does not have any topological for (i = 1; i ≤n; i ++)
ordering.
{
(b) Both PQRS and SRQP are topological
X[i] = Y[i – 1] + Z [i – 2];
orderings.
Y[i] = 2* X[i];
(c) Both PSRQ and SPRQ are topological
orderings. Z[i] = 3*X[i];
(d) PSRQ is the only topological ordering. }

return X[n];
47. Define Rn to be the maximum amount }
earned by cutting a rod of length n meters into
one or more pieces of integer length and selling The running time of f1(n) and f2(n) are
them. For i > 0, let p[i] denote the selling price (a) Θ(n) and Θ(n)
of a rod whose length is i meters. Consider the
array of prices: (b) Θ(2n) and Θ(n)

p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, (c) Θ(n) and Θ(2n)

p[5] = 10, p[6] = 17, p[7] = 18 (d) Θ(2n) and Θ(2n)

Which of the following statements is/are

correct about R7? 49. If we use Radix Sort to sort n integers in the
range (nk⁄12, nk), for some k > 0 which is
(a) R7 = 18 independent of n, the time taken would be
(b) R7 = 19 (a) Θ(n)
(c) R7 is achieved by three different solutions. (b) Θ(kn)
(d) R7 cannot be achieved by a solution (c) Θ(n log n)
consisting of three pieces.
(d) Θ(n2)
48. Conider the following C funcitons:
50. In a balanced binary search tree with n
intf1(int n) elements, what is the worst-case time
{ complexity of reporting all elements in range [a,
b]? Assume that the number of reported
if(n = = 0||n = = 1) return n; elements is K.
else (a) Θ(log n)
return (2* f1(n – 1) + 3* f1 (n – 2)); (b) Θ(n log k)
} (c) Θ(log n + k)
int f2 (int n) (d) Θ(k log n)
{

int i;

int X[N], Y[N], Z[N];

X[0] = Y[0] Z [0] = 0;