5.2 Abstract Data Structures

Question 1

What is a variable?

Answer 1

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

Question 2

What is an array?

Answer 2

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

Question 3

What is important about arrays?

Answer 3

They are static - can’t be expanded

Question 4

What are the advantages of arrays?

Answer 4

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

Question 5

What isa multi dimensional array?

Answer 5

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

Question 6

Code a multi dimension al array?

Answer 6

Question 7

What is a tuple?

Answer 7

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

Question 8

What is important to remember with a tuple?

Answer 8

Can’t be changed or expanded.

Question 9

Code a tuple?

Answer 9

Question 10

What are records?

Answer 10

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

Question 11

What are dynamic data structures?

Answer 11

Lists or Records that can grow or shrink as requested.

Question 12

Record, Array, Tuple

Which are static?

Answer 12

Array and Tuple are static

Question 13

Record, Array, Tuple

Which can grow and shrink?

Answer 13

None.

Question 14

Record, Array, Tuple

Which can have multiple data types?

Answer 14

Array and Tuple

Question 15

Record, Array, Tuple

Which must have a fixed number of items?

Answer 15

All of them.

Question 16

Record, Array, Tuple

Which can have more than one dimension?

Answer 16

Array.

Question 17

Record, Array, Tuple

Which can hold an item of the other two structures?

Answer 17

Array

Question 18

What are stacks?

Answer 18

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

Question 19

How is data added to the stack?

Answer 19

It is pushed into the top end.

push(item)

Question 20

How is data removed from a stack?

Answer 20

It is popped from the top end.

pop(item)

Question 21

What is overflow?

Answer 21

Attempting to push onto a stack that is full.

Question 22

What is underflow?

Answer 22

Attempting to pop from a stack that is empty.

Question 23

How do you check if a stack is full?

Answer 23

isFull()

Question 24

How do you check if a stack is empty?

Answer 24

isEmpty()

Question 25

What is peek()?

Answer 25

Returns top item from the stack without removing it?

Question 26

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

Answer 26

size()

Question 27

What is a queue?

Answer 27

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.

Question 28

What is another name for a queue?

Answer 28

FIFO - first in, first out

Question 29

How is data added to a queue?

Answer 29

Data is pushed from the back. This is called enQueue enQueue(item)

Question 30

How is data removed from a queue?

Answer 30

Popped out from the front. This is called deQueue deQueue()

Question 31

How do you check if the queue is full?

Answer 31

isFull()

Question 32

How do you check if a queue is empty?

Answer 32

isEmpty()

Question 33

Is a queue static or dynamic?

Answer 33

Static - has a set length

Question 34

What is a list?

Answer 34

A collection of data that can grow in size.

Question 35

How does a List grow in size?

Answer 35

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.

Question 36

Why are Lists good?

Answer 36

They do not have to be declared.

Question 37

Why are Lists bad?

Answer 37

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

Question 38

What are Linked lists?

Answer 38

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

Question 39

What is the first item in a Linked List called?

Answer 39

Head

Question 40

What is the last item in a Linked List called?

Answer 40

Null

Question 41

How do you get from the head to the null?

Answer 41

You need to traverse to each place.

Question 42

What is an item in a Linked List called?

Answer 42

A node

Question 43

How do you delete an item from a linked list?

Answer 43

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.

Question 44

What are Linked Lists useful for?

Answer 44

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.

Question 45

What are the advantages of linked lists?

Answer 45

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.