Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > 1.4 Data Types, Data Structures and Algorithms > Flashcards

1.4 Data Types, Data Structures and Algorithms Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What does AND (∧) mean?

A

A logical operator which returns TRUE (or 1) if and only when all inputs are TRUE (or 1)

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

What is ASCII?

A

A character set used to represent alphanumeric characters or symbols as a set of 8 bits

1 check bit and 7 bits for the number

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

What is binary?

A

A number system that only uses 1s and 0s to represent numbers (a base 2 system)

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

What is bitwise manipulation?

A

Operations perfomed on a set of bits

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

What is boolean?

A

A data type that can only store one of two possible values (1 or 0, TRUE or FALSE, etc.)

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

What is a character?

A

A data type for storing one letter, number or special character

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

What is Denary?

A

A number system that only uses 10 characters (0 to 9) to represent numbers (a base 10 system)

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

What are the 5 data types?

A

Character
Boolean
String
Integer
Real/Float

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

What is Floating Point Arithmetic?

A

Performing arithmetic operations on floating point numbers in binary

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

What is Hexadecimal?

A

A number system that only uses 16 characters (
0 to 9 and A to F) to represent the numbers (a base 16 system)

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

What is an integer?

A

A data type for storing whole numbers with no decimals, positive or negative

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

What does OR (V) mean?

A

A logical operator which returns TRUE (or 1) if and only if any one of the inputs are TRUE (or 1)

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

What is the primitive data type?

A

A basic built in data type provided by a programming language

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

What is a Real/Floating point?

A

A data type for storing numbers with decimal or fractional parts

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

What are the binary Shifts?

A

A bitwise manipulation where a set of bits are all moved by one place in a given direction, and the end bit may be taken as a carry or appended to the other end depending on the shift method

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

What is the String data type?

A

Used to store a sequence of alphanumeric characters or symbols, typically within quotation marks

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

What is Two’s Complement?

A

A method of storing negative numbers in binary

It involves flipping all the bits of the binary representation of the positive number and then adding 1

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

What is UNICODE?

A

A character set that is a superset of ASCII

It is used to represent alphanumeric characters and symbols as an integer code point which is equal to that character’s ASCII code

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

What does XOR do?

A

A logical operator which returns TRUE or 1 when only one input is TRUE or 1

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

What are arrays?

A

A data structure for storing a finite, ordered set of data of the same data type within a single identifier

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

What is a Binary Search Tree?

A

A tree where each node cannot have more then 2 children nodes

The right node and its descendants always have a greater value than the root node (first data item)

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

What is a Depth First Transversal?

A

A method of traversing an entire graph by travelling as far as possible along one route before backtracking and trying alternative unexplored routes

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

What is a Breadth First Transversal?

A

A method of traversing an entire graph by visiting all the neighbours of the first node before repeating the same with each neighbour in the order they were visited

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

What is a Directed Graph?

A

A graph where the order of the vertices paired in an edge matter

The edges are one way

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

What is a graph?

A

A data structure consisting of a set of vertices/nodes connected by a set of edges/arcs

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

What is a Hash Table?

A

A data structure where a hashing algorithm calculates a value to determine where a data item is to be stored

The data item can then be directly accessed by recalculation, without any search

Uses an algorithm to determine storage location.

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

What are Linked Lists?

A

A data structure that stores an ordered sequence of data where each item is stored with a pointer to the next item

The items are not stored contiguously (in this same order) in memory

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

What are Lists?

A

A data structure that stores a sequence of data values, each with a unique index

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

What are Queues?

A

A first in first out (FIFO) data structure

The first item added/pushed on to the queue is the first to be removed/popped off

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

What are Stacks?

A

A last-in-first-out data structure

The last item added/pushed is the first to be removed/popped off

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

What are Records?

A

A data structure that stores a collection of fields which store data based on attributescan be did data type

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

What are Trees?

A

AA data structure that uses a set of linked nodes to form a hierarchical structure starting at a root node

Each node is a child/sub-node of a parent node

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

What are Tuples?

A

A data structure for storing an immutable, ordered set of data, which can be of different data types, within a single identifier

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

What is an Undirected Graphs?

A

A graph where the order of the vertices paired in an edge does not matter

Their edges are bidirectional

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

