Data Structures Overview Terms & Concepts

Question 1

array

Answer 1

primitive data structure
collection of items
stored sequentially

Question 2

array insertion

Answer 2

new value placed in arbitrary position

all following elements move over one position to make room

Question 3

array index

Answer 3

access any item

Question 4

abstract data type (ADT)

Answer 4

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

Question 5

List ADT operation: Size

Answer 5

get the number of items in the list

Question 6

List ADT operation: Get

Answer 6

get the value at a specific location

Question 7

List ADT operation: Find

Answer 7

find the location of a matching element

Question 8

List ADT operation: insert

Answer 8

put a new value into the list at a specific location

Question 9

List ADT operation: remove

Answer 9

take a value out of the list at a specific location

Question 10

List ADT operation: Set

Answer 10

replace one item with another

Question 11

big-O notation

Answer 11

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

Question 12

Efficiency of List ADT Size operation implemented with an array

Answer 12

O(1)

Question 13

Efficiency of List ADT Get operation implemented with an array

Answer 13

O(1)

Question 14

Efficiency of List ADT Find operation implemented with an array

Answer 14

O(n)

Question 15

Efficiency of List ADT Set operation implemented with an array

Answer 15

O(n)

Question 16

Efficiency of List ADT insert operation implemented with an array

Answer 16

O(n)

Question 17

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

Answer 17

O(1)

Question 18

Efficiency of List ADT Remove operation implemented with an array

Answer 18

O(n)

Question 19

Efficiency of List ADT Sort operation implemented with an array

Answer 19

O(n log n)

Question 20

Efficiency of Ordered List ADT Size operation implemented with an array

Answer 20

usually O(1)

Question 21

Efficiency of Ordered List ADT Get operation implemented with an array

Answer 21

O(1)

Question 22

Efficiency of Ordered List ADT Find operation implemented with an array

Answer 22

O(log n)

Question 23

Efficiency of Ordered List ADT Insert operation implemented with an array

Answer 23

O(n)

Question 24

Efficiency of Ordered List ADT Remove operation implemented with an array

Answer 24

O(n)

Question 25

Set ADT

Answer 25

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

Question 26

Set ADT operations

Answer 26

Add, In, Intersection, Union

Question 27

Set ADT operation: Add

Answer 27

add an item to the set

Question 28

Set ADT operation: In

Answer 28

is an item in the set?

Question 29

Set ADT operation: Intersection

Answer 29

Return the intersection of two sets

Question 30

Set ADT operation: Union

Answer 30

Return the union of two sets

Question 31

grow your program

Answer 31

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

Question 32

test in isolation

Answer 32

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

Question 33

Trace statement

Answer 33

track errors testing operations commented out

Question 34

toString method

Answer 34

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

Question 35

boundary testing

Answer 35

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

Question 36

intersection operation

Answer 36

the set of all elements the two have in common.

Question 37

orthogonal methods

Answer 37

two similar methods, working the same way.

Question 38

union operation

Answer 38

all the elements found in either of two sets.

Question 39

refactoring

Answer 39

improving code quality without affecting results

Question 40

data structure

Answer 40

an arrangement of data in a computer's memory.

Question 41

algorithm

Answer 41

manipulates data in data structures

Question 42

iteration in a data structure

Answer 42

visiting each item in turn to perform some action on it

Question 43

recursion

Answer 43

a method that calls itself

Question 44

fields

Answer 44

an object's variables

Question 45

instantiating an object

Answer 45

creating an object

Question 46

instance

Answer 46

object of a class

Question 47

constructor

Answer 47

``` has the same name as the class called whenever a new object is created ```

Question 48

access modifiers

Answer 48

keywords public and private | determine which methods can access a method or field

Question 49

private

Answer 49

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

Question 50

public

Answer 50

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

Question 51

inheritance

Answer 51

``` 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 ```

Question 52

polymorphism

Answer 52

``` treats objects of different classes the same way. different class must be derived from same base class ```

Question 53

garbage collection

Answer 53

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

Question 54

insertion, searching, deletion operations

Answer 54

fundamental to most data structures

Question 55

array hole

Answer 55

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

Question 56

initialization list

Answer 56

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

Question 57

container class

Answer 57

a class used to store data objects

Question 58

class interface

Answer 58

the functions and arguments of class methods

Question 59

abstraction

Answer 59

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

Question 60

ordered array

Answer 60

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

Question 61

binary search

Answer 61

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.

Question 62

logarithm

Answer 62

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.

Question 63

bubble sort

Answer 63

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.

Question 64

invariants

Answer 64

conditions in algorithms that remain unchanged as the algorithm proceeds.

Question 65

selection sort

Answer 65

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.

Question 66

insertion sort

Answer 66

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.

Question 67

operation of compareTo( ) method

Answer 67

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

Question 68

stable algorithms

Answer 68

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

Question 69

in place sorting

Answer 69

very little extra memory is required