Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures & Algorithms > MIDTERM > Flashcards

MIDTERM Flashcards

1
Q

What should the vocabulary of pseudocode be?

A

Problem Domain

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is another word for list?

A

Collection

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What kind of list is an array?

A

Linear List

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Stacks

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What end of a stack do removals happen?

A

Head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What end of a stack do additions happen?

A

Head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is it called when a stack is full?

A

an Overflow State

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What operations does a stack have?

A
  1. Push
  2. Pop
  3. Peek
  4. isFull
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a linked list?

A

A collection of nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does a node consist of?

A

Data and pointer(s)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

One: Pointer to next

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

Link Hopping, or Pointer Hopping

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the first node in a list called?

A

Head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the last node in a list called?

A

Tail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What direction can a singly linked list be traversed?

A

From head to tail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

Pointer to previous

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What end of a queue do additions happen?

A

Tail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What end of a queue do removals happen?

A

Head

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

Queue

20
Q

What operations does a queue have?

A
  1. Clear
  2. Enqueue
  3. Dequeue
  4. Peek
  5. isEmpty
21
Q

How is a priority queue different from a queue?

A

Removals based on priority, not first in first out

22
Q

How must priority be stored for a priority queue?

A

Key Value

23
Q

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

A

insert_with_priority
pull_highest_priority

24
Q

Which algorithm only sorts the array if necessary?

A

Insertion sort

25
Q

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

A

Last pass

26
Q

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

A

Bubble Sort

27
Q

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

A

Selection Sort

28
Q

How is information for a function call stored in memory?

A

Dynamically on the runtime stack

29
Q

What information is saved about a function?

A

Variables, parameter values, and return address

30
Q

What is the function call information called in memory?

A

Activation Record or Stack Frame

31
Q

How long does an activation record exist in memory?

A

As long as the function owning it is executing

32
Q

Which activation record outlives every other one?

A

main()

33
Q

What is the name of the last recursive call?

A

The Anchor

34
Q

What is the purpose of the anchor?

A

Ensures we don’t fall into an infinite loop

35
Q

What are the 3 types of recursion?

A
  1. Linear
  2. Binary
  3. Multiple
36
Q

Which two algorithms use the divide and conquer approach?

A

Merge and QuickSort

37
Q

Which algorithm uses a pivot?

A

QuickSort

38
Q

How many subsets does QuickSort use?

A

3

39
Q

What is the acronym for the subsets of a QuickSort?

A

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

40
Q

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

A

A Parameter

41
Q

What are the two types of templates?

A
  1. Function
  2. Class
42
Q

What is the format for a template function definition?

A

template < typename T > returnType function_name(parameter list)

43
Q

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

A

Specialization or Generated Function or Instantiating a function

44
Q

What is the format for a generic class declaration?

A

template < typename T > class className {}

45
Q

How do you instantiate an instance of a generic class?

A

className< dataType > obj;

Data Structures & Algorithms (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions