Brainscape's Knowledge GenomeTM

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


See full index

CS 109 Intro to Java > Data Structures and Algorithms > Flashcards

Data Structures and Algorithms Flashcards

1
Q

A _________________ cannot directly access variables in the outer class. It needs to refer to an ____________ of the outer class.

A

nested static class, instance

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

A _____________ is actually defined WITHIN a method (as opposed to the class). It’s not a class within a class, but a class within a ____________.

A

local class, method

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

In nested classes, the variable in the nested/inner class ______________ the value from the outer class.

A

shadows

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

A nested __________ class cannot directly access variables in the outer class.

A

static

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

The ________ is a chain of connected elements. Each element in the list is called a __________. While the type of connection may vary, the core structure consists of elements that point to each other. The first element in the list is the ______, and the last element is the _______

A

linked list, node, head, tail

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

A _________________ is like a train, with nodes pointing forward.

A

singly linked list

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

A _______________ resembles web browsing history, with nodes pointing forward and backward so that all are connected both ways.

A

doubly linked list

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

A ___________________ is a variation of a singly linked list, and the tail node points back to the head

A

circular linked list

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

Unlike arrays, a _______________ has non-continuous memory, and it requires you to step through each node to find a given node.

A

linked list

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

When compared to an array, why is a linked list less efficient?

A

You need to traverse each node.

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

In this type of linked list, the tail node points to the head node.

A

circular linked

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

In a singly linked list, the tail node points to what?

A

Null

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

How does your browsing history demonstrate a doubly linked list?

A

You can traverse the list forwards and backwards.

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

The reason that the == does not work is because arrays are _________ in Java, and so the compiler is comparing their __________ in memory, NOT the values that you gave them.

A

objects, address

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

You can use == for _______________ like integers, but not objects, such as arrays.

A

primitive variables

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

Are two arrays of the same set of elements equivalent using the comparison operator (==) ?

A

The two arrays are references to 2 different objects in memory hence not equivalent

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

What happens when you compare two objects of the same parent class for equivalency on which one of the objects overrides a parent class method? Are the objects equivalent?

A

The two objects are not equal because the overriding method introduced replaces the initial parent class method

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

A ____________ of an array only creates a copy of an array (or parts of an array) for primitive data types.

A

shallow copy

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

A ______________ creates a copy of an array of objects while still creating new references to objects underneath.

A

deep copy

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

The _____________ method lets you copy part of an array or an entire array.

A

arraycopy

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

A _________ creates a mirror image of the array.

A

clone

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

In Java, a _____ copy would copy only the double data types of an array.

A

shallow

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

Clone the oldRates array and name it rates, double data type.

A

double[] rates = oldRates.clone();

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

If a program needed to create a copy of an array with new references to an object, what type of copy would be performed?

A

Deep copy

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

If you only want to clone a portion of an array in Java, which method do you use?

A

arraycopy

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

Why is cloning multi-dimensional arrays in Java not available using the clone method?

A

A Java multi-dimensional array is an array of objects

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

Contra attack

A

The use of contrapositive and contradiction methods in order to justify a given statement.

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

Induction

A

One of the most important tools for analyzing algorithms. It involves proving mathematical statements true with a finite set of elements.

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

Loop variants

A

Analyzing the correctness of an algorithm consisting of loops with conditions that both hold true immediately before and immediately after every iteration of the

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

This can be defined as the function which determines the amount of time an algorithm takes to give the desired output.

A

Time complexity

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

This function describes the total memory space consumed upon running an algorithm.

A

Space complexity

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

Consumption of space depends on these three things:

A

1: type of data structures
2: the memory allocations completed for the variables used
3: the results stored after execution

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

data structure

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

algorithm

A

a collection of steps to solve a problem

35
Q

Stack data structure

A

last in first out, stores object in a “vertical tower” structure

36
Q

How to initialize a stack in Java?

A

Stack<String> stack = new Stack<String>();</String></String>

37
Q

How to add an element to a stack?

A

stack.push(“ElementOne”);
stack.push(“ElementTwo”);

38
Q

How to remove the top most object from a stack?

A

stack.pop();

39
Q

What does the peek method do with a stack?

A

Looks for the object at the top of the stack without removing it.

stack.peek();

40
Q

Queue data structure

A

First in First Out (FIFO), similar to waiting in line to checkout at a store

a collection designed for holding elements prior to processing

41
Q

Enqueue

A

adding an element to the tail of a queue
offer();

42
Q

Dequeue

A

removing an element from the head of the queue
poll();

43
Q

Priority queue data structure

A

A FIFO data structure that serves elements with highest priorities first before elements with lower priority.

Queue<String> queue = new PriorityQueue<>();</String>

44
Q

Linked lists data structure

A

stores Nodes in 2 parts (data+address), node are in non consecutive memory locations, elements are linked using pointers.

easy to insert and remove elements in this data structure with constant time complexity O(1), non-contiguous nodes, unlike array lists when inserting a new element there is no shifting of contiguous elements.

Bad at searching because there is no index. Must do a linear search which is timely in large data sets. O(n)

singly linked lists can on be traversed UNIDIRECTIONALLY

doubly linked lists can be traversed BIDIRECTIONALLY

LinkedList<String> linkedlist = new LinkedList<String>();</String></String>

