GATE Semi Syllabus Quiz 1 for GATE & PSU CS Exams

Question 1

Consider the following sequence of elements.

Find the maximum sum of contiguous subsequence of a list S.

Question 2

One host having IP address 219.51.38.0 sends a message to a host of IP address 201.82.03.86,. What will be the destination address attached to message by source host.

Question 3

Consider the CRC technique for detecting the error in the frame:
S1: In framing, CRC code is appended as the trailer in the frame
S2: It is appended in the trailer portion or at the end of the frame for saving some time.
Which of the following is true?

Question 4

Consider the following program
int find (int n)
{
int gate = 1;
for (i = 1; i < = n; i++)
for (j=1; j < = i; j++)
for (k = 1; k < = j; k++)
gate = gate +1;
return gate;
}
What is the value returned by find (10)?

Question 5

If the following elements 5, 3, 4 ,2, 6, 7 and 1 are inserted into a Max heap then what is printed for an in order traversal of the Max heap.

Question 6

A pipelined processor uses 5 stages with execution time of 3,4,3,2,4 cycles respectively. The corresponding non-pipelined processor uses 8 clock cycles to complete a instruction (ignore buffer delay). Calculate speedup assuming that a very large number of instruction are to be executed.

Question 7

Assume that the control memory is 24 bits wide. The control portion of the microinstruction format is divided into two fields. A micro-operation field of 13 bits specifies the micro-operations to be performed. An address selection field specifies a condition, based on the flags that will cause a microinstruction branch. There are eight flags.
a) How many bits are in the address selection field?
b) How many bits are in the address field?
c) What is the size of the control memory?
What is the answer to the above questions?

Question 8

Let sum(n)=0+1+2+…..+n for all natural numbers n. give an induction proof to show that the which of the following equation is true for all natural numbers m and n:

A. sum(m+n)=sum(m)+sum(n)+mn
B. sum(m+n) = 0
C. sum(m)+sum(n) = mn

Question 9

Consider the partial implementation of a 2-bit counter using T flip-flops following the sequence 0-2-3-1-0, as shown below.

To complete the circuit, the input X should be

Question 10

Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys.
Schema I : Registration (rollno, courses)
Field ‘courses’ is a set-valued attribute containing the set of courses a student has registered for.
rollno → courses
Schema II : Registration (rollno, courseid,
email)
Non-trivial functional dependencies:
rollno, courseid → email
email → rollno
Schema III : Registration (rollno, courseid,
marks, grade)
Non-trivial functional dependencies:
rollno, courseid → marks,
grade
marks → grade
Schema IV : Registration (rollno, courseid,
credit)
Non-trivial functional dependencies:
rollno, courseid → credit
courseid → credit
Which one of the relational schemas above is in 3NF but not in BCNF?

Question 11

Consider the following SQL query
SELECT studentid, studentname
FROM student
WHERE birthyear >=ALL (SELECT birthyear from student)
Identify the answer returned by above query?

Question 12

Which technique is used by 802.11 b HR-DSSS for data transfer?

Question 13

Transpose of a matrix must be calculated for which of the following algorithm that uses DFS?

Question 14

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 15

In parallel access system, a cache has latency of 40ns to access the index field of each set and 20ns to access the tag field within a set, memory access takes 250ns, 75% of memory references are reads and 25% for writes. Hit ratio is 0.6 for read access then what is the average access time if write-through policy is used?

Question 16

What will be output generated by the following code :
main()
{
char a[10];
char *b = 'Gradeup' ;
int length = strlen(B) ;
int i;
for(i=0 ; i < length ; i++)
{
a[i] = b[length - i];
}
printf("%s" , a);
}

Question 17

In RSA algorithm, prime numbers used are 5 and 7.Value of e is 3. Encrypt the message 654.

Question 18

Find the latency of Token Ring (in bits) where data rate of link is 20 Mbps and 40 stations separated by 100 meters and bit delay at each station is 1 bit. (Assume propagation speed as

)

Question 19

Consider the following statements:
S1: Processing
S2: Transmission
S3: Propagation
S4: Queuing
Which of the above statement(s) causes of packet delay?

Question 20

If the last operation performed on a computer with an 8-bit word was an addition in which the two operands were 00000010 and 00000011,what would be the value of the following flags (Carry, Zero, Overflow, Sign, Even-Parity, Half-Carry)?