Test: Graphs & Hashing- 2 - Computer Science Engineering (CSE) MCQ

# Test: Graphs & Hashing- 2 - Computer Science Engineering (CSE) MCQ

Test Description

## 10 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Graphs & Hashing- 2

Test: Graphs & Hashing- 2 for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Test: Graphs & Hashing- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Graphs & Hashing- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Graphs & Hashing- 2 below.
Solutions of Test: Graphs & Hashing- 2 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Test: Graphs & Hashing- 2 solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Graphs & Hashing- 2 | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Graphs & Hashing- 2 - Question 1

### The average search time of hashing, with linear probing will be less if the load factor

Detailed Solution for Test: Graphs & Hashing- 2 - Question 1

Load factor is the ratio of number of records that are currently present and total number of records that can be present. If the load factor is less, free space will be more. This means probability of collision is less. So, the search time will be less.

Test: Graphs & Hashing- 2 - Question 2

### A hash table can store a maximum of 10 records. Currently there are records in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2, with a has function resolving collisions by linear probing is

Detailed Solution for Test: Graphs & Hashing- 2 - Question 2

If the new record hashes onto one of the six locations 7, 8, 9, 10, 1 or 2, the location 2 will receive the new record. The probability is 6/10 (as 10 is the total possible number of locations).

 1 Crore+ students have signed up on EduRev. Have you?
Test: Graphs & Hashing- 2 - Question 3

### Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8. Which of the following locations will never be probed if a collision occurs at position 4?

Detailed Solution for Test: Graphs & Hashing- 2 - Question 3

You can verify that the 1st, 3rd, 5th, 7th...probes check at location 5.
The 2nd, 6th, 10th...probes check at location 8. The 4th, 8th, 12th...probes check at location 4. The rest of the address space, will never be probed.

Test: Graphs & Hashing- 2 - Question 4

A has table has space for 100 records. What is the probability of collision before the table is 10% full?

Detailed Solution for Test: Graphs & Hashing- 2 - Question 4

If there is only one record, then the probability of a collision will be 1/100. if 2, then 2/100 etc. If 9 then 9/100. So, the required probability is 1 + 2 + 3 ... 9/100 = 0.45.

Test: Graphs & Hashing- 2 - Question 5

A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is

Detailed Solution for Test: Graphs & Hashing- 2 - Question 5

Probability for the first record not colliding is x/x.
Probability for the second record not colliding is x - 1/x. (This is because one place is already occupied. So favorable number of cases is x-1).
Probability for the third record not colliding is x - 2/x.
Probability for the (m - 1)th record not colliding is x - (m - 2)/x.
Now the next (mth) record is resulting in a collision. Out of the x places, it should hash to one of the (m - 1) places already, filled. So probability is (m - 1)/x.
The required probability is (x/x) (x - 1/x) (x - 2/x) ...(x - (m - 2)/x) (m - 1/x)

Test: Graphs & Hashing- 2 - Question 6

In the given binary tree, using array (the array starts from index 1), you can store the node 4 at location,

Detailed Solution for Test: Graphs & Hashing- 2 - Question 6

Since, 4 is the left child of 3 and 3 have index value 3. So, 4 has index value 2 x [index value of parent 3]
= 2 x 3 = 6

Test: Graphs & Hashing- 2 - Question 7

A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 10 leaf nodes

Detailed Solution for Test: Graphs & Hashing- 2 - Question 7

10 leaf nodes, where i = internal node and l = leaf node

So number of nodes in strict binary tree will be:
Nodes = n + (n - 1), n = leaf, (n - 1) internal
= (2n - 1)
So = 10 + (10 - 1)
= 10 + 9
= 19

Test: Graphs & Hashing- 2 - Question 8

The eccentricity of node labeled 5 in the graph in

Detailed Solution for Test: Graphs & Hashing- 2 - Question 8

Eccentricity of a given node is the maximum of minimum path from other nodes to the given node.
Cost of minimum path from 1 to 5 is 7 Cost of minimum path from 2 to 5 is 6 Cost of minimum path from 3 to 5 is 4 Cost of minimum path from 4 to 5 is 7 Since the maximum is 7, eccentricity of node 5 is 7.

Test: Graphs & Hashing- 2 - Question 9

The center of the graph in above questions is the node labeled

Detailed Solution for Test: Graphs & Hashing- 2 - Question 9

Find eccentricity of all nodes.
Eccentricity of node 1 is ∞
Eccentricity of node 2 is 6
Eccentricity of node 3 is 8
Eccentricity of node 4 is 5
Eccentricity of node 5 is 7
Center of a graph is the node with minimum eccentricity.

Test: Graphs & Hashing- 2 - Question 10

In which of the following cases, linked list implementations of sparse matrices consumes the same memory space as the conventional way of storing the entire array?
(Assume all data-types need the same amount of storage.)

Detailed Solution for Test: Graphs & Hashing- 2 - Question 10

Conventional way needs a storage of m x n.
In the case of linked list implementation of sparse matrices, storage needed will be m + 3 x (the number of non-zero entries).
Only in case (c), both the methods need the same storage of 30.

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests
Information about Test: Graphs & Hashing- 2 Page
In this test you can find the Exam questions for Test: Graphs & Hashing- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Graphs & Hashing- 2, EduRev gives you an ample number of Online tests for practice

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests