CMP4010 Computational Thinking - Week 4: Non-Linear Data Structures

Flashcards covering key vocabulary and concepts related to non-linear data structures in computational thinking.

Data Structures

Organized ways to store, manage, and retrieve data in a computational context.

Tree

A hierarchical data structure consisting of nodes, with one node as the root and other nodes as children.

Graph

A data structure that consists of a set of vertices connected by edges, representing relationships between pairs of elements.

Heap

A tree-based data structure that satisfies the heap property, where each parent node is prioritized over its children.

Hash Table

A data structure that uses a hash function to map keys to values for efficient data retrieval.

Traversal

The process of visiting each node in a data structure to access or modify its data.

Depth-First Traversal (DFT)

A graph traversal method that explores as far as possible down one branch before backtracking.

Breadth-First Traversal (BFT)

A graph traversal strategy that explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Preorder Traversal

A tree traversal method where the root node is visited before its child nodes.

Inorder Traversal

A tree traversal method where the root is visited between its left and right child nodes.

Postorder Traversal

A tree traversal method where the root node is visited after its child nodes.

Insertion (Data Structure Operation)

Adding a new data element to a data structure.

Deletion (Data Structure Operation)

Removing a data element from a data structure.

Searching (Data Structure Operation)

Finding the location of a given data element in a data structure.

Sorting (Data Structure Operation)

Arranging data elements in a logical order, either ascending or descending.

Merging (Data Structure Operation)

Combining data elements from two or more data structures into one.

Complete Graph

A graph where every pair of distinct vertices is connected by a unique edge.

Adjacent Vertices

Two vertices in a graph that are connected by an edge.

Connected Graph

A graph in which there is a path between every pair of distinct vertices.

Max-Heap

A type of heap where the value of each node is greater than or equal to the values of its children.

Min-Heap

A type of heap where the value of each node is less than or equal to the values of its children.