Data Structures Flashcards
What is a data structure?
A group/collection of related data elements
What is an array?
- Data structure where there is a predetermined number of elements of the same type.
- Elements are accessed via indexes
What is a record?
Set of data items which are all related to a single entity and can contain data of different types
What is a stack?
‘First In, Last out’ data structure where data elements can only be added and removed at the top
What examples can stacks be used for?
- Store subprogram addresses
- Store recursion values
- Store short-term arithmetical results
- Undo Function
What does a ‘Push’ and a ‘Pop’ include in a stack data structure?
- Push adds items to the top of a stack and pop removes the item from the top.
- Underflow may occur if you attempt to pop an empty stack and overflow occurs if you attempt to push to a full stack.
Why are stacks and queues commonly used for most situations?
The natural processing order is first in last out or first in first out depending on the situation.
How would a stack be implemented?
Would be stored in an array and a pointer would keep track of the top of the stack.
Pseudocode for pushing onto a stack:
If stackPointer < stackMaximum then:
stackPointer = stackPointer + 1
stackArray(stackPointer) = dataItem
Else:
Output “Stack is full - your data has not been saved”
Pseudocode for popping from a stack:
If stackPointer > 0 then:
dateItem = stackArray(stackpointer)
stackPointer = stackPointer - 1
Else:
Output “Stack is empty - no data can be retrieved”
What is a Queue?
‘First In, First Out’ data structure which could be used for printer queues and keyboard buffers
How would you implement a queue?
Data would be stored in an array and two pointers would keep track of the front and the back of the queue.
What is a linked list?
A set of data elements where each element contains the data itself and a pointer to the next element.
What are the benefits of using a linked list?
Items can be added without rearranging the entire order and can use memory more efficiently if programmed dynamically.
What are the drawbacks of using linked lists?
More difficult to program and manipulate than an array, extra programming is needed to send the data in the opposite direction and it can only be accessed in a linear manner.
What is a binary tree?
Data structure made up of nodes and branches, root node at the top of the tree and the data is added in the order it occurs in.
Name an advantage and disadvantage of using a binary tree rather than an array.
It is faster to search and add a value however it is more complex to program and process.
What happens if a binary tree is not well balanced?
searching and processing times will be significantly increased
What are the three methods of traversing a binary tree?
Preorder (root, left, right)
Inorder (left, root, right)
Postorder (left, right root)
What is a hash table?
Two components including a table where the actual data is stored and a mapping function (hash function)
What is the point of a hash function?
Uses the data that will be entered in the table to generate a location as to where it should be stored.
What is separate chaining?
The original table stores a link to a dynamic structure like a linked list which will add a new node in case of duplicate data locations.
What is an advantage and disadvantage of separate chaining?
It avoids data collisions however it will slow down trying to find the data again as the linked list would have to be searched after the hashing algorithm is complete
What other solution can be used instead of separate chaining?
Flagging the original block and moving the data into an overflow area for subsequent linear search
