NAC Tech Sample Test Part B

Information Technology
1. In a graph G there are 2n vertices which correspond to ‘n’ bit strings. Two nodes are connected iff the
first 3 bits are similar. What are the number of connected components?
1. 1
2. 3
3. 8
4. 2n-3
2. Let x, y and z denote the first vertex visited in post-order, in-order and pre-order traversals respectively
of a complete binary tree. Which of the following is always true?
1. x = y
2. x = z
3. y = z
4. None of these
3. Consider the following functions: f(n)=
n 3n ; g(n) = n n log 3 3 ; h(n) = n!
Which of the following is true?
1. h(n) is O (f(n))
2. h(n) is O (g(n))
3. f(n) is O (g(n))
4. g(n) is not O (f(n))
4. Consider the following program
n = b1b2b3….bm
int n, rev;
rev = 0;
while (n > 0) {
rev = rev * 10 + n %10;
n = n/10;
}
Which of the following is true at the end of the ith iteration?
1. n = b1b2…bm–i and rev = bmbm–1….bm–i+1
2. n= bm–i+1….bm–1bm and rev = bm–i…b2b1
3. n= b1b2…bm and rev = bm…b2b1
4. none of these
5. A program ‘c’ with 200 integers in the range 0 – 50 represents the scores of 200 students. It then prints
the frequency of each score above 25. What would be the best way for ‘c’ to store the frequency?
1. an array of 25 numbers
2. an array of 50 numbers
3. an array of 200 numbers
4. a dynamically allocated array of 250 numbers