Brainscape's Knowledge GenomeTM

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


See full index

Computing - A Level OCR (Paper 1) > Data Structure > Flashcards

Data Structure Flashcards

1
Q

What is an attribute?

A

-Column in a table (like fields in databases)

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

How does a record store data?

A
  • Stored by attribute
  • Accessed by attribute
  • Unordered
  • Attributes and structure for record need to be set up in advance
  • More friendly in use but more complex to set up
  • Data can be modified added or deleted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a list?

A
  • Ordered set of data organised by an index
  • Data accessed through index value (starting at 0)
  • Requires little or no set up
  • Easier to set up but less user friendly in use
  • Data can be modified added or deleted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a Tuple?

A
  • Immutable list (cannot be changed once it is set up)

- structure exactly like a list

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

What is a 1D array?

A
  • very similar to list but also has defined scope (number of elements)
  • Defines a set of variables under a single descriptor with an index, names(0), names(1) etc etc
  • can access and manipulate the data by its indexed address
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a 2D array?

A
  • Effectively a table
  • data is referred to by its point in a table, (5,5)
  • data is accessed by its point in a table
  • Data can be altered
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a 3D array?

A

-same as 1D and 2D but also has a third coordinate (X,Y,Z)

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

What is a stack?

A
  • LIFO
  • data added to (pushed) and removed from (popped) the top
  • implemented using pointers. Pointer increases values when data added and decreases when data removed
  • error message generated when stack full or empty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Queues?

A
  • FIFO
  • Data does not move forward in the queue but two pointers ,start and end, track the data in the structure
  • If item is popped from the queue the start pointer increases in value
  • If item is pushed into the queue the end pointer increase in value
  • A circular queue can be formed eg; when two locations are free (5 and 1) with 5 being the max location the next items will be added into 5 then 1
  • If start pointer = end pointer error message should generate.
  • If start pointer = 1 and end pointer = max error message should generate
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a linked list?

A
  • Allows us to store data on various criteria
  • Does not modify data stored in memory (you can sort for certain things but it will not reposition these items in memory)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How does a linked list function?

A
  • Uses pointers to point to the next item in a certain order
  • end of list when pointer = 0
  • possible to have more than one pointer at the same time
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the free storage pointer?

A

-points to the first of these available spaces

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

How do you add data to a linked list?

A

1-Store data at the location indicated by free storage pointer
2-Alter the pointer to the next free storage space
3-ID where in the list the data should be inserted
4-set the pointer for the item that preceded it to the new data item
5-Update the pointer for the new data item to that previously stored in the item that preceded it

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

How do you remove items from linked lists?

A
  • pointer in the preceding node is set to the value of the pointer in the item to be removed
  • that value of the pointer in the item that has been removed will be added to the free pool
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How do you traverse a linked list?

A

Algorithms in photos

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

What does each node on a tree have to have?

A
  • sub-tree pointers that point to any subtrees for that node
  • data accosted with that node
  • pointers to other nodes at the same level
18
Q

What is a binary tree?

A
  • specific kind of tree, each node can only have two children
  • each node contains; left and right pointers and data
19
Q

What is preorder traversal of trees?

A
  • start at root node
  • traverse left sub-tree
  • traverse right sub-tree
20
Q

What is in-order tree traversal?

A
  • Traverse the left sub tree
  • visit the root node of the left
  • traverse right sub tree
  • visit root node of the right
21
Q

What is post order tree traversal?

A
  • traverse left sub tree
  • traverse right sub tree
  • return to root node
22
Q

Why would we use pre and post order traversal?

A
  • provide a means of writing expressions without needing brackets
  • postorder traversal of a tree is one method of converting between infix (human syntax) and reverse polish
23
Q

What is reverse polish? What is it good for?

A
  • postorder (postfix) notation

- able to utilise the stack effectively when processing an expression

24
Q

What is the processes of reverse polish?

A
  1. If the next symbol is an operand load it to the stack
  2. If the next symbol is an operator, pop the last two items off the stack, perform the operation and place the result in the stack
25
Q

What is a graph?

A
  • collection of data nodes and the connections between them
  • nodes are referred to as vertices
  • connections are edges
  • edges can be directional (making a directed graph)
  • if edges are bi-directional then its an undirected graph
  • numbers represent measurements between then
26
Q

What are graphs used for?

A
  • in real life they can map road networks
  • in computer they can map internet networks
  • you can work out the shortest distance between them or the best routes between them
27
Q

What is depth first traversal of graphs? Algorithm?

A
  • algorithm in book
  • visit all the nodes attached to a node connected to the starting node before progressing to the second node attached to the starting node. (Working dow branches of a tree)
  • uses a stack
28
Q

What is breadth first traversal of graphs? Algorithm?

A
  • algorithm in book
  • visit all the nodes attached directly to the starting node first
  • uses a queue
29
Q

What are hash tables used for?

A
  • accessing data of a more random nature

- constructed from 2 parts; array (where data is stored) and a mapping function (the hashing function)

30
Q

What are hash functions? How would we generate one?

A

-applied to s key item or filed within the data and generates an address where the location of the data can be found
-many ways to do this. One way to is to take a string as an input and return a hash value composed of the sum of the ASCII characters that compose the input string MOD the size of the table
-

31
Q

What is a problem with hash functions? What is one way this can be avoided?

A
  • may not always generate unique values
  • collisions can occur
  • sperate chaining = data elements are stored in linked lists rather than being stored directly within the array. When data hashes to a value, it is stored in the linked list at that index in the array. No limit on length hence collisions no longer an issue
32
Q

How do we find data in a hash table?

A
  • hash the data we are searching for
  • go to that location in the table
  • look down the list originating from that location
  • check if data is there
33
Q

What are the main features of a hash function?

A
  1. Hash value is fully determined by the data being hashed
  2. Hash function uses all the input data
  3. Data is uniformly distributed across the entire set of possible hash values
  4. Function generates very different values for similar data

Computing - A Level OCR (Paper 1) (15 decks)

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