CS 1.4 Data Types Structures Boolean Algebra

Name the five primitive data types

Integer, real (floating point), character, string, Boolean

What is casting, and give an example of why it might be needed?

Converting one data type to another, e.g. converting user input (usually a string like "12") into an integer so a numerical comparison like "is this value below 20" can be performed

What is a bit, and what is a byte?

A bit is the smallest unit of digital information, either 0 or 1; a byte is a group of 8 bits

What does each column in an 8-bit binary number represent, from right to left?

Powers of 2: 1, 2, 4, 8, 16, 32, 64, 128 (i.e. 2^0 up to 2^7)

What is the Most Significant Bit (MSB) used for in signed binary numbers?

It indicates whether the number is positive (MSB = 0) or negative (MSB = 1)

How does sign and magnitude representation work?

The MSB represents the sign (1 = negative, 0 = positive), and the remaining bits represent the magnitude (size) of the number as normal binary

What is the method for converting a positive denary number to two's complement?

Convert the absolute value to binary as normal (no change needed since it's positive)

What is the method for converting a negative denary number to two's complement?

Take the binary representation of the positive (absolute) value, invert all the bits (0s become 1s and 1s become 0s), then add 1

Why is two's complement preferred over sign and magnitude for arithmetic?

Calculations (especially addition and subtraction) on two's complement numbers are less computationally intensive/more straightforward than sign and magnitude

What is the consequence of using a sign bit (in either sign & magnitude or two's complement) on the maximum value that can be stored?

The maximum size of the number that can be stored is halved, since one bit is used for the sign rather than the magnitude

What is overflow in binary arithmetic, and when does it occur?

Overflow occurs when the sum of two binary numbers exceeds the number of bits available to store the result, which can incorrectly flip the sign bit and produce an incorrect result

How is binary subtraction typically performed using two's complement?

Convert the number being subtracted into its two's complement (invert the bits and add 1), then add this to the other number using normal binary addition, discarding any overflow bit beyond the given number of bits

What is hexadecimal, and why is it used instead of binary?

A base-16 number system (0-9 then A-F); it's more concise (one hex digit represents 4 binary bits/a nibble), easier for humans to read/write, and less error-prone to communicate than long binary strings

Give two practical uses of hexadecimal

Any two of: debugging, configuring hardware devices, cryptographic algorithms, defining colours (e.g. in web design/CSS)

How do you convert a binary number to hexadecimal?

Split the binary number into groups of 4 bits (nibbles) starting from the right, then convert each nibble to its hexadecimal value

What are the two main components of a floating point binary number?

The mantissa (holds the significant digits/precision of the number) and the exponent (controls how far the binary point is shifted, scaling the number)

What does it mean for a floating point binary number to be normalised?

The mantissa starts with 01 (for positive numbers) or 10 (for negative numbers), immediately after the sign bit — this ensures a consistent, unambiguous format

Why is normalising floating point numbers useful?

It ensures a consistent format for representation and makes arithmetic and comparisons between floating point numbers more straightforward

What must be true before adding or subtracting two floating point numbers?

Both numbers must have the same exponent — this may require shifting the mantissa of one number and adjusting its exponent to match the other first

What happens to a floating point number's exponent if its mantissa needs to be shifted right during normalisation after an arithmetic operation?

The exponent is incremented (increased) to compensate for the mantissa being shifted right

What is a logical shift, and what are the two types?

Moving all the bits in a binary number left or right by a specified number of positions; the two types are left shift and right shift

What is the effect of a single logical left shift on an unsigned binary number's value?

It doubles the value (equivalent to multiplying by 2)

What is the effect of a single logical right shift on an unsigned binary number's value?

It halves the value (equivalent to integer division by 2)

What is a mask in the context of bitwise manipulation?

A binary number used in bitwise operations to isolate, set, clear, or toggle specific bits in another binary value, acting like a filter

How does a bitwise AND operation work with a mask?

The result bit is 1 only if both the corresponding bit in the original number AND the mask are 1; otherwise the result is 0 — used to isolate/clear specific bits

How does a bitwise OR operation work with a mask?

The result bit is 1 if either the corresponding bit in the original number OR the mask is 1; otherwise the result is 0 — used to set specific bits to 1

How does a bitwise XOR operation work with a mask?

The result bit is 1 only if exactly one of the corresponding bits (in the number or the mask) is 1, but not both; used to toggle/flip specific bits

What is a character set, and why is it needed?

A list of all characters and their associated binary code, standardising how binary values map to characters so different systems interpret them consistently

How many bits does standard ASCII use, and how many characters can it represent?

7 bits, representing 128 distinct characters (an 8-bit extended version exists, representing 256 characters)

Give two limitations of ASCII

Any two of: limited to 128 characters (mainly English), not suitable for multilingual/non-English text, no provision for modern symbols/emoji

How does Unicode address the limitations of ASCII?

It uses a much larger bit range (up to 32 bits depending on encoding), allowing it to represent a huge variety of characters from different languages, scripts, and symbols including emoji

What is the trade-off between ASCII and Unicode?

ASCII is more storage-efficient (fewer bits per character) but can only represent 128 characters; Unicode can represent far more characters (including international text and emoji) but requires more storage

What is an array, and what are its key characteristics?

An ordered, fixed-size (static) collection of elements that can only store one data type, with elements accessed directly by index

When is an array an appropriate data structure to use?

When you need a fixed-size collection with random access to elements by index, and don't need to frequently resize, insert, or remove elements in the middle

What is a record, and give an example use case

A single entity made up of a group of related fields (potentially of different data types), e.g. a row in a database representing one student's ID, name, and grade

What is the key difference between a list and an array?

A list is dynamic (can change size, elements can be non-contiguous in memory, and can hold multiple data types), whereas an array is fixed-size, contiguous, and holds only one data type

What is a tuple, and how does it differ from a list?

An ordered, immutable set of values of any type — unlike a list, once created its elements cannot be added, removed, or changed

Give the pseudocode operation used to add a new value to the end of a list, and one used to insert at a specific position

append(value) adds to the end; insert(position, value) inserts at a given position

What is a linked list, and how does it differ structurally from an array?

A dynamic data structure holding an ordered sequence, where each item (node) contains a data field and a pointer to the next item; unlike an array, nodes don't need to be stored in contiguous memory locations

How do you traverse a linked list?

Start at the node referenced by the 'start' pointer, output/process the data at the current node, then follow that node's pointer to the next node, repeating until a null/empty pointer signals the end of the list

How is a new node added into the middle of a linked list (without moving existing data)?

The new value is placed in the next free memory location, and the pointer of the preceding node is updated to point to the new node, while the new node's pointer is set to point to what the preceding node used to point to

How is a node "removed" from a linked list?

The pointer of the preceding node is updated to skip over (point past) the node being removed and point directly to the next node instead — the removed node's data isn't erased, it is just no longer part of the traversal path

Give one advantage and one disadvantage of a linked list compared to an array

Advantage: values can be easily added or removed by just updating pointers, without shifting other elements. Disadvantage: uses more memory (extra space for pointers) and items can't be accessed directly by index — you must traverse from the start

What does LIFO stand for, and which data structure uses it?

Last In First Out — used by a stack

Name the main operations of a stack

push(value) — add to top; pop() — remove and return top value; peek() — return top value without removing; isEmpty(); size()

Give a real-world use of a stack in computing

Reversing an action such as "undo" or navigating "back" a page in a browser

What does FIFO stand for, and which data structure uses it?

First In First Out — used by a queue

Name the main operations of a queue

enQueue(value) — add to the back; deQueue() — remove and return from the front; peek(); isEmpty(); isFull()

What is the difference between a linear queue and a circular queue?

A linear queue is implemented as a simple array where items are added/removed from fixed ends, which can waste space once the rear reaches the end of the array; a circular queue reuses freed space at the front by wrapping the rear pointer back to the start of the array once it reaches the end

What is a graph, made up of?

A set of vertices/nodes connected by edges (also called arcs or pointers)

What is the difference between a directed and an undirected graph?

In a directed graph, edges can only be traversed in one direction; in an undirected graph, edges can be traversed in both directions

What is a weighted graph?

A graph where a numerical value (weight) is attached to each edge

What is an adjacency matrix used for?

Representing a graph as a grid of rows and columns, where a value in the matrix indicates whether (and, for weighted graphs, how strongly) two nodes are connected by an edge

How does a breadth-first search traverse a graph?

It systematically visits all neighbours of the current node before moving on to their neighbours (visiting layer by layer), using a queue to keep track of nodes to visit next

How does a depth-first search traverse a graph?

It explores as far as possible along one branch before backtracking, using a stack to keep track of nodes to visit next

*What data structure does breadth-first search use, and what data structure does depth-first search use?

Breadth-first search uses a queue; depth-first search uses a stack

What is a tree, and how does it relate to a graph?

A connected, undirected graph with nodes and pointers that has a hierarchical structure with a single root node and no cycles

Define the following tree terms: root, leaf, parent, child

Root: the single top node with no incoming edges. Leaf: a node with no children. Parent: a node with outgoing edges to another node. Child: a node with an incoming edge from another (parent) node

What is a binary tree?

A rooted tree where every node has a maximum of two children

What is the order of traversal for post-order (depth-first) traversal of a binary tree?

Left subtree, then right subtree, then the root node

What is the order of traversal for breadth-first traversal of a binary tree?

Start at the root, then visit each node level by level, moving left to right across each level before moving down to the next

How do you decide where to insert a new value into a binary search tree?

Compare the new value to the current node: if smaller, move to the left child; if larger, move to the right child; repeat until reaching an empty position, where the new value is inserted

How do you delete a leaf node (no children) from a binary search tree?

Simply remove it directly, since it has no children to reconnect

How do you delete a node with one child from a binary search tree?

Replace the node being deleted with its single child

How do you delete a node with two children from a binary search tree?

Replace the node with its in-order successor (the minimum value in its right subtree, or alternatively the maximum value in its left subtree), then delete that successor node from its original position

What is a hash table, and what is it used for?

An associative array combined with a hash function that maps keys to indexes, providing fast (potentially constant-time) access to data for searching and indexing

What is a collision in a hash table?

When the hash function produces the same hash value (index) for two or more different keys

What is linear probing, as a method of resolving hash table collisions?

When a collision occurs, the data is placed in the next available (empty) position in the table, checked sequentially or at a set interval, until a free slot is found

What is chaining, as a method of resolving hash table collisions?

Instead of storing data directly in the table, each hash table slot points to a linked list; when a collision occurs, the new item is added to that slot's linked list (chain) rather than overwriting existing data

*What is a drawback of using linear probing to resolve collisions?

It reduces the efficiency of retrieval, since if a collision occurred during insertion, the retrieval process may need to check multiple locations sequentially before finding (or confirming the absence of) the correct data

What is rehashing, and why is it used?

Creating a new (usually larger) hash table and re-inserting all existing items using the hash function again; it's used when a table becomes too full or has too many collisions, which would otherwise degrade performance

What is the order of precedence for Boolean operators (highest to lowest)?

Brackets first, then NOT, then AND, then OR

What does the AND (conjunction) operator return, and when?

Returns TRUE only if both inputs are TRUE; otherwise returns FALSE

What does the OR (disjunction) operator return, and when?

Returns TRUE if either input is TRUE; only returns FALSE if both inputs are FALSE

What does the NOT (negation) operator do?

Inverts the input value — NOT TRUE = FALSE, and NOT FALSE = TRUE

What does the XOR (exclusive disjunction) operator return, and when?

Returns TRUE if the inputs are different from each other; returns FALSE if the inputs are the same

What is a truth table used for?

Visualising all possible input combinations for a Boolean expression and the resulting output for each combination

What is a Karnaugh map used for?

A visual tool for simplifying Boolean algebra expressions by grouping together terms with common factors, making it easier to identify and eliminate redundant terms

What are the rules for forming valid groups on a Karnaugh map?

Groups must be rectangular, must contain a number of 1s that is a power of 2 (1, 2, 4, or 8), should be made as large as possible, can overlap, and the grid wraps around at the edges

Give the general AND rule for X AND 1, and for X AND 0

X AND 1 = X; X AND 0 = 0

Give the general OR rule for X OR 1, and for X OR 0

X OR 1 = 1; X OR 0 = X

What is De Morgan's Law for NOT(A AND B)?

NOT(A AND B) is equivalent to (NOT A) OR (NOT B) — negate each variable and flip AND to OR

What is De Morgan's Law for NOT(A OR B)?

NOT(A OR B) is equivalent to (NOT A) AND (NOT B) — negate each variable and flip OR to AND

What is the distributive law in Boolean algebra?

A AND (B OR C) is equivalent to (A AND B) OR (A AND C); similarly A OR (B AND C) is equivalent to (A OR B) AND (A OR C) — similar to factorising in normal maths

What is the associative law in Boolean algebra?

(A AND B) AND C is equivalent to A AND (B AND C), and the same applies for OR — brackets can be removed and variables regrouped without changing the result

What is the commutative law in Boolean algebra?

The order of variables does not change the result: A AND B is the same as B AND A, and A OR B is the same as B OR A

What is the double negation law in Boolean algebra?

NOT(NOT(A)) = A — negating a variable twice returns the original variable

What is a D-type flip flop, and what does it store?

A fundamental digital circuit component (a type of bistable circuit) used to store the state of 1 bit of data, changing state only on the edge of a clock pulse

What happens to the outputs Q and NOT(Q) of a D-type flip flop on the rising edge of the clock pulse?

If the data input D is high (1), Q goes high and NOT(Q) goes low; if D is low (0), Q goes low and NOT(Q) goes high — and Q holds this value until the next rising clock edge

What are the inputs and outputs of a half adder circuit?

Two inputs, A and B; two outputs, Sum (S) and Carry out (Cout)

How are the Sum and Carry outputs of a half adder calculated in terms of logic gates?

Sum = A XOR B; Carry out = A AND B

What are the inputs and outputs of a full adder circuit?

Three inputs: A, B, and a carry in (Cin); two outputs: Sum (S) and Carry out (Cout)

How can a full adder be built using half adders?

Using two half adders (the first combining A and B, the second combining that result's sum with Cin) plus an OR gate to combine the two carry outputs into the final Cout

*How could four full adder circuits be used together to add two 4-bit binary numbers?

By chaining four full adders together, with the carry-out of each adder connected to the carry-in of the next adder along, allowing the carry to propagate correctly across all 4 bits