Java A desk can be modelled as a simple data structure with the following ADT De
ID: 3782534 • Letter: J
Question
Java
A desk can be modelled as a simple data structure with the following ADT Desk: add (x) puts item x on top of the desk process() processes the top item on the desk and removes it (either sending it to someone else or just throwing it away!) find(x) finds and retrieves the item x if it's somewhere on the desk scan() looks at the top item on the desk, but doesn't remove it. What data structure can you think of that is most like the ADT Desk? Give reasons. Write out in pseudocode in the space below how you would implement the find(x) method in the ADT Desk above, using only stacks. Assume the standard methods for a stack have already been defined. What is the running time of your method above? You must explain your answer to get full marks. Consider the following sequence of numbers that is given to us as input: 12, 3, 44, 23, 11, 7, 29, 32. We sort the sequence described above, using mergesort. Draw a diagram that shows all the recursive calls with their corresponding inputs that will be required to sort this sequence. Explain in a high-level way as well as in pseudo code how to remove a node from a double-linked list.Explanation / Answer
a) The data structure used in the ADT desk is STACKS. Looking at operations given we can conclude this. add(x) adds items on the top similar to that of push operation in the stack. Process(x) processes items from the top of the stack.
b)Pseudocode
Let the stack of desk be D[ ]. ie in an array.
1)Read x
2)find(x)
3)for(i=0;i<=top;i++)
4)if(x==D[i])
5)temp1=i
6)temp2=D[i]
7)endif,end for
8)print temp1 as the position of x in stack
9)print temp2 as the retrieved item from stack
10)end find function
c)Let the size of stack be denoted by 'n'(ie top).
Considering the average case, the 'for' loop would iterate for 'n' times and the 'if' statement in the loop would iterate for 'n-1' times.The statements in the 'if' condition may or may not execute in the loop depending upon the condition. Hence the if condition will become the basic statement. It iterates for n(n-1) times or (n^2 - n) times. Therefore the running time would be (n^2 - n).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.