Data types, data structures and algorithms Flashcards

Question

Give advantages of using adjacency lists

Answer 1

-Better to work with for small, sparse graphs -No wasted memory space because it only allocates memory to the edges that exist within the graph (rather than all possible ones like with matrices)

Answer 2

A graph in which the number of edges is relatively SMALL compared to the number of POSSIBLE edges among the vertices. (small edge to vertex ratio) LESS EDGES

Answer 3

A graph in which the number of edges is relatively large compared to the number of POSSIBLE edges among the vertices. (large edge to vertex ratio) MORE EDGES

Answer 4

-Last in first out (LIFO) data structure -Can be implemented as a static or dynamic structure -Used to reverse an action -They are implemented using a pointer which points to the top of the stack

Answer 5

-First in first out (FIFO) data structure -Can use an array to implement it -2 POINTERS one at the start and the other at the end of queue

Answer 6

They can lead to inefficient memory usage due to the "wasted space" problem In a linear queue, elements are added at the back and removed from the front . As items are removed, even tho the front of the queue technically moves forward, the space at the front is not reused. Over time, the queue might reach the end of the allocated memory even if there’s free space at the beginning. -To combat this: either shifting all elements to the front (which is inefficient) or setting a maximum size that limits the queue’s use ( so that the queue appears full). So circular queues are preferred, as they allow the queue to wrap around and reuse the memory efficiently.

Answer 7

FIFO Get around the 'waste space' problem from linear queues: START -Front Pointer: The front pointer typically starts at 0, because the first element in the queue will be added at index 0. -Rear Pointer: The rear pointer also starts at 0 because initially, no items have been added yet. However, after adding the first element (enqueue), the rear pointer moves to 1. END -When the rear pointer reaches maxsize - 1, it wraps around to index 0, ensuring that the queue efficiently uses the available space.

Answer 8

A subsection of a tree consisting of a parent and all the children of a parent

Answer 9

A data structure -Its a simply connected graph with no loops or multiple edges

Answer 10

For n nodes there is n-1 edges

Answer 11

For n edges there is n+1 nodes

Answer 12

A type of tree -Each node has a max of 2 child nodes

Answer 13

-Pre order -In order -Post order

Answer 14

Methods of traversing binary trees

Answer 15

Root left right

Answer 16

Left root right

Answer 17

Left right root

Answer 18

A data structure Its an array coupled with a hash function. HF takes in an input (key) and produces an output (hash) -Role of hash function is to map a key to its index

Answer 19

a low probability of collisions

Answer 20

To map a key(input) to an index (output) in the hash table

Answer 21

Operation: Conjunction Symbol: ^

Answer 22

Operation: Disjunction Symbol: V

Answer 23

Operation: Negation Symbol: ¬

Answer 24

Operation: Exclusive disjunction Symbol: ⊻

Answer 25

Break negation (break the line), change the operator (change the sign)

Answer 26

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

Answer 27

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

Answer 28

Shows that the order of literals doesnt matter xy= yx

Answer 29

Addition or removal of brackets and reordering of literals (variables) in a boolean expression x*(y*z) = (x*y)*z = x*y*z

Answer 30

A type of sequential logic circuit and memory unit which can store the value of one bit The output can only change at a rising clock edge (which is the start of a clock tick) It has 2 inputs: data and a clock -A clock meaning a regular pulse generated by CPU used to coordinate the computer's components It has 2 outputs: Q and NOT Q

Answer 31

Uses 4 NAND gates

Answer 32

Sequential logic circuit and memory unit

Answer 33

SEQUENTIAL= (flip-flops belong to the sequential category) their output depends on both current inputs and the past states (value that was previously stored) (i.e., they have memory). COMBINATIONAL (like simple logic gates)= Their output depends only on the current inputs without any memory (eg A AND B where 0 AND 1 = 0)

Answer 34

In a D-type flip-flop, the output (Q) depends on: -The current input (D/Data) -The clock signal: determines when the flip-flop samples the D input. The D-type flip-flop responds on the rising edge of the clock pulse (start of clock tick). This means that Q only updates when a rising clock edge occurs and if the value of D (past value) has also changed since the last clock pulse. -Past state: The value that was previously stored when the last clock pulse was applied (the past state). flip-flop holds its last output value until the next clock edge which continues as the output (Q) until the clock pulse triggers an update with a new D input value. => important as it allows digital systems to keep track of information over time, essential for building memory etc....

