Graphs and Hashing Data Structures

Comprehensive fill-in-the-blank practice flashcards covering graph data structures, representations, traversals (BFS & DFS), hashing components, collision resolution methods, and practical applications.

A graph can be viewed as a cyclic tree where the vertices maintain complex relationships instead of a __________ relationship.

parent-child

In a directed graph, an edge from vertex $A$ to vertex $B$ designates vertex $A$ as the initial node and vertex $B$ as the __________ node.

terminal

In an undirected graph, the ordered pair $(u, v)$ and the pair __________ are considered identical.

$$(v, u)$$

In graph theory, a path is called a closed path if the initial node is identical to the __________ node.

terminal

A path that contains no repeated edges or vertices, except for the first and last vertices, is defined as a __________.

cycle

In graph terminology, an edge that is associated with the exact same end points is called a __________.

loop

A vertex in a graph that has a degree of zero is termed an __________ node.

isolated

According to the graph degree theorem, the sum of the degrees of all vertices equals twice the number of __________.

edges

The complete graph shown in the diagram containing 4 vertices is denoted as __________.

$$K_4$$

A complete graph containing $n$ vertices contains exactly __________ edges.

$$\frac{n(n-1)}{2}$$

An adjacency matrix represents a graph with $V$ vertices using a binary matrix of dimensions __________.

$$V \times V$$

In an adjacency matrix representation of a graph, querying whether an edge exists between two vertices takes __________ time.

$$O(1)$$

A major disadvantage of an adjacency matrix is that adding a new vertex takes __________ time.

$$O(V^2)$$

The graph representation depicted in the figure, which uses an array of linked lists corresponding to vertex neighbors, is an __________.

adjacency list

An adjacency list representation of a graph saves space by requiring a total space complexity of __________.

$$O(|V| + |E|)$$

Breadth-First Search (BFS) explores vertices level by level using a __________ data structure.

queue

To prevent infinite loops during graph traversal caused by cycles, algorithms maintain a boolean __________ array.

visited

The network flow algorithm that utilizes BFS to find the maximum flow in a capacitated network is the __________ algorithm.

Ford-Fulkerson

A graph whose vertices can be partitioned into two independent sets $U$ and $V$ such that no edge connects vertices of the same set is called a __________ graph.

bipartite

Depth-First Search (DFS) explores paths as deeply as possible before backtracking and inherently relies on a __________ data structure.

stack

A linear ordering of all vertices in a Directed Acyclic Graph (DAG) such that vertex $u$ appears before $v$ for every edge $(u, v)$ is called __________.

topological sorting

For finding Strongly Connected Components in a directed graph, Kosaraju's Algorithm requires __________ passes of DFS.

two

Tarjan's Algorithm identifies Strongly Connected Components (SCCs) in a directed graph using a __________ pass of DFS.

single

The transformation of variable-sized input data into a fixed, small-sized index value is known as __________.

hashing

The three fundamental components of hashing are the key, the hash function, and the __________.

hash table

In the division method of hashing with table size $M$, the hash formula is given by $h(k) =$ __________.

$$k \bmod M$$

The hash function method that squares the key and extracts the middle digits is the __________ method.

mid-square

The hash function method that partitions a key into parts and adds them modulo the table size is the __________ method.

folding

For secure data storage, passwords are saved as non-reversible __________ rather than plain text.

fingerprints

In blockchain technology, blocks are linked via hashes to guarantee permanent __________.

immutability

The string-matching algorithm that uses hashing to compare pattern segments rapidly against text segments is the __________ algorithm.

Rabin-Karp

The memory-efficient probabilistic data structure depicted below, which tests set membership with a small margin of error using a bit array, is a __________.

Bloom filter

In image processing, __________ hashing produces a compact signature of visual features to identify duplicate images despite resizing or compression.

perceptual

Compilers organize identifiers, variable names, and scope information in a hash-based structure known as a __________.

symbol table

In 3D computer graphics, objects are placed into grid cells using __________ hashing to accelerate collision detection.

spatial

In separate chaining, multiple keys hashing to the same slot are stored within a singly-linked list called a __________.

chain

If a chain in separate chaining becomes excessively long, the search time in the worst case degrades to __________.

$$O(n)$$

In open addressing, all elements reside within the hash table itself, requiring the table size to be __________ the total number of keys.

greater than or equal to

The open addressing technique that sequentially searches for the next adjacent slot when a collision occurs is called __________ probing.

linear

While linear probing offers the best cache performance, its primary drawback is that it suffers from __________.

clustering

In quadratic probing, the algorithm resolves clustering by searching for the __________ slot in the $i\text{th}$ iteration.

$$i^2\text{'th}$$

In double hashing, the offset for the $i\text{th}$ probe rotation is computed using the formula __________.

$$i \times \text{hash}_2(x)$$

The process shown in the diagram, in which a hash table is expanded and its entries are redistributed into new slots, is called __________.

rehashing

The decisive parameter that determines when to rehash, defined as the number of stored items divided by the table size, is the __________.

load factor