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 and Structures > Flashcards

1.4 Data Types and Structures Flashcards

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

What is a data type?

A

Formal classification of the type of data being stored or manipulated within a program to determine which operations can be performed on that data

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

What are primitive data types?

A

Common data types built into the language which can only contain one value

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

What are some examples of data types?

A

Integer

Float/real

Boolean

Char

String

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

What is an integer?

A

A positive or negative whole number

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

What is an example of an integer?

A

1

-98

38420

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

What is float/real?

A

A positive or negative number which can include decimal points

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

What is an example of a float/real?

A

1.849

-45.3

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

What is a Boolean?

A

Only one of True or False

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

What is an example of a Boolean?

A

True

False

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

What is a char?

A

A single character

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

What is an example of a char?

A

“a”

”#”

“5”

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

What is a string?

A

Not a primitive data type but a basic one in most languages

Collection of char data types

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

What is an example of a string?

A

“hello!”

“sh63£”

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

What is a composite/compound data type?

A

Built by combining primitive data types

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

What is an example of a composite/compound data type?

A

Record

Class

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

What is a data structure?

A

Collection of data organised to allow efficient processing

Lend themselves to different applications

Some highly specialised to specific tasks

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

What is an abstract data type?

A

Conceptual model

Describes how data is organised and which operations can be carried out on data

From perspective of end-user who doesn’t need to know how it’s implemented

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

What is binary?

A

Base 2

Uses 1s and 0s

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

List the forms of storage (e.g. bit, byte) from smallest to largest

A

Bit

Nibble

Byte

Kilobyte

Megabyte

Gigabyte

Terabyte

Petabyte

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

What is a bit?

A

A single 1 or 0

Smallest form of data storage in a computer

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

What is a nibble?

A

4 bits

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

What is a byte?

A

8 bits

2 nibbles

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

What is a kilobyte?

A

1000 bytes

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

What is a megabyte?

A

1000 KB

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

What is a gigabyte?

A

1000 MB

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

What is a petabyte?

A

1000 TB

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

What is a terabyte?

A

1000 GB

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

What is the largest number that can be stored by a nibble?

A

15

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

What is the largest number that can be stored by a byte?

A

255

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

What is 9 as a byte?

A

00001001

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

What is 102 as a byte?

A

01110011

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

What is hexadecimal?

A

Base-16

0-9 and A-F

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

What is each hex digit equivalent to?

A

A nibble

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

What are the uses of hex?

A

RBG = representing colours

MAC addresses

Memory dumps

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

What are the advantages of hex?

A

Easier to read and interpret

Fewer digits to represent the same value

Compared to binary, less likely that digit written down incorrectly

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

How do you convert denary to hex?

A

Convert into binary

Split into nibbles

Convert each nibble to hex

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

What is 87 in hex?

A

87 = 01010111 = 57

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

What is 210 in hex?

A

210 = 11010010 = D2

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

How do you convert hex to denary?

A

Convert all terms to denary (as per a nibble)

Times those numbers by 16 to the power of the nibble they are in minus 1 (if it’s the second nibble, times by 16^1)

Add numbers together

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

What is B9 in denary?

A

B9 = 176 + 9 = 185

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

What is 2CA in denary?

A

2CA = 512 + 192 + 10 = 718

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

What are two ways of representing negative numbers in binary?

A

Sign and magnitude

Two’s complement

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

What is sign and magnitude?

A

Changing left most bit (most significant bit) to represent if negative or not

0 = positive

1 = negative

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

What is -10 in sign and magnitude?

A

10001010

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

What is 103 in sign and magnitude?

A

01100111

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

What is two’s complement?

A

Changing left most bit (most significant bit) to present either 0 or -128

1 = -128

0 = 0

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

What is the method for converting a number to two’s complement?

A

Calculate number as positive binary value

Keep rightmost 1 and everything to the right of it the same

Flip all other value

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

What is -103 in two’s complement?

A

103 = 01100111

-103 = 10011001

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

What are the rules for binary addition?

A

1 + 0 = 1

1 + 1 = 0 carry 1

0 + 0 = 0

1 + 1 + 1 = 1 carry 1

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

