Brainscape's Knowledge GenomeTM

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


See full index

Comp Sci 1 > 1.4 Data types, structures and algorithms > Flashcards

1.4 Data types, structures and algorithms Flashcards

1
Q

What is a primitive data type

A

Basic type is a data type provided by a programming language as a basic building block

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

What are the common primitive data types (5)

A

Integer
Floating point/ real
Character
String
Boolean

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

What do integers hold

A

Whole numbers

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

What do floating points/ reals hold

A

A number with a fractional part

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

What do characters hold

A

A single alphanumeric character or special symbol

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

What do strings hold

A

Multiple alphanumeric or special symbols

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

What do booleans hold

A

The value 0 or 1 sometimes represented by False or True

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

Why do we use binary

A

Because computers can only represent values as on or off; because they are reliant on electricity. It is also very reliable ; the computer always receives the correct data.

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

Why doe we use hexadecimal(4)

A

Much easier to read than a long string of binary
Quicker to write and take up less space
Less chance of making an error while typing
Very easy to convert to and from binary

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

What is hexadecimal used for (4)

A

Colours
MAC addresses
Assembly languages
Machine Code

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

Define Bit

A

the smallest unit of data in a computer, holds either a 0 or a 1

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

Define nibble

A

A sequence of 4 bits

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

Define Byte

A

A sequence of 8 bits

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

How many bits are required to hold a value of 2^n or below

A

n

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

What are the prefixes for bytes

A

Kilobyte - kB - 10^3
Megabyte - MB - 10^6
Gigabyte - GB - 10^9
Terabyte - TB - 10^9
Kibibyte - kiB - 2^10
Mebibyte - Mib

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

How do character sets work

A

Each single alphanumeric and special character is represented by an individual binary value

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

What is ASCII?

A

7 bit character set that can hold 128 characters used mostly for english

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

What is extended ASCII

A

8 bit character set that can hold 256 characters with extra characters for different langauages

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

What is Unicode?

A

16 or 32 bit character set that can hold characters for many languages

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

What is the comparison operator for equal

A

==

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

What is the comparison operator for not equal

A

<> or !=

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

What is the comparison operator for greater than

A

>

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

What is the comparison operator for less than

A

<

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

What is the comparison operator for greater than or equal

A

> =

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

What is the comparison operator for less than or equal

A

<=

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

What happens when the result of a binary cacluation is greater than the assigned number of bits can hold

A

Binary overflow error

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

What is the range of values a binary number can hold with n digits

A

0 - 2^n -1

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

What is the most significant bit of a binary number

A

The first bit

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

What is sign and magnitude

A

Method where the most significant bit represents either + (0) or - (1)

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

Why is sign and magnitude not used

A

Normal arithmetic does not work properly when using it, meaning more complicated circuits would have to be designed

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

What is two’s complement?

A

Method by which the most significant bit is changed from positive to negative

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

How to convert a number to negative using twos complement

A

Traverse from right to left until you find the first 1, after this one flip the remaining bits

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

What is the range of a twos complement number with n bits

A

-(2^(n-1)) <-> 2^(n-1) -1

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

What is fixed point binary

A

Method of storing reals which uses a specified number of bits where the decimal point is fixed

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

Advantage of fixed point binary

A

Easier to process

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

Disadvantage of fixed point binary

A

Cannot represent the range or accuracy of numbers that may be required

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

How does the accuracy of a fixed point binary number vary with range

A

Inversely

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

What is floating point representation

A

A method where the decimal place in a number can vary based on the exponent.

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

What is the mantissa?

A

The part of a floating point number that holds the actual number

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

What is the exponent

A

The part of a floating point number that sets the position of the floating pint

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

How does floating point work

A

Floating point starts in between 1st and 2nd bit and exponent moves point to the right x times when the exponent is equal to x. If x is negative then to the left

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

What is normalisation

A

The process of moving the floating point to achieve the maximum level of precision for a given number of bits

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

How do we normalise

A

Make the first digit after the binary point a significant digit (e.g. 1 id msb is 0 and 0 if msb 1) and changing the exponent accordingly

44
Q

What is bit manipulation

A

The changing of the values in a binary value using some sort of operation

45
Q

Why are bits manipulated

A

Error detection and correction algorithms
Data encryption
Data compression

46
Q

How can we manipulate bits

A

Shifts
Bitwise operations

47
Q

What is a logical shift right

A

The shifting of bits to the right by one place, putting the least significant bit into the carry bit

48
Q

What is a logical shift left

A

The shifting of bits to the right by one place, putting the most significant bit into the carry bit

49
Q

What is the purpose of logical shifts

A

Right can be used to examine least significant bit
Right divides by 2 left multiplies by 2

50
Q

What is the problem with logical shifts

A

Will not work with twos complement numbers as number may lose its negative nature

51
Q

What is an arithmetic shift right

A

The shifting of bits to the right by one place, putting the least significant bit into the carry bit. The new msb is the value of the old msb

52
Q

What is an arithmetic shift left

A

The shifting of bits to the left by one place, putting the second most significant bit into the carry bit to preserve the sign bit. A 0 fills on the left

53
Q

What is a circular shift right

A

LSB moved into carry bit, carry bit moved into MSB

54
Q

What is a circular shift left

A

