Data Structures

xazucicu's version from 2015-05-20 03:00


Question Answer
What is a stack?Its a data structure in which the elements are added and removed from one end only. (LIFO)
What is LIFO?Last In First Out
What is the objective of white box testingTo ensure that the every part of the method or algorithm is executed at least once. To ensure everything works properly
What does the push() method do? It adds a new DataElement item to the stack
Equivalence Setsinputs in the same equivalence category should have the same outputs. (Ex: if a negative number should return false then all negative inputs should return false)
What does the initializeStack( ) do?It Initializes the stack to an empty state.
isEmptyStack() does what?determines if the stack is empty. returns true if it is and False it is not empty. O(1)
isFullStack()determines if the stack is full. returns True if it is or false if it isn't. O(1)
top() returns the top element of the stack. O(1)
What are the preconditions of top( ) ?the stack must exist and cannot be empty.
pop()removes the top element of the stack. O(1)
Preconditions for pop( ) ?stack must exist. It cannot be empty.
what is StackClass()?it is the default constructor for the StackClass. Creates an array size 100 to implement stack
PostCondition for StackClass()?sets variable stackTop = 0; And initializes list array (list = new DataElement[maxStackSize];
what is the Big O notation for copy contructorO(n)
What is a queue?A data structure in which the elements are added at one end, called the rear or back and deleted from the other end called front or first
What is FIFO?First In First Out used in queues.
initializeQueue()?initializes queue to an empty state
isEmptyQueue()?determines whether the queue is empty
isFullQueue()?returns if the queue is full
front()?returns the front, the first element of the queue.
back()?returns the last element of the queue
addQueue()?adds new element to the rear of the queue
deleteQueue() ?removes the front element of the queue
what is the root of a binary tree?it is the top node of the tree
what is a leaf in a binary tree?it is a node that does not have any children
maximum children for each parent in a tree?each parent can have up to 2 children. but can have less
what is the Big O for a binary tree?O(logN)
what is inOrder traversal?the left subtree is visited first then the node. then the right subtree
height of tree?length of longest path from root down to leaf
when is a tree balanced?when the height is O(logN)
height of parent formula?take the max height between the children and add 1 to the bigger height
AVL trees?require the height heights of the left and right children of every done to differ by at most plus or minus 1