Artificial Intelligence

1.What is the term used for describing the judgmental or commonsense part of problem solving?

Heuristic Critical Value based Analytical

2.What stage of the manufacturing process has been described as "the mapping of function onto form"?

Design Distribution project management field service

3.Which kind of planning consists of successive representations of different levels of a plan?

hierarchical planning non-hierarchical planning All of the above project planning

4.What was originally called the "imitation game" by its creator?

The Turing Test LISP The Logic Theorist Cybernetics

5.Decision support programs are designed to help managers make:

budget projections visual presentations business decisions vacation schedules

Programming and data structures

1.In the runtime environment, the languages that necessarily need heap allocation is
The one that use global variables The one that allow dynamic data structures The one that support recursion The one that use dynamic scoping

2.What is the requirement for evaluating an expression without any embedded function calls?
Two stack One stack In general case a turning machine is needed As many stacks as the height of an expression tree

3.What is the advantage of chained hash table (external hashing) over open addressing scheme?
Easier deletion is possible Less space is required Worst case complexity of search operations is less None of the above

4.The process in which load addresses are assigned to various parts of the program and to reflect the assigned addresses, code and date in a program are adjusted is called
Relocation Symbol resolution Parsing Assembly

5.Why there are security concerns in case of dynamic linking?
Because cryptographic procedures are not available for dynamic linking. Because security is dynamic Because linking is not secured Because the path for searching dynamic libraries is not known till runtime.

Theory of Computation questions and answers

1.From the options given below the statement, which is not necessarily true if X1 is the recursive language and X2 and X3 are the languages that is recursively enumerable but not recursive is
X2 ∩ X1 is recursively enumerable X2 ∪ X1 is recursively enumerable X2 – X1 is recursively enumerable X1 – X3 is recursively enumerable

2.For the language {ap I P is a prime}, the statement which hold true is
It is not regular but context free It is regular but not context free It is neither regular nor context free, but accepted by a turing machine It is not accepted by turing machine

3.The statement that holds true is
Infinite union of finite sets is regular The union of two non-regular set is not regular Every finite subset of a non-regular set is regular Every subset of a regular set is regular

4.The language described by the regular expression (0+1)*0(0+1)*0(0+1)* over the alphabet {0 1} is the set of
All strings containing at least two 1’s All strings containing at least two 0’s All strings that begin and end with either 0’s or 1’s All strings containing the substring 00

5.3-SAT and 2-SAT problems are
NP-complete and in P respectively Undecidable and NP-complete Both NP-complete Both in P

Computer Networks

1.For real time multimedia, file transfer, DNS and email, the transport layer protocols used are respectively
TCP, UDP, TCP and UDP UDP, UDP, TCP and TCP UDP, TCP, UDP and TCP TCP, TCP, UDP and UDP

2.A device that can look at all protocol headers up to the transport layer is called l ayer-4 firewall. Which one of the following statement is true layer-4 firewall?
It cannot block all ICMP traffic It cannot block entire HTTP traffic during 9:00pm and 5:00am It cannot block TCP traffic from a specific user on a multi-user system during 9:00pm and 5:00am It cannot stop incoming traffic from a specific IP address but allow outgoing traffic to the same address

3.The source and destination are connected through two intermediate routers. During the data transmission from source to destination how many times each packet has to visit the network layer and the data link layer?
Network layer – 6 times and data link layer – 4 times Network layer – 4 times and data link layer – 2 times Network layer – 4 times and data link layer – 6 times Network layer – 2 times and data link layer – 3 times

4.For the application layer in the Internet stack, the protocol data unit (PDU) is
Datagram Message Frame Segment

5.The transport layer protocols that is used to support electronic mail is
TCP SMTP UDP IP

Compiler Design

1. In compilers generation of intermediate code based on an abstract machine model is useful because
Syntax-directed translations can be written for intermediate code generation To generate code for real machines directly from high-level language programs is not possible Portability of the front end of the compiler is enhanced Implementation of lexical and syntax analysis is easier

2.Which one of the following statement is false for the SLR (1) and LALR (1) parsing tables for a context free grammar?
The reduce entries in both the tables may be different The error entries in both the tables may be different The go to part of both tables may be different The shift entries in both the tables may be identical

