Data Structures and Algorithms - Key Terms Flashcards

A comprehensive set of Q&A flashcards covering core data structures and algorithms concepts from the lecture notes.

A mathematical model for a class of data structures with similar behavior, defining operations that can be performed but not how they are implemented.

Abstract Data Type (ADT)

A finite sequence of simple, definite steps for accomplishing a computational task that must terminate and produce an output.

Algorithm

A fixed-length, ordered collection of values of the same type stored in contiguous memory locations, with each element identified by at least one array index.

Array

The actual value or variable stored at a specific index within an array.

Array Element

A key used to identify and access a specific element within an array.

Array Index

The automatic conversion that the Java compiler makes between primitive types (like int) and their corresponding object wrapper classes (like Integer).

Autoboxing

A self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees (the balance factor) for any node is no more than 1.

AVL Tree

In an AVL tree, the value Height(Left Subtree) - Height(Right Subtree) for a node; it must be -1, 0, or +1 to keep the tree balanced.

Balance Factor

A binary tree with a strict ordering rule: keys in the left subtree are less than the node's key, and keys in the right subtree are greater; duplicates are not allowed.

Binary Search Tree (BST)

A tree data structure in which each node has at most two children, referred to as the left child and the right child.

Binary Tree

A tree traversal method that visits nodes level by level, starting from the root. Also known as Level Order Traversal.

Breadth-First Traversal (BFT)

A particular way of organizing data in a computer to be used efficiently; the arrangement of data in memory to represent values of an abstract data type.

Data Structures

A tree traversal method that explores as far as possible along each branch before backtracking. Includes Inorder, Preorder, and Postorder traversals.

Depth-First Traversal (DFT)

A queue operation that removes the first element from the front of the queue.

Dequeue

A linked list in which each node contains a data field and two pointers, one pointing to the next node and one pointing to the previous node, allowing traversal in both directions.

Doubly Linked List

A resizable array that can change its size during runtime, with memory allocated on the heap (e.g., Java's ArrayList).

Dynamic Array

A queue operation that adds an entity to the rear terminal position of a queue.

Enqueue

A principle where the first element added to a data structure (like a queue) will be the first one to be removed.

First-In-First-Out (FIFO)

A type of diagram that represents an algorithm or process, showing the steps as boxes of various kinds and their order by connecting them with arrows.

Flowchart

A method for storing and retrieving records from a database by performing a computation on a search key to identify its position in a hash table.

Hashing

A function that performs a calculation on a search key to identify a position (slot) in a hash table.

Hash Function

An array used in a hash system to store records.

Hash Table

A depth-first traversal method where nodes are visited in the order: left subtree, root node, right subtree. For BSTs, this returns nodes in sorted order.

Inorder Traversal

A principle where the last element added to a data structure must be the first one to be removed.

Last-In-First-Out (LIFO)

A node in a tree that has no children.

Leaf Node

A data structure where elements are organized sequentially, and traversal typically follows one direction from start to end (e.g., arrays, linked lists).

Linear Data Structure

A data structure consisting of a chain of nodes, where each node contains data and a reference (a link) to the next node in the sequence.

Linked List

An abstract data type that represents a finite sequence of values, where the same value may occur more than once.

List

A fundamental component in data structures like linked lists and trees that contains information (data) and one or more links to other nodes.

Node

A language feature where a copy of a variable's value is passed to a method; the original variable is not modified by the method.

Pass-by-Value

A stack operation that returns the value of the top element without removing it.

Peek / Top in a Stack

A bit string representing a memory address that can be stored in memory and manipulated by a program.

Pointer

A stack operation that removes and returns the entity from the top of the stack.

Pop in a Stack

A depth-first traversal where nodes are visited in the order: left subtree, right subtree, root node.

Postorder Traversal

A depth-first traversal where nodes are visited in the order: root node, left subtree, right subtree.

Preorder Traversal