Brainscape's Knowledge GenomeTM

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


See full index

Data Structures > Data Structures 2 > Flashcards

Data Structures 2 Flashcards

1
Q

Explain the binary search algorithm.

A

An iterative algorithm by which a sorted list can be searched. The iteration consists of choosing the midpoint between the first and last item on the list, comparing that item to the item being searched for, and then establishing a new list to be searched once the item is decided to be in front of or behind the midpoint item.

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

What are the three big ideas that we will be learning about in the Data Structures course?

A
  1. Organizing data properly helps build efficient solutions to problems.2. Types of data structures and ideas about them. 3. Abstraction is a key tool.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition: Abstraction

A

The considering of something as a general quality or characteristic instead of a specific instance.

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

What is an ADT?

A

An ADT, or abstract data type, is a description of an object (or set of objects) together with a set of operations that can be performed on the object.

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

What two operations are associated with a basic integer counter ADT?

A

Increment and get value (initialization is implicit in the definition of the ADT).

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

What is a stack and what are its operations?

A

A stack is an ADT that is a type of list. The only part of the list that is accessibly by the user is the top of the list. Its operations include: pop, which deletes top element; top, which returns the top element; and push, which puts a new element on the top of the list.

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

Definition: activation record

A

The record of information saved while a method call is performed in the registers. Its purpose is to make sure there is no overwriting of information that is needed in the calling routine. The paper is put on the top of the stack of other papers of other calling routines that might be open.

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

What does CPU stand for?

A

Central Processing Unit. Or, in other words the processor.

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

What is a primitive type and how is it designated?

A

It is a data type that has a certain amount of memory set aside for it, and it is those memory cells that hold the actual object. Whenever it is then called by the program, the actual entity is looked up. It is designated by a lower case type, e.g. int, double.

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

What is an object type and how is it designated?

A

An object type is a data type that has a pointer in memory that points to where the actual memory that stores the object is located. Whenever the object is referenced, it goes through this pointer first. You can create multiple pointers to one object without constructing any new objects.

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

What does overloading refer to?

A

Overloading a class indicates that there are multiple constructors that are in the class.

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

What are helper methods and how are they designated?

A

Helper methods are methods within a class that are only called by other methods in the class and that aren’t available fore the user to use. They are labeled as private.

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

What is an orphan?

A

It is an object in memory that is no longer reachable by the program because all pointers to it have been deleted or changed to reference another object. Orphans and other extraneous data is periodically and systematically erased by the computer.

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

What is the stack?

A

A special place inside memory that stores temporary variables created in each function. Once the function running exits, any information it stored on the stack is freed (deleted). The computer manages the stack memory for you, and you can access anything on the stack quickly, but there is a size limit to what you put there.

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

What is the heap and what is a risk associated with using it too much?

A

The heap is a larger area in memory that, in C, you manage and organize yourself with the functions malloc(), calloc(), and free() to allocate and deallocate space in the heap. If you fail to deallocate memory when you’re not using it any more, you may get a memory leak, which means some data stored in the heap is set aside and cannot be accessed any longer. However, data in the heap is not deleted when a function is exited.

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

What is an interface and what is a benefit to using one?

A

An interface specifies and lists the variables and methods that a class must implement. A benefit of using interfaces is that they can be used to simulate multiple inheritance.

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

Does the main method always have to be inside a class in Java?

A

Yes.

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

What does the extends keyword do in Java?

A

Extends is used after a subclass declaration to refer to a different superclass that it is inheriting.

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

What does DOS stand for? What is MS-DOS?

A

Disk Operating System. Sometimes used as shorthand for MS-DOS (Microsoft Disk Operating System), which is the standard operating system for IBM PC (IBM Personal Computer).

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

What are the defining properties of a queue ADT?

A

A queue ADT is a line of objects. Objects are pushed in at one end of the queue and popped at the other end. It is a last in, last out data structure.

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

What are the defining properties of a deque ADT?

A

A deque is a data structure that is like a line of objects, like a queue, but that can push and pop objects at both ends of the line.

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

What are the defining properties of a bag ADT?

A

A bag is (usually) a collection of one type of object, and it is unordered and unindexed, and you can access any object in the bag if you know for which instance you are looking.

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

What are two reasons you might want to use an explicit iterator instead of a for each loop?

A

If you want to use the remove method of the iterator interface, or if you don’t want to iterate through all of the elements of the collection.

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

Algorithmic efficiency of selection sort? When does it happen?

A

O(n^2) worst case is when it is backwards sorted and you have to visit every element each time to find the smallest one

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

Algorithmic efficiency of insertion sort? When does it happen?

A

O(n^2) happens when it is already sorted and you have to visit every item in new array to find next element’s place

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

Algorithmic efficiency of bubble sort? When does it happen?

A

O(n^2) worst case is when you have to go through n passes of the algorithm, that is, there is at least one swap every run

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