3.Only two registers are available in the instruction set architecture of the processor. The code motion moves the statements from one place to another while preserving correctness. The only allowed complier optimization is code motion. In the compiled code, the minimum number of spills to memory is
0 1 2 3

4.Assume that no other optimization other than optimizing register allocation is applied. To compile this code segment without any spill to memory the minimum number of registers needed in the instruction set architecture of the processor is
3 6 4 5

5.The languages that need heap allocation in the runtime environment are
Those that use global variables Those that use dynamic scoping Those that support recursion Those that allow dynamic data structure

Programming and data structures

1.Which one of the following statement is true for Abstract Data type (ADT)?
It is same as an abstract class It is a data type for which only the operations defined on it can be used but none else It is the data type that cannot be instantiated None of the above.

2.Consider a binary tree that is initially empty. The numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in a binary tree in that order. The binary search tree uses the usual ordering on natural numbers. The in-order traversal sequence of the resultant tree will be
7 6 5 4 8 9 0 1 2 3 1 9 2 7 3 8 5 6 0 4 0 1 2 3 4 5 6 7 8 9 0 3 2 5 6 4 8 1 9 7

3.Faster access to non-local variables is achieved using an array of pointers to activation records called a
Activation tree Stack Heap None of the above

4.The programming language feature that cannot be implemented on a certain processor, which supports only immediate and the direct addressing modes is
Pointers Records Arrays Recursive procedures with local variables

Theory of Computation questions and answers

1.From the options given below, the pair having different expressive power is
Deterministic Push Down Automata (DPDA) and Non-deterministic Push Down Automata (NPDA) Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata(NFA) Single tape turning machine and multi tape turning machine Deterministic single tape turning machine and Non-Deterministic single tape turning machine

2.The problem that is undecidable -
Finiteness problem for FSA’s Membership problem for CFG’s Equivalence problem for FSA’s Ambiguity problem for CFG’s

3.The language which is generated by the grammar S-> aSa I bSb I a I b over the alphabet {a, b} is the set of
Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes

4.Two persons X and Y have been asked to show that a certain problem p is NP-complete. X shows a polynomial time reduction from the 3-SAT problem to p and Y shows a polynomial time reduction from p to 3-SAT. From these reduction it can be inferred that
π is NP-complete π is NP-hard but not NP-complete π is in NP but not NP-complete π is neither NP-hard nor in NP

5.Out of the three problems S, Q and R, S is an NP-complete problem and Q and R are the two other problems not known to be in NP. Which one of the following statements is true if Q is polynomial time reducible to S and S is the polynomial time reducible to R?
Q is NP-complete R is NP-complete Q is NP-hard R is NP-hard

Computer Networks test questions

1.We have two hosts A and B that are using sliding window protocol for flow control, and to transfer data from A to B full duplex link is used. The send window size and receive window size is 5 packets each. Data packets that are sent only from A to B are all 1000byte long and the transmission time for such a packet is 50µs. Acknowledgement packets that are sent only from B to A are very small and it requires negligible transmission time. In this communication the maximum achievable throughput, if the propagation delay over the link is 200µs, is
9.12 x 106 bps 10.09 x 106 bps 12.33 x 106 bps 11.11 x 106 bps

2.Which one of the following statement does not hold true about Internet protocol (IP)
IP packets from the same source to the same destination can take different routes in the network If the packet is unable to reach its destinations within a given number of hops, IP ensures that a packet is discarded A computer can have multiple IP address All of the above

3.Let computer A and computer B that have the IP addresses 10.105.1.113 and 10.105.1.91 respectively use the same net mask N. For A and B to belong to same network, the value of N should not be
255.255.255.224 255.255.255.0 255.255.255.128 255.255.255.192

4.Consider the packets are correctly delivered. In the best case, how many bytes including headers are delivered to the IP layer at the destination, for one application message? Consider only data packets
200 220 240 260

5.Neglecting errors, acknowledgements and other overheads, the rate at which application data is transferred to host Hc, is
150.8kbps 245.6kbps 400.9kbps 354.5kbps

Programming and data structures questions and answers

