Here I am looking for the TANCET M.E (CSE) old Question paper, will you please provide me the same??

This is the TANCET M.E (CSE) old Question paper

1. Consider the following C function.
float f,(float x, int y) {
float p, s; int i;
for (s=1, p=1, i=1; i < y; i ++) {
p*= x/i;
s+=p;
}
return s;
}

For large values of y, the return value of the function f best approximates
• X Y
• e x
• ln (1 + x)
• X X

2. Assume the following C variable declaration
int *A [10], B [10][10];
Of the following expressions
• A[2]
• A [2] [3]
• B [1]
• B [2] [3]
which will not give compile-time errors if used as left hand sides of assignment statements in a C program ?
• I, II, and IV only
• II, III, and IV only
• II and IV only
• IV only

3. Let P(E) denote the probability of the event E. Given P(A)= 1, P(B) = 1/2, the values of P(A \ B) and P(B / A) respectively are
• ¼, ½
• ½, ¼
• ½, 1
• 1, ½

1. Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, Band C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 8 elements, and (iii) the result of merging B and C gives A ? .
• 2
• 30
• 56
• 256

5. n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is
(a)
• 3 n
• (2n)!
2 n
•

6. Let T(n) be the number of different binary search trees on n distinct elements.
Then T(n) = where x is

• n - k + 1
• n - k
• n - k – 1
• n - k - 2

7. Consider the set å * of all strings over the alphabet å = (0, 1). å * with the concatenation operator for strings
• does not form a group
• forms a non-commutative group
• does not have a right identity element
• forms a group if the empty string is removed from å *

8. Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
• k and n
• k - 1 and k + 1
• k - 1 and n - 1
• k + 1 and n-k

9. Assuming all numbers are in 2's complement representation, which of the following numbers is divisible by 11111011 ?
• 11100111
• 11100100
• 11010111
• 11011011

10. For a pipelined CPU with a single ALU, consider the following situations
• The j + 1-st instruction uses the result of the j-th instruction as an operand
• The execution of a conditional jump instruction
• The j-th and j + 1-st instructions require the ALU at the same time
Which of the above can cause a hazard?
• I and II only
• II and III only
• III only
• All the three

11. Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
• Q (1)
• Q (log n)
• Q (n)
• Q (n 2)

12. Ram and Shyam have been asked to show that a certain problem Õis NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Õ, and Shyam shows a polynomial time reduction from Õ to 3-SAT. Which of the following can be inferred from these reductions?
• Õ is NP-hard but not NP-complete
• Õ is in NP, but is not NP-complete
• Õ is NP-complete
• Õ is neither NP-hard, nor in NP

13. Nobody knows yet if P = NP. Consider the language L defined as follows:


Which of the following statements is true?
• L is recursive
• L is recursively enumerable but not recursive
• L is not recursively enumerable
• Whether L is recursive or not will be known after we find out if P = NP

14. The regular expression 0* (10*)* denotes the same set as
• (1*0)*1*
• 0 + (0 + 10)*
• (0 + 1)* 10(0 + 1)*
• none of the above
15. If the strings of a language L .can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
(a) L is necessarily finite
(b) L is regular but not necessarily finite
(c) L is context free but not necessarily regular
(d) L is recursive but not necessarily context free

16. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar ?
(a) Removing left recursion alone
(b) Factoring the grammar alone
(c) Removing left recursion and factoring the grammar
(d) None of the above

17. Assume that the SLR parser for a grammar G has n 1 states and the LALR parser for G has n 2 states. The relationship between n l and n 2 is
(a) n 1 is necessarily less than n2
(b) n 1 is necessarily equal to n2
(c) n 1 is necessarily greater than n2
(d) none of the above

18. In a bottom-up evaluation of a syntax directed definition, inherited attributes can
(a) always be evaluated
(b) be evaluated only if the definition is L-attributed
(c) be evaluated only if the definition has synthesized attributes
(d) never be evaluated

19. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?
• 7 5 1 0 3 2 4 6 8 9
• 0 2 4 3 1 6 5 9 8 7
• 0 1 2 3 4 5 6 7 8 9
• 9 8 6 4 2 3 0 1 5 7

20. Consider the following three claims
• (n + k) m = Q (n m), where k and m are constants
• 2 n + 1 = 0(2 n)
• 2 2n + 1 = 0(2 n)
Which of these claims are correct?
(a) I and II
(b) I and III
(c) II and III
(d) I, II and III

21. Consider the following graph


