4.2 - Fundamentals of data structures

Question 1

What are the 3 features of static data structures?

Answer 1

They reserve memory for a set amount of data - established by the programmer in advance, even though less memory may actually be needed during program execution

They store data in consecutive memory locations

Very efficient in accessing elements directly but inefficient in memory use - memory wasted if array declared with space for 100 but only 10 added

Question 2

What are the 3 features of dynamic data structures?

Answer 2

Memory efficient - memory capacity not fixed and can grow/shrink during run-time; constrained only by the overall memory allocation to the program

Requires memory to store pointers to the next item(s)

Accesses data by memory location rather than by index - often sequential rather than direct

Question 3

What are the 5 features of a queue?

Answer 3

Holds an ordered sequence of items in a First In, First Out (FIFO) structure - first element added is first one removed

New elements added to the end

Remaining elements don’t move up to take up empty space when an element is removed

“Head” pointer maintained at the front to keep queue’s order - indicates the element at the front of the queue

“Tail” pointer indicates the element at the back

Question 4

How is a new item added to a circular queue using the Enqueue method? (3 points)

Answer 4

Expression = (position of tail pointer + 1) MOD max

If the expression equals the position of the head pointer, the item is added to the circular queue

Otherwise, the queue must be full and the item cannot be added.

Question 5

How is a new item added to a static priority queue using the Enqueue method? (4 points)

Answer 5

1. isFull() method is used to check if the queue is full.
2. If the queue is not full, the algorithm parses through the list from the back until an item of an equal or greater priority is found.
3. As it does this, the items which are parsed through are moved back by one position to make space for the new item.
4. When the item of equal or greater priority is found, the new item is added in the position behind it.

Question 6

How is a new item added to a dynamic priority queue using the Enqueue method?

Answer 6

1. isFull() method is used to check if the queue is full.
2. If the queue is not full, the algorithm parses through the list from the first item onward until an item of a lower priority is found.
3. Once the item of a lower priority is found, the address stored in the pointer of the item ahead is stored in a temporary variable and is changed to the address of the new value.
4. The address stored in the pointer of the new item is then changed to the address stored in the temporary variable so that it links to the item of a lower priority.

Question 7

What are the 3 features of a stack?

Answer 7

Holds an ordered, linear sequence of items

Last In, First Out (LIFO) structure - element added last will be first one removed

Only top element can be accessed - pointer must be maintained at the top

Question 8

Define ‘binary tree’.

Answer 8

A rooted tree where every node has at most two child nodes

Question 9

What are the 3 features of a binary search tree?

Answer 9

Nodes of left subtree - values lower than root

Nodes of right subtree - values higher than root

Can be built to speed up searching