1.4 Data Types and Structures Flashcards

Question

What is a gigabyte?

Answer 1

Base-16 0-9 and A-F

Answer 2

RBG = representing colours MAC addresses Memory dumps

Answer 3

Easier to read and interpret Fewer digits to represent the same value Compared to binary, less likely that digit written down incorrectly

Answer 4

Convert into binary Split into nibbles Convert each nibble to hex

Answer 5

87 = 01010111 = 57

Answer 6

210 = 11010010 = D2

Answer 7

Convert all terms to denary (as per a nibble) Times those numbers by 16 to the power of the nibble they are in minus 1 (if it's the second nibble, times by 16^1) Add numbers together

Answer 8

B9 = 176 + 9 = 185

Answer 9

2CA = 512 + 192 + 10 = 718

Answer 10

Sign and magnitude Two's complement

Answer 11

Changing left most bit (most significant bit) to represent if negative or not 0 = positive 1 = negative

Answer 12

Changing left most bit (most significant bit) to present either 0 or -128 1 = -128 0 = 0

Answer 13

Calculate number as positive binary value Keep rightmost 1 and everything to the right of it the same Flip all other value

Answer 14

103 = 01100111 -103 = 10011001

Answer 15

1 + 0 = 1 1 + 1 = 0 carry 1 0 + 0 = 0 1 + 1 + 1 = 1 carry 1

Answer 16

99 = 01100011 103 = 01100111 01100011 + 01100111 ------------------- 11001010 ------------------- 11 111 = 11001010

Answer 17

Convert numbers to two's complement Flip number you're subtracting to a negative Add numbers together

Answer 18

75 = 01001011 36 = 00100100 -36 = 11011100 01001011 + 11011100 ------------------ 100100111 ------------------- 1 11 = 00100111

Answer 19

Decimal point doesn't move Values before fixed point represent whole numbers Values after fixed point represent fractions Can be expressed using Two's complement

Answer 20

Underflow - when number is too small to be represented

Answer 21

Decimal place can be moved Enables greater range of numbers and greater precision of numbers More efficient way of storing binary numbers

Answer 22

Mantissa Exponent

Answer 23

Where the decimal point should move to

Answer 24

Number being represented

Answer 25

Between the two leftmost bits

Answer 26

If first number is 1, fill with 1s If first number is 0, fill with 0s

Answer 27

Standard form that should be used to represent numbers Using normalisation, make sure digit after the binary point is SIGNIFICANT

Answer 28

Where the number is too large a positive or negative to store Crashes

Answer 29

When the number is too small to be able to store Crashes

Answer 30

Check if exponents are the same. If not, increase smaller exponent to match higher one When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by Add together just the mantissas using normal binary addition rules

Answer 31

Check if exponents are the same. If not, increase smaller exponent to match higher one When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by Negate the value to subtract Add together just the mantissas using normal binary addition rules

Answer 32

Standard collection of characters and the bit patterns used to represent them to allow computers to be able to communicate and exchange text efficiently

Answer 33

American Standard Code for Information Interchange

Answer 34

Each character encoded with binary string of 7 bits

Answer 35

Error-checking/correction purposes

Answer 36

Uses more bits to store a character than ASCII, meaning a wider range of characters can be stored

Answer 37

Can support languages with alphabet character sets larger than 26 Uses up to 32 bits to represent each character and can be used to represent special symbols Supports over 4 billion possible codes

Answer 38

Allows the programmer to work with sets of bits through logical bitwise operations In both high and low level languages, used to perform a logical operation on each individual bit of a binary number

Answer 39

Directly supported by the processor, making them fast and efficient Works on a single bit (or set of bits) within a binary string Often used in low-level languages to manipulate the contents of registers or memory locations

Answer 40

AND OR XOR NOT

Answer 41

Used to move binary digits Can be used for arithmetic operations

Answer 42

Bit pattern that's been defined by a programmer, allowing specific bits in a piece of data to be tested or altered Binary string used in conjunction with a logical bitwise operator to identify or manipulate a single bit (set of bits) within another binary string

Answer 43

Turn off/select bits

Answer 44

Turn on/select bits

Answer 45

Reverse/toggle/complement/inverse

Answer 46

Divide or multiply binary values

Answer 47

Multiplying and dividing by a factor of 2 Encryption/decryption Data collision detection in a network Compression algorithms Routing packets of data Peripheral communication protocols Graphics manipulation

Answer 48

1. moving all the bits of the number one place to the left 2. discarding the most significant bit 3. putting a 0 into the empty place on the right

Answer 49

1. moving all bits of the number one place to the right 2. discarding the least significant bit 3. putting a 0 into the empty place on the left

Answer 50

Arithmetic shift

Answer 51

Most significant bit is not shifted Remaining bits are shifted Sign of number is preserved and empty places are padded

Answer 52

Empty places are padded with 0

Answer 53

Empty places are padded with 0

Answer 54

Empty spaces are padded with 0

Answer 55

Empty places are padded with 1

Answer 56

No bits are lost Bits are shifted out at one end into the other end of register

Answer 57

In cryptography, cyclic shift of a code will always yield another code (Twofish cipher makes extensive use of cyclic shift because they are very fast operations) Cyclic left shift used in some operations in modular arithmetic

Answer 58

12 x 6 = (12 x 4) + (12 x 2)

Answer 59

Ordered sequence of elements stored under a single identifier Data is immutable

Answer 60

Cannot be changed

Answer 61

Returning multiple items from a function Passing multiple values to a subroutine but grouped under a single parameter Often used when returning records from a database

Answer 62

Static data structure Can only store data of the same data type

Answer 63

Length doesn't change during run time

Answer 64

Lets you use the equivalent of rows and columns Each element in an array becomes a separate array Each coordinate needs two values

Answer 65

name[x,y] name[x][y]

Answer 66

Abstract data type LIFO Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)

