Brainscape's Knowledge GenomeTM

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


See full index

A-LEVEL COMP SCI > DATA STRUCTURES > Flashcards

DATA STRUCTURES Flashcards

1
Q

What is an array?

A

a variable that can contain more than 1 data item (a variation of a list)

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

What is the difference between lists and arrays?

A

lists are not contiguous whilst arrays are

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

What does contiguous mean?

A

all the data is stored together 1 element after the other

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

What is a record data structure?

A
  • a collection of related fields (a variable
  • each field in a record can have a different data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a tupule?

A

a list that cant be changed once created (immutable)

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

What are the key properties of a list?

A
  • mutable
  • items can be changed or replaced
  • can store more than 1 data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the key properties of an array?

A
  • mutable
  • items can be changed or replaced
  • can only store 1 data type
  • length cant be changed (static)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the key properties of a tuple?

A
  • immutable
  • items cant be changed or replaced
  • can store more than 1 data type
  • length cant be changed (static)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a linked list?

A
  • a data structure constructed from nodes and pointers
  • provides a foundation upon which other structures can be built such as stacks, queues, graphs and trees
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What identifies the first node in a linked list?

A

a start pointer

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

What does each node contain in a linked list?

A
  • data
  • a pointer to the next node
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How are doubly linked lists made?

A

adding an extra pointer which causes the nodes to point to the previous and next items

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

How are circular linked lists made?

A

making the last node point to the 1st node

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

How are doubly circular linked lists made?

A

each node in a circular linked list has an additional pointer pointing to the previous item

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

How can a linked list be implemented?

A
  • using an array
  • using objects
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the applications of linked lists?

A
  • used by OS managing a processor to store process blocks in a ready state
  • used by image viewers to switch between previous and next images
  • used by music players to store tracks in a playlist
  • used by web browsers to navigate backwards and forwards
  • used for hash table collision resolution as an overflow
  • used for maintaining a file allocation table of linked clusters on secondary storage
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What operations can be performed on a linked list?

A
  • add (adds a node to the linked list)
  • delete (removes a node from the linked list)
  • next (moves to the next item in the list)
  • previous (moves to the previous item in a doubly linked list)
  • traverse (a linear search through the linked list)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a graph?

A

a data structure consisting of nodes/vertices and pointers/edges

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

How does a graph differ from a linked list and binary tree?

A

each vertex can have more than 2 edges and point to any vertex in the data structure

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

What is a directed graph?

A

a graph in which the edges point in 1 direction

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

What is an undirected graph?

A

a graph in which the edges don’t point in a specified direction

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

What does it mean if a graph is weighted?

A

each edge has a value representing a relationship between the vertices

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

How can graphs be stored?

A
  • typically stored as objects/using a dictionary (known as adjacency lists)
  • can also be stored as an array (known as an adjacency matrix) (a 1 represents an edge existing between 2 vertices)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What are the applications of a graph?

A
  • mapping road networks for navigation systems
  • storing social network data
  • resource allocation in operating systems
  • representing molecular structures and geometry
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is abstraction?

A

using only the necessary detail and discarding unnecessary detail

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

What is a stack?

A
  • a data structure
  • items are pushed onto the top of a stack when they are added to it and popped off the top when they are deleted from it
  • it is also possible to peek at the top of a stack without deleting it
  • LIFO structure
27
Q

What is a LIFO structure?

A
  • last in, first out structure
  • last item pushed onto the stack is the first item to be popped off the stack
28
Q

What points to the node at the top of a stack?

A

stack pointer

29
Q

What is a stack overflow?

A

an attempt to push an item onto a full stack

30
Q

What is a stack underflow?

A

an attempt to pop an item off of an empty stack

31
Q

How are stacks implemented?

A
  • often using an array
  • can be created using object orientated techniques
32
Q

What are stacks used for?

A
  • used by processors to track the flow of programs
  • performing depth-first searches on graph data structures
  • keeping track of user inputs for undo operations
  • backtracking algorithms
  • evaluating mathematical expressions without brackets (using a shunting yard algorithm and reverse polish notation)
33
Q

What operations can be performed on a stack?

A
  • push (adding an item to the top of a stack)
  • pop (removing an item from the top of a stack)
  • peek (returning the value from the top of the stack without removing it)
34
Q

What is a queue?

A
  • a linear data structure
  • items are enqueued at the back of the queue and dequeued from the front
  • its also possible to peek at the front of the queue without deleting it
  • FIFO structure
35
Q

What is a priority queue?

A

new items joining at the front of the queue

36
Q

What is a FIFO structure?

A
  • first in, first out structure
  • first item enqueued is the first item to be dequeued
37
Q

What is a tail pointer?

A

the back pointer in a queue which always points to the last item

38
Q

What is a head pointer?

A

the front pointer in a queue which always points to the first item

39
Q

What is a queue overflow?

A

an attempt to enqueue an item in a full queue

40
Q

What is a queue underflow?

A

an attempt to dequeue an item from an empty queue

41
Q

How can queues be implemented?

A
  • using an array
  • using object orientated techniques
42
Q

What is the problem when implementing a queue using an array?

A

the array will quickly run out of space as both the back and front pointers are moving in the same direction as items are added and removed from the queue

43
Q

How is the problem that occurs when using an array to implement a queue solved?

A

cycle the back pointer to the front of the array when it reaches the end (creating a circular queue)

44
Q

Why are circular queues useful?

A
  • ideal if you want to restrict the no. of items and have a known memory footprint
  • particularly useful in game design where no. of sprites on screen affects framerate
45
Q

What are the applications of a queue?

A
  • process scheduling
  • transferring data between processors and printer spooling
  • performing breadth-first searches on graph data structures
46
Q

What operations can be performed on a queue?

A
  • enqueue (adding an item to the back of the queue)
  • dequeue (removing an item from the front of the queue)
  • peek (returning the value from the front of the queue without removing it)
47
Q

What is a tree?

A

a data structure consisting of nodes and pointers

48
Q

What is the root node of a tree?

A
  • the node at the top of a tree
  • connects to 0, 1 or more child nodes
49
Q

What are nodes at the bottom of the tree called?

A

leaf nodes

50
Q

How are nodes connected in a tree?

A

pointers/edges

51
Q

What is a subtree?

A

a set of nodes and edges from any single node down through all of its descendants

52
Q

What are the applications of a tree?

A
  • storing and managing file and folder structures
  • implementations of the A* pathfinding algorithm
  • storing and manipulating any form of hierarchical data that requires a parent node to have 0, 1 or more child nodes (eg: family tree/corporate structure)
53
Q

What is a binary tree?

A

a tree where each node can only have 0/1/2 pointers with each pointer connecting to a different node

54
Q

How can binary trees be implemented?

A

can be stored as arrays/objects

55
Q

What are the applications of binary trees?

A
  • database applications where efficient searching and sorting is required without moving items which is slow
  • wireless networking and router tables
  • OS scheduling processes
  • Huffman coding (used for compression algorithms (eg: JPEG and MP3))
  • cryptography
56
Q

What is a hash table?

A
  • a data structure that implements an associative array (a dictionary). In an associative array, data is stored as a collection of key-value pairs.
  • the position of the data within the array is determined by applying a hashing algorithm to the key - a process called hashing. The hashing algorithm is called a hash function
57
Q

Why do collisions occur in hash tables?

A

2 items cant occupy the same position in the hash table

58
Q

How is the chance of a collision minimised in a hash table?

A

the hash table is significantly large to minimise chances of the algorithm returning the same value for more than 1 item (collision)

59
Q

What are properties of a good hashing function?

A
  • calculated quickly
  • result in as few collisions as possible
  • use as little memory as possible
60
Q

How are collisions from hashing functions resolved?

A
  • repeatedly check next available space in hash table until an empty position is found and store the item there (known as open addressing). to find the item later, the hashing function delivers the start position from which a linear search can then be applied until the item is found (known as linear probing)
  • using a 2 dimensional hash table. it is then possible for more than 1 item to be placed at the same position (known as chaining)
  • using a second table (overflow table)/linked list for collisions which can then be searched sequentially
61
Q

What is a disadv of linear probing?

A
  • prevents other items from being stored at their current location in the hash table
  • also results in clustering (several positions being filled around common collision values)
62
Q

What is rehashing?

A

the process of finding an alternative position for items in a hash table

63
Q

What are applications of a hash table?

A
  • used in situations where items in a large data set need to be found quickly (eg: file systems linking a file name to the path of the file, identifying key words in a programming language during compilation)
64
Q

What operations can be performed on a hash table?

A
  • add
  • delete
  • retrieve (retrieves an item from a hash table using its hash value)

A-LEVEL COMP SCI (12 decks)

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