Data Structures

Question 1

Primitives

Answer 1

int, float, byte, etc. All built from bits.

Question 2

Basic types used to build software

Answer 2

Primitives

Question 3

Byte

Answer 3

8 bits, 0-255

Question 4

Half a byte

Answer 4

Nybble, Hex

Question 5

Integer types

Answer 5

Short (2B), Int (4B), Long (8B)

Question 6

Short integer

Answer 6

2 bytes

Question 7

int Integer

Answer 7

4 bytes

Question 8

Long integer

Answer 8

8 bytes

Question 9

Hex

Answer 9

Half-byte, 0-f

Question 10

Memory location

Answer 10

Pages on physical memory/RAM (frames), or on disk/ROM

Question 11

Frame

Answer 11

Page in physical memory

Question 12

Page Replacement steps

Answer 12

Find page on disk, find empty/victim frame, write victim frame to disk if dirty, bring new page into memory, update frame table

Question 13

FIFO

Answer 13

First-in-first-out, replace oldest page first

Question 14

LRU

Answer 14

Least-recently-used, replace page that was called on the longest ago

Question 15

Page vs. Frame

Answer 15

Frame is the storage unit/location in memory, page is the stuff being store

Question 16

array indexing directions

Answer 16

row / column

Question 17

Array lookup

Answer 17

Super fast, but modifying the array sucks

Question 18

Linked Lists

Answer 18

Every node references next node. Lookups are slow, but modifying the list is easy.

Question 19

Queue

Answer 19

FIFO, built from arrays or lists

Question 20

Stack

Answer 20

LIFO, built from arrays or lists

Question 21

Queue terminology

Answer 21

Enqueue, dequeue, remove

Question 22

Stack terminology

Answer 22

Push, pop, empty

Question 23

Operational Ceiling

Answer 23

Limit before failure

Question 24

Limit before failure

Answer 24

Operational Ceiling

Question 25

Linear/Serial Search

Answer 25

O(n), starts at one end and moves down the line

Question 26

Binary Search

Answer 26

O(log n), divide at midpoint & repeat, needs ordered list

Question 27

Search starts at one end and moves down the line

Answer 27

Linear/Serial Search

Question 28

Search divides at midpoint & repeat, needs ordered list

Answer 28

Binary Search

Question 29

Hash Function

Answer 29

Maps a key (name) to an integer index of a hash table array / bucket. O(1) ideally, O(n) in practice. Calculates the key based on the data that’s being stored.

Question 30

Collision

Answer 30

Multiple keys mapping to the same index–can be resolved by having the bucket itself being a collection, moving shit to the next open spot (open addressing), or using a perfect hash function instead.

Question 31

Multiple keys mapping to the same index

Answer 31

Collision

Question 32

If collision, slapping data in the next free index of the hash table.

Answer 32

Open Addressing

Question 33

Open Addressing

Answer 33

When mapping new key, if there’s a collision, just go down the indices until you find a free space. When doing a lookup, the hash function will still return the original index, so you just go down the indices until you find what you’re looking for, or find an empty spot.

Question 34

Where shit is stored in hashing

Answer 34

Buckets

Question 35

Bubble Sort

Answer 35

Compare [0] and [1], swap if needed, compare [1] and [2], etc. Then start again, up to len-1, etc. O(n^2)

Question 36

Compare [0] and [1], swap if needed, compare [1] and [2], etc. Then start again, up to len-1, etc. O(n^2)

Answer 36

Bubble Sort

Question 37

Insertion Sort

Answer 37

Make new list, and go down line of original list, placing things into new list in order. O(n^2)

Question 38

Make new list, and go down line of original list, placing things into new list in order. O(n^2)

Answer 38

Insertion Sort

Question 39

Selection Sort

Answer 39

Find min element and move to start, find 2nd to min element and move it into next spot, etc. O(n^2)

Question 40

Find min element and move to start, find 2nd to min element and move it into next spot, etc. O(n^2)

Answer 40

Selection Sort

Question 41

Quicksort

Answer 41

Select pivot, move smaller elements to the left and bigger to the right, then pivot on those two list, etc. O(n log n)

Question 42

Select pivot, move smaller elements to the left and bigger to the right, then pivot on those two list, etc. O(n log n)

Answer 42

Quicksort