Sample midterm

Data Structures Midterm     Name: __________________________

1) Draw a picture of a Doubly Linked List, with nodes holding values of 4, 5, and 7. You should not only have a head and tail, but also a header and a trailer.







2) Draw and describe the steps involved in removing the middle element (5).








3) Deleting from the end of a singly linked list is O(n). Demonstrate the steps in deleting from the end of such a list and explain why it is O(n).







4) Deleting an element from the middle of a singly linked list (the node is passed in) is O(n). Explain, in a sentence or two, why.







5) Deleting from the end of a doubly Linked list, where we have a reference to the tail, is on the order of what? Explain why.









6) Draw a circular array with a couple of elements and a front and rear.







7) How would you implement (in words) removal from the end of the circular array? What data members would you modify? How would you handle boundary conditions?






8) How would you implement removal from the middle of a vector based on a normal array, rather than a circular array? Explain in words.






9) Give one reason it might be better to use an array rather than a singly-linked list to implement a stack.






10) f(n) = 15n^2 + 10n + 1. This is O of what? Give a proof with c and n_0.








12) Write a Java class for a node for a singly-linked list.
13) Write code for a Singly Linked List class, which makes use of that node. Make a head, a tail, and a size. Include the following methods (others may exist, but you need not write them), and make certain to handle the boundary conditions and to check for error conditions:
insertBefore(Node n, int x);
insertAfter(Node n, int x);
remove(int value);
removeSpan(Node start, Node finish);
swap(Node n, Node m);