UQUIZ 4 Flashcards CS 300 UW MADISON

We are applying binary search on this specific array to find number 7:

[3,6,7,9,10,12,15,17,19]

What is the second subarray that will be checked

A

[3,6,7,9]

B

[12,15,17,19]

C

[6,7]

D

[7,9]

D

[7,9]

This is because we split array in 2, notice 10 is middle term, 7 < 10 so we discard 10 as well and have 3,6,7,9. Do a binary search on this again giving us our second subarray and then we have {7,9]

In a binary search algorithm, what happens if the middle element is equal to the target value?

A

The algorithm continues searching in the left half of the array.

B

The algorithm continues searching in the right half of the array.

C

The algorithm stops and returns the index of the middle element.

D

The algorithm returns -1.

C

The algorithm stops and returns the index of the middle element.

What is the algorithmic complexity class for selection sort

A

constant

B

linear

C

quadratic

D

logarithmic

C

quadratic

Which of the sorting algorithms below is not stable

A

Selection sort

B

Insertion sort

C

Bubble sort

A

Selection sort

What will be the state of the array after running two iterations of insertion sort?

[5,4,3,1,6]

A

[1,4,5,3,6]

B

[1,3,4,5,6]

C

[3,4,5,1,6]

D

[4,5,3,1,6]

C

[3,4,5,1,6]

What is the worst case complexity of merge sort?

A

O(N)

B

O(N2)

C

O(logN)

D

O(NlogN)

D

O(NlogN)

What is the worst case complexity for quick sort

A

O(N)

B

O(logN)

C

O(NlogN)

D

O(N2)

D

O(N2)

Which methods should be implemented when implementing the iterator interface

next(), hasNext()

Which interface should the collection implement to use the for-each loop

Iterable - for each loops rely on the iterable interface

What is the iterable interface. What is its key method?

Represents collections that can be iterated over

Its key method is iterator()

Iterator iterator()

This is implemented by classes like ArrayList

What is the iterator interface

Provides a way to iterate over elements in a collection

boolean hasNext()

next()

What does the iterator() method return

A reference to an iterator

What is depth in a tree

The distance from the root (the root is 0 so a direct connection would mean a depth of 1)

What is height in a tree

The distance from the leaves to the node specified

What is in order traversal?

Left child, parent, right child (BOTTOM UP)

What is post order traversal?

left child, right child, parent (BOTTOM UP)

What is pre order traversal

Parent, left child, right child

What is a predecessor Node?

The highest value previous node (left)

What is a successor node?

The lowest value next node (right)

How do you remove a node from a Binary Static Tree (BST)

Set the parent reference to null

How do you remove a node in the middle of your BST?

Set the parent reference of that node to reference the child node

How do you removing nodes with two children

Find successor and replace node to be removed with successor

How do you remove a node with two children but the successor is not a leaf (has children)

Replace child node of successor with it's successor

What is a balanced tree?

A tree where the depth of both the left and right subtrees differ by at most one

What is the worst case complexity of an unbalanced binary search tree

O(N)

What is a heap

Binary, nearly complete binary tree

What is a max heap

Root is the highest, each successive node is less than the previous

What is amin heap

Root is the lowest, each successive node is higher than the previous node

Good for priority queues

What is the height of a heap

O(logN)

How are heaps stored in arrays

From top to bottom, left to right - with the root at index 0 as it usually requires less instructions

How do you get a node's right child

2 x index

How do you get a node's left child

2 x index + 1

How do we get a node's parent

Floor index / 2

What is the worst case algorithmic complexity for removing an element from the heap

O(logN)

If we use in order traversal on a max heap, the first element to visit will be the maximum value

False

Given a heap with 6 nodes, what will be the index of the last internal node?

2

Consider a new node at the root of a tree, where would the previous node go

It would take the left child's place

What is the worst case algorithmic complexity for heap sort?

O(NlogN)

How many of these references/return values may be null AND cause a NullPointerException to be thrown?

students[0][1].toUpperCase()

While there can be 4 errors caused, there can only be 3 null pointers b/c toUpperCase()'s error would be a wrong data type

Which sorting algorithm would be the best choice if our array is nearly sorted?

B

insertion sort

What is the worst case complexity of getting an element at certain index i for a doubly linked list?

O(N)

Which sort is unstable

selection

Which sort is not in place

merge

Consider a heap represented with the following array:

[10, 9, 8, 4, 6, 7, 5]

What will be the new state of the array after removing the root?

B

[9, 6, 8, 4, 5, 7]

What has a faster access to O(1) elements - Arrays or LinkedLists?

Arrays O(1) ex - get()

LinkedLists O(N)

Which has faster insertions deletions - Arrays or LinkedLists?

LinkedLists O(1)

Arrays O(1)

Do you extend or implement stacks and queues?

Implement

What is a pointer

A node that has no data but contains a memory address

What is the worst-case runtime complexity of the remove() operation in a binary search tree (NOT necessarily balanced), given problem size N is the total number of elements stored in the tree?

O(N) Think of just a bunch of single branches

What direction do you percolate when inserting

New leaf might be smaller than its parent - HEAPIFY UP

What direction do you percolate when removing

Replace root with last leef, HEAPIFY DOWN