GATE 2010 CSE Computer Science and information technology
[Q1 – Q25 carry ONE mark each ]
Q1➡| Engineering Mathematics Let G = (V,E) be a graph. Define ξ(G) = , where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then
Q2➡| Engineering Mathematics Newton-Raphson method is used to compute a root of the equation x2 – 13 = 0 with 3.5 as the initial value. The approximation after one iteration is
Q4➡| Engineering Mathematics Consider the set S = {1, ω, ω2}, where ω and ω2 are cube roots of unity. If * denotes the multiplication operation, the structure (S,*) forms
Q7➡| Digital Logic Design A main memory unit with a capacity of 4 megabytes is built using 1M 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is
Q8➡| Digital Logic Design P is a 16-bit signed integer. The 2’s complement representation of P is (F87B)16. The 2’s complement representation of 8*P is
Q10➡| Data Structures In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
Q12➡| Algorithms Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n2 time units and package B requires 10nlog10n time units to process n records.What is the smallest value of k for which package B will be preferred over A?
Q16➡| Computer Network One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?
Q17➡| Theory-of-Computation Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
Q18➡| Database Management System Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
Q19➡| Database Management System A relational schema for a train reservation database is given below. Passenger (pid, pname, age) Reservation (pid, class, tid) What pids are returned by the following SQL query for the above instance of the tables? SLECT pid FROM Reservation , WHERE class ‘AC’ AND EXISTS (SELECT * FROM Passenger WHERE age > 65 AND Passenger. pid = Reservation.pid)
Q20➡| Database Management System Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? I. 2-phase locking II. TIme-stamp ordering
Q21➡| Software Engineering The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand using
