Reuse empty spaces.

-, -, 3, 5, 7, -, -, -.

Given a 5 element queue Q (from front to back: 1, 3, 5, 7, 9), and an empty stack S, remove the elements one-by-one from Q and insert them into S, then remove them one-by-one from S and re-insert them into Q. The queue now looks like (from front to back): 9, 7, 5, 3, 1.

3. What is the reason for using a "circular queue" instead of a regular one

Reuse empty spaces.

4. Write a method that finds the smallest element in a Stack of Integers, removes all its occurrences in the stack and then returns that modified stack

5. Given an array and a singly linked list. Which of these data structures uses more memory space to store the same number of elements? Explain your answer.

6. What changes do you need to make to a linked list in order to have a constant time access to the last mode?

7. Given a doubly linked list where each node has two references (prev and next): one that points to a previous node and another to a next node:

Assuming the linked list above, provide the output for the following code fragments. The list is restored to its initial state before each line executes:

a) _________ head.next.next.next.data;

b) _________ head.next.next.prev.prev.data;

c) _________ tail.prev.prev.prev.next.data;

8. Given a doubly linked list where each node has two references (prev and next): one that points to a previous node and another to a next node.

Write the statements to insert a new node

Node toInsert = new Node(6);

containing the 6 between the node with the 5 and the node with the 9. You do not need to write the whole method but just the statements to make the connections.

nextNode = prevNode.getNext(); //now nextNode is 5prevNode.setNext(toInsert); //prevNode is 9nextNode.setPrev(toInsert);toInsert.setNext(nextNode);toInsert.setPrev(prevNode);

9. Implement a C+ method

public void removeAllMatchingItems(AnyType keyItem)

that removes each and every item equal the keyItem from a singly-linked list.

public void removeAllMatchingItems(AnyType keyItem){

if(list == null)

return;

if(head == null)

return;

while(head!= null && head.data.equals(keyItem)){

head = head.next;

}

Node temp = head;

Node prev = head;

while(temp!= null){

if(temp.data.equals(keyItem)){

prev.next = temp.next;

}else{

prev = temp;

}

temp = temp.next;

}

}

10. Given a sorted singly-linked list, where the head contains the smallest element Implement a C++ method

public void insertInOrder(Comparable keyItem)

that creates a new node and inserts it in-order into the list. You assume the LinkedList class given in lectures.

public void insertInOrder(Comparable keyItem){ Node newNode = new Node(keyItem); if(head == null){ head = newNode; return; } Node temp = head; Node prev = head; while(temp!= null && temp.data.compareTo(keyItem)>0){ prev = temp; temp = temp.next; } prev.next = newNode; newNode.next = temp;}

11. A Queue is best characterized as

c) First In First Out

12. Given an empty queue Q, what does it look like after the following operations?

a. Q.enqueue(5)

b. Q.enqueue(2)

c. Q.dequeue()

d. Q.enqueue(3)

e. Q.dequeue()

13. Given an efficient circular array-based queue Q capable of holding 10 objects. Show the final contents of the array after the following code is executed:

for (int k = 1; k ≤ 7; k++)

Q.enqueue(k);

for (int k = 1; k ≤ 7; k++)

Q.enqueue(Q.dequeue());

14. Write a method

a. public Queue<String> contains(Queue<String> q, String str)

that takes a Queue and an element and returns true if the Queue contains this element or false if not. The elements in the Queue must remain in their original order once this method is complete.

15. Show how to implement a queue using two stacks. What is the worse-case runtime complexity of the dequeue method?

Дата добавления: 2015-11-16