Brainscape's Knowledge GenomeTM

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


See full index

A Level Computer Science > 4.2 Data Structures > Flashcards

4.2 Data Structures Flashcards

1
Q

Static vs Dynamic Data Structures
- when size is determined
- storage

A
  • static: storage size determined before program is run (fixed size)
  • dynamic: can change size during run time
  • static: can waste storage space is number of data items is small compared to size
  • dynamic: only take up amount of storage space required
  • dynamic: need memory to store pointer to next items
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Enumerated (definition)

A

In the form of a list

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

Arrays (2)

A
  • elements must be of the same data type
  • objects are mutable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Lists (3)

A
  • elements can be of different data types
  • objects are mutable
  • is a dynamic data structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Tuples (3)

A
  • elements can be of different data types
  • objects are immutable
  • more efficient than lists since are immutable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Text Files can only store

A

Strings

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

Advantage of Text Files

A

They can be created, altered or prepared independently from the program

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

Binary Files (3)

A
  • hard for human to understand
  • are directly compatible with the computer
  • tend to be more secure as without correct definitions would be difficult to convert data into meaningful information
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

CSV Files (4)

A
  • comma separated files
  • type of text file used to store a set of records
  • each record is stored on a single line
  • each field in the record is separated by a comma
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Types of Access of Files
- read
- write
- append
- read binary file
- write to binary file

A
  • r = read
  • w = write (overwrites entire file)
  • a = append
  • rb = read binary file
  • wb = write to binary file
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Queues
- Acronym
- Number of Pointers

A
  • FIFO (First In First Out)
  • 2 pointers: rear and front
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Linear Queues
- type of structure
- queue = empty if …
- disadvantage

A
  • static data structure
  • queue = empty if front > rear
  • dis: limited amount of space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Circular Queues
- definition
- what pointers store

A
  • queue which has a fixed amount of space but where the end of the queue is connected to the front
  • front points to element of array which should be removed next
  • rear points to last element added
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Priority Queues (2 + Enqueue)

A
  • when elements are assigned they are ordered according to some rule
  • each item is assigned a priority as it is added to the queue
  • enqueue: same as linear queue, except value is inserted into correct position according to a given priority
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Enqueue Algorithm

A
  • check if full (if rear + 1 = front)
  • if not full
    • increment rear by 1
    • add item at the location indicated by the value of rear pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Push Function + Algorithm

A
  • adds data pushed to top of stack
  • check isFull()
  • if not full
    • increment top pointer by 1
    • insert data at location indicated by the value of the top pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Stack
- type of structure
- acronym
- no. pointers

A
  • static data structure
  • LIFO (Last In First Out)
  • 1 pointer: top
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Dequeue Algorithm

A
  • check if empty (if front > rear)
  • if not empty
    • get item at location indicated by front pointer
    • increment value of front pointer by 1
  • return item
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Pop Function + Algorithm

A
  • removes data at top of stack and returns it
  • check isEmpty()
  • if not empty
    • get value at location indicated by the value of top pointer
    • reduce top pointer by 1
  • return value
17
Q

Peek Function + Algorithm

A
  • returns value at the top of stack without removing it
  • return stackarray[top]
18
Q

Test for Empty Stack AKA + Algorithm

A
  • known as stack underflow
  • if top == -1
    • return True
19
Q

Test for Full Stack AKA + Algorithm

A
  • known as stack overflow
  • if top == max
    • return True
20
Q

Method to Reverse the Order of a List Using a Stack

A
  • push all elements in list onto stack
  • for each element in stack:
    • perform pop function
    • store value returned in next available space in a list
21
Q

Method to Reverse the Order of a Queue Using a Stack

A
  • elements of queue are dequeued from queue
  • elements are then pushed onto stack
  • elements are popped off stack
  • elements are enqueued to queue
22
Q

Graph (definition)

A

Has a set of vertices and edges where each edge joins two vertices

23
Q

Labelled Graph (definition)

A

One that has its vertices associated with a label

24
Q

Directed Graph (definition)

A

Graph that consists of arcs and vertices where every arc connects two vertices and has a direction

25
Q

Weighted Graph (definition)

A

Graphs where every edge is given a weight

26
Q

Adjacency Matrix vs List

A
  • Use an adjacency matrix with dense graphs (many edges) to avoid searching through long lists to check for adjacency
  • Use an adjacency list with sparse graphs as it takes up less storage and lists are short so don’t take a long time to search for adjacency
27
Q

Tree (definition)

A

Connected undirected graph with no cycles

28
Q

A Tree with n vertices has

A

n-1 edges

29
Q

Rooted Tree (definition)

A

Tree in which one vertex has been designated as the root
- all edges and vertices stem from the root node

30
Q

Binary Tree (definition)

A

Rooted tree where each node has at most 2 children

31
Q

Rooted Graph (definition)

A

Graph where one of the nodes has been distinguished as a root

32
Q

Rooted Tree (definition)

A

Tree where one of the nodes has been distinguished as a root

33
Q

Assigning one of the nodes of a tree as a root allows us to

A

Talk about parents and children

34
Q

Hashing Algorithm (definition)

A

A mathematical calculation performed on search criteria to find its location

35
Q

Collision (definition) (aim) (resolution)

A
  • When the same index is produced for different values in a hash table
  • aim of a good hashing algorithm is to cut down collisions while optimising space needed
  • one collision resolution strategy is to use the next free space available
36
Q

Time Complexity of a Hash Table

A

Instant Time: O(1)

37
Q

Clustering (definition)

A

Where lots of values are close together in a hash table

38
Q

Process of Adding a Record to a Hash Table

A
  • a unique attribute from the record is used to position record into table
  • hash algorithm is applied to the unique attribute
  • record is inserted at the location indicated by the hash value of unique attribute
  • if an item is already at the location (i.e. a collision), the item is inserted into the next available location
39
Q

Vectors
- type of structure
- can be represented as

A
  • dynamic data structures
  • list of numbers, 1D array, dictionary
40
Q

Stack: Starting Positions of Pointers

A

top = -1

41
Q

Queue: Starting Positions of Pointers

A

rear = -1
front = 0

42
Q

Enqueue with Circular Queues

A
  • check if full (if rear + 1 = front)
  • if not full
    • increment rear by (rear+1) % MAX_SIZE
    • add item at the location indicated by the value of rear pointer

A Level Computer Science (13 decks)

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