CSC301: Data Structures

These flashcards cover key concepts from data structures, including definitions, classifications, and specific examples that will help reinforce understanding for the upcoming exam.

What are the main considerations when choosing a data structure?

Short access time, ease of update, economy of storage, simple maintenance, and reliability.

Define data structure.

A logical or mathematical model that organizes data.

What is a primitive data structure?

Fundamental data types like integer, real, character, and Boolean.

What is a non-primitive data structure?

Data structures created using primitive data structures, such as arrays, linked lists, queues, stacks, trees, and graphs.

What is a linear data structure?

A data structure where elements are arranged in a sequence or linear list.

Give two examples of linear data structures.

Arrays and linked lists.

What defines a non-linear data structure?

Data items are not arranged in sequence; examples include trees and graphs.

What is a binary tree?

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

Define a node in a binary tree.

An item of information in the tree that may link to other nodes.

Explain the term 'leaf' in context of trees.

A terminal node in a tree that has no children.

What is a stack?

A linear list that operates on a Last-In-First-Out (LIFO) principle.

What is a queue?

A linear list that operates on a First-In-First-Out (FIFO) principle.

How does a circular queue differ from a regular queue?

In a circular queue, the last position is connected back to the first position, thus treating the queue as circular.

What are some applications of a stack?

Function call management, expression evaluation, backtracking algorithms.

What is the use of recursion in data structures?

It is used in traversing data structures such as trees and graphs.

Define hash table in data structures.

A data structure that implements an associative array, where a hash function is used to compute an index into an array of buckets.

What is the complexity of inserting an element into a binary search tree on average?

O(log n) for balanced trees.

Describe an adjacency list representation of graphs.

A collection of lists for each vertex, where each list contains the nodes that are adjacent to it.

What is a directed graph?

A graph where edges have a direction, indicating how one node can reach another.

What is big-O notation?

A mathematical notation used to describe the upper bound of the complexity of an algorithm.

What is the purpose of linked lists?

To provide a flexible way to store collections of data, where elements can easily be inserted or removed.

Describe the difference between singly linked and doubly linked lists.

Singly linked lists contain nodes with one pointer to the next node, while doubly linked lists contain two pointers that reference both the next and previous nodes.

What is a tree traversal?

The process of visiting each node in a tree data structure in a specific order.

What are the three standard tree traversal methods?

Preorder, Inorder, and Postorder.

What is the significance of a primary key in databases?

It uniquely identifies each record in the database table.

Define an algorithm.

A step-by-step procedure for solving a problem or performing a task.

Explain what a record is in data structures.

A collection of related data fields that can be treated as a single unit.

Outline the difference between Static and Dynamic data structures.

Static data structures have a fixed size, while dynamic data structures can grow or shrink in size during program execution.