1.Consider a two dimensional array of integers arr[1…. 10][1…. 15]. One memory location is occupied by each integer. The first element of array is stored at location 100 and the array is stored in row-major order. The address of the element arr[i][j] is
15j + i + 84 15i + j + 84 21i + j + 93 21j + I + 93

2.Assuming that the height of a tree with a single node is 0, the maximum height of any AVL-tree with 7 nodes is
5 4 3 2

3.Consider an empty binary search tree into which the following numbers are inserted in the given order: 10,1, 3, 5, 15, 12, 16. The height of the maximum distance of a leaf node from the root is
2 4 3 8

4.Linked list are not suitable data structures of _________________
Binary search Insertion sort Polynomial manipulation Radix sort

5.For efficiently converting an infix expression to the post fix form, use
A parse tree An operand stack An operator stack Both an operator and an operand stack

Computer Science Concepts

(1) Let i, j and n be the integer variables of the C program fragment given below.
val (j) = θ (n/2) val (j) = θ (log n) val (j) = θ (2n) val (j) = θ (n)

(2) In a complete binary tree, LASTPOST denotes the last vertex visited in a post order traversal, LASTIN denotes the last vertex visited in an inorder traversal and LASTPRE denotes the last vertex visited in a preorder traversal. The statement, which always holds true, is
LASTIN = LASTPRE LASTPRE = LASTPOST LASTIN = LASTPOST None of the above.

(3) Which one of the following statement is false?
√ logn = O (log log n) 100n log n = O (nlogn/100) 2n ≠ O (nk) If 0x = O (ny)

(4) Consider an unweighted, undirected connected graph. In terms of time complexity, the shortest path from a node S to every other node is most efficiently computed by
Performing a DFS starting from S Performing a BFS starting from S Warshall’s algorithm Dijkstra’s algorithm starting from S

(5) _____________ in place sorting algorithm needs the minimum number of swaps.
Selection sort Quick sort Insertion sort Heap sort

Programming and data structures questions and answers

1.Consider a program that reads 500 integers in the range of [0, 100] that represents the score of 500 students. Frequency of each score above 50 is then printed. For the program to store the frequencies the best way is
A dynamically allocated array of 550 numbers An array of 100 numbers An array of 500 numbers An array of 50 numbers

2.What is the goal of structured programming?
Able to infer the flow of control from the program text Able to infer the flow of control from the Compiled code To avoid the use of GOTO statements None of the above

3.To check whether an arithmetic expression has balanced parenthesis, the best data structure that can be used is
Stack Tree List Queue

4.Consider a stack S of size n ≥ 1 which is initially empty. In an empty stack first n natural numbers are pushed in sequence and then n pop operations are performed. Push and pop operations take x seconds each. The time elapse between the end of one stack operation and the start of the next operation is y. For m ≥ 1, define the stack-life of m as the time elapsed from the end of push (m) to the start of the pop operation that removes m from stack S. What is the average stack-life of an element of this stack?
3y + 2x n (x + y) - x n (x + y) y + 2x

5.The logic programming languages and functional languages have the common properties that
Both use Horn-clauses Both are declarative Both are procedural languages Both are based on -calculus.

Compiler Design questions and answers

1.In compilers generation of intermediate code based on an abstract machine model is useful because
Syntax-directed translations can be written for intermediate code generation To generate code for real machines directly from high-level language programs is not possible Portability of the front end of the compiler is enhanced Implementation of lexical and syntax analysis is easier

2.Which one of the following statement is false for the SLR (1) and LALR (1) parsing tables for a context free grammar?
The reduce entries in both the tables may be different The error entries in both the tables may be different The go to part of both tables may be different The shift entries in both the tables may be identical