What are the Association Laws?

A

A ∧ (B ∧ C) = (A ∧ B) ∧ C
A V (B V C) = (A V B) V C

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

What are Boolean expressions?

A

A combination of Boolean values and logical operators which evaluates to either TRUE or FALSE depending on the inputs

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

What is Boolean Logic?

A

A type of algebra with logical operators where all the values and expressions ultimately reduce to TRUE or FALSE

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

What are the Commutation Laws?

A

A ∧ B = B ∧ A
A V B = B V A

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

What are the De Morgan’s Laws?

A

¬(A V B) = ¬A ∧ ¬B
¬(A ∧ B) = ¬A V ¬B

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

What are the Distribution Laws?

A

A ∧ (B V C) = (A ∧ B) V (A ∧ C)
(A V B) ∧ (C V D) = (A ∧ C) V (A ∧ D) V (B ∧ C) V (B ∧ D)

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

What is the Double Negation Law?

A

¬¬A = A

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

What are D-Type Flip Flops?

A

A sequential logic circuit used to store a single bit

It has two stable states, which can be flipped between using an input signal

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

What are Full Adders?

A

A combination od two half adders that takes a carry bit and two other input bits and returns their sum and trhe new carry as two output bits

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

What are Half Adders?

A

A combinational arithmetic circuit that adds two numbers and produces a sum bit (S) and carry bit (C) as the output

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

What are Karnaugh Maps

A

A method of simplifying Boolean expressions by redrawing the truth table and applying a set of visual rules to obtain expressions wit (or close to) the minimum logical operators, as a sum of products

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

What are Logic Gate Diagrams?

A

A graphical method of representing Boolean expressions using the standard symbols for logic gates

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

Why do computers store data in binary?

A

Easier to process and takes up less space

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

Binary to decimal?

1101

A

Write out the binary number under powers of increasing 2…

2^3 2^2 2^1 2^0
1 1 0 1 = 13
8 + 4 + 1 = 13

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

Decimal to binary?

82

A

Write out the powers of 2 again, take away the greatest one possible till 0 is acquired.

82 - 64 = 18
18 - 16 = 2
2 - 2 = 0… done.

01010010

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

Hexadecimal to binary?

B2

A

Split up the hexadecimal..
B 2
B = 11 2 = 2
11 = 1011 2 = 0010 (convert to binary)
Then combine to make the full conversion = 10110010 = B2

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

Hexadecimal to decimal?

4C3

A

Same thing as binary to decimal, line up the hexadecimal number with the columns of increasing powers of 16…

16^2 16^1 16^0
4 C 3
4x256 + 12x16 + 3x1 = 1219

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

How can you tell if a floating point numbers in binary have been normalised?

A

They start with either…

01, for a positive number
10, for a negative number

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

Normalise the binary number 000110100101 which is a floating point number with an eight bit mantissa and a four bit exponent.

A

Mantissa = 01101000
Exponent = 0011

if you got this wrong check one note and revisit later on…

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

Why is hexadecimal used to represent data?

A

More compact so use less memory, so more numbers can be stored in computer systems. More user friendly representation of binary-coded values

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

Why is decimal used?

A

Easiest to read and understand for humans

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

Each binary shift to the left or the right does what affect to the binary number?

A

Left = Doubling
Right = Halving

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

What is a mask?

A

A mask can be applied to binary numbers by combining them withy a logic gate

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

What happens when you mask the binary numbers below with an AND, OR and XOR gates?

00101011
10111011

A

AND = 00101011

XOR = 10010000

OR = 10111011

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

What is a character set?

A

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

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

How many different characters could be represented through ASCII?

A

0-127, so therefore 128

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

What else can you say about arrays, how do they start?

A

Zero indexed base

59
Q

How does a 3D array select an item? (pseudocode )

A

threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]]
print(threeDimensionalArray[0,1,2])
» 19

Uses…

threeDimensionalArray[z,y,x], where z is the array number, y is the row number and x is the column number.

60
Q

How does a 2D array select an item? (pseudocode )

A

twoDimensionalArray = [[123, 28, 90, 38, 88, 23, 47],[1, 23, 12,
14, 16, 29, 12]]
print(twoDimensionalArray)
» [[23, 28, 90, 38, 88, 23, 47],
[ 1, 23, 12, 14, 16, 29, 12]]
print(twoDimensionalArray[1,3]) // Goes down and then across
» 14

