hw10.md

layout	title
default	Homework 10 - 抽象数据类型与算法

Homework 10 - 抽象数据类型与算法

1. Bubble Sort the list: 33, 56, 17, 8, 95, 22
   Make sure the final result is from small to large.
   Write out the list after the 2nd pass. (10 points)

33 17 8 56 22 95 // 1st pass
17 8 33 22 56 95 // 2nd pass

2. Give a sorted array as list = {60, 65, 75, 80, 90, 95}.
   Design an algorithm to insert the value of x into the sorted array.
   Then test the algorithm with value 50,67,99.

// JavaScript Code

function insertMyX(x, first, last) {
  mid = (last - first) % 2 ? 
        (list[Math.floor((last + first) / 2)] + list[Math.floor((last + first) / 2) + 1]) / 2: 
        list[(last + first) / 2]

  if (x <= list[first])
    console.log(`insert x before list[${first}]`)              // Insert x before list[first]
  else if (x >= list[last])
    console.log(`insert x after list[${last}]`)                // Insert x after list[last]
  else if (x < mid)
    insertMyX(x, first, Math.floor((last + first) / 2))
  else
    insertMyX(x, Math.floor((last + first) / 2) + 1, last)
}

insertMyX(x, 0, 5)

思考：为什么选择插入点在 list 头上、中间、尾巴上的三个数作为算法测试的数据，你能解释吗？

对于二分法而言，这分别代表了三种情况：在区域左侧，在区域内，在区域右侧。三个 case 即可测试算法遇到的三种情况。

3. What is the state of the stack after the following sequence of Push and Pop operations?

Push "anne";    // ["anne"]
Push "get";     // ["anne", "get"]
Push "your";    // ["anne", "get", "your"]
Pop;            // ["anne", "get"],           "your" <- The element popped
Push "my";      // ["anne", "get", "my"]
Push "gun";     // ["anne", "get", "my", "gun"]