Q1 – What is the result of evaluating the postfix expression “43*25*+b-“ ?
8
14
10
5
(UGC NET DEC 2023)
Ans – (Can’t tell)
Explanation –
Expression | Stack (after operation) |
4 | 4 |
3 | 4, 3 |
* | 4*3 = 12 |
2 | 12, 2 |
5 | 12, 2, 5 |
* | 12, 2*5 = 10 |
+ | 12 + 10 = 22 |
b | 22, b |
– | 22 – b |
So, this postfix expression answer is 22 – b, which is not an option.
Q2 – Which collision resolution technique involves maintaining a linked list of collided keys?
Linear probing
Quadratic probing
Chaining
Double hashing
(UGC NET DEC 2023)
Ans – (3)
Explanation – When the number two (or more) keys have the same hash value, they try to collide-in with other keys, they approach to be at the same location in the table.
The question seeks to know which of the techniques for collision resolution stores all colliding keys in a linked list, that is, all keys that would be positioned at the same location.
Chaining uses a linked list at each spot (bucket) to hold all collided keys. Each bucket of the hash table is assigned a linked list. When several keys collide-thought of as hashing to the same bucket-they are added to a linked list in that bucket.
Other alternatives are as follows
Linear Probing – where, upon collision, the function keeps on checking the subsequent slot by moving one space at a time until an empty slot is found.
Quadratic Probing – finds the next empty spot via the quadratic function (for example, adding 1², 2², etc.).
Double Hashing – Uses a second hash function to calculate the degree of the next slot found after a collision occurs.
Q3 – Which data structure is typically used to implement hash table?
Linked List
Array
Binary Tree
Stack
(UGC NET DEC 2023)
Ans – (2)
Explanation – The hash table is a data structure that employs a hashing function to store key-value pairs. This maps keys into array indices that facilitate fast insertion, deletion, and lookup operations.
Internally, the hash table uses an array to store data at specific index locations provided by the hash function.
Under ideal circumstances, this allows insert, delete, and search operations to be executed with an average-case time complexity of O(1).
