1. Consider the following two problems on undirected graphs
a: Given G(V, E), does G have an independent set of size |V| -4?
b: Given G(V, E), does G have an independent set of size 5?
Which one of the following is TRUE?
A. a is in P and b is NP-complete
B. a is NP-complete and b is in P
C. Both a and b are NP-complete
D. Both a and b are in P
______________________________________________
2. Consider three tables with following number of tuples in each
S(a,b,c) = 100
R(a,d,e) = 80
T(x,d,f) = 90
Tuples in S and R with same value of attribute “a” = 60
Tuples in R and T with same value of attribute “d” = 70
Maximum and minimum number of tuples in (S left outer join R) full outer join T is:
A. 130 120
B. 150 140
C. 140 130
D. 140 120
______________________________________________
3. Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ms. The minimum frame size is:
A. 94
B. 416
C. 464
D. 512
______________________________________________
4. Consider the grammar with the following translation rules and E as the start symbol.
E -> E1 # T {E.value = E1.value * T.value }
| T {E.value = T.value }
T -> T1 & F { T.value = T1.value + F.value }
| F {T.value = F.value}
F -> num {F.value = num.value }
Compute E. value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.
A. 200
B. 180
C. 160
D. 40
______________________________________________
5. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
A. P3 is decidable if P1 is reducible to P3
B. P3 is undecidable if P3 is reducible to P2
C. P3 is undecidable if P2 is reducible to P3
D. P3 is decidable if P3 is reducible to P2s complement
______________________________________________
6. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
A. 2
B. 3
C. 4
D. 6
______________________________________________
7. A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000,1 by 0001,…, 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit is 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?
A. 2
B. 3
C. 4
D. 5
______________________________________________
8. Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?
A. Database relations have a large number of records
B. Database relations are sorted on the primary key
C. B+ -trees require less memory than binary search trees
D. Data transfer from disks is in blocks
______________________________________________
9. Consider the following C program segment
struct CellNode
{
struct CellNode *leftChild;
int element;
struct CellNode *rightChild;
};
int DoSomething(struct CellNode *ptr)
{
int value = 0;
if(ptr ! = NULL)
{
if(ptr->leftChild ! = NULL)
value = 1 + DoSomething(ptr - > leftChild);
if(ptr - > rightChild ! = NULL)
value = max(value, 1 + DoSomething(ptr - > rightChild));
}
return (value);
}
The value returned by the function DoSomething when a pointer to the root of a non-empty tree is passed as argument is
A. The number of leaf nodes in the tree
B. The number of nodes in the tree
C. The number of internal nodes in the tree
D. The height of the tree
______________________________________________
10. Consider the following program segment for a hypothetical CPU having three user registers Rl, R2 and R3.
Let the clock cycles required for various operations be as follows:Register to/from memory transfer: 3 clock cycles
ADD with both operands in register: 1 clock cycle
Instruction fetch and decode: 2 clock cycles per word
The total number of clock cycles required to execute the program isA. 29
B. 24
C. 23
D. 20
______________________________________________
11. A hash table implementation uses function of (% 7) and linear probing to resolve collision. What is the ratio of numbers in the following series with out collision and with collision if 7 buckets are used:
32, 56, 87, 23, 65, 26, 93
A. 2,5
B. 3,4
C. 4,3
D. 5,2
______________________________________________
12. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
A. 2
B. 3
C. 4
D. 6
______________________________________________
13. A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is
A. 0.5
B. 0.625
C. 0.75
D. 1.0
______________________________________________
14. Assume the following C variable declaration
int *A [10], B [10][10];
Of the following expressions
I. A[2]
II. A [2] [3]
III. B[l]
IV. B[2][3]
which will not give compile-time errors if used as left hand sides of assignment statements in a C program?
A. I, II, and IV only
B. II, III, and IV only
C. II and IV only
D. IV only
______________________________________________
15. Packets of the same session may be routed through different paths in
A. TCP, but not UDP
B. TCP and UDP
C. UDP, but not TCP
D. Neither TCP, nor UDP
______________________________________________
16. Which one of the following is true for a CPU having a single interrupt request line and a single interrrupt grant line?
A. Neither vectored interrupt nor multiple interrupting devices are possible.
B. Vectored interrupts are not possible but multiple interrupting devices are possible.
C. Vectored interrupts and multiple interrupting devices are both possible.
D. Vectored interrupt is possible but multiple interrupting devices are not possible.
______________________________________________
17. Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d1 d2… dm.
int n, rev;
rev = 0;
while(n > 0)
{
rev = rev * 10 + n % 10;
n = n/10;
}
The loop invariant condition at the end of the ith iteration is:
A. n = d1d2… dm-i and rev = dmdm-1….dm-i+1
B. n = dm-i+1…dm-1dm (or) rev = dm-i…d2d1
C. n != rev
D. n = d1d2…dm (or) rev = dm…d2d1
______________________________________________
18. Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that
(i) each is sorted in ascending order,
(ii) B has 5 and C has 3 elements,
(iii) the result of merging B and C gives A?
A. 2
B. 30
C. 56
D. 256
______________________________________________
19. In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is
A. 4
B. 6
C. 7
D. 9
______________________________________________
20. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true ?
(i) 9679, 1989, 4199 hash to the same value
(ii) 1471, 6171 hash to the same value
(iii) All elements hash to the same value
(iv) Each element hashes to a different value
A. (i) only
B. (ii) only
C. (i) and (ii) only
D. (iii) or (iv)
____________________________________________
______________________________________________
Answers
1. C
2. C
3. C
4. C
5. A
6. B
7. C
8. D
9. D
10. B
11. C
12. B
13. A
14. D
15. B
16. B
17. A
18. D
19. D
20. C
0 comments:
Post a Comment