| - finite
- ordered
- items must be of the same type | What are 3 properties of a 1-dimensional array? |
| birdName = ["robin", "blackbird", "pigeon"] | How would you define an array called birdName with the contents "robin", "blackbird" and "pigeon"? |
| len[birdName] | How would you return the length of the array birdName? |
| 7 | Assuming this table is called numbers, what would be in numbers[1,2]? |
| 2-dimensional | What type of array is this?
quarterSales = [[100, 110], [130, 80], [90, 210], [60, 130]] |
| - The elements don't need to be of the same type
- Immutable (it's elements can't be changed and you can't dynamically add or remove elements) | How is a tuple different from an array? |
| pupil = ("John", 78, "a") | How do you define a tuple in python?
create a tuple called pupil with the values "john", "78", "a" |
| pupil[0] | How do you refer to the first element in the tuple called "pupil"? |
| When you want to store data permanently in a file on disk | When would you use a record? |
| student.surname | Below is the declaration of a new record, how would you then refer to the surname?
studentType = record
integer ID
string firstname
string surname
date dateOfBirth
string class
end record |
| One which is created by the programmer, rather than defined within the programming language
- A logical description of how the programmer views data - only concerned with what the data is representing, not how it's constructed | What is an abstract data type? |
| - Queues
- Stacks
- Trees
- Graphs | What are 4 examples of abstract data types? |
| - Printer queue
- Queue of keys pressed on a keyboard | What are two real-world examples of uses of queues? |
| enQueue(item) | How do you add an item to the end of a queue? (code) |
| deQueue() | how do you remove the front item from the queue and return it? |
| isEmpty() | how do you check if the queue is empty? |
| isFull() | How do you check if a queue is full? |
| - Dynamic data structures are ones which can grow or shrink in size
- They require a heap in order to work | What is a dynamic data structure and what do they require in order to work? |
| A portion of memory from which space is automatically allocated or de-allocated as needed | What is the heap? |
| A list | What's an example of a dynamic data structure in python? |
| May grow too large and cause overflow, crashing the program | What's a downside of using a dynamic data structure? |
| - moving the items forward items are removed (may cause long processing time with large queues)
- keeping the items in place and using pointers instead | What are 2 ways of implementing a linear queue? |
| - Space which can't be filled will slowly show up at the start of the queue
- Can be fixed with a circular queue - putting new items at the start of the queue once the end is reached like a loop | What is an issue with using pointers in a linear queue and how can it be fixed? |
| A queue where the items are ordered by priority, not order in which they were added | What is a priority queue? |
| Check the priority of each item in the queue, starting at the back and moving it along one place until an item with the same or lower priority is found, at which point the new item can be inserted | How would you implement a priority queue? |
| Trying to pop from a stack which is already empty | In the context of stacks, what is underflow? |
| myList.isEmpty() | In python, how do you test if a list "myList" is empty? |
| myList.append(123) | in python, how do you add "123" to the end of the list "myList"? |
| Removes the first occurence of "item" in the list "myList" | In python, what does "myList.remove(item)" do? |
| myList.search(item) | In python, how do you search for "item" in the list "myList"? |
| myList.length() | in python, how do you return the length of the list "myList"? |
| Returns the position of "item" in the list | in python, what does "index(item)" do? |
| myList.insert(2,7) | in python, how do you insert "2" at the position "7" in the list "myList"? |
| With pointer fields which point to the next 'node' in a list | How are linked lists connected? |
| - Pressing the back button on a web browser
- Pressing undo in photoshop or word | What are two common everyday applications of a stack? |
| - A pointer to the top of the stack
- A var holding the size of the array (the maximum size of the stack) | A stack can be implemented with either a dynamic or a static data structure, what two additional variables are needed if a static data structure is used? |
| push(item) | How do you add a new item to a stack? (code) |
| pop() | How do you remove and return an item from a stack? (code) |
| Returns the top item from the stack without removing it | In the context of stacks, what does peek() do? |
| isEmpty() | How do you check if a stack is empty? (code) |
| isFull() | How do you check if a stack is full? (code) |
| append() | What command would you use to 'push' an item onto the end of a stack in python? |
| The address of the instruction that control should return to when a subroutine ends | What does the call stack hold? |
| - Stack frames are groupings in the stack, they show the stuff related to different subroutines called | What is a stack frame? |
| Divide the key by the number of AVAILABLE addresses and take the remainder as the address | What is a common hashing algorithm? (explain the process, not the name) |
| - Apply the hashing algorithm to the key field of the item
- Check the resulting cell in the list
- if the item is there, return the item
- if the cell is empty, the item isn't in the table
- if there's another item in that spot, keep moving forward until either the item is found or a blank cell is encountered | How do you search for an item in a hash table? (step by step) |
| - Dividing the item into equal parts and then adding them together to get the hash value
- If it's too big to store, divide by the number of spaces in the table | What is the folding method? (hashing algorithm) and what extra step must be taken if the resulting hash is too large to store on the table? |
| Using the ASCII code for each character | How can you hash an alphanumeric string? |
| 65 | What is the ASCII value for A? |
| Finding a free space after a collision occurs | What is rehashing? |
| Dictionaries | What data structure are hash tables used for the implementation of? |
| An abstract data type consisting of pairs of items - a key and a value | What is a dictionary? |
| Dictionary | What data structure is this?
IDs = {342: "Ellen", 634: "Jasmine", 885: "Max", 571: "Sheila"} |
| Adjacency matrix and adjacency list | What are the two ways of implementing a graph? |
| - Adjacency matrix
- Distance is 2 | Which implementation of a graph is this? (adjacency matrix or adjacency list?)
And what is the distance from B --> D? |
| Write 1s instead of weights in the table | How would you alter an adjacency matrix to represent an unweighted graph? |
| - In a graph with lots of nodes but very few connections there is alot of wasted memory
- Adjacency lists fix the issue | What is an issue with adjacency matrices? And what is an alternative which fixes this issue? |
| Adjacency List | What type is this? |
| 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 | What would be the order of traversal for a depth-first traversal? |
| 1, 2, 7, 8 3, 6 9 12 4, 5 10, 11 | What about in a breadth-first traversal? |
| - Roads between towns
- Networks | What are two things graphs could be used to represent? |
| left subtree -> root node -> right subtree | What order is the tree traversed in an in-order traversal? |
| left subtree -> right subtree -> root node | What order is the tree traversed in a post-order traversal? |
| root node -> left subtree -> right subtree | What order is the tree traversed in a pre-order traversal? |
| - Pen-type
- Laser Scanners
- CCD readers
- Camera based readers | What are 4 types of barcode scanners? |
| Pen-type readers are the most durable type BUT they need to come into physical contact with what they're reading to work | What type of barcode reader is the most durable and what is the drawback of it? |
| - Barcode Readers
- biometric devices
- sensors | Give 3 examples of automatic input devices? |
| Can store lots of data cheaply but is inconvenient to move around | One advantage and one disadvantage of magentic storage |
| Portable and cheap but small capacity and easily damaged | TWO advantages and TWO disadvantages of optical storage |
| - Backup is a precaution against losing data
- Archiving is storing rarely used data to free up space | What's the difference between backup and archiving? |
| Pits and lands - Pits are burned into the disk's surface with a laser making it less reflective at those points.
pit = 1
land = 0 | How is data stored on optical storage?
And how is 0 and 1 represented? |
| Blu-Ray has shorter wavelength in the laser which allows much smaller pits to be engraved which means more can be fit in a smaller space | Blu-Ray vs CD ROM - Which has higher capacity and why? |
| They all have a way of representing 1 and 0 without power | What is a similarity between all secondary storage devices? |
| Camera-based scanners | What is the most reliable type of barcode reader? (use for Berlin Film Festival Tickets) |
| Laser scanners | What type of barcode reader is used in supermarkets? |
| - RFID (Radio Frequency Identification)
- Passive and Active | What is the technology used for oyster cards and what are the two types? |
| Dog tagging | What is another use of RFID tags other than bank cards/oyster cards? |
| OLED is plastic so it can bend | What's the difference between LED and OLED screens? |
| - don't last as long
- sensitive to water
- slow refresh rate (bad for games) | What are 3 disadvantages of OLED displays? |
| - Thinner
- Don't need backlighting
- Consume less power | What are 3 advantages of OLED displays? |
| - they're decent quality and FAST
- They use toner as ink | What's the good thing about laser printers and what type of ink do they used? |
| - Inkjet
- Works by spraying minute dots on the page | What type of printer is very high quality and how does it work? |
| Moving an aileron | What is a use of an actuator in the context of a plane? |
| - Fast read/write speed
- Power efficient
- Less fragile
- Silent
- More portable | Name 5 advantages of SSDs |
| - Relatively low capacity
- Expensive | Give 2 disadvantages of SSDs |
