Flashcards in Data Types and Structures Deck (22):
Describe a 1D array
Data structure which contains as set of variables of the same data type
Position is stored using an integer index
What is a 2D array?
An array of arrays
What is the difference between an array and a linked list?
Array - items organised sequentially
Linked List - items organised sequentially, but each item contains a link to next item
Give two advantages of linked lists
Dynamic Data structure, can grow and shrink
Very flexible, order of items can be changed without moving data
More memory efficent
Give a disadvantage of a linked list
Not possible to identify a specific item directly using its index
Give an example of a dynamic data structure which linked lists are used to implement
Why is it inefficient to to resize an array in the middle of execution?
Array has to be copied into new memory to accommodate the extra added items
Double array in memory
What is a stack?
A stack is a data structure which behaves like a vertical list
Elements can be added or deleted from the top of the stack
'Last in, First out'
In what situation would a stack be useful?
Situation which calls for the most recent items to be accessed
Store code produced during compilation of high level languages
Intermediate results of calculations
If you have a stack overflow error on a computer what does this mean?
Program has attempted to place too many items on the stack
Describe a queue
1D array or list, items are inserted and retrieved at different ends
'First in, First Out'
Identify three variables required for implementation of a stack
Maximum stack size
How can a 2D array be accessed?
(Two fixed loops)
Describe a linked last
Dynamic data structure where data items have a link to the next item in the list
Describe a record
Data structure consisting of several variables of different types
Describe situations where queues are useful to implement
- multiple printing jobs have to be processed
- scheduling of tasks in a multitasking environment.
- event-driven languages where events are placed in a queuing system to wait being processed
What is a circular queue?
A queue which uses a system where only the start and end pointers move, allowing the array to behave as if its spaces were arranged in a circle.
Where will a link to the last data item point to?
How many pointers does a queue usually need?
What is a dynamic data structure?
Data structure that can grow or shrink during execution
What are two advantages of a 1D array over a 2D array?
- Allows different data types
- More memory efficient if stored in suitable data type