Suppose that an intermixed sequence of stack push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence could not occur?
If we implement a stack using a resizing array, when and how is the array resized?
Use a stack to evaluate the postfix expression 1 2 + 3 4 * - 9 /
. Write the state of the stack after each token (i.e., an operator or operand) is processed.
In using the shunting yard algorithm to convert A - (B ^ C ^ D * E) + F / G
from partially parenthesized infix form to postfix form, list the elements that are popped from the operator stack in the order they are popped.
In using a stack to check delimiter matching, three different kinds of errors can occur. Give example expressions that would create each kind of error, and indicate which could result in stack underflow if things are not properly checked first.
What does the following code fragment print when n is 50? In general, what does it do when presented with a positive integer n?
Stack s = new Stack(); while (n > 0) { s.push(n % 2); n = n / 2; } while (!s.isEmpty()) System.out.print(s.pop());
Which abstract data type, stack or queue, would you choose to implement an "Undo" feature in a word processor? Which would you choose to store mouse click events when implementing a user interface?
What does the following code fragment print when n is 10? In general, what does it do when presented with a positive integer n?
Queue q = new Queue(); q.enqueue(0); q.enqueue(1); for (int i = 0; i < n; i++) { int a = q.dequeue(); System.out.println(a); int b = q.peek(); q.enqueue(a + b); }
If a class implements Iterable interface, what can you do with the class objects?
Consider the program below and then answer the questions posed:
class Node { public int iData; // data item (key) public Node next; // next node in list public Node(int id){ // constructor iData = id; } }
class LinkList { private Node first; // reference to first node on list public LinkList() { // constructor first = null; } public Node find(int key) { // find the node with a given key Node current = first; // start at the first node while (current != null && current.iData != key) current = current.next; // go to next node return current; } public void displayList() { // display the list for (Node current = first; current != null; current = current.next) System.out.println(current.iData); // print data } public void insertFirst(int key) { // insert a node at the front of the list // See question (a)... } public Node delete(int key) { // delete the node with a given key // See question (b)... } }
class LinkListApp { public static void main(String[] args) { LinkList theList = new LinkList(); // create a list theList.insertFirst(22); theList.insertFirst(44); theList.insertFirst(66); Node d = theList.delete(44); d = theList.delete(88); theList.displayList(); // display list } // end main() }
Implement the insertFirst
method that inserts a new node with the given data key at the front of the linked list. Assume the list is not empty.
Implement the delete
method that deletes a node with the given data key. Assume the list is not empty. If the key does not exist in the list, the method should return null
and should not change the list.
Predict the printed results of the main method in LinkListApp
Name two advantages of using linked lists over arrays to store data.
Name an advantage of using arrays over linked lists to store data.
Below is a method which uses a stack of integers with typical push and pop operations:
public static int foo(int x, int y) { if (x <= 0 || y <= 0) return 0; stack.push(y); return foo(x - 1, y-1) + stack.pop(); }
Assuming the stack is initially empty, draw a snapshot of the stack after every push and pop statement for each recursive call for foo(3,4). Label each stack snapshot with the recursive call, and the push or pop statement. For example, the following shows the first two snapshots of the stack after the push statement for the call foo(3,4)
and after the push statement for the call foo(2,3)
.
4 --- foo(3,4) - push 3 4 --- foo(2,3) - push
To what integer value does foo(3,4)
evaluate when invoked?
Analyze the runtime of the following loops given an even input size N using direct loop analysis or recurrence relations. Derive the runtime cost function, and then a Big-O notation for the cost function. Assume that each loop statement takes 1 unit of time, and the update of loop variable can be ignored (does not count into running time).
(a)for (int i = 0; i < N; i++) { if (i % 2 == 0) { for (int j = 0; j < N; j++) System.out.println("1 iteration executed!"); } else { for (int j = 0; j < 10; j++) System.out.println("1 iteration executed!"); } }(b)
for (int i = 0; i < N; i++) { for (int j = i; j < 2 * N; j++) { System.out.println("1 iteration executed!"); } }
One can solve the N-Queens problem by implementing a backtracking algorithm using a stack. Show the values of such a stack after each push or pop operation for 4-Queens problem until the first solution is found.
One can solve a maze by implementing a pathfinding algorithm using a queue or a stack. Using a queue search on the following maze (1's represent walls; 0's represent traversable areas; top left corner is the starting position; the bottom right corner is the finish), show the sequence of positions found by the pathfinding algorithm. Assume that when checking for valid "next" positions, one looks up, then right, then down, and then finally left -- in that order.
0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0
A doubly circular linked list is a list where each node points to its successor and its predecessor in a circular manner. The head
variable points to the first node in the list. An empty list is represented by a null
value in head. The prev
value of the first list node points to the last node (i.e., the "tail") and the next
value of the last node in the list points to the first node. The structure of a node and an (incomplete) list class are given by the following class definitions.
public class Node { public int value; Node next; // "next" points to the successor Node prev; // "prev" points to the predecessor } public class List { public Node head; // head must point to first node in list public List() { // Constructor head = null; // Empty list } //... other methods ... }
Write a Java method for the List class that inserts a Node object x at the head of the doubly circular list:
public void insertAtHead(Node x) { // write the code that should go here... }
Write a Java method for the List class that inserts an Node object x at the tail of the doubly circular list:
public void insertAtTail(Node x) { // write the code that should go here... }
Write a Java method for the List class that deletes the Node object at the tail of the doubly circular list:
public void deleteAtTail() { // write the code that should go here... }
Show the traces for each sort requested below when applied to the array shown.
{ 'f', 'b', 'a', 'h', 'c', 'd', 'g', 'e' }
What's the average runtime cost of insertion sort in big O notation?
What is the best case and worst case time complexity in Big O notation for the selection sort algorithm?
int numberOfPairings(int n) // write the code that should go here... }
4 2 3 3 12 9 1 1 3 3 3 3 -9 -9 -1 === === === === === === === === === The expression evaluates to -1
^ ^ * ( - / +
0 1 1 2 3 5 8 13 21 34In general, this will print out the first
n
values of the Fibonacci sequence
iterator()
method and then use it's next()
and hasNext()
methods to iterate through the items of the object in question.public void insertFirst(int key) { // insert a node at the front of the list Node node = new Node(key); node.next = first; first = node; }
public Node delete(int key) { // delete the node with a given key // if the list is empty, there is nothing to delete.. if (first == null) return null; Node node = first; // if the key was found on the 1st node, reset "first".. if (node.iData == key) { first = node.next; return node; } // traverse the list to find parent of node with the given key.. while (node.next != null && node.next.iData != key) { node = node.next; } if (node.next == null) { // then key wasn't present return null; } else { // re-route references to skip over node to be deleted.. Node deletedNode = node.next; node.next = node.next.next; return deletedNode; } }
66 22
2 3 3 3 4 4 4 4 4 ======== ======== ======== ======= ======= ======= foo(3,4) foo(2,3) foo(1,2) pop pop pop push push push foo(3,4) = foo(2,3) + pop foo(2,3) = foo(1,2) + pop foo(1,2) = foo(0,1) + pop foo(0,1) = 0 So, foo(1,2) = 0 + 2 = 2 foo(2,3) = 2 + 3 = 5 foo(3,4) = 5 + 4 = 9 <-- final answer = 9
$\displaystyle{C(n) = \frac{n^2}{2} + 5n \sim \frac{n^2}{2}; \quad C(n) \textrm{ is } O(n^2)}$
$\displaystyle{C(n) = \frac{3n^2}{2} + \frac{n}{2} \sim \frac{3n^2}{2}; \quad C(n) \textrm{ is } O(n^2) }$
2 1 0 0 2 3 3 3 3 3 3 0 0 0 0 0 0 0 1 1 1 1 === === === === === === === === === === === ===
1 | 2 | 4 | Wall | Wall |
3 | Wall | 6 | Wall | Wall |
5 | 7 | 9,10 | Wall | Wall |
8 | Wall | 12,13 | Wall | not visited |
11 | 14 | 15,16,17 | 18,19,20 | 21,22,23 |
enqueue pos 1 dequeue pos 1, mark visited enqueue pos 2 (with parent pos 1) enqueue pos 3 (with parent pos 2) dequeue pos 2, mark visited enqueue pos 4 (with parent pos 2) dequeue pos 3, mark visited enqueue pos 5 (with parent pos 3) dequeue pos 4, mark visited enqueue pos 6 (with parent pos 4) dequeue pos 5, mark visited enqueue pos 7 (with parent pos 5) enqueue pos 8 (with parent pos 5) dequeue pos 6, mark visited enqueue pos 9 (with parent pos 6) dequeue pos 7, mark visited enqueue pos 10 (with parent pos 7) dequeue pos 8, mark visited enqueue pos 11 (with parent pos 8) dequeue pos 9, mark visited enqueue pos 12 (with parent pos 9) dequeue pos 10, mark visited (for the second time) enqueue pos 13, (with parent pos 10) dequeue pos 11, mark visited enqueue pos 14, (with parent pos 11) dequeue pos 12, mark visited enqueue pos 15 (with parent pos 12) dequeue pos 13, mark visited (for the second time) enqueue pos 16 (with parent pos 13) dequeue pos 14, mark visited enqueue pos 17 (with parent pos 14) dequeue pos 15, mark visited enqueue pos 18 (with parent pos 15) dequeue pos 16, mark visited (for the second time) enqueue pos 19 (with parent 16) dequeue pos 17, mark visited (for the third time) enqueue pos 20 (with parent pos 17) dequeue pos 18, mark visited enqueue pos 21 (with parent 18) dequeue pos 19, mark visited (for the second time) enqueue pos 22 (with parent 19) dequeue pos 20, mark visited (for the third time) enqueue pos 23 (with parent 20) dequeue pos 21, mark visited -- done (we just dequeued the end position) So the path taken backwards (following parents) is: 21, 18, 15, 12, 9, 6, 4, 2, 1 Thus the path taken is: 1, 2, 4, 6, 9, 12, 15, 18, 21
public void insertAtHead(Node x) { if (head == null) { // no nodes in circular list head = x; head.next = head; head.prev = head; } else { // one or more nodes in list head.prev.next = x; x.prev = head.prev; x.next = head; head.prev = x; head = x; } }
public void insertAtTail(Node x) { insertAtHead(x); head = head.next; }
public void deleteAtTail() { if (head == null) { // no nodes in circular list ; //do nothing (optionally throw exception) } else if (head.next == head) { // one node in list head = null; } else { Node newTail = head.prev.prev; newTail.next = head; head.prev = newTail; } }
Order before selection sort application: f b a h c d g e 0 1 2 3 4 5 6 7 ------------------------ a b f h c d g e a b f h c d g e a b c h f d g e a b c d f h g e a b c d e h g f a b c d e f g h a b c d e f g h a b c d e f g h Order after selection sort application: a b c d e f g h
Order before insertion sort application: f b a h c d g e 0 1 2 3 4 5 6 7 ------------------------ f b a h c d g e b f a h c d g e a b f h c d g e a b f h c d g e a b c f h d g e a b c d f h g e a b c d f g h e a b c d e f g h Order after insertion sort application: a b c d e f g h
int numberOfPairings(int n) { return (n == 2 ? 1 : (n - 1) * numberOfPairings(n-2)); }