跳转至

3.26. 练习

3.26. Exercises

  1. 使用除以 2 算法将以下值转换为二进制。显示余数的堆栈。

    • 17
    • 45
    • 96

  2. 将以下中缀表达式转换为前缀（使用完整的括号）：

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

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

    • A · B · C · D + E + F

  3. 将上述中缀表达式转换为后缀（使用完整的括号）。

  4. 使用直接转换算法将上述中缀表达式转换为后缀。显示转换过程中堆栈的状态。

  5. 评估以下后缀表达式。显示每个操作数和操作符处理时的堆栈状态。

    • 2 3 · 4 +

    • 1 2 + 3 + 4 + 5 +

    • 1 2 3 4 5 · + · +

  6. 使用列表实现队列 ADT 的另一种方法是将队列的尾部放在列表的末尾。这对 Big-O 性能意味着什么？

  7. 如果反向执行链表 add 方法的两个步骤，会产生什么结果？结果是什么类型的引用？可能会出现哪些问题？

  8. 解释当要删除的项在链表的最后一个节点时，链表 remove 方法是如何工作的。

  9. 解释当项在链表中唯一的节点时，remove 方法是如何工作的。

  10. 修改中缀到后缀的算法，使其能够处理错误。

  11. 修改后缀评估算法，使其能够处理错误。

  12. 实现一个直接的中缀表达式评估器，结合中缀到后缀转换和后缀评估算法的功能。你的评估器应该从左到右处理中缀标记，并使用两个堆栈，一个用于操作符，一个用于操作数，来执行评估。

  13. 将前一个问题中的直接中缀表达式评估器转换为计算器。

  14. 实现队列 ADT，使用列表将队列的尾部放在列表的末尾。

  15. 设计并实现一个实验，以对比两个队列实现的性能。你能从这样的实验中学到什么？

  16. 修改热土豆模拟程序，允许随机选择计数值，使每次传递不再从前一次预测。

  17. 考虑一个现实生活中的情况。提出一个问题，然后设计一个可以帮助回答它的模拟。可能的情况包括：

    • 排队洗车的汽车

    • 超市结账的顾客

    • 在跑道上起飞和降落的飞机

    • 银行出纳员

    确保说明你做出的任何假设，并提供必须考虑的任何概率数据。

  18. 实现一个基数排序机器。基数排序对于十进制整数是一种机械排序技术，使用一个主箱和 10 个数字箱。每个箱子像一个队列一样维护其值的到达顺序。算法从将每个数字放入主箱开始。然后按位考虑每个值。如果考虑的是个位数字，534 被放入数字箱 4 中，667 被放入数字箱 7 中。一旦所有值都放入了对应的数字箱中，从箱子 0 到箱子 9 收集值，并将它们放回主箱。该过程继续进行到十位数字、百位数字等。处理完最后一个数字后，主箱中的值将按顺序排列。

  19. HTML 标签的匹配问题是另一个例子。在 HTML 中，标签有开标签和闭标签两种形式，必须平衡以正确描述网页文档。这个非常简单的 HTML 文档：

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

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

    旨在展示 HTML 语言中标签的匹配和嵌套结构。编写一个程序，检查 HTML 文档中的开闭标签是否正确。

  20. 扩展 Listing 3.15 中的程序，以处理带空格的回文。例如，I PREFER PI 是一个回文，如果忽略空白字符，它正向和反向读法相同。

  21. 实现 size 方法时，我们计算了列表中的节点数量。另一种策略是在列表头部存储节点数量作为附加数据。修改 UnorderedList 类以包括这些信息，并重写 size 方法。

  22. 实现 remove 方法，使其在项不在列表中时也能正确工作。

  23. 修改列表类以允许重复项。这种变化将影响哪些方法？

  24. 在 UnorderedList 类中实现 __str__ 方法。什么是列表的良好字符串表示？

  25. 实现 __str__ 方法，使列表以 Python 的方式显示（使用方括号）。

  26. 实现未排序列表 ADT 中定义的剩余操作（append、index、pop、insert）。

  27. 为 UnorderedList 类实现 slice 方法。它应接受两个参数 start 和 stop，并返回从 start 位置开始到但不包括 stop 位置的列表副本。

  28. 实现有序列表 ADT 中定义的剩余操作。

  29. 考虑无序列表和有序列表之间的关系。是否可以使用继承来构建更高效的实现？实现这个继承层次结构。

  30. 使用链表实现栈。

  31. 使用链表实现队列。

  32. 使用链表实现双端队列（Deque）。

  33. 设计并实现一个实验，以比较 Python 列表与作为链表实现的列表的性能。

  34. 设计并实现一个实验，以比较基于 Python 列表的栈和队列与链表实现的性能。

  35. 上述链表实现称为 单向链表，因为每个节点只有一个对序列中下一个节点的引用。另一种实现被称为 双向链表。在这种实现中，每个节点有对下一个节点的引用（通常称为 next）以及对前一个节点的引用（通常称为 back）。头引用还包含两个引用，一个指向链表中的第一个节点，一个指向最后一个节点。用 Python 编写这种实现。

  36. 创建一个队列的实现，使 enqueue 和 dequeue 操作的平均性能为 \(O(1)\)。

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

    • 17
    • 45
    • 96

  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 rear 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 rear 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 it works correctly in the case where the item is not in the list.
  23. Modify the list classes to allow duplicates. Which methods will be impacted by this change?
  24. Implement the __str__ method in the UnorderedList class. What would be a good string representation for a list?
  25. Implement the __str__ method so that lists are displayed the Python way (with square brackets).
  26. Implement the remaining operations defined in the unordered list ADT (append, index, pop, insert).
  27. 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.
  28. Implement the remaining operations defined in the ordered list ADT.
  29. Consider the relationship between unordered and ordered lists. Is it possible that inheritance could be used to build a more efficient implementation? Implement this inheritance hierarchy.
  30. Implement a stack using linked lists.
  31. Implement a queue using linked lists.
  32. Implement a deque using linked lists.
  33. Design and implement an experiment that will compare the performance of a Python list with a list implemented as a linked list.
  34. Design and implement an experiment that will compare the performance of the Python list-based stack and queue with the linked list implementation.
  35. 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 Python.
  36. Create an implementation of a queue that would have an average performance of \(O(1)\) for enqueue and dequeue operations.
最后更新: 2024年9月12日
创建日期: 2024年9月9日