BARC 2018 Live Quiz Session Questions : 21/03/2018 for GATE & PSU CS Exams

Question 1

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. The root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

Question 2

Consider the Circuit given below.

If the decimal input is 92 then Y_out corresponds to I_m then value of m is___

Question 3

A queue can be implemented using 2 stacks. Let stacks used are s1 and s2 and the queue be q.
Let operations enqueue and dequeue be:
enqueue(q, x):
a. push everything from s1 to s2 until s1 is empty
b. P
c. Q.
Dequeue(q):
a. pop item from s1.
The best possible option for P and Q are respectively

Question 4

A disk drive has 100 cylinders, numbered 0 to 99. Disk requests come to the disk driver for cylinders 12, 26, 24, 4, 42, 8 and 50 in that order. The driver is currently serving a request at a cylinder 24. A seek takes 6 msec per cylinder moved. How much seek time is needed for shortest seek time first (SSTF) algorithm?

Question 5

Suppose that someone starts with a chain letter. Each person who receives the letter is asked to send it on to 4 other people. Some people do this, while some do not send any letter. How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people who read it but did not send it out? Also find how many people sent out the letter?

Question 6

Find the solution for the following instance of post correspondence problem. Let ∑ = {0, 1}. Let X and Y be lists of three strings as follows:

Question 7

A unix file system has 1-KB blocks and 4-byte disk addresses. What is the maximum file size if i-nodes contain 10 direct entries and one single, double and triple indirect entry each?

Question 8

Consider the following grammar
E → E(E) E | ∈
Which one of the following is true?
1) The grammar is ambiguous
2) The grammar is unambiguous
3) The grammar will generate all strings having balanced parenthesis

Question 9

Rule which states that addition of same attributes to right side and left side will result in other valid dependency is classified as:

Question 10

Consider a “CUSTOMERS” database table having a column “CITY” filled with all the names of Indian cities (in capital letters). The SQL statement that finds all cities that have “GAR” somewhere in its name, is: