Brainscape's Knowledge GenomeTM

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


See full index

DSA > Data Structures Overview Terms & Concepts > Flashcards

Data Structures Overview Terms & Concepts Flashcards

1
Q

array

A

primitive data structure
collection of items
stored sequentially

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

array insertion

A

new value placed in arbitrary position

all following elements move over one position to make room

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

array index

A

access any item

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

abstract data type (ADT)

A

a scheme for organizing data that is independent of how it is stored in the computer
defined by a name and list of operations that can be performed on it

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

List ADT operation: Size

A

get the number of items in the list

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

List ADT operation: Get

A

get the value at a specific location

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

List ADT operation: Find

A

find the location of a matching element

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

List ADT operation: insert

A

put a new value into the list at a specific location

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

List ADT operation: remove

A

take a value out of the list at a specific location

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

List ADT operation: Set

A

replace one item with another

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

big-O notation

A

tool for measuring operation execution speed
dependent on data type and implementation
“order of”

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

Efficiency of List ADT Size operation implemented with an array

A

O(1)

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

Efficiency of List ADT Get operation implemented with an array

A

O(1)

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

Efficiency of List ADT Find operation implemented with an array

A

O(n)

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

Efficiency of List ADT Set operation implemented with an array

A

O(n)

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

Efficiency of List ADT insert operation implemented with an array

A

O(n)

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

Efficiency of List ADT Add at end operation implemented with an array

A

O(1)

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

Efficiency of List ADT Remove operation implemented with an array

A

O(n)

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

Efficiency of List ADT Sort operation implemented with an array

A

O(n log n)

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

Efficiency of Ordered List ADT Size operation implemented with an array

A

usually O(1)

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

Efficiency of Ordered List ADT Get operation implemented with an array

A

O(1)

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

Efficiency of Ordered List ADT Find operation implemented with an array

A

O(log n)

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

Efficiency of Ordered List ADT Insert operation implemented with an array

A

O(n)

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

Efficiency of Ordered List ADT Remove operation implemented with an array

A

O(n)

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

Set ADT

A

like a list that doesn’t allow duplicates, but the position of items in the collection is undefined and irrelevant.

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

Set ADT operations

A

Add, In, Intersection, Union

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

Set ADT operation: Add

A

add an item to the set

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

Set ADT operation: In

A

is an item in the set?

29
Q

Set ADT operation: Intersection

A

Return the intersection of two sets

30
Q

Set ADT operation: Union

A

Return the union of two sets

31
Q

grow your program

A

instead of trying to write the whole thing at once, divide the problem into convenient steps.

32
Q

test in isolation

A

get your ADT working separately from the main program by creating new main program from scratch

33
Q

Trace statement

A

track errors
testing operations
commented out

34
Q

toString method

A

always written for ADTs
outputs results
when printing out a reference, toString called automatically, without explicit call

35
Q

boundary testing

A

using a testing method for values at the start and end of a collection

36
Q

intersection operation

A

the set of all elements the two have in common.

37
Q

orthogonal methods

A

two similar methods, working the same way.

38
Q

union operation

A

all the elements found in either of two sets.

39
Q

refactoring

A

improving code quality without affecting results

40
Q

data structure

A

an arrangement of data in a computer’s memory.

41
Q

algorithm

A

manipulates data in data structures

42
Q

iteration in a data structure

A

visiting each item in turn to perform some action on it

43
Q

recursion

A

a method that calls itself

44
Q

fields

A

an object’s variables

45
Q

instantiating an object

A

creating an object

46
Q

instance

A

object of a class

47
Q

constructor

A 
has the same name as the class
called whenever a new object is created
48
Q

access modifiers

A

keywords public and private

determine which methods can access a method or field

49
Q

private

A

a field or method that can only be accessed by methods of the same class

50
Q

public

A

a field or method that can be accessed by methods in other classes

51
Q

inheritance

A 
the creation of one class, called the extended or derived class, from another class called the base class.
the extended class has all the features of the base class, plus some additional features
52
Q

polymorphism

A 
treats objects of different classes the same way.
different class must be derived from same base class
53
Q

garbage collection

A

blocks of memory with no valid references are returned to the free memory store

54
Q

insertion, searching, deletion operations

A

fundamental to most data structures

55
Q

array hole

A

one or more empty cells that have filled cells above them at higher index numbers

56
Q

initialization list

A

single statement creates a new array with size determined by the number of values in the list.

57
Q

container class

A

a class used to store data objects

58
Q

class interface

A

the functions and arguments of class methods

59
Q

abstraction

A

the process of designing a program by first starting with class functionality rather than implementation details

60
Q

ordered array

A

data items arranged by ascending key values, smallest to largest.

61
Q

binary search

A

for ordered arrays
each guess divides the range of possible values in half until the range is only one number long
the correct number is identified in only seven guesses, this is the maximum.

62
Q

logarithm

A

the inverse of raising something to a power.
the logarithm to the base B of a number A is roughly the number of times you can divide A by B before the result is less than 1.

63
Q

bubble sort

A

slow and simple
compare two items, if item closer to beginning of array is larger than item closer to end, then swap them. move to next pair and swap if necessary, continue to end of array and start over and continue until all ascending.

64
Q

invariants

A

conditions in algorithms that remain unchanged as the algorithm proceeds.

65
Q

selection sort

A

pass through all the items and pick the lowest number, swap the least with the first (position 0). start again at position 1, swap least with position 1. process continues until all sorted.

66
Q

insertion sort

A

partially sorted group. remove first item of unsorted items, shift the sorted items to make room for the item at each position and compare each position until item reaches it’s sorted position, then insert. process repeats until all unsorted items are inserted in sorted positions.

67
Q

operation of compareTo( ) method

A

s2.compareTo(s1)
s1 < s2 - return value is < 0
s1 equals s2 - return value is 0
s1 > s2 - return value > 0

68
Q

stable algorithms

A

sort only what needs to be sorted and leave everything else in original order.

69
Q

in place sorting

A

very little extra memory is required

DSA (26 decks)

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