Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

1 > Data types, data structures and algorithms > Flashcards

Data types, data structures and algorithms Flashcards

1
Q

What is a string?

A

A collection of characters

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

1 nybble=

A

1 nybble = 4 bits

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

The least significant bit of a binary number is the one furthest to the…

A

right

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

BINARY ADDITION

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

A

0+0+0=0
0+0+1=1
1+1+0= 10 (0 carry 1)
1+1+1= 11 (1 carry 1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Explain sign magnitude

A

A way of representing negative numbers in binary

Ignore most sig bit and convert remaining bits to decimal then change the sign

e.g 10101101 =173
1 10101101 = -173 (1 for negative)
0 10101101 = +173 (0 for positive)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Explain two’s compliment

A

Its a way of representing negative numbers in binary

This is done by making the most significant bit negative

eg 7 = 00000111
In two’s complement
-7=-128+64+32+16+8+1
=11111001

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is an easy way of converting a number to two’s complement?

A

Flip the bits in the positive version and adding one

eg 7 = 00000111
In two’s complement
=11111000 then add one

=11111001

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Number bases

A

Decimal = base 10
Binary = base 2
Hexadecimal = base 16

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

HEX conversion values

A

0-9 = 0-9
A-F = 10-15

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Convert hex 4E7F into decimal

A

16^3 : 4 (4X4096)
16^2 : E (14X256)
16^1 : 7 (7X16)
16^0 : F (15X1)

(4X4096) + (14X256) + (7X16) + (1X15)= 20095

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Convert hex B2 into decimal

A

16x11 =B
1X2= 2

(16X11) + (1X2) 178

OR

B=11 2=2
11=1011 2=0010
COMBINE: 10110010

10110010=178

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Can be split into 2 parts mantissa and exponent

What is this?

A

Floating point binary numbers

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Why does floating point binary need to be normalised?

A

To make sure they are as precise as possible in a given number of bits

(meaning making use of as much mantissa as possible)

To normalise number make sure it starts with:
01 for positive num
10 for negative num

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is meant by a character set?

A

A published collection of characters and corresponding codes which can be used by computers for respresenting text

2 examples of character sets are ASCII and Unicode

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Give examples of character sets

A

ASCII and Unicode

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

ASCII

A

Example of a character set
-Uses 7 bits (2^7= 128 characters)
-Capital A-Z=65-90
-Lower a-z= 97-122
-Also has codes to represent other symbols and numbers
-Can only represent characters in English language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

UNICODE

A

-Uses a varying number of bits
-Better than ASCII as it can represent more characters meaning that it can be used for more different languages rather than just English
-Can represent letters, numbers, symbols, emojis….

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is an array?

A

An ordered, finite set of elements of a single type

-Taken to be zero-indexed (first index 0) unless stated in question

Linear array = 1D

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is a record made up of?

A

Row in a file made up of fields

-eg used in databases

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Lists can contain elements of more than one data type

TRUE OR FALSE

A

TRUE
(Unlike arrays)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is a list?

A

A data structure consisting of a number of ordered elements where each element can occur more than once

(ordered because the elements retain the sequence in which they were added until you change them)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

A difference between lists and arrays is that the values in a list are stored non-contiguously.
What does this mean?

A

Non contiguous = The values don’t have to be stored in consecutive memory locations. Each element of a list can be in different places in memory.

Because lists store references (or pointers) to their values, which may be scattered in memory. This flexibility allows lists to grow dynamically and hold elements of different types.

Arrays, on the other hand, store values in contiguous memory locations, which ensures fast access using indexes but requires fixed size memory allocation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Give ways to represent graphs

A

-Adjacency matrix
-Adjacency list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Give advantages of using adjacency matrices

A

Advantages:
Fast Edge Lookup:
-Checking whether an edge exists between two vertices is O(1), as it’s just a direct index access.

Simplicity:
-Easy to implement and understand, especially for dense graphs.

-Efficient for Dense Graphs:
Works well when the number of edges is close to the maximum possible (otherwise wasted memory space as it allocates space in memory for every possible edge in the graph even the ones that dont exist)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Give advantages of using adjacency lists

A

-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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is meant by sparse graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is meant by a dense graph?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is a stack?

A

-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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is a queue?

A

-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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Give a disadvantage of linear queues and why they aren’t effective at implementing queues

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

How do Circular queues work?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is meant by a subtree?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is meant by a tree?

A

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

34
Q

Formula for finding the number of edges in a tree

A

For n nodes there is n-1 edges

35
Q

Formula for finding the number of nodes in a tree

A

For n edges there is n+1 nodes

36
Q

What is a binary tree?

A

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

37
Q

Give methods of traversing a binary tree

A

-Pre order
-In order
-Post order

38
Q

-Pre order
-In order
-Post order
Are examples of?

A

Methods of traversing binary trees

39
Q

Pre order traversal

A

Root left right

40
Q

In order traversal

A

Left root right

41
Q

Post order traversal

A

Left right root

42
Q

Hash tables

A

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

43
Q

A good hashing function should have ….

A

a low probability of collisions

44
Q

What is the role of a hash function?

A

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

45
Q

BOOLEAN ALGEBRA:

AND

A

Operation: Conjunction
Symbol: ^

46
Q

BOOLEAN ALGEBRA:

OR

A

Operation: Disjunction
Symbol: V

47
Q

BOOLEAN ALGEBRA:

NOT

A

Operation: Negation
Symbol: ¬

48
Q

BOOLEAN ALGEBRA:

XOR

A

Operation: Exclusive disjunction
Symbol: ⊻

49
Q

De Morgan’s law

A

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

50
Q

DISTRIBUTION LAWS:

LAW OF CONJUNCTION OVER DISJUNCTION

A

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

51
Q

DISTRIBUTION LAWS:

LAW OF DISJUNCTION OF CONJUNCTION

A

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

52
Q

Commutative law

A

Shows that the order of literals doesnt matter
xy= yx

53
Q

Associative law

A

Addition or removal of brackets and reordering of literals (variables) in a boolean expression
x(yz) = (xy)z = xyz

54
Q

D type flip flops

A

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

55
Q

Explain the logic circuit of a D type flip flop

A

Uses 4 NAND gates

56
Q

A D Type flip flop is an example of a…

A

Sequential logic circuit and memory unit

57
Q

A flip-flop is a type of SEQUENTIAL logic circuit. While many logic circuits, like simple gates, are COMBINATIONAL.

What is the difference?

A

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)