Answer 35

Memory Unit: The D-type flip-flop functions as a single-bit memory storage device. Stores a bit of data by holding its output (Q) constant until it’s updated by the next clock pulse. Logic Circuit: The D-type flip-flop is also a sequential logic circuit. Like other logic circuits, it takes inputs (D and clock) and produces outputs (Q and sometimes Q’). -Outputs depend on input and past states

Answer 36

Form registers As a single flipflop is a memory unit then multiple can form registers

Answer 37

A logic circuit used to perform the addition of binary numbers -There are two types: half and full

Answer 38

Has two inputs ( A and B) and 2 outputs (Sum and Carry) -Symbols XOR then AND XOR for sum AND for carry *Its used to perform the addition of binary numbers. It takes binary inputs and produces a sum as output, often accompanied by a carry-out if the sum exceeds the maximum value that can be represented with the given number of bits.

Answer 39

Similar to half adder but has an additional input which is carry in. As it has this the circuits can be chained together to form a ripple adder (where the carry output from each stage ripples to the next stage (from one full adder to another) -Uses 2 XOR gates, 2 AND gates and an OR gate

Answer 40

Kaurnaugh Maps -Can be used in a table with 2, 3 or 4... input variables

Answer 41

-Twos compliment -Sign magnitude

Answer 42

-With more bits, the mantissa can represent numbers more precisely, reducing rounding errors. E.G. in a 4-bit mantissa: 1.101 (binary) may approximate a number, but a 6-bit mantissa like 1.10101 gives a closer representation. -Smaller Gaps Between Numbers: A longer mantissa reduces the gap between two adjacent floating-point numbers.

Answer 43

The mantissa holds the significant digits of the number. These digits determine the precission of the value being represented.

Answer 44

Longer Mantissa: Increases precision but uses more memory May slow computation due to the additional processing.

Answer 45

Fewer bits lead to less precision, resulting in larger rounding errors. -Smaller Gaps Between Numbers: A shorter mantissa increases the gap between two adjacent floating-point numbers.

Answer 46

-An adjacency matrix allocates space for every possible edge between vertices, even those that don't exist in the graph. This results in a large amount of wasted memory, especially for sparse graphs (less edges) -Not good for sparse graphs

Answer 47

Slower Edge Lookup: -Checking whether an edge exists between two vertices can take O(V) in the worst case (linear search in the adjacency list of a vertex/search through the whole list) -More Complex Implementation: Slightly harder to implement compared to an adjacency matrix, especially for weighted graphs as a dictionary would have to be used

Answer 48

(1/2)n(n-1)

Answer 49

A static data structure is a data structure with a fixed size, determined at the time of its creation. Key Characteristics: Size is predetermined: Cannot grow or shrink during runtime. Memory allocation: Fixed memory is allocated at compile time. Examples: Arrays (in most languages like C, Java, etc.). Disadvantages: Inflexibility: Cannot adapt to changing data requirements; may lead to wasted memory or insufficient storage. Wasted space: If the reserved size is too large for the actual data.

Answer 50

Advantages: Efficient access: Random access is often faster because memory locations are contiguous. -Memory is allocated at compile-time, no overhead during runtime for storing pointers and allocation and deallocation

Answer 51

-Inflexibility: Cannot adapt to changing data requirements; may lead to wasted memory or insufficient storage. So Wasted space: If the reserved size is too large for the actual data.

Answer 52

-No wasted space in memory as space is allocated when needed

Answer 53

-Implementation is more challenging, requiring careful management of memory (e.g., pointers in linked lists). -Overhead: Dynamic memory allocation may introduce runtime overhead due to pointers and repeated allocations or reallocations, potentially slowing performance. -Risk of fragmentation due to constant allocation and deallocation

Answer 54

-Uses 2 XOR gates, 2 AND gates and an OR gate

Answer 55

A primitive data type is a basic, predefined type of data that is built into a programming language. It represents the simplest form of data that cannot be broken down into smaller components. (int, bool, char, string, double/float)

Answer 56

If the data is not in any order // binary search requires the data to be in order * When the number of items to search is small