Algorithms
GATE 2015 SET 1
Minimum-Spanning-Tree
An unordered list contains n distinct elements. The number of comparisons to find an element in
this list that is neither maximum nor minimum is
Algorithms
GATE 2015 SET 2
Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5
nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the
processor's read requests result in a cache hit. The average read access time in nanoseconds is
__________.
computer organization
GATE 2015 SET 2
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The
lower bound for the number of operations to convert the tree to a heap is
Data Structures
GATE 2015 SET 2
Heap-Tree
A binary tree T has 20 leaves. The number of nodes in T having two children is _______.
Data Structures
GATE 2015 SET 2
Binary-Trees
A system has 6 identical resources and N processes competing for them. Each process can request
atmost 2 resources. Which one of the following values of N could lead to a deadlock?
operating systems
GATE 2015 SET 2
Computer Networks
GATE 2015 SET 2
Computer Networks
GATE 2015 SET 2
Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN.
Ethernet frames may carry data up to 1500 bytes (i.e. MTU=1500 bytes). Size of UDP header is 8
bytes and size of IP header is 20 bytes. There is no option field in IP header. How many total
number of IP fragments will be transmitted and what will be the contents of offset field in the last
fragment?
Computer Networks
GATE 2015 SET 2
R contains a, b, e, f, g but not c, d.
R contains all of a, b, c, d, e, f, g.
R contains e, f, g but not a, b.
R contains e but not f, g.
DBMS
GATE 2015 SET 2
Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB,
where KB refers to kilobyte. These partitions need to be allotted to four processes of sizes 357 KB,
210 KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are
NOT allotted to any process?
operating systems
GATE 2015 SET 2
operating systems
GATE 2015 SET 2
A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page
table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the
maximum size of the page table of a process is 24 megabytes, the length of the virtual address
supported by the system is _______________ bits.
operating systems
GATE 2015 SET 2
Match the above algorithms on the left to the corresponding design paradigm they follow.
Algorithms
GATE 2015 SET 2
Data Structures
GATE 2015 SET 2
(a, left_end, k) and (a+left_end+1, n-left_end-1, k-left_end-1)
(a, left_end, k) and (a, n-left_end-1, k-left_end-1)
(a+left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k)
(a, n-left_end-1, k-left_end-1) and (a, left_end, k)
Algorithms
GATE 2015 SET 2
Data Structures
GATE 2015 SET 2
Hashing
computer organization
GATE 2015 SET 2
The maximum number of processes that can be in Ready state for a computer system with n CPUs
is
operating systems
GATE 2015 SET3
Consider the following statements.
I. TCP connections are full duplex
II. TCP has no option for selective acknowledgement
III. TCP connections are message streams
Only I and III are correct
Only II and III are correct
All of I, II and III are correct
Computer Networks
GATE 2015 SET3