Algorithmic efficiency of mergesort?

A

O(NlogN) levels of recursion: log N, then how much work to merge each level? have to look at every item in each level: N.

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

Algorithmic efficiency of quicksort?

A

O(N^2) at worst, expected to be O(NlogN)

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

What is one pass of quick sort?

A

Choose median of three pivot (what the median is of the set of the first element, middle element, & last element), swap it with whatever is at the end of the array. Then approach from either end until you find two elements that are out of place with respect to the pivot, swap them. Repeat until you meet in the middle, then put pivot back quicksort the two sets to left and right of original pivot.

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

What are the defining properties of a valid minimum binary heap?

A

Each parent has a smaller priority value than its child, and it is a complete binary tree, which means every level is filled all the way except for possibly the last, which is only filled from left to right.

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

How do you perform an insert in a binary heap PQ?

A

Put it in at the first empty spot in the tree, then bubble it up as far as it needs to go.

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

How do you perform a remove in a binary heap PQ?

A

Take out the root, replace it with the last (lowest priority) item and allow this item to bubble down however far it needs to go.

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

How do you do a bottom-up build on a binary heap PQ?

A

You start with the lowest priority item that has children, and then you bubble it down AS FAR AS IT NEEDS TO GO. You then go to the next lowest priority parent, do the same, until you’ve done every node that is a parent (the last being the root).

34
Q

How to splay trees work?

A

Each time a node is accessed (that is, retrieved/searched for one purpose or another) the node is rotated up via AVL rotations to be closer to the root

35
Q

What is the amortized efficiency of a sequence of M operations in an n-node splay tree?

A

O(MlogN)

36
Q

What’s the best way to implement a union find structure?

A

With an array

37
Q

How would you change a binary heap priority queue to be able to edit the priorities of existing elements in the heap?

A

Basically, you keep a hash table of the elements that are in the binary heap, and when you need to change a priority, you look up its location in the binary heap and then go get it and bubble it as far up or far down as it needs to go, all the way keeping track of the positions of each swapped element in the heap in the hash table.

38
Q

What are the tags that you might use before each segment of code in a J-Unit test?

A

@Before, @Test

39
Q

What do you do under an @Before tag of a JUnit test?

A

You have a public void method that will construct an instance of whatever class you might be testing, and also initialize anything else that might be needed in every test

40
Q

What command will you primarily use in a JUnit test to confirm that the results are as you expect or confirm that they are not?

A

assertEquals(Expected value of object or primitive, Actual value of Object or primitive)

41
Q

What tag do you have before each JUnit test in a JUnit test class?

A

@Test

42
Q

What kind of method contains each test segment?

A

public void

43
Q

How do you write a JUnit test?

A