Answer 67

Last In First Out

Answer 68

Data is placed on top and removed from the top

Answer 69

push(data) pop() peek() is_empty() is_full()

Answer 70

Adds an element to the top of the stack

Answer 71

Removes an element from the top of the stack and returns it

Answer 72

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

Answer 73

Checks whether a stack is empty

Answer 74

Checks whether a stack is at maximum when stored in a static structure

Answer 75

Holds return addresses when subroutines are called (recursion) Undo in word Back button in web browser In calculations to ensure correct order of precedence When dealing with interrupts (current process and values put on stack to allow ISRs to be completed)

Answer 76

Attempting to push onto a stack that's full

Answer 77

Attempting to pop from a stack that's empty

Answer 78

Only need a single pointer to the top of the stack Store maxSize of stack in variable to determine if stack full Use top pointer or equivalent to keep track of top of stack If stack empty, top = -1

Answer 79

Abstract data type FIFO Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)

Answer 80

First In First Out

Answer 81

Data is placed at the rear/back of the queue and removed from the front

Answer 82

enqueue(data) dequeue() is_empty() is_full()

Answer 83

Adds an element to the back of the queue

Answer 84

Removes an element form the front of the queue and returns it

Answer 85

Checks whether the queue is empty

Answer 86

Checks whether a queue is at maximum capacity (if size of queue is constrained)

Answer 87

