Section 7: Data Structures Flashcards
Chapter 40:
What is Hashing?
Convert a string or document into a specific form using and algorithm that would completely scramble the result if one character is changed.
Chapter 40:
What is the difference between Hashing and Encryption?
Encryption is designed to be reversible, and used in transmission.
Hashing is designed to not be reversible, and used in signature checking.
Chapter 40:
What is a Hash Table?
A collection of values where the location of a value is its hash.
Chapter 40:
When using a Hash Table, What happens when an item is inserted, but its hash value is already taken?
It is rehashed.
Depending on the implementation, it may:
Place it in the next space to the right.
or
Store both values at the hash location using an array or equivelant.
Chapter 40:
How can we search a Hash Table for a value?
Hash the value you are searching for,
Look at that index,
{
If the cell has the value you are looking for, the value is present.
If the cell is empty, the value is not present.
} If the cell has a different value, look to the right and check again.
Chapter 40:
What is Rehashing?
In a hash table, if the hash of a value is taken, Rehashing is how to find the new location.
Chapter 40:
Why are Hash Tables useful?
They allow for efficient searching.
Chapter 40:
What common Data Type is implemented using a Hash Table?
Dictionaries.
Chapter 40:
What is a Dictionary?
An unordered collection of data where the values are referenced with a keyword instead of a location index.
Chapter 37:
What is an Abstract Data Type?
A logical description of how data is viewed.
The behaviour is defined by the type, but the implementation can be different.
Chapter 37:
What are four examples of Abstract Data Types?
Queues, Stacks, Trees, Graphs.
Chapter 37:
What kind of Abstract Data Type is a Queue?
FIFO.
First in first out.
New elements can only be added to the end of a Queue.
Elements can only be taken from the front of the Queue.
Chapter 37:
What is the difference between a Static Data Type and a Dynamic Data Type?
Dynamic Data Types have the ability to grow and shrink.
Static Data Types have a fixed size which must be stated on declaration.
Chapter 37:
What is a circular Queue?
When an arbitrary limit on a Queue has been reached, the last element can point back to the front of the queue, to reuse empty space at the front.
Chapter 37:
What is a Priority Queue?
A Queue where certain values may be placed further forward, and “jump the queue” or “cut in”.
Chapter 38:
What is a List?
An ordered collection of data values.
Data Types can be different for different indexes.
Data values can be repeated.
Chapter 38:
What is the difference between an Array and a List?
Arrays are static, meaning they must be declared with a size and cannot grow or shrink.
Arrays are declared with a data type that must be true for all of the values.
Lists are dynamic, meaning they can grow and shrink in size.
Lists can store different data types in different locations.
Both are ordered.
Chapter 38:
How do you insert an item into a list?
From the end of the list, back to the insertion index, copy List[x] to List[x+1].
This will push all of the values at the index and after forward one.
Then set the value of the index to the insertion value.
Chapter 38:
How do you delete an item from a list?
From the insertion index to the end of the list, copy List[x+1] to List[x].
This will push every value after the index back one.
Then set the value of the last index to Null.
Chapter 38:
What are Linked Lists?
Values are bound to pointers for other locations.
This means you can add new items to the end, change the pointers, and have it effectively be in the middle.
Chapter 39:
What kind of Abstract Data Type is a Stack?
LIFO.
Last in first out.
New elements can only be added to the top of a Stack.
Elements can only be taken from the top of the Stack.