1、程序员面试-7 及答案解析(总分：100.00，做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.如何找出数组中只出现一次的数字 （分数：3.00）_2.如何判断一个整数 x 是否可以表示成 n(n2)个连续正整数的和 （分数：3.00）_3.数组和链表的区别是什么 （分数：3.00）_4.何时选择顺序表、何时选择链表作为线性表的存储结构为宜 （分数：3.00）_5.如何使用链表头 （分数：3.00）_6.如何实现单链表的插入、删除操作 （分数：3.00）_7.如何找出单链表中的倒数第 k 个元素 （分数：3.00）_8.如何实现单链表反转 （分数：3.00）_9.如何从
2、尾到头输出单链表 （分数：3.00）_10.如何寻找单链表的中间结点 （分数：3.00）_11.如何进行单链表排序 （分数：3.00）_12.如何实现单链表交换任意两个元素(不包括表头) （分数：3.00）_13.如何检测一个较大的单链表是否有环 （分数：4.00）_14.如何判断两个单链表(无环)是否交叉 （分数：4.00）_15.如何删除单链表中的重复结点 （分数：4.00）_16.如何合并两个有序链表(非交叉) （分数：4.00）_17.什么是循环链表 （分数：4.00）_18.如何实现双向链表的插入、删除操作 （分数：4.00）_19.为什么在单循环链表中设置尾指针比设置头指针更好 （
3、分数：4.00）_20.如何删除结点的前驱结点 （分数：4.00）_21.如何实现双向循环链表的删除与插入操作 （分数：4.00）_22.如何在不知道头指针的情况下将结点删除 （分数：4.00）_23.如何统计一行字符中有多少个单词 （分数：4.00）_24.如何将字符串逆序 （分数：4.00）_25.如何找出一个字符串中第一个只出现一次的字符 （分数：4.00）_26.如何输出字符串的所有组合 （分数：4.00）_27.如何检查字符是否是整数?如果是，返回其整数值 （分数：4.00）_28.如何查找字符串中每个字符出现的个数 （分数：4.00）_程序员面试-7 答案解析(总分：100.00，
4、做题时间：90 分钟)一、论述题(总题数：28，分数：100.00)1.如何找出数组中只出现一次的数字 （分数：3.00）_正确答案：()解析：一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。要求时间复杂度是 O(n)，空间复杂度是 O(1)。 如果本题对时间复杂度没有要求的话，最容易想到的方法就是首先对这个整型数组排序，然后从第一个数字开始遍历，比较相邻的两个数，从而找出这个只出现一次的数字，所以其时间复杂度最快为 O(nlogn)。由于时间复杂度与空间复杂度的限制，该种方法不可取，所以需要一种更高效的方式。题目强调只有一个数字出现一次，其他的出现了
5、两次，首先想到的是异或运算的性质：任何一个数字异或它自己都等于 0，根据这一特性，如果从头到尾依次异或数组中的每一个数字，因为那些出现两次的数字全部在异或中抵消掉了，所以最终的结果刚好是那个只出现一次的数字。 程序示例如下： #includestdio.h int findNotDouble(int a,int n) int result=a0; int i; for(i=1;in;+i) result=ai; return result; int main() int array=1,2,3,2,4,3,5,4,1; int len=sizeof(array)/sizeof(array0);
6、 int num=findNotDouble(array,len); printf(“%d/n“,num); return 0; 程序输出结果： 5 引申：如果题目改为整型数组中除了两个数字之外，其他的数字都出现了两次，如何求解这两个只出现一次的数? 在上述解决方案的基础上，如果能够把原数组分为两个子数组，在每个子数组中，包含一个只出现一次的数字，而其他数字都出现两次，问题就可以很容易地解决了：分别对两个子数组按照上述解决方案执行结果。 现在问题的难点就是如何划分为两个符合求解方案的子数组。首先从头到尾依次异或数组中的每一个数字，因为其他数字都出现了两次，在异或中全部抵消掉了，所以最终得到的结
7、果将是两个只出现一次的数字的异或结果。而这两个数字肯定不一样，那么这个异或结果肯定不为 0，也就是说在这个结果数字的二进制表示中至少就有一位为 1，否则就为 0 了。在结果数字中找到第一个为 1 的位的位置，记为第 N 位，此时以第 N 位是不是 1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第 N 位都为 1，而第二个子数组的每个数字的第 N 位都为 0。通过这种方法就可以把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。 程序示例如下： #includestdio.h void fmdOnce(int data,int n,int
8、int r1=0; for(int i=0;in;i+) r1=datai; int bitNum=0; while(!(r1 +bitNum; int flag=(1bitNum); num1=0; num2=0; for(int j=0;jn;j+) if(dataj else num2=dataj; int main() int array=1,2,3,2,4,3,5,1; int num1, hum2; findOnce(array,sizeof(array)/sizeof(array0),num1,num2); printf(“%d/n%d/n“,num1,num2); return
9、 0; 程序输出结果： 5 42.如何判断一个整数 x 是否可以表示成 n(n2)个连续正整数的和 （分数：3.00）_正确答案：()解析：假设 x 可以表示成 n(n2)个连续正整数的和，那么数学表达式如下：x=m+(m+1)+(m+2)+.+(m+n-1)，其中 m 为分解成的连续整数中最小的那一个，由于 m 是大于等于 1 的正整数，可知x=(2m+n-1)n/2，变换之后 m=(2x/n-n+1)/2，由 m 的范围可以知道(2x/n-n+1)/21，以上就是 X和 n 的关系。给定一个 n，看是否 x 能分解成 n 个连续整数的和，可以判断是否存在 m，也就转换成(2x/n-n+1)
10、是否是偶数的问题。 判断一个数是否是偶数，是一个比较容易解决的问题，所以本题就迎刃而解了，程序示例如下： #inchudestdio.h #includemath.h int main() int m=0,n=0,start=0,end=0,flag=0; float temp=0.0; printf(“请输入被分解的数:“); scanf(“%d“, printf(“请输入需要被分解的数字的个数:“); scanf(“%d“, temp=(float)m/n-(float)(n-1)/2; if(temp=(int)temp) for(flag=1,start=(int)temp,end=s
11、tart+n;startend;start+) printf(“%d“,start); printf(“/n“); if(flag=0) printf(“没有符合条件的个数/n“); return 0; 程序输出结果： 请输入被分解的数：10 请输入需要被分解的数字的个数：4 1 2 3 43.数组和链表的区别是什么 （分数：3.00）_正确答案：()解析：数组与链表是两种不同的数据存储方式。链表的特性是在中间任意位置添加元素、删除元素都非常地快，不需要移动其他的元素。通常对于单链表而言，链表中每一个元素都要保存一个指向下一个元素的指针；而对于双链表，每个元素既要保存一个指向下一个元素的指针，
12、还要保存一个指向上一个元素的指针；循环链表则在最后一个元素中保存一个指向第一个元素的指针。 数组是一组具有相同类型和名称的变量的集合，这些变量称为数组的元素，每个数组元素都有一个编号，这个编号称为数组的下标，可以通过下标来区别并访问这些元素，数组元素的个数也称为数组的长度。 具体而言，数组和链表的区别主要表现在以下几个方面： 1)逻辑结构。数组必须事先定义固定的长度(元素个数)，不能适应数据动态地增减的情况，即在使用数组之前，就必须对数组的大小进行确定。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。数组中插入、删除数据项时，需要移动其他数据项。而链表采用动态分配内存的形
13、式实现，可以适应数据动态地增减的情况，需要时可以用 new/malloc 分配内存空间，不需要时用 delete/free 将已分配的空间释放，不会造成内存空间浪费，且可以方便地插入、删除数据项。 2)内存结构。(静态)数组从栈中分配空间，对于程序员方便快速，但是自由度小。链表从堆中分配空间，自由度大，但是申请管理比较麻烦。 3)数组中的数据在内存中是顺序存储的，而链表是随机存储的。数组的随机访问效率很高，可以直接定位，但插入、删除操作的效率比较低。链表在插入、删除操作上相对数组有很高的效率，而如果要访问链表中的某个元素，那就得从表头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问效率比
14、数组低。 4)链表不存在越界问题，数组有越界问题。数组便于查询，链表便于插入删除，数组节省空间但是长度固定，链表虽然变长但是占了更多的存储空间。 所以，由于数组存储效率高、存储速度快的优点，如果需要频繁访问数据，很少插入删除操作，则使用数组；反之，如果频繁插入删除，则应使用链表。两者各有用处。4.何时选择顺序表、何时选择链表作为线性表的存储结构为宜 （分数：3.00）_正确答案：()解析：顺序表按照顺序存储，即数据元素存放在一个连续的存储空间之中，实现顺序存取或(按下标)直接存取。链表按照链接存储，即存储空间一般在程序的运行过程中动态分配与释放，且只要存储器中还有空间，就不会产生存储溢出的问题
15、。 顺序表与链表各有短长，在实际应用中，应根据具体问题的要求和性质来选择使用哪一种存储结构，通常有以下几方面的考虑： 1)空间。顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。顺序表的存储密度比链表大，当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2)时间。顺序表是随机存取结构，若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表
16、的首尾两端，则采用尾指针表示的单循环链表为宜。 所以，不能笼统地说哪种实现更好，必须根据实际问题的具体需要，并对各个方面的优缺点进行综合评估，才能最终选择一种比较适合的实现方法。5.如何使用链表头 （分数：3.00）_正确答案：()解析：在回答这个问题前，首先弄清楚一个概念，什么是结点?简单地说，结点表示的就是数据域与指针域的和，数据域存储数据元素的信息，指针域指示直接后继存储位置，所以结点表示数据元素或数据元素的映像关系。 单链表的开始结点之前附设一个类型相同的结点，称之为头结点，头结点的数据域可以不存储任何信息(也可以存放如线性表的长度等附加信息)，头结点的指针域存储指向开始结点的指针(即
17、第一个元素结点的存储位置)。如图所示为带头结点的单链表。 图 1 带头结点的单链表头结点的作用主要有以下两点： 1)对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。 2)对带头结点的链表，表头指针是指向首结点的非空指针，因此空表与非空表的处理是一样的。 在实现运算时，需要动态产生出其头结点，并将其后继指针置为空。 void initial_List(node *L) L=(node*)malloc(sizeof(node); L-
18、next=NULL; 需要注意的是，开始结点、头指针、头结点并不是一个概念，它们是有区别的。开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点，而链表的头指针是指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。图 2 所示链表的头指针为 head，则称该链表为链表 head，在定义链表变量时可以这样声明：node *head，而头结点是人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，无论链表是否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后
19、)。6.如何实现单链表的插入、删除操作 （分数：3.00）_正确答案：()解析：插入运算是将值为 x 的新结点插入到单链表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间。具体算法如下： 1)找到 ai-1 存储位置 p。 2)生成一个数据域为 x 的新结点*s。 3)令结点*p 的指针域指向新结点 s。 4)新结点 s 的指针域指向结点 ai。 图 3 所示为单链表插入结点示意图。 图 3 单链表插入结点示意图单链表插入结点具体算法实现如下： Status InsertList(LinkList head,DataTypex,int i) ListNode *p; p=head;
20、 int j=1; while(p +j; if(!p)ji) printf(“Position Error“); retum ERROR; s=(ListNode*)malloc(sizeof(ListNode); s-data=x; s-next=p-next; P-next=s; return OK; 单链表插入算法的时间主要耗费在查找操作 GetNode，即获得结点上，故单链表插入操作的时间复杂度为O(n)。 单链表的删除操作是将单链表的第 i 个结点删去。其具体步骤如下： 1)找到 ai-1 的存储位置 P(因为在单链表中结点 ai 的存储地址是在其直接前趋结点 ai-1 的指针域
21、next中)。 2)令 pnext 指向 ai 的直接后继结点(即把 ai 从链上摘下)ai+1。 3)释放结点 ai 的空间，将其归还给“存储池”。 图 4 所示为单链表删除结点示意图。 7.如何找出单链表中的倒数第 k 个元素 （分数：3.00）_正确答案：()解析：为了找出单链表中的倒数第 k 个元素，最容易想到的方法是首先遍历一遍单链表，求出整个单链表的长度 n，然后将倒数第 k 个，转换为正数第 n-k 个，接下去遍历一次就可以得到结果。但是该算法需要对链表进行两次遍历，第一次遍历用于求解单链表的长度，第二次遍历用于查找正数第 n-k 个元素。 于是想到了第二种方法，如果沿从头至尾的
22、方向从链表中的某个元素开始，遍历 k 个元素后刚好达到链表尾，那么该元素就是要找的倒数第 k 个元素。根据这一性质，可以设计如下算法：从头结点开始，依次对链表的每一个结点元素进行这样的测试，遍历 k 个元素，查看是否到达链表尾，直到找到那个倒数第 k 个元素为止。此种方法将对同一批元素进行反复多次的遍历，对于链表中的大部分元素而言，都要遍历 k 个元素，如果链表长度为 n，该算法时问复杂度为 O(kn)级，效率太低。 存在另外一种更高效的方式，只需要一次遍历即可查找到倒数第 k 个元素。由于单链表只能从头到尾依次访问链表的各个结点，所以如果要找链表的倒数第 k 个元素，也只能从头到尾进行遍历查
23、找。在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移 k-1 步，然后两个指针同时往前移动。循环直到先行的指针值为 NuLL 时，另一个指针所指的位置就是所要找的位置。程序代码如下： templateclass T struct ListNode T data; ListNode* next; ; templateclass T ListN0deT* FindElem(ListNodeT *head,int k) ListNodeT *ptr1, *ptr2; ptr1=ptr2=head; for(int i=0;ik;+i)前移 k 步 ptr1=ptr1-next; whil
24、e(ptr1!=NULL)循环检测 ptr1=ptr1-next; ptr2=ptr2-next; return ptr2; 8.如何实现单链表反转 （分数：3.00）_正确答案：()解析：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下： struct ListNode int m_nKey; ListNode* m_pNext; 为了正确地反转一个链表，需要调整指针的指向，而与指针操作相关代码总是容易出错的。先举个例子看一下具体的反转过程。例如，1、m、n 是 3 个相邻的结点，假设经过若干步操作，已经把结点 1 之前的指针调整完毕，这些结点的 m pNext
25、指针都指向前面一个结点。现在遍历到结点 m，当然需要调整结点的m_pNext 指针，让它指向结点 1，但需要注意的是，一旦调整了指针的指向，链表就断开了，因为已经没有指针指向结点 n，没有办法再遍历到结点 n 了，因此为了避免链表断开，需要在调整 m 的 m pNext 之前要把 n 保存下来。接下来试着找到反转后链表的头结点，不难分析出反转后链表的头结点是原始链表的尾结点，即 m pNext 为空指针的结点。 具体的实现过程如下： ListNode* ReverseIteratively(ListNode* pHead) ListNode* pReversedHead=NULL; ListN
26、ode* pNode=pHead; ListNode* pPrev=NULL; while(pNode!=NULL) ListNode* pNext=pNode-m_pNext; if(pNext=NULL) pReversedHead=pNode; pNode-m_pNext=pPrev; pPrev=pNode; pNode=pNext; return pReversedHead; 如果本题简化为逆序输出单链表元素，那么递归将是最简单的方法。在递归函数之后输出当前元素，这样能确保输出第 n 个结点的元素语句永远在第 n+1 个递归函数之后执行，也就是说第 n 个元素永远在第 n+1个元素之
27、后输出，最终先输出最后一个元素，然后是倒数第 2 个、倒数第 3 个，直到输出第一个元素位置。具体实现过程如下： void PrintReverseLink(ListNode* head) if(head-Next != null) PrintReverseLink(head-m_pNext); printf(“%d/n“,head-m_Next-m_nKey); 本题不是要求逆序输出，而是需要把单链表逆序，所以在使用递归思想的时候，还需要处理递归后的逻辑问题。具体而言，是在反转当前结点之前先调用递归函数反转后续结点，不过该方法存在一个问题，就是反转后的最后一个结点会形成一个环，所以必须将函数
28、返回的结点的 m pNext 域设置为 NULL，同时考虑到链表反转时需要改变 head 指针，所以在进行参数传递时，需要传递引用。 具体的实现过程如下： ListNode* Reverse(ListNode* p,ListNode* return p else ListNode* temp=Reverse(p-m_pNext,head); temp-m_pNext=p; return temp; 需要注意的是，当单链表有环时，就会无法反转，因为如果单链表有环，则存在两个结点指向同一结点的情况。如果反转就变成一个结点指向两个了，而这对于单链表是不可能的。9.如何从尾到头输出单链表 （分数：3.
29、00）_正确答案：()解析：struct ListNode int m_nKey; ListNode *m_pNext; ; 从头到尾输出单链表比较简单，于是很自然地想把链表中链接结点的指针反转过来，改变链表的方向，然后就可以从尾到头输出了，但该方法需要额外的操作，是否还有更好的方法呢?答案是肯定的。 接下来的想法是从头到尾遍历链表，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。该方法虽然没有只需要遍历一遍链表，但是需要维护一个额外的栈空间，实现起来会比较麻烦。 是否还能有更高效的方法?于是我们想到了第三种方法，既
30、然想到了栈来实现这个函数，而递归本质上就是一个栈结构，于是很自然地又想到了用递归来实现。要实现反过来输出链表，每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。 具体实现如下： void PrintListReversely(ListNode* pListHead) if(pListHead!=NULL) PrintListReversely(pListHead-m_pNext); printf(“%d“,pListHead-m_nKey); 该题还有两个常见的变体： 1)从尾到头输出一个字符串。 2)定义一个函数求字符串的长度，要求该函数体内不能
31、声明任何变量。 对于这两个变体的解答，都可以参考本题的实现方式，在此就不再赘述了。10.如何寻找单链表的中间结点 （分数：3.00）_正确答案：()解析：最容易想到的思路是首先求解单链表的长度 length，然后遍历 length/2 的距离即可查找到单链表的中间结点，但是此种方法需要遍历两次链表，即第一次遍历求解单链表的长度，第二次遍历根据索引获取中间结点。 如果是双向链表，可以首尾并行，利用两个指针一个从头到尾，一个从尾到头，当两个指针相遇的时候就找到中间元素。以此思想为基础，如果是单链表也可以采用双指针的方式来实现中间结点的快速查找。 第一步，有两个指针同时从头开始遍历。第二步，一个快指
32、针一次走两步，一个慢指针一次走一步。第三步，快指针先到链表尾部，而慢指针则恰好到达链表中部(快指针到链表尾部，当链表长度为奇数时，慢指针指向的即是链表中间指针；当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点)。 具体实现如下： node* SearchMid(node* head) node* temp=head; node* mid=head; while(head!=NULL temp=temp-next; mid=temp; return mid; 11.如何进行单链表排序 （分数：3.00）_正确答案：()解析：最容易想到的排序算法是冒泡排序法，所以
33、首先用冒泡排序法进行单链表的排序。程序示例如下： #includestdio.h #includestdlib.h typedef struct node int data; struct node *next; linklist; linklist *head=NULL; linklist* CreateList(int* arr,int len) int data; linklist *pCurrent,*rear; head=(linklist*)malloc(sizeof(linklist); rear=head; int count=0; while(countlen) pCurre
34、nt=(linklist*)malloc(sizeof(linklist); pCurrent-data=arrcount; rear-next=pCurrent; rear=pCurrent; count+; rear-next=NULL; return head; void ShowList(linklist *p) while(p) printf(“%d“,p-data); p=p-next; printf(“/n“); void BubbleSortList(linklist *p)链表冒泡顺序 linklist *_temp=p-next; linklist *_node=p-nex
35、t; int temp; for(;_temp-next;_temp=_temp-next) for(_node=p-next;_node-next;_node=_node-next) if(node-data_node-next-data) temp=_node-data; node-data=_node-next-data; _node-next-data=temp; int main() int array=3,4,5,1,2,-1,7; CreateList(array,sizeof(array)/sizeof(array0); BubbleSortList(head); ShowLi
36、st(head-next); return 0; 程序输出结果： -1 1 2 3 4 5 7 在各种排序算法中，冒泡排序并非最高效的。对链表这一特定数据结构而言，最好使用归并排序算法。而堆排序、快速排序这些在数组排序时性能非常好的算法，用在只能“顺序访问”的链表中却不尽如人意，但是归并排序却可以，它不仅保持了 O(nlogn)的时间复杂度，而且它的空间复杂度也从 O(n)降到了 O(1)，除此之外，归并排序是分治法的实现。具体实现过程如下： #includeiostream #define MAXSIZE 1024 #define LENGTH 8 using namespace std;
37、typedef struct int rMAXSIZE+1; int length; SqList; void Merge(SqList SR,SqList for(j=m+1,k=i;i=m+k) if(SR.ri=SR.rj) TR.rk=SR.ri+; else TR.rk=SR.rj+; while(i=m) TR.rk+=SR.ri+; while(j=n) TR.rk+=SR.rj+; void MSort(SqList SR,SqList SqList TR2; if(s=t) TR1.rs=SR.rt; else m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR, TR2,m+1,t); Merge(TR2,TR1,s,m,t); void MergeSort(SqList int main() int i; SqList L=0,49,38,6