What is 99 + 103 in binary?

A

99 = 01100011
103 = 01100111

01100011 \+  01100111 -------------------
11001010 -------------------
 11    111

= 11001010

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

What is the method for binary subtraction?

A

Convert numbers to two’s complement

Flip number you’re subtracting to a negative

Add numbers together

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

What is 75 - 36 in binary?

A

75 = 01001011

36 = 00100100
-36 = 11011100

01001011
+ 11011100
——————
100100111
——————-
1 11

= 00100111

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

What is fixed point binary?

A

Decimal point doesn’t move

Values before fixed point represent whole numbers

Values after fixed point represent fractions

Can be expressed using Two’s complement

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

What is the problem with fixed point binary?

A

Underflow - when number is too small to be represented

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

What is 5.75 in fixed point binary?

A

0101.1100

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

What is floating point binary?

A

Decimal place can be moved

Enables greater range of numbers and greater precision of numbers

More efficient way of storing binary numbers

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

What values are needed in floating point binary?

A

Mantissa

Exponent

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

What is the exponent?

A

Where the decimal point should move to

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

What is the mantissa?

A

Number being represented

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

Where does the binary point start?

A

Between the two leftmost bits

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

Which way should be binary point move in the exponent is positive?

A

Right

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

Which way should the binary point move if the exponent is negative?

A

Left

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

What should the bits be filled with when the exponent is negative?

A

If first number is 1, fill with 1s

If first number is 0, fill with 0s

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

What does normalised mean?

A

Standard form that should be used to represent numbers

Using normalisation, make sure digit after the binary point is SIGNIFICANT

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

What should normalised positive numbers start with?

A

01

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

What should normalised negative numbers start with?

A

10

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

What is overflow?

A

Where the number is too large a positive or negative to store

Crashes

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

What is underflow?

A

When the number is too small to be able to store

Crashes

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

What is the method of adding normalised form numbers?

A

Check if exponents are the same. If not, increase smaller exponent to match higher one

When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by

Add together just the mantissas using normal binary addition rules

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

What is the method of subtracting normalised form numbers?

A

Check if exponents are the same. If not, increase smaller exponent to match higher one

When doing this, need to adjust floating point on mantissa to the left, the number of places that you need to increase the exponent by

Negate the value to subtract

Add together just the mantissas using normal binary addition rules

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

What is a character set?

A

Standard collection of characters and the bit patterns used to represent them to allow computers to be able to communicate and exchange text efficiently

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

What does ASCII stand for?

A

American Standard Code for Information Interchange

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

What is ASCII?

A

Each character encoded with binary string of 7 bits

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

What is the 8th bit in ASCII often reserved for?

A

Error-checking/correction purposes

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

What is Unicode?

A

Uses more bits to store a character than ASCII, meaning a wider range of characters can be stored

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

What are the advantages of Unicode?

A

Can support languages with alphabet character sets larger than 26

Uses up to 32 bits to represent each character and can be used to represent special symbols

Supports over 4 billion possible codes

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

What version of ASCII is generally used?

A

UTF-16

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

What is bitwise manipulation?

A

Allows the programmer to work with sets of bits through logical bitwise operations

In both high and low level languages, used to perform a logical operation on each individual bit of a binary number

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

What are logical bitwise operations?

A

Directly supported by the processor, making them fast and efficient

Works on a single bit (or set of bits) within a binary string

Often used in low-level languages to manipulate the contents of registers or memory locations

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

What are the four logical bitwise operations?

A

AND

OR

XOR

NOT

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

What are binary or logical shifts?

A

Used to move binary digits

Can be used for arithmetic operations

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

What is a mask?

A

Bit pattern that’s been defined by a programmer, allowing specific bits in a piece of data to be tested or altered

Binary string used in conjunction with a logical bitwise operator to identify or manipulate a single bit (set of bits) within another binary string

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

What does the AND logical bitwise operation do?

A

Turn off/select bits

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

What is the result of AND operator applied to the binary string 10111100 using a mask of 11110000?

A

10110000

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

What does the OR logical bitwise operation do?

A

Turn on/select bits

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

What is the result of OR operator applied to the binary string 10111100 using a mask of 11110000?

