Comp 271: Data Structures
数据结构代考 31.7 pts possible. 0.5 pts / question unless otherwise indicated 120 minutes time. 15 pages. Please pace appropriately.
Name:
Final Exam 数据结构代考
31.7 pts possible. 0.5 pts / question unless otherwise indicated 120 minutes time. 15 pages. Please pace appropriately.
Please pace appropriately (~8 mins/page)!
IMPORTANT NOTE: for numbered problems, if you answer and receive no partial credit, you will be deducted up to an additional 0.3 pts.
In the Sorts homework we used ArrayList to perform array-like operations. ArrayList uses methods to do the same things we did with indexed arrays.FINAL EXAM1代写
Examples:
myArr[k] = myArr[k+1]; à myArr.set(k, myArr.get(k+1) ); int [] myArr = new int[50]; à ArrayList<Integer> myArr = new ArrayList<Integer>(50);
- Translate the following three lines (from a swap function) so that they work for ArrayLists (0.6pts)
temp = myArr[a]; myArr[a] = myArr[b]; myArr[b] = temp;
- Ifwe take a typical singly-linked list implementation and maintain a pointer to the tail, which of the following are O(1) operations. Circle all the apply. (0.6 pts, -0.2 for each wrong)
a)Adding an element at thehead
b)Adding an element at thetail
c)Removing the headelement
d)Removing the tailelement
e)Removing the second element (the one the head pointsto)FINAL EXAM1代写
f)Removing the second to last element (the one that points to the tailelement)
- Knowing the answer to the question above, for a singly-linked list with a tail..
a)whichend(s) can you add to if you will use it as a FIFO queue?
b)whichend(s) can you add to if you will use it as a LIFO queue?
- Fill the following table with the big-O time of each operation. (2 pts total, -0.4 for each incorrect, no additionalpenalty)
| #2 | Add(element) | Remove(element) | Contains(element) | |
| Skip list
(expected) |
||||
| our SortedList | ||||
| Heap (priority
queue) |
root only: | O(n) | ||
| LinkedList
(doubly-linked) |
数据结构代考 | |||
| HashSet/HashMap by key | By key:
By value: |
|||
| ArrayList (Unsorted array) | Assume resizing: _____ | Assume resizing: | ||
| Sorted array (no
empty spaces) |
Using binary
search: |
|||
| TreeSet/TreeMap
(self-balancing) |
2.This is a one-to-one matching. Place the letter for the match in the second column in the table above. (0.6 pts, -0.2 per mistake, no addedpenalty)
a)although not a queue in Java, this can function very effectively as a LIFO queue because the add(element) function adds to the end ofit
b)by far the most common mapimplementation
c)this is operated on as though it is a binary tree, but is often kept asan array
d)O(1) to find the median of the elements in thisstructure 数据结构代考
e)a singly-linked list where finding the minimum is O(1) but the max isO(n)
f)This implementation maintains elements in sorted order in a linear structure, but can be searched and added to faster thanO(n)
g)This implements both a FIFO and LIFO queue
h)People generally use a hash table instead of this, but it has the benefit of maintaining items in sortedorder
LinkedList 数据结构代考
The following questions involve a doubly-linked list. For reference, the DoublyLinkedNode class used in the linked list implements the following functions:
public DoublyLinkedNode<E> previous(); public void setPrevious(DoublyLinkedNode<E>) public DoublyLinkedNode<E> next();
public void setNext(DoublyLinkedNode<E>); public E value();
public void setValue(E);数据结构代考
3 There are some mistakes in the code for the remove function for this doubly- linked list. They are in bold and underlined below. Replace the part that is mistaken with the correct code. (6 fixes total, 1.8 pts, no additional penalty)
public E remove(E value) {
// post: first element matching value is removed from list DoublyLinkedNode<E> finger = head;
// iterate to the item to be removed
while (finger != tail && !finger.value().equals(value)) { finger = finger.next());
}
if (finger != null) {
// remove the node and return the element in it
// fix next field of element above if (finger.previous() != null) {
finger.previous().setNext(finger);数据结构代考
} else {
head = finger;
} // fix previous field of element below if (finger.next() != null) {
finger.next().setPrevious(finger);
} else {
tail = finger;
}
count--; // fewer elements return finger;
}
// if finger is null return null;
}
Priority Queue
Start with the following heap for the next two problems
- write the resulting heap upon removingthe 0 value node. (Hint: replace the node with the last value in the heap, and percolate that value up or down to satisfy the heap property. no need to show work
but display the answer in tree form (not as an array) (1.0 pt)
b) Starting over with the heap as originally drawn, write the resulting heap if youadd the value -2 (read: negative 2)to it (hint: add at the end and percolate up – no need to show work, but display the answer in tree form) (1.0 pt)数据结构代考
Hash Tables 数据结构代考
Suppose you have a class called ‘Student’ which holds student information and uses the student’s ID as the key.
Here is the hashCode method for this class – NOTE THE VALUE ‘2’:
public int hashCode(){
return (2 * this.ID);
}
- Hash the following student ID/name pairsinto the following hash table using LINEAR PROBING to deal with collisions. (1.2 pts, -0.4 for each incorrect, no added penalty)
ID NAME
2 Mary
1 Jim
6 Sarah
11 Kat
Index <key, name> chain
| 0 | (don’t miss the bolded instructions) |
| 1 | |
| 2 | |
| 3 | |
| 4 |
2.Now in linear probing, if we now remove Jim we would have to leave a“reserved” space, as opposed to simply deleting the entry. What does that mean, and Why?
- There are generally two types of implementations for a graph, one which uses a linked list to store the neighbors of each vertex (called GraphList) and one which uses an adjacency matrix to store the edges (called GraphMatrix). For each of the following descriptions, your choices are one of the following (1.8pts)GraphList, GraphMatrix, Both, Neither
a)Capable of holding n2 edges (though it may not beefficiently)
b)It may be preferable to specify the size when you construct the graph, as resizing is
c)Searching for an edge between two vertices is O(n) for a sparsegraph
d)Searching for an edge between two vertices is O(1) for a sparsegraph
e)Searching for an edge between two vertices is O(1) for a densegraph
f)Searching for an edge between two vertices is O(n) for a densegraph
2.Find the minimum spanning tree for the following graph. No need to show your
public static int recFunc (int n, int count) { if (n > 2) {
return (recFunc (n / 2, count + 1) );
} else {
return (count);
}
}
- Whatvalue does recFunc(100,0) return, exactly (okay to be off by at most 1). Note, integer division rounds down (5/2 à 2, not 5)
- Describe using a mathematical function what recFunc returns with large ‘n’and ‘count’ at
- How much time, in Big O notation, does recFunctake?
- For each recursive call, O(1) memory must be stored. In Big-O notation, how much memory is necessary to compute the solution for the value‘n’?
After running the following three lines of code… String A = new String(“Jack”);
String B = new String(“Jack”);数据结构代考
- Why does ‘A == B’ evaluate to false while ‘A.equals(B) evaluate totrue?
- What is an advantage of using ArrayList instead of arrays of primitives to store values?
There is a shuffled set of ‘n’ cards on a table. You pick from the top of the deck, and insert it in the proper location in your hand so that your hand is always sorted. You do this until you have all the cards are sorted in your hand.
1.What is the name for this kind of sortingalgorithm?
We will improve the algorithm from class. Unlike the sort we learned in class, instead of looking at your hand from left to right to find the proper location to place the card (an O(n) operation), you are more likely in this case to intelligently search the cards in your hand (in the same way your search in a dictionary for a word) since the cards in your hand are sorted.
- What is the big O for inserting one card in your hand thisway?数据结构代考
- How many times, in big O notation, will you be performing the insertion in the problemabove?
- Given the answer to the last two problems, how long does it takes to sort the entire deck of ‘n’ shuffled cards this way inbig-O?
- In the implementation on arrays discussed in class, how long did this sort take for a deck of ‘n’ cards, in bigO?
In the sorts homework we used merge sort and insertion sort on a mixture of two different types of data – nearly-sorted arrays and shuffled arrays. However, what if we used heap sort and selection sort instead? Note, it’s not a good idea.
1.Write the big-O of each in the followingtable
Shuffled
Heap sort O( ) O( )
nearly-sorted
Selection sort O( ) O( )
When you add the amount of time two different operations take, the big O is the time for the slower operation (e.g. O(n2 ) + O(n3 ) = O(n3 ) ). Half of the test data was shuffled, and half was nearly-sorted. Use this information to answer the following two questions.
- What is the big-O for heap sort on the mixed testdata?
- What is the big-O for selection sort on the mixed testdata?数据结构代考
- What is the overall big-O for a hybrid sort method that sends nearly-sorted data to selection sort, and shuffled data to heapsort?
- Would you rather replace selection sort with insertion sort, or heap sort with merge sort for this algorithm to work better? Pick one, and explain what the overall big-O time complexity would be in this case on the mixed data.
1.What is the difference between an abstract class and an interface? In particular, why might you choose one over theother?
- What is wrong with the followingcode?
A = new String(“Adam”);
B = new String(“Amanda”); if (A < B) {
System.out.println(A + “ is alphabetically earlier than “ + B);
}
- Garbage collectorquestion
Recall, the assignment operator (‘=’) for objects in Java does not create copies or change values of an object internally, but rather changes which object a variable points to (a.k.a. ‘references’) in memory.数据结构代考
Given the following code, circle which of the strings will be picked up by the garbage collector after these lines are finished?
A, B, C, A&B, B&C, A&C, A&B&C, or none of the above
String r = new String(“A”); String s = new String(“B”); String t = new String(“C”); s = t;
t = r; r = s; t = r;
- Write the letter for the following data structures next to the description. Note, the matching is one-to-one so if one appears suitable to multiple descriptions it may have to change so the others match. (2 pts total, -0.4 for each wrong, no additional penalty)
If there are O(n log n) evenly distributed edges, search for an edge is O(log n)
The fastest, best implementation to represent a dense graph数据结构代考
This type of graph is useful for showing dependencies between methods
Use this to represent relationships with different strengths between items
a)weighted b)directed c) adjacency matrix graph d) linked-list graph
Primitives
Wrapper classes
e)Integer,Double f) int, double FINAL EXAM1代写
O(1) search with index, O(log n) fastest search for a value, does not resize
O(1) search with index, O(n) fastest search for a value, does not resize
O(1) search with index, O(n) fastest search for value, dynamically resizes
Great LIFO, bad FIFO queue unless you add a tail pointer and add at the tail
A Deque – great LIFO and FIFO behavior since the head and tail are symmetric
This is basically what a skip list is without the “express lane” nodes
g)ArrayList h) singly-linked list i) ourSortedList
j) LinkedList k)sortedarray l) unsorted array 数据结构代考
No extra methods in this, only a promise that duplicates are not allowed
You can only access elements on the top or bottom of this interface
This isn’t a sub-interface of java.util.Collection since it only stores associations
The super-interface for most interfaces in the Java collections framework
A group of static methods that work on collections (e.g. shuffle, sort, …)
You can access elements by an index, but speeds can range from O(1) to O(n)
m)Map n)Queue o) List p) Set q) Collection r) Collections
this tree is self-balancing for fast, efficient behavior
an in-order traversal of this tree gives the elements in sorted order
this has no particular ordering. e.g. heaps are abstractly represented as these.
s)binary tree t) binarysearch tree u) AVL tree
an alternative to hash tables that maintains items in sorted order 数据结构代考
a map implementation which is O(1) and fastest for very small load factors
a map which can hold more items than its underlying array
useful when all you need to do is choose the highest/lowest value each time
same expected times as a AVL tree for add/search/remove operations
v)treemap w) hash table, chaining x) hash table, linearprobing
y)skiplist z) heap/priority queue
Big O – the following questions only ask what the big-O should be. Unless specified, assume the number of items is ‘n’.
- In the game 20 questions (or Guess Who), the number of questions if you are choosing among n objects, and asking intelligent questions that divide your search space.
- With ‘n’ as the number of characters in the alphabet, what is the order for the time it takes to find a 4 character password using brute force (searching through all possibilities)?
- What is the time complexity for each of the expressions below (1.0pts)
a)Simply the big O for: 7 log n + 4 n log (3 n) + 2n
b)Simplify the big O for: 600 * log (5 n) + 0.00001n2
c)The speed of this loop: for (i = 0; i < n; i +=1000)
d)The speed of this loop: for (i = 1; i < n; i *=2)
e)The speed of this for loop: for (i = 0; i < n; i *=01);
The following code is a poor implementation of bubble sort, but it does sort the list.
public static void listBubbleSort(List x) { int n = x.size();
for (int pass=1; pass < n; pass++) { for (int i=0; i < pass-1; i++) {
if (x.get(i) > x.get(i+1)) { swap(x, i, i+1); 数据结构代考
}
}
}
}
- What is the speed of this sort if the implementation is passed an ArrayList? (hint: if bubble sort acts as if it is simply sorting anarray)
- What is the speed of executing a single ‘x.get(i)’ statement if x is aLinkedList?
- What is the speed of this sort if the implementation is passed aLinkedList?
- There is a mistake in the code. In particular one value of the list will not be sorted. Which value is that? Or just fix the code.
Someone apparently decided to implement one of the sorts we discussed in class using recursion with the following code:
public static void recSort (double [] data, int firstUnsorted, int lastUnsorted) {
// start with a guess for the maximum value int maxIndex = firstUnsorted;
double maxValue = data[firstUnsorted];
// loop through the unsorted portion and SELECT the maximum for (int i = firstUnsorted; i <= lastUnsorted; i++) {
if (data[i] > maxValue) { maxIndex = i; maxValue = data[i];
} FINAL EXAM1代写
}
// place the maximum value at the end of the array swap (data, maxIndex, lastUnsorted);
// now sort the rest of the array recursively if (lastUnsorted – firstUnsorted > 1) {
// there is still more to be sorted
// recursively call recSort on the rest of the data
recSort(data, firstUnsorted, lastUnsorted – 1);
} else {
return;
}
}
- Of the types of sorts we learned about, which one is the code above an implementation of? Note, the original version doesn’t use recursion.
- How much extra space (in addition to the array elements) does the original, non- recursive versionrequire?
- For a call to sort n values – e.g. recSort(data,0,n-1) – how many times will recSort becalled?
- If each recursive function call is O(1) extra memory, how much extra memory is required to sort the entire list, in big Onotation?
1.Circle the integer values below that you would end up testing while searching for the value 10(0.4 pts, -0.2 for each mistake, no additional penalty)
2.What is a likely value for ‘p’ (the probability of adding another layer to the node of a skiplist) given the depiction of the skip list above. Explain using numbers derived from the figure.数据结构代考
- If we wanted to convert a skiplist to a List in the java collections framework, we would likely want to use an indexable skiplist implementation as briefly mentioned in class, since the only other way to know we visit the k-th element is by dropping to the lowest level (and rendering the skiplist O(n) lookup by index.
Explain what an indexable skiplist is and how it would work with a figure (or annotate the figure above in a few locations appropriately)
更多其他：C++代写 java代写 r代写 代码代写 金融代写 物理代写 考试助攻 C语言代写 finance代写 lab代写 计算机代写 code代写 data代写 report代写 数学代写
