Brainscape's Knowledge GenomeTM

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


See full index

A level OCR Computer Science > 1.4.2 Data structures definitions/info > Flashcards

1.4.2 Data structures definitions/info Flashcards

(b) (c)

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

What is a stack?

A

A data structure which follows a last in, first out (LIFO) structure
- holds an ordered, linear sequence of items

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

what is needed to keep track of a stack?

A

a pointer which points to the top of the stack

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

what is the operation to add an item to a stack?

A

push - adds an element to the top of a stack

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

what is the operation to remove an item from a stack?

A

pop - removes an element from the top of the stack

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

what is the peek operation?

A

returns a copy of the element on the top of the stack without removing it

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

what are the steps for the push operation?

A
  • check if the stack is full
  • add an item by incrementing the pointer by 1 and then inserting the item into the array at the pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what are the steps for the pop operation?

A
  • checks if the stack is empty
  • store the item at the top of the stack (at the index equal to the pointer)
  • reduce the pointer by 1
  • return the item
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what are the steps for the peek operation?

A
  • return the item at the top of the stack (at the index equal to the pointer)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what other functions can there be for a stack?

A

is_empty - checks if the stack is empty
is_full - checks if the stack is at maximum capacity when stored in a static structure

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

what is a static data structure?

A

a data structure of fixed size

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

what are the ways a stack can be implemented?

A
  • using a static array
  • using a dynamic linked list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what is a queue?

A

a data structure which follows first in, first out (FIFO) structure
- holds an ordered linear sequence of items

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

what is the operation to add an item to a queue?

A

enqueue - adds an element to the queue

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

what is the operation to remove an item from a queue?

A

dequeue - removes an element from the front of the queue

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

what is needed to keep track of a queue?

A
  • a pointer at the front
  • a pointer at the back/rear
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what other operations can a queue have?

A
  • is_empty - checks if the queue is empty
  • is_full - checks if the queue is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what are the steps for the enqueue operation? (for linear queues)

A
  • check if the queue is full
  • increment the back/rear pointer
  • add the item to where the back/rear is pointing to
  • check if this is the first item to be added to the queue (if the front pointer = -1) and if so, sets the front pointer to 0
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

what are the steps for the dequeue operation? (for linear queues)

A
  • check if the queue is empty
  • store the item at the front of the queue in a variable
  • increment the front pointer
  • return the item
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

what is a circular queue?

A

a queue which reuses the empty slots at the front of the queue when elements are dequeued

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

how does a circular queue work?

A
  • as items are enqueued, and the rear pointer reaches the last position, it wraps around to point at the start of the array
  • as items are dequeued, the front pointer will wrap around until it passes the rear pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

how is the enqueue operation adjusted for circular queues?

A
  • use an additional check to cycle back to the beginning if there is free space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

how is the dequeue operation adjusted for circular queues?

A
  • use an additional check to cycle to the beginning of the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what is a priority queue?

A

a queue where each element in the queue has a priority
when new elements are added into the queue, they are inserted ahead of those with a lower priority and behind those with equal priority.

24
Q

what is a dynamic data structure?

A

a data structure where the size can change at any time

25
Q

what is a graph?

A

an abstract data structure that can represent relationships between objects.

26
Q

what does a graph consist of?

A

nodes (hold the data)
edges (represent the relationships)

27
Q

what are neighbours in a graph?

A

when two nodes are connected by an edge

28
Q

what is the degree of a node?

A

the number of other nodes that a node is connected to

29
Q

what is a loop?

A

an edge that connects a node to itself

30
Q

what is a path?

A

a sequence of nodes that are connected by edges

31
Q

what is a cycle?

A

a closed path (starts and ends at the same node with no repeats)

32
Q

what are some applications of graphs?

A
  • social networking
  • transport networks
  • the internet
  • the world wide web
33
Q

what is an undirected graph?

A

a graph where you can traverse in either direction between nodes

34
Q

what is a directed graph?

A

a graph where the edges have a direction

35
Q

what is a weighted graph?

A

a graph that has values associated with the edges

36
Q

what is a tree?

A

a graph that:
- has no cycles
- must be connected

37
Q

what does a tree having no cycles mean?

A

there is only one possible path between any two nodes

38
Q

what is the root of a tree?

A

the start node for traversals
rooted trees have roots

39
Q

what is a branch?

A

a path from the root to an end point

40
Q

what is a leaf?

A

an end point on a tree
- a leaf node has no other nodes attached to it except 1

41
Q

what is the height of a tree?

A

equal to the number of edges that connect the root node to the leaf node furthest from it

42
Q

what is a binary tree?

A

a tree which:
- has a root node
- every node must have at most two child nodes

43
Q

what is a binary search tree?

A

a rooted tree where the nodes are ordered

44
Q

how does the binary search tree algorithm work?

A
  • set the current node to the root node
  • use a while loop to check if we have reached a leaf node
  • if the data in the current node is greater than the search item, we go to the left
  • if the data in the current node is less than the search item, we go right
  • if the data in the current node = the search item, return true
  • if a leaf node is reached, return false
45
Q

what is a breadth first traversal?

A

a traversal which goes along the horizontal layers of a graph/tree

46
Q

how does a breadth first traversal work?

A
  • visit the root node
  • visit all nodes attached to the root node
  • move to the first node attached to the starting node and repeat, visiting the nodes attached to this node
47
Q

what does a breadth first traversal use to store nodes?

A

a queue stores visited nodes

48
Q

what are the different types of depth first traversal?

A

pre-order
in-order
post-order

49
Q

how does a pre-order traversal work?

A

visit, left, right

50
Q

how does an in-order traversal work?

A

left, visit, right

51
Q

how does a post-order traversal work?

A

left, right, visit

52
Q

what is used to store previous nodes in a depth first traversal?

A

a stack

53
Q

what is a linked list?

A

a dynamic data structure which has links to sort the data

54
Q

how is an item added to an unordered linked list?

A
  • insert data into the next available free node
55
Q

how is an item added to an ordered linked list?

A
  • create a new node
  • traverse the list to find the correct position
  • set the pointer of the new node to the pointer of the pointer of the current node
  • set the pointer of the current node to the pointer of the new node
56
Q

what is the free pointer used for?

A

it is used to point to the next available free location

57
Q

what are the steps to search a linked list?

A
  • set current to the head pointer
  • use a while loop to continue code until the end of the linked list
  • check if the current node = data
  • return true if true
  • increment current to the next pointer if not
  • return false if the while loop breaks

A level OCR Computer Science (25 decks)

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