(1) Starting from the root and performing ____________, level order traversal of a rooted tree can be done.
Breadth first search Depth first search In-order traversal Pre-order traversal
(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)
1, _, _, _, _, _, 3 8, _, _, _, _, _, 10 1, 8, 10, _, _, _, 3 1, 10,8, _, _, _, 3
(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?
Emin is present in every minimum spanning tree of G Emax is not present in any minimum spanning tree. The removal of Emax must disconnect G, if Emax is in a minimum spanning tree. G has a unique minimum spanning tree.
(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array
Solves it in time θ (n²) Solves it in linear time using a left to right pass of the array Solves it in linear time using a right to left pass of the array Solves it using divide and conquer in time θ (n logn)
(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number of leaves in a complete n-array tree. The value of n is
5 4 3 2
Breadth first search Depth first search In-order traversal Pre-order traversal
(2) We have a hash function and a hash table. The size of hash table is 7 with starting index zero. The hash function is (3x+4) mod 7. Assume that initially the hash table is empty and the sequence 1, 3, 8, 10 is inserted into the table using closed hashing. The content of the table is (‘_’ denotes an empty location in the table)
1, _, _, _, _, _, 3 8, _, _, _, _, _, 10 1, 8, 10, _, _, _, 3 1, 10,8, _, _, _, 3
(3) Which one of the following statement is false if G is an undirected graph with distinct edge weight, Emax is the edge with maximum weight and Emin is the edge with minimum weight?
Emin is present in every minimum spanning tree of G Emax is not present in any minimum spanning tree. The removal of Emax must disconnect G, if Emax is in a minimum spanning tree. G has a unique minimum spanning tree.
(4) Consider an array L. If an element in an array L is greater than all elements to the right of it then it is called a leader. The best algorithm to find all leaders in an array
Solves it in time θ (n²) Solves it in linear time using a left to right pass of the array Solves it in linear time using a right to left pass of the array Solves it using divide and conquer in time θ (n logn)
(7) Consider a complete n-array tree. This tree is such that each node has either n number of children or no children. Let l = 10 be the number of internal nodes and L = 41 be the number of leaves in a complete n-array tree. The value of n is
5 4 3 2
No comments:
Post a Comment