# CS GATE 2009 (Test 1)

Tag: cs gate 2009
Q.1
Given the following state table of an FSM with two states A and B, one input and one output: If the initial state is A = 0, B = 0, what is the minimum length of an input string which will take the machine to the state A = 0, B = 1 with Output = 1?
A. 3
B. 4
C. 5
D. 6
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.2
What is the chromatic number of an n-vertex simple connected graph which does not contain any odd length cycle? Assume n ≥ 2
A. 2
B. 3
C. n - 1
D. n
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.3
Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm? P. Always find a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.
A. P only
B. Q only
C. Both P and Q
D. Neither P nor Q
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.4
Let R and S be relational schemes such that R={a, b, c} and S={c}. Now consider the following queries on the database: Where R.c = S.c
Which of the above queries are equivalent?
A. I and II
B. I and III
C. II and IV
D. III and IV
Answer : Option C
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.5
Consider the following relational schema: Suppliers (sid:integer, sname: string, city:string, street: string) Parts (pid:integer, pname: string, color:string) Catalog (sid:integer, pid:integer, cost: real)
Consider the following relational query on the above database:
SELECT S.sname
FROM Suppliers S
WHERE S.sid NOT IN (SELECT C. sid
FROM Catalog C
WHERE C.pid NOT IN (SELECT P.pid
FROM Parts P
WHERE P.color<> ‘blue’))
Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?
A. Find the names of all suppliers who have supplied a non-blue part
B. Find the names of all suppliers who have not supplied a non-blue part
C. Find the names of all suppliers who have supplied only blue parts
D. Find the names of all suppliers who have not supplied only blue part
Answer : Option A
Explaination / Solution:
No Explaination.

Workspace
Report
Topic: Databases Tag: CS GATE 2009
Q.6
Consider the following relational schema: Suppliers (sid:integer, sname: string, city:string, street: string) Parts (pid:integer, pname: string, color:string) Catalog (sid:integer, pid:integer, cost: real) Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?
A. The schema is in BCNF
B. The schema is in 3NF but not in BCNF
C. The schema is in 2NF but not in 3 NF
D. The schema is not in 2NF
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report
Q.7
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
A. No two vertices have the same degree
B. At least two vertices have the same degree
C. At least three vertices have the same degree
D. All vertices have the same degree
Answer : Option C
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
A CPU generally handles an interrupt by executing an interrupt service routine
A. as soon as an interrupt is raised
B. by checking the interrupt register at the end of fetch cycle
C. by checking the interrupt register after finishing the execution of the current instruction
D. by checking the interrupt register at fixed time intervals
Answer : Option C
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
The essential content(s) in each entry of a page table is/are
A. Virtual page number
B. Page frame number
C. Both virtual page number and page frame number
D. access right information
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report
Q.10
Match all items in Group I with correct options from those given in Group 2
Group 1                                     Group 2
P. Regular expression             1. Syntax analysis
Q. Pushdown automata          2. Code generation
R. Dataflow analysis               3. Lexical analysis
S. Register allocation              4. Code Optimization
Codes:
A. P-4, Q-1, R-2, S-3
B. P-3, Q-1, R-4, S-2
C. P-3, Q-4, R-1, S-2
D. P-2, Q-1, R-4, S-3
Answer : Option B
Explaination / Solution:
No Explaination.

Workspace
Report