Shared Flashcard Set

Details

CPE103 Midterm 1
n/a
62
Computer Science
Undergraduate 1
05/05/2009
Click here to study/print these flashcards.

Create your own flash cards! Sign up here.

Additional Computer Science Flashcards

 

 

Cards

Term
Stack (LL)
pop()
 Definition
O(1)
Term
Stack (LL)
push()
 Definition
O(1)
Term
Stack (LL)
peek()
 Definition
O(1)
Term
Stack (LL)
isEmpty
 Definition
O(1)
Term
Stack (Array)
pop()
 Definition
O(1)
Term
Stack (Array)
push()
 Definition
O(1)
Term
Stack (Array)
peek()
 Definition
O(1)
Term
Stack (Array)
isEmpty()
 Definition
O(1)
Term
Queue (LL)
dequeue()
 Definition
O(1)
Term
Queue (LL)
enqueue()
 Definition
O(1)
Term
Queue (LL)
isEmpty()
 Definition
O(1)
Term
Queue (Circular Array)
dequeue()
 Definition
O(1)
Term
Queue (Circular Array)
enqueue()
 Definition
O(1)
Term
Queue (Circular Array)
isEmpty()
 Definition
O(1)
Term
Big Oh
 Definition
The Upperbounds of a function
Term
Big Omega Ω
 Definition
The lowerbound of a function
Term
Big Theta Θ
 Definition
The upper and lowerbound of a function
[this must be the exact same power]
Ex: f(n)= 3n^3, g(n) = 4n^3
Θ(n) = n^3
Term
Little oh
 Definition
Is an upperbound, but is NOT a lower bound. [Must be big Oh, but not big Omega or big theta]
Term
List (LL)
Summing/Max/min
 Definition
O(N)
Term
List (LL)
Access ith element
 Definition
O(N)
Term
List (LL)
Search unsorted
 Definition
O(N)
Term
List (LL)
Search sorted
 Definition
O(N)
Term
List (LL)
Insert w/o changing order
 Definition
O(1)
Term
List (LL)
Add to end of list
 Definition
O(N)
Term
List (LL)
Add to sorted spot
 Definition
O(N)
Term
List (LL)
Delete first element
 Definition
O(1)
Term
List (LL)
Delete last element
 Definition
O(1)
Term
List (LL)
Find and delete element (sorted or not)
 Definition
O(N)
Term
List (Array)
Summing/max/min
 Definition
O(N)
Term
List (Array)
Access ith element
 Definition
O(1)
Term
List (Array)
Search unsorted
 Definition
O(N)
Term
List (Array)
Search sorted
 Definition
O(logN)
Term
List (Array)
Insert w/o changing order
 Definition
O(N)
Term
List (Array)
add to end of list
 Definition
O(1)
Term
List (Array)
Add to sorted spot
 Definition
O(N)
Term
List (Array)
Delete first
 Definition
O(N)
Term
List (Array)
Delete last
 Definition
O(1)
Term
List (Array)
find and delete given element (sorted or not)
 Definition
O(N)
Term
Binary Search Trees (BST)
Average height
 Definition
O(logN)
Term
Binary Search Trees (BST) Worst case height
 Definition
O(N) When all elements are on the right or left side
Term
Binary Search Trees (BST)
Best case height
 Definition
O(logN)
When it is a complete BST
Term
Heap
Height running time
 Definition
O(logN)
Term
Heap
methods running time
 Definition
O(logN)
Term
Heap
left child formula
 Definition
2i + 1
Term
Heap
right child formula
 Definition
2i + 2
Term
Heap
parent formula
 Definition
(i-1)/2
Term
Heap properties
 Definition
Complete until last level
height O(logN)
Parents are always less than the children
Term
Heap
enqueue (how to)
 Definition
*add to next available spot in the tree (end of the queue)
*percolate up until the parent is no longer greater than the child
Term
Heap
dequeue (how to)
 Definition
Step1: remove root, store in temp
Step2: place last element of tree into root (from the end of the queue)
Step3: while parent is greater than the children, swap with the SMALLEST child(if one exists)
Term
Number of elements in a Tree
 Definition
2^n+1 - 1
Term
BST Delete (how to)
 Definition

One child: link previous child up to the new root/parent Two Childs: look in the right subtree for smallest element, put into root/parent. NOTE: May need to call multiple time if smallest has left and right children

 

The element you are bringing up is the next largest child[find this by looking in the right subtree for the smallest element]
Term
BST
insert (how to)
 Definition
If given element is less than root, go to left subtree
If given element is greater than root, right subtree
Continue until new node is found, insert there
Term
BST
Find (how to)
 Definition
If root is null
{return false}
else
{
if element == root
return true;
else{
if element is smaller, call on left child
if element is greater, call on right child
Term

BST Find minimum

(How to)

 Definition
IF root has not children, throw exception Else go left until current node has no children, then return current node
Term
Stack (LL)
push (how to)
 Definition
Node temp = top;
top = new Node();
top.element = item;
top.link = temp;
Term
Stack (LL)
pop() [how to]
 Definition
if top is null -> throw exception
else T temp = top.element;
top = top.link;
return temp;
Term
Stack (Array)
push (how to)
 Definition
if top+1 == arr.length
resize
also
top++
arr[top] = item;
Term
Stack (Array)
pop (how to)
 Definition
if top == -1, throw exception
else
return arr[top--];
Term
Queue (LL)
enqueue (how to)
 Definition
if front is null
set front = new node
point end to front
else
end.next = new node
end = end.next
Term
Queue (LL)
dequeue (how to)
 Definition
if front is null, throw exception
else
T temp = front.ele
front = front.next
return temp
Term
Queue (Circular array)
enqueue (how to)
 Definition
if count == length, resize
else if end == arr.length, end = 0, arr[end] = item;
else
arr[++end] = item;
count++;
Term
Queue (Circular Array)
dequeue (how to)
 Definition
if (count == 0) -> throw EX
T temp = arr[front];
if (front == arr.length)
front = 0;
else
front++;
return temp;
Supporting users have an ad free experience!