Showing posts with label GATE-Data Structures. Show all posts
Showing posts with label GATE-Data Structures. Show all posts
Friday, January 4, 2013
GATE Questions-Data Structures-Hashing
2 comments:
Labels:
GATE,
GATE-Data Structures
Previous GATE questions with solutions on Data Structures (Hashing) - CS/IT
GATE-2010
1. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
0
|
|
1
|
|
2
|
42
|
3
|
23
|
4
|
34
|
5
|
52
|
6
|
46
|
7
|
33
|
8
|
|
9
|
|
10
|
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
(a) 46, 42, 34, 52, 23, 33
(b) 34, 42, 23, 52, 33, 46
(c) 46, 34, 42, 23, 52, 33
(d) 42, 46, 33, 23, 34, 52
Ans: option (c)
Explanation:
Linear Probing - The location where the key value should be stored in the table is determined by the hash function. Here hash function is k mod 10. For e.g., if we need to store 42 then find 42 mod 10, then we get the value 2, that means the key value 42 should be stored in the table index 2. When there is a collision, linearly come down to locate next empty location and store the value in that location.
For the above question, only option (d) will give you the above hash table. Hash table for all options are given below:
Thursday, January 3, 2013
GATE Questions-Data Structures-Trees
16 comments:
Labels:
GATE,
GATE-Data Structures
Previous GATE questions with solutions on Data Structures (Trees) - CS/IT
GATE-1995
1. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
(a) log2n (b) n-1 (c) n (d) 2n
GATE-1995
1. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
(a) log2n (b) n-1 (c) n (d) 2n
Ans: option(b)
Explanation:
A binary tree is a tree data structure in which each node has at most two child nodes.
The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1, or 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
A binary tree is a tree data structure in which each node has at most two child nodes.
The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1, or 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
GATE Questions-Data Structure- Arrays
10 comments:
Labels:
GATE,
GATE-Data Structures
Previous GATE questions with solutions on Data Structures (Arrays) - CS/IT
GATE-2005
(a) An array of 50 numbers
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers
Ans: Option (a)
Explanation:
GATE-2005
1. A program P reads in 500 integers in the range [0,100] representing the scores of 500 students. It then prints the frequency of each score above 50. what would be the best way for P to store the frequencies?
(a) An array of 50 numbers
(b) An array of 100 numbers
(c) An array of 500 numbers
(d) A dynamically allocated array of 550 numbers
Ans: Option (a)
Explanation:
We have to store frequencies of scores above 50. That is number of students having score 51, number of students having score 52 and so on. For that an array of size 50 is the best option.
Subscribe to:
Posts (Atom)