资源描述：
《算法面试题总结.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、.1算法面试题总结1.把二元查找树转变成排序的双向链表 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10 / 6 14 //4 81216 转换成双向链表4=6=8=10=12=14=16。解：首先我们定义的二元查找树节点的数据结构如下： typedefstructtree{ intdata;//valueofnode structtree*left;//leftchildofnode structtree*right;//rightchildofnode}*ptree; ptreef(ptree
2、root,intsign)//sign==0返回链头，sign==1返回链尾{//main函数中调用f(root,0);ptreep=root;if(p->left)//如果左子树非空{p->left=f(p->left,1);//第4个参数为，表明f函数返回root左子树中根的链尾p->left->right=p;//双链表中left记录前驱，right记录后继}if(p->right){p->right=f(p->right,0);p->right->left=p;}if(sign==0)while(p->left)p=p->left;//顺着left找到双链表首元素
3、elsewhile(p->right)p=p->right;//顺着right找到双链表尾元素returnp;}2.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 ..3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。解
4、：设数组元素为a[1~n]，f(i)表示以a[i]为尾元素的最大子段和，则有f(1)=a[1],f(i)=max{f(i-1)+a[i],a[i]}(i>1)动态规划求f(i),b[i]保存f(i)的值。Intf(inti){intj,max;max=b[1]=a[1];for(j=2;j<=I;j++){b[i]=a[i-1]>0?a[i-1]+a[i]:a[i];if(b[i]>max)max=b[i];}returnmax;//返回b[1]~b[i]中最大值}4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所
5、经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树 10 / 5 12 / 4 7则打印出两条路径：10,12和10,5,7。解：首先我们定义的二元查找树节点的数据结构如下： typedefstructtree{ intdata;//valueofnode structtree*left;//leftchildofnode structtree*right;//rightchildofnode}*ptree;ptreeX[MAX];//X记住路径设树的根为root;指定和为S，以下为回溯算法void
6、f(intk,ptreeroot,intsum)//sum为已访问结点元素之和{intj,ss=sum+root->data;X[k]=root;if(ss==S)..{printf(“”);for(j=1;j<=k;j++)printf(“%d”,X[j]->data);}else{if(root->left&&ssleft,ss);if(root->right&&ssright,ss);}}5.查找最小的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最
7、小的4个数字为1，2，3和4。解：1：可以借用找第k小元素的办法，当找到第k小元素时，这一元素和它左边的元素构成最小的k个元素。2：可以考虑用小堆排序的办法，每一次小堆调整得到最小的元素，进行k次小堆调整即可得到k个最小元素的有序序列。第6题腾讯面试题： 给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下： 【0，1，2，3，4，5，6，7，8，9】举一个例子， 数值:0,1,2,3,4,5,6,7,8,9 分配:6,2,1,0,0,0,1,0
