MIDTERM

Question 1

What should the vocabulary of pseudocode be?

Answer 1

Problem Domain

Question 2

What is another word for list?

Answer 2

Collection

Question 3

What kind of list is an array?

Answer 3

Linear List

Question 4

What kind of data structure is Last In, First Out?

Answer 4

Stacks

Question 5

What end of a stack do removals happen?

Answer 5

Head

Question 6

What end of a stack do additions happen?

Answer 6

Head

Question 7

What is it called when a stack is full?

Answer 7

an Overflow State

Question 8

What operations does a stack have?

Answer 8

1. Push
2. Pop
3. Peek
4. isFull

Question 9

What is a linked list?

Answer 9

A collection of nodes

Question 10

What does a node consist of?

Answer 10

Data and pointer(s)

Question 11

How many pointers are held in a node for a stack?

Answer 11

One: Pointer to next

Question 12

What is it called when moving from one node to another by following a next reference?

Answer 12

Link Hopping, or Pointer Hopping

Question 13

What is the first node in a list called?

Answer 13

Head

Question 14

What is the last node in a list called?

Answer 14

Tail

Question 15

What direction can a singly linked list be traversed?

Answer 15

From head to tail

Question 16

What is the difference between a singly linked list and a doubly linked list?

Answer 16

Pointer to previous

Question 17

What end of a queue do additions happen?

Answer 17

Tail

Question 18

What end of a queue do removals happen?

Answer 18

Head

Question 19

What kind of data structure is First in, First out?

Answer 19

Queue

Question 20

What operations does a queue have?

Answer 20

1. Clear
2. Enqueue
3. Dequeue
4. Peek
5. isEmpty

Question 21

How is a priority queue different from a queue?

Answer 21

Removals based on priority, not first in first out

Question 22

How must priority be stored for a priority queue?

Answer 22

Key Value

Question 23

What are some operations that are different for a priority queue?

Answer 23

insert_with_priority
pull_highest_priority

Question 24

Which algorithm only sorts the array if necessary?

Answer 24

Insertion sort

Question 25

On which pass will an insertion sort algorithm consider the whole array?

Answer 25

Last pass

Question 26

Which algorithm places the largest element in it's position after the first pass?

Answer 26

Bubble Sort

Question 27

Which algorithm finds the smallest element and places it in it's final position on each pass?

Answer 27

Selection Sort

Question 28

How is information for a function call stored in memory?

Answer 28

Dynamically on the runtime stack

Question 29

What information is saved about a function?

Answer 29

Variables, parameter values, and return address

Question 30

What is the function call information called in memory?

Answer 30

Activation Record or Stack Frame

Question 31

How long does an activation record exist in memory?

Answer 31

As long as the function owning it is executing

Question 32

Which activation record outlives every other one?

Answer 32

main()

Question 33

What is the name of the last recursive call?

Answer 33

The Anchor

Question 34

What is the purpose of the anchor?

Answer 34

Ensures we don't fall into an infinite loop

Question 35

What are the 3 types of recursion?

Answer 35

1. Linear 2. Binary 3. Multiple

Question 36

Which two algorithms use the divide and conquer approach?

Answer 36

Merge and QuickSort

Question 37

Which algorithm uses a pivot?

Answer 37

QuickSort

Question 38

How many subsets does QuickSort use?

Answer 38

3

Question 39

What is the acronym for the subsets of a QuickSort?

Answer 39

L.E.G. Less than Equal to Greater than

Question 40

How is the type of data specified for a generic function or class?

Answer 40

A Parameter

Question 41

What are the two types of templates?

Answer 41

1. Function 2. Class

Question 42

What is the format for a template function definition?

Answer 42

template < typename T > returnType function_name(parameter list)

Question 43

What is it called when the compiler creates a specific version of a generic function?

Answer 43

Specialization or Generated Function or Instantiating a function

Question 44

What is the format for a generic class declaration?

Answer 44

template < typename T > class className {}

Question 45

How do you instantiate an instance of a generic class?

Answer 45

className< dataType > obj;