SLR14 Flashcards
(75 cards)
1
Q
What’s are the characteristics of Lists as a data type
A
- mutable
- ordered collection of items
- items can be changed or replaced
- can store more than one data type
2
Q
What’s are the characteristics of an array as a data type
A
- mutable
- ordered collection of items
- items can be changed or replaced
- can only store one data type
3
Q
What’s are the characteristics of a Tulpe as a data type
A
- immutable
- unordered collection of items
- items cannot be changed or replaced
- can store more than one data type
4
Q
What’s are the characteristics of a record as a data type
A
- mutable
- ordered collection of items
- items can be changed or replaced
- can store more than one data type
5
Q
What does LIFO stand for
A
Last In First Out
6
Q
What structure do stacks function in
A
LIFO
7
Q
How many pointers does a stack have a where are they?
A
One and the top node
8
Q
What happens when you try to remove an item from an empty stack
A
Underflow error
9
Q
What happens when trying to add an item to a full stack
A
An overflow error
10
Q
What are stacks used for
A
- user inputs
- back tracking algorithms
- evaluating mathematical equations without brackets
11
Q
What are the three operations of a stack
A
- push
- pop
- peek
12
Q
What does the push operation do in a stack
A
Adds a new item to the top of a stack
13
Q
What does the pop operation do in a stack
A
Removes the top item off of the stack
14
Q
What does the peek operation do in a stack
A
Returns the value of the top item in a stack without removing or deleting it
15
Q
What is the process of enqueuing in an array
A
Adding an item to the back of a queue
16
Q
What is the process of dequeuing in an array
A
Removing the item from the front of the queue
17
Q
What will happen if you try and remove an item from an empty queue in an array
A
An underflow error
18
Q
What will happen if you try an add an item to a full queue in an array
A
An overflow error
19
Q
In what way does a queue in an array operate
A
FIFO
20
Q
What does FIFO stand for
A
First In First Out
21
Q
What does FIFO stand for
A
First In First Out
22
Q
What are the three operations in a queue in an array
A
- enqueue
- dequeue
- peek
23
Q
What is the process of enqueuing in an array
A
Adding an item to the back of a queue
24
Q
What is the process of dequeuing in an array
A
Removing an item from the from of a queue
25
What is the process of peeking in a queue in an array
Returning the value of the item at the front of the queue without removing or deleting it
26
What type of data structure is a queue
A linear data structure
27
As Queues are a FIFO structure what does this allow us to do that you can’t do with a stack
Add priority
28
What does priority do
Allows items to skip the queue or part of the queue based on there importance
29
How many pointers does a queue have and where are they
Two and at the back and the front
30
Where can queues be implemented
- in an array
- Object-Orientated Programming
31
What are the front and back pointers also known as
Head and tail pointers
32
When are the head and tail pointers moving
In circular queues
33
What can queues be used for
- process scheduling
- transferring data between processors and printers
- performing breadth-first searches on graph data structures
34
How are linked lists made
Attaching two nodes together with a pointer
35
How can linked lists become circular
By having the last node have a pointer back to the first node
36
What effect do linked lists have on run times and why
Dramatically changing run times because they are a dynamic data structure meaning data is not stored in order
37
Where are linked lists used
- Operating systems
- Image viewers
- Music players
- Web browsers
- Hash table collision resolution
- Maintaining a file allocation
38
What are the 5 operations of a linked list and what do they do
- ADD: add a node to the linked list
- DELETE: remove a node from the linked list
- NEXT: moves to the next item in the linked list
- PREVIOUS: moves to the previous item in a doubly liked list
- TRAVERSE: a linear search through the linked list
39
How are linked lists made in graphs
Nodes / vertices
Pointers / edges
40
In graphs do edges have direction or not
Either
41
How can graphs be weighted
Each edges has its own value which can be represented as many things such as distance, time and bandwidth
42
What are weighted graphs used for
Mapping roads
Storing social network data
Resource allocation in OS
Representing molecular structures and geometry
43
How are graphs stored in an array
[( [0, 1, 1, 1, 0],
[0, 0, 1, 0, 1,],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 0],
[0, 0, 1, 0, 0] ])
44
What does a tree consist of
Nodes and pointers
45
Where is the trees root node
At the top of the tree
46
What is at the bottom of a tree
The left nodes
47
What are the typical uses of rooted trees
Storing and managing file and folder structures
Implementations of the A* pathfinding algorithm
Any form of hierarchical data like family trees, corporate structure
48
What are the typical uses of binary trees
Database applications
Wireless networking and router cables
OS scheduling process
Huffman coding
Cryptography (GMM)
49
What are the 7 operations of trees
Add
Delete
Binary search
Pre-order traversal
In-order traversal
Post-order traversal
Breadth-first search
50
What is the priority system in a depth-first traversal graph
LIFO
51
What are the two main stages in a depth-first search
1. Visited nodes are pushed onto the stack
2. When there are no nodes left to visit the nodes get popped off the stack
52
What are the steps of an iterative approach to a depth-first traversal graph (6)
1. Set the root node as the current node
2. Add the current node to the list of visited nodes if it isn’t already in the list
3. Follow every edge connected to the node
If the connected node is not in the visited list push the linked node on to the stack
4. Pop the stack and set the removed item as the current node
5. Repeat from step two until there are no nodes left to visit
6. Output all visited nodes
53
What are the steps of a recursive approach to a depth-first traversal graph (4)
1. Set the root vertex as the current vertex
2. Output the vertex
3. Add the vertex to the list of all visited vertices
4. If the vertex has an edge that has not been visited
- follow the edge and make that vertex become the current vertex
- repeat from step 2
54
What is the breadth-first traversal method used for
Finding the shortest path through a graph
55
What type of data structure is breadth-first traversal graph
FIFO
56
What is the method for a breadth-first traversal graph (6)
1. Set the root node as the current vertex
2. Add the current vertex to the list of visited if not already on the list
3. For every edge connected to the vertex
- if the connected node is not in the visited list, enqueue the linked node
4. Dequeue and set the vertex that’s been removed at the current vertex
5. Repeat from step 2 until the queue is empty
6. Output all visited vertices
57
How many children can each binary trees node have
Either 0, 1, 2
58
Where can binary trees be used
Dictionary’s
Arrays
Objects
59
Where are binary search tree used
In database applications where efficient searching is needed
60
How many directions does a 1D array, 2D array, 3D Array, 4D Array, 5D Array grow in
One
Two
Three
One with a full 3D array in each
Two with a full 4D Array in each
61
How do you input data in an empty binary tree
1. First check if there is free memory if not output and error
2. Create a new node and insert the data into it
3. If the binary tree is empty: the new node becomes the root node along with a starter pointer pointing to it
62
How do you input data into a binary tree that’s not empty (3(4))
1. First check if there is a free memory if not output an error
2. Create a new node and insert the data into it
3. If the tree isn’t empty:
1. Start at the root node
2. If the new node should be placed before / after the current node follow the left / right pointer
3. Repeat step 2 until until a leaf node is reached
4. Decide weather the new node should come before or after the left node and go left or right accordingly
63
How do you delete data from a binary tree if the node that is being deleted has no children
1. Start with the root node a set it as the current node
2. While the current node exists and is not the root the to be deleted:
1. Set the previous node to be the same as the current node
2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
3. If the node to be deleted has no children: the previous nodes pointer is set to null
64
How do you delete data from a binary tree if the node being deleted has one child
1. Start with the root node a set it as the current node
2. While the current node exists and is not the root the to be deleted:
1. Set the previous node to be the same as the current node
2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
3. If the node to be deleted has one child: if the current node is less / greater than the previous nodes left / right pointer to the nodes left / right child
65
How do you delete data from a binary tree if the node to be deleted has 2 children
1. Start with the root node a set it as the current node
2. While the current node exists and is not the root the to be deleted:
1. Set the previous node to be the same as the current node
2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
3. If the node to be deleted has two children:
1. If the right node exists and it has a left sub tree find the smallest leaf node in the right sub tree
1. Changes the current node to be the smallest left node
2. Remove the smallest left node
2. If the right node exists and it has no left subtree
1. Set the current node to be the current nodes right pointer
2. Set the current nodes right pointer to be null
66
What is the main goal of a hash table
To be impossible to reverse engineer
67
What are hash tables used for
To find something from a sorted or unsorted listed
68
What are hash tables used for in programming
To implement a dictionary data structure
69
Why are hash tables often much larger than what they need to be
To make sure no value is returned more than once
70
What is it known as when two things output the same value in a hash table or occupy the same space in a hash table
A collision
71
What are hashing functions used for
Calculating the position of an item in a hash table
72
What should a good hashing function include (3)
1. Be calculated a quick as possible
2. Result in as few collisions as possible
3. Use as little memory as possible
73
What happens when there are to many items in a hash table for it to handle
Clustering (2D hash table with an overflow table)
74
How does an overflow hashing table function
As a linked list where items in a hash table can be stored while there isn’t a place to store them
75
How do you add an item to a hash table
1. Calculate the position of the item in the hash table
2. If the calculated position is empty then insert the item and stop
3. If the calculated position is not empty then check the first position in the overflow table
1. If empty then stop
2. If not check the next position in the overflow table
3. Repeat until the item is inserted or the table is full
