C949

Question 1

Array

Answer 1

An ordered list where each item is directly by a positional index. A data structure that stores subitems. Primary search method, Binary.

Question 2

Linked list

Answer 2

Stores ordered list of items in nodes. Each node stores data and has a pointer to the next node. Faster than an array.

Question 3

Hash Table

Answer 3

Stores unordered items by mapping(or hashing) each item to a location in an array(or vector)

Question 4

Chaining

Answer 4

Handles hash table collision by using a list for each bucket. Each list may store multiple items that map to the same bucket.

Question 5

Bucket

Answer 5

Each element in a hash table

Question 6

Hash Key

Answer 6

Value used to map an index

Question 7

Modulo hash function

Answer 7

(num_keys/num_buckets)

Question 8

Hash table searching

Answer 8

Supports fast search, insert and remove. O(1) linear search requires(N).

Question 9

Max-Heap

Answer 9

A binary tree that maintains the property that a node’s key is greater than or equal to the node’s children key. The root is always the max key.

Question 10

Heap Storage

Answer 10

Heaps are stores using Arrays. If represented by a tree the root node is always entry 0. Works with Tree based data structures.

Question 11

Max-Heap Insert

Answer 11

An insert into a max-heap starts by inserting the node in the tree’s last level. Then swapping the node with it’s parent until no violation occurs.

Question 12

Max-heap remove

Answer 12

Always removes the root. Each node is swapped until no violation occurs.

Question 13

Percolating

Answer 13

The upward movement of a node in a heap.

Question 14

Min-Heap

Answer 14

Like a max-heap, but a node’s key is less than or equal to it’s children’s keys.

Question 15

Heap parent and child indices

Answer 15

Because heaps do not have a node structure nodes are referred to by index. Parent index for a node at index 12: ((12-1) // 2) = 5, child index for a node at index 6: 2* 6 + 2 = 14 **Double # and add 1, double # and add 2.

Question 16

Priority Queues with Heaps

Answer 16

Both functions return the value in the root, but the Pop() function removes the value and the Peek function does not. Pop and Push worst case is 0(logN) and Peek, IsEmpty and GetLength is worst case O(1)

Question 17

Array Based List

Answer 17

A list ADT implemented using an array. Allows for operations such as append, prepend, insert after, remove and search.

Question 18

Linked List vs Array

Answer 18

If a program requires fast insertion a linked list is a better choice.

Question 19

Abstract Data Type(ADT)

Answer 19

A data type described by a predefined user operation. Such as “insert data at rear” without indicating how each operation is implemented.

Question 20

Array in Java

Answer 20

Generic class that supports different data types.

Question 21

Tuple

Answer 21

A container with ordered elements.

Question 22

Stack

Answer 22

An ADT with “Last in first out” rule. Pop and Peek cannot be used in empty list.

Question 23

Stack and Queue in Python

Answer 23

Can be implemented using a class with a single linked list.

Question 24

Queue

Answer 24

An ADT in which items are inserted at the end and removed from the front.(Linked List, Array, Vector)

Question 25

Linked List

Answer 25

A linear data structure that consists of nodes that link to the next node.

Question 26

Double Linked List

Answer 26

A data structure that can also include a reference to the head node. If no variable is assigned returns None or Null.

Question 27

Dequeue

Answer 27

Short for double ended queue. Items can be inserted and removed from the front and back.

Question 28

Bag

Answer 28

An ADT for storing items in which the order does not matter and duplicates items are allowed.

Question 29

Set

Answer 29

ADT for a collection of items. No duplicate items. (BST/Hash Table)

Question 30

Priority Queue

Answer 30

A queue where each item has a priority. Higher are closer to the front.(Heap)

Question 31

Dictionary(Map)

Answer 31

Keys and Value Pairs (BST, Hash Table)

Question 32

Graph

Answer 32

A data structure for representing connections among items. Consists of vertices connected by edges.

Question 33

Vertex

Answer 33

A line item in a graph. Also called nodes.

Question 34

Edge

Answer 34

A connection between two vertices

Question 35

Graph Weight

Answer 35

The graph in which weight is associated with edges

Question 36

Graph Direction

Answer 36

The graph in which all the edges are bidirectional

Question 37

Binary Tree

Answer 37

Each node has up to two children

Question 38

Leaf

Answer 38

A node with no children

Question 39

Internal Node

Answer 39

A node with at least on child

Question 40

Depth

Answer 40

The number of edges away from the root.

Question 41

Height

Answer 41

The largest depth of any node.

Question 42

Preorder traverasal

Answer 42

Root, left, right

Question 43

Bubble sort

Answer 43

Sorting Algorithm that swaps adjacent elements if the second element is less than the first element. Has a runtime of O(N2) N is the number of elements in a list.

Question 44

Bucket sort

Answer 44

Sorting algorithm that individually sorts. Useful when input is uniformly distributed over a range.

Question 45

Merge Sort

Answer 45

Continually splits a list in half. Used with a recursive function

Question 46

Big O complexity

Answer 46

Best to worst: O(1), o(logN), O(n), O(nlogN), O(n^2), O(2^N), O(nl)

Question 47

Radix Sort

Answer 47

10 buckets

Question 48

Interval Search

Answer 48

Divides the data in half until it finds the target. Fastest for sorted data.

Question 49

Record

Answer 49

Data structure for items that are related.

Question 50

Class

Answer 50

A term for a template to create an object.

Question 51

Characteristics of an algorithm

Answer 51

Uses an agnostic code repository.

Question 52

O(1)

Answer 52

Constant time. Always at the top.

Question 53

O(N)

Answer 53

Linear time. Twice as many variables means twice as much time.

Question 54

O(log N)

Answer 54

Logarithmic time. Splits the variables in half with each search. Cutting time.

Question 55

O(N^2)

Answer 55

Quadratic time. Checks every variable against every other variable. Twice as many variables means four times as long.

Question 56

O(N^3)

Answer 56

Exponential. Longest

Question 57

Quicksort

Answer 57

a sorting algorithm that repeatedly partitions the input into low and high parts (each unsorted), and then recursively sorts each of those parts. To partition the input, quicksort chooses a pivot to divide the data into low and high parts. The pivot can be any value within the array, commonly the value of the middle array element. Runtime O(N log N)

Question 58

Selection Sort

Answer 58

Selection sort is a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part. Runtime O(N^2)

Question 59

Insertion Sort

Answer 59

a sorting algorithm that treats the input as two parts, sorted and unsorted, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part. Runtime O(N^2)

Question 60

Merge Sort

Answer 60

Merge sort is a sorting algorithm that divides a list into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted list. The recursive partitioning continues until a list of one element is reached, as a list of one element is already sorted. Runtime O(N log N)

Question 61

Radix Sort

Answer 61

Radix sort is a sorting algorithm designed specifically for integers. The algorithm makes use of a concept called buckets and is a type of bucket sort.

Any array of integer values can be subdivided into buckets by using the integer values’ digits. A bucket is a collection of integer values that all share a particular digit value

Question 62

Bubble Sort

Answer 62

a sorting algorithm that iterates through a list, comparing and swapping adjacent elements if the second element is less than the first element. Runtime O(N^2)

Question 63

Quickselect

Answer 63

an algorithm that selects the
smallest element in a list. Ex: Running quickselect on the list (15, 73, 5, 88, 9) with k = 0, returns the smallest element in the list, or 5.

Question 64

Bucket Sort

Answer 64

a numerical sorting algorithm that distributes numbers into buckets, sorts each bucket with an additional sorting algorithm, and then concatenates buckets together to build the sorted result.