3.We have a grammar with not epsilon and unit production (i.e. of type A->ε and
2n - 1 2n n - 1 n/2

4.Only two registers are available in the instruction set architecture of the processor. The code motion moves the statements from one place to another while preserving correctness. The only allowed complier optimization is code motion. In the compiled code, the minimum number of spills to memory is
0 1 2 3

5.Assume that no other optimization other than optimizing register allocation is applied. To compile this code segment without any spill to memory the minimum number of registers needed in the instruction set architecture of the processor is
3 6 4 5

Database test questions for interview

1.The two relation schemes R1 (A, B) and R2 (C, D) has two corresponding relation instances r1 and r2. B from R1 is the foreign key that refers to C in R2. The statement that always holds true if data in r1 and r2 satisfy referential integrity constraints is
πB (r1) – πC (r2) ≠E πB (r1) = πC (r2) πB (r1) – πC (r2) = E πC (r2) – πB (r1) = E

2.The relation R that has x number of tuples is joined with relation S that has y number of tuples. The maximum and minimum sizes of join respectively are
xy and x + y x + y and I x - yI xy and 0 x + y and 0

3.Consider a B+ tree in which order of the internal node is 3 and that of the leaf node is 2. The key values are inserted into this tree in the order given as 10, 3, 6, 8, 4, 2, 1. The order of the internal node is the maximum number of tree pointers in each node and the order of the leaf node is the maximum number of data items that can be stored in it. Assume that the B+ tree is initially empty. As a result of this iteration the maximum number of times leaf nodes would get split up is
2 3 4 5

4.Which one of the following statement is incorrect for the basic ER and relational models?
An attribute of an entity can be composite An attribute of an entity can have more than one value An attribute can have exactly one value or a NULL value in a row of a relational table An attribute can have more than one value in a row of a relational table.

5. Which one of the following statement about B+ trees is correct?
B+ trees are for secondary indexes and B trees are for primary indexes B+ trees are for main memory and B trees are for storing data on disk B+ trees height is independent of the number of records On B+ trees range queries are faster

Algorithm questions and answers

(1) Starting from the root and performing ____________, level order traversal of a rooted tree can be done.
Breadth first search Depth first search In-order traversal Pre-order traversal

(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)
1, _, _, _, _, _, 3 8, _, _, _, _, _, 10 1, 8, 10, _, _, _, 3 1, 10,8, _, _, _, 3

(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?
Emin is present in every minimum spanning tree of G Emax is not present in any minimum spanning tree. The removal of Emax must disconnect G, if Emax is in a minimum spanning tree. G has a unique minimum spanning tree.

(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array
Solves it in time θ (n²) Solves it in linear time using a left to right pass of the array Solves it in linear time using a right to left pass of the array Solves it using divide and conquer in time θ (n logn)

(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number of leaves in a complete n-array tree. The value of n is
5 4 3 2

Operating system test questions for interview

(1) The use of __________ works on the principle of locality.
Cache memory Interrupts Polling DMA

(2) Consider a computer system with 6 tape drives and n processes completing for them. What is the maximum value of n for the system to be deadlock free assuming each processes may need 3 tape drives?
3 2 4 7

(3) When size of the memory is increased the page replacement policy that sometimes leads to more page faults is
FIFO Optimal LRU None of the above

(4) The capacity of a memory unit = The number of words x The number of bits/words. For the memory of 4k x 16 the number of separate address and data lines needed is
12 address and 16 data lines 12 address and 12 data lines 11 address and 6 data lines 12 address and 8 data lines

(5) A system has m number of resources of same type and 3 processes A, B and C. share these resources. A, B and C have the peak demand of 3, 4 and 6 respectively. Deadlock will not occur if
m = 15 m = 8 m = 13 m = 9

Web technologies questions and answers

(1) Out of the options given below the one, which is not a client server application is
Ping E-mail Web browsing Internet chat

(2) We have an HTML form that is to be designed to enable purchase of office stationary. For the items that are selected mark it with check. Submit button is to be pressed ones the credit card details are filled. Assuming that security is handled in a way that is transparent to the form design, the option that would be appropriate for sending the data to the server is
Only POST Only GET Either GET or POST Neither GET nor POST

(3) The objects that can be used in expression and scriplets in JSP without explicitly declaring them is
Response and session only Session and request only Request and response only Session, request and response

(4) _____________ indicates a correct association of the three commands PROMPT, HEAD and RCPT with protocols where these are used
FTP, HTTP, SMTP HTTP, FTP,SMTP SMTP,HTTP,FTP HTTP, SMTP,FTP

(5) Which one of the following statement about HTTP is false?
It can be used to test the validity of a hypertext links It allows information to be stored in a UR It runs over TCP protocol It describes the structure of web pages

Software Engineering questions and answers

(1) Each of the modules A and B shown in the figure below has cyclomatic complexity 10. The cyclomatic complexity of the sequential integration of A and B is

20 22 19 10

(2) For the good software requirement specifications (SRS) document
Goals of implementation are not desired. Algorithm for software implementation is not desired Non-functional requirements are not desired Functional requirements are not desired

(3) A software for digital signal processing which is expected to have 40000 lines of code needs to be developed by a company. This software is to be developed using the basic COCOMO model and for this the company needs to determine the effort in person-months. For the software development on the embedded system, the multiplicative factor for this model is 2.8 and the exponentiation factor is 1.20. The estimated effort in person month is
287.47 950.35 234.25 122.5

(4) Three statements about the cyclomatic complexity of the control flow graph as a program module are given below:
I) The cyclomatic complexity of a modules level to maximum number of linear independent circuits in a graph.
II) The cyclomatic complexity of a module is the addition of the number of number of decisions in the module and the one where a decision is effectively any conditional statements in the 

module.
III) The cyclomatic complexity can also be used as number of linearly independent paths that should be tested during path coverage testing.
The statements that hold true for the cyclomatic complexity is
II and III I and II I and III I, II and III

(5) We have different modules of software whose coupling is categorized as follows:
a. Content coupling
b. Common coupling
c. Control coupling
d. Stamp coupling
e. Data coupling

Which one of the following option indicates the coupling between modules ranked in the order of strongest (least desirable) to weakest (most desirable)?
b, d, a, c, e a, c, e, b, d e, d, c, b, a a, b, c, d, e

Computer Architecture Organization questions and answers

(6) If 1Mbyte is the board memory of a graphics card then the mode, which does not support card, is
On a 14” monitor 1600x400 resolution with 16 million colors On a 17” monitor 1600x400 resolution with 256 colors On a 17” monitor 800x400 resolution with 16 million colors On a 14” monitor 800x800 resolution with 256 colors

7.A CPU is connected with a device that is transferring data byte wise, at the rate of10Kbyte/s. Interrupt overhead = 4μs. The byte transfer time between the device interfaces register and CPU or memory is negligible. The minimum performance gain of operating the device under interrupt mode over operating it under program-controlled mode is
5 15 25 35

8.A CPU that runs at a frequency of 1GHz has a five-stage pipeline. In the first stage of the pipeline, instructions are fetched. A conditional branch instruction computes the target address and evaluation of the condition is done in the third stage of the pipeline. Until the outcome of the conditional branch is known the process does not fetch the new instruction. In this program out of 109 instructions 20% are instruction of conditional branching. What will be the total execution time of the program is each instruction takes one cycle to complete on average?
1.0s 1.1s 1.2s 1.3s

9.The one that does not interrupt a running process is
Scheduler process Power failure A device Timer

10.3 clock cycles are required for register to/from memory transfer. 1 clock cycle is required for Add with both operands in register and 2 clock cycles per word are required for instruction fetch and decode. What are the total number of clock cycles required to execute the program?
35 28 30 24

Computer Architecture Organization

(1) In a computer, whose average memory access time is 20ns has the page fault service time 10Ms. For every 106 memory accesses one page fault is generated. The effective access time for the memory is
10ns 43ns 30ns 25ns

(2) Let T1 be the time taken for a single instruction on a pipelined CPU and T2 be the time take for a single instruction on a non-pipelined but identical CPU. Comparing T1 and T2 we can say that
T1=T2 + the time taken for one instruction fetch cycle T1 T1≤T2 T1≥T2

(3) The number of bits needed for cache indexing is
10 15 5 20

(4) The number of tag bits needed is
17 20 22 25

(5) A and B are the data inputs and Y is the control input of a multiplexer. When Y = 0 data input A is selected and when Y = 1 data input B is selected. The connections required to realize the 2-variable Boolean function f = X+Z, without using any additional hardware are
X to A, 0 to B, Z to Y Z to A, 1 to B, 0 to Y Z to A, 1 to B, X to Y X to A, 1 to B, Z to Y