61
Q

Where are records typically found?

A

As a row in a file or in a database

62
Q

What is the difference between lists and arrays?

A

List values are stored non-contiguously, lists can also store more than one data types

63
Q

What does it mean when data is stored in non-contiguous memory?

A

This means that they do not have to be stored next to one another in memory

64
Q

Checks if the list is empty

A

list.isEmpty()

65
Q

Adds a new value to the
end of the list

A

list.append(value)

66
Q

Removes the value the first time it appears in the list

A

list.remove(value)

67
Q

Searches for a value in the
list

A

list.search(value)

68
Q

returns length of list

A

list.length()

69
Q

Returns the position of the item

A

list.index(value)

70
Q

How to insert value into a list in a specific place

A

List.insert(position,value)

71
Q

How to remove and return last value in list

A

list.pop()

72
Q

How to remove and return specific value in list

A

List.pop(position)

73
Q

What does immutable mean?

A

It cannot be changed, elements cannot be added or removed once it has been created

Cannot be changed at runtime.

74
Q

Are tuples immutable or mutable?

A

Immutable

75
Q

Within a linked list what is each item called?

A

A node, containing a data field alongside another address called a link or a pointer field

76
Q

What does the data field contain?

A

The data field contains the value of the actual data which is part of the list

77
Q

What does the pointer field contain?

A

The pointer field contains the address of the next item in the list.

78
Q

What do linked lists store the index of the first item in their list as?

A

The pointer which also points to the next available space

79
Q

By the way that linked lists are stored, how does this affect their transversal? And how is it different to an array?

A

As items in linked lists are stored in a sequence, they can only be traversed in this order; an item cannot be directly accessed, as is possible in an array

80
Q

What is a weighted graph?

A

A graph with costs added to each edge

81
Q

What does an adjacency list look like and when is it used?

A

When computers can process graphs by using…

Adjacency List
A → {B:4, C:18, D:12}
B → {A:4, C:5, E:8}
C → {A:18, B:5, D:5}
D → {A:12, E:3}
E → {B:8, D:3}

82
Q

What does an adjacency matrix look like and when is it used?

A

When computers can process graphs by using…

Adjacency Matrix
A B C D E
A - 4 18 12 -
B 4 - 5 - 8
C 18 5 - 5 -
D 12 - - - 3
E - 8 - 3 -

83
Q

What are the advantages of adjacent matrix?

A

Convenient to work with due to quicker access times
Easy to add nodes

84
Q

What are the disadvantages of adjacent matrix?

A

More space efficient for large, sparse networks

85
Q

When are stacks typically used in computers?

A

used to reverse an action, such as to go back a page in web browsers

The ‘undo’ buttons
that applications widely make use of also utilise stacks

86
Q

Can stacks be static or dynamic?

A

Both, where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory

87
Q

Where does the pointer point to in a stack?

A

Points to the top of the stack, where the next piece of data will be inserted

88
Q

What does Stack.isEmpty() do?

A

Checks if the stack is empty

Works by checking the value of the top pointer

89
Q

How to add a new value to end of stack

A

What does Stack.push(value) do?

90
Q

return top value of stack

A

stack.peek()

91
Q

Removes and returns the top value of the stack

A

stack.pop()

92
Q

stack.isFull()

A

Checks if the stack if full and returns a Boolean value

Works by comparing stack size to the top pointer

92
Q

Returns the size of the stack

A

stack.size()

92
Q

When are queues commonly used?

A

Printers, keyboards and simulators

93
Q

How can you select a field from a record using pseudocode?

A

recordName.fieldName

94
Q

What is the difference between a tuple and an array?

A

Tuples are initialised using regular bracket instead of square brackets

95
Q

What is the root node>

A

The node which doesn’t have any incoming nodes, at the top of the tree

96
Q

What is a child node?

A

Any node which has an incoming edge

97
Q

What is a parent node?

A

Any node which has outcoming edges

98
Q

What is a subtree?

A

A section of the tree which consists of a parent and all the children of that parent

99
Q

What is a leaf?

A

A nod which has no children

100
Q

What is a collision? (hashing)

