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

array

A

An array allows you to store multiple items of the same data type under a shared common name.

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

Arrays can store data of the same data type contiguously in memory. This means…

A

… random access to all element is available via its direct index.

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

Limitations of arrays:

A
  • They can only store one data type

- They’re a static data structure (their scope is pre-determined)

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

record

A

an un-ordered data structure which is accessed through an attribute. It can store many different data types.

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

What are pythons versions of arrays?

A

Lists and tuples

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

Tuples

A

Tuples are lists that cannot be edited and is said to be immutable.

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

immutable

A

structure and data cannot be changed at run time.

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

mutable

A

structure and data can be changed at run time.

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

Static data structure

A

size of the structure cannot change at run time

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

Dynamic data structure

A

size of the structure can change at run time.

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

Stack data structure

A

A stack is known as a LIFO, a single pointer is used to point to the top item of the stack, when a new item is pushed onto the stack the pointer is incremented. When an item is popped off the stack the pointer decrements to point to the new top of the stack.

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

LIFO

A

last in first out - the last item you push to the top of the list is the first item you pop off the stack.

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

Queue data structure

A

A queue is known as a FIFO structure. A pair of pointers is used to point to the front and back of the queue. If an item is popped from the queue the front pointer points to the item being popped. If an item is pushed onto a queue the tail pointer increments by one and points to the new end of queue.

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

FIFO

A

first in first out - because the new items get pushed to the back of the queue and new items get popped from the front of the queue.

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

Algorithm for insertion into a stack:

A
  1. Check to see if the stack is full
  2. If the stack is full report error and stop
  3. Increment the stack pointer
  4. Insert new data item into location pointed to by the stack pointer and stop
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Algorithm for deletion/fetching from a stack:

A
  1. Check to see if the stack is empty
  2. If the stack is empty report an error and stop
  3. Copy the data item in location pointed to by the stack pointer/ delete the data item
  4. Decrement the stack pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Algorithm for insertion into a queue:

A
  1. Check to see is the queue is full
  2. If the queue is full report an error ad stop
  3. Insert new data item into location pointed to by the head pointer
  4. Increment the head pointer and stop
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Algorithm for deletion/fetching from a queue:

A
  1. Check to see if the queue is empty
  2. If the queue is empty report an error and stop
  3. Copy data item in location pointed to by the tail pointer/ delete the data item
  4. Increment tail pointer and stop
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

linked lists

A

A list of data together with a set of links to sort the data. Data is stored in the order its input and pointers are used to link the data into the desired order.

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

uses of linked lists

A
  1. Implementing undo functionality
  2. Dealing with browser cache
  3. Helping with operating system job queues
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Adding data from linked lists:

A
  1. Store the data at the location indicated by the free storage pointer
  2. Alter the free storage pointer to the next free storage space
  3. Set the pointer for the item that will precede it to the new data item
  4. Update the pointer for the new data item to that previously stored in the item the preceded it (i.e. the next data item)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Removing data from linked lists:

A
  1. If the item to remove is in the first position
    a. Then update starting pointer value of item you want to delete and update all the pointers
  2. Else if the item is in any other position
    a. Update the pointer value in the preceding node from the one you want to delete to the value of the pointer in the item to be removed and all the succeeding data items pointers
  3. Update the free storage
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Traversing data from linked lists:

A
  1. Set the pointer to the start value
  2. Repeat:
    a. Go to the node
    b. Output the data at the node
    c. Set the pointer to the value of the next item pointer at the pointer
    d. until pointer = 0/null
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Searching for an item in a linked list:

A
  1. Set the pointer to the start value
  2. Repeat:
    a. Go to node (pointer value)
    b. If the data at the node is the search item
    i. Then Output the data and stop
    c. Else
    i. Set the pointer to the value of the next item pointer at the node
    d. Until pointer = 0
  3. Output data not found
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Benefits of Hash tables

A

Speed of lookup, deletion and insertion of items is fast

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

hash table

A

an array which is coupled together with a hash function. The value from the hash function (hash value) maps the initial key to a fixed index in the hash table.

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

collision

A

the same hash value is given by two different keys.

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

collision solution

A
  • Storing the key in the next available space

- adding a linked list to the location where the hash value is repeated

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

clustering

A

when there is a collision and the key is stored in the next available space increasing the likelihood of collisions.

30
Q

solution clustering

A

combine hashtable with linked lists as overflow spaces

31
Q

Searching an item in a hash table:

A
  1. Feed the key to the hash function
  2. Go directly to array index (HashValue)
  3. If the value is equal to the value that you’re searching for then output the value
  4. Else follow the linked list in sequence until you find the value and output the value
32
Q

Inserting an item in a hash table:

A
  1. Feed in key to the hash function
  2. Go directly to the array index (HashValue)
  3. If the location is empty then insert the value
  4. Else follow the linked list in sequence until a free space in found and insert the value
33
Q

