1.4 Data types, data structures and algorithms

Question 1

Sign and magnitude

Answer 1

First bit = sign (0 = +, 1 = -); remaining bits = magnitude. Issue: two zeros (+0/-0).

Question 2

Two’s complement

Answer 2

Negative numbers: invert bits + add 1. Solves negative zero; simplifies subtraction.

Question 3

Normalisation (floating point)

Answer 3

Adjusts mantissa/exponent so mantissa starts with 0.1 (positive) or 1.0 (negative); maximises precision.

Question 4

Renormalisation after arithmetic

Answer 4

After addition/subtraction, mantissa may need shifting left/right and exponent adjusting to maintain normalised form.

Question 5

Bitwise AND mask use

Answer 5

Used to clear bits (set to 0).

Question 6

Bitwise OR mask use

Answer 6

Used to set bits (set to 1).

Question 7

XOR bitwise use

Answer 7

Used to toggle/flip bits.

Question 8

Difference between ASCII and UNICODE

Answer 8

ASCII = 7/8 bit, 128/256 chars, English focused. UNICODE = 16/32 bit, covers global characters (emojis, symbols).

Question 9

UTF-8 vs UTF-16

Answer 9

UTF-8: Variable length (1-4 bytes), ASCII compatible. UTF-16: 2 or 4 bytes, better for Asian languages.

Question 10

Stack (LIFO)

Answer 10

Last In, First Out. Push, Pop. Uses: call stack, undo function.

Question 11

Queue (FIFO)

Answer 11

First In, First Out. Enqueue, Dequeue. Uses: print spooler, ready queue.

Question 12

Linked list

Answer 12

Nodes containing data and pointer to next node; dynamic size; sequential access.

Question 13

Binary Search Tree property

Answer 13

Left child < Parent < Right child.

Question 14

Hash table

Answer 14

Uses hash function to compute index; O(1) average lookup.

Question 15

Graph (directed vs undirected)

Answer 15

Directed: edges have direction (one-way). Undirected: edges are bidirectional.

Question 16

Tree

Answer 16

Hierarchical structure; root, parent, child, leaf nodes; no cycles.

Question 17

How to delete from a linked list?

Answer 17

Adjust pointers of previous node to skip the node to be deleted; deallocate memory.

Question 18

De Morgan’s First Law

Answer 18

NOT (A AND B) = (NOT A) OR (NOT B).

Question 19

De Morgan’s Second Law

Answer 19

NOT (A OR B) = (NOT A) AND (NOT B).

Question 20

Distribution law

Answer 20

A AND (B OR C) = (A AND B) OR (A AND C); A OR (B AND C) = (A OR B) AND (A OR C).

Question 21

Association law

Answer 21

(A AND B) AND C = A AND (B AND C); (A OR B) OR C = A OR (B OR C).

Question 22

Commutation law

Answer 22

A AND B = B AND A; A OR B = B OR A.

Question 23

Double negation

Answer 23

NOT (NOT A) = A.

Question 24

D type flip flop

Answer 24

1-bit memory; stores state on clock edge; data (D) transferred to output (Q).

Question 25

Edge-triggered

Answer 25

Flip flop only changes state on rising or falling edge of clock signal.

Question 26

Half adder outputs

Answer 26

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

Question 27

Full adder difference to half adder

Answer 27

Includes a Carry-in (CIN) input to chain multiple bits.