描述

开本: 16开纸张: 胶版纸包装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787302488811丛书名: 直击招聘

产品特色

编辑推荐

几百道面试真题，本书汇总国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，按知识点类型对常见的数据结构难点和疑点进行了系统归纳和透彻剖析，并提供了一定数量的自测题便于自我检验。

内容简介

本书汇集国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，按知识点类型对常见的数据结构难点和疑点进行了系统归纳和透彻剖析，并提供了一定数量的自测题以便于读者自我检验。
　　全书逻辑清晰、通俗易懂，适合参加IT企业校园招聘和面试笔试环节的同学复习，也适合数据结构和算法设计编程爱好者以及在校学生阅读和提高。

作者简介

李春葆：武汉大学教授，主要研究方向为数据挖掘和算法设计，从事近30年计算机C/C 语言、数据结构和算法设计等课程的线本科教学工作，具备丰富的教学经验，曾参于深圳名企的笔试和面试题库建设。出版多本C/C 语言、数据结构、算法设计与分析及数据库开发方面的精品教材和教学辅导书。
李筱驰：美国俄亥俄州立大学计算机科学专业硕士毕业，曾参加谷歌等名企面试，具备比较丰富的企业笔试和面试经验。目前在西雅图亚马逊总部工作。

目　　录

在面试笔试中数据结构的考点主要包含两个方面：一是常用数据结构的基本知识点，包括各种数据结构的逻辑特点、存储方式和运算算法，如一个城市图的存储、在城市图中查找两个城市之间的短路径等；二是常用数据结构的应用知识点，能够熟练地利用数据结构解决问题，如用栈或者队列求解迷宫问题，用栈求解皇后问题等。

很多数据结构都是递归数据结构，递归也是求解问题的基本方法，所以面试者必须具有递归算法设计能力，掌握从递归模型、递归算法执行过程到递归算法设计的一般方法，为二叉树、图等复杂数据结构算法设计打下坚实的基础。

本书系统归纳了数据结构常见的知识要点，汇集国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析，透彻地剖析了难点和疑点，每道面试题给出了难度标识，从一星到五星难度依次递增。

在本书的编写过程中参考了众多网站和博客，无法一一列出，在此编者表示衷心感谢。

编者

2018年3月

在线试读