Deleting an item in a hash table:

A
  1. Feed in key to hash function
  2. Go directly to array index (HashValue)
  3. If the value is equal to the value you’re searching for then mark as empty
  4. Else follow the linked list in sequence until you find the value then mark as empty and update the free pointer in the linked list.
34
Q

uses of tuples

A

useful for accessing data that must not be changed

35
Q

list

A

an ordered data structure accessed through an index. the have no predefined scope and can be edited during run time.

36
Q

differences between one-dimensional arrays and list

A

arrays have a defined scope

37
Q

hash function

A

A hash function is code which takes in data called a key and outputs a value (hash value).

38
Q

multi-dimensional

A

an array containing one or more arrays.

39
Q

What does a node in a linked link contain?

A

the data and a reference to the next node

40
Q

graph

A

a set of edges/arcs connecting vertices/nodes

41
Q

Possible uses of graphs:

A
  1. Navigation Systems
  2. Data Transmission
  3. Web page links
  4. Social media trends
42
Q

dense graph

A

A graph which has more edges in relation to vertices

43
Q

sparse graph

A

A graph which has few edges in relation to vertices

44
Q

digraphs

A

has one or more edges that have an arrow indicating you can only go in one direction

45
Q

tree

A

hierarchical data structure with data related to the data above it in the tree.
a simple connected graph with no cycles

46
Q

arcs on a tree

A

branches

47
Q

node at the top of the tree

A

root node

48
Q

nodes lower than the root node

A

children

49
Q

nodes with no sub-nodes

A

leaf-nodes or terminal nodes

50
Q

binary tree

A

Tree structure where each node can only have two branches left or right

51
Q

What do the nodes on a binary tree contain

A

left pointer, data, right pointer

52
Q

depth first traversing uses a

A

stack

53
Q

breadth first traversing uses a

A

queue

54
Q

depth first traversing

A

follows one path down to a child node, it the visits this then backtracks to the next level then moves down to the next child node. Once all the child nodes from one branch have been visited it visits all the nodes on the next layer up.

55
Q

breadth first traversing

A

It starts at the root node, and visits all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.

56
Q

Inserting items into a binary search tree:

A

look at each node starting at the root. If the new value is less than the value at the node, move left otherwise move right. Repeat this for each node arrived at until there is no node. Insert a new node at this point and enter the data.

57
Q

Algorithm for insertion into a binary tree:

A
  1. If tree is empty enter data item at root and stop; Current node = root
  2. Else repeat:
    a. If new data item is less than value at current node go left, else go right.
    b. Current node = node reach (null if no node)
    c. Until current node is null
  3. Create new node and enter data
58
Q

different traversal methods

A

preorder
inorder
postorder

59
Q

Depth first algorithm

A
  1. PUSH the first node onto the stack
  2. Repeat:
    a. push each node onto the stack until a child node is reached
    b. visit the node which is the lowest you can reach
    c. if no node to visit pop off the stack
  3. Until stack is empty
60
Q

Breadth first algorithm

A
  1. PUSH the first node into the queue
  2. mark as visited
  3. REPEAT:
    a. visit all unvisited nodes connected to the first node
    b. push nodes onto the queue
  4. until all nodes visited
  5. REPEAT:
    a. POP next node from queue
    b. REPEAT:
    i. visit unvisited nodes connected to current node
    ii. PUSH nodes onto quue
    c. until all nodes visited
  6. until queue empty
61
Q

Preorder

A
  1. starts at root
  2. traverses the left sub tree
  3. traverses the right sub tree
62
Q

In order

A
  1. Traverses the left sub tree
  2. visits the root
  3. traverses the right sub tree
63
Q

Postorder

A
  1. Traverses the left sub tree
  2. traverses the right sub tree
  3. return to the root node
64
Q

preorder dot

A

dot left

65
Q

inorder dot

A

dot below

66
Q

post order dot

A

dot right

67
Q

beneficial characteristics of hashing algorithms

A
  • quick to calculate
  • minimizes the collisions
  • provides a smaller output than input
68
Q

similarities / differences between array and linked list

A
  • linked list is dynamic but array is static
  • an array can have an element accessed directly whereas a linked list needs to be traversed until the desired element is found
  • contents of array stored contiguously in memory whereas for linked lists its just in the order inputted
69
Q

use of visualisation in data structures

A

a graph is an abstract data structure which is actually an array. However, it easier to visualise and understand a graph making the coding easier to tackle.

70
Q

Uses of stacks in computer systems

A
  • Temporarily storing the contents of registers while handling an interrupt
  • Storing return addresses (during subroutine calls)
  • Traversing a Graph data structure
  • Passing parameters
  • Reversing the order of a set of data
71
Q

error when you try and add a data item to an already full structure

A

overflow

72
Q

typical uses of graphs

A
  • mapping data trasnmission
  • Webpage links
  • social media trends

A level Comp Sci (15 decks)

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