45
Q

ArrayList vs. LinkedList

A

ArrayList is much faster to retrieve an element compared to LinkedList.

Doubly LinkedLists are fastest at the beginning and end of the list, but slowest in the middle. But still slower than

46
Q

Linear time

A

O(n)

looping through elements in an array

searching through a linked list

47
Q

Constant time

A

O(1)

random access of an element within an array

inserting at the beginning of a linked list

48
Q

Logarithmic time

A

O(log n)

binary search

49
Q

Quasi linear time

A

O(n log n)
quicksort
mergesort
heapsort

50
Q

quadratic time

A

O(n^2)
insertion sort
selection sort
bubblesort

slow with large data set

51
Q

O(n!)

A

factorial time
extremely slow

52
Q

Linear search

A

iterate through a collection one element of a time

linear time complexity

slow for large data sets,
fast for small data sets

DOES NOT NEED TO BE SORTED

53
Q

Binary search

A

Search algorithm that finds the position of a target value within a sorted array. Half of the array is eliminated during each “step”.

DATA NEEDS TO BE SORTED

most efficient with large data sets

54
Q

BubbleSort

A

A sorting algorithm that compares adjacent elements and goes along the length of the array.

not very efficient.

O(n^2) time complexity

55
Q

SelectionSort

A

search through an array and keep track of the minimum value during each iteration. At the end of each iteration, we swap variables.

O(n^2) time complexity.

56
Q

InsertionSort

A

after comparing elements to the left shift elements to the right to make room to insert a value.

O(n^2) quadratic time complexity

less steps than bubble sort,

best case is O(n) better than selectionSort O(n^2)

57
Q

Recursion

A

Apply the result of a procedure to a procedure.

A recursive method calls itself.

58
Q

Insertion Sort explanation:

A

Two loops should be made: one that starts looping through the array, the other loops again, but goes backward (decrements) down. Each nested loop ensures the next element is greater than the current.

59
Q

What is the advantage of selection sort?

A

it requires no additional memory for operation

60
Q

For a given array of [32, 44, 12, 15], the number of iterations performed using selection sort algorithm are:

A

The number of iterations performed in case of selection sort is (n - 1) where n is the length of the array. Since this is 4 element array, the number of iterations will be 3.

61
Q

What type of structure uses data stored inside a tree node?

A

key-value

62
Q

An important use of heap data structure is _____.

A

Priority queue

Since heaps are very useful in the data structures that require an element to be removed with highest or lowest priority, one of its major application areas is designing priority queues.

63
Q

Which of the following Java statements best depicts the instantiation of the first element within a stack?

A

private Node top;

We use a class (usually called Node) to represent an element in our linked list. Since the head of the list is the one we can use in a stack, we can name it top.

64
Q

Steps in Dijkstra’s algorithm:

A

start at the ending vertex and mark it with a 0 and label it as your current vertex by putting a circle around it.

identify all of the vertices that are connected by an edge to your current vertex, and calculate their distance to the ending vertex by adding their current mark to the weight of the connecting edge

once you’ve marked all of the vertices that are connected by an edge to your current vertex, label the current vertex as visited and put an X through it

65
Q

Graphs come under which category of data structures?

A

Non-linear

Graphs come under the category of non-linear data structures, as the data elements are organized non-sequentially and multiple data elements can be reached from a single data element.

66
Q

A while loop can evaluate ________ conditions.

A

one or more

67
Q

Which interface requires the compareTo method to be overridden

A

Comparable

68
Q

Regular queues use the _________ while priority queues remove elements based on _________

A

FIFO, priority

69
Q

What is a bad character rule?

A

The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character

70
Q

What are similarities between recursion and iteration?

A

they both return the same end result

71
Q

Which package does the List interface belong to?

A

java.util

72
Q

How many forms of the add method can be used with lists?

A

TWO, the add method can be used with and without passing an index value

73
Q

B-tree feature to optimize speed is ____?

A

the use of indexing

74
Q

An abstract class cannot ________

A

be instantiated

You cannot create an instance of an abstract class/instantiate one. It is better used for hierarchies: Think of it as a model. You could have a Vehicle class that is abstract, with Truck, SUV, or Semi as classes under it.

75
Q

What is the operation called that is performed by selection sort to move numbers from the unsorted section to the sorted section of an array?

A

Swapping

76
Q

The back/forward functionality is best served by a ________________. You can’t go past the last step, nor can you proceed before the first. However, you can go back and forth within the quest itself.

A

doubly linked list

77
Q

A sort map is _______?

A

a searchable collection of elements

78
Q

Which of the following sets are implemented classes of the List interface?

A

There are 10 implemented classes, including ArrayList, LinkedList, Stack, and Vector.

79
Q

Consider a situation where the minimum number of swap operation is required. Which sorting algorithm is best for this use-case?

A

selection sort

Selection sort requires fewer swap operations as compared to other sorting algorithms.

80
Q

What is the main characteristic of binary trees?

A

each parent only has two children

81
Q

In loop variants, the relationship between the variables __________.

A

is the same before and after the loops.

82
Q

Out of a random bunch of last year’s holiday greeting cards, Clara wants to find the one her mother sent her. The optimal algorithm to use will be _____.

A

Linear

83
Q
A

CS 109 Intro to Java (6 decks)

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