حل واجب M180

M180: Data Structure and Algorithms in Java
Tutor-Marked Assignment (Fall 2013/2014)
Cut-Off Date: December 7, 2013

Question 1: (4 marks)
Assume that we have two algorithms for solving one specific algorithm. The first algorithm (A) takes time n,
while algorithm (B) takes time 3lg n+5. When should we choose algorithm A, and when should we choose
algorithm B?
Question 2: (7 marks)
Given a Node P in a list of nodes (linked list) that contains [3, 5, 4, 1]. Draw the initial list and the results of
the following statements, applied in the same order below:
(a) P.next = P.next.next;
(b) P.next = new Node(7, P.next);
(c) P.next.next = new Node(8);
(d) P.next.next = P;
Question 3: (5 marks)
Define a class for circular doubly linked lists with the following two procedures:
(A) Insert one node at the head of the list.
(B) Delete any given node in the list
Question 4: (4 marks)
Given the following binary tree below:
Draw the resulted tree after performing the following operations (Add 5, Add 17, Delete 23, and Delete 9)