1.
The lexical analysis for a modem computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
A.
B.
Deterministic pushdown automata
C.
Non-deterministic pushdown automata
D.
2.
An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cache block comprising of the following. 1 Valid bit , 1 Modified bit. As many bits as the minimum needed to identify the memory block mapped in the cache. What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache?
3.
An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10 ms. Rotational speed of disk is 6000 rpm. lf all 10() libraries are loaded from random locations on the disk, how long does it take to load all libraries? (The time to transfer data from the disk block once the head has been positioned at the start of the block may be neglected.)
4.
Which of the following problems are decidable?
1) Does a given program ever produce an output?
2) If L is context-free language, then, is L also context-free?
3) If L is regular language, then, is L also regular?
4) If L is recursive language, then, is L also recursive?
5.
Given the language L-{ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
6.
In the IPv4 addressing format, the number of networks allowed under Class C addresses is
7.
Register renaming is done is pipelined processors
A.
As an alternative to register allocation at compile time
B.
For efficient access to function parameters and local variables
C.
To handle certain kinds of hazards
D.
As part of address translation
8.
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given: 10, 8,5,3,2. Two new elements 1 and 7 are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is…...
9.
Consider the following recursive C functionVoid get(int n){ if(n<1) return; get(n-1); get(n-3); printf("%d",n); }If get (6) function is being called in main () then how many times will the get () function beinvoked before returning to the main ( ) ?
10.
Unlike Ipv4, Ipv6 does not include the following field in the base header
A.
B.
C.
Field for Fragmentation information
D.
11.
Let G be a simple undirected planar graph on 10 vertices with 15edges. If G is a connected Graph, then the number of bounded faces in any embedding of G on the plane is equal to
12.
Assuming P ε NP, which of the following is TRUE?
13.
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time
Algorithm to solve A.
14.
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?
A.
This algorithm is equivalent to the first-come-first-serve algorithm
B.
This algorithm is equivalent to the shortest-job-first algorithm
C.
This algorithm is equivalent to the shortest-remaining-time-first algorithm
D.
This algorithm is equivalent to the round-robin algorithm
15.
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production to parse a String with ‘n’ tokens?
16.
The smallest integer than can be represented by an 8-bit number in 2’s complement form is
17.
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
18.
Which one of the following problems is undecidable?
A.
Deciding if the language generated by a given context-free grammar is finite.
B.
Deciding if the language generated by a given context-free grammar is empty.
C.
Deciding if a given context-free grammar is ambiguous
D.
Deciding if a given string is generated by a given context-free grammar.
19.
Which of following statements is/are FALSE?
I. XML overcomes the limitations in HTML to support a structured way of organizing content.
II. XML specification is not case sensitive while HTML specification is case sensitive.
III. XML supports user defined tags while HTML uses pre-defined tags.
IV. XML tags need not be closed while HTML tags must be closed
20.
A software requirements specification (SRS) document should avoid discussing which one of
the following?
A.
B.
Non-functional requirements
C.
D.
Interfaces with third party software
21.
Identify the correct order in which a server process must invoke the function calls accept,
bind, listen, and recv according to UNIX socket APL
A.
Listen, accept, bind recv
B.
Bind, listen, accept, recv
C.
Bind, accept, listen, recv
D.
Accept, listen, bind recv
22.
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, 210KB, 468 KB and 491 KB in that order. If the best fit algorithm is used, which partitions are NOT allotted to any process?
23.
Which one of the following assertions concerning code inspection and code walkthrough is true?
A.
Code inspection is carried out once the code has been unit tested
B.
Code inspection and code walkthrough are synonyms
C.
Adherence to coding standards is checked during code inspection
D.
Code walkthrough is usually carried out by an independent test team
24.
Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following
Pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?
25.
Consider the following array of elements.
The minimum number of interchanges needed to convert it into a max-heap is