Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 3345 > Exam 1 > Flashcards

Exam 1 Flashcards

1
Q

Reversed Card

A formula in which some number in a sequence depends on the previous numbers in a sequence.

A

What is a recurrence relation?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How does a skip list search work?

A

A search proceeds along the list with the greatest span until two references are found that enclose the required key. Then the search proceeds at the next level down until the required key found, or is deemed to be not present.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Reversed Card

LIFO

A

Stacks are sometimes known as ______ lists.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the findMin algorithm?

A
  • FindMin(BinaryNode t)
    • if(t==null) return null;
    • if(t.left==null) return t;
    • return findMin(t.left);
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the Preorder traversal algorithm?

A
  • DFSPre(Node X)
    • If(X!=null)
      • Do Work at Node
      • DFSPre(x.left)
      • DFSPre(x.right)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Reversed Card

it allows GenericClass m = new GenericClass(); to be written simply as GenericClass m = new GenericClass<>();

A

What does the diamond operator do?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What four methods make up the simplest linked list interface?

A

Addathead
RemoveAtHead
Clear
isEmpty

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How much space does merge sort require?

A

2n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Reversed Card

One takes only an object as an argument
One takes an object and a nextNode as arguments

A

When making a linked list, we use two constructors, what are their differences?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What a wrapper class?

A

A data type that stores a primitive type and adds extra functionality and methods to be used on the primitive type.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the PostOrder traversal algorithm?

A
  • DFSPost
    • If(X!=null)
      • DFSPost(x.left)
      • DFSPost(x.right)
      • Do work
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Reversed Card

Finding the insertion point.

A

What is the first step to doing an insertion or deletion in a probabilistic skip list?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Classes that extend the iterable interface can implement what?

A

The enhanced for loop.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Reversed Card

  • Guess the result and prove it by induction.
  • Expand the recurrence by repeatedly substituting it into itself.
  • The general solution method.
A

What are the three main ways to solve recurrence relations?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Reversed Card

An amortized runtime means that the runtime could be as large as O(n), but if m consecutive calls are made to the member functions, the runtime is MO(logN).

A

What is amortized runtime?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Reversed Card

It enables additions and deletions at either end of the list.

A

How is a deque different?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the linear time algorithm for the positive max subsequence problem?

A

Public static int maxsubsum(int[] a)

Int max sum = 0, this sum =0;

For (int I =0, I < a.length, i++)

Thissum += a[i];

If(thissum > maxsum ) maxsum = thissum;

Else if (thissum < 0) thissum = 0;

Return maxsum;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the two modes of insert in a red-black tree?

A

Top down insert and bottom up insert

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Reversed Card

Reading the data (from disk)

A

When using an efficient algorithm, what is generally the bottleneck?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Reversed Card

A perfect binary tree of all black nodes.

A

What is embedded in every Red-Black tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is a doubly linked list?

A

A list in which every node maintains a link to its previous and next node.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the suggested probabilistic variable value for a probabilistic skip list?

A

.25

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Reversed Card

2n+2

A

What is the T(n) of a for loop from 1-n?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Reversed Card

When the work at a ndoe is performed before its children are processed.

A

What is preorder traversal?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is autoboxing/ unboxing?

A

Compiler features that allow primitive types to be passed as wrapper classes and vice versa.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is a full binary tree?

A

A tree in which every node, other than the leaves, has two children.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Reversed Card

sqrt(N)

A

What is the average depth of a binary tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Reversed Card

return root == null;

A

What is the IsEmpty algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Reversed Card

one in which the numbers are in the sequence are a product of the previous number and some k.

A

What is a geometric recurrence?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Reversed Card

A tree with the lowest amount of nodes needed to obtain a tree of height h.

A

What is a skinny AVL tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What does returning a value count as for time complexity?

A

One unit to return.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

When we are speaking of trees, N always represents what?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

How are nested loops analyzed?

A

inside out; the total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is the wild card operator?

A

?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is the recursive maxim?

A

“Don’t compute anything more than once.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Reversed Card

An in order traversal is used

A

What kind of traversal is used to evaluate an expression tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Reversed Card

Path length = 0.

A

What is the path length from every node to itself?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is the first and most crucial thing we do when creating Binary search tree functions?

A

Test for an empty tree first.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Reversed Card

depth = 0.

A

What is the depth of the root?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What are the four fundamental rules of recursion?

A
  1. You must have some base case that can be solved without recursion.
  2. The recursive call must always be with a case that makes some progress toward the base case.
  3. Assume that all recursive calls work.
  4. Never duplicate work by solving the same instance of a problem in a recursive call.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Reversed Card

?

A

What is the wild card operator?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What kind of list is required for a sufficient implementation of a deque?

A

A doubly linked list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

Reversed Card

  • Contains(x, BinaryNode t)
    • if(t == null) return false;
    • if(x.compareTo(t.Object) < 0) return contains(x, t.left);
    • if(x.compareTo(t.Object) > 0) return containts(x, t.right);
    • else return true;
A

What is the contains algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

Reversed Card

A tail node, insert at tail, remove at head

A

What extra variable and operations are used in a queue?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

Stacks are sometimes known as ______ lists.

A

LIFO

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

Every red black tree with N nodes has a height less than or equal to what?

A

