Data Structures Advantages And Disadvantages

Front 1

What is a data structure?

Back 1

A data structure is a way of storing data so that the positions of elements has meaning.

Front 2

What is a static data structure?

Back 2

A static data structure is one which does not change in size when the program is running.

Front 3

Example of a static data structure?

Back 3

Array

Front 4

What is a dynamic data structure?

Back 4

The structures increase and decrease in size whilst the program is running, when data is added the structure gets bigger as data is removed it will get smaller.

Front 5

Example of a dynamic data structure?

Back 5

Linked list, dynamic tree

Front 6

Advantages of static structures?

Back 6

1. Compiler an allocate space during compilation

2. Easy to program

3. Easy to check for overflow

4. An array allows random access

Front 7

Disadvantages of static structures?

Back 7

1. Programmers has to estimate the maximum amount of space that is going to be needed

2. Can waste a lot of space (if estimate was too high)

Front 8

Advantages of dynamic structures?

Back 8

1. Only uses the space needed at any time

2. Makes efficient use of memory

3. Storage no longer requires can be returned for the system for other uses

Front 9

Disadvantages of dynamic structures?

Back 9

1. Difficult to program

2. Can be slow to implement searches

3. A linked list only allows serial access (starting at the beginning going through one at a time

Front 10

3 examples of data structures?

Back 10

Stacks, Queues, Trees

Front 11

What type of structure is a stack?

Back 11

LIFO - Last In First Out

Front 12

Describe a Stack

Back 12

1. The computer can only manipulate the top of the stack

2. It has stack pointer which points to the top of the stack (last item of data added)

Front 13

Keywords to add and remove data from a stack?

Back 13

Add - Push

Remove - Pop

Front 14

4 steps to insert new data to a stack?

Back 14

1. Check to see if stack is full

2. If the stack is full report an error and stop

3. Increment stack pointer

4. Insert new data item into cell pointed to by the SP

Front 15

4 steps to delete/read data from the stack?

Back 15

1. Check to see if stack is empty

2. If the stack is empty report an error and stop

3. Copy data item in the cell pointed to by the SP

4. Decrement the stack pointer and stop

Front 16

Describe a queue

Back 16

1. Has two pointers - one to the front of the queue and one to the back

2. New elements are added to the tail/back

3. Elements being deleted or read are taken from the front of the queue

Front 17

What happens when a queue is empty?

Back 17

The tail and head pointers have the same value

Front 18

4 points to insert new data into a queue

Back 18

1. Check to see if queue is full

2. If the queue is full then report an error and stop

3. Increment cell pointed to by the tail pointer

4. Add new data to the cell pointed to by the tail pointer

Front 19

4 points to read/delete data from a queue?

Back 19

1. Check to see if queue is empty

2. If queue is empty report error and stop

3. Copy the data item pointed to by front pointer

4. Increment from pointer

Front 20

What do we call a queue that is within an array?

Back 20

A circular queue

Front 21

Benefits of a circular queue

Back 21

1. Easier to program

2. All available storage can be reused

Front 22

Describe a Tree

Back 22

Each data item is called a node, the first data item is called the root.

The position of the data is determined by its relationship with existing data already in the tree.

They allow us to store data in a particular order.

Front 23

Algorithm for inserting a node into a tree?

Back 23

1. Start at the root

2. REPEAT

1. Compare the new data to current node

2. If new data < current node, follow left pointer (branch)

3. Else follow the right pointer

3. UNTIL there is no node at the end of the pointer

4. Write the new data into the tree

5. Create two new (empty) branches for his new node

Front 24

How to read a tree?

(non algorithmic)

Back 24

1. If there is a left branch that has not been traversed, do the following:

2. Read the node if not already read

3. If there is a right branch, traverse it and repeat step 2

4. Go back up one layer and repeat

Front 25

Problem with deleting data from a tree?

Back 25

Each node is not only a data item but a part of the structure as well.

If we simply delete data it would be like sawing off a branch and having everything else on that branch fall off too.

Front 26

Solution to deleting data from a tree?

Back 26

Instead of deleting it properly, we leave it in there but label it as 'deleted'. This means that the computer will not read it when the tree is being searched through.

Front 27

What are the two purposes of a node

Back 27

1. To store an item of data

2. To maintain an ordered structure

Front 28

Two searching algorithms?

Back 28

Serial Search

Binary Search

Front 29

Algorithm for serial search

Back 29

1. Check array is not empty

2. Each data element in the array is compared to the search item in turn

3. When the item is found, the index is returned, search is stopped

4. If the computer reaches the end of the array without finding the item, an error message is produced

Front 30

Algorithm for binary search

Back 30

1. While the list is not empty

2. Find the mid point data item in the current list

3. If the mid point item is the required item then return the index and stop

4. If value being searched for is less that the value in the middle then...

1, Make the search list the first half of the current list

2. Else make the search list the second half of the current list

5. Report an error if item is not in list

Front 31

Describe a serial search

Back 31

1. Each data element in the array is compared to the search item in turn

2. When the item is found the index is returned, search is stopped

3. If the computer reaches the end of the array without finding the item an error message is produced

Front 32

Describe a Binary Search

Back 32

1. Continually compare the middle data item in the list with the search item

2. Repeatedly split the list into two equal halves

3. Until the middle value = the search item or error if the new list is empty

Front 33

Algorithm to merge files

Back 33

1. Select value at the front of each list

1. While neither list is empty

2. Compare the values in the lists

3. Copy the smaller value to the new list

4. Read the next value in the list that has had a value copied

2. When one list is empty copy the remainder of the other list to the new list

Front 34

What does the previous (merging files) algorithm assume?

Back 34

That there are no duplicate values in the lists and that both actually contain data

Front 35

Name two sorting algorithms

Back 35

Insertion Sort

Quick Sort

Front 36

When is the insertion sort suitable?

Back 36

When the list...

1. is small

2. is almost sorted in the right order

3. contains many data items of equal value as it is stable (equal values aren't reordered)

Front 37

Advantages of insertion sort?

Back 37

1. Easy to implement

2. Efficient when lots of duplicate values in list

3. Can sort a list of data as it receives each data item

4. Only requires a constant (set) amount of memory space

Front 38

Disadvantages of insertion sort?

Back 38

1. Not good on large data sets

2. Not efficient when data is in reverse order

Front 39

When is the quick sort suitable?

Back 39

When the list...

1. is large

2. is in reverse order

3. The data is completely out of sequence

Front 40

Advantages of quick sort?

Back 40

1. Efficient on large data sets

2. Efficient on data in reverse order

3. Efficient when data is completely out of sequence

Front 41

Disadvantages of quick sort?

Back 41

1. Hard to implement

2. Not good on data that is partially sorted

3. Not good on data with lots of duplicate values

Front 42

Algorithm for a quick sort?

Back 42

1. H?????