·第3章·线性表Ⅱ——链表
* 链表存储结构的特点。* 单链表结构及其算法设计方法。* 双链表结构及其算法设计方法。* 循环链表结构及其算法设计方法。* 灵活运用链表解决一些较复杂的应用问题。3.1 线性表链式存储结构概述3.1.1 要点归纳 1. 链表　　线性表的链式存储结构称为链表，通常线性表中的一个元素用一个链表结点存放，每个结点增加指针域表示结点之间的逻辑关系。　　有一个指针域的链表称为单链表（通常结点指针指向其后继结点）；有两个指针域的链表称为双链表（通常结点的一个指针指向其后继结点，另外一个指针指向其前驱结点）。　　链表和顺序表相比，由于每个结点需要额外空间表示逻辑关系，所以链表的存储密度相对较低（双链表的存储密度低于单链表）；当查找序号为i的结点时需要从前向后扫描，对应的时间为O(n)，所以链表不具有随机存取特性。但由于链表中的每个结点单独分配空间，所以链表具有很好的适应性，不需要事先确定空间大小；在链表中插入和删除结点只需要修改前后相关结点的指针域，不用移动结点。 2. STL的list链表容器　　STL提供了list链表容器，它是一个双链表类模板，可以从任何地方快速地插入与删除。它的每个元素之间用指针相连，不能随机访问元素。其主要的成员函数如下。* size()：返回表中实际元素的个数。* empty()：判断表是否为空。* push_back()：在表的尾部插入元素。* pop_back()：删除后一个元素。* remove ()：删除所有指定值的元素。* erase()：从容器中删除一个或几个元素。* clear()：删除所有的元素。* insert(pos,elem)：在pos处插入elem元素并返回该元素的位置。* swap()：交换两个元素。* begin()：该函数返回链表容器的第1个元素。* end()：该函数返回链表容器的后一个元素后面的一个位置。　　在编程中使用链表的地方都可以用list链表容器代替，但为了理解链表的概念和原理，后面的算法没有使用list，而是直接采用基础编程。3.1.2 面试题解析　　【面试题3-1 ?】对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（）。　　A．顺序存储方式 B．链式存储方式 C．散列存储方式 D．以上均可以　　答：线性表主要有顺序和链式两类存储方式，而后者能够进行较快速的插入和删除。答案为B。　　【面试题3-2 ?】以下（）不是链表的特征。　　A．数据在内存中一定是连续的 B．在插入或删除时无须移动其他元素　　C．可以随机访问表内的元素 D．需要事先估计存储空间　　答：以上只有在插入或删除时不需要移动其他元素是链表的特征，其他都不是。答案为 A、C、D。　　【面试题3-3 ?】以下关于链式存储结构的叙述中（）是不正确的。　　A．结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构　　B．逻辑上相邻的结点物理上不必邻接　　C．可以通过计算直接确定第i个结点的存储地址　　D．插入、删除运算操作方便，不必移动结点　　答：链式存储结构不具有随机存取特性，即不能通过计算直接确定第i个结点的存储地址。答案为C。　　【面试题3-4 ?】频繁的插入、删除操作使用什么结构比较合适，链表还是数组？　　答：若采用数组存储含n个元素的线性表，插入、删除操作平均大约需要移动n/2个元素，而采用链表存储线性表时插入、删除操作不需要移动元素，只需要修改结点的指针域，所以更高效，答案为链表。3.2 单链表算法设计3.2.1 要点归纳 1. 单链表的结构和基本运算　　在单链表中，声明结点类型如下：　　 typedef struct LNode { T data; struct LNode *next; //指向后继结点 } LinkNode; //声明单链表结点类型　　　　通常，单链表采用的是带头结点的结构，如图3.1所示，这样做的目的是使得空表和非空表、首结点和其他结点的处理相一致，从而简化算法设计。
图3.1 带头结点的单链表　　在单链表中如果有头结点，通常用头结点的地址（即头指针）来标识整个单链表，第1个数据结点称为首结点，指向首结点的指针称为首指针。在不带头结点的单链表中通常用首指针来标识整个单链表，指向尾结点的指针称为尾指针。　　在单链表中从一个结点出发只能向后查找后继结点，所以插入和删除一个结点需要已知前驱结点，通过修改相关指针域达到插入和删除结点的目的。 2. 单链表的算法设计　　基于查询操作的算法设计　　这类算法首先是通过单链表的指针链进行查找，找到满足条件的结点后进行插入或者删除操作。　　【例3-1】设计一个算法删除非空单链表L中所有值的结点（假设这样的结点可能有多个）。　　解：通过一遍扫描求出结点值为max，再从头到尾扫描删除所有值为max的结点。由于在单链表中删除结点需要已知前驱结点，为此用pre指向p结点的前驱结点，两者同步移动。对应的算法如下： void Delmaxnodes(LinkNode *&L) { LinkNode *pre=L,*p=L->next; T max=p->data; while(p!=NULL) //查找结点的结点值max { if(p->data>max) max=p->data; p=p->next; } p=L->next; while(p!=NULL) //查找等于max的结点并删除 { if(p->data==max) { pre->next=p->next; //删除p结点 free(p); //释放p结点 p=pre->next; //让p继续指向pre结点的后继结点 } else { pre=p; //pre、p指针同步后移 p=p->next; } } }　　　　基于建表思路的算法设计　　单链表的建表就是根据给定的数据序列来整体创建单链表，其方式有头插法建表和尾插法建表。　　头插法建表就是先创建头结点L，并将其next指针设置为NULL。每次创建一个新结点s，将它插入到头结点之后、首结点之前，即s->next=L->next;L->next=s。所以采用头插法建立的单链表的结点值顺序与数据序列的顺序相反。　　尾插法建表就是先创建头结点L，设置一个指向尾结点的指针r，初始时r=L。每次创建一个新结点s，将它插入到单链表的末尾，即r->next=s;r=s（保证r始终指向尾结点）。后需要将尾结点next域设置为空，即r->next=NULL。所以采用尾插法建立的单链表的结点值顺序与数据序列的顺序相同。　　这两个建表算法尽管简单，但是有很多相关算法的基础。在一些情况下，建表的结点已经存在，只需要采用建表思路修改结点的指针域来生成新的单链表。　　【例3-2】设计一个算法将非空单链表L的所有结点逆置。　　解：用p扫描所有数据结点，先建立只有头结点的空单链表L，然后将p结点采用头插法一个一个地插入。对应的算法如下：　　 void Reverse(LinkNode *&L) { LinkNode *p=L->next,*q; L->next=NULL; //变为空的单链表 while(p!=NULL) //扫描所有数据结点 { q=p->next; //临时保存p结点的后继结点 p->next=L->next; //头插法 L->next=p; p=q; } }　　　　有序单链表的算法设计　　可以利用有序单链表的有序性和二路归并等提高算法的效率，其思路与有序顺序表的相关算法思路相同。　　【例3-3】设计一个算法将两个非空递增有序单链表合并为一个递减有序单链表，要求空间复杂度为O(1)。　　解：题目要求空间复杂度为O(1)，所以只能利用两个单链表L1、L2的数据结点来新建合并后的单链表L3。因为是由两个递增单链表创建一个递减单链表，所以采用头插法来建立单链表L3。对应的算法如下：　　 void Merge(LinkNode *&L1,LinkNode *&L2,LinkNode *&L3) { LinkNode *p1=L1->next,*p2=L2->next,*q; free(L1);L1=NULL; //释放L1头结点并置为NULL free(L2);L2=NULL; //释放L2头结点并置为NULL L3=(LinkNode *)malloc(sizeof(LinkNode)); L3->next=NULL; while(p1!=NULL && p2!=NULL) { if(p1->datadata) { q=p1->next; //临时保存p1结点的后继结点 p1->next=L3->next; //采用头插法将p1结点插入到L3中 L3->next=p1; p1=q; } else { q=p2->next; //临时保存p2结点的后继结点 p2->next=L3->next; //采用头插法将p2结点插入到L3中 L3->next=p2; p2=q; } } if(p2!=NULL) //若p2没有扫描完,让p1指向p2结点 p1=p2; while(p1!=NULL) //将没有扫描完的依次扫描 { q=p1->next; //临时保存p1结点的后继结点 p1->next=L3->next; //采用头插法将p1结点插入到L3中 L3->next=p1; p1=q; } }　　　　上述算法的时间复杂度为O(m n)。如果要求不破坏单链表L1、L2，那么就需要采用复制方法创建单链表L3的所有数据结点，对应的空间复杂度为O(m n)。3.2.2 面试题解析　　【面试题3-5 ?】在一个单链表HL中，若要在指针first所指结点的后面插入一个指针second所指向的结点，则执行（）。　　A．second->next=first->next ; first->next=second;　　B．first->next=second->next; second=first;　　C．second->next=first->next ; second->next=first;　　D．first->next=second->next; second->next=first;　　答：先让second结点的next指针域指向first的后继结点，即second->next=first->next，再让first结点的指针域指向second结点，即first->next=second。答案为A。　　【面试题3-6 ?】在一个单链表中，若删除p所指结点的后继结点，则执行（）。　　A．p = p->next; p->next = p->next->next;　　B．p->next = p->next;　　C．p->next = p->next->next;　　D．p = p->next->next;　　答：在删除p所指结点的后继结点时，让p结点的指针域指向其后继结点的后继结点，即p->next=p->next->next。答案为C。　　【面试题3-7 ??】将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（）。　　A．O(m) B．O(1) C．O(n) D．O(m n)　　答：其操作是先在长度为m的单链表中通过遍历找到尾结点p（时间复杂度为O(m)），再让p结点的指针域指向长度为n的单链表的首结点（时间复杂度为O(1)），总的时间复杂度为O(m)。答案为A。　　【面试题3-8 ??】输入一个链表的头结点，从尾到头输出每个结点的值。链表的结点定义如下：　　 struct ListNode { int? m_nKey; ListNode* m_pNext; };　　　　解：除了结点类型不同，其他与例3-2完全一样。尽管该题不难，但该题以及变种经常出现在各大公司的面试、笔试题中。　　【面试题3-9 ???】设计一个递归算法逆置一个非空单链表。　　解：例3-2是采用头插法实现单链表的逆置的，这里要求采用递归方法。　　通常，单链表的递归算法是针对不带头结点的单链表。假设由首结点指针first标识一个不带头结点的非空单链表，设f(first)返回逆置后的首结点指针，为大问题，则f(first->next)返回逆置后的首结点指针p，为小问题，如图3.2所示。当小问题解决后，大问题的求解只需要将a1结点（first指向它）链接到first->next结点的末尾就可以了。对应的递归模型如下：　　 f(first) ?返回first 当first=NULL或者只有一个结点时 f(first) ?f(first->next);将first结点链接到first->next的后面其他情况
图3.2 小问题的求解结果　　对应的算法如下：　　 LinkNode *reverse(LinkNode *first) //逆置不带头结点的单链表first { LinkNode *p; if(first==NULL || first->next==NULL) return first; p=reverse(first->next); first->next->next=first; //将first结点链接到first->next结点的后面 first->next=NULL; //将first结点作为逆置后的尾结点 return p; } void Reverse(LinkNode *&L) //逆置带头结点的单链表L { L->next=reverse(L->next); //L->next为不带头结点的单链表 }　　　　注意：　　在reverse(LinkNode *first)函数中，first是值参数（对应的实参是不变的），逆置后单链表的首结点指针是作为返回值实现的，如果将其改为引用参数，结果是错误的。
　　【面试题3-10 ???】将一个非空单链表中序号从i到j的结点逆置。　　解：又是单链表的逆置，但需要考虑以下几点。　　? 参数i、j可能错误，例如它们的值超过了单链表的长度等，所以对应函数设计为bool函数类型。　　? 先找到第i-1个结点pre，置pre->next=NULL（断开）。p扫描pre结点原来的后面结点一直到第j个结点（让r指向第1个p结点），将每个p结点采用头插法插入到pre结点之后（逆置这些结点，逆置后的尾结点就是r结点）。后将余下的结点链接在r结点的后面。　　对应的算法如下：　　 int ListLength(LinkNode *L) //求单链表的长度 { LinkNode *p=L;int i=0; while(p->next!=NULL) { i ; p=p->next; } return(i); } bool Reverseij(LinkNode *&L,int i,int j) { int k=0,n; //k用于扫描时的结点计数 LinkNode *pre=L,*p,*q,*r; n=ListLength(L); //n为单链表L的长度 if(i<0 || i>n || j<0 || j>n || i>j) //参数错误返回假 return false; while(k //查找第i-1个结点pre { k ; pre=pre->next; } p=pre->next; //p指向第1个逆置的结点 r=p; //用r保存第1个逆置的结点 pre->next=NULL; //断开 while(k //将p结点到第j个结点采用头插法插入到pre结点之后 { k ; q=p->next; //q临时保存p结点的后继结点 p->next=pre->next; pre->next=p; p=q; } r->next=q; //将第j个结点的后继结点连接到r结点之后 return true; }　　　　注意单链表结构中没有存放长度的地方，有人在编程时假设头结点中存放了结点个数，甚至直接用L->length表示长度，这都是错误的。如果是在线编程，程序可能会导致崩溃；如果是面试或者笔试，严厉的考官会直接判0分。
　　【面试题3-11 ???】对于一个带头结点的整数单链表，以第1个结点为基准，将所有小于其值的结点移动到它的前面，将所有大于等于其值的结点移动到它的后面。　　解：base为基准值，pre指向首结点，p指向其后继结点。当p≠NULL时循环，若p->data LinkNode *pre,*p; T base; if(L==NULL || L->next==NULL) return; base=L->next->data; //base存放基准值 pre=L->next; p=pre->next; while(p!=NULL) { if(p->data //若p结点值小于基准值 { pre->next=p->next; //删除p结点,其采用头插法插入到L中 p->next=L->next; L->next=p; p=pre->next; //p继续指向pre结点的后继结点 } else { pre=p; //pre、p同步后移 p=pre->next; } } }　　　　【面试题3-12 ???】单链表的分割：将一个非空单链表中所有小于等于x的结点移动到所有大于x结点的前面。　　解法1：pre指向首结点，p指向其后继结点。当p≠NULL时循环，若p->data≤x，通过pre结点将p结点删除，并采用头插法插入到前面，否则pre、p同步向后面移动。对应的算法如下：　　 void move1(LinkNode *&L,T x) { LinkNode *pre=L,*p=pre->next; while(p!=NULL) { if(p->data<=x) //删除p结点,其采用头插法插入到L中 { pre->next=p->next; p->next=L->next; L->next=p; p=pre->next; } else { pre=p; //pre、p同步后移 p=pre->next; } } }　　　　解法2：扫描单链表L，采用尾插法建立两个单链表L和L1，将所有小于等于x的结点插入到L中，将所有大于x的结点插入到L1中，后将L1和L1链接起来。对应的算法如下：　　 void move2(LinkNode *&L,int x) { LinkNode *p=L->next,*r,*r1,*L1; r=L; L1=(LinkNode *)malloc(sizeof(LinkNode)); r1=L1; while(p!=NULL) { if(p->data<=x) //将p结点链接到L的末尾 { r->next=p; r=p; } else //将p结点链接到L1的末尾 { r1->next=p; r1=p; } p=p->next; } r->next=L1->next; //将L1链接在L的后面 r1->next=NULL; free(L1); }　　【面试题3-13 ??】设计一个算法求非空单链表的中间位置结点。例如，(1,2,3,4,5)的中间位置结点是3（元素个数为奇数），而(1,2,3,4)的中间位置结点是2（元素个数为偶数）。　　解：采用快、慢两个指针fast和slow，初始时均指向头结点。当fast≠NULL且fast->next≠NULL时循环，慢指针向后移动一个结点，即slow=slow->next，快指针向后移动两个结点，即fast=fast->next->next。循环结束后，slow指向的结点就是满足题目要求的中间位置结点。对应的算法如下：　　 LinkNode * Middle(LinkNode *L) { LinkNode *fast=L,*slow=L; while(fast!=NULL && fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow; }　　　　【面试题3-14 ???】单链表重新排列1：将一个非空单链表(a1,a2,…,an,b1,b2,…,bn)重新排列为(a1,b1,a2,b2,…,an,bn)，要求空间复杂度为O(1)。　　解：在第2章中相同问题的数据序列是采用数组存储的，解决方法是高难度的完美洗牌算法，这里采用单链表存储数据，相应算法要简单得多。　　采用尾插法建新表L，r作为尾指针。p指向a1结点，调用上一个面试题的算法求出中间结点q，q=q->next指向b1结点，当q≠NULL时循环，依次将p、q结点链接到新表的表尾。对应的算法如下：　　 void Rearrange1(LinkNode *&L) { LinkNode *p,*q,*r; if(L->next==NULL) return; r=L; //r作为新链表的尾结点 p=L->next; //p指向a1结点 q=Middle(L); //q指向中间结点（这里单链表数据结点的个数是偶数） q=q->next; //q指向b1结点 while(q!=NULL) { r->next=p;r=p; //将p结点链接到新链表的表尾 p=p->next; r->next=q;r=q; //将q结点链接到新链表的表尾 q=q->next; } r->next=NULL; //尾结点的next域置空（尽管这里不需要,但这样做是一个好习惯） }　　　　【面试题3-15 ????】单链表重新排列2：将一个非空单链表(a1,a2,…,an?1,an)重新排列为(a1,an,a2,an?1,…)。　　解：将原单链表L按中间结点拆分为两个单链表，其中，L中含前半部分结点，L1含后半部分结点（注意，当n为偶数时，两个单链表中的结点个数相同；当n为奇数时，L中比L1中多一个结点）。将L1逆置，然后采用上一个面试题的方法产生终的结果单链表。对应的算法如下：

书摘插画

抢先评论了 “直击招聘——程序员面试笔试数据结构深度解析” 取消回复

还没有评论。

直击招聘——程序员面试笔试数据结构深度解析

汇总几百道国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析

作者:李春葆、李筱驰出版社:清华大学出版社出版时间:2018年05月

ISBN: 9787302488811

年中特卖用“SALE15”折扣卷全场书籍85折！可与三本88折，六本78折的优惠叠加计算！全球包邮!

描述

目录

抢先评论了 “直击招聘——程序员面试笔试数据结构深度解析” 取消回复

评论

直击招聘——程序员面试笔试数据结构深度解析

汇总几百道国内外众多著名IT企业近几年的数据结构面试笔试真题并予以解析

作者:李春葆、李筱驰 出版社:清华大学出版社 出版时间:2018年05月

ISBN: 9787302488811

年中特卖用“SALE15”折扣卷全场书籍85折！可与三本88折，六本78折的优惠叠加计算！全球包邮!

描述

目 录

抢先评论了 “直击招聘——程序员面试笔试数据结构深度解析” 取消回复

评论

相关产品

新100个基本：自我更新指南

世界著名学府给孩子的成长训言

哈佛凌晨四点半：哈佛大学送给青少年的礼物

靠自己去成功：刘墉励志珍藏系列（献给所有受尽呵护，但不得不独自面对未来的年轻人；成功要自己去成功，如同成长要自己去成长）

作者:李春葆、李筱驰出版社:清华大学出版社出版时间:2018年05月

目录