MSB moved into carry bit, carry bit moved into LSB

55
Q

When does and AND return true

A

when both inputs are true

56
Q

When does an OR return true

A

When either or both inputs are true

57
Q

When does a XOR return true

A

When either but not both inputs are true

58
Q

When does a NOT return true

A

When the input is false

59
Q

When does a NOT return false

A

When the input is true

60
Q

What is a boolean mask

A

A set of numbers that is used with an original number and a boolean operator to set, clear or toggle the input of bits

61
Q

What is an AND bitwise used for

A

Clear a particular bit, leaving others unchanged

62
Q

What is an OR birwise used for

A

Set a particular bit leaving others unchanged

63
Q

What is a XOR bitwise used for

A

Toggle a particular bit leaving others unchanged

64
Q

What is an elementary data type

A

Data type that holds a single data value

65
Q

What is a composite data type

A

Data type that can be constructed by compounding other data types

66
Q

What is an abstract data type

A

A data type created by the programmer which is a logical description of how we view the data and possible operations

67
Q

What is a queue

A

A First In First Out Data Structure. (FIFO)

68
Q

Example uses of a queue

A

Output waiting to be printed
Characters typed on a keyboard are held in a queue on a keyboard buffer

69
Q

What are the psuedocode methods of a queue

A

enqueue (item)
dequeue
isEmpty
isFull
size

70
Q

What is the problem with non circular queues

A

Once the back of the queue is reached no more data can be added even if there are free spaces at the front of the queue

71
Q

How does a circular queue work

A

Has a pointer to the start and end of the queue. When space is freed up at front of queue it becomes the back so more data can be added. Pointer is modded by maxsize such that it loops

72
Q

What is a priority queue

A

A queue in which some items are allowed to jump the queue if they are determined to have a higher priority

73
Q

What is a static data structure

A

One that is fixed in size e.g. array

74
Q

What is a dynamic data structure

A

One that can grow and shrink by allocating or deallocating memory from the heap e.g. python list

75
Q

What are the advantages of a queue

A

Simple to program
Predictable memory usage

76
Q

What are the disadvantages of a queue

A

Fixed length
Single pass
Can’t reuse spaces

77
Q

What are the advantages of a circular queue

A

Can reuse free spaces

78
Q

What are the disadvantages of a circular queue

A

Slightly more complex to program

79
Q

What are the advantages of a priority queue

A

Gives preference to more important items

80
Q

What are the disadvantages of a priority queue

A

Additional processing required to keep order

81
Q

When might a priority queue be used

A

Accident and emergency

82
Q

What is the purpose of abstract data types

A

To be able to deal with more complex problems with more efficient problem solving methods

83
Q

List psuedocode operations

A

isEmpty()
append(item)
remove(item)
count(item)
len(item)
index(item)
insert(pos, item)
pop()
pop(pos)

84
Q

What is a linked list

A

A list of nodes or elements of a data connected by pointers with a starting point and a next free pointer at the front/back respectively

85
Q

What is a stack

A

A stack is a Last in First out (LIFO) abstract data structure

86
Q

Stack psuedocode methods

A

push(item)
pop()
isFull()
isEmpty()
peek()
size()

87
Q

What is stack overflow?

A

Attempting to push to a stack that’s full

88
Q

What is a call stack?

A

A system level data structure that provides the mechanism for passing parameters and return addresses to subroutines

88
Q

What is stack underflow?

A

Attempting to pop from a stack that is empty

89
Q

What is a hash table

A

A data structure that offers very fast insertion and searching.

90
Q

how does a hash table work?

A

Stores items in it using a hashing algoritm to decide its address. This algorithm can then be used again on search data to find where it is stored

91
Q

What is a collision in a hash table

A

When two pieces of data (primary keys) are assigned to the same address

92
Q

How are collisions dealt with in a hash table

A

An address for the colliding data is found in reference to the original location, e.g. go right till there is a free space

93
Q

What must be done in a hash table when an item is deleted

A

Item must be replaced by a dummy item or marker that will later be treated as a free space

94
Q

What is a dictionary

A

An abstract data type made up of associated pairs, each pair has a key and value. Value is accessed via the key

95
Q

How might a dictionary be used

A

A translation program
Other data structures maybe be implemented a s dictionary, e.g. trees
Ascii or unicode tables

96
Q

What is a graph?

A

An abstract data structure representing complex relationships. A set of vertices or nodes connected by edges or arcs

97
Q

What is an directed graph

A

One that does not have arrows on edges indicating direction

98
Q

What is a weighted graph

A

A weighted graph is a graph that has a numerical value associated with each edge.

99
Q

What is a directed graph

A

One that has arrows on its edges representing direction

100
Q

How can a graph be represented

A

An agency matrix
An agency list

101
Q

What is an adjacency matrix?

A

A table where each row and column represents a node. An item at [row,column] indicates a connection

102
Q

What is an agency list

A

A list which stores nodes paired with a list of nodes they are connected to

103
Q

What are the advantages of an adjacency matrix

A

Continent to work with
Adding edge is simple

104
Q

What is the disadvantage of an adjacency matrix

A

A sparse graph with not many edges will leave most of the cells empty, wasting a lot of memory space

105
Q
A

Comp Sci 1 (6 decks)

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