Chapter 3 Data Structures Flashcards
(25 cards)
What is a data structure?
A way of bundling data so it has well-defined rules for access, change, and scope.
What is an elementary data type?
A simple data value like integers, reals, characters, or booleans.
Difference between arrays and lists?
Arrays are fixed-type, fixed-size; lists can be variable-type and dynamic.
What is a record?
A fixed collection of variables (attributes) under a common name.
Why arrays are O(1) access?
Because element positions can be computed directly using memory offset.
What is a pointer?
A variable that stores the memory address of another variable.
Why arrays can’t store different types?
Because they use fixed-size memory blocks for each entry.
What is a linked list?
A data structure of nodes (triplets: previous, key, next) linked together.
What is the head of a list?
The first node (triplet) in a linked list.
What is a doubly linked list?
A list where each node has pointers to both the previous and next nodes.
Accessing the i-th item in a list?
O(n) since you must traverse from the head to the i-th node.
Adding an item to the end of a list?
O(1) if you use the tail pointer.
What is a queue?
A FIFO (first-in-first-out) data structure.
What is a stack?
A FILO (first-in-last-out) data structure.
What is a rooted binary tree?
A tree with a starting root node where each node has ≤ 2 children.
Structure of a binary tree node?
(left, key, right) triplet.
What is a graph?
A set of vertices and edges representing relationships.
What is an adjacency matrix?
A 2D array showing vertex connections in a graph.
What is an adjacency list?
An array of lists storing only adjacent vertices.
What is a hash function?
A function that maps data (keys) to integer indexes.
What is a hash table?
A structure using a hash function to store and access data in O(1) time.
What is a hash collision?
When two keys map to the same hash table index.
How to resolve hash collisions?
By chaining (linked lists) or open addressing (probing).
What is chaining?
Storing colliding entries in a linked list at each hash table slot.
