1. Introduction to Data Structures and Algorithms

Question 1

data structure

Answer 1

A data structure is a way of organizing, storing, and performing operations on data.

Question 2

record

Answer 2

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

Question 3

array

Answer 3

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

Question 4

linked list

Answer 4

A linked list 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.

Question 5

binary tree

Answer 5

A binary tree 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.

Question 6

hash table

Answer 6

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

Question 7

max-heap

Answer 7

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.

Question 8

min-heap

Answer 8

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.

Question 9

graph

Answer 9

A graph is a data structure for representing connections among items, and consists of vertices connected by edges.

Question 10

vertex

Answer 10

A vertex represents an item in a graph.

Question 11

edge

Answer 11

An edge represents a connection between two vertices in a graph.

Question 12

algorithm

Answer 12

An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.

Question 13

computational problem

Answer 13

A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output.

Question 14

NP-complete

Answer 14

NP-complete problems are a set of problems for which no known efficient algorithm exists.

Question 15

abstract data type / ADT

Answer 15

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.

Question 16

list

Answer 16

A list is an ADT for holding ordered data.

Question 17

dynamic array

Answer 17

A dynamic array is an ADT for holding ordered data and allowing indexed access.

Question 18

stack

Answer 18

A stack is an ADT in which items are only inserted on or removed from the top of a stack.

Question 19

queue

Answer 19

A queue is an ADT in which items are inserted at the end of the queue and removed from the front of the queue.

Question 20

deque

Answer 20

A deque (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.

Question 21

bag

Answer 21

A bag is an ADT for storing items in which the order does not matter and duplicate items are allowed.

Question 22

set

Answer 22

A set is an ADT for a collection of distinct items.

Question 23

priority queue

Answer 23

A priority queue is 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.

Question 24

dictionary

Answer 24

A dictionary is an ADT that associates (or maps) keys with values.

Question 25

compression

Answer 25

Given data represented as some quantity of bits, compression transforms the data to use fewer bits.

Question 26

Huffman coding

Answer 26

Huffman coding is a common compression technique that assigns fewer bits to frequent items, using a binary tree.

Question 27

heuristic

Answer 27

Heuristic: A technique that willingly accepts a non-optimal or less accurate solution in order to improve execution speed.

Question 28

heuristic algorithm

Answer 28

A heuristic algorithm is an algorithm that quickly determines a near optimal or approximate solution.

Question 29

0-1 knapsack problem

Answer 29

0-1 knapsack problem: The knapsack problem with the quantity of each item limited to 1.

Question 30

self-adjusting heuristic

Answer 30

A self-adjusting heuristic is an algorithm that modifies a data structure based on how that data structure is used.

Question 31

Dynamic programming

Answer 31

Dynamic programming is a problem solving technique that splits a problem into smaller subproblems, computes and stores solutions to subproblems in memory, and then uses the stored solutions to solve the larger problem.

Question 32

longest common substring

Answer 32

The longest common substring algorithm takes 2 strings as input and determines the longest substring that exists in both strings.