Test: Graphs & Hashing- 1

# Test: Graphs & Hashing- 1

Test Description

## 15 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Graphs & Hashing- 1

Test: Graphs & Hashing- 1 for Computer Science Engineering (CSE) 2022 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Graphs & Hashing- 1 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Graphs & Hashing- 1 MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Graphs & Hashing- 1 below.
Solutions of Test: Graphs & Hashing- 1 questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Graphs & Hashing- 1 solutions in Hindi for Question Bank for GATE Computer Science Engineering 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- 1 | 15 questions in 45 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Graphs & Hashing- 1 - Question 1

### Consider the following graph: Among the following sequences 1. a b e g h f 2. a b f e h g 3. a b f h g e 4. a f g h b e Which are depth first traversals of the above graph?

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

Test: Graphs & Hashing- 1 - Question 2

### In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

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

Number of vertices = n
Number of edges = k
Number of connected components = n - k
Ex. 8 vertex with 6 edges

So components = 8 - 6 = 2.

Test: Graphs & Hashing- 1 - Question 3

### Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is .

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

In graph G there is a directed edge between i to j when j is either i + 1 or 3i.

Since minimum value is finding, so we need to make edge which maximum difference in i and j here (99 - 33) = 66 is maximum. So 7 edges are needed.

Test: Graphs & Hashing- 1 - Question 4

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

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

If a graph contain n vertices and n edges and it is simple connected graph then it forms a cycle. Atleast 3 vertices should participate hence the number of spanning trees will be atleast 3.

Test: Graphs & Hashing- 1 - Question 5

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity,

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

The most efficient algorithm for finding the number of connected components (articulation point) in an undirected graph on n vertices and m edges using depth-first search takes θ(m + n) time. Assume n < m.

Test: Graphs & Hashing- 1 - Question 6

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

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

The BFS using Queue data structure is QMNPRO.

Test: Graphs & Hashing- 1 - Question 7

Let G of be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

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

Tightest upper bound on running time of DFS is

Test: Graphs & Hashing- 1 - Question 8

An advantage of chained hash table (external hashing) over the open addressing scheme is

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

Deletion is easier, because chained hash table uses linked list

Test: Graphs & Hashing- 1 - Question 9

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?
1. 9679,1989,4199 hash to the same value
2. 1471,6171 hash to the same value
3. All elements hash to the same value
4. Each element hashes to a different value

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

Input (4322,1334,1471,9679,1989,6171,6173, 4199)
Given Hash function,
h(a) = x mod 10
h(a) = h(1)
= {1471,6171} hash to the same value
h(a) = h(2) = {4322}
h(a) = h(3) = {6173}
h(a) = h(9)
= {9679,1989,4199}has to the same value.
h(0), h(5), h{6), h(7), h(8) are empty for given input.
So the statement (i) and (ii) are correct.

Test: Graphs & Hashing- 1 - Question 10

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43,165,62,123,142 are inserted in the table, in what location would the key value 142 be inserted?

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

43,165,62,123 and 142 are inserted in the table. 43 mapped to location 3,165 mapped to location 5, 62 mapped to location 2, 123 mapped to location 3 (occupied), so it goes to location 4, 142 mapped to location 2 (occupied), 3, 4, and 5 are also probes, so it goes to location 6.

Test: Graphs & Hashing- 1 - Question 11

Which of the following statement(s) is TRUE?
I. A hash function takes a message of arbitrary length and generates a fixed length code.
II. A hash function takes a message of fixed length and generates a code of variable length.
III. A hash function may give the same hash value for distinct messages.

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

A hash function takes a message of arbitrary length and generates a fixed length code, by taking mod (some value).
A hash function may give the same hash value for distinct messages.

Test: Graphs & Hashing- 1 - Question 12

Consider a hash function that distributes keys uniformly. The hash table size is 20. After hashing of how many keys will the probability that any new key hashed collides with an existing one exceed 0.5.

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

Probability of hashed 1st key = 20/20 = 1
Probability of hashed 2nd key with no collision = 19/20
Probability of hashed 3rd key with no collision = 18/20
Similarly, probability of hashed rth key with no collision
According to question: Probability of hashed (n + 1)th key with collision > 0.5 Probability of hashed (n + 1)th key with collision
P(C) = 1 - P (Till (nth) no collision)

19 x 18 x 17 .... x 20 - n + 1 < 0.5 x (20)n-1
By put n = 5, we get 0.581, for n = 6, we get 0.436, which satisfies the equation.

Test: Graphs & Hashing- 1 - Question 13

Consider the hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the has 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 dosed hashing?
Note that - denotes an empty location in the table

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

Size of hash table = 7
h(x) = (3x + 4) mod 7
h(1) =. (3.1 + 4) mod 7 = 7 mod 7
= 0; insert at 0th location.
h(3) = (3.3 + 4) mod 7 = 13 mod 7
= 6; insert at 6th location
h(8) = (3.8 + 4) mod 7 = 28 mod 7
= 0; 0th position is already filled by element 3 so insert 8 at next free location which is 1st position
h(10) = (3.10 + 4) mod 7 = 34 mod 7 = 6
but 6th position is already filled with the element 3 so insert 10 at next free location which is 2nd position

Test: Graphs & Hashing- 1 - Question 14

Consider a hash table of size 11 that uses open addressing with linear probing. Let h(k) = kmod 11 be the hash function used. A sequence of records with keys 43 36 92 87 11 4 71 13 14 is inserted into an initially empty hash table, the bins of which are indexed from zero to ten. What is the index of the bin into which the last record is inserted?

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

Test: Graphs & Hashing- 1 - Question 15

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order:
5, 28, 19, 15, 20, 33, 12, 17, 10
The maximum, minimum, and average chain lengths in the hash table, respectively, are

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

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Graphs & Hashing- 1 Page
In this test you can find the Exam questions for Test: Graphs & Hashing- 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Graphs & Hashing- 1, EduRev gives you an ample number of Online tests for practice

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests

### Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!