58
Q

In a D-type flip-flop, the output (Q) depends on…..

A

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….

59
Q

A D-type flip-flop is both a memory unit and a logic circuit. Explain this

A

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

60
Q

Sets of flipflops can be conbined to…

A

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

61
Q

What is meant by an ‘adder’?

A

A logic circuit used to perform the addition of binary numbers

-There are two types: half and full

62
Q

What is a half adder?

A

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.

63
Q

What is a full adder?

A

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

64
Q

Sometimes a boolean expression is identical to another shorter expression. Its more desirable to use the shorter version. What can be used in order to simplify an expression?

A

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

65
Q

Ways of representing negative numbers in binary

A

-Twos compliment
-Sign magnitude

66
Q

Floating point binary

Increasing mantissa=….

A

-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.

67
Q

What does the mantissa represent in floating point binary?

A

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

68
Q

Give disadvantages of increasing the mantissa in floating point binary

A

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

69
Q

Give disadvantages of decreasing mantissa

A

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.

70
Q

Give disadvantages of using adjacency matrices

A

-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

71
Q

Give disadvantages of using adjacency lists

A

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

72
Q

Formula for possible number of edges in a graph with n vertices

A

(1/2)n(n-1)

73
Q

What is a static data structure?

A

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.

74
Q

Give advantages of using static data structures

A

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

75
Q

Give disadvantages of using static data structures

A

-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.

76
Q

Give advantages of using dynamic data structures

A

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

77
Q

Give disadvantages of using dynamic data structures

A

-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

78
Q

What are the logic gates used in a full adder?

A

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

79
Q

What is meant by a primitive data type?

A

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)

80
Q

Why would you use linear search over binary search?

A

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

81
Q
A

1 (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions