Data Structures Flashcards
What is a tree?
A graph with no cycles
What is in-order traversal?
Left node, root, right node
What is pre-order traversal?
Root, left node, right node
What is post-order traversal?
Left node, right node, root
How do gateways differ from routers?
Gateways allow for networks of different types to be connected, routers only connect networks of the same type
What is the domain name system?
DNS is used to translate URLs into IP addresses
What is hashing sued for?
To read and write data to and from a large data structure
What is a hashing algorithm?
Ah algorithm that is applied to data to provide a numerical value that is used as an index in the data structure
What are two identical keys called?
Synonyms
What is the name given to the process during which two identical keys are produced?
Collisions
What is the most common way of handling collisions?
To store the value in the next available memory location
What is the most common hashing algorithm?
Diving the key by the number of available memory locations and using the remainder as the index
What is the process of folding?
Splitting a value into equal components, adding them together, and using the remainder when divided by the number of available memory locations as the index
What is collision resolution used for?
To reduce the number of collisions when a hash table starts to get full
How does collision resolution work?
Rehashing is a common collision resolution used to fill remaining memory locations