2log2(n+1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Reversed Card

They are not necessarily adjacent.

A

What can be said about the nodes of a linked list’s position in memory?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Reversed Card

Log A + Log B

A

Log(A*B) = ?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What is the T(n) of a for loop from 1-n?

A

2n+2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Reversed Card

the current partition to be sorted drops below 25 (approximately).

A

The most efficient implementations of QuickSort revert to Insertion Sort when

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Reversed Card

O(log N) this is worst

A

What is the worst case tree height of an AVL tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

Reversed Card

this is the case that two Insertion took place in the right subtree of the right child.

A

Let x be the out of balance node, and k be the key that was inserted what is the case that x.rightChild.value < k ?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

Reversed Card

1 unit to initialize i, n+1 units for comparisons, and n units for all increments.

A

What is a for loops cost?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

What is the runtime of all operations in an AVL tree when lazy deletion has not occured?

A

O(log N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

Reversed Card

get, set, add, remove, isempty, clear, size, and capacity increase.

A

What are the ArrayList’s 8 basic operations?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

What is the Euclid algorithm?

A

Long(long m, long n)

while(n!=0)

long rem = m % n;

m = n;

n = rem;

return m;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

What is the time complexity of Euclids algorithm?

A

O(logn), solved by noticing that after two iterations the remainder is less than n/2.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

What are the four fundamental properties of Red-Black Trees?

A
  • Every node is either red or black.
  • The root of the tree is black.
  • A red node must have no children or exactly two black children.
  • Every path from a node x to a descendent null-link must have the same number of black nodes.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

Reversed Card

Get and Set take constant time.

A

What is the advantage of the built in ArrayList?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

What is the advantage of the built in ArrayList?

A

Get and Set take constant time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

The minimum number of nodes in an AVL tree of height h is given by what recurrence relation?

A

S(h) = S(h-1) + S(h-2) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Reversed Card

Recursion.

A

What is commonly used when writing the operations of a Binary search tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

Let x be the out of balance node, and k be the key that was inserted what is the case that x.leftchild < k < x.value?

A

this is the case that insertion took place in the right subtree of x’s left child.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

Reversed Card

Primitive types, Wrapper classes must be used.

A

What type of objects cannot be used in place of generic type parameters?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

What part of the java library includes an implementation of common data structures?

A

The java collections API

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

What are skip lists made of?

A

Ordered Linked Lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

Reversed Card

inside out; the total running time of a statement inside a group of nested loops is the running time of the statement multiplied by the product of the sizes of all the loops.

A

How are nested loops analyzed?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

If an outer class is called outer, what is the implicit reference to the outer class object that created the inner class called?

A

outer.this

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

What is the average depth of a binary tree?

A

sqrt(N)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

Reversed Card

When the work at a node is done after its children have been evaluated.

A

What is postorder traversal?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

What are the two steps for proving something by induction?

A

The first step is proving a base case, that is, showing the theorem is true for some small value.

It is shown that if k is true, the theorem must also be true for k+1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

What is the time unit of a simple operation or assignment?

A

One time unit.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

What is the length of a path?

A

The number of edges on the path, namely k-1 if k are the nodes of the path.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

Reversed Card

The unbalanced node’s child is swapped with the unbalanced node’s grandchild.

A

What happens first in a double rotation?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q

Describe the “model” computer that is used for time complexity analysis

A
  • simple instructions: addition, multiplication, comparison, and assignment
  • takes exactly one time unit to do any simple instruction.
  • has infinite memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q

What is a recurrence relation?

A

A formula in which some number in a sequence depends on the previous numbers in a sequence.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q

What is the algorithm for fast exponentiation?

A

Long power(long a, int b)

if(b == 0) return 1;

if(b == 1) return a;

if(b%2 == 0) return power(a*a, b/2);

else return power(a*a, b/2)*a;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q

Reversed Card

if(head is null) head = new Node(x, head)
else:
if(head>x) head = new Node(x, head)
else:
Node prev = head;
Node ref = head.next;
while(ref!=null && ref.val > x) move prev and ref up
prev.setNext(new Node(x, ref));

A

What is the insertInorder Algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q

Reversed Card

Nested inside of the Binary tree class.

A

Where is the binary node class usually located?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q

Reversed Card

The worst case time complexity.

A

What is generally the quantity searched for when analyzing an algorithms runtime?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q

If an array is ever used to implement a list, what must we keep track of?

A

The front and end indices, and the size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q

Reversed Card

A height variable.

A

What extra information do AVLNodes have that BSTNodes do not?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q

What is amortized runtime?

A

An amortized runtime means that the runtime could be as large as O(n), but if m consecutive calls are made to the member functions, the runtime is MO(logN).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q

What is the path from nodes N1 to Nk?

A

A sequence of nodes such that leads from n1 to nk

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q

Reversed Card

B*Log(A)

A

Log(AB) = ?*

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
90
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
91
Q

What are the add and remove operations called in a queue?

A

Enqueue, dequeue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
92
Q

What two implementations are there of the built in List interface?

A

ArrayList, and LinkedList

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
93
Q

Reversed Card

A list in which 50% of nodes have just one reference, 25% have just two, etcetera.

A

What is a probabilistic skip list?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
94
Q

Xn + Xn = ?

A

2Xn

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
95
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
96
Q

What is a probabilistic skip list?

A

A list in which 50% of nodes have just one reference, 25% have just two, etcetera.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
97
Q

Reversed Card

An arbitrary number, possibly zero.

A

A tree that is not binary may have how many children?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
98
Q

What is a perfect binary tree?

A

A full binary tree in which all the leaves are at the same depth or level.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
99
Q

Reversed Card

the running time of the test plus the larger of the running times of either statement.

A

What is the runtime of an if/else statment?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
100
Q

What is Euclid’s algorithm used for?

A

Finding the GCD of two numbers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
101
Q

What are the AVL tree properties?

A
  • Abides by the Binary search tree property.
  • The heights of the left and right subtrees of any node differ by no more than 1.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
102
Q

Reversed Card

rotate with left child

A

What function is called when Insertion took place in the left subtree of the left child of X(out-of-balance node).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
103
Q

Reversed Card

The type of object that will replace the parameter type.

A

When instantiating a class, what goes inside of the angle brackets?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
104
Q

Reversed Card

When the division into regions of size equal to powers of two is maintained.

A

When can insertion and deletion in a skip list take O(N)?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
105
Q

A rotate with left child causes the Node X to replace it’s left child with what?

A

The left child’s right subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
106
Q

Reversed Card

A list in which insertion is done at one end and removal is done at the other end.

A

What is a queue?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
107
Q

What is the runtime of an if/else statment?

A

the running time of the test plus the larger of the running times of either statement.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
108
Q

What extra information do AVLNodes have that BSTNodes do not?

A

A height variable.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
109
Q

Reversed Card

For every node X in the tree, the values of all the items in its left subtree are smaller than teh item in X, and values of all the items in its right subtree are larger than the item in X.

A

What is the Binary search tree property?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
110
Q

Reversed Card

The length of the longest path from the root to a leaf.

A

What is the height of a tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
111
Q

Reversed Card

If Logx B = a

A

Xa = B if and only if what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
112
Q

Reversed Card

The information saved on a stack when a method is called and the registers must be cleared.

A

What is a stack frame, or activation record?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
113
Q

When using an efficient algorithm, what is generally the bottleneck?

A

Reading the data (from disk)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
114
Q

Reversed Card

A postorder traversal.

A

What kind of traversal is used to convert an expression tree into a postfix expression?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
115
Q

Collections add or remove return what?

A

True or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
116
Q

Reversed Card

O(logn), which is given by the number of multiplications computed.

A

What is the runtime of fast exponentiation?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
117
Q

Reversed Card

An object, NOT a node.

A

What does the remove from head function return?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
118
Q

What is a full binary tree sometimes called?

A

A proper tree, or a 2 tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
119
Q

Reversed Card

A perfect Binary tree.

A

A Red-Black tree where all nodes are black is what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
120
Q

Reversed Card

The front and end indices, and the size.

A

If an array is ever used to implement a list, what must we keep track of?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
121
Q

What is the new size of an ArrayList after capacity expansion?

A

2(size) + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
122
Q

Reversed Card

log_(1/p)(n) where p is the probability fraction one has chosen.

A

How is the maximum level a probabilistic skip list chosen?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
123
Q

How does merge sort work?

A

sorts an array by partitioning the array into blocks of size one, then pairs of these are merged into blocks of size 2 values, then pairs of those blocks are merged into size four. This behavior continues until the entire array is enclosed in a single block.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
124
Q
A

How can we determine the relative growth of two functions f(n) and g(n)?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
125
Q

In a tree, the root of each subtree is said to be what?

A

A child of the whole tree’s root.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
126
Q

What are not compatible with the Object data type?

A

Primitive types are not compatible.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
127
Q

How many rotations maybe required to restore the balance condition of an AVL tree?

A

Only one rotation is ever needed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
128
Q

What is the runtime of adding an removing from a linked list?

A

O(1), it is constant.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
129
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
130
Q

Reversed Card

references to the nodes with the smallest and larges elemetns in a tree or subtree.

A

What do findMin and FindMax return?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
131
Q

Reversed Card

The height of the left and rigth subtrees of any node can differ by no more than 1.

A

What is the AVL tree balance condition?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
132
Q

What is an Abstract Data Type?

A

a set of objects together with a set of operations.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
133
Q

A binary tree consists of what?

A

A root and two subtrees, both of which could be empty.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
134
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
135
Q

Reversed Card

By downcasting the object to the proper type.

A

How can a generic object of Object type be accessed and used properly?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
136
Q

What do findMin and FindMax return?

A

references to the nodes with the smallest and larges elemetns in a tree or subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
137
Q

The GCD of three or more positive numbers is equal to what?

A

the product of the prime factors common to all of the integers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
138
Q

Reversed Card

The directory structure is a popular application.

A

What is a popular application of trees in operating systems?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
139
Q

Reversed Card

To the base case.

A

All recursive functions must eventually reduce to what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
140
Q

Reversed Card

A double rotation.

A

What restores the balance from an inside insertion?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
141
Q

What is the least common multiple algorithm?

A
  • Break each number down into its prime numbers.
  • Multiply together each factor the greatest number of times it occurs in any of the numbers.
  • The product is the LCM.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
142
Q

What is generally considered an error in the stack adt?

A

A pop or peek on an empty list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
143
Q

What is a type bounds?

A

it specifies the properties that the parameter types must have and goes inside of the angle brackets after the type parameter.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
144
Q

Reversed Card

The node is a unary operator, such as a unary minus (negative)

A

What does it mean if a node has only one child in an expression tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
145
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
146
Q

Reversed Card

A doubly Linked List.

A

What kind of implementation is the built in Linked List?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
147
Q

the running time of all operations in a binary search tree is what?

A

O(d) where d is the depth of the node containing the accessed item.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
148
Q

Reversed Card

  • BinaryNode Insert(x, BinaryNode t)
    • if(t==null) return new BinaryNode(x, null, null);
    • int compare = x.compareTo(t.element);
    • if(compare < 0) t.left = insert(x, t.left)
    • else if(compare > 0 ) t.right = insert(x, t.right);
    • else do nothing;
    • return t;
A

What is the binary tree insertion algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
149
Q

Reversed Card

2(size) + 1

A

What is the new size of an ArrayList after capacity expansion?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
150
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
151
Q

What is the double rotate with left child algorithm?

A
  • DoubleRotateWLeft(Node x)
    • x.left = rotateWRight(x.left);
    • Return rotateWithLeftChild(x);
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
152
Q

Reversed Card

“Don’t compute anything more than once.”

A

What is the recursive maxim?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
153
Q

How is the maximum level a probabilistic skip list chosen?

A

log_(1/p)(n) where p is the probability fraction one has chosen.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
154
Q

Reversed Card

A collection of nodes that is either empty or consists of a distinguished root node and zero or more subtrees each of whose roots are connected by a directed edge from r.

A

What is a tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
155
Q

Reversed Card

  • DoubleRotateWLeft(Node x)
    • x.left = rotateWRight(x.left);
    • Return rotateWithLeftChild(x);
A

What is the double rotate with left child algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
156
Q

What is the height of an empty AVL tree defined as?

A

height = -1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
157
Q

Reversed Card

  • FindMin(BinaryNode t)
    • if(t==null) return null;
    • if(t.left==null) return t;
    • return findMin(t.left);
A

What is the findMin algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
158
Q

A rotate with right child causes the Node X to become what

A

It’s right child’s left subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
159
Q

What is the diamond operator?

A

<>

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
160
Q

Reversed Card

When n < 25.

A

When is insertion sort generally faster?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
161
Q

Reversed Card

outer.this

A

If an outer class is called outer, what is the implicit reference to the outer class object that created the inner class called?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
162
Q

Reversed Card

2n

A

How much space does merge sort require?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
163
Q

Reversed Card

Top down insert and bottom up insert

A

What are the two modes of insert in a red-black tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
164
Q

What is an AVL tree?

A

A balanced search tree where the heights of the left and right subtrees of any node differ by no more than 1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
165
Q

What should the last node in a linked list always point to?

A

null.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
166
Q

Reversed Card

Any node other than a null link.

A

In a Red-Black tree, an internal node is considered to be what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
167
Q

Reversed Card

O(N)

A

What is the runtime of operations that must search linked lists?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
168
Q

Reversed Card

It goes in angle brackets after the class name.

A

When creating a generic class, where does a generic type parameter go?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
169
Q

How is a proof by contradiction done?

A

A statement is assumed false, it is then shown that this assumption implies that some known property is false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
170
Q

Reversed Card

sorts an array by partitioning the array into blocks of size one, then pairs of these are merged into blocks of size 2 values, then pairs of those blocks are merged into size four. This behavior continues until the entire array is enclosed in a single block.

A

How does merge sort work?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
171
Q

We say that A is congruent to B modulo N, if

A

N divides A - B, this intuitively means that the remainder is the same when N divides either A or B.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
172
Q

All insertions in a red black tree create a new what?

A

A new red node with null links.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
173
Q

In a Red-Black tree, an internal node is considered to be what?

A

Any node other than a null link.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
174
Q

How do we prove the property of the worst case height of an AVL tree to be O(log N)?

A

We construct the AVL tree of height h that contains the fewest nodes, we call these the skinniest AVL trees.

We deduce a recurrence relation for the minimum number of nodes in an AVL tree of height h.

We solve this recurrence relation and then rearrange the result to get an equation for the maximum height of an AVL tree with N nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
175
Q

Reversed Card

Nodes without children.

A

What are leaf nodes?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
176
Q

Reversed Card

An if/else statement in the else of an outer if/else statement.

A

What is the structure of the InsertInOrder algorithm for a linked list?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
177
Q

What restores the balance from an inside insertion?

A

A double rotation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
178
Q

Reversed Card

a reference that is assigned to the left or right child of the current node. i.e. t.right = insert(x, t.right);

A

Each recursive call to insert returns what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
179
Q

Each recursive call to insert returns what?

A

a reference that is assigned to the left or right child of the current node. i.e. t.right = insert(x, t.right);

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
180
Q

Reversed Card

The left child’s right subtree.

A

A rotate with left child causes the Node X to replace it’s left child with what?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
181
Q

Xa = B if and only if what?

A

If Logx B = a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
182
Q

If a tree has N nodes, how many edges does it have?

A

N-1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
183
Q

What does the delete function do if a value is not found?

A

It does nothing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
184
Q

Reversed Card

The first step is proving a base case, that is, showing the theorem is true for some small value.

It is shown that if k is true, the theorem must also be true for k+1.

A

What are the two steps for proving something by induction?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
185
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
186
Q

Reversed Card

  • Break each number down into its prime numbers.
  • Multiply together each factor the greatest number of times it occurs in any of the numbers.
  • The product is the LCM.
A

What is the least common multiple algorithm?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
187
Q

Reversed Card

printList, makeEmpty

A

What are some popular but not required linked list operations?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
188
Q

Reversed Card

Anywhere in the class where the type of an object can be anything.

A

Where is the parameter type used in a class definition?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
189
Q

What does it mean if a node has only one child in an expression tree?

A

The node is a unary operator, such as a unary minus (negative)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
190
Q

Reversed Card

LinkedList
Node

A

What are the minimal two classes needed to implement a linked list?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
191
Q

Reversed Card

The parent node sets its child node to its grandchild.

A

How is a node with one child deleted?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
192
Q

Reversed Card

MO(logN)

A

What is the runtime of find, insert, and delete in a skip list?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
193
Q

Reversed Card

An insertion took place in the right subtree of teh rigth child, or the left subtree of the left child.

A

What is meant by an outside insertion?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
194
Q

What are the two most commonly used methods for proving statements in data structure analysis?

A

Proof by induction, and proof by contradiction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
195
Q

Why must we use the static keyword when nesting a class inside of a class?

A

To allow the nested class to use the members of the outer class.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
196
Q

What are the two special cases dealt with first in most list operations?

A

Head is Node,
List is Empty.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
197
Q

Reversed Card

2n+1

A

2n + 2n = ?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
198
Q

Reversed Card

this is the case that insertion took place in the left subtree of the right child.

A

Let x be the out of balance node, and k be the key that was inserted what is the case that x.value < k < x.rightChild.value?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
199
Q

Reversed Card

  1. You must have some base case that can be solved without recursion.
  2. The recursive call must always be with a case that makes some progress toward the base case.
  3. Assume that all recursive calls work.
  4. Never duplicate work by solving the same instance of a problem in a recursive call.
A

What are the four fundamental rules of recursion?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
200
Q

When is using an inner class useful?

A

when each inner class object is associated with exactly one instance of an outer class object.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
201
Q

What can be said about the nodes of a linked list’s position in memory?

A

They are not necessarily adjacent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
202
Q

What is the essential class variable of the Linked List class?

A

the head node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
203
Q

Reversed Card

Enqueue, dequeue

A

What are the add and remove operations called in a queue?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
204
Q

Reversed Card

Linked lists are used to implement these data structures.

A

What data structure is used to implement stacks, queues and deques?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
205
Q

What is the Binary search tree property?

A

For every node X in the tree, the values of all the items in its left subtree are smaller than teh item in X, and values of all the items in its right subtree are larger than the item in X.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
206
Q

Why does deletion cause the average runtime of O(log N) to not always hold?

A

Because deltion will always faovr making one sides subtree shorter, therefore making all insertion sequences no longer equally likely.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
207
Q

Reversed Card

A binary search tree with a balance condition.

A

What is an AVL Tree?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
208
Q

Reversed Card

The number of edges on the path, namely k-1 if k are the nodes of the path.

A

What is the length of a path?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
209
Q

How is a deque different?

A

It enables additions and deletions at either end of the list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
210
Q

Reversed Card

A recursive call at the last line of a method, and an example of bad recursion.

A

What is tail recursion?

211
Q

Reversed Card

the product of the prime factors common to all of the integers.

A

The GCD of three or more positive numbers is equal to what?

212
Q

How is a generic array created?

A

(Anytype []) new Object[];

213
Q

What is the structure of the InsertInOrder algorithm for a linked list?

A

An if/else statement in the else of an outer if/else statement.

214
Q

When making a linked list, we use two constructors, what are their differences?

A

One takes only an object as an argument
One takes an object and a nextNode as arguments

215
Q

When implementing recursion, what ADT is usually used?

A

A stack

216
Q

What is the runtime of operations that must search linked lists?

A

O(N)

217
Q
A
218
Q

What is generally the quantity searched for when analyzing an algorithms runtime?

A

The worst case time complexity.

219
Q
A
220
Q

What is a for loops cost?

A

1 unit to initialize i, n+1 units for comparisons, and n units for all increments.

221
Q

Reversed Card

Object element
Node next

A

What two data members make up a linked list node?

222
Q

How can Euclids algorithm be used for finding the GCD of 3 or more positive numbers?

A

by repeatedly taking the GCDs of pairs of numbers: gcd(gcd(a, b), c)

223
Q

Reversed Card

<>

A

What is the diamond operator?

224
Q

Reversed Card

an algorithm that can correctly give an answer for the data it has read at any given time.

A

What is an online algorithm?

225
Q

Reversed Card

A sequence of nodes such that leads from n1 to nk

A

What is the path from nodes N1 to Nk?

226
Q

Reversed Card

O(nlogn).

A

What is the average case time complexity of quicksort?

227
Q

Reversed Card

A function that is defined in terms of itself.

A

Waht is a recursive function?

228
Q

What does a collection do?

A

stores identically typed objects

229
Q

What can a red node never have?

A

A red node can never have a red child, or just one child.

230
Q

What are the three cases which the delete algorithm must address?

A
  1. Deleting a leaf Node.
  2. Deleting a node with one child.
  3. Deleting a node with two children.
231
Q

Reversed Card

Finding the GCD of two numbers.

A

What is Euclid’s algorithm used for?

232
Q

What is a tree?

A

A collection of nodes that is either empty or consists of a distinguished root node and zero or more subtrees each of whose roots are connected by a directed edge from r.

233
Q

Waht is a recursive function?

A

A function that is defined in terms of itself.

234
Q

Reversed Card

It’s right child’s left subtree.

A

A rotate with right child causes the Node X to become what

235
Q

Reversed Card

O(log N)

A

What is the average depth of a binary search tree?

236
Q

Reversed Card

Test for an empty tree first.

A

What is the first and most crucial thing we do when creating Binary search tree functions?

237
Q
A
238
Q

What does the remove from head function return?

A

An object, NOT a node.

239
Q

Reversed Card

The sum of the depths of all nodes in a tree.

A

What is the intenal path length?

240
Q

What is the InOrder Traversal Algorithm?

A
  • DFSIn(Node X)
    • If(X!=null)
      • DFSIn(x.left);
      • Do work
      • DFSIn(x.right);
241
Q

Reversed Card

Proof by induction, and proof by contradiction.

A

What are the two most commonly used methods for proving statements in data structure analysis?

242
Q

What is the insertInorder Algorithm?

A

if(head is null) head = new Node(x, head)
else:
if(head>x) head = new Node(x, head)
else:
Node prev = head;
Node ref = head.next;
while(ref!=null && ref.val > x) move prev and ref up
prev.setNext(new Node(x, ref));

243
Q

What is the divide and conquer strategy?

A

split the problem into two roughly equal subproblems, which are then solved recursively and then patched together.

244
Q

What is lazy deletion?

A

When nodes have a deleted marker that is turned on when they are deleted.

245
Q

A rotate with left child causes the Node X to become what?

A

It’s left child’s right subtree.

246
Q

What is a skinny AVL tree?

A

A tree with the lowest amount of nodes needed to obtain a tree of height h.

247
Q

Reversed Card

Keep a record of frequency in each node and update it when a duplicate is added or removed.

A

What is one way to handle a tree that will have duplicates inserted?

248
Q

What is the runtime of find, insert, and delete in a skip list?

A

MO(logN)

249
Q

Reversed Card

The java collections API

A

What part of the java library includes an implementation of common data structures?

250
Q

Reversed Card

N-1

A

At worst case, a binary tree can have a depth of what?

251
Q

Reversed Card

O(d) where d is the depth of the node containing the accessed item.

A

the running time of all operations in a binary search tree is what?

252
Q

Reversed Card

O(log N)

A

What is the runtime of all operations in an AVL tree when lazy deletion has not occured?

253
Q

What is the path length from every node to itself?

A

Path length = 0.

254
Q

Reversed Card

rotate with right

A

What function is called when Insertion took place in the right subtree of the right child?

255
Q

Reversed Card

Object, left child, right child.

A

What are the variables of a BinaryNode?

256
Q

Reversed Card

A tree in which no node can have more than two children.

A

What is a binary tree?

257
Q

What does the structural condition of balance mean?

A

That no node is allowed to get too deep.

258
Q

LogA B = ?

A

(Logc B)

(Logc A)

259
Q

Reversed Card

A data type that stores a primitive type and adds extra functionality and methods to be used on the primitive type.

A

What a wrapper class?

260
Q

Reversed Card

a set of objects together with a set of operations.

A

What is an Abstract Data Type?

261
Q
A
262
Q

What is the intenal path length?

A

The sum of the depths of all nodes in a tree.

263
Q

Reversed Card

An edge from one directory node to the other.

A

In a path name, each slash indicates what?

264
Q

What are the ArrayList’s 8 basic operations?

A

get, set, add, remove, isempty, clear, size, and capacity increase.

265
Q
A
266
Q

Reversed Card

  • Abides by the Binary search tree property.
  • The heights of the left and right subtrees of any node differ by no more than 1.
A

What are the AVL tree properties?

267
Q

What time unit do declartions count for?

A

They count for no time unit.

268
Q

Reversed Card

AddAtHead
RemoveAtHead

A

These two linked list operations are identical to a stack push and pop…

269
Q

What is the rotateWithLeftChild() algorithm?

A

RotateWithLeft(Node n)

  • Node leftPoint = n.left;
  • n.left = leftPoint.right;
  • leftPoint.right = n;
  • n.height = Math.max(height(n.left), height(n.right)) + 1;
  • leftPoint.height = Math.max(height(leftpoint.left), height(leftPoint.right)) + 1;
  • Return leftPoint;
270
Q

Reversed Card

An underlying array, the array capacity, and the current number of items in the array.

A

The ArrayList class contains what data variables?

271
Q

Reversed Card

One unit to return.

A

What does returning a value count as for time complexity?

272
Q

Reversed Card

Selection sort, bubble sort, insertion sort.

A

What are three examples of simple sorting algorithms?

273
Q

Reversed Card

An extra operation for a stack that returns a value without popping the node at the head of the list.

A

What is the peek routine?

274
Q

Reversed Card

split the problem into two roughly equal subproblems, which are then solved recursively and then patched together.

A

What is the divide and conquer strategy?

275
Q

Reversed Card

the head node

A

What is the essential class variable of the Linked List class?

276
Q

Let x be the out of balance node, and k be the key that was inserted what is the case that x.rightChild.value < k ?

A

this is the case that two Insertion took place in the right subtree of the right child.

277
Q

When is an algorithm O(logn)?

A

when it takes constant time to cut the problem size by a fraction, usually 1/2.

278
Q

What is an AVL Tree?

A

A binary search tree with a balance condition.

279
Q

What fixes the balance after an outside insertion?

A

A single rotation

280
Q

What happens first in a double rotation?

A

The unbalanced node’s child is swapped with the unbalanced node’s grandchild.

281
Q

Reversed Card

When insertions and deletions occur throughout the list.

A

When is an array not a good option for a list?

282
Q

Reversed Card

Base 2

A

In computer science, all logarithms are to what base?

283
Q

What is commonly used when writing the operations of a Binary search tree?

A

Recursion.

284
Q

Reversed Card

  • simple instructions: addition, multiplication, comparison, and assignment
  • takes exactly one time unit to do any simple instruction.
  • has infinite memory
A

Describe the “model” computer that is used for time complexity analysis

285
Q

Reversed Card

That no node is allowed to get too deep.

A

What does the structural condition of balance mean?

286
Q

How can we determine the relative growth of two functions f(n) and g(n)?

A
287
Q

Reversed Card

  1. Scan the infix expression from left to right.
  2. If the scanned character is an operand, output it.
  3. Else,
    1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
    2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Repeat steps 2-6 until infix expression is scanned.
  7. Print the output
  8. Pop and output from the stack until it is not empty.
A

What is the algorithm for converting an infix expression to postfix?

288
Q

What is embedded in every Red-Black tree?

A

A perfect binary tree of all black nodes.

289
Q

What are the three main ways to solve recurrence relations?

A
  • Guess the result and prove it by induction.
  • Expand the recurrence by repeatedly substituting it into itself.
  • The general solution method.
290
Q

Reversed Card

the running time of the statements inside the for loop multiplied by the number of iterations.

A

The running time of a for loop is at most what?

291
Q

What is the base case of a recursive function?

A

It is the value for which the function is known without having to resort to recursion.

292
Q

Reversed Card

A statement is assumed false, it is then shown that this assumption implies that some known property is false.

A

How is a proof by contradiction done?

293
Q

What is the AVL tree balance condition?

A

The height of the left and rigth subtrees of any node can differ by no more than 1.

294
Q

Reversed Card

Add and remove at head take constant time.

A

What is the advantage of a LinkedList over an ArrayList?

295
Q

Reversed Card

Only one rotation is ever needed.

A

How many rotations maybe required to restore the balance condition of an AVL tree?

296
Q

What kind of implementation is the built in Linked List?

A

A doubly Linked List.

297
Q
A
298
Q

What are the only two operations besides, peek, makeEmpty, and isEmpty, that you can do to a stack?

A

Pop, Push

299
Q

Reversed Card

A single rotation

A

What fixes the balance after an outside insertion?

300
Q

Reversed Card

True or false.

A

Collections add or remove return what?

301
Q

Reversed Card

Pop, Push

A

What are the only two operations besides, peek, makeEmpty, and isEmpty, that you can do to a stack?

302
Q

Reversed Card

N-1

A

If a tree has N nodes, how many edges does it have?

303
Q

Reversed Card

A balanced search tree where the heights of the left and right subtrees of any node differ by no more than 1.

A

What is an AVL tree?

304
Q

Reversed Card

the right childs left subtree.

A

A rotate with right child causes the Node X to replace it’s right child with what?

305
Q

The most efficient implementations of QuickSort revert to Insertion Sort when

A

the current partition to be sorted drops below 25 (approximately).

306
Q

When is an array not a good option for a list?

A

When insertions and deletions occur throughout the list.

307
Q

What are leaf nodes?

A

Nodes without children.

308
Q

How is a leaf node deleted?

A

The parent node’s child node is set to null.

309
Q

Reversed Card

it divides at least one of the two numbers.

A

If a prime number N divides a product of two numbers, then

310
Q

What is the height of a tree?

A

The length of the longest path from the root to a leaf.

311
Q

Let x be the out of balance node, and k be the key that was inserted what is the case that K < x.leftChild.Value?

A

this is the case that insertion took place in the left subtree of x’s left child.

312
Q

Reversed Card

RotateWithLeft(Node n)

  • Node leftPoint = n.left;
  • n.left = leftPoint.right;
  • leftPoint.right = n;
  • n.height = Math.max(height(n.left), height(n.right)) + 1;
  • leftPoint.height = Math.max(height(leftpoint.left), height(leftPoint.right)) + 1;
  • Return leftPoint;
A

What is the rotateWithLeftChild() algorithm?

313
Q

Reversed Card

To pass functions as parameters.

A

What are function objects used for?

314
Q

What is the average running time of most operations in a binary search tree?

A

O(logN)

315
Q

Reversed Card

A child of the whole tree’s root.

A

In a tree, the root of each subtree is said to be what?

316
Q

What does the contains function do?

A

It returns true if a node in tree T has item x, or false if not.

317
Q

Reversed Card

The parent node’s child node is set to null.

A

How is a leaf node deleted?

318
Q

When creating a generic class, where does a generic type parameter go?

A

It goes in angle brackets after the class name.

319
Q

Trees are actually what?

A

Graphs

320
Q

Log(AB) = ?*

A

B*Log(A)

321
Q

What is an expression tree?

A

A tree in which the leaves are operands, such as constants or variable names, and the internal nodes contain operators.

322
Q

What is the average case time complexity of quicksort?

A

O(nlogn).

323
Q

Reversed Card

It becomes its right child’s left child.

A

When an outer insertion occurs to the right, what does the imbalanced node become?

324
Q

What does the diamond operator do?

A

it allows GenericClass m = new GenericClass(); to be written simply as GenericClass m = new GenericClass<>();

325
Q

Reversed Card

Primitive types are not compatible.

A

What are not compatible with the Object data type?

326
Q

Reversed Card

When using a generic Collections, a wild card goes inside of the angle brackets after Collection along with the extends keyword to allow a class and any of its subclasses to be used in the collection.

A

When and for what are wildcards used?

327
Q

Reversed Card

height = -1

A

What is the height of an empty AVL tree defined as?

328
Q

What is the peek routine?

A

An extra operation for a stack that returns a value without popping the node at the head of the list.

329
Q

Where is the binary node class usually located?

A

Nested inside of the Binary tree node.

330
Q

What does an AVL tree ensure?

A

It ensures that the depth of a tree is O(log N)

331
Q

What is the algorithm for converting an infix expression to postfix?

A
  1. Scan the infix expression from left to right.
  2. If the scanned character is an operand, output it.
  3. Else,
    1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
    2 Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
  4. If the scanned character is an ‘(‘, push it to the stack.
  5. If the scanned character is an ‘)’, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
  6. Repeat steps 2-6 until infix expression is scanned.
  7. Print the output
  8. Pop and output from the stack until it is not empty.
332
Q

What is the Big Oh time of a simple sorting algorithm?

A

O(N2)

333
Q

What are the three variables of a treeNode?

A

Object element;

TreeNode firstChild;

TreeNode secondChild;

334
Q

Reversed Card

Addathead
RemoveAtHead
Clear
isEmpty

A

What four methods make up the simplest linked list interface?

335
Q

Reversed Card

By enclosing the body in a while loop and replacing the recursive call with one assignment per method argument.

A

How can tail recursion be eliminated?

336
Q

Reversed Card

Classes built with no data and one single method.

A

What are function objects?

337
Q

Reversed Card

A tree in which the leaves are operands, such as constants or variable names, and the internal nodes contain operators.

A

What is an expression tree?

338
Q

Reversed Card

Let the Node be N.

N.Object = findMin(N.right).Object;

Delete(findMin(N.right);

A

How is a node with two children deleted?

339
Q

Reversed Card

Long(long m, long n)

while(n!=0)

long rem = m % n;

m = n;

n = rem;

return m;

A

What is the Euclid algorithm?

340
Q

When an outer insertion occurs to the right, what does the imbalanced node become?

A

It becomes its right child’s left child.

341
Q

Where is the insertion point in a probabilistic skip list?

A

The point in the list after the previous node.

342
Q

What function is called when Insertion took place in the left subtree of the left child of X(out-of-balance node).

A

rotate with left child

343
Q

Reversed Card

double rotate with left.

A

What function is called when Insertion took place in the right subtree of the left child?

344
Q

What function is called when Insertion took place in the right subtree of the right child?

A

rotate with right

345
Q

What interface does the Collections interface extend?

A

The iterable interface

346
Q

What type of objects cannot be used in place of generic type parameters?

A

Primitive types, Wrapper classes must be used.

347
Q

Reversed Card

A root and two subtrees, both of which could be empty.

A

A binary tree consists of what?

348
Q

What is one way to shorten code for assignments?

A

making multiple assignments in one line right to left.

349
Q
A
350
Q

What is a directory in the UNIX File System?

A

A file with a list of all its children.

351
Q

Reversed Card

Long power(long a, int b)

if(b == 0) return 1;

if(b == 1) return a;

if(b%2 == 0) return power(a*a, b/2);

else return power(a*a, b/2)*a;

A

What is the algorithm for fast exponentiation?

352
Q

Reversed Card

O(log N) assuming all insertion sequences are equally likely.

A

What is the average depth over all nodes in a binary search tree assuming that all insertion sequences are equally likely?

353
Q

These two linked list operations are identical to a stack push and pop…

A

AddAtHead
RemoveAtHead

354
Q

What data structure is used to implement stacks, queues and deques?

A

Linked lists are used to implement these data structures.

355
Q

Reversed Card

A queue

A

What ADT is used in operating systems and algorithm design?

356
Q

Reversed Card

ArrayList, and LinkedList

A

What two implementations are there of the built in List interface?

357
Q

Reversed Card

O(N2)

A

What is the Big Oh time of a simple sorting algorithm?

358
Q

When is the maximum level of a probabilistic skip list chosen?

A

At construction

359
Q

Reversed Card

A stack

A

When implementing recursion, what ADT is usually used?

360
Q

What two data members make up a linked list node?

A

Object element
Node next

361
Q

What is an online algorithm?

A

an algorithm that can correctly give an answer for the data it has read at any given time.

362
Q

Reversed Card

head = new Node(object, head);

A

The addAtHead function has only one line of code. What is it?

363
Q

The running time of a for loop is at most what?

A

the running time of the statements inside the for loop multiplied by the number of iterations.

364
Q

The ArrayList class contains what data variables?

A

An underlying array, the array capacity, and the current number of items in the array.

365
Q

What is the advantage of a LinkedList over an ArrayList?

A

Add and remove at head take constant time.

366
Q

A rotate with right child causes the Node X to replace it’s right child with what?

A

the right childs left subtree.

367
Q

Log(A*B) = ?

A

Log A + Log B

368
Q

What is postorder traversal?

A

When the work at a node is done after its children have been evaluated.

369
Q

Reversed Card

Graphs

A

Trees are actually what?

370
Q

What is a queue?

A

A list in which insertion is done at one end and removal is done at the other end.

371
Q

Reversed Card

We construct the AVL tree of height h that contains the fewest nodes, we call these the skinniest AVL trees.

We deduce a recurrence relation for the minimum number of nodes in an AVL tree of height h.

We solve this recurrence relation and then rearrange the result to get an equation for the maximum height of an AVL tree with N nodes.

A

How do we prove the property of the worst case height of an AVL tree to be O(log N)?

372
Q

Reversed Card

A reference that points to itself, and another entry that points to the parent of the directory.

A

Besides a list of its children, what else does a Unix directory have?

373
Q

Reversed Card

Head is Node,
List is Empty.

A

What are the two special cases dealt with first in most list operations?

374
Q

What kind of traversal is used to evaluate an expression tree?

A

An in order traversal is used

375
Q

Reversed Card

the process performed by the compiler that turns generic classes into non-generic classes.

A

What is type erasure?

376
Q

What is preorder traversal?

A

When the work at a ndoe is performed before its children are processed.

377
Q

Reversed Card

  • DoubleRotateWRight(node x)
    • x.right = rotateWLeft(x.right);
    • Return rotateWRight(x);
A

What is the double rotate with right child algorithm?

378
Q

Reversed Card

infix.

A

An expression that is in standard form is said to be____

379
Q

Reversed Card

this is the case that insertion took place in the right subtree of x’s left child.

A

Let x be the out of balance node, and k be the key that was inserted what is the case that x.leftchild < k < x.value?

380
Q

Reversed Card

it specifies the properties that the parameter types must have and goes inside of the angle brackets after the type parameter.

A

What is a type bounds?

381
Q

Reversed Card

O(logn), solved by noticing that after two iterations the remainder is less than n/2.

A

What is the time complexity of Euclids algorithm?

382
Q
A
383
Q

How is a node with two children deleted?

A

Let the Node be N.

N.Object = findMin(N.right).Object;

Delete(findMin(N.right);

384
Q

What is a popular application of trees in operating systems?

A

The directory structure is a popular application.

385
Q

What is the worst case tree height of an AVL tree?

A

O(log N) this is worst

386
Q

Reversed Card

Object element;

TreeNode firstChild;

TreeNode secondChild;

A

What are the three variables of a treeNode?

387
Q

All recursive functions must eventually reduce to what?

A

To the base case.

388
Q

What else may be used besides the Object class for genericity, and how?

A

An interface may be used as the parameter type and return type to create a generic function.

389
Q

What ADT is used in operating systems and algorithm design?

A

A queue

390
Q

When is insertion sort generally faster?

A

When n < 25.

391
Q

Reversed Card

They count for no time unit.

A

What time unit do declartions count for?

392
Q

Reversed Card

null checks

A

When compound logical statements are used in linked list traversals, what should always be done first?

393
Q

Reversed Card

A new red node with null links.

A

All insertions in a red black tree create a new what?

394
Q

Reversed Card

when each inner class object is associated with exactly one instance of an outer class object.

A

When is using an inner class useful?

395
Q

Reversed Card

2h+1-1

A

A perfect binary tree has how many nodes?

396
Q

Reversed Card

double rotate with right

A

What function is called when Insertion took place in the left subtree of the right child?

397
Q

When can insertion and deletion in a skip list take O(N)?

A

When the division into regions of size equal to powers of two is maintained.

398
Q

Reversed Card

The iterable interface

A

What interface does the Collections interface extend?

399
Q

Reversed Card

Public static int maxsubsum(int[] a)

Int max sum = 0, this sum =0;

For (int I =0, I < a.length, i++)

Thissum += a[i];

If(thissum > maxsum ) maxsum = thissum;

Else if (thissum < 0) thissum = 0;

Return maxsum;

A

What is the linear time algorithm for the positive max subsequence problem?

400
Q

Where is the parameter type used in a class definition?

A

Anywhere in the class where the type of an object can be anything.

401
Q

Reversed Card

S(h) = S(h-1) + S(h-2) + 1

A

The minimum number of nodes in an AVL tree of height h is given by what recurrence relation?

402
Q

What extra variable and operations are used in a queue?

A

A tail node, insert at tail, remove at head

403
Q

When creating a generic method, where do the angle brackets go?

A

Before the return type.

404
Q

In a path name, each slash indicates what?

A

An edge from one directory node to the other.

405
Q

Reversed Card

  1. An insertion into the left subtree of the left child of unbalanced node.
  2. An insertion in to the right subtree of the left child of unbalanced node.
  3. An insertion into the left subtree of the right child of unbalanced node.
  4. An insertion into the right subtree of the right child of the unbalanced node.
A

What are the four cases that may cause a balance violation?

406
Q

What function is called when Insertion took place in the right subtree of the left child?

A

double rotate with left.

407
Q

Reversed Card

2Xn

A

Xn + Xn = ?

408
Q
A
409
Q

What two kind of rotations is a double rotation?

A
  1. a rotate with right, followed by a rotate with left

or

  1. a rotate with left, followed by a rotate with right.
410
Q

Reversed Card

  1. Deleting a leaf Node.
  2. Deleting a node with one child.
  3. Deleting a node with two children.
A

What are the three cases which the delete algorithm must address?

411
Q

What is an inside insertion?

A

an insertion into the right subtree of the left child, or the left subtree of the right child.

412
Q

Reversed Card

After the class name, before the object reference.

A

When instantiating a generic class, where do the angle brackets go?

413
Q

Reversed Card

(Anytype []) new Object[];

A

How is a generic array created?

414
Q

Reversed Card

Stores a current position starting at the beginning.
HasNext();
Next();
Remove();

A

What is the basic implementation of an iterator?

415
Q

Reversed Card

stores identically typed objects

A

What does a collection do?

416
Q

Let x be the out of balance node, and k be the key that was inserted what is the case that x.value < k < x.rightChild.value?

A

this is the case that insertion took place in the left subtree of the right child.

417
Q

What is a rooted Binary tree?

A

A tree with a root node in which every node has at most two children.

418
Q

Reversed Card

O(logN)

A

What is the average running time of most operations in a binary search tree?

419
Q

What is a geometric recurrence?

A

one in which the numbers are in the sequence are a product of the previous number and some k.

420
Q

What is the basic implementation of an iterator?

A

Stores a current position starting at the beginning.
HasNext();
Next();
Remove();

421
Q

What are the minimal two classes needed to implement a linked list?

A

LinkedList
Node

422
Q
A
423
Q

Reversed Card

O(1), it is constant.

A

What is the runtime of adding an removing from a linked list?

424
Q

A tree that is not binary may have how many children?

A

An arbitrary number, possibly zero.

425
Q

Reversed Card

The point in the list after the previous node.

A

Where is the insertion point in a probabilistic skip list?

426
Q

In computer science, all logarithms are to what base?

A

Base 2

427
Q

What is the runtime of fast exponentiation?

A

O(logn), which is given by the number of multiplications computed.

428
Q

Reversed Card

N divides A - B, this intuitively means that the remainder is the same when N divides either A or B.

A

We say that A is congruent to B modulo N, if

429
Q

When instantiating a generic class, where do the angle brackets go?

A

After the class name, before the object reference.

430
Q

Besides a list of its children, what else does a Unix directory have?

A

A reference that points to itself, and another entry that points to the parent of the directory.

431
Q

Reversed Card

if(head ==null) throw error
Object result = head.value;
head = head.next;
return result;

A

What is the removeFromHead algorithm?

432
Q

Reversed Card

A list in which every node maintains a link to its previous and next node.

A

What is a doubly linked list?

433
Q

When instantiating a class, what goes inside of the angle brackets?

A

The type of object that will replace the parameter type.

434
Q

Reversed Card

A search proceeds along the list with the greatest span until two references are found that enclose the required key. Then the search proceeds at the next level down until the required key found, or is deemed to be not present.

A

How does a skip list search work?

435
Q

What is the contains algorithm?

A
  • Contains(x, BinaryNode t)
    • if(t == null) return false;
    • if(x.compareTo(t.Object) < 0) return contains(x, t.left);
    • if(x.compareTo(t.Object) > 0) return containts(x, t.right);
    • else return true;
436
Q
A
437
Q

Reversed Card

by repeatedly taking the GCDs of pairs of numbers: gcd(gcd(a, b), c)

A

How can Euclids algorithm be used for finding the GCD of 3 or more positive numbers?

438
Q

When and for what are wildcards used?

A

When using a generic Collections, a wild card goes inside of the angle brackets after Collection along with the extends keyword to allow a class and any of its subclasses to be used in the collection.

439
Q

What kind of traversal is used to convert an expression tree into a postfix expression?

A

A postorder traversal.

440
Q

Reversed Card

It returns true if a node in tree T has item x, or false if not.

A

What does the contains function do?

441
Q

Reversed Card

It’s left child’s right subtree.

A

A rotate with left child causes the Node X to become what?

442
Q

The addAtHead function has only one line of code. What is it?

A

head = new Node(object, head);

443
Q

What is the average depth of a binary search tree?

A

O(log N)

444
Q

Reversed Card

Before the return type.

A

When creating a generic method, where do the angle brackets go?

445
Q

Reversed Card

  1. a rotate with right, followed by a rotate with left

or

  1. a rotate with left, followed by a rotate with right.
A

What two kind of rotations is a double rotation?

446
Q

What are the variables of a BinaryNode?

A

Object, left child, right child.

447
Q

Reversed Card

Because deltion will always faovr making one sides subtree shorter, therefore making all insertion sequences no longer equally likely.

A

Why does deletion cause the average runtime of O(log N) to not always hold?

448
Q

Reversed Card

A preorder traversal.

A

What kind of traversal is used to convert an expression tree into a prefix expression?

449
Q

Reversed Card

null.

A

What should the last node in a linked list always point to?

450
Q

Reversed Card

It ensures that the depth of a tree is O(log N)

A

What does an AVL tree ensure?

451
Q
A

When we are speaking of trees, N always represents what?

452
Q

Reversed Card

making multiple assignments in one line right to left.

A

What is one way to shorten code for assignments?

453
Q

Reversed Card

The path from the root to the farthest null-link is no more than twice as long as the path from the root to the nearest null link.

A

What is the fundamental Red-Black Tree Property?

454
Q

Reversed Card

The enhanced for loop.

A

Classes that extend the iterable interface can implement what?

455
Q

What is the fundamental Red-Black Tree Property?

A

The path from the root to the farthest null-link is no more than twice as long as the path from the root to the nearest null link.

456
Q

How can tail recursion be eliminated?

A

By enclosing the body in a while loop and replacing the recursive call with one assignment per method argument.

457
Q

What is the IsEmpty algorithm?

A

return root == null;

458
Q

What is a stack frame, or activation record?

A

The information saved on a stack when a method is called and the registers must be cleared.

459
Q

What kind of traversal is used to convert an expression tree into a prefix expression?

A

A preorder traversal.

460
Q

Reversed Card

Compiler features that allow primitive types to be passed as wrapper classes and vice versa.

A

What is autoboxing/ unboxing?

461
Q

Reversed Card

2log2(n+1)

A

Every red black tree with N nodes has a height less than or equal to what?

462
Q

Reversed Card

To allow the nested class to use the members of the outer class.

A

Why must we use the static keyword when nesting a class inside of a class?

463
Q

Reversed Card

A pop or peek on an empty list.

A

What is generally considered an error in the stack adt?

464
Q

What are function objects?

A

Classes built with no data and one single method.

465
Q

Reversed Card

A file with a list of all its children.

A

What is a directory in the UNIX File System?

466
Q

Reversed Card

O(n2), different from its average case.

A

What is the time complexity of Quick sort?

467
Q

Reversed Card

An interface may be used as the parameter type and return type to create a generic function.

A

What else may be used besides the Object class for genericity, and how?

468
Q

Reversed Card

  • Every node is either red or black.
  • The root of the tree is black.
  • A red node must have no children or exactly two black children.
  • Every path from a node x to a descendent null-link must have the same number of black nodes.
A

What are the four fundamental properties of Red-Black Trees?

469
Q

Reversed Card

a clearly specified set of simple instructions to be followed to solve a problem.

A

What is an algorithm?

470
Q

When compound logical statements are used in linked list traversals, what should always be done first?

A

null checks

471
Q

Reversed Card

When every node that is inserted is larger or smaller than the one before, ie, they are inserted in order.

A

When does the worst case depth happen in a binary search tree?

472
Q

What is a binary tree?

A

A tree in which no node can have more than two children.

473
Q

At worst case, a binary tree can have a depth of what?

A

N-1

474
Q

What is the binary tree insertion algorithm?

A
  • BinaryNode Insert(x, BinaryNode t)
    • if(t==null) return new BinaryNode(x, null, null);
    • int compare = x.compareTo(t.element);
    • if(compare < 0) t.left = insert(x, t.left)
    • else if(compare > 0 ) t.right = insert(x, t.right);
    • else do nothing;
    • return t;
475
Q

What are the three steps to creating an expression tree from a postfix expression?

A
  1. We read our expression one symbol at a time. If the symbol is an operand, we create a one node tree and push it to a stack of trees.
  2. If the symbol is an operator, we pop two trees from the stack and form a new tree whose root is the operator.
  3. The new tree is then pushed onto the stack, and the process continues until it is complete.
476
Q

Reversed Card

2 constructors, right child, left child, object, height.

A

What is the AVL node implemenation?

477
Q

What is the performance time of a degenerate tree?

A

The same as that of a linked list. O(n)

478
Q

2n + 2n = ?

A

2n+1

479
Q

What is tail recursion?

A

A recursive call at the last line of a method, and an example of bad recursion.

480
Q

What is a complete binary tree?

A

A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

481
Q

What is the first step to doing an insertion or deletion in a probabilistic skip list?

A

Finding the insertion point.

482
Q

A Red-Black tree where all nodes are black is what?

A

A perfect Binary tree.

483
Q

Reversed Card

A red node can never have a red child, or just one child.

A

What can a red node never have?

484
Q

When does the worst case depth happen in a binary search tree?

A

When every node that is inserted is larger or smaller than the one before, ie, they are inserted in order.

485
Q

What is the time complexity of Quick sort?

A

O(n2), different from its average case.

486
Q

Reversed Card

  1. We read our expression one symbol at a time. If the symbol is an operand, we create a one node tree and push it to a stack of trees.
  2. If the symbol is an operator, we pop two trees from the stack and form a new tree whose root is the operator.
  3. The new tree is then pushed onto the stack, and the process continues until it is complete.
A

What are the three steps to creating an expression tree from a postfix expression?

487
Q

Reversed Card

Ordered Linked Lists

A

What are skip lists made of?

488
Q

A perfect binary tree has how many nodes?

A

2h-1

489
Q

Reversed Card

Operands are pushed onto a stack until an operator is encountered.
Two operands are then popped and the operator is applied to them and saved in a result variable.
The result is pushed back onto the stack, and this is continued until the end of the expression.

A

What is the algorithm for evaluating a postfix expression?

490
Q

Reversed Card

It is the value for which the function is known without having to resort to recursion.

A

What is the base case of a recursive function?

491
Q

Reversed Card

(Logc B)

(Logc A)

A

LogA B = ?

492
Q

Reversed Card

One time unit.

A

What is the time unit of a simple operation or assignment?

493
Q

What is the average depth over all nodes in a binary search tree assuming that all insertion sequences are equally likely?

A

O(log N) assuming all insertion sequences are equally likely.

494
Q

Reversed Card

At construction

A

When is the maximum level of a probabilistic skip list chosen?

495
Q

If a prime number N divides a product of two numbers, then

A

it divides at least one of the two numbers.

496
Q
A
497
Q

What are the four cases that may cause a balance violation?

A
  1. An insertion into the left subtree of the left child of unbalanced node.
  2. An insertion in to the right subtree of the left child of unbalanced node.
  3. An insertion into the left subtree of the right child of unbalanced node.
  4. An insertion into the right subtree of the right child of the unbalanced node.
498
Q

Reversed Card

when it takes constant time to cut the problem size by a fraction, usually 1/2.

A

When is an algorithm O(logn)?

499
Q

What is an algorithm?

A

a clearly specified set of simple instructions to be followed to solve a problem.

500
Q

What is the double rotate with right child algorithm?

A
  • DoubleRotateWRight(node x)
    • x.right = rotateWLeft(x.right);
    • Return rotateWRight(x);
501
Q

What is the removeFromHead algorithm?

A

if(head ==null) throw error
Object result = head.value;
head = head.next;
return result;

502
Q
A
503
Q

Reversed Card

The length of the unique path from the root to it.

A

What is the depth of a node?

504
Q

What function is called when Insertion took place in the left subtree of the right child?

A

double rotate with right

505
Q

An expression that is in standard form is said to be____

A

infix.

506
Q

How can a generic object of Object type be accessed and used properly?

A

By downcasting the object to the proper type.

507
Q

What is the depth of the root?

A

depth = 0.

508
Q

Reversed Card

this is the case that insertion took place in the left subtree of x’s left child.

A

Let x be the out of balance node, and k be the key that was inserted what is the case that K < x.leftChild.Value?

509
Q

What are some popular but not required linked list operations?

A

printList, makeEmpty

510
Q

Reversed Card

.25

A

What is the suggested probabilistic variable value for a probabilistic skip list?

511
Q

What is the depth of a node?

A

The length of the unique path from the root to it.

512
Q

What is type erasure?

A

the process performed by the compiler that turns generic classes into non-generic classes.

513
Q

How is a node with one child deleted?

A

The parent node sets its child node to its grandchild.

514
Q

What are function objects used for?

A

To pass functions as parameters.

515
Q

What is meant by an outside insertion?

A

An insertion took place in the right subtree of teh rigth child, or the left subtree of the left child.

516
Q

Reversed Card

It does nothing.

A

What does the delete function do if a value is not found?

517
Q

What is one way to handle a tree that will have duplicates inserted?

A

Keep a record of frequency in each node and update it when a duplicate is added or removed.

518
Q

What are three examples of simple sorting algorithms?

A

Selection sort, bubble sort, insertion sort.

519
Q

Reversed Card

When nodes have a deleted marker that is turned on when they are deleted.

A

What is lazy deletion?

520
Q

Reversed Card

A doubly linked list.

A

What kind of list is required for a sufficient implementation of a deque?

521
Q

What is the algorithm for evaluating a postfix expression?

A

Operands are pushed onto a stack until an operator is encountered.
Two operands are then popped and the operator is applied to them and saved in a result variable.
The result is pushed back onto the stack, and this is continued until the end of the expression.

522
Q

Reversed Card

an insertion into the right subtree of the left child, or the left subtree of the right child.

A

What is an inside insertion?

523
Q

What is a degenerate tree?

A

a tree where, for each parent node, there is only one associated child node.

524
Q

What is the AVL node implemenation?

A

2 constructors, right child, left child, object, height.

CS 3345 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions