CMPS 390 Flashcards
What is recursion?
A self calling method.
Show an example of recursion for the fibonacci sequence.
int fib(int n) {
if(n == 1) {
return 1;
}
if(n == 2) {
return 1;
}
return(fib(n - 1) + fib(n - 2));
}
Create even or odd method with no modulus.
boolean EvenOrOdd(int n) {
if(n == 1) {
return false;
}
if(n == 2) {
return true;
}
return(EvenOrOdd(n - 2));
}
What does the diagram for a singly linked list (node first) look like?
-
What does a doubly linked list: node first look like?
-
What is the difference between an array and a linked list?
[Edit: An array is indexed and a linked list is not.] An array has a fixed size, and the size must be known ahead of time. A Linked List can grow organically. Also, changing the positions in a linked list is easier due to being able to change node destinations.
What is a stack?
LIFO - Last in First Out. (Think of a PEZ dispenser)
What operations are used on a stack?
Pop - removes an element on the top. Push - pushes an element on the top. Peek - Gives you the element at the top.
What is a queue?
FIFO - First in First out. (Think of waiting in line for a roller coaster)
What operations are used on a queue?
Enqueue - Add to back of queue. Dequeue - Remove item from the front of queue. Peek - give you the element on the front. Empty - is the queue empty.
Linked List Write code to add an element to the start.
procedure addToHead(element)
head = new Node(element, head)
if(not the Tail)
tail = head
end if
end procedure
Linked List Write code to add an element to the end
procedure addToTail(element)
if(this is the tail)
tail->next = new Node(element)
tail = tail->next
endif
else
head -> tail = new Nodel(element)
end procedure
Linked List Write code to remove an element from the head
procedure RemoveFromHead()
if(this is the head)
element = head->info
temp = head
if(this is the last item in the list)
Break pointer connection between head and tail to terminate list
else
set head.next to equal next item in list
endif
release temp from memory pool reutrn element else return 0
end if
end procedure
Linked List Write code to remove an element from the tail
procedure RemoveFromTail()
if(this is the tail)
element = tail->info
if(this is the last item in the list)
Break pointer connection between head and tail to terminate list release head from memory pool
else
Traverse list until you reach the tail release tail from memory pool set tail pointer to previous element if one exists set tail’s point to next element to null
endif
return element
else
return 0
end if
end procedure
Given a stack (S), use a queue (Q) to reverse the elements.
while(!S.isEmpty()) {
Q.Enqueue(S.Pop());
}
while(!Q.isEmpty()) {
S.Push(Q.Dequeue());
}
