1.4.2 Data structures Flashcards Preview

A Level Computer Science > 1.4.2 Data structures > Flashcards

Flashcards in 1.4.2 Data structures Deck (51)
Loading flashcards...

What are the features of an inorder traversal?

Outputs the data in ascending order


Describe an inorder traversal

Pointers below the nodes

  • Traverses the left sub-tree
  • Visits the root
  • Traverses the right sub-tree


What are the features of a postorder traversal?

A 'bottom up' method

Used if data needs to be deleted from the tree


Describe a postorder traversal

Pointers to the right of the node

  • Traverses left sub-tree
  • Traverses right sub-tree
  • Visits the root


What is a hash table?

An array structure with an associated hash function


What is the process of hashing?

When the data being stored (the key) is inserted into the hashing function and a hash value is output

The hash value relates to a specific location in the hash table


What are two applications of hashing?

Speeding up data retrieval

Checking validity of data


How would you search for a particular record in a hash table?

The record would be inserted into the hashing function, and then the output is the location in which you need to search


How is hashing used to check the validity of data?

If data is sent to a new location, the hash value is sent too

Once the data arrives, the hash function is carried out again, and if the new and old hash values don't match, then the data is invalid


What is the advantage of a hash table when locating a record in a file?

Using the hash function means there will be only one location outputted that needs to be searched


What are 3 features of a good hash algorithm?

  • Generates a uniform spread of unique indexes to avoid collisions
  • Produces hash values quickly, thus being fast
  • Is complex, thus reducing the chance of collisions, with unique hash values


What is a collision in the context of hashing?

A collision occurs when the hash function produces the same hash value for different keys, thus giving the same memory location in the hash table to both keys


What are two methods of dealing with collisions in the context of hashing?

Open addressing (closed hashing): inserts a colliding key into the next available memory location, known as rehashing


Closed addressing (open hashing): apply a linked list to a memory location where a collision occurs. This is an overflow list, which holds all subsequent keys which collide with the data already stored in this location


What are some uses of hashing?

Searching a database: can quickly find data in a database

Sending files: used to validate the data sent

Storing passwords safely: hashes the user's password before storing it


Describe the structure of a graph

A graph is composed of multiple vertices, each connected to others by edges


Describe the difference between a directed and undirected graph

Directed graph: the edges have a direction, the way of travel

Undirected graph: no specific direction on an edge


Describe the difference between a weighted and unweighted graph

Weighted: has weights/costs marked on each edge

Unweighted: has no additional edge values


How can an adjacency matrix be used to store a graph?


How can a list be used to store a graph?


How can a dictionary be used to store a graph?


How can ordered pairs be used to store a graph?