GATE CSE 2018
Q1.
Consider the following C program. #include < stdio.h > struct Ournode{ char x,y,z; }; int main(){ struct Ournode p = {'1', '0','a'+2}; struct Ournode *q = &p printf("%c,%c",*((char*)q+1),*((char*)q+2)); return 0; } The output of this program is:Q2.
The size of the physical address space of a processor is 2^{P} bytes. The word length is 2^{W} bytes. The capacity of cache memory is 2^{N} Bytes. The size of each cache block is 2^{M} words. For a K-way set-associative cache memory, the length (in number of bits) of the tag field isQ3.
The value of \int_{0}^{\frac{\pi }{4}}x\cos (x^{2})dx correct to three decimal places (assuming that \pi = 3.14 ) isQ4.
Which one of the following is a closed form expression for the generating function of the sequence \left \{ a_{n} \right \}, where a_{n}=2n+3 for all n = 0, 1, 2,...?Q5.
The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.Q6.
Consider the following languages: I. \{a^{m}b^{n}c^{p}d^{q}|m+p=n+q, \; where \; m,n,p,q \geq 0 \} II. \{a^{m}b^{n}c^{p}d^{q}|m=n \; and \; p=q, \; where \; m,n,p,q\geq 0 \} III. \{a^{m}b^{n}c^{p}d^{q}|m=n=p \; and \; p\neq q, \; where \; m,n,p,q\geq 0 \} IV. \{a^{m}b^{n}c^{p}d^{q}|mn=p+q, \; where\; m,n,p,q\geq 0\} Which of the languages above are context-free?Q7.
Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier-sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium. Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0 and begins to carrier-sense the medium. The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P's ongoing transmission is _____.Q8.
Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is ____.Q9.
In a system, there are three types of resources: E, F and G. Four processes P_0,P_1,P_2 \; and \; P_3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P_2,F] is the maximum number of instances of F that P_2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available. From the perspective of deadlock avoidance, which one of the following is true?Q10.
Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, ... , 199), and 256 sectors per track (numbered as 0, 1, ... , 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time: [120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1] Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is _______.