GATE CSE 2010
Q2.
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?Q3.
Two alternative packages A and B are available for processing a database having 10^{k} records. Package A requires 0.0001n^{2} time units and package B requires 10n \log _{{10}} n time units to process n records. What is the smallest value of k for which package B will be preferred over A?Q4.
A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively. When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?Q5.
A computer system has an L1 cache, an L2 cache, and a main memory unit connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively. When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?Q6.
The weight of a sequence a_{0},a_{1},...,a_{n-1} of real numbers is defined as a_{0}+a_{1}/2+...+a_{n-1}/2^{n-1} A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a_{0},a_{1},...,a_{n-1}. Then X is equal toQ8.
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?Q9.
Consider the languages L1=\{0^{i}1^{j}\;| \; i\neq j\}. L2=\{0^{i}1^{j}\;| \; i=j\}. L3=\{0^{i}1^{j}\;| \; i=2j+1\}. L4=\{0^{i}1^{j}\;| \; i \neq 2j\} Which one of the following statements is true?Q10.
Which of the following statements are true? I. Shortest remaining time first scheduling may cause starvation II. Preemptive scheduling may cause starvation III. Round robin is better than FCFS in terms of response time