Karteikarten
[Almost Done] Data Structures - OCR Computer Science A Level
Karten in diesem Stapel (44)
- 1What is an Abstract Data Structure?> Created by the programmer
> Not defined within the programming language
> Easy to represent in graphical forms
> Programming languages require other data types to represent them - 2What are some Examples of Abstract Data Structure?> Queues
> Stacks
> Trees
> Graphs - 3What is a Static Data Structure?A data structure with a fixed size: it cannot increase in size, or decrease and free up memory (while the program is running): an array.
- 4What is a Dynamic Data Structure?> Collection of data in memory that has the ability to grow or shrink in size
> Uses a heap - a portion of memory where space is automatically allocated or de-allocated when required
> Supported in Python, Java, and C (amongst others) - 5What are the Advantages and Disadvantages of a Static Data Structure?> Suitable for storing a fixed number of items without exceeding memory
> The size has to be decided in advance, meaning that no more can be added if the number of items fills up, regardless of how much free space there is in memory - 6What are the Advantages and Disadvantages of a Dynamic Data Structure?> Useful for implementing data structures where the maximum size of the data structure is not known in advance
> Methods or functions may already be written in advance in the programming language (e.g.: lists in Python)
> The data structure can potentially cause an overflow and crash the program if it exceeds the maximum memory limit - 7What is a Queue?> First in, first out (FIFO) data structure
> Contains multiple elements, similar to a one-dimensional array
> New elements can only be added to the end
> Elements can only be retrieved from the front
> Sequence of elements is determined by the order in which they are inserted - 8What are some Examples of Queues being Used?> Multiple documents to be printed on one printer, e.g., in a room of networked computers
> Characters typed on a keyboard are held in a queue in a keyboard buffer
> Simulation problems, e.g., simulating traffic data - 9What Operations can be Performed on a Queue?> enQueue(item) - Adds a new item to the rear
> deQueue() - Removes the front item and returns it
> isEmpty() - Returns true if the queue is empty, false if not
> isFull() - Returns true if the queue is full, false if not - 10How can a Linear Queue be Implemented with Static Data Structures?One of two ways:
1. When items leave the queue, all other items are moved up one position in the allocated memory, however this could require significant processing time
2. A front and rear pointer are created, which change depending on items entering and exiting the queue, however, as items exit, there is empty space at the front which cannot be filled, so there becomes less and less space: the elements themselves do NOT move - 11How can a Circular Queue be Implemented with Static Data Structures?> A front and rear pointer are created, which change depending on items entering and exiting the queue
> Unlike a linear queue, the pointers "wrap" around
> Meaning an element that wouldn't fit in the array will go to the beginning (assuming it isn't full)
> This requires extra effort to program, and is less flexible than a dynamic data structure
(Pseudocode can be found in textbook) - 12What is a Priority Queue?> Acts like a queue, in terms that items are dequeued by removing them from the front
> The order of the items in the queue is determined by a priority, not the order they entered / exited
> Highest priority items are at the front of the queue, lowest are at the back
> Possible that a new item joins at the front, rather than the rear - 13What is a List?> Abstract data type consisting of a number of items
> The same items can occur more than once
> Sequenced, so you can refer to the first to last element
> Whilst list can refer to dynamic or static lists (the latter being arrays), they are usually dynamic unless specified - 14What Abstract Data Structures can be Implemented using a List?> Queues
> Stacks
> Trees - 15What Operations can be Performed on a List?> isEmpty() - Returns true if the list is empty, false if not
> append(item) - Adds a new item to the end of the list
> remove(item) - Removes the first occurrence of an item
> search(item) - Returns true if a specific item is found in the list, false if not
> length() - Returns the number of items
> index(pos, item) - Inserts a new items at the specified position
> pop() - Removes the last item in the list and returns it
> pop(pos) - Removes the item at the specified position and returns it - 16How would an Item be Inserted into a Static List?1. Check to see if the list is already full, if it isn't proceed, if it is, quit (and print a message)
2. Determine where the new item needs to be inserted
3. Starting at the end of the list, move all the other items up to where the item needs to be inserted up one
4. Insert the new item in the correct place - 17How would an Item be Deleted from a Static List?1. Replace the item with a blank value
2. Move up all items, until the blank value, by copying them to the previous spot
3. Replace the last element (which is duplicated) with a blank - 18What is a Linked List?> Dynamic data structure
> Used to hold an ordered sequence
> Items in the sequence are not (necessarily) held in contiguous (consecutive) data locations, or even in the order in which they occur in the sequence
> Each item in the list is called a node
> Each node contains a data field, and a link or pointer field
> The data field holds the node's data, the link field holds the next item's memory address
> If the link field is null, it indicates that there are no further items
> The list needs a pointer variable, which contains the memory address of the first node in the list - 19How would you Insert an Item into a Linked List?1. Store the new item in the node pointed to by the "nextfree" variable
2. Determine, by following the links, where the new item should be inserted
3. Change the "nextfree" variable to point to the next free location
4. Change the new item's pointer to point to the appropriate item
5. Change the item before the new item's pointer to point to the new item
(this sounds long winded and complicated, but it's really not, just hard to explain; certain steps can be in a different order too, as long as the result is the same)
Pseudocode in textbook - 20How would you Delete an Item from a Linked List?1. Follow the pointers until the item to be deleted is found
2. Change the item before the item to be deleted's pointer to the item after the one to be deleted
3. Change the item to be deleted's pointer to the "nextfree" variable's value
4. Change the "nextfree" variable to point to the item to be deleted (this means that the item will be overwritten when necessary)
(this sounds long winded and complicated, but it's really not, just hard to explain, once again)
Pseudocode in textbook - 21What is a Stack?> Last in, first out (LIFO) data structure
> Contains multiple elements, similar to a one-dimensional array
> New elements can only be added to the top
> Elements can only be retrieved from the top
> Sequence of elements is determined by the order in which they are inserted - 22What are some Examples of Stacks being Used?> Back buttons in web browsers
> Undo functions in various applications (e.g.: word processors, music software, etc.)
> Hold return addresses when subroutines are called
> Calculations (apparently) - 23What Operations can be Performed on a Stack?> push(item) - Adds a new item to the top of the stack
> pop() - Removes the top item from the stack and returns it
> peek() - Returns the top item from the stack (does not remove it)
> isEmpty() - Returns true if the stack is empty, false if not
> isFull() - Returns true if the stack is full, false if not - 24How can a Stack be Implemented with Static Data Structures?> Two additional variables are created
> One pointer variable, which points to the top of the stack
> One being the maximum size of the array, which is used to stop overflow in the stack - 25Why would isFull() or isEmpty() need to be Called when Adding or Popping an Item to a Stack?> If the stack is static, there will be a maximum size determined by the array size
> If the pointer exceeds this size, an overflow error would occur, which could potentially crash the program, or write to unwanted memory, affecting it elsewhere
> If the pointer goes below 0, an underflow error would occur if an attempt is made to pop an item, potentially causing a crash - 26What are Graphs?> Form of abstract data structure (in the data structure topic‽ wow!)
> Used to represent complex relationships
> Set of vertices or nodes connected by edges or arcs - 27What is the Difference between Directed and Undirected Graphs?> Directed graphs (digraphs) have at least one one-way edge
> Undirected graphs all have two-way edges - 28What is the Difference between Weighted and Unweighted Graphs?> Weighted graphs show a sort of cost from one vertex to another - e.g.: a distance
> Unweighted graphs do not show this - 29What is the Adjacency Matrix?> Two dimensional array used to implement and represent a graph
> Rows and columns represent nodes
> Values in cells represents connecting edges
> Undirected graphs have symmetrical adjacency matrices - 30What is the Adjacency List?> List used to implement and represent a graph
> Each node points to a list of adjacent nodes
> If weighted, is implemented using a list of dictionaries, with the key being the node, and the value being the weight: {node : weight}
> If unweighted, an array is used to represent all adjacent nodes - 31What are the Advantages and Disadvantages of the Adjacency Matrix?> Convenient to work with and simple to understand
> Sparse graphs leave most elements empty
> The 2D array is static: it cannot grow or shrink, so the graph is limited to the size defined at the beginning of the program - 32What are the Advantages and Disadvantages of the Adjacency List?> More space efficient than adjacency matrix - no empty spaces
> Can be dynamic (i.e.: not use an array), allowing the graph to grow or shrink while the program is running
> Less convenient to work with and therefore harder to understand
> If dynamic, could potentially cause under / overflow errors - 33What are the 2 ways of Traversing a Graph?1. Depth-first
2. Breadth-first - 34What is Depth-First Traversal in Graphs?> Type of traversal that goes as far down one route as possible before backtracking
> Changes route at each intersection
> Follows the graph alphabetically / numerically
> Begins at the first letter / number
> Finishes once all nodes have been visited - 35What is Breadth-First Traversal in Graphs?> Type of traversal that visits all neighbouring nodes
> Visits the first visited node after all neighbouring nodes, then repeats the process
> Follows the graph alphabetically / numerically
> Begins at the first letter / number
> Finishes once all nodes have been visited - 36What are some Examples of Graphs being Used?> Computer networks - nodes being computers, weighted edges being the bandwidth
> Roads between towns, with weighted edges representing distance, journey time, fares etc.
> Tasks in a project, some of which have to be completed before others
> Webpages and links - 37What is a (Rooted) Tree?> Type of abstract data structure
> Similar to graphs, with "branches" or edges between each node
> One root note at the top, representing the top of the hierarchical structure
> Nodes at the bottom are known as leaf notes, representing the bottom of the hierarchical structure - 38What are some Examples of Trees being Used?> Hierarchical data, such as folder structures, in OSs
> Making information easy to search for (i.e.: binary trees)
> Manipulating sorted lists of data - 39Define the Following Terms used with Trees: > Node > Edge > Root > Child > Parent > Subtree > Leaf> Node - the data itself contained in the tree
> Edge - connector between two nodes
> Root - top of the hierarchy, the only node with no incoming edges
> Child - set of nodes that have incoming edges from the same node
> Parent - node with outgoing edges to children
> Subtree - set of nodes and edges comprised of a parent and all its descendants
> Leaf - a node with no children - 40What is a Binary Tree?> Rooted tree with a maximum of two children
> Usually used to search for items (when organised in such a fashion) - 41How would you Construct a Binary Search Tree?> Place the first item at the root
> For each item in the list, visit the root, and branch left or right if the value is less than or greater than the root respectively
> Continue down the branch with the same rule until a leaf node is reached
> Branch down and place the item to the left or right of the leaf node - 42What are the 3 Ways of Traversing a Binary Tree?> Pre-order traversal
> In-order traversal
> Post-order traversal
the names of which refer to whether the root of each subtree has been visited before, between, or after both branches - 43What's the Easy Way of Traversing a Binary Tree?draw lines lmao- it's that simple
> Pre-order traversal - mark the left of each node
> In-order traversal - mark the bottom of each node
> Post-order traversal - mark the right of each node
then draw an outline around the tree, starting to the left of the root node, and ending at the right of it - 44What's the Hard Way of Traversing a Binary Tree?idk lol i forgot
textbook doesn't say
Informationen
- Beschreibung
- A level Computer Science (Data Structures) Karteikarten am [Almost Done] Data Structures - OCR Computer Science A Level, erstellt von Malachy Moran-Tun am 06/10/2021.
- Erstellt von
- Malachy Moran-Tun
- Aufrufe
- 41
- Bewertung