1.4 Data types and structures

• List datatypes

  Integer

  Float

  Character

  String

  Boolean
• What is a bit shift

  An operation that moves all bits by a certain number of places left or right
• What does a bitwise operation do

  Takes binary numbers and does the corresponding logic operation to pairs of bits
• What is a bitmask

  Data that is used in a bitwise operation
• What is an array


  A set of data items with the same type

  It is static - size is fixed during runtime

  Held in a contiguous block of memory

  Zero based
• Types of data structures

  Arrays

  Graphs and trees

  Lists

  Tuples

  Records
• Defining quality of a list

  Not fixed size during runtime so items can be added and removed
• Defining quality of a tuple

  Immutable list (cannot be changed)
• Defining quality of a record

  multiple related attributes of different data types
• Facts of a stack

  LIFO data structure (last in first out)

  Uses a single pointer at the top of the stack

  Push and pop items from a stack
• Uses of stacks

  Back/Forward button on browsers

  Interrupts

  Recursion
• Facts of a queue

  FIFO dynamic data structure (first in first out)

  A queue may be linear or circular

  Uses a pair of pointers, one for front and one for back
• Uses of queues

  Print jobs

  CPU processing
• What is a tree

  A tree is a unidirectional non linear data structure with a root node
• What is a binary search tree

  A tree with a maximum of two child nodes

  The left child is smaller than the parent while the right is greater
• How to remove a node from a binary search tree

  If the node is a leaf, remove the pointer to the node

  If there is only one child, copy the child onto the node and delete the child

  If there are two children, replace the node with an empty node with pointers to both children
• What is a linked list


  A data structure that has a data field and one or two address fields that point to the next and previous items in the list
• Facts of a linked list

  May not be stored in contiguous memory

  If there are no further items that is shown by a null value

  If the list is empty the start value will be null
• Uses of linked lists

  To keep a list of items with the same hash value in the hash table

  Used with graphs to make adjacency lists

  Songs in music playlists
• What are the boolean laws

  Commutative

  Associative

  Distributive

  Absorption

  De morgans
• What is the commutative law

  a AND b = b AND a

  a or b = b or a
• What are the associative laws

  (a AND b) AND c = a AND (b AND c)

  (a OR b) OR c = a OR (b OR c)
• What are the distributive laws

  a AND (b OR c) = (a AND b) OR (a AND c)

  a OR (b AND c) = (a OR b) AND (a OR c)
• What are the absorption laws

  a AND (a OR b) = a

  a OR (a AND b) = a
• What is de morgans law

  NOT(a AND b) = (NOT-a OR NOT-b)

  NOT(a OR b) = (NOT-a AND NOT-a)
• What is the double negation law

  NOT-NOT-a = a
• What is a half adder

  A combination of a XOR and an AND gate that will output the sum and carry of the addition of two bits
• What is a full adder

  Two half adders and an OR gate that can sum and carry two inputs and a carry-in
• What is overflow


  When the number is too large to be stored by the computer
• What is underflow


  When the number is too close to zero to be stored by the computer
• What gates determine sum and carry for a half adder

  Sum - XOR gate

  carry - AND gate
• Where are D-Type flip flops used

  As memory cells in SRAM that store a single bit
• When does a D-Type flip flop change state

  They are positive edge triggered, which means they only change state on the rising edge of the clock
• What is a karnaugh map

  A way to represent the output of logic functions in a grid
• How to group ones in a karnaugh map

  Do not include any zeros

  No diagonal groupings

  Must contain 2^n groups

  Each group should be as large as possible

  Groups may wrap around the map

  As few groups as possible
• What must you remember for making karnaugh maps

  Change the bits on the axis one at a time