1.4.1 Data Types Flashcards
Primitive Data Types
“The basic data types provided by a programming language as building blocks. Most languages allow more complicated composite types to be recursively construction starting from basic types. E.g. char, integer, float, Boolean. As an extension a ‘string’ data type is constructed behind the scenes of many char data types.”
Integer
“A data type used to store positive and negative whole numbers
Real
“A data type used to store an approximation of a real number in a way that can support a trade-off between range and precision. A number is, in general, represented approximately to a fixed number of significant digits and scaled using an exponent.”
Floating Point
“A data type used to store an approximation of a real number in a way that can support a trade-off between range and precision. A number is, in general, represented approximately to a fixed number of significant digits and scaled using an exponent.”
Character
“A single alphanumeric character or symbol.”
String
“A sequence of alphanumeric characters and or symbols. e.g. a word or sentence.”
Boolean
“Used to store the logical conditions TRUE / FALSE. Often translated to On/Off, Yes/No etc.”
Binary
“Binary describes a numbering scheme in which there are only two possible values for each digit: 0 and 1. The term in computing refers to any digital encoding system in which there are exactly two possible states. E.g. in memory, storage, processing and communications, the 0 and 1 values are sometimes called “low” and “high”, respectively.”
Sign and Magnitude
“A method in computing of being able to store and represent floating point real numbers (both positive and negative) as a string of pure binary digits. Uses the concepts of two’s complements, mantissa and exponent.”
Two’s Complement
“A method in computing of being able to store negative numbers as string of pure binary digits. It works by turning the MSB into a sign bit, where 0 represents a positive number and 1 represents a negative.”
Hexadecimal
“A numerical system of notation which uses 16 rather than 10 as its base. The 16 Hex base digits are 0-9 and the letters A-F.”
Denary
“A numerical system of notation which uses 10 as its base. The 10 Decimal base digits are 0-9.”
Floating Point Arithmetic
“The mathematical process of performing simply calculations on more than one floating-point number stored in binary notation.”
Bitwise Manipulation
“The act of algorithmically manipulating bits or other pieces of data shorter than a word. Programming tasks that require a bit manipulation include low-level device control, error detection and correction algorithms, data compression, encryption algorithms, and optimisation.”
Shifts
“An operation that moves the bits held in a register, called the shift register, either to the left or the right. There are three different types of shift: arithmetic shift, logical shift and cyclic shift. They are distinguished by what happens to the bits that are shifted out of the register at one end and what is moved in to fill the vacant space at the other end.”
AND
“A logical operator used within a program. AND works by only returning TRUE if both values being compared are TRUE.”
OR
“A logical operator used within a program. OR works by returning TRUE as long as either value being compared is TRUE.”
XOR
“A logical operator used within a program. XOR stands for exclusive OR. It will return TRUE if the two items being compared are different.”
Character Sets
“The set of symbols that may be represented in a computer at a particular time. These symbols, called characters, can be letters, digits, spaces or punctuation marks, the set includes control characters.”
ASCII
America Standard Code for Information Interchange: “A character set devised for early telecommunication systems but proved to be ideal for computer systems. ASCII codes use 7-bits giving 32 control codes and 96 displayable characters (the 8th bit is often used for error checking).”
UNICODE
“Standard character set that replaces the need for all the different character sets. It incorporates characters from almost all the world’s languages. It is a 16-bit extension of ASCII.”
Adding data to a Linked List
- Store the data at the location indicated by the free storage pointer
- Alter the free storage pointer to the next free storage space
- Work out where in the list the new item should be inserted
- Set the pointer for the item that will precede it to the new data item
- Update the pointer for the new data item to that previously stored in the item that preceded it
Deleting data from a Linked List
IF item to remove is in first position THEN
Update starting pointer value to pointer value of item you want to delete
Update free pointers
EXIT PROCEDURE
ELSE
Update pointer value in the preceding node from the one you want to delete to the value of the pointer in item to be removed
Update free pointers
EXIT PROCEDURE
END IF
Traversing a Linked List
Set the pointer to the start value Repeat Go to node(pointer value) Output data at node Set the pointer to the value of the next item pointer at the pointer Until pointer = 0
Searching a Linked List
Set the pointer to the start value
Repeat
Go to node(pointer value)
IF data at node is search item
output value and stop
Else
Set the pointer to value of next item pointer at the node
Endif
Until pointer = 0
Output “data item not found”Traversing a Graph using the Depth-first method
- PUSH the first vertex onto the stack
- Mark vertex as visited
- Repeat
- Visit next unvisited vertex to the one on top of the stack
- Mark as visited
- PUSH vertex onto stack
- IF no vertex to visit
- POP vertex off stack
- END IF
- Until stack is empty
- Traversing a Graph using the Breadth-first method
- PUSH the first vertex onto the stack
- Mark vertex as visited
- Repeat
- Visit unvisited vertex’s connected to first vertex
- PUSH vertex’s onto queue
- Until all vertex’s visited
- Repeat
- POP next vertex from queue
- Repeat
- Visit unvisited vertex’s connected
- to current vertex
- PUSH vertex onto queue
- Until all vertex’s visited
- Until queue is empty
Inserting into a Binary Search Tree
- If tree is empty enter data item at root and stop.
- Current node = root.
- Repeat steps 4 & 5 until current node is null.
- If new data item is less than value at current node go left, else go right.
- Current node = node reached (null if no node).
- Create new node and enter data.
Traversing a Binary Search Tree using the Preorder method
- PREORDER_TRAVERSE(tree)
- Visit root of tree
- PREORDER_TRAVERSE(left subtree)
- PREORDER_TRAVERSE(right subtree)
Traversing a Binary Search Tree using the Inorder method
- INORDER_TRAVERSE(tree)
- INORDER_TRAVERSE(left subtree)
- Visit root of tree
- INORDER_TRAVERSE(right subtree)
Traversing a Binary Search Tree using the Postorder method
- POSTORDER_TRAVERSE(tree)
- POSTORDER_TRAVERSE(left subtree)
- POSTORDER_TRAVERSE(right subtree)
- Visit root of tree
Inserting into a Stack
- Check to see if stack is full.
- If the stack is full report an error and stop.
- Increment the stack pointer.
- Insert new data item into location pointed to by the stack pointer and stop.
Deleting data / Reading from a Stack
- Check to see if stack is empty.
- If the stack is empty report an error and stop.
- Copy data item in location pointed to by stack pointer.
- Increment the stack pointer.
Inserting into a Queue
- Check to see if the queue is full.
- If the queue is full report and error and stop.
- Insert new data item into location pointed to by the head pointer.
- Increment the head pointer and stop.
Deleting data / Reading from a Queue
- Check to see if queue is empty.
- If the queue is empty report error and stop.
- Copy data item in location pointed to by the tail pointer.
- Increment tail pointer and stop.
Searching a Hash Table
- Feed in key to Hash function
- Go directly to array index (HashValue)
- IF (value = value searching for) THEN
- Value found
- ELSE
- Follow linked list in sequence until
- value found
- END IF
Inserting into a Hash Table
- Feed in key to Hash function
- Go directly to array index (HashValue)
- IF (location is empty) THEN
- Insert Value
- ELSE
- Follow linked list in sequence until
- free space found
- Insert Value
- END IF
Deleting data from a Hash Table
- Feed in key to Hash function
- Go directly to array index (HashValue)
- IF (value = value searching for) THEN
- Mark as empty
- ELSE
- Follow linked list in sequence until
- value found
- Mark as empty
- Update free pointers in linked list
- END IF
