2012百度校招试题（移动终端研发 深圳）
共四道道
1. 简述线性表 二叉平衡树 哈希表存储数据时的优劣
2.简答：一个十进制数m转化N进制，N属于[1, 16]。
3.读程序（程序我只记得个大概）
#include<iostream>
using namespace std;
int var_1=0;
char *pvar_1=NULL;
int main()
{
int var_2;
char str[]="abe";
char *p="efs";
int *kk=vector<int >;
kk=new *int
p =(char *)malloc(20);
if(p==NULL)
printf("dfdf");
if(kk==NULL)
pritnf("ddfdsfds");
if(kk!=NULL)
free (kk)
if(p!=NULL)
delete p;
}
1.c程序存储分类；
2.var_1 var_2 str p kk "efs" "abe"分别存储在什么地方
3.p分配失败程序会怎样
4. free (kk) delete p;有什么不妥，两种释放方式异同点？
四。系统设计题（40分）
对已排好序的数组A，一般来说可用二分查找 可以很快找到。
现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9},
试在这样的数组中找一元素x，看看是否存在。
请写出你的算法，必要时可写伪代码，并分析其空间 时间复杂度。
[解决办法]
你第四题答错了。所谓的循环递增是说分段符合递增，并未说只有两段，可能存在N段，你答题的思路是基于那个例子，只有两段递增区间，这是片面的。
应该是：解题关键是找到递增区间的分隔点，由分隔点进行差别
1、先从中选取一点。判断它左右两点，确认是否为边界点
2、分左边界，中间，右边界三种情况分别处理
3、根据递增和给定X值，在符和条件的区间进行分段查找，重复上速过程
这样才能得到正确的解。呵呵。。。下班了，没时间，有时间可试着写个程序证明一下。
[解决办法]
第一题：
对于优劣势，一方面考虑存储，一方面考虑性能：
线性表：可以用顺序表和链表实现，而且存储结构不一样，性能也不一样，总的来说线性表的优势是结构简单，访问节点比较快，对单节点的操作比较简单；适合于小数据量的存储，并且访问不存在经常变化的需求；
散列表：实现了随机访问，所以性能比较快，但是对于散列函数的设计要求比较高，而且设计需要根据自己的需求进行设计，实现高访问；
二叉平衡树：比较灵活，在空间上可以实现高效压缩存储，但是对于节点的操作比较复杂
第二题：
根据进制之间的转化关系：
首先要定义算法，即求余取模，但是这样做效率不高，除法运算的效率比较低，可以使用一种类似8421编码实现所有算法的转化
第三题：
(1)heap,stack,code segment,data segment,regsiter
(2)
stack: var_1 var_2 str
heap:p kk
data segment:"efs" "abe"
(3)输出：dfdf
(4)delete 只是销毁值，但是空间依然存在
free 释放空间
所以先delete 然后free 这样就比较安全
第四题：
既然二分法排序，而且序列中出现小的数据聚集现象，那就应该先进行归并排序，然后再进行2分法查找
[解决办法]