Simulation Print queue Priority queue (each element in queue has a priority and are ordered by priority?

Answer 88

Two pointers needed Front pointer points to first item, initialised at 0 Rear pointer to last item, initialised at -1 Queue is empty when rear < front

Answer 89

Reuses the empty slots at the front of the array that are caused when elements are dequeued As items enqueued and rear pointer reaches last position of the array, wraps around to start of array (as long as not full) As items dequeued, front points wraps around until passed rear pointer (meaning queue is empty)

Answer 90

rear = (rear + 1) % maxSize front = (front + 1) % maxSize

Answer 91

Data structures consisting of a fixed number of variables (FIELDS)

Answer 92

Each field has an IDENTIFIER and a data type Each field can have a DIFFERENT DATA TYPE

Answer 93

nameOfRecord.fieldname

Answer 94

Abstract data type DYNAMIC data structure used to hold a sequence Other data types can be implemented using a linked list (stacks, queues) Items in the sequence are in NON-CONTIGUOUS DATA LOCATIONS Composed of nodes Items stored in an order

Answer 95

Size of the list can change during runtime

Answer 96

The data (may be complex data structure) A pointer (index) of the next node

Answer 97

Start pointer (identifying first node in the list) nextFree pointer (showing index of next free space in the array)

Answer 98

1. follow the start pointer to the first node. Examine data of this node 2. if pointer of that node is not Null, follow pointer to next node 3. repeat until end of list is reached (pointer of current node is Null)

Answer 99

cp = start while cp != None: print(list[cp][0]) cp = list[cp][1]

Answer 100

1. start by checking if linked list is already full 2. check if adding into an empty list 3. checking if adding into the start of a list

Answer 101

Data can be easily added or removed in an order without needing to move lots of other data items Can be used to implement more abstract data types (queues, stacks, binary trees)

Answer 102

Traversal of a linked list is very slow

Answer 103

Contains pointers to the next node and the previous node

Answer 104

Abstract data type Used to represent complex, non-linear relationships between objects Consists of nodes (vertices) connected by edges (or arcs)

Answer 105

When graphs are connected by an edge

Answer 106

Number of nodes that it's connected to

Answer 107

An edge that connects a node to itself

Answer 108

Sequence of nodes connected by edges

Answer 109

Closed path Path that starts and ends at the same node with no node visited more than once

Answer 110

Social networking - nodes are individual people and edges represent that two people are acquaintances Transport networks - nodes are towns and edges trainlines connecting two towns Internet - nodes are routers and edges represent that two routers are connected World Wide Web - nodes are webpages and edges represent that two pages are linked

Answer 111

Edges don't have arrows so the graph can be traversed in both directions

Answer 112

Edges have arrows denoting direction of graph traversal Edges don't have arrows going both ways, they have two arrows if bidirectional

Answer 113

The edges don't have values associated with them

Answer 114

Edges have a value associated with them Values could represent distance between places, time taken to travel, amount of network traffic

Answer 115

Each row and column represents a node The item at [row, column] indicates a connection Unweighted graphs have a 1 at each edge

Answer 116

Convenient to work with Adding an edge is simple

Answer 117

Spare graph with not many connections (edges) will leave most cells empty, wasting a lot of memory space

Answer 118

List of nodes created and each node points to a list of adjacent nodes Weighted graph represented as a dictionary of dictionaries

Answer 119

Visiting all the nodes

Answer 120

Depth first traversal Breadth first traversal

Answer 121

Solutions where the answer is far from the node Decision-based tree system

Answer 122

1. push first node onto the stack and mark this node as visited 2. repeat the following until stack is empty a. visit next unvisited node b. push onto stack and mark as visited c. if no further unvisited connected nodes, pop from stack

Answer 123

Answer is closer to the node

Answer 124

1. push first node onto queue and mark as visited 2. repeat the following until all connected nodes to current node are marked as visited a. visit next unvisited node b. push onto queue and mark as visited 3. repeat following until queue is empty a. pop node from queue b. repeated following until all connected nodes to the current node are marked as visited i. visit next unvisited node ii. push onto queue and mark visited

Answer 125

Common abstract data type - should not be used as generalised abstract data structure Connected, undirected graph with no cycles which is used for searching Ideally, BUILD ONCE, TRAVERSE OFTEN

Answer 126

Binary trees Binary search trees Expression trees

Answer 127

Start node for traversals If tree has a root, called a rooted tree

Answer 128

Path from the root to an end point

Answer 129

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

Answer 130

Tree with one node designated the root Root commonly situated in diagrams above other nodes Nodes connected by parent-child relationships Node can have any number of children

Answer 131

Node that comes directly before another adjacent node (considered the child)

Answer 132

Rooted trees Each node has a max of 2 child nodes

Answer 133

In compilers to build syntax trees Within routers to store routing tables

Answer 134

To speed up searching

Answer 135

Nodes ordered to optimise searching Rooted tree Nodes of left subtree have values lower than root Nodes of right subtree have values higher than root

Answer 136

The data (may be primitive or more complex object) Left pointer to a child Right pointer to a child

Answer 137

Pre-order In-order Post-order

Answer 138

Post order

Answer 139

Visit root, traverse left subtree, traverse right subtree

Answer 140

Traverse left subtree, visit root, traverse right subtree

Answer 141

Traverse left subtree, traverse right subtree, visit root

Answer 142

Remove the node

Answer 143

Remove that node Link child to the parent node of the node removed

Answer 144

Find a node that will preserve search tree properties and put it in the place of the deleted node Node with the next largest key

Answer 145

Quickly retrieve data from a large data set Enabling efficient searching and maintaining of the hash table (adding, updating, deleting)

Answer 146

Use key value pairs Key generated from data that needs to be stored and then put through hash function/algorithm producing an address, which is the address in the array where data should be stored When retrieving data, same process followed and data can be instantly retrieved from address produced by hash function no matter size of array

Answer 147

Free space

Answer 148

Applying a hashing algorithm (or hash function) to a key

Answer 149

Using an array because have to able to access each position of the array directly, which is done by specifying index of position within the array

Answer 150

Positions within an array in a hash table, each used to store data (can be single piece or more complex object like record)

Answer 151

Generated from data that needs to be stored Must be stored as part of, or alongside, the data

Answer 152

Must be big enough to store all data but not so large that you waste table

Answer 153

When speed of insertion, deleting and looking up is a priority

Answer 154

Algorithm that converts hash key to hash values Good hash function essential for effective performance of hash table Must be designed and tested to minimise number of possible collisions

Answer 155

Always produce same hash value for same key Perform uniform distribution of hash values, meaning that every value has equal probability of being generated Minimise clustering, which arises when many different keys produce the same hash value Be very fast to compute

Answer 156

Use hash function to generate index of position in the array that will be used to store data Key must be stored as part of, or alongside, data

Answer 157

When two or more different keys produce the same hash value Greater the LOAD FACTOR, greater chance of collisions

Answer 158

How full the hash table is

Answer 159

Cannot store two sets of data at the same location

Answer 160

Linear probing Chaining

Answer 161

When key creates hash value that references a position that is already occupied, place data in next free position in hash table Can probe sequentially or use an interval until empty bucket is found (SKIP FACTORING) Each time this is done, increase likelihood of further collisions (clustering)

Answer 162

Hash key to generate index value Examine indexed position to see if key (stored together with data) matches key of data looking for If no match, check each location that follows (at appropriate interval) until matching record found If reach empty bucket without finding matching key, data not in hash table

Answer 163

Significantly reduces efficiency of using hash table for searching Worst case - have to inspect every position of the array Why it's important to design hash table to have extra capacity so hopefully algorithm will find free position not far from correct place

Answer 164

Using linked lists

Answer 165

Instead of storing actual data in hash table, store pointer to location where data stored Each data item stored as node with key value, data and pointer to next node First value to be stored will have Null pointer as only item in list When collision, pointer for next node at that location updated to point to new node Creates chain of nodes whose keys resolve to the same hash value

Answer 166

Hash key to generate index value Examine indexed position to get pointer to node at head of list Examine key of node to see if matches key looking for If not node looking for, follow linked list until find node look for If end of list reached without finding matching key (or head pointer is Null), data not in hash table

Answer 167

Every key hashes to same value and have to carry out linear search

Answer 168

Over time, items added and deleted from hash table If hash table starts to fill up or large number of items in wrong place, performance of hash table will degrade

Answer 169

New hash table is created (larger if needed) Key for each item in existing table rehashed and item inserted into new hash table If new table larger, hashing algorithm modified to generate larger range of value Opportunity to review overall effectiveness of hash function and review how collisions handled

Answer 170

All hashing algorithms involve mod function at some point as hash address has to be range of table addresses Mid square Folding method

Answer 171

Items to be deleted must be replaced with dummy item or marker When searching for item which hashes to that spot, if not found, search will continue until it's found or free space located If new item is to be added and address contains dummy item, will replace dummy

Answer 172

Fundamental component of a digital circuit Each gate has one or more inputs and produces single output that depends on the inputs Multiple can be combined to make complex circuits to carry out processing

Answer 173

Multiple logic gates combined

Answer 174

Determined by voltage that flows around the system High voltage = 1/True Low voltage = 0/False

Answer 175

Looks like a D Both inputs have to be true for the output to be true

Answer 176

Y = A ∧ B

Answer 177

Looks like an umbrella Either inputs must be true for the output to be true

Answer 178

Y = A ∨ B

Answer 179

Looks like a triangle with a dot on the end Reverses the input

Answer 180

OR gate with an additional line Either inputs but not both must be true for output to be true

Answer 181

Y = A ∨ B But with OR symbol underlined

Answer 182

NOT AND OR

Answer 183

Shows all possible inputs and outputs from a logic gate or circuit Inputs can be expressed in any order

Answer 184

(A ∧ B) V ¬(D ∧ E)

Answer 185

Version of a truth table for a Boolean expression that's laid out in a way that makes it easier to simplify

Answer 186

Sizes of groups must be to the power of 2 (2, 4, 8) Groups should be as large as possible Every 1 must be included in a group Groups can overlap each other Groups can wrap around sideways and top to bottom

Answer 187

Manipulated algebraically to form simpler expressions that implement the same logic

Answer 188

Allow simpler circuit to be produced with fewer logic gates Reduce cost of circuit Reduce amount of heat generated Reduce processing time

Answer 189

Conjunction

Answer 190

Disjunction

Answer 191

Exclusive disjunction

Answer 192

The same as

Answer 193

Either logical function AND or OR may be replaced by the other, given certain changes to the equation

Answer 194

¬(A v B) ≡ ¬A ^ ¬B ¬(A ^ B) ≡ ¬A v ¬B

Answer 195

Allows for the multiplying or factoring out of an expression

Answer 196

Term outside the brackets doesn't appear inside the brackets Operator is different

Answer 197

X ^ (Y v Z) ≡ (X ^ Y) v (X ^ Z) X v (Y ^ Z) ≡ (X v Y) ^ (X v Z)

Answer 198

Allows for removal of brackets from an expression and the regrouping of variables

Answer 199

Term outside the brackets doesn't appear inside the brackets Operator is the same

Answer 200

X ^ (Y ^ Z) ≡ (X ^ Y) ^ Z ≡ X ^ Y ^ Z

Answer 201

Two negatives make a positive

Answer 202

¬¬A ≡ A

Answer 203

The second term inside the bracket can always be eliminated and absorbed by the term outside the bracket

Answer 204

Term outside the brackets appears inside the brackets Operators must be different

Answer 205

X v (X ^ Y) ≡ X X ^ (X v Y) ≡ X X v X ^ Y ≡ X

Answer 206

X ^ 0 ≡ 0 0 ^ X ≡ 0 X ^ 1 ≡ X X ^ X ≡ X X ^ ¬X ≡ 0

Answer 207

X v 0 ≡ X 0 V X ≡ X X v 1 ≡ X X v X ≡ X X v ¬X ≡ 1

Answer 208

(A v B) ^ (B v ¬B) (A v B) ^ 1 (A v B)

Answer 209

(A ^ B ^ ¬C) v (A ^ ¬C) D = A ^ ¬C (D ^ B) v D D A ^ ¬C

Answer 210

¬B ^ (A v B) (¬B ^ A) v (¬B ^ B) (¬B ^ A ) v 0 ¬B ^ A

Answer 211

Elemental sequential logic circuit that can store on bit and flip between two states, 0 and 1

Answer 212

Synchronous sequential circuit that can be used to store the value of single binary digit Has internal loop, allowing the previous output value to be stored

Answer 213

Data signal (D) Clock signal

Answer 214

Changes at D make no difference to output

Answer 215

Value of input D will appear at output Q

Answer 216

If there are changes in the data during the period when the clock signal is high, output at Q will chance in line with D, which might not be a desirable feature of the circuit

Answer 217

Introduces delay in processing the clock signal D is only processed at rising edge of each signal change from the clock On rising edge of each clock signal, state of D is accepted at output Q (updated to reflect this Once clock signal input goes low, state of circuit won't change and will continue to output (thus store) whatever value was already present on its output

Answer 218

Synchronising change of state of flip flop circuits

Answer 219

Creating registers Shift operations (multiplication and division) Intermediate storage needed during arithmetic operation Static RAM

Answer 220

Faster and more expensive than regular dynamic RAM, which must be periodically refreshed Typically used for cache memory which DRAM used for main memory

Answer 221

Circuit that performs the addition of two bits Takes input of two bits (A and B) and outputs the sum (S) and the carry (C)

Answer 222

Only has two inputs so cannot use the carry from a previous addition as a third input to a subsequent addition Can only add 1-bit numbers

Answer 223

Combines two half-adders Three inputs of A, B and carry bit Cin Two outputs of S and Cout

Answer 224

To add numbers together where each has multiple bits