在一棵(排序？)二叉树中搜索指定值,数据结构定义为(

《在一棵(排序？)二叉树中搜索指定值,数据结构定义为(》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、在一棵(排序？)二叉树中搜索指定值,数据结构定义为(我们要像海绵一样，不断吸收有用有益的知识。在一棵（排序？）二叉树中搜索指定值，数据结构定义为（唉唉，数据结构的具体名字都不记得了，mygod）：structNode{Node*lnext;Node*rnext;intvalue;};函数定义为（情况同上，啥都记不清了）：Node*search(Node*root,intvalue){}实现这个search函数。用递归，经典的树的遍历，pass先。第二个的题目：计算Tribonaci队列（嗯，九成九记错了那个单词......），规则是T(n)=T(n-1)+T(n-2)+T(

2、n-3)，其中T(0)=T(1)=1，T(2)=2。函数定义：intTribonaci(intn){}备注，不考虑证整数溢出，尽可能优化算法。　　这一题我一看就知道要考什么，很显然的递归定义，但也是很显然的，这里所谓的优化是指不要重复计算。　　简单的说，在计算T(n)的时候要用到T(n-1)、T(n-2)和T(n-3)的结果，在计算T(n-1)的时候也要用到T(n-2)和T(n-3)的结果，所以在各项计算的时候必须把以前计算的结果记录下来，去掉重复计算。这里用到的一点小技巧就是要新写一个函数用来做这种事情，嗯，看看我写的代码吧！/**GetthevalueofT(n-1),

3、andretrievetheresultofT(n-2)andT(n-3).@param[in]nTheninT(n).@param[out]midValueofT(n-2).@param[out]rightValueofT(n-3).@returnValueofT(n-1).*/intfind_trib(intn,int&mid,int&right){if(3==n){mid=1;right=1;return2;}else{inttemp;mid=find_trib(n-1,right,temp);returnmid+right+temp;}}/**Findvalueof

4、T(n).@param[in]TheninT(n).@returnValueofT(n).@noteT(n)=T(n-1)+T(n-2)+T(n-3)(n>2)T(0)=T(1)=1,T(2)=2.*/inttribonaci(intn){if(n<0){//Undefinedfeature.return0;}if(0==n

5、

6、1==n){return1;}if(2==n){return2;}intmid,right;intleft=find_trib(n,mid,right);returnleft+mid+right;}　　啊啊，对了，答卷的时候我可没心情写注释.....

7、.刚才到VC.Net2003上测试了一下，貌似没有啥问题。唉，看来我多少还是懂一点算法的......　　第三个的题目：　　在一个无向图中，寻找是否有一条距离为K的路径，描述算法即可，不用实现，分析算法的时间和空间复杂度，尽量优化算法。　　OK，这个就是传说中的软肋了..................我也就不把自己的答案写出来了（丢人啊），虽然后来仔细想想，我那个挫挫的方法也能够用......只是效率......　　这是第二次笔试，作个记录，以备日后参考，题目另行记录。1、两个二进制数的异或结果2、递归函数最终会结束，那么这个函数一定（不定项选择）：　　1.使用了局部变量　

8、　2.有一个分支不调用自身　　3.使用了全局变量或者使用了一个或多个参数3、以下函数的结果？intcal(intx){　　　　if(x==0)return0;　　　　else　　　　　　returnx+cal(x-1);}4、以下程序的结果？voidfoo(int*a,int*b){　　　　*a=*a+*b;　　　　*b=*a-*b;　　　　*a=*a-*b;}voidmain(){　　　　inta=1,b=2,c=3;我们要像海绵一样，不断吸收有用有益的知识。　　　　foo(&a,&b);　　　　foo(&b,&c);　　　　foo(&c,&a);　　　　printf("

9、%d,%d,%d",a,b,c);}5、下面哪项不是链表优于数组的特点？　　1.方便删除2.方便插入3.长度可变4.存储空间小6、T(n)=25T(n/5)+n^2的时间复杂度？7、n个顶点，m条边的全连通图，至少去掉几条边才能构成一棵树？8、正则表达式(01

10、10

11、1001

12、0110)*与下列哪个表达式一样？　　1.(0

13、1)*2.(01

14、01)*3.(01

15、10)*4.(11

16、01)*5.(01

17、1)*9、如何减少换页错误？　　1.进程倾向于占用CPU　　2.访问局部性（localityofreference）