Indian Institute of Technology Mumbai (IIT-M) 2005 M.E Information Technology GATE IT - Question Paper

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

Earning:   Approval pending.