1.1 Data structures Flashcards
What is a data structure?
A way of organizing, storing, and performing operations on data.
What operations can be performed on a data structure?
- Accessing stored data
- Updating stored data
- Searching for specific data
- Inserting new data
- Removing data
Define a record in the context of data structures.
A data structure that stores subitems, often called fields, with a name associated with each subitem.
What is an array?
A data structure that stores an ordered list of items, where each item is directly accessible by a positional index.
True or False: A linked list stores items in an unspecified order.
False
Describe a linked list.
A data structure that stores an ordered list of items in nodes, where each node stores data and has a pointer to the next node.
What is a binary tree?
A data structure in which each node stores data and has up to two children, known as a left child and a right child.
Define a hash table.
A data structure that stores unordered items by mapping (or hashing) each item to a location in an array.
What is a heap?
A tree that maintains the property that a node’s key is either greater than or equal to (max-heap) or less than or equal to (min-heap) the node’s children’s keys.
Explain a graph.
A data structure for representing connections among items, consisting of vertices connected by edges.
True or False: A binary tree node can have zero, one, or two children.
True
True or False: Items stored in an array can be accessed using a positional index.
True
What is the impact of choosing the appropriate data structure?
It depends on the type of data being stored and the operations the program may need to perform on that data.
Fill in the blank: A linked list avoids the _______.
shifting problem
What happens when inserting an item at a specific location in an array?
Requires making room for the item by shifting higher-indexed items.
What is required to insert a new item in a linked list?
A list node for the new item must first be created.
True or False: Inserting an item at the end of a 999-item array requires items to be shifted.
False
How many items need to be shifted when inserting at the beginning of a 999-item array?
999
How many items need to be shifted when inserting at the beginning of a 999-item linked list?
0
