5.2 Abstract Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

What is a variable?

A

A memory location to hold a specific size and type of data.

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

What is an array?

A

A declared size of memory space that can store related data.

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

What is important about arrays?

A

They are static - can’t be expanded

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

What are the advantages of arrays?

A

Easier to predict performance
Easier to predict how the program will run
more organised
static - so no unnecessary data stored.

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

What isa multi dimensional array?

A

2 or more data types saved in a certain spot. They have to be the same data type.

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

Code a multi dimension al array?

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

What is a tuple?

A

A special type of array with
An ordered set of values
Of mixed types
That can’t be changed

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

What is important to remember with a tuple?

A

Can’t be changed or expanded.

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

Code a tuple?

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

What are records?

A

A special type of array like tuples but that can be implemented like an object.

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

What are dynamic data structures?

A

Lists or Records that can grow or shrink as requested.

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

Record, Array, Tuple

Which are static?

A

Array and Tuple are static

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

Record, Array, Tuple

Which can grow and shrink?

A

None.

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

Record, Array, Tuple

Which can have multiple data types?

A

Array and Tuple

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

Record, Array, Tuple

Which must have a fixed number of items?

A

All of them.

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

Record, Array, Tuple

Which can have more than one dimension?

A

Array.

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

Record, Array, Tuple

Which can hold an item of the other two structures?

A

Array

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

What are stacks?

A

A stack is an abstract data type that holds an ordered, linear sequence of items. However it is a push pop structure.

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

How is data added to the stack?

A

It is pushed into the top end.

push(item)

20
Q

How is data removed from a stack?

A

It is popped from the top end.

pop(item)

21
Q

What is overflow?

A

Attempting to push onto a stack that is full.

22
Q

What is underflow?

A

Attempting to pop from a stack that is empty.

23
Q

How do you check if a stack is full?

A

isFull()

24
Q

How do you check if a stack is empty?

A

isEmpty()

25
Q

What is peek()?

A

Returns top item from the stack without removing it?

26
Q

How do you check the number of items in the stack?

A

size()

27
Q

What is a queue?

A

A queue is a type of array which is limited to only allow data to be inserted from one end and retrieved from the other. But can be infinitely long.

28
Q

What is another name for a queue?

A

FIFO - first in, first out

29
Q

How is data added to a queue?

A

Data is pushed from the back. This is called enQueue

enQueue(item)

30
Q

How is data removed from a queue?

A

Popped out from the front. This is called deQueue

deQueue()

31
Q

How do you check if the queue is full?

A

isFull()

32
Q

How do you check if a queue is empty?

A

isEmpty()

33
Q

Is a queue static or dynamic?

A

Static - has a set length

34
Q

What is a list?

A

A collection of data that can grow in size.

35
Q

How does a List grow in size?

A

List will create a static array in another part of the memory twice the size of the item and copy that data over. Until it is needed.

36
Q

Why are Lists good?

A

They do not have to be declared.

37
Q

Why are Lists bad?

A

Lists use random access memory
Programs with lots of data will cause programming times to be long.

38
Q

What are Linked lists?

A

A linked list is a linear data structure, in which the elements are linked using pointers.

39
Q

What is the first item in a Linked List called?

A

Head

40
Q

What is the last item in a Linked List called?

A

Null

41
Q

How do you get from the head to the null?

A

You need to traverse to each place.

42
Q

What is an item in a Linked List called?

A

A node

43
Q

How do you delete an item from a linked list?

A

The item would be cleared from the space and become blank.
So the pointed would move over the space to the next item. Leaving the space null.

44
Q

What are Linked Lists useful for?

A

Effective insertion and deletion - it takes a lot less time and complexity than other structures.
And it is simple and can be used to implement a stack, queue, record or tuple.

45
Q

What are the advantages of linked lists?

A

Can implement a variety of ADTs
Dynamic memory allocation - no memory wasted.
Good to represent trees and graphs.
Expanded in a constant time.
Insertion and deletion is efficient.