Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

A Level Computer Science > 1.4.2 Data structures > Flashcards

1.4.2 Data structures Flashcards

1
Q

Describe a primitive data type

A

A data type which is assigned to a variable used to hold a single piece of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Describe a composite or compound data type

A

A data type which is assigned to a variable used to hold multiple related pieces of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Describe an abstract data type

A

A conceptual model that describes how data is stored and which operations can be carried out on them

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Describe what a data structure is

A

The implementation of an abstract data type in a program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Explain what a static data structure is

A

A set amount of memory locations / size to store data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain what a dynamic data structure is

A

Can group data, while also being able to grow in size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is an array data structure?

A

A data type that holds data that are usually related. It has a fixed size that cannot be changed during running.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a tuple data structure?

A

A data structure that cannot mutate, which contains multiple constants

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe a list data structure

A

A dynamic array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Describe a record data structure

A

A data structure which allows you to make your own data type consisting of different fields

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Describe a linked list data structure

A

A list data structure which stores data in the next free space, and links them together with pointers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a node, for a linked list, and what does it contain?

A

An individual element of the linked list

Contains the data item and the next address location

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are some advantages of a linked list?

A
  • Flexible structure - pointers can be changed to shape the ordering system
  • Can easily remove nodes, as very few pointers need to be changed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are some disadvantages of a linked list?

A
  • Slow to check through as it must be started at the beginning and then worked through
  • Hard to update with new nodes, as all previous nodes have to be checked and pointers moved to add the new item
  • Hard to find a specific item, as every node has to be gone through to find it
  • More storage space is required since the pointers also have to be stored
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Describe a linear queue data structure

A

FIFO. Pointers point to the start of the queue where items are removed, and to the end where items are added

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Describe a circular queue data structure

A

Functions the same as a linear queue, except it reuses the empty spaces at the front of the queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the advantage of a circular queue over a linear queue?

A

After elements are removed, the circular queue can reuse the space left behind

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Describe a priority queue structure

A

Each element has a priority value alongside the data, and it is all stored in priority order. This is similar to an ordered linked list.

A new element is added according to its priority value, and the highest priority element is removed first

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Describe a stack data structure

A

LIFO. The last item to be added to the stack is the first item to be removed.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the purpose of the peek() operation?

A

Returns the item at the top of a stack without removing it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the purpose of the push() operation?

A

Adds an element to the top of the stack

22
Q

What is the purpose of the pop() operation?

A

Removes an element from the top of a stack

23
Q

Describe a tree data structure

A

A hierarchical structure of data, stored as nodes, with parent nodes branching into children nodes.

24
Q

Define a node in a tree data structure

A

A unit for data, containing: a sub-tree pointer, the node’s data, and pointers to other nodes on the same level

25
Q

Define a parent and child for a tree data structure

A

Parent: the predecessor node to branching nodes

Child: a node branching from a predeceasing node

26
Q

Describe a binary search tree data structure

A

A dynamic data structure, which can change size during program running. It can have only 0, 1 or 2 branches from each node

27
Q

What is an advantage of binary search trees over standard root search trees?

A

Binary trees take a shorter time to search for a particular item than a rooted tree

28
Q

What are the 3 methods of traversing a binary tree?

A

Preorder traversal

Inorder traversal

Postorder traversal

29
Q

What are the features of a preorder traversal?

A

Is a ‘top down’ method

Can be used to duplicate the data to create an identical binary tree

30
Q

Describe a preorder traversal

A

Pointers are to the left of the node

  • Root visited first
  • Traverses left sub-tree
  • Traverses right sub-tree
31
Q

What are the features of an inorder traversal?

A

Outputs the data in ascending order

32
Q

Describe an inorder traversal

A

Pointers below the nodes

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

What are the features of a postorder traversal?

A

A ‘bottom up’ method

Used if data needs to be deleted from the tree

34
Q

Describe a postorder traversal

A

Pointers to the right of the node

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

What is a hash table?

A

An array structure with an associated hash function

36
Q

What is the process of hashing?

A

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
Q

What are two applications of hashing?

A

Speeding up data retrieval

Checking validity of data

38
Q

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

A

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

39
Q

How is hashing used to check the validity of data?

A

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
Q

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

A

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

41
Q

What are 3 features of a good hash algorithm?

A
  • 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
Q

What is a collision in the context of hashing?

A

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
Q

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

A

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
Q

What are some uses of hashing?

A

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
Q

Describe the structure of a graph

A

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

46
Q

Describe the difference between a directed and undirected graph

A

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

Undirected graph: no specific direction on an edge

47
Q

Describe the difference between a weighted and unweighted graph

A

Weighted: has weights/costs marked on each edge

Unweighted: has no additional edge values

48
Q

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

A
49
Q

How can a list be used to store a graph?

A
50
Q

How can a dictionary be used to store a graph?

A
51
Q

How can ordered pairs be used to store a graph?

A

A Level Computer Science (20 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions