Question 1: True or False (15 points)

1. In singly linked list head and tail contain data.

2. This code can be used to add element e to the front of the singly linked list: public void addFirst(E e) { head = new Node (e, head); if (size == 0) tail = head; size++; }

3. When doing analysis of algorithm, we focus on the worst-case running time because it is easier to analyze.

4. The running time of an algorithm typically grows with the input size.

5. Any recursion method should contain at least one base case.

6. Insertions and deletions to and from the stack follow the last-in first-out scheme

7. In Stack, the method top() returns the last inserted element without removing it

8. The method size() returns the number of elements stored in the stack.

9. In computer science, a tree is an abstract model of a hierarchical structure

10. A tree consists of nodes with a parent-child relation

Question 2: Multiple Choice- Choose the best answer from the choices given (10 points) 1. In singly linked list: Size(), isEmpty(), last(), and first methods are A. Accessor methods B. Update methods C. ADT methods D. None of answers 2. The method .... . in the stack inserts an element to the top of the stack. A. Push B. Add C. Insert D. Pop 3. The method removes and returns the last inserted element from the stack. A. Push B. Add c. Insert D. Pop 4. Stack operations: top (), size (), and isEmpty() are: A. Auxiliary methods B. Main methods C. Update methods DA+C 5. The method .......... returns the element at the front of the queue without removing it A. First B. Pop () C. Enqueue () D. Dequeue (0 6. The method returns the number of elements stored in the queue A. size B. setSize() C. Capacity 0 D. Length ( 7. A is a collection of vertices and edges. E. Graph F. Tree G. Linked List H. Binary Tree 8. In graph, the method that Returns an array containing the two endpoint vertices of edge e. A. vertices() B. edges() c. end Vertices(e) D. opposite(v, e) 9. In map, the method that returns an iterable collection of the keys in M A. entrySet () B. Values() C. keyset () D. Keys () 10. When implementing priority queue using sorted list, the complexity of adding new element is E. 0(1) F. O(log n) G. O(n) H. O(n log n) Answers Key 1. 2. 4. 5. 6. 7. 8. 9. 10. 3