A

11111100

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

What does the XOR logical bitwise operation do?

A

Reverse/toggle/complement/inverse

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

What is the result of XOR operator applied to the binary string 10111100 using a mask of 11110000?

A

01001100

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

What does applying shifts do?

A

Divide or multiply binary values

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

What are the uses of shifts?

A

Multiplying and dividing by a factor of 2

Encryption/decryption

Data collision detection in a network

Compression algorithms

Routing packets of data

Peripheral communication protocols

Graphics manipulation

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

How is a logical left shift completed?

A
  1. moving all the bits of the number one place to the left
  2. discarding the most significant bit
  3. putting a 0 into the empty place on the right
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
92
Q

How is a logical right shift completed?

A
  1. moving all bits of the number one place to the right
  2. discarding the least significant bit
  3. putting a 0 into the empty place on the left
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
93
Q

Can you logically shift signed numbers?

A

No

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

What type of shift should be used if the number is signed?

A

Arithmetic shift

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

What is a arithmetic shift?

A

Most significant bit is not shifted

Remaining bits are shifted

Sign of number is preserved and empty places are padded

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

What happens in an arithmetic left shift of a positive number?

A

Empty places are padded with 0

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

What happens in an arithmetic left shift of a negative number?

A

Empty places are padded with 0

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

What happens in an arithmetic right shift of a positive number?

A

Empty spaces are padded with 0

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

What happens in an arithmetic right shift of a negative number?

A

Empty places are padded with 1

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

What is a circular/cyclic shift?

A

No bits are lost

Bits are shifted out at one end into the other end of register

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

What are the uses of a cyclic shift?

A

In cryptography, cyclic shift of a code will always yield another code (Twofish cipher makes extensive use of cyclic shift because they are very fast operations)

Cyclic left shift used in some operations in modular arithmetic

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

How do you multiply 12 x 6 using shifts and addition?

A

12 x 6 = (12 x 4) + (12 x 2)

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

What is a tuple?

A

Ordered sequence of elements stored under a single identifier

Data is immutable

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

What does immutable mean?

A

Cannot be changed

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

What are the uses of a tuple?

A

Returning multiple items from a function

Passing multiple values to a subroutine but grouped under a single parameter

Often used when returning records from a database

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

What is used to define a tuple?

A

()

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

What is used to access a tuple?

A

[]

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

What is an array?

A

Static data structure

Can only store data of the same data type

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

What does static mean?

A

Length doesn’t change during run time

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

How is an array defined?

A

[]

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

What is a 2D array?

A

Lets you use the equivalent of rows and columns

Each element in an array becomes a separate array

Each coordinate needs two values

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

How is a 2D array accessed?

A

name[x,y]

name[x][y]

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

What is a stack?

A

Abstract data type

LIFO

Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)

114
Q

What does LIFO stand for?

A

Last In First Out

115
Q

What does LIFO mean?

A

Data is placed on top and removed from the top

116
Q

What are the operations that can be performed on a stack?

A

push(data)

pop()

peek()

is_empty()

is_full()

117
Q

What does push(data) do?

A

Adds an element to the top of the stack

118
Q

What does pop() do?

A

Removes an element from the top of the stack and returns it

119
Q

What does peek() do?

A

Returns a copy of the element on the top of the stack without removing it

120
Q

What does is_empty do in a stack?

A

Checks whether a stack is empty

121
Q

What does is_full do in a stack?

A

Checks whether a stack is at maximum when stored in a static structure

122
Q

What are the uses of a stack?

A

Holds return addresses when subroutines are called (recursion)

Undo in word

Back button in web browser

In calculations to ensure correct order of precedence

When dealing with interrupts (current process and values put on stack to allow ISRs to be completed)

123
Q

What is stack overflow?

A

Attempting to push onto a stack that’s full

124
Q

What is stack underflow?

A

Attempting to pop from a stack that’s empty

125
Q

How is a stack implemented?

A

Only need a single pointer to the top of the stack

Store maxSize of stack in variable to determine if stack full

Use top pointer or equivalent to keep track of top of stack

If stack empty, top = -1

126
Q

What is a a queue?

A

Abstract data type

