GATE CSE 2001
Q1.
Consider the following data path of a simple non-pilelined CPU. The registers A, B, A1, A2, MDR, the bus and the ALU are 8-bit wide. SP and MAR are 16- bit registers. The MUX is of size 8x(2:1) and the DEMUX is of size 8x(1:2). Each memory operation takes 2 CPU clock cycles and uses MAR (Memory Address Register) and MDR (Memory Date Register). SP can be decremented locally. The CPU instruction "push r", where = A or B, has the specification M[SP]\rightarrowr SP \rightarrow SP - 1 How many CPU clock cycles are needed to execute the "push r" instruction ?Q2.
Which is the most appropriate match for the items in the first column with the items in the second columnQ3.
Let f (n) =n^{2} logn and g(n) = n(logn)^{10} be two positive functions of n. Which of the following statements is correct ?Q7.
Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct ?Q8.
Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i\leq n ) , the index of the parent isQ9.
Consider the circuit shown below. The output of a 2:1 Mux is given by the function (ac' + bc). Which of the following is true?