Examen de muestra/práctica Septiembre 2019, preguntas PDF

Preview

Summary

Exam sample questions...

Description

ICOM 4035 / CIIC 4020 Data Structures - CS2

Sample Exam Pag 1 of 3

SE1.

Consider the following need that a software developer has encountered during the design of a system. She has the need to work with a stack of integers, but it must support to work with blocks (or chunks) of integers. Whenever a push operation is done, one or more integers are pushed as one block. Such blocks can be different sizes greater than or equal to 1. She knows that she can do this without the need to write a new implementation of the stack from scratch. For this she will use an implementation of the Stack ADT as we saw in class.She wants to use an implementation of Stack as a class SomeStack that she wrote in this course. Class SomeStack could be any of the classes that we presented in lectures implementing Stack. So, her approach is to implement the following class, which is a subclass of SomeStack. public class BlocksStack extends SomeStack { // NO EXPLICIT INSTANCE VARIABLE IN THIS CLASS /** Pushes a new chunk on top of the stack, whose elements are the elements of the array given as explicit parameter. All elements in the array are added as part of a “single” chunk. @param arr the array whose elements are added to the stack, from 0 to arr.length-1. **/ public void push(Integer[] arr) {...} /** Works as the normal push. But the element to be added to the stack is added as a chunk of size 1. @param e the element to be added to the stack. **/ public void push(Integer e) {...} /** Pops all the elements from the block on top of the stack. Elements are returned as content of an array. @return An array of the elements on the block on top of the stack; of null if the stack is empty. **/ public Integer[] popBlock() {...} /** Works as the normal pop operation on stacks, but requires that the block on the top of the stack has size == 1. If block on top is not of size 1, the announced exception is thrown. @return If valid to do so, returns the single element from the block of size 1 on top of the stack. It returns null if the stack is empty. @throws IllegalStateException Whenever the stack is not empty and the block at the top is of size > 1. **/ public Integer pop() throws IllegalStateException {...} } // end of class BlocksStack

For example: Assume s is of type BlocksStack, initially empty, and let a1 = {3, 5, 8} and a2 = {7, 9}, both of type Integer[]. Consider the following sequence of operations executed in the given order 1..8:

1. 2. 3. 4.

Operation s.push(a1); s.push(5); s.push(8); s.push(a2);

Returned Object Nothing Nothing Nothing Nothing

5. 6. 7. 8.

Operation s.popBlock(); s.pop(); s.popBlock(); s.pop();

Returned Object Array {7, 9} Integer 8 Array {5} EXCEPTION

And from that, she gave me the idea for this exercise. Provide the implementation for each of the specified methods so that the class BlockStack achieves the desired functionality. Note that your solution should work as long as the super class is a valid implementation of the Stack ADT. You don’t have to worry about size() or top() here; just complete the implementation of the following four methods as described in the above skeleton of the class BlockStack.

1.1. public void push(Integer[] arr) {...} Professor Pedro I. Rivera Vega File:..../SAMPLE Exam

ICOM 4035 / CIIC 4020 Data Structures - CS2

Sample Exam Pag 2 of 3

1.2. public void push(Integer e) {...} 1.3. public Integer[] popBlock() {...} 1.4. public Integer pop() throws IllegalStateException {...} Hint: You need to think of some additional information (which has to be an integer too) that you need to store in the stack of integers that is inherited as part of the two new push operations. That additional information will be crucial for the implementations of the new pop operations. Always keep in mind that what the super class provides is just a simple stack of integers, and that you only know that it is a correct implementation of Stack ADT.

SE2. Recall the LinkedPositionalList (partially given in the addendum pages) that implements a list of type PositionalList. Add the following method to that class to count the number of pairs of consecutive elements in the list that have same value. The implementation should be based on direct operations with nodes of the internal linked list and not in other methods of PositionalList, and should have worst-case execution time O(n), assuming n is the size of the list. This method presumes that the generic data type of the elements, E, is instantiated to a Comparable object data type; otherwise, it must throw IllegalStateException. For example, if list is of type LinkedPositionalList and we have list = (8, 5, 6, 6, 6, 5, 3, 3, 5, 8, 8, 5), then list.countEqCPairs() will return 4.

SE3. Working with Stacks - Consider the Stack ADT. Develop a static method to copy a stack which is passed as its explicit parameter. For this, assume that MyStack is an implementation of Stack. The copy method should not alter the stack to be copied, neither should it be altered if the returned copy is modified afterwards. The method should return a new stack that is a separate copy of the one whose reference is received as the explicit parameter value. Note: You should only use the Stack methods in this question; no other data structure (such as Java lists or anything else) are allowed. The API for that method is: public static Stack copy(MyStack s).

Professor Pedro I. Rivera Vega File:..../SAMPLE Exam

ICOM 4035 / CIIC 4020 Data Structures - CS2

Sample Exam Pag 3 of 3

SE4.

For each of the following functions write the big Oh expression, in terms of n, which corresponds to the worst-case execution time of the given method.

Function and Time (2 pts each)

Brief Explanation (5 pts each)

boolean whatever(int n, int x) { int w = 1; for (int i=1; i...