DS Basic Data Structures: Exercises

Section 3.26 Basic Data Structures: Exercises

Exercises Exercises

1.

Convert the following values to binary using the Divide by 2 algorithm. Show the stack of remainders.

2.

Convert the following infix expressions to prefix (use full parentheses):

(A + B) · ( C + D) · (E + F)
A + ((B + C) · (D + E))
A · B · C · D + E + F

3.

Convert the above infix expressions to postfix (use full parentheses).

4.

Convert the above infix expressions to postfix using the direct conversion algorithm. Show the stack as the conversion takes place.

5.

Evaluate the following postfix expressions. Show the stack as each operand and operator is processed.

- 2 3 · 4 +
1 2 + 3 + 4 + 5 +
1 2 3 4 5 · + · +

6.

The alternative implementation of the queue ADT is to use a list such that the tail of the queue is at the end of the list. What would this mean for Big-O performance?

7.

What is the result of carrying out both steps of the linked list add method in reverse order? What kind of reference results? What types of problems may result?

8.

Explain how the linked list remove method works when the item to be removed is in the last node.

9.

Explain how the remove method works when the item is in the only node in the linked list.

10.

Modify the infix-to-postfix algorithm so that it can handle errors.

11.

Modify the postfix evaluation algorithm so that it can handle errors.

12.

Implement a direct infix evaluator that combines the functionality of infix-to-postfix conversion and the postfix evaluation algorithm. Your evaluator should process infix tokens from left to right and use two stacks, one for operators and one for operands, to perform the evaluation.

13.

Turn your direct infix evaluator from the previous problem into a calculator.

14.

Implement the queue ADT, using a list such that the tail of the queue is at the end of the list.

15.

Design and implement an experiment to do benchmark comparisons of the two queue implementations. What can you learn from such an experiment?

16.

Modify the hot potato simulation to allow for a randomly chosen counting value so that each pass is not predictable from the previous one.

17.

Consider a real life situation. Formulate a question and then design a simulation that can help to answer it. Possible situations include:

Cars lined up at a car wash
Customers at a grocery store check-out
Airplanes taking off and landing on a runway
A bank teller

Be sure to state any assumptions that you make and provide any probabilistic data that must be considered as part of the scenario.

18.

Implement a radix sorting machine. A radix sort for base 10 integers is a mechanical sorting technique that utilizes a collection of bins, one main bin and 10 digit bins. Each bin acts like a queue and maintains its values in the order that they arrive.

The algorithm begins by placing each number in the main bin. Then it considers each value digit by digit. The first value is removed and placed in a digit bin corresponding to the digit being considered. For example, if the ones digit is being considered, 534 is placed in digit bin 4 and 667 is placed in digit bin 7.

Once all the values are placed in the corresponding digit bins, the values are collected from bin 0 to bin 9 and placed back in the main bin. The process continues with the tens digit, the hundreds, and so on. After the last digit is processed, the main bin contains the values in order.

19.

Another example of the parentheses matching problem comes from Hypertext Markup Language (HTML). In HTML, tags exist in both opening and closing forms and must be balanced to properly describe a web document. This very simple HTML document:

<html>
   <head>
      <title>
         Example
      </title>
   </head>

   <body>
      <h1>Hello, world</h1>
   </body>
</html>

is intended only to show the matching and nesting structure for tags in the language. Write a program that can check an HTML document for proper opening and closing tags.

20.

Extend the program from Listing 3.15 to handle palindromes with spaces. For example, I PREFER PI is a palindrome that reads the same forward and backward if you ignore the blank characters.

21.

To implement the size method, we counted the number of nodes in the list. An alternative strategy would be to store the number of nodes in the list as an additional piece of data in the head of the list. Modify the UnorderedList class to include this information and rewrite the size method.

22.

Implement the remove method so that does not throw an exception in the case where the item is not in the list (by leaving the list unchanged).

23.

Modify the list classes to allow duplicates. Which methods (if any) will be impacted by this change? Make sure you update the comments at the start of the methods to reflect any changes in the input and output the method expects.

24.

Implement the remaining operations defined in the unordered list ADT (append, index, pop, insert).

25.

Implement a slice method for the UnorderedList class. It should take two parameters, start and stop, and return a copy of the list starting at the start position and going up to but not including the stop position.

26.

Implement the remaining operations defined in the ordered list ADT.

27.

Use inheritance to implement a MinMaxUnorderedList that is a child of UnorderedList and adds a minimum and maximum property. This will allow users to access the minimum and maximum values in the list in an \(O(1)\) operation. This will require changes to any methods that add or remove items from the list. How will those changes affect the Big-O characteristics of those methods?

28.

Implement a stack using linked lists.

29.

Implement a queue using linked lists.

30.

Implement a deque using linked lists.

31.

Design and implement an experiment that will compare the performance of a Java ArrayList with a list implemented as a linked list.

32.

Design and implement an experiment that will compare the performance of the Java ArrayList-based stack and queue with the linked list implementation.

33.

The linked list implementation given above is called a singly linked list because each node has a single reference to the next node in the sequence. An alternative implementation is known as a doubly linked list. In this implementation, each node has a reference to the next node (commonly called next) as well as a reference to the preceding node (commonly called back). The head reference also contains two references, one to the first node in the linked list and one to the last. Code this implementation in Java.

34.

Create an implementation of a queue that would have an average performance of \(O(1)\) for enqueue and dequeue operations.

You have attempted of activities on this page.

Prev Top Next