Indian Institute of Technology Kanpur (IIT-K) 2008 M.E Computer Science CBSE Gate - Question Paper

(B) 133
(C) 124
(D) 123
12. The numbers 1, 2, n are inserted in a binary search tree in a few order. In the resulting
tree, the right subtree of the root contains p nodes. The 1st number to be inserted in the tree
must be
(A) p
(B) p + 1
(C) n - p
(D)n — p + 1
13. A function f described on stacks of integers satisfies the subsequent properties. f(q5) = Oand f
(push(S,i)) = max(f (S),0)+ifor all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, two in order from bottom to top, what is f(s)?
(A) 6
(B) 4
(C) 3
(D)2
14. In a depth 1st traversal of a graph G with n vertices, k edges are marked as tree edges.
The number of connected components in G is
(A) k
(B) k + 1
(C) n — k - 1
(D)n - k
15. In the subsequent table, the left column contains the names of standard graph algorithm,
and the right column contains the time complexities of the algorithms. Match every algorithm
with its time complexity.
(1) Bellman Ford algorithm (A) 0 (mlog n)
(2) Kruskal’s algorithm (B) 0 (n3)
(3) Floyd-Warshall algorithm (C) 0 (nm)
(4) Topological Sorting (D) 0 (n + m)
(A)1-C2-A3-B4-D
(B)1-B2-D3-C4-A
(C)1-C2-D3-A4-B
(D)1-B2-A3-C4-D
16. A hash table contains 10 buckets and uses linear probing to resolve collisions. The key
values are integers and the hash function used is key 0i’o 10. if the values 43, 165, 62, 123,
142 are inserted in the table, in what location would the key value 142 be inserted?
(A) two (B) three (C) four (D)6
17. A learner wishes to create symbolic links in a computer system running Unix. 3 text
files named “file 1”, “file 2”, and “file 3” exist in her current working directory and the learner
has learn and write permissions for all 3 files. presume that file one contains info
about her hobbies, file two contains info about her friends and file three contains info
about her courses. The learner executes the subsequent sequence of commands from her
current working directory?
In — s file one file 2
In — s file two file 3
Which of the subsequent kinds of info would be lost from her file system
I. Hobbies
II. Friends
III. Courses
(A) land II only
(B) II and III only
(C) II only
(D)I and III only
18. The shell command
find. —name passwd —print is executed in/etc directory of a computer system running Unix.
Which of the subsequent shell commands will provide the identical info as the above command
when executed in the identical directory?
(A) Is passwd
(B) cat passwd
(C) grep name passwd
(D) grep print passwd
19. A user level process in Unix traps the signal sent on a Ctrl-C input, and has a signal
handling routine that saves improper files before terminating the process. When a Ctrl-C
input is provided to this process, what is the mode in which
the signal handling routine executes?
(A) kernel mode
(B) superuser mode
(C) privileged mode
(D) user mode
20. The Function Point (FP) computed for a software project are often used to find an
estimate of Lines of Code (LOC) needed for that project. Which of the subsequent statements if
FALSE in this situation.
(A) The relationship ranging from FP and LOC depends on the programming language used to
implement the software.
(B) LOC requirement for an assembly language implementation will be more for a provided FP
value, than LOC for implementation in COBOL.
(C) On an average, 1 LOC of C++ provides approximately 1.6 times the functionality of a
single LOC of FORTRAN.
(D) FP and LOC are not related to every other.

Earning:   Approval pending.