1.4 Data types, data structures and algorithms

Question 1

What is a D-Type Flip Flop and how does it work? (1.4.3)

Answer 1

• Logic circuit, stores 1 bit only
• 2 inputs, control signal + clock
• Clock: regular CPU pulse, coordinates, rises / falls
• 4 NAND gates used

Question 2

How does a Half Adder work? (1.4.3)

Answer 2

• Takes 2 inputs
• Gives 2 outputs: sum & carry
• Formed of AND & XOR
• When both A & B False, outputs False
• When A or B True, sum True
• When both inputs True, carry True, sum False

Question 3

What is the order for in-order traversal? (1.4.2)

Answer 3

1. Leftwards:
2. Left subtree
3. Parent
4. Right subtree
5. Root
6. Rightwards:
7. Left subtree
8. Parent
9. Right subtree

Question 4

What are the 3 types of graph data structures? (1.4.2)

Answer 4

• Directed: only traversed in 1 direction
• Undirected: traversed both directions
• Weighted: arcs have cost attached

Question 5

What is the order for pre-order traversal? (1.4.2)

Answer 5

1. Root node
2. Leftwards:
3. Left subtree
4. Right subtree
5. Rightwards:
6. Left subtree
7. Right subtree

Question 6

How does a Full Adder work? (1.4.3)

Answer 6

• Like Half Adder, additional input
• Allows carry representation
• Formed from 2 XOR gates, 2 AND gates, 1 OR gate
• Chained together

Question 7

What are hash tables as data structures? (1.4.2)

Answer 7

• Array coupled with hash function
• Hash function takes data, produces unique output
• Maps data to unique index
• If same output, collision, placed in next available

Question 8

How do linked lists work? (1.4.2)

Answer 8

• Dynamic, holds ordered sequence
• Each item called node, contains data, & pointer (next item in list)

Question 9

What are stacks and queues used for? (1.4.2)

Answer 9

Stacks:

• Performing depth-first searches on graphs
• Tracking user inputs (e.g. undo)
• Backtracking (e.g. pathfinding)

Queues:

• Performing breadth-first searches on graphs
• Transferring data between processors
• Process scheduling

Question 10

What is a root, child, and leaf, in tree data structures? (1.4.2)

Answer 10

Root: node with no incoming nodes

Child: node with incoming edges

Parent: node with outgoing edges

Leaf: node with no children

Question 11

What is the order for post-order traversal? (1.4.2)

Answer 11

1. Leftwards:
2. Left subtree, leaf first
3. Right subtree, leaf first
4. Parent
5. Rightwards:
6. Left subtree, leaf first
7. Right subtree, leaf first
8. Parent
9. Root