Test 1

Question 1

O(n)

Answer 1

denotes that the function has the same or lower rate of growth than n

Question 2

Ω(n)

Answer 2

denotes that the function has the same or quicker rate of growth than n

Question 3

Θ(n)

Answer 3

denotes that the function has the same rate of growth as n

Question 4

stack-empty complexity

Answer 4

O(1)

Question 5

stack push complexity

Answer 5

O(1)

Question 6

stack pop complexity

Answer 6

O(1)

Question 7

enqueue complexity

Answer 7

O(1)

Question 8

dequeue complexity

Answer 8

O(1)

Question 9

list-search

Answer 9

O(n)

Question 10

list-insert

Answer 10

O(1)

Question 11

list-delete

Answer 11

O(1)

Question 12

root

Answer 12

top element of the tree; element with no parents

Question 13

external node; leaf

Answer 13

a node with no children

Question 14

internal node

Answer 14

a node with at least one child

Question 15

tree depth

Answer 15

distance from root to a node

Question 16

tree height

Answer 16

distance from root to lowest node

Question 17

preorder, postorder, or inorder traversal complexity

Answer 17

O(n)

Question 18

preorder traversal

Answer 18

traversal in which a node is visited before its descendants

Question 19

postorder traversal

Answer 19

traversal in which a node is visited after its descendants

Question 20

inorder traversal

Answer 20

traversal in which a node is visited after its left subtree and before its right subtree

Question 21

euler tour traversal

Answer 21

a traversal that walks around the entire tree and has preorder, postorder, and inorder traversal as special cases.

Question 22

insertion sort average performance

Answer 22

O(n^2)

Question 23

quick sort average performance

Answer 23

O(n log(n))

Question 24

merge sort average performance

Answer 24

O(n log(n))

Question 25

selection sort average performance

Answer 25

O(n^2)

Question 26

counting sort average performance

Answer 26

O(n+r)

Question 27

radix sort average performance

Answer 27

O(n * k/d)

Question 28

heap

Answer 28

a nearly complete binary tree in which each node has a value > its parents value

Question 29

max-heap-insert

Answer 29

O(log(n))

Question 30

heap-extract

Answer 30

O(log(n))

Question 31

max-heapify

Answer 31

O(log(n)

Question 32

build-max-heap

Answer 32

O(n)

Question 33

heap sort

Answer 33

O(n log(n))

Question 34

chaining

Answer 34

a collision-handling strategy in which each entry in the array contains a linked list

Question 35

linear probing

Answer 35

a collision-handling strategy in which the colliding entry goes to the next linearly available index.

Question 36

double hashing

Answer 36

a collision-handling strategy in which the colliding entry gets a secondary hash function to find another index.

Question 37

binary search performance

Answer 37

O(log n)

Question 38

BST Tree Insert

Answer 38

O(h)

Question 39

BST Tree Delete

Answer 39

O(h)

Question 40

RBT Tree Insert

Answer 40

O(log n)

Question 41

RBT Tree Delete

Answer 41

O(log n)