33768251
Descrição
FlashCards por Malachy Moran-Tun, atualizado more than 1 year ago
|
|
Criado por Malachy Moran-Tun
mais de 2 anos atrás
|
|
| Questão | Responda |
| What 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 |
| What are some Examples of Abstract Data Structure? | > Queues > Stacks > Trees > Graphs |
| What 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. |
| What 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) |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| How 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 |
| How 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) |
| What 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 |
| What 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 |
| What Abstract Data Structures can be Implemented using a List? | > Queues > Stacks > Trees |
| What 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 |
| How 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 |
| How 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 |
| What 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 |
| How 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 |
| How 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 |
| What 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 |
| What 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) |
| What 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 |
| How 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 |
| Why 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What are the 2 ways of Traversing a Graph? | 1. Depth-first 2. Breadth-first |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| What 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 |
| Define 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 |
| What is a Binary Tree? | > Rooted tree with a maximum of two children > Usually used to search for items (when organised in such a fashion) |
| How 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 |
| What 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 |
| What'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 |
| What's the Hard Way of Traversing a Binary Tree? | idk lol i forgot textbook doesn't say |
Quer criar seus próprios Flashcards gratuitos com GoConqr? Saiba mais.