常用算法与排序(面试).pdf

第 10章 常用算法与排序 程序由两部分组成：算法和数据。算法是程序的灵魂，我 们在编写程序的过程中无时无刻不在应用算法，可以说精通算 法是一名优秀程序员必须具备的素质。在求职面试中，也会涉 及到很多与算法、排序相关的试题。本章将列举一些常用的算 法和排序的试题，希望对广大求职者有所帮助。 10.1 算法基础 面试真题1：简述什么是单向链表 高频考点： 考点分析： 链表是一种重要的数据结构，该结构由节点组成。每个节点包含两部 数据，第一部分是节点本身的数据，第二部分是指向下一个节点的指针。对 于单向链表，链表中存在两个特殊的节点，分别为“头节点”和 “尾节点”。 头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。单向 链表结构如图 10.1所示。 图10.1 单向链表结构 对于链表的操作，无非是进行节点的查找、插入和删除操作。 （1）查找节点 在进行节点查找时，通常根据节点的数据查找节点。要实现节点的查找， 首先需要解决的问题就是遍历链表中的所有节点。可以从链表头节点开始， 利用循环的方式向下查找，如果当前节点指向的下一个节点不为空，则将下 一个节点设置为当前节点。 （2）插入节点 插入节点需要考虑两种情况。第一种情况是在链表尾节点处插入节点， 这种情况比较简单，只要将当前尾节点的Next （指向下一个节点的指针）指 向新插入的节点就可以了。第二种情况是在链表的中间位置插入节点，首先 需要确定在哪个节点后插入新的节点，这就应该由用户来确定了，本例中为 了演示的需要，笔者将树视图控件中的当前选项设置为当前节点。然后需要 记录当前节点的下一个节点 （避免发生 “脱节”），可以定义一个临时的节 点进行记录。将当前节点的下一个节点指向新添加的节点，再将新添加节点 2 的下一个节点指向临时节点，整个插入节点的流程如图10.2所示。 图10.2 插入节点流程图 （3）删除节点 删除节点与插入节点类似，也需要考虑两种情况。第一种情况是删除尾 节点，这种情况操作相对比较简单，首先找到尾节点之前的一个节点，将该 节点指向的下一个节点设置为空，然后释放尾节点资源。第二种情况是删除 链表中间部分的节点。首先需要找到当前节点的上一个节点，并定义一个临 时节点PriorNode进行记录，然后再定义一个临时节点TempNode记录当前 节点的下一个节点，最后将PriorNode 的下一个节点指向TempNode，并释放 当前节点，整个流程如图10.3所示。 图10.3 删除节点流程图 参考答案： 链表是一种重要的数据结构，该结构由节点组成。每个节点包含两部 数据，第一部分是节点本身的数据，第二部分是指向下一个节点的指针。对 于单向链表，链表中存在两个特殊的节点，分别为“头节点”和 “尾节点”。 头节点本身没有数据，只存储下一个节点的指针，尾节点只存储数据。 面试真题 ：简述什么是双向链表 2 高频考点： 考点分析： 在单向链表的存储结构中，只有一个指示直接后继的指针域，由此从某 个节点出发只能顺指针往后查询其他节点。若要查询节点的直接前驱，则需 要从表头指针出发。为了克服单链表这种单向性的缺点，可以使用双向链表。 在双向链表的节点中有两个指针域，其一指向直接前驱，另一个指向直接后 继。 双向链表的算法描述和单向链表基本相同，但是双向链表在删除和插入 时与单向链表有很大的不同。双向链表在删除节点时，不但要修改节点的直 接后继指针，还要同时修改节点的直接前驱指针。在插入时更是要修改插入 节点的前驱和后继的两个方向上的指针。 参考答案： 在单向链表的存储结构中，只有一个指示直接后