FIFO

Static (if implemented using an array) but can be dynamic if implemented using other data structures (linked list)

127
Q

What does FIFO stand for?

A

First In First Out

128
Q

What does FIFO mean?

A

Data is placed at the rear/back of the queue and removed from the front

129
Q

What are the operations that can be performed on a queue?

A

enqueue(data)

dequeue()

is_empty()

is_full()

130
Q

What does enqueue(data) do?

A

Adds an element to the back of the queue

131
Q

What does dequeue() do?

A

Removes an element form the front of the queue and returns it

132
Q

What does is_empty do in a queue?

A

Checks whether the queue is empty

133
Q

What does is_full do in a queue?

A

Checks whether a queue is at maximum capacity (if size of queue is constrained)

134
Q

What are the uses of a queue?

A

Simulation

Print queue

Priority queue (each element in queue has a priority and are ordered by priority?

135
Q

How is a queue implemented?

A

Two pointers needed

Front pointer points to first item, initialised at 0

Rear pointer to last item, initialised at -1

Queue is empty when rear < front

136
Q

What is a circular queue?

A

Reuses the empty slots at the front of the array that are caused when elements are dequeued

As items enqueued and rear pointer reaches last position of the array, wraps around to start of array (as long as not full)

As items dequeued, front points wraps around until passed rear pointer (meaning queue is empty)

137
Q

How are the front and rear pointers moved in a circular queue?

A

rear = (rear + 1) % maxSize

front = (front + 1) % maxSize

138
Q

What is a record?

A

Data structures consisting of a fixed number of variables (FIELDS)

139
Q

What are fields in a record?

A

Each field has an IDENTIFIER and a data type

Each field can have a DIFFERENT DATA TYPE

140
Q

How are fields retrieved from records?

A

nameOfRecord.fieldname

141
Q

What is a linked list?

A

Abstract data type

DYNAMIC data structure used to hold a sequence

Other data types can be implemented using a linked list (stacks, queues)

Items in the sequence are in NON-CONTIGUOUS DATA LOCATIONS

Composed of nodes

Items stored in an order

142
Q

What does dynamic mean?

A

Size of the list can change during runtime

143
Q

What are the parts of a node?

A

The data (may be complex data structure)

A pointer (index) of the next node

144
Q

What are the pointers of a linked list?

A

Start pointer (identifying first node in the list)

nextFree pointer (showing index of next free space in the array)

145
Q

How is a linked list traversed?

A
  1. follow the start pointer to the first node. Examine data of this node
  2. if pointer of that node is not Null, follow pointer to next node
  3. repeat until end of list is reached (pointer of current node is Null)
146
Q

What is the code for traversing a linked list (implemented using an array)?

A

cp = start

while cp != None:
print(list[cp][0])
cp = list[cp][1]

147
Q

How is an item added to a linked list?

A
  1. start by checking if linked list is already full
  2. check if adding into an empty list
  3. checking if adding into the start of a list
148
Q

What are the benefits of a linked list?

A

Data can be easily added or removed in an order without needing to move lots of other data items

Can be used to implement more abstract data types (queues, stacks, binary trees)

149
Q

What are the problems of a linked list?

A

Traversal of a linked list is very slow

150
Q

What is a doubly linked list?

A

Contains pointers to the next node and the previous node

151
Q

What is a graph?

A

Abstract data type

Used to represent complex, non-linear relationships between objects

Consists of nodes (vertices) connected by edges (or arcs)

152
Q

What are neighbours in graphs?

A

When graphs are connected by an edge

153
Q

What is the degree of a node?

A

Number of nodes that it’s connected to

154
Q

What is a loop in a graph?

A

An edge that connects a node to itself

155
Q

What is a path in a graph?

A

Sequence of nodes connected by edges

156
Q

What is a cycle in a graph?

A

Closed path

Path that starts and ends at the same node with no node visited more than once

157
Q

What can graphs represent?

A

Social networking - nodes are individual people and edges represent that two people are acquaintances

Transport networks - nodes are towns and edges trainlines connecting two towns

Internet - nodes are routers and edges represent that two routers are connected

World Wide Web - nodes are webpages and edges represent that two pages are linked

158
Q

What is an undirected graph?

A

Edges don’t have arrows so the graph can be traversed in both directions

159
Q

What is a directed graphs?

A

Edges have arrows denoting direction of graph traversal

Edges don’t have arrows going both ways, they have two arrows if bidirectional

160
Q

What is an unweighted graphs?

A

The edges don’t have values associated with them

161
Q

What is a weighted graphs?

A

Edges have a value associated with them

Values could represent distance between places, time taken to travel, amount of network traffic

162
Q

What is an adjacency matrix?

A

Each row and column represents a node

The item at [row, column] indicates a connection

Unweighted graphs have a 1 at each edge

163
Q

What are the advantages of using an adjacency matrix to represent a graph?

A

Convenient to work with

Adding an edge is simple

164
Q

What are the disadvantages of using an adjacency matrix to represent a graph?

A

Spare graph with not many connections (edges) will leave most cells empty, wasting a lot of memory space

165
Q

What is an adjacency list?

A

List of nodes created and each node points to a list of adjacent nodes

Weighted graph represented as a dictionary of dictionaries

166
Q

What does traversing mean?

A

Visiting all the nodes

167
Q

What are the two types of graph traversal?

A

Depth first traversal

Breadth first traversal

168
Q

What data structure does a depth first traversal use?

A

Stack

169
Q

What is a depth first traversal suitable for?

A

Solutions where the answer is far from the node

Decision-based tree system

170
Q

What is the method of a depth first traversal?

A
  1. push first node onto the stack and mark this node as visited
  2. repeat the following until stack is emptya. visit next unvisited node
    b. push onto stack and mark as visited
    c. if no further unvisited connected nodes, pop from stack
171
Q

What data structure does a breadth first traversal use?

A

Queue

172
Q

What is a breadth first traversal suitable for?

A

Answer is closer to the node

173
Q

What is the method of a breadth first traversal?

A
  1. push first node onto queue and mark as visited
  2. repeat the following until all connected nodes to current node are marked as visiteda. visit next unvisited node
    b. push onto queue and mark as visited
  3. repeat following until queue is emptya. pop node from queue
    b. repeated following until all connected nodes to the current node are marked as visited
       i. visit next unvisited node
   ii. push onto queue and mark visited
174
Q

What is a tree?

A

Common abstract data type - should not be used as generalised abstract data structure

Connected, undirected graph with no cycles which is used for searching

Ideally, BUILD ONCE, TRAVERSE OFTEN

175
Q

What are the different types of tree?

A

Binary trees

Binary search trees

Expression trees

176
Q

What is a root in a tree?

A

Start node for traversals

If tree has a root, called a rooted tree

177
Q

What is a branch in a tree?

A

Path from the root to an end point

178
Q

What is a leaf in a tree?

A

End point

179
Q

What is the height of a tree?

A

Equal to the number of edges that connect root node to leaf node furthest from it

180
Q

What is a rooted tree?

A

Tree with one node designated the root

Root commonly situated in diagrams above other nodes

Nodes connected by parent-child relationships

Node can have any number of children

181
Q

What is a parent node?

A

Node that comes directly before another adjacent node (considered the child)

182
Q

What is a binary tree?

A

Rooted trees

Each node has a max of 2 child nodes

183
Q

Where is a binary tree used?

A

In compilers to build syntax trees

Within routers to store routing tables

184
Q

What was a binary search tree built for?

A

To speed up searching

185
Q

What is a binary search tree?

A

Nodes ordered to optimise searching

Rooted tree

Nodes of left subtree have values lower than root

Nodes of right subtree have values higher than root

186
Q

What are the different parts of a node?

A

The data (may be primitive or more complex object)

Left pointer to a child

Right pointer to a child

187
Q

What are the types of traversal of binary trees?

A

Pre-order

In-order

Post-order

188
Q

Which type of traversal should be done in exams when asked for a depth first traversal?

A

Post order

189
Q

What is a pre-order traversal?

A

Visit root, traverse left subtree, traverse right subtree

190
Q

What is an in-order traversal?

A

Traverse left subtree, visit root, traverse right subtree

191
Q

What is a post-order traversal?

A

Traverse left subtree, traverse right subtree, visit root

192
Q

How do you delete a leaf node?

A

Remove the node

193
Q

How do you delete a node with one child?

A

Remove that node

Link child to the parent node of the node removed

194
Q

How do you delete a node with two children?

A

Find a node that will preserve search tree properties and put it in the place of the deleted node

Node with the next largest key

195
Q

What are hash tables used for?

A

Quickly retrieve data from a large data set

Enabling efficient searching and maintaining of the hash table (adding, updating, deleting)

196
Q

How does a hash table work?

A

Use key value pairs

Key generated from data that needs to be stored and then put through hash function/algorithm producing an address, which is the address in the array where data should be stored

When retrieving data, same process followed and data can be instantly retrieved from address produced by hash function no matter size of array

197
Q

What should an effective hash table always have?

A

Free space

198
Q

What is hashing?

A

Applying a hashing algorithm (or hash function) to a key

199
Q

How is a hash table implemented?

A

Using an array because have to able to access each position of the array directly, which is done by specifying index of position within the array

200
Q

What are buckets?

A

Positions within an array in a hash table, each used to store data (can be single piece or more complex object like record)

201
Q

What is a key in a hash table?

A

Generated from data that needs to be stored

Must be stored as part of, or alongside, the data

202
Q

Why must the size of the array for a hash table be planned carefully?

A

Must be big enough to store all data but not so large that you waste table

203
Q

When is a hash table used?

A

When speed of insertion, deleting and looking up is a priority

204
Q

What is a hash function?

A

Algorithm that converts hash key to hash values

Good hash function essential for effective performance of hash table

Must be designed and tested to minimise number of possible collisions

205
Q

What are the requirements of a hash function?

A

Always produce same hash value for same key

Perform uniform distribution of hash values, meaning that every value has equal probability of being generated

Minimise clustering, which arises when many different keys produce the same hash value

Be very fast to compute

206
Q

How is data inserted into a hash table?

A

Use hash function to generate index of position in the array that will be used to store data

Key must be stored as part of, or alongside, data

207
Q

What is a collision in a hash table?

A

When two or more different keys produce the same hash value

Greater the LOAD FACTOR, greater chance of collisions

208
Q

What is the load factor?

A

How full the hash table is

209
Q

Why are collisions a problem?

A

Cannot store two sets of data at the same location

210
Q

How are collisions dealt with?

A

Linear probing

Chaining

211
Q

What is linear probing?

A

When key creates hash value that references a position that is already occupied, place data in next free position in hash table

Can probe sequentially or use an interval until empty bucket is found (SKIP FACTORING)

Each time this is done, increase likelihood of further collisions (clustering)

212
Q

How is data retrieved when linear probing is used?

A

Hash key to generate index value

Examine indexed position to see if key (stored together with data) matches key of data looking for

If no match, check each location that follows (at appropriate interval) until matching record found

If reach empty bucket without finding matching key, data not in hash table

213
Q

What is the problem with linear probing?

A

Significantly reduces efficiency of using hash table for searching

Worst case - have to inspect every position of the array

Why it’s important to design hash table to have extra capacity so hopefully algorithm will find free position not far from correct place

214
Q

What is chaining?

A

Using linked lists

215
Q

How does chaining work?

A

Instead of storing actual data in hash table, store pointer to location where data stored

Each data item stored as node with key value, data and pointer to next node

First value to be stored will have Null pointer as only item in list

When collision, pointer for next node at that location updated to point to new node

Creates chain of nodes whose keys resolve to the same hash value

216
Q

How is data retrieved when chaining is used?

A

Hash key to generate index value

Examine indexed position to get pointer to node at head of list

Examine key of node to see if matches key looking for

If not node looking for, follow linked list until find node look for

If end of list reached without finding matching key (or head pointer is Null), data not in hash table

217
Q

What is the worst case scenario using chaining

A

Every key hashes to same value and have to carry out linear search

218
Q

What problem is rehashing used to address?

A

Over time, items added and deleted from hash table

If hash table starts to fill up or large number of items in wrong place, performance of hash table will degrade

219
Q

What is rehashing?

A

New hash table is created (larger if needed)

Key for each item in existing table rehashed and item inserted into new hash table

If new table larger, hashing algorithm modified to generate larger range of value

Opportunity to review overall effectiveness of hash function and review how collisions handled

220
Q

What are some alternative hashing algorithms?

A

All hashing algorithms involve mod function at some point as hash address has to be range of table addresses

Mid square

Folding method

221
Q

How are deletions dealt with in a hash table?

A

Items to be deleted must be replaced with dummy item or marker

When searching for item which hashes to that spot, if not found, search will continue until it’s found or free space located

If new item is to be added and address contains dummy item, will replace dummy

222
Q

What is a logic gate?

A

Fundamental component of a digital circuit

Each gate has one or more inputs and produces single output that depends on the inputs

Multiple can be combined to make complex circuits to carry out processing

223
Q

What is a logic circuit?

A

Multiple logic gates combined

224
Q

What are the inputs of a logic circuit?

A

Determined by voltage that flows around the system

High voltage = 1/True
Low voltage = 0/False

225
Q

What is the output conventionally labelled as in a logic circuit?

A

Q

226
Q

What is an AND gate?

A

Looks like a D

Both inputs have to be true for the output to be true

227
Q

What is an example expression for an AND gate?

A

Y = A ∧ B

228
Q

What is an OR gate?

A

Looks like an umbrella

Either inputs must be true for the output to be true

229
Q

What is an example expression for an OR gate

A

Y = A ∨ B

230
Q

What is a NOT gate?

A

Looks like a triangle with a dot on the end

Reverses the input

231
Q

What is an example expression for a NOT gate?

A

Y = ¬A

232
Q

What is an XOR gate?

A

OR gate with an additional line

Either inputs but not both must be true for output to be true

233
Q

What is an example expression for an XOR gate?

A

Y = A ∨ B

But with OR symbol underlined

234
Q

What is the order of precedence of logic gates?

A

NOT

AND

OR

235
Q

What is a truth table?

A

Shows all possible inputs and outputs from a logic gate or circuit

Inputs can be expressed in any order

236
Q

What the Boolean notation for the Boolean expression (A AND B) OR NOT (D AND E)?

A

(A ∧ B) V ¬(D ∧ E)

237
Q

What is a Karnaugh map?

A

Version of a truth table for a Boolean expression that’s laid out in a way that makes it easier to simplify

238
Q

What are the rules for groups in Karnaugh maps?

A

Sizes of groups must be to the power of 2 (2, 4, 8)

Groups should be as large as possible

Every 1 must be included in a group

Groups can overlap each other

Groups can wrap around sideways and top to bottom

239
Q

How are Boolean expressions simplified?

A

Manipulated algebraically to form simpler expressions that implement the same logic

240
Q

Why should Boolean expressions be simplified?

A

Allow simpler circuit to be produced with fewer logic gates

Reduce cost of circuit

Reduce amount of heat generated

Reduce processing time

241
Q

What is another word for an AND logic gate?

A

Conjunction

242
Q

What is another word for an OR logic gate?

A

Disjunction

243
Q

What is another word for an XOR logic gate?

A

Exclusive disjunction

244
Q

What is another word for a NOT logic gate?

A

Negation

245
Q

What is equivalence?

A

The same as

246
Q

What is the symbol for equivalence?

A

≡

247
Q

What is De Morgan’s law?

A

Either logical function AND or OR may be replaced by the other, given certain changes to the equation

248
Q

How does De Morgan’s law apply to Boolean expressions?

A

¬(A v B) ≡ ¬A ^ ¬B

¬(A ^ B) ≡ ¬A v ¬B

249
Q

What is the distribution law?

A

Allows for the multiplying or factoring out of an expression

250
Q

What must be true to use the distribution law?

A

Term outside the brackets doesn’t appear inside the brackets

Operator is different

251
Q

How does the distribution law apply to Boolean expressions?

A

X ^ (Y v Z) ≡ (X ^ Y) v (X ^ Z)

X v (Y ^ Z) ≡ (X v Y) ^ (X v Z)

252
Q

What is the association law?

A

Allows for removal of brackets from an expression and the regrouping of variables

253
Q

What must be true to use the association law?

A

Term outside the brackets doesn’t appear inside the brackets

Operator is the same

254
Q

How does the association law apply to Boolean expressions?

A

X ^ (Y ^ Z) ≡ (X ^ Y) ^ Z ≡ X ^ Y ^ Z

255
Q

What is the double negation rule?

A

Two negatives make a positive

256
Q

How does the double negation rule apply to Boolean expressions?

A

¬¬A ≡ A

257
Q

What is the absorption rule?

A

The second term inside the bracket can always be eliminated and absorbed by the term outside the bracket

258
Q

What must be true to use the absorption law?

A

Term outside the brackets appears inside the brackets

Operators must be different

259
Q

How does the absorption rule apply to Boolean expressions?

A

X v (X ^ Y) ≡ X

X ^ (X v Y) ≡ X

X v X ^ Y ≡ X

260
Q

What are the general rules using AND?

A

X ^ 0 ≡ 0

0 ^ X ≡ 0

X ^ 1 ≡ X

X ^ X ≡ X

X ^ ¬X ≡ 0

261
Q

What are the general rules using OR

A

X v 0 ≡ X

0 V X ≡ X

X v 1 ≡ X

X v X ≡ X

X v ¬X ≡ 1

262
Q

What is (A ᴧ ¬B) v B simplified?

A

(A v B) ^ (B v ¬B)

(A v B) ^ 1

(A v B)

263
Q

What is A ^ B ^ ¬C V A ^ ¬C simplified?

A

(A ^ B ^ ¬C) v (A ^ ¬C)

D = A ^ ¬C

(D ^ B) v D

D

A ^ ¬C

264
Q

What is ¬B ^ ¬(¬A V ¬B) simplified?

A

¬B ^ (A v B)

(¬B ^ A) v (¬B ^ B)

(¬B ^ A ) v 0

¬B ^ A

265
Q

What is a flip flop?

A

Elemental sequential logic circuit that can store on bit and flip between two states, 0 and 1

266
Q

What is D-type flip flop?

A

Synchronous sequential circuit that can be used to store the value of single binary digit

Has internal loop, allowing the previous output value to be stored

267
Q

What are the two external inputs of a D-type flip flop?

A

Data signal (D)

Clock signal

268
Q

What happens in a D-type flip flop when the clock signal is low (0)?

A

Changes at D make no difference to output

269
Q

What happens in a D-type flip flop when the clock signal is high (1)?

A

Value of input D will appear at output Q

270
Q

What are the problems with a D-type flip flop?

A

If there are changes in the data during the period when the clock signal is high, output at Q will chance in line with D, which might not be a desirable feature of the circuit

271
Q

What is an edge-triggered D-type flip flop?

A

Introduces delay in processing the clock signal

D is only processed at rising edge of each signal change from the clock

On rising edge of each clock signal, state of D is accepted at output Q (updated to reflect this

Once clock signal input goes low, state of circuit won’t change and will continue to output (thus store) whatever value was already present on its output

272
Q

What is the clock needed for in a flip flop?

A

Synchronising change of state of flip flop circuits

273
Q

What are D-type flip flops used for?

A

Creating registers

Shift operations (multiplication and division)

Intermediate storage needed during arithmetic operation

Static RAM

274
Q

What is static RAM?

A

Faster and more expensive than regular dynamic RAM, which must be periodically refreshed

Typically used for cache memory which DRAM used for main memory

275
Q

What is a half adder?

A

Circuit that performs the addition of two bits

Takes input of two bits (A and B) and outputs the sum (S) and the carry (C)

276
Q

What logic is the carry column produced by?

A

A AND B

277
Q

What logic is the sum column produced by?

A

A XOR B

278
Q

What is the problem with a half-adder?

A

Only has two inputs so cannot use the carry from a previous addition as a third input to a subsequent addition

Can only add 1-bit numbers

279
Q

What is a full adder?

A

Combines two half-adders

Three inputs of A, B and carry bit Cin

Two outputs of S and Cout

280
Q

Why would full adders be concatenated?

A

To add numbers together where each has multiple bits

Computer Science (8 decks)

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