Skip to main content

GATE Questions-Data Structures-Hashing

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:

A
B
C
D
0




1




2
42
42
42
42
3
52
23
23
33
4
34
34
34
23
5
23
52
52
34
6
46
33
46
46
7
33
46
33
 52
8




9




10




GATE-2010
2. How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
(a) 10 (b) 20 (c) 30 (d) 40

Ans: option (c)
Explanation:
For the above hash table to occur, collision occurs for 52 and 33. That means, 42 and 23 must always appear before 52 and 33. Also note that 34 should always come before 52 and 33, else 52 and 33 may occupy 34's place. Therefore 42,23, and 34 should appear before 52 and 33. Hence 42, 23 and 34 can occur in 3! ways.
Now notice that 52 should come before, and finally 46 can appear at 5 different places.

Therefore, total number of different sequences = 3! x 5 = 30


GATE-2004
3. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i) 9679, 1989, 4199 hash to the same value
ii) 1471, 6171 has to the same value
iii) All elements hash to the same value
iv) Each element hashes to a different value
(a) i only (b) ii only (c) i and ii only (d) iii or iv

Ans: option (c)
Explanation:
Refer question number 1.

GATE-2007
4. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that ‘_’ denotes an empty location in the table.
(a) 8, _, _, _, _, _, 10         (b) 1, 8, 10, _, _, _, 3
(c) 1, _, _, _, _, _,3 (d) 1, 10, 8, _, _, _, 3

Ans: option (b)
Explanation:
Refer question number 1.
h(x) = (3x + 4) mod 7
h(1) = (3 + 4) mod 7 = 0
h(3) = (9 + 4) mod 7 = 6
h(8) = (24 + 4) mod 7 = 0
h(10) = (3 + 4) mod 7 = 6

0
1
1
8
2
10
3

4

5

6
3

Comments

Popular posts from this blog

C Questions

C Questions
C Questions

Note : All the programs are tested under Turbo C/C++ compilers.
It is assumed that,
Programs run under DOS environment, The underlying machine is an x86 system, Program is compiled using Turbo C/C++ compiler.
The program output may depend on the information based on this assumptions (for example sizeof(int) == 2 may be assumed).
Predict the output or error(s) for the following:

void main()
{
int const * p=5; printf("%d",++(*p));
}
Answer:
Compiler error: Cannot modify a constant value.
Explanation:
p is a pointer to a "constant integer". But we tried to change the value of the "constant integer".
main()
{
char s[ ]="man"; int i;
for(i=0;s[ i ];i++)
printf("\n%c%c%c%c",s[ i ],*(s+i),*(i+s),i[s]);
}
Answer: mmmm
aaaa nnnn
Explanation

Zoho Interview | Set 1 (Advanced Programming Round)

Third Round: (Advanced Programming Round) Here they asked us to create a “Railway reservation system” and gave us 4 modules. The modules were:
    1. Booking
    2. Availability checking
    3. Cancellation
    4. Prepare chart
We were asked to create the modules for representing each data first and to continue with the implementation phase.

 My Solution :

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<time.h>#include<iomanip.h>#include<fstream.h>char f[10]="f";char s[10]="s";int addr,ad,flag,f1,d,m,i,amt;float tamt; class login {public:char id[100];char pass[100];char*password;void getid(){ cout<<"Enter your id:";gets(id); password=getpass("Enter the password:");strcpy(pass,password);}void displayid(){ cout<<"Id:";puts(id); cout<<"Password:";puts(pass);}}; class detail {public:in…

Hackerrank > SQL > Basic Select

Select
01-Select All
Given a City table, whose fields are described as +-------------+----------+ | Field       | Type     | +-------------+----------+ | ID          | int(11)  | | Name        | char(35) | | CountryCode | char(3)  | | District    | char(20) | | Population  | int(11)  | +-------------+----------+
write a query that will fetch all columns for every row in the table.

My Solution
SELECT*FROM city;
---------------------------------------------------------------------------------
02-Select by ID
Given a City table, whose fields are described as