A

A collision is where two inputs result in the same hashed value

101
Q

What does a good hashing algorithm have?

A

A low chance of collision
Fast

102
Q

What is a linear queue?

A

a data structure consisting of an array

103
Q

What do circular queues do that linear queues do not?

A

Once the queue’s rear pointer is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty

104
Q

What are the advantages of using a circular queue instead of a linear queue?

A

They use space in an array more effectively, although they are harder to implement

105
Q

What does Queue. enQueue(value) do?

A

Adds a new item to the end of the queue

Increments the back pointer

106
Q

What does Queue. deQueue() do?

A

Removes the item from the front of the queue

Increments the front pointer

107
Q

What does Queue. isEmpty() do?

A

Checks if the queue if empty by comparing the front and back pointer

108
Q

What does Queue. isFull() do?

A

Checks if the queue is full by comparing the back pointer and queue size

109
Q

What are hash tables normally used for?

A

Hash tables are normally used for indexing, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored

110
Q

What is collision resolution?

A

When collisions occur and the item is typically placed in the next available location

111
Q

What does the hash function do?

A

The hash function takes in data (a key) and releases an output (the hash)

The role of the hash function is to map the key to an index in the hash table

112
Q

What is a Node?

A

An item in the tree

113
Q

What is a root?

A

A single node which does not have any incoming nodes, typically the node at the top of the tree

114
Q

What is an Edge?

A

Connects two nodes together and is also known as a branch, or arc

115
Q
A
116
Q

What does the symbol v with a _ underneath it represent?

A

XOR Gate

117
Q

When interpreting a Karnaugh Map, what sjhoykd you do first?

A

Highlight and try to group all the 1s in the map

Remember that overlapping top and bottom and sides is possible

118
Q

What are the three logic circuits you need to be familiar wwith?

A

D-Type Flip Flops
Half Adders
Full Adders

119
Q

When does the output of a D-Type Flip Flop change?

A

At a rising edge, the start of a clock tick

120
Q

When are half adders used?

A

In digital circuits

121
Q

When are full adders used?

A

ALUs
CPU registers
memory units

122
Q

What is the purpose of a D-type flip flop?

A

To store the value of a single bit

123
Q

When does a ripple adder come into play?

A

Because the full adders have a carry input, the circuits can be chained together to form what’s known as a ripple adder

124
Q

Difference between list and 1 d array

A

Lists are similar to 1D arrays and elements can be accessed in the
same way. The difference is that list values are stored non-contiguously. This means they
do not have to be stored next to each other in memory, as data in arrays is stored. Lists
can also contain elements of more than one data type, unlike arrays

125
Q

What is the benefit of using a linked list that uses objects

A

any available memory can be used to store data as they do not have to be contiguously adjacent

126
Q

Applications of linked lists

A

OS managing processor to store process blocks in a ready state and web browsers to navigate backwards and forwards

127
Q

Linked list add

A

Adds a node to the linked list

128
Q

Linked list delete

A

Removes a node from the linked list

129
Q

Linked list next

A

Moves to the next item in the listL

130
Q

inked list previous

A

Moves to the previous item in a doubly linked list

131
Q

Linked list traverse

A

A linear search through the linked list

132
Q

What is a binary tree

A

Each node has a max of 2 children

133
Q

What are the two inputs for a d type flip flop

A

Control signal and a clock input

134
Q

What is a d type flip flop

A

Logic circuit which can store the value of one bit

135
Q

Image of a d type flip flop

A
136
Q

WHere are d type flip flops used

A

memory circuits counters and shift registers

137
Q

How are d type flip flops used in shift registers

A

Handle signals arriving on parallel lines at different times

138
Q

Why is it important to use as few expressions as possible

A
139
Q

What do tuples and lists have in common?

A

They both can have different data types

140
Q

How does arrays get stored in memory?

A

In Contiguous memory

141
Q

What does OR mask do

A

Change bits in a binary number to one

142
Q

Function of AND mask

A

AND something with 0 it will turn it to 0 (masking out a bit )

143
Q

Disadvantage of embedded OS

A

Difficult to update if required

144
Q

What does list.search(value)

A

Returns true or false depending on whether the value is present in the list

145
Q
A

Computer Science (33 decks)

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