面试总结之数据结构

*.队列和栈有什么区别？队列先进先出，栈后进先出*.二分查找算法：1)递归方法实现：intBSearch(elemtypea[],elemtypex,intlow,inthigh)/*在下届为low，上界为high的数组a中折半查找数据元素x*/{intmid;if(lowhigh)return-1;mid=(low+high)/2;if(x==a[mid])returnmid;if(xa[mid])return(BSearch(a,x,low,mid-1));elsereturn(BS2)非递归方法实现：intBSearch(elemtypea[],keytypekey,intn){intlow,high,mid;low=0;high=n-1;while(low=high){mid=(low+high)/2;if(a[mid].key==key)returnmid;elseif(a[mid].keykey)low=mid+1;elsehigh=mid-1;}return-1;}*.递归计算如下递归函数的值（斐波拉契）：f(1)=1f(2)=1f(n)=f(n-1)+f(n-2)n2非递归算法:intf(intn){inti,s,s1,s2;s1=1;/*s1用于保存f(n-1)的值*/s2=1;/*s2用于保存f(n-2)的值*/s=1;for(i=3;i=n;i++){s=s1+s2;s2=s1;s1=s;}return(s);}递归算法:Intf(intn){If(n==1||n==2)Rerurn1;ElseRerutnf(n-1)+f(n-2);}*.冒泡排序voidBubbleSort(elemtypex[],intn)//时间复杂度为0(n*n);{inti,j;elemtypetemp;for(i=1;in;i++)for(j=0;jn-i;j++){if(x[j].keyx[j+1].key){temp=x[j];x[j]=x[j+1];x[j+1]=temp;}}}//补充一个改进的冒泡算法:voidBubbleSort(elemtypex[],intn){Inti,j;BOOLexchange;//记录交换标志for(i=1;in;++i)//最多做n-1趟排序{Exchange=false;For(j=n-1;j=i;--j){If(x[j]x[j+1]){x[0]=x[j];X[j]=x[j+1];X[j+1]=x[0];Exchange=true;//发生了交换,设置标志为真.}}if(!Exchange)//为发生替换,提前终止算法return;}}1.链表和数组的区别在哪里？2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？4.请编写能直接实现strstr()函数功能的代码。5.编写反转字符串的程序，要求优化速度、优化空间。6.在链表里如何发现循环链接？7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码,编写出一个从字符串到长整形的函数？）9.给出一个函数来输出一个字符串的所有排列。10.请编写实现malloc()内存分配函数功能一样的代码。11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。12.怎样编写一个程序，把一个有序整数数组放到二叉树中？13.怎样从顶部开始逐层打印二叉树结点数据？请编程。14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？15.深度遍历二叉树。16.二分法查找。intDicFind(int*Array,intCount,intValue){}structNode{Node*Parent;Node*Left,*Right;};voidThrough(Node*Root){}*.现在最快且最通用的排序算法是什么？（A）A.快速排序B.冒泡排序C.选择排序D.外部排序*.下列程序运行时会崩溃，请找出错误并改正，并且说明原因。#includestdio.h#includemalloc.htypedefstruct{TNode*left;TNode*right;intvalue;}TNode;TNode*root=NULL;voidappend(intN);intmain(){append(63);append(45);append(32);append(77);append(96);append(21);append(17);//Again,数字任意给出}voidappend(intN){TNode*NewNode=(TNode*)malloc(sizeof(TNode));NewNode-value=N;if(root==NULL){root=NewNode;return;}else{TNode*temp;temp=root;while((N=temp.value&&temp.left!=NULL)||(Ntemp.value&&temp.right!=NULL)){while(N=temp.value&&temp.left!=NULL)temp=temp.left;while(Ntemp.value&&temp.right!=NULL)temp=temp.right;}if(N=temp.value)temp.left=NewNode;elsetemp.right=NewNode;return;}}*.实现双向链表删除一个节点P，在节点P后插入一个节点，写出这两个函数。试编写3个函数实现（1）建立一个双向链表（2）插入一个节点（3）删除一个节点1．数据的逻辑存储结构（如数组，队列，树等）对于软件开发具有十分重要的影响，试对你所了解的各种存储结构从运行速度、存储效率和适用场合等方面进行简要地分析。2.把一个链表反向填空7.下面哪种排序法对12354最快aquicksortb.bublesortc.mergesort3英文拼写纠错：在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。(1)请描述你解决这个问题的思路；(2)请给出主要的处理流程，算法，以及算法的复杂度；(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。4寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。(1)请描述你解决这个问题的思路；(2)请给出主要的处理流程，算法，以及算法的复杂度。13、折半查找对线形表的要求元素值是否有序，存储结构是顺序的还是链式的4、一个具有767个结点的完全二叉树，其叶子结点个数为（4）。A、383B、384C、385D、3865、对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反应数据之间的逻辑关系，则应该用（5）。A、顺序方式存储B、链接方式存储C、散列方式存储D、以上方式均可23、设rear是指向非空带头结点的循环单链表的尾指针，则删除链表第一个结点的操作可表示为（23）。A、p=rear;rear=rear→next;free(p);B、rear=rear→next;free(p);C、rear=rear→next→next;free(p);D、p=rear→next→next;rear→next=p→nextfree(p);25、设二叉排序树中关键字由1到1000内的整数构成，现要查找关键字为363的结点，下述关键字序列（25）不可能是在二叉排序树上查找到的序列？A、2，252，401，398，330，344，397，363B、924，220，911，244，898，258，362，363C、925，202，911，240，912，245，363D、2，399，387，219，266，382，381，278，36334、一个具有n（n﹥0）个顶点的连同无向图至少有（34）条边。A、n＋1B、nC、n/2D、n－143、shell排序、快速排序、堆排序的稳定性如何（47）；若要尽可能地完成对实数数组的排序，且要求排序是稳定的，则应选（48）；若用插入排序算法对n个记录进行排序，最佳情况下，对关键字进行的比较次数为（49）；对于多关键字而言，（50）是一种方便而又高效的文件组织方式；若用冒泡排序对关键字序列｛19，16，11，8，5，3｝从小到大进行排序，则需要交换的总次数为（51）。供选择的答案：（47）：A、shell排序是稳定的B、快速排序是稳定的C、堆排序是稳定的D、都不稳定（48）：A、快速排序B、堆排序C、归并排序D、基数排序（49）：A、n2-1B、N-1C、n2D、n＋1（50）：A、顺序文件B、索引文件C、散列文件D、倒排文件（51）：A、3B、6C、15D、1245、已知图G＝（V，E），其中V＝｛a,b,a,d,a,e,d,e,e,b,c,b,c,e,c,f,f,e｝,则从该图的顶点a出发的深度优先遍历序列是（56），广度优先遍历序列是（57），其深度优先生成树（或森林）是（58），广度优先生成树（或森林）是（59），该图的一个拓扑序列是（60）。供选择的答案：（56）：A、abdecfB、abdcefC、aebdcfD、adebfc（57）：A、abcedfB、abdcefC、aebcdfD、abdecf（58）：A、aB、abedbedcfcfC、aD、abedbedcfcf（59）：A、aB、abedbedcfcfC、aD、abedbedcfcf（60）：A、abcdefB、aedbefC、adcfebD、acdebf1.假设执行语句S的时间为O(1)，则执行下列程序短的时间为（）for(i=1;i=n;i++)for(j=I;j=n;j++)S;A.O(n)B.O(n2)C.O(n*i)D.O(n+1)2.二位数组A[10…20，5…10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的地址是（）A.1208B.1212C.1368D.13643.设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能得出栈序列是（）A.1，2，3，4，5，6B.2，1，3，4，5，6C.3，4，2，1，5，6D.4，3，2，1，5，64.设有98个已排序列元素，采用二分法查找时，最大比较次数是（）A.49B.15C.20D.75.Hash表示用于数据存储的一种有效的数据结构，Hash表等查找复杂度依赖于Hash值算法的有效性，在最好的情况下，Hash表的查找复杂度为（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10.一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是（）A、EDCBA；B、DECBA；C、DCEAB；D、ABCDE1.假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求：1)通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表2)给定一个SONG_ID，为其添加一个新的URL_ID3)添加一个新的SONG_ID4)给定一个URL_ID，将其置为不可用限制条件：内存占用不超过1G，单个文件大小不超过2