DATA STRUCTURES EXAM 1 -
CHAPTER 1 QUESTIONS AND
ANSWERS
Data structure - Correct Answers -way of organizing, storing, and performing operations
on data.
linked list - Correct Answers -stores an ordered list of items in nodes, where each node
stores data and has a pointer to the next node
binary tree - Correct Answers -data structure in which each node stores data and has
up to two children, known as a left child and a right child
hash table - Correct Answers -data structure that stores unordered items by mapping
(or hashing) each item to a location in an array
- operations performed on a data structure include accessing or updating stored data,
search for specific data, inserting new data, and removing data.
record - Correct Answers -stores subitems, often called fields, with a name associated
with each subitem
array - Correct Answers -stores an ordered list of items, where each item is directly
accessible by a positional index
Heap - Correct Answers -A max-heap is a tree that maintains the simple property that a
node's key is greater than or equal to the node's childrens' keys.
A min-heap is a tree that maintains the simple property that a node's key is less than or
equal to the node's childrens' keys.
Graph - Correct Answers -A graph is a data structure for representing connections
among items, and consists of vertices connected by edges.
A vertex represents an item in a graph.
An edge represents a connection between two vertices in a graph.
(T/F) A linked list stores items in an unspecified order. - Correct Answers -False
A linked list stores an ordered list of items. The links in each node define the order in
which items are stored.
, (T/F) A node in a binary tree can have zero, one or two children - Correct Answers -
True
A binary tree node can have no children, a single left or right child, or both a left and
right child.
(T/F) A list node's data can store a record with multiple subitems - Correct Answers -
True
The data stored in a list node can be a record with multiple subitems.
Ex: A linked list storing employee data might use a record containing the employee's
name, title, and salary. Also, the list node itself can be implemented as a record, having
subitems for the data and the pointer to the next node.
(T/F) Items stored in an array can be accessed using a positional index - Correct
Answers -True
Array elements are stored in sequential locations, so can be easily accessed using an
index.
Inserting an item at the end of a 999-item array requires how many items to be shifted?
- Correct Answers -0
Appending an item just places the new item at the end of the array. No shifting of
existing items is necessary.
Inserting an item at the end of a 999-item linked list requires how many items to be
shifted? - Correct Answers -0
The new item is simply added to the end.
Inserting an item at the beginning of a 999-item array requires how many items to be
shifted? - Correct Answers -999
Inserting at the beginning requires making room for the new item. So every current item
must be shifted once.
Inserting an item at the beginning of a 999-item linked list requires how many items to
be shifted? - Correct Answers -0
No shifting of other items is required, which is an advantage of using linked lists.
Abstract data types (ADT) - Correct Answers -An abstract data type (ADT) is a data
type described by predefined user operations, such as "insert data at rear," without
indicating how each operation is implemented.
CHAPTER 1 QUESTIONS AND
ANSWERS
Data structure - Correct Answers -way of organizing, storing, and performing operations
on data.
linked list - Correct Answers -stores an ordered list of items in nodes, where each node
stores data and has a pointer to the next node
binary tree - Correct Answers -data structure in which each node stores data and has
up to two children, known as a left child and a right child
hash table - Correct Answers -data structure that stores unordered items by mapping
(or hashing) each item to a location in an array
- operations performed on a data structure include accessing or updating stored data,
search for specific data, inserting new data, and removing data.
record - Correct Answers -stores subitems, often called fields, with a name associated
with each subitem
array - Correct Answers -stores an ordered list of items, where each item is directly
accessible by a positional index
Heap - Correct Answers -A max-heap is a tree that maintains the simple property that a
node's key is greater than or equal to the node's childrens' keys.
A min-heap is a tree that maintains the simple property that a node's key is less than or
equal to the node's childrens' keys.
Graph - Correct Answers -A graph is a data structure for representing connections
among items, and consists of vertices connected by edges.
A vertex represents an item in a graph.
An edge represents a connection between two vertices in a graph.
(T/F) A linked list stores items in an unspecified order. - Correct Answers -False
A linked list stores an ordered list of items. The links in each node define the order in
which items are stored.
, (T/F) A node in a binary tree can have zero, one or two children - Correct Answers -
True
A binary tree node can have no children, a single left or right child, or both a left and
right child.
(T/F) A list node's data can store a record with multiple subitems - Correct Answers -
True
The data stored in a list node can be a record with multiple subitems.
Ex: A linked list storing employee data might use a record containing the employee's
name, title, and salary. Also, the list node itself can be implemented as a record, having
subitems for the data and the pointer to the next node.
(T/F) Items stored in an array can be accessed using a positional index - Correct
Answers -True
Array elements are stored in sequential locations, so can be easily accessed using an
index.
Inserting an item at the end of a 999-item array requires how many items to be shifted?
- Correct Answers -0
Appending an item just places the new item at the end of the array. No shifting of
existing items is necessary.
Inserting an item at the end of a 999-item linked list requires how many items to be
shifted? - Correct Answers -0
The new item is simply added to the end.
Inserting an item at the beginning of a 999-item array requires how many items to be
shifted? - Correct Answers -999
Inserting at the beginning requires making room for the new item. So every current item
must be shifted once.
Inserting an item at the beginning of a 999-item linked list requires how many items to
be shifted? - Correct Answers -0
No shifting of other items is required, which is an advantage of using linked lists.
Abstract data types (ADT) - Correct Answers -An abstract data type (ADT) is a data
type described by predefined user operations, such as "insert data at rear," without
indicating how each operation is implemented.
