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...
31

What are the features of an inorder traversal?

Outputs the data in ascending order

32

Describe an inorder traversal

Pointers below the nodes

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

33

What are the features of a postorder traversal?

A 'bottom up' method

Used if data needs to be deleted from the tree

34

Describe a postorder traversal

Pointers to the right of the node

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

35

What is a hash table?

An array structure with an associated hash function

36

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

37

What are two applications of hashing?

Speeding up data retrieval

Checking validity of data

38

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

39

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

40

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

41

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

42

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

43

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

44

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

45

Describe the structure of a graph

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

46

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

47

Describe the difference between a weighted and unweighted graph

Weighted: has weights/costs marked on each edge

Unweighted: has no additional edge values

48

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

49

How can a list be used to store a graph?

50

How can a dictionary be used to store a graph?

51

How can ordered pairs be used to store a graph?