IT2503 Data Structures Reviewer

A set of 35 vocabulary flashcards covering hash tables, sets, maps, graph representations, collision handling, and search traversal concepts from the IT2503 Pre-Final Reviewer.

Load Factor

The factor that measures how full a hash table is, representing the proportion of capacity that is occupied.

Edges

The components that represent the connections between objects in a graph data structure.

Set

A data structure that stores unique elements without duplicates.

Map

A data structure that stores elements as key-value pairs.

Hashing

The process of converting a given key into another value using a hash function.

Ordered Set

The type of set implemented using a binary search tree.

Tree Map

The map type that stores elements in sorted order.

Unweighted Graph

A graph in which all edges have equal weight.

Vertices

The elements that represent the objects or nodes in a graph data structure.

Graph Data Structure

A collection of interconnected nodes containing data that represent relationships and connections between objects.

Chaining

A collision-handling technique where multiple keys share one bucket using a linked list.

Directed Graph

A graph where each edge has a direction representing a one-way relationship.

containsKey

The hash table operation that checks if a specified key exists in the table.

Hash Function

A mathematical function that produces a fixed-size numerical output from a given key.

Unordered Set

The type of set implemented using a hash table.

BFS Queue State at Completion

In Breadth-First Search traversal, the condition where the queue becomes empty once all reachable vertices have been visited.

Collision

The situation in a hash table where several different keys produce the same hash index.

Cyclic Graph

A graph type used to model networks where some routes form loops, such as road systems with circular paths.

HashMap

A data structure designed for fast average key-based lookup, best suited for storing identifiers that change frequently.

Linked List Map

A map data structure used when keys must be processed in the exact order they were entered, preserving insertion order.

Weighted Graph

A graph where edges carry values such as cost or distance, used to determine least-costly routes.

Load Factor Threshold Exceeded

The condition where a hash table becomes too full, causing retrieval to slow down significantly due to an excessive number of collisions.

Undirected Graph

A graph type where edges represent mutual, two-way connections, such as mutual friendships in a social network.

Chaining Collision Technique

The collision-handling approach where each hash table bucket maintains a linked list of keys that hash to that slot.

TreeMap for Customer Records

The collection appropriate for maintaining records sorted by key, such as ordering customer records by account number.

Set for Tracking Visitors

The data structure best suited for keeping track of unique entities, such as distinct website visitors, by preventing duplicate entries.

Prime Number Table Size

A design parameter that minimizes key clustering when implementing division-based hash functions.

Tree-based Set

A set represented as a binary search tree, where each node represents an individual element of the set.

Linear Probing

An open addressing method in which a colliding key is placed in the next available index in the table.

Bipartite Graph

A graph consisting of two distinct sets of vertices with edges connecting only between sets, such as students connected to enrolled courses.

Disconnected Graph BFS Traversal

The procedure of starting a new Breadth-First Search on each unvisited vertex or component individually to achieve complete traversal.

Rehashing to a Larger Size

The maintenance operation performed to restore performance when load factor is too high by rebuilding the table to a larger capacity and recomputing key indices.

BFS for Isolated Vertices

The method of executing Breadth-First Search from each disconnected component to identify isolated nodes or profiles in a network.

Division-Based Hashing Function

A hash function defined by $h(k) = k \bmod m$, where choosing a prime number for the table size $m$ prevents clustering.

Rehashing at Load Factor > 0.85

The corrective procedure required when a hash table's load factor exceeds $0.85$: resizing the table and recomputing indices for all keys.