Data Structures 7

Question 1

Array: access, search, insert, delete

Answer 1

Access: O(1)Search: O(n)Insert: O(n)Delete: O(n)

Question 2

Array: memory

Answer 2

Memory: O(n)

Question 3

Array: advantage, disadvantage

Answer 3

Advantage: quick insert, quick access if index is knownDisadvantage: slow search, slow delete, fixed size

Question 4

Doubly Linked List: access, search, insert, delete

Answer 4

Access: O(n)Search: O(n)Insert: O(1)Delete: O(1)

Question 5

Doubly Linked List: memory

Answer 5

Memory: O(3n) (LL: O 2n)

Question 6

Doubly Linked List: advantage, disadvantage

Answer 6

Advantage: quick insert, quick deleteDisadvantage: slow search

Question 7

Binary Tree: advantage, disadvantage

Answer 7

Advantage: quick search, delete, insertDisadvantage: complex deletion

Question 8

of elements in a binary tree

Answer 8

2^(# of rows)

Question 9

Heap: advantage, disadvantage

Answer 9

Advantage: quick insert, quick delete, access to largest itemDisadvantage: slow access to all other items

Question 10

Heap Binary Tree: access, search, insert, delete,

Answer 10

Access: O(1)Search: O(n)Insert: O (lg n) Best case: sorted arrayDelete: O (lg n)

Question 11

Heap Binary Tree: max-heapify, build-max-heap, heap-sort

Answer 11

Max-heapify: O(n)Build-max-heap: O(n)Heap-sort: O(n lgn)

Question 12

Heap Binary Tree: memory

Answer 12

Memory: O(n)

Question 13

Heap Binary Tree: definition

Answer 13

A binary tree with two additional constraints:Shape - complete treeHeap property - max/min heap

Question 14

Heap Binary Tree: advantage, disadvantage

Answer 14

Advantage: fast access, quick insert and deleteDisadvantage: slow search, efficient memory if full

Question 15

Heap-sort: definition

Answer 15

Array size doesn’t change, but heap size doesTake off bottom, reshuffle, repeatLess efficient than max-heapify because it sorts from the top instead of the bottom

Question 16

Binary Search Tree: search, insert, delete

Answer 16

Search: O(h) / balanced, O(lg n)Insert: O(h) / balanced, O(lg n)Delete: O(h) / balanced, O(lg n)

Question 17

Binary Search Tree: max, min, successor, predecessor

Answer 17

Max: O(h)Min: O(h)Successor: O(h)Predecessor: O(h)

Question 18

Binary Search Tree: property

Answer 18

value[left[x]] <= value[x]value[right[x] >= value[x]

Question 19

Binary Search Tree: memory

Answer 19

Memory: O(n)

Question 20

Binary Search Tree: advantage, disadvantage

Answer 20

Advantage: quick search, quick insert and deleteDisadvantage: slower than hash table

Question 21

Height of binary tree

Answer 21

number of edges on the longest downward path between the root and a leaflog(n) - complete binary tree

Question 22

Node height

Answer 22

number of edges on the longest downward path between node and a leaf

Question 23

Node depth

Answer 23

number of edges on the longest downward path between node and the root

Question 24

Tries: advantage, disadvantage, memory

Answer 24

Advantage: faster search than a hash table, no collisions, no hash function needed, quick insert and deleteDisadvantage: can take up more space than a hash tableMemory: A LOT - need empty memory for every possibility

Question 25

Tries: definition

Answer 25

Key-value storage; a kind of treeKey -not- stored in node, value stored in nodeNode variables : Boolean isNode, String value, array Edges

Question 26

Heap Priority Queue: insert, max, extract max, increase value

Answer 26

Heap-insert: O(lg n)Heap-maximum: O(1)Heap-extract-max: O(lg n)Heap-increase-value: O(lg n)

Question 27

Priority Queue: advantage, disadvantage

Answer 27

Advantage: cheap way to sort priorities, sometimes you want to do things firstDisadvantage: worse at inserting and searching than BST

Question 28

BST Priority Queue: insert, max, extract max, increase valye

Answer 28

BST-insert: O(h)BST-maximum: O(h)BST-extract-max: O(h)BST-increase-value: O(h)

Question 29

Red Black Tree: search, insert, delete

Answer 29

Search: O(lg n)Insert: O(lg n)Delete: O(lg n)

Question 30

Red Black Tree: max, min, successor, predecessory

Answer 30

Max: O(lg n)Min: O(lg n)Successor: O(lg n)Predecessor: O(lg n)

Question 31

Red Black Tree: memory

Answer 31

Memory: O(n)

Question 32

Red Black Tree: height

Answer 32

Height: O(lg n)

Question 33

Red Black Tree: properties

Answer 33

1. Every node is either red or black2. The root is black3. Every leaf (NIL) is black4. If a node is red, then both its children are black5. All simple paths from node to child leaves contain the same # of black nodes

Question 34

Red Black Tree: advantage, disadvantage

Answer 34

Advantage: quick insert, delete, and searchDisadvantage: complex implementation

Question 35

Black height

Answer 35

of black nodes, including nil, on the path from given node to a leaf, not inclusive; any node with height h has black-height >= h/2

Question 36

Dictionary: definition

Answer 36

A data structure that maps keys to values.

Question 37

Direct-access table: definition

Answer 37

An element key k is stored in slot k.

Question 38

Direct-access table: memory

Answer 38

Memory: O(n)

Question 39

Direct-access table: search

Answer 39

Search: O(1)

Question 40

Direct-access table: advantage, disadvantage

Answer 40

Advantage: quick search, quick insert and deleteDisadvantage: lots of wasted memory, keys must be unique, keys should be dense

Question 41

Hash tables: memory

Answer 41

An implementation of a dictionary.Memory: O(n)

Question 42

Hash tables: search, insert, delete

Answer 42

Search: O(1-n)Insert: O(1-n)Delete: O(1-n)

Question 43

Hash collision

Answer 43

two (or more) keys hash to same slot

Question 44

Chaining

Answer 44

make each slot is the head of a linked list

Question 45

ArrayLists: insert

Answer 45

Insert: often O(1), sometimes more

Question 46

ArrayLists: advantages, disadvantages

Answer 46

Advantage: advantages of an array, plus does not run out of spaceDisadvantage: inserting can be slower than an array

Question 47

Stack: definition

Answer 47

Last in, first out.

Question 48

Stack: advantage, disadvantage

Answer 48

Advantage: quick accessDisadvantage: inefficient with an array

Question 49

Graph: definition

Answer 49

Finite set of vertices connected by edges, directed or not.

Question 50

Graph: advantage, disadvantage

Answer 50

Advantage: best models real-world situationsDisadvantage: can be slow and complex

Question 51

Adjacency list: memory

Answer 51

"Memory: O(|V|+|E|) "

Question 52

Adjacency list: add vertex/edge, delete vertex/edge

Answer 52

Add vertex: O(1)Add edge: O(1)Delete vertex: O(|E|)Delete edge: O(|E|)

Question 53

Adjacency list: query for adjacency

Answer 53

Query for adjacency: O(|V|)

Question 54

Adjacency matrix: memory

Answer 54

"Memory: O(|V|^2) "

Question 55

Adjacency matrix: add vertex/edge, delete vertex/edge

Answer 55

Add vertex: O(|V|^2)Add edge: O(1)Delete vertex: O(|V|^2)Delete edge: O(1)

Question 56

Adjacency matrix: query for adjacency

Answer 56

Query for adjacency: O(1)

Question 57

Breadth-first search

Answer 57

Visits the neighbor vertices before visiting the child verticesOften used to find the shortest path from one vertex to another.A queue is usually implemented

Question 58

Depth-first search

Answer 58

Visits the child vertices before visiting the sibling verticesA stack is usually implemented

Question 59

Java stream: definition

Answer 59

a sequence of data

Question 60

Exception handling

Answer 60

When there's an error, the program makes an error object and passes it off to the runtime system, which looks for a method in the call stack to handle it.

Question 61

O(1)

Answer 61

O(1) = happens once

Question 62

O(lg n)

Answer 62

happens for up to the height of a balanced tree

Question 63

O(n)

Answer 63

happens for each element

Question 64

Θ-notation

Answer 64

asymptotically tight bound

Question 65

O-notation

Answer 65

asymptotic upper bound

Question 66

Ω-notation

Answer 66

asymptotic lower bound