Brainscape's Knowledge GenomeTM

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


See full index

EDUQAS Computer Science: Component 1 > 1.1 > Flashcards

1.1 Flashcards

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

Data Structure

A

A data structure is a group / set / collection of related data items / elements

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

Data Structure Advantages

A

Convenient / best way of organising data relating to a real problem
An efficient way to deal with various elements as one item

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

Data Structure Disadvantage

A

More Complex to program

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

Array

A
  • An array is a data structure which is a set of data elements of the same data type
  • Elements are accessed using an index
  • Has a pre determined number of elements
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

2D Array

A

A 2D array is a grid-like structure which can hold both rows and columns of the same data type.

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

Record

A
  • A record is a set of data items related to a single individual / entity
  • It can contain data of different data types
  • Can be processed as one item by a computer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Linked List

A
  • Nodes in a list contain the data itself and address of the next node (pointer)
  • First element is head node, list has to be traveresed from start.
  • Dynamic structure (can grow/shrink)
  • Last node points to null
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Searching Linked List

A

UNORDERED
Can’t be terminated until all items have been inspected

ORDERED
Can be terminated when a value greater than search is found

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

Linked List Advantages

A
  • New items can be inserted without rearranging the other elements
  • Uses memory more efficiently as is dynamic and can shrink/grow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Linked List Disadvantages

A
  • More complex to program
  • Can only be accessed in a linear manner
  • Use more memory as store pointer aswell as data
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Stack

A
  • Data Structure where items can only be added and removed from the top
  • Last in first out (LIFO)
  • Push (add), Pop (remove)
  • Limited access, can only be accessed from the top
  • Can be used as a recursive data structure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Stack Underflow and Overflow

A

UNDERFLOW
Attempt to POP an empty stack

OVERFLOW
Attempt to PUSH a full stack

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

Binary Tree

A
  • Each node has a max of 2 children
  • Everything on the left is less than or equal to the root
  • Everything on the right is greater than the root
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Binary Tree nodes contain…

A
  • Data
  • Left Node
  • Right Node
  • Leaf nodes (no children) point to null
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Delete a Binary Tree node

A

DELETE ROOT
Replace root with highest value from left side of tree

1 CHILD
Replace node with child

2 CHILDREN
Replace node with child at left pointer

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

Pre Order Traversal Use

A

Clone a tree e.g. make a copy of files in a hierarchical file structure

ROOT -> LEFT -> RIGHT

17
Q

In Order Traversal Use

A

Outputting node content in order

LEFT -> ROOT -> RIGHT

18
Q

Post Order Traversal Use

A

Deleting all of the node contents

LEFT -> RIGHT -> ROOT

19
Q

Binary Tree Comparisons with Array and Linked List

A

ARRAY ADVANTAGE
Faster to search/ add (in order) a value

ARRAY DISADVANTAGE
More complex to program tree

LINKED LIST ADVANTAGE
Faster to access data in tree

LINKED LIST DISADVANTAGE
Binary tree has 2 pointers, list has 1

20
Q

Hash Table

A
  • Provides direct access to an item via its index and performance is not affected by the number of items stored
  • Index is a numeric value calculated from the value
  • Data can be retrieved using the key/index and hashing algorithm to return the value
  • Stores data in an associative array
21
Q

Hashing Table: Chaining

A
  • Original table has dynamic data strucutre for each location
  • After collision new node on linked list is created
  • Slow down finding data
  • Doesnt require prior knowledge of how many elements
22
Q

Hashing Table: Progressive Overflow

A
  • If location is occupied, use the next available location
  • wrap to start if end is reached
  • easy to maintain
  • not very efficient (could search through whole file)
  • Records are likely to be stored close to the calculated location
  • If blank is reached, not in file
  • Less total storage space
  • Fixed max capacity of the main file
23
Q

Hashing Algorithm: Overflow

A
  • Seperate pre-allocated file
  • Flag original block
  • Move data into overflow area
  • Overflow area uses linear seach
  • Re organisation/ bigger file will eventually be needed
24
Q

Queue

A
  • Processing order is first in first out (FIFO)
  • 2 pointers, front and rear (rear points to next empty position)
  • Enqueue: insert a value
  • Dequeue: remove a value from front

EDUQAS Computer Science: Component 1 (9 decks)

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