Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
42 Cards in this Set
- Front
- Back
What is a data structure?
|
A data structure is a way of storing data so that the positions of elements has meaning. |
|
What is a static data structure?
|
A static data structure is one which does not change in size when the program is running.
|
|
Example of a static data structure? |
Array
|
|
What is a dynamic data structure?
|
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. |
|
Example of a dynamic data structure?
|
Linked list, dynamic tree |
|
Advantages of static structures?
|
1. Compiler an allocate space during compilation 2. Easy to program 3. Easy to check for overflow 4. An array allows random access |
|
Disadvantages of static structures?
|
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) |
|
Advantages of dynamic structures?
|
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 |
|
Disadvantages of dynamic structures?
|
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 |
|
3 examples of data structures?
|
Stacks, Queues, Trees |
|
What type of structure is a stack?
|
LIFO - Last In First Out |
|
Describe a Stack
|
2. It has stack pointer which points to the top of the stack (last item of data added) |
|
Keywords to add and remove data from a stack?
|
Add - Push Remove - Pop |
|
4 steps to insert new data to a stack?
|
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 |
|
4 steps to delete/read data from the stack?
|
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 |
|
Describe a queue
|
2. New elements are added to the tail/back 3. Elements being deleted or read are taken from the front of the queue |
|
What happens when a queue is empty?
|
The tail and head pointers have the same value |
|
4 points to insert new data into a queue
|
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 |
|
4 points to read/delete data from a queue?
|
2. If queue is empty report error and stop 3. Copy the data item pointed to by front pointer 4. Increment from pointer |
|
What do we call a queue that is within an array?
|
A circular queue |
|
Benefits of a circular queue
|
2. All available storage can be reused |
|
Describe a Tree
|
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. |
|
Algorithm for inserting a node into a tree?
|
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 |
|
How to read a tree? (non algorithmic) |
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 |
|
Problem with deleting data from a tree?
|
If we simply delete data it would be like sawing off a branch and having everything else on that branch fall off too. |
|
Solution to deleting data from a tree?
|
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. |
|
What are the two purposes of a node
|
2. To maintain an ordered structure |
|
Two searching algorithms?
|
Binary Search |
|
Algorithm for serial search
|
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 |
|
Algorithm for binary search
|
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 |
|
Describe a serial search
|
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 |
|
Describe a Binary Search
|
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 |
|
Algorithm to merge files |
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 |
|
What does the previous (merging files) algorithm assume? |
That there are no duplicate values in the lists and that both actually contain data
|
|
Name two sorting algorithms |
Insertion Sort Quick Sort |
|
When is the insertion sort suitable? |
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) |
|
Advantages of insertion sort? |
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 |
|
Disadvantages of insertion sort? |
1. Not good on large data sets 2. Not efficient when data is in reverse order |
|
When is the quick sort suitable? |
When the list... 1. is large 2. is in reverse order 3. The data is completely out of sequence |
|
Advantages of quick sort? |
1. Efficient on large data sets 2. Efficient on data in reverse order 3. Efficient when data is completely out of sequence |
|
Disadvantages of quick sort? |
1. Hard to implement
2. Not good on data that is partially sorted 3. Not good on data with lots of duplicate values |
|
Algorithm for a quick sort? |
1. H????? |