Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computing > [Unit 1.4.2] Data Structures > Flashcards

[Unit 1.4.2] Data Structures Flashcards

data structures

1
Q

define “data structure”

A

collection of data organised for efficient processing

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

define “primitive data types”

A

single values (integers/floats)

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

define “compound data types”

A

combine primitive data types (records/dates)

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

what is a linear data structure

A

ordering data in a sequential order. each element is connected to the one before and after.

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

what is a non linear data structure

A

data organised with a hierarchy like a family tree

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

what are the two types of linear data structures

A

static:
fixed size, change content. memory allocated at compiler time

Dynamic:
change size, change content. memory allocated during run time as needed.

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

what are records

A

data structures consists of fixed number of attributes (fields/columns)

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

three similarities between records and OOP

A

-bundle related properties together
-define attributes (to manipulate data)
-can have multiple instances

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

four differences between records and OOP

A

-record is data structure. class is template for data structure
-classes have methods
-classes can change visibility of properties
-classes have inheritance

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

what are the features of an array

A

same data type
static
stored contiguously
mutable

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

what are the features of a list

A

different data types
dynamic
stored contiguously
mutable

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

what are the features of a tuple

A

different data types
static
immutable

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

what are the features of a linked list

A

dynamic
data does not have to be stored contiguously
each item is called a node

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

what two features is a node comprised of

A

data and pointer

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

what is the pointer in a node

A

contains the address of the next node

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

what does it mean if a pointer is null

A

end of linked list
node not linked to another (if one has been deleted)

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

what is the head pointer (linked lists)

A

points to location of first node

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

what is the free space pointer and what does it mean if it is null (linked lists)

A

indicates next free element (if null then list is full)

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

what is the tail pointer (linked lists)

A

indicates location of last node

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

what are the three types of linked lists

A

single linked
doubly linked
circular linked

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

what is a single linked list

A

navigation is forwards only

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

what is a doubly linked list

A

navigation can be forwards or backwards
(must have two pointers (previous&next))

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

what is a circular linked list

A

last node links to first node.
can be single linked or doubly linked.

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

differences between array and linked list (4)

A

accessing data faster in array
uses less memory per item in array
array is static data structure
slow to add/remove data in array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
how do you add a node to a linked list
-check free storage pointer is not NULL -traverse list to free node and add data -update pointer of previous node to new item -update pointer of new item to same as previous node used to point to -if list was empty update head pointer -update free storage pointer to next free location
26
how do you delete a node from a linked list
-check if list is empty (output error if yes) -traverse to node of item to delete -update pointer of deleted node to NULL -update previous node pointer to same as deleted item was -if deleted node was the first. update head pointer -update free storage pointer if required
27
how do you traverse a linked list
-check if list is empty (error if yes) -begin at node of head pointer -print -follow pointer to next node -repeat until pointer is NULL (end of list)
28
what is a queue
linear data structure that stores elements sequentially.
29
what does FIFO stand for?
first in first out
30
what are the two main operations performed on queues
enqueue (add to end) dequeue (remove from start)
31
what are the two types of pointers in a queue
front/head back/rear/tail
32
what happens if you enqueue a full queue
queue overflow error
33
what happens if you dequeue an empty queue
queue underflow error
34
what are some real life uses of queues
print queue CPU scheduling modelling situations like traffic jams
35
why are linear queues inefficient
they run out of space quickly. you could shuffle up each item after dequeue but this is inefficient and takes time on longer queues
36
what is a circular queue
front and rear end are connected requires less memory more efficient
37
what is a priority queue
each element has a priority
38
how does a priority queue work
when you add element. it is inserted ahead of lower priorities, but behind equal or higher priorities.
39
how do you enqueue an item
check if queue is full -print error message if it is increment rear pointer by 1 add element to location of rear pointer
40
how do you dequeue an item
check if queue is empty -print error message if it is take item at location of front pointer increment front pointer by 1
41
how do you enqueue an item in a circular queue
check if queue is full -print error message change rear pointer to (rear +1) MOD maxsize of queue add element to location of rear pointer
42
how do you dequeue an item in a circular queue
check if queue is empty -print error message take item at location of front pointer change front pointer to (front + 1) MOD maxsize of queue
43
what is a stack
linear data structure, stores elements sequentially
44
a stack is a LIFO. what does LIFO mean
Last in first out
45
is a stack: static or dynamic?
it can be static or dynamic
46
what does push() do
add item to top of stack
47
what does pop() do
remove item from top of stack
48
define "stack overflow"
when you try to push() a full stack
49
define "stack underflow"
when you try to pop() an empty stack
50
what are stacks used for
reversing order of set of data items used for calculations used for handling interrupts.
51
how do you push a stack
check if stack is full -print error message increment top pointer by 1 add element to location of top pointer
52
how do you pop a stack
check if stack is empty -print error message take element from location of top pointer decrease top pointer by 1
53
what are the features of a tree data structure
non linear data represented hierarchically nodes connected by edges each tree has a root node
54
define "node"
fundamental element of tree. contains data. may link to another node
55
define "root" in terms of a tree data structure
top most node in tree. no parent
56
define "parent" in terms of a tree data structure
node has one or more child nodes
57
define "child" in terms of a tree data structure
node that descends from another node
58
define "leaf" in terms of a tree data structure
node with no children
59
define "edge" in terms of a tree data structure
connection between two nodes. may also be called a pointer
60
define "subtree" in terms of a tree data structure
tree formed by a node and its descendants
61
define "binary tree"
special rooted tree where every node has, at most, two child nodes
62
define "Binary search tree" (BST)
binary tree where nodes are ordered allowing for efficient searching
63
what are the properties of a binary search tree
- nodes of left subtree are less than root node - nodes of right subtree are more than root node - each subtree is also a BST, has the same properties
64
what are the 3 things in every binary tree
data left pointer right pointer
65
what are the two types of tree traversal
depth first breadth first
66
what are the three types of depth first tree traversal
pre-order post-order in-order
67
how does pre order tree traversal work
visit root node traverse left subtree recursively in pre-order traverse right subtree recursively in pre-order
68
how does post order tree traversal work
traverse left subtree recursively in post-order traverse right subtree recursively in post-order visit root node
69
how does in-order tree traversal work
traverse left subtree recursively in in-order visit root node traverse right subtree recursively in in-order
70
define backtracking
undoing a step, returning to previous node after exploring all possible paths from the current node
71
how does breadth first tree traversal work
visit each node level by level typically left to right
72
how do you insert an item into a binary search tree
- check if full, output error if so - create new node with required data - if binary tree is empty the new node becomes first item. create start pointer - if it isn't empty: - start at root - if new node is less follow left pointer - if new node is more follow right pointer - repeat until pointer is null - if it is less set left pointer to new node - if it is more set right pointer to new node
73
how do you delete a leaf node in a binary search tree
- check if node to be removed is less or more than parent - if less change left pointer of parent to null - if more change right pointer of parent to null - add deleted node to free storage list
74
how do you delete a node with one child in a binary search tree
- check if node to be removed is less or more than parent - if less, update parent left pointer to point to only child - if more update parent right pointer to point to only child - add deleted node to free storage list
75
how do you delete a node with two children in a binary search tree
- find smallest value in right subtree and swap with deleted node - if there are no left nodes in right subtree, upshift subtree by one - delete leaf node (the new one that was swapped) - add deleted node to free storage list

Computing (9 decks)

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