Midterm Review

Question 1

Arrays

Answer 1

Linear lists which use contiguous memory and are usually homogenous.
Operations are limited to its structure.
Can be used to implement different types of lists.

Question 2

List Operations

Answer 2

Insert, Delete, Update, Read

Search, Reorder, Resize, Rules

Question 3

Stacks

Answer 3

Structures that use the LIFO approach. Elements can only be pushed onto or popped from the top of the stack.
Peek operation may give access to top without modifying the stack.

Question 4

Overflow

Answer 4

When a stack is full and does not contain enough space to accept new values.

Question 5

Stack Operations

Answer 5

Push() - add to top
Pop() - remove from top
Peek() - look at top
isFull() - check for overflow

Question 6

Singly Linked List

Answer 6

Can be traversed in one direction (head to tail).

Each node contains a pointer to the next node (null if none).

Question 7

Linked List Operations

Answer 7

addNode() - add new after current

deleteNode() - delete current (none if null)

Question 8

Queue

Answer 8

A list that grows by adding to its tail and shrinks by removing from its head and is a FIFO structure which operates similar to stacks.

Question 9

Queue Operations

Answer 9

Clear - clear queue
Enqueue - add to tail
Dequeue - remove from head
Peek - return first element without removing
isEmpty - check if anything in queue

Question 10

Insertion Sort

Answer 10

Consider first 2 and swap if needed.

For every following element, place in proper position.

Question 11

Bubble Sort

Answer 11

Swap adjacent elements (if wrong order) and reduce inspected elements by 1 for each pass.

Question 12

Selection Sort

Answer 12

Find lowest and place in front. Find next and place next to front, etc.

Question 13

Merge Sort

Answer 13

1. Divide: if input small enough use straightforward method, otherwise divide into subsets
2. Recur: recursively solve subproblems in subsets
3. Conquer: take solutions and merge into full solution

Question 14

Quick Sort

Answer 14

1. Divide: select a specific element to be pivot and store in 3 sequences - less than, equal to, and greater than (LEG)
2. Recur: recursively sort L and G
3. Conquer: order by inserting L then E then G

Question 15

Specialization

Answer 15

A specific version of a templated function AKA generated function

Question 16

Generic Class

Answer 16

A class that defines all the algorithms used by that class; however, the actual type of the data being manipulated will be specified as a parameter when objects of that class are created.