Unit 10: Data Structures and Algorithms

Question 1

Is a way of organizing, storing, and performing operations on data. Operations performed on a data structure include accessing or updating stored data, searching for specific data, inserting new data, and removing data.

Answer 1

Data structure

Question 2

Is the data structure that stores subitems, often called fields, with a name associated with each subitem.

Answer 2

Record

Question 3

A data structure that stores an ordered list of items, where each item is directly accessible by a positional index.

Answer 3

Array

Question 4

Is 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.

Answer 4

Linked list

Question 5

Is a data structure in which each node stores data and has up to two children, known as a left child and a right child

Answer 5

Binary tree

Question 6

Is a data structure that stores unordered items by mapping (or hashing) each item to a location in an array.

Answer 6

Hash table

Question 7

Is a tree that maintains the simple property that a node’s key is greater than or equal to the node’s childrens’ keys.

Answer 7

max-heap

Question 8

Is a tree that maintains the simple property that a node’s key is less than or equal to the node’s childrens’ keys

Answer 8

mini-heap

Question 9

Is a data structure for representing connections among items, and consists of vertices connected by edges

Answer 9

Graph

Question 10

Represents an item in a graph.

Answer 10

Vertex

Question 11

Represents a connection in a graph.

Answer 11

Edge

Question 12

Describes a sequence of steps to solve a computational problem or perform a calculation.

Answer 12

Algorithm

Question 13

Specifies an input, a question about the input that can be answered using a computer, and the desired output.

Answer 13

Computational problem

Question 14

Problems are a set of problems for which no known efficient algorithm exists.

Answer 14

Np-complete

Question 15

Efficient algorithm

Answer 15

is one whose runtime increases no more than polynomially with respect to the input size.

Question 16

A data type described by predefined user operations, such as “insert data at rear,” without indicating how each operation is implemented.

Answer 16

Abrstract data type (ADT)

Question 17

An ADT for holding ordered data. Common underlyning data structures: Array, linked list

Answer 17

List

Question 18

An ADT for holding ordered data and allowing indexed access.Common underlyning data structures: Array

Answer 18

Dynamic array

Question 19

An ADT in which items are only inserted on or removed from the top of a stack.Common underlyning data structures: Linked list

Answer 19

Stack

Question 20

An ADT in which items are inserted at the end of the queue and removed from the front of the queue.Common underlyning data structures: Linked list

Answer 20

Queue

Question 21

(pronounced “deck” and short for double-ended queue) is an ADT in which items can be inserted and removed at both the front and back. Common underlyning data structures: Linked list

Answer 21

Dqueue

Question 22

An ADT for storing items in which the order does not matter and duplicate items are allowed. Common underlyning data structures: Linked list, Array

Answer 22

Bag

Question 23

An ADT for a collection of distinct items.Common underlyning data structures: Binary tree, hash table

Answer 23

Set

Question 24

A queue where each item has a priority, and items with higher priority are closer to the front of the queue than items with lower priority.Common underlyning data structures: Heap

Answer 24

Priority queue

Question 25

An ADT that associates (or maps) keys with values.Common underlyning data structures: Hash table, binary search tree

Answer 25

Dictionary (map)

Question 26

To have a user interact with an item at a high-level, with lower-level internal details hidden from the user.

Answer 26

Abstraction

Question 27

The amount of resources used by the algorithm.

Answer 27

Computational complexity

Question 28

Typically measured by the algorithm’s computational complexity.

Answer 28

Algorithm efficiency

Question 29

A function, T(N), that represents the number of constant time operations performed by the algorithm on an input of size N

Answer 29

Runtime complexity

Question 30

The space complexity not including the input data

Answer 30

Auxillary space complexity

Question 31

Function that represents the number of fixed-size memory units used by the algorithm for an input of size N.

Answer 31

Space copmplexity