Brainscape's Knowledge GenomeTM

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


See full index

A-Level Computer Science > 14: Data Structures > Flashcards

14: Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What is meant by a static data structure?

A

Structure size cannot change at runtime

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

What is meant by a dynamic data structure?

A

Structure size can change at runtime

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

What is meant by an immutable data structure?

A

Structure/data cannot be changed at runtime

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

What is meant by a mutable data structure?

A

Structure/data can be changed at runtime

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

What is a record?

A

A collection of related fields. A field is a variable, and 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
6
Q

What is meant by continguous?

A

All the data is stored together, one element after the other

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

Are arrays contiguous?

A

yes

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

Are lists contiguous?

A

no

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

What are the features of an array? (5)

A
  • static
  • mutable
  • ordered collection of items
  • items can be changed or replaced
  • can only store one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the features of a list? (5)

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

What are the features of a tuple? (5)

A
  • static
  • immutable
  • ordered collection of items
  • items cannot be changed or replaced
  • can store more than one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a stack?

A
  • A data structure that is essential for the operation of a computer
  • Items can be pushed onto the top of the stack when added to it and popped off the top when they are deleted from it
  • Known as a LIFO structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is meant by a LIFO structure?

A
  • Last-in-first-out

- The last item to be pushed onto the stack must also be the first item to be popped off

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

What is the purpose of a stack pointer?

A

Always point to the node at the top

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

What is a stack overflow?

A

Any attempt to push an item onto a full stack

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

What is a stack underflow?

A

Any attempt to pop an item off an empty stack

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

How is a stack implemented?

A
  • using an array

- object oriented techniques

18
Q

What are stacks used for?

A
  • keeping track of user inputs for Undo operations

- Backtracking algorithms - e.g. pathfinding maze solutions

19
Q

What operations can be performed on a stack?

A
  • Push: Adding an item to the top of the stack
  • Pop: Removing an item from the top of the stack
  • Peek: Returning a value from the top of the stack without removing it
20
Q

What is a queue?

A
  • A linear data structure
  • items are enqueued at the back of the queue and dequeued from the front of the queue
  • Known as a FIFO structure
21
Q

what is a FIFO structure?

A
  • First-in-first-out

- First item in the queue is the first item to be dequeued

22
Q

What is the purpose of the back pointer of a queue?

A

Always points to the last item

23
Q

What is the purpose of the front pointer of a queue?

A

Always points to the first item

24
Q

What is a queue overflow?

A

An attempt to enqueue an item in a full queue

25
Q

What is a queue underflow?

A

An attempt to dequeue an item from an empty queue

26
Q

How are queues implemented?

A
  • an array

- object-oriented technique

27
Q

What are the applications of a queue?

A
  • Process scheduling

- Transferring data between processors and printer spooling

28
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
29
Q

What is a linked list?

A

a data structure that provides a foundation upon which other structures can be built, such as stacks, queues, graphs and trees

30
Q

How is a linked list constructed?

A
  • nodes and pointers
  • A start pointer identifies the first time
  • each node contains data and a pointer to the next node
  • data in lists can be stored anywhere in memory, with pointers indicating the address of the next item
31
Q

How can you make a doubly linked list?

A

By adding an extra pointer, nodes can point to the previous and next items

32
Q

How do you create a circular linked list?

A
  • making the last node point to the first node
33
Q

How do you implement linked lists using an array?

A
  • being static data structures, arrays are stored contiguously in memory, requiring the use of an index register to determine where a specific index is in relation to a book address
34
Q

What are the applications of a linked list?

A
  • operating systems managing a processor to store process blocks in a ready state
  • Image viewers to switch between previous and next images
  • music players to store tracks in a playlist
  • web browsers to navigate backwards and forwards
35
Q

What operations can be performed on a linked list?

A
  • Adds: 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
36
Q

What are the advantages of linked lists?

A
  • Dynamic data structure, so no need to give initial size
  • No memory wastage as size can change at runtime
  • Good for linear data structures, such as stacks and queues
  • Easy to implement insertion and deletion operations
37
Q

What are the disadvantages of linked lists?

A
  • pointers need to be stored, which requires more memory
  • Direct access to an element is not possible so searching can be time consuming
  • Reverse traversal is only possible in doubly linked lists
38
Q

How do you add an item to a linked list?

A
  1. Check there is free memory for a new node. Output an error if not
  2. Create a new node and insert data into it/insert data in the node indicated by the free storage pointer
  3. If the linked list is empty:
    - The new node becomes the first item. Create a start pointer to it
  4. If the new node should be placed before the first node:
    - The new node becomes the first node. Change the start pointer to it
    - The new node points to the second node
  5. If the new node is to be placed inside the linked list:
    - Start at the first node
    - If the data in the current node is less than the value of the new node:
    —- Follow the pointer to the next node
    —- Repeat from step 5b until the correct position is found or the end of the linked list is reached
    - The new node is set to point where the previous node pointed
    - The previous node is set to point to the new node
  6. Update the free pointer to the next available storage space
39
Q

How do you delete an item from a linked list?

A
  1. Check if the linked list is empty and output an error if there is no start node
  2. If the first item is the item to delete, set the start pointer to the next node
  3. If the item to delete is inside the linked list:
    - Start at the first node
    - If the current node is the item to delete then the previous node’s pointer is set to point to the next node
    - Follow the pointer to the next node
    - Repeat from step 3b until the item is found or the end of the linked list is reached
  4. Update the free pointer
40
Q

How to traverse a linked list

A
  1. Check if the linked list is empty
  2. Start at the node the start pointer is pointing to
  3. Output the item
  4. Follow the pointer to the next node
  5. Repeat from step 3 until the end of the linked list is reached

A-Level Computer Science (25 decks)

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