Among the following sequences
• a b e g h f
• a b f e h g
• a b f h g e
• a f g h b e
Which are depth first traversals of the above graph?
(a) I, II and IV only (b) I and IV only
(e) II, III and IV only (d) I, III and IV only
22. The usual Q (n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
(a) remain Q (n 2) (b) become Q (n (log n) 2)
(e) become Q (n log n) (d) become Q (n)

23. In a heap with n elements with the smallest element at the root, the 7 th smallest element can be found in time
• Q (n log n)
• Q (n)
• Q (log n)
• Q (1)

24. Which of the following statements is FALSE?
(a) In statically typed language, each variable in a program has a fixed type
(b) In un-typed languages, values do not have any types
(c) In dynamically typed languages, variables have no types
(d) In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program

25. Using a larger block size in a fixed block size file system leads to
• better disk throughput but poorer disk space utilization
• better disk throughput and better disk space utilization
• poorer disk throughput but better disk space utilization
• poorer disk throughput and poorer disk space utilization

26. In a system with 32 bit virtual addresses and 1 KB page size, use of one-level page tables for virtual to physical address translation is not practical because of
(a) the large amount of internal fragmentation
(b) the large amount of external fragmentation
(c) the large memory overhead in maintaining page tables
(d) the large computation overhead in the translation process

27. Which of the following assertions is FALSE about the Internet Protocol (IP)?
(a) It is possible for a computer to have multiple IP addresses
(b) IP packets from the same source to the same destination can take different routes in
the network
(c) IP ensures that a packet is discarded if it is unable to reach its destination within a
given number of hops
(d) The packet source cannot set the route of an outgoing packets; the route is determined
only by the routing tables in the routers on the way

28. Which of the following functionalities must be implemented by a transport protocol over and above the network protocol?
(a) Recovery from packet losses
(b) Detection of duplicate packets
(c) Packet delivery in the correct order
(d) End to end connectivity


29. Which of the following scenarios may lead to an irrecoverable error in a database system?
• A transaction writes a data item after it is read by an uncommitted transaction
• A transaction reads a data item after it is read by an uncommitted transaction
• A transaction reads a data item after it is written by a committed transaction
• A transaction reads a data item after it is written by an uncommitted transaction

30. Consider the following SQL query
select distinct a 1. a 2, ...... , a n
from r 1, r 2……….., r m
where P

For an arbitrary predicate P, this query is equivalent to which of the following relational algebra expressions?
(a)
(b)
(c)
(d)











COMPUTER SCIENCE & ENGINEERING

Section – A
• The rank of the matrix

is
• 4
• 2
• 1
• O
1.2 The trapezoidal rule for integration gives exact result when the integrand is a polynomial of degree
• 0 but not 1,
• 1 but not 0
• 0 or 1
• 2
1.3 The solution to the recurrence equation T(2 k ) = 3 T(2 k-l) + 1, T(1) = 1 is:
• 2k
• (3 k+1 - 1)/2
• 3 log 2 k
• 2 log 3 k
1.4 The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is:
• 2
• 3
• 4
• n – 2 ë n/2 û + 2
1.5 In the worst case, the number of comparisons needed to search a singly linked list
of length n for a given element is
• log 2 n
• n/2
• log 2 n – 1
• n
1.6 Which of the following is true?
• The set of all rational negative numbers forms a group under multiplication.
• The set of all non-singular matrices forms a group under multiplication.
• The set of all matrices forms a group under multiplication.
• Both B and C are true.
1.7 The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as
• Context Free
• Regular
• Deterministic Context Free
• Recursive
1.8 If X then Y unless Z" is represented by which of the following formulas in
propositional logic ? (" Ø " is negation, " Ù " is conjunction, and " ® " is implication)
• (X Ù Ø Z) ® Y
• (X Ù Y) ® Ø Z
• X ® (Y Ù Ø Z)
• (X ® Y) Ù Ø Z
1.9 A device employing INTR line for device interrupt puts the CALL instruction on the data bus while
• INTA is active
• HOLD is active
• READY is active
• None of the above
1.10 In 8085 which of the following modifies the program counter?
• Only PCHL instruction
• Only ADD instructions
• Only JMP and CALL instructions
• All instructions
1.11 In serial data transmission, every byte of data is padded with a '0' in the beginning
and one, or two ‘1's at the end of byte because
• Receiver is to be synchronized for byte reception
• Receiver recovers lost '0's and '1's from these padded bits
• Padded bits are useful in parity computation
• None of the above.
1.12 . Minimum sum of product expression for f(w,x,y,z) shown in Karnaugh-map below is
wx ®
yz ¯ 00 01 11 10
00 0 1 1 0
01 X 0 0 1
11 X 0 0 I
10 0 I 1 x
A. xz +y'z
B. xz' + zx'
C. x'y + zx'
D. None of the above
1.13 Which of the following is not a form of memory?
• instruction cache
• instruction register
• instruction opcode
• translation look aside buffer
1.14 The decimal value 0.25
• is equivalent to the binary value 0.1
• is equivalent to the binary value 0.01
• is equivalent to the binary value 0.00111…
• cannot be represented precisely in binary
1.15. The 2's complement representation of the decimal value -15 is
• 1111
• 11111
• 111111
• 10001
1.16. Sign extension is a step in
• floating point multiplication
• signed 16 bit integer addition
• arithmetic left shift
• converting a signed integer from one size to another
• In the C language
• At most one activation record exists between the current activation record and the activation record for the main
• The number of activation records between the current activation record and the activation record for the main depends on the actual function calling sequence.
• The visibility of global variables depends on the actual function calling sequence.
• Recursion requires the activation record for the recursive function to be saved on a different stack before the recursive function can be called.
1.18 The- results returned by functions under value-result and reference parameter passing conventions
• Do not differ
• Differ in the presence of loops
• Differ in all cases
• May differ in the presence of exceptions
• Relation R with an associated set of functional dependencies, F, is, decomposed into BCNF. The redundancy (arising out of functional dependencies) in the resulting set of relations is
• Zero
• More than zero but less than that of an equivalent 3NF decomposition
• Proportional to the size of P+
• Indeterminate
1.20 With regard to the expressive power of the formal relational query languages, which of the following statements is true?
• Relational algebra is more powerful than relational calculus
• Relational algebra has the same power as relational calculus
• Relational algebra has the same power as Safe relational calculus
• None of the above
1.21 In 2's complement addition, overflow
• is flagged whenever there is carry from sign bit addition
• cannot occur when a positive value is added to a negative value
• is flagged when the carries from sign bit and previous bit match
• None of the above
1.22 Which of the following scheduling algorithms is non-preemptive?
• Round Robin
• First-In First-Out
• Multilevel Queue Scheduling
• Multilevel Queue Scheduling with Feedback
¬ 1.23 The optimal page replacement algorithm will select the page that
• Has not been used for the longest time in the past.
• Will not be used for the longest time in the future .
• Has been used least number of times.
• Has been used most number of times.
1.24 In the absolute addressing mode
• the operand is inside the instruction
• the address of the operand is inside the instruction
• the register containing the address of the operand is specified inside the instruction
• the location of the operand is implicit
1.25 Maximum number of edges in a n - node undirected graph without self loops is
• n 2
• n (n-1)/2
• n-1
• (n+1)(n)/2
.
2.1 Consider the following logic circuit whose inputs are functions f 1, f 2, f 3 and output is f.

f 1(x,y,z)
f 2(x,y,z)
f3 (x,y,z)= ?
Given that
f 1(X,Y,Z) = å (0,1,3,5),
f 2(X,Y,Z) = å (6,7), and
f(x,y,z) = å (I,4,5),
f3 is
A. å (1,4,5)
B. å (6,7)
C. å (0,1,3,5)
D. None of the above
2.2 Consider the following multiplexor where I0, I1, I2, I3 are four data input lines
selected by two address line combinations AIAO =00,01,10,11 respectively and f is
the output of the multiplexor. EN is the Enable input.

The function f (x, y ,z) implemented by the above circuit is
• xyz’
• xy+z
• x+y
• None of the above
2.3. Let f(A,B} = A' +B . Simplified expression for function f (f(x+y.y),z) is
• x' +z
• xyz'
• xy' + z
• None of the above.
2.4. What are the states of the Auxiliary Carry (AC) and Carry Flag (CY) after executing the following 8085 program?
MVI H, 5DH
MVI L , 6BH
MOV A, H
ADD L
• AC= 0 and CY =0
• AC= 1 and CY= 1
• AC= 1 and CY=O
• AC = 0 and CY = 0
2.5 The Finite state machine described by the following state diagram with A as
starting state, where an arc label is x/y and x stands for I-bit input and y stands for
2-bit output

• Outputs the sum of the present and the previous bits of the input.
• Outputs 01 whenever the input sequence contains 11
• Outputs 00 whenever the input sequence contains 10
• None of the above
2.6 The performance of a pipelined processor suffers if
• the pipeline stages have different delays
• consecutive instructions are dependent on each other
• the pipeline stages share hardware resources
• all of the above
2.7 Horizontal microprogramming
• does not require use of signal decoders
• results in larger sized microinstructions than vertical microprogramming
• uses one bit for each control signal
• all of the above.
2.8 Consider the following declaration of a 'two-dimensional array in C:
char a[100][100];
Assuming that the main memory is byte-addressable and that the array is stored starting from memory address 0, the address of a[40][50] is
• 4040
• 4050
• 5040
• 5050
2.9. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
• n/2
• (n-1)/3
• (n-1)/2
• (2n+1)/3
2.10. Consider the following algorithm for searching for a given number x in an unsorted - array A[1..n] having n distinct values:
• Choose an i uniformly at random from 1..n;
• If A[i] = x then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?
• n
• n-l
• 2n
• n/2
2.11. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return (A ( é Ö n ù ));
is best described by
• O(n)
• O(log n)
• O(1og log n)
• O(1)
2.12. A weight-balanced tree is a binary tree in which for each node. The number of nodes
in the left sub tree is at least half and at most twice the number of nodes in the right
sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?
• log 2 n
• log 4/3 n
• log 3 n
• log 3/2 n
2.13. The smallest finite automaton which accepts the language
{x | length of x is divisible by 3} has .
A. 2 states
B. 3 states
C. 4 states
D. 5 states
2.14. Which of the following is true?
• The complement of a recursive language is recursive.
• The complement of a recursively enumerable language is recursively enumerable.
• The complement of a recursive language is either recursive or recursively enumerable.
• The complement of a context-free language is context-free.
• The Newton-Raphson iteration X n+l == (X n/2) + 3/(2X n)
can be used to solve the equation
• X 2 =3
• X 3=3
• X 2=2
• X 3=2
2.16 Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is
• 1/16
• 1/8
• 7/8
• 15/16
2.17 The binary relation S = f (empty set) on set A = { 1,2,3} is
• Neither reflexive nor symmetric
• Symmetric and reflexive
• Transitive and reflexive.
• Transitive and symmetric
2.18 The C language is.
• A context free language
• A context sensitive language
• A regular language
• Parsable fully only by a Turing machine
2.19. To evaluate an expression without any embedded function calls
• One stack is enough
• Two stacks are needed
• As many stacks as the height of the expression tree are needed
• A Turing machine is needed in the general case
2.20 Dynamic linking can cause security concerns because
• Security is dynamic
• The path for searching dynamic libraries is not known till runtime
• Linking is insecure
• Cryptographic procedures are not available for dynamic linking
• Which combination of the following features will suffice to characterize an OS as a multi programmed OS?
• More than one program may be loaded into main memory at the same time for execution.
• If a program waits for certain events such as I/O. another program is immediately scheduled for execution.
• If the execution of a pr ogram terminates, another program is immediately scheduled for execution.
• a
• a and b
• a and c
• a, b, and c
2.22 In the index allocation scheme of blocks to a file, the maximum possible size of the file
depends on .
• the size of the blocks, and the size of the address of the blocks.
• the number of blocks used for the index, and the size of the blocks.
• the size of the blocks, the number of blocks used for the index, and the size of the
address of the blocks.
d. None of the above
2.23 A B + -tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk blocks are of size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice
of the degree (i.e. the number of pointers per node) of the B+ -tree? .
• 16
• 42
• 43
• 44
2.24 Relation R is decomposed using a set functional dependencies, F, and relation S is decomposed using another set of functional dependencies, G. One decomposition is definitely BCNF, the other is definitely 3NF, but it is not known which is which. To make a guaranteed identification, which one of the following tests should be used on the decompositions? (Assume that the closures of F and G are available).
• Dependency-preservation
• Loss less-join
• BCNF definition
• 3NF definition
2.25 From the following instance of a relation schema R (A,B,C), we can conclude that:
A B C
1 1 1
1 1 0
2 3 2
2 3 2
• A functionally determines B and B functionally determines C
• A functionally determines B and B does not functionally determine C
• B does not functionally determine C
• A does not functionally determine B and B does not functionally determine C

Rests of the questions are in the attachment; please download it freely from here:

Attached Files

TANCET M.E (CSE) old Question paper.doc (170.5 KB, 88 views)