@Testpublic void test1() {//some codeassertEquals(expected value, actual value)}

44
Q

Why are JUnit tests useful?

A

Because you can run a whole bunch of tests at the same time without having exceptions hold you up at runtime

45
Q

How is a fast finds union find structure implemented? What is the efficiency of a find in this case? A union?

A

As an array, with each position holding the name of that element’s equivalence class. That way a find is constant time, and a union is O(N) time

46
Q

How is a fast unions union find structure implemented? What is the efficiency of a union in this case? A find?

A

An array, with equivalence classes represented as trees, each element containing its parent node in the equivalence class it’s in. The root contains a negative number indicating it’s equivalence class’s size. Find: could be O(N), union: O(1).

47
Q

What is a trie?

A

A tree that has a null root with each node containing a letter of a word, spelled from child of node to bottom of tree.

48
Q

How is Dijstra’s algorithm implemented?

A

You have a Boolean array that indicates whether you’ve visited the node, an int array initialized to positive infinity that keeps track of shortest distance found from root to each node, and another pointer (or int) array that is initialized to some value like 0. You visit the root, update distance values for nodes that are connected to it (that is, distance to current node plus edge connecting current node to that node), and then do it for each node in turn, deciding where to go based on what the CLOSEST UNKNOWN node is.

49
Q

What is Kruskal’s algorithm?

A

An algorithm to find a minimum spanning tree. Consists of looking at the least cost edge of entire graph, deciding if it creates a cycle in the graph, and then adding it to the minimum spanning tree if it doesn’t. Repeat until you can’t add anything more without creating a cycle.

50
Q

What does path compression mean?

A

In a union find structure, each time a find is performed, you return to the root, changing each element’s parent node to the root if it isn’t already.

51
Q

What type of graph implementation is best for sparse graphs?

A

An adjacency list

52
Q

What type of graph implementation is best for dense graphs?

A

An adjacency matrix.

53
Q

How do you perform a remove on an AVL tree?

A

You remove item, find inorder successor, keep finding inorder successor until you find one with at most one child, which you can then replace with nothing or its only child. Then, you go back up to root, checking every balance factor until you get all the way back.

54
Q

How do you perform an insert on an AVL tree?

A

You find where the new item belongs, put it there, and then you return to root, checking balance factors, and if a node is unbalanced on the way there, you perform rotations to balance it, and then you stop, because tree will be balanced after one rotation.

55
Q

How do you perform a topological sort on a graph?

A

Find node with indegree of zero. Add it to topologically sorted list, remove it from the graph. Repeat until no nodes left. Remember, topological orderings are not unique, so you may need to have some other way of comparing which node should come next if there are two options.

56
Q

Algorithmic efficiency of insert/remove/contains/traversal in binary search tree?

A

O(N)

57
Q

Algorithmic efficiency of insert/remove/contains in AVL tree?

A

O(log N) remember rebalancing is constant time, and you will at most have to do it height of tree = log N times.

58
Q

What are the operations on a min PQ?

A

insert(priority, element), min() (equivalent to peek), removeMin()

59
Q

What is a ranked array?

A

level order traversal of a tree stored in an array, with the root at index 1

60
Q

What is the algorithmic efficiency of each of a min PQ’s operations?

A

min: O(1)removeMin: O(log N) (have to bubble down)insert: O(log N) if you don’t have to resize array, O(N) if you do

61
Q

How to implement bottom up build?

A

Start with element at index i = size/2, which is the rightmost nonleaf in second lowest level of heap, repeat while i is greater than one, bubble down value if it is greater than one or more of its children, subtract one from i

62
Q

What is the insertion algorithmic efficiency of a skip list?

A

O(log N)

63
Q

How is a skip list implemented?

A

With a linked list that has every 2^i node having a link to every 2^i node ahead of it.

64
Q

What is the main problem with using a skip list?

A

It is too rigid to allow efficient insertion. You have to replace the restriction that every 2^i node has a link to every 2^i node ahead of it. Say a level k node is a node that has k links. We then make it so that every ith link in a k level node links to the next node with at least i levels.

65
Q

How do you perform a search or insertion in a skip list?

A

Traverse along top level until you find that the NEXT node on that level is either null or larger than the one you’re looking for. Then you go down a level, repeat the process, until you’ve hit level one and the NEXT node is either larger than the one you’re looking for or null. For an insertion, the new node’s level is determined randomly (flip a coin until you get heads because approximately 1/2^i nodes are level i)

66
Q

What is a treap?

A

A tree that is a binary search tree when looking up information, and a binary heap with respect to the random priority value.

67
Q

What’s the algorithmic efficiency of a treap’s operations?

A

O(log N) usually for all operations, but it could be O(N) in worst case

68
Q

How do you insert in treap?

A

Insert like a binary tree at correct leaf spot, then ROTATE up!!!!!!!

69
Q

How do you remove in a treap?

A

ROTATE the node you want to remove down, like a heap, switching it with lower priority value child (if min priority is more urgent), and then, once it becomes a leaf, you can remove it.

70
Q

What is the sum of all degrees in a graph equal to?

A

2*number of edges

71
Q

What is the relationship between the number of edges (M) and the number of vertices (N) in an undirected graph?

A

M <= N(N-1)/2

72
Q

What’s the relationship between the number of edges (M) and the number of vertices (N) in a directed graph?

A

M <= N(N-1)

73
Q

What’s the relationship between the number of edges (M) and the number of vertices (N) in a connected graph?

A

M >= N-1

74
Q

What’s the relationship between the number of edges (M) and the number of vertices (N) in a tree? A forest?

A

M = N-1, M<=N-1

75
Q

What are the small scale operations on a graph?

A

number vertices, edges, adjacent(u, v), neighbors(v), degree(v), incident(v, e), connected(u, v)

76
Q

What are the large scale operations on a graph?

A

Breadth first, depth first traversals, shortest path between two vertices, find spanning tree, connected components, is Connected, isTree, Hamiltonian Tour = visit every vertex exactly once, Eulerian path = visit all edges exactly once, topological sort

77
Q

What’s in the iterator interface?

A

hasNext, Next, remove

78
Q

What’s in the iterable interface?

A

iterator

79
Q

Algorithmic efficiency of an adjacency matrix implementation of a graph for: testing if edge exists, finding successors of a vertex, and finding predecessors of a vertex?

A

O(1), O(N), O(N)

80
Q

Algorithmic efficiency of an adjacency list for: testing if an edge exists, finding successors of a vertex, finding predecessors of a vertex?

A

O(N) (degree of vertex), O(N) (degree of i), O(N+M)

81
Q

Algorithmic efficiency of an edge list for: testing if an edge exists, finding successors of a vertex, and finding predecessors of a vertex?

A

O(M), O(M), O(M)

82
Q

How to test if a graph is acyclic?

A

Find connected portions of each graph (union finds structure for vertices) and for each of the connected portions, look at number of edges and make sure it equals the number of vertices minus 1.

Data Structures (14 decks)

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