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.

(rather than arrays as they have to be next to eachother in memory)

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

Give ways to process 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

-Ea

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 large, sparse graphs

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

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

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

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.

31
Q

How do Circular queues work?

A

FIFO
Get around the ‘waste space’ problem from linear queues:

-The queue’s rear pointer is equal to the max size of queue
-When ADDING an item to the queue, it is added to the position pointed to by the REAR pointer. If the rear is at the last position in the queue, it wraps around to the beginning (index 0).(so rear is at index 0)

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

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 releases an output (hash) by using a hash function

-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
A
53
Q

Commutative law

A

Shows that the order of literals doesnt matter
xy= yx

54
Q

Associative law

A

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

55
Q

D type flip flops

A

A type of logic circuit 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

56
Q

Explain the logic circuit of a D type flip flop

A

Uses 4 NAND gates

57
Q

A D Type flip flop is an example of a…

A

Sequential logic circuit and memory unit

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

59
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 typically responds on the rising edge of the clock pulse. 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….

60
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

61
Q

Sets of flipflops can be conbined to…

A

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

62
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

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

64
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

65
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

66
Q
A

1 (5 decks)

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