2019阿里巴巴技术面试题集锦！参考答案1

【知识点详解】 1. **单向链表逆序输出**： - 在链表处理中，逆序输出是一个常见的操作，它可以将链表中的元素顺序反转。在面试题001中，给出了一个非递归的解决方案。首先定义链表节点结构体，包括数据和指向下一个节点的指针。然后通过迭代的方式，用三个指针`prev`、`pcur`和`next`辅助完成逆序。在循环中，`prev`始终指向前一个节点，`pcur`当前节点，`next`指向当前节点的下一个节点。在每次迭代中，更新指针关系，最后将头节点的`next`指针指向新的尾节点，完成逆序。 2. **无数学库求平方根**： - 面试题002考察了基础算法的应用，尤其是二分法的运用。已知`sqrt(2)`近似值，可以在区间`(1.4, 1.5)`上进行二分查找。每次计算中间值`mid`，如果`mid * mid`大于2，则将高界`high`设为`mid`，否则将低界`low`设为`mid`。循环直到相邻两次计算的`mid`差值的绝对值小于设定的精度`EPSINON`。这里使用了二分法的高效性来逐步逼近`sqrt(2)`的精确值。 3. **二叉搜索树中找第K小的节点**： - 面试题003中，二叉搜索树(BST)的特性决定了我们可以利用递归快速找到第K小的节点。BST的性质是左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。因此，若左子树的节点数等于K-1，根节点就是第K小的节点；若左子树节点数小于K-1，则第K小的节点在右子树；否则在左子树。在递归过程中，同时返回当前子树的节点数，与K比较，以确定查找的方向。在C++的代码实现中，定义一个`ResultType`类，记录找到的节点值和是否找到标志，通过`kthSmallestHelper`函数递归搜索。 总结以上，这三道面试题主要考察了以下技术点： - 链表操作：创建链表节点，逆序输出链表。 - 算法应用：二分法求平方根，避免使用现成的数学库函数。 - 二叉搜索树的性质：理解并利用BST的性质进行递归查找，例如找第K小的节点。 这些知识点对于面试者来说，展示了其对基础数据结构的掌握程度，编码能力，以及在实际问题中灵活应用算法的技巧。对于面试官而言，这些问题可以有效地评估候选人是否具备扎实的计算机科学基础和解决实际问题的能力。