2014暴风影音笔试题

       1.溢出与越界的区别

　　2.指出如下代码中的错误

int main()

　　{

　　char a;

　　char* p = &a;

　　strcpy(p， "Hello");

　　printf("p is %s"， p);

　　return 0;

　　}

      3.指出如下代码的输出结果

void fun(char str[])

　　{

　　void* p = malloc(100);

　　printf("%d\n%d"， sizeof(str)， sizeof(p));

　　}

　　int main()

　　{

　　char str[100] = "Hello";

　　fun(str);

　　return 0;

　　}

　　4.利用TCP发送数据的时候，调用send发送5次，每次发送100字节，问接收方调用recv最少几次，最多几次?

　　5.自定义实现字符串转为整数的算法，例如把“123456”转成整数123456.(输入中可能存在符号，和数字)

　　6.给出一棵二叉树的前序和中序遍历，输出后续遍历的结果，假设二叉树中存储的均是ASCII码。如前序：ABDHECFG，中序：HDBEAFCG，则输出后序为：HDECFGCA。

　　7.给出了一个n*n的矩形，编程求从左上角到右下角的路径数(n > =2)，限制只能向右或向下移动，不能回退。例如当n=2时，有6条路径。

　参考答案：

　　1.溢出主要指的是超出了自身的范围，常见的有整数溢出和缓冲区溢出;而越界则指的是操作数组的下标超出了数组应有的长度范围。

　　2.由于p指向的只是一个字节的地址，strcpy拷贝溢出。

　　3.数组作为函数参数时会退化为指针，所以sizeof(str)为4;而p本身就是一个指针，所以sizeof(p)为4。

　　4.TCP的基本工作流程：send时会先发送到发送缓冲区，接收时会从接收缓冲区取数据。由于缓冲区的大小不定，按题意，最少recv接收1次，最多500次。

　　5.可以参见c中的stoi函数实现，主要是要考虑各种特殊情况，例如符号和溢出，下面是示例实现代码。

　//返回结果的有效标志

　　enum Status {VALID，IN_VALID};

　　int gStatus = VALID;

　　int strToInt(const char* str)

　　{

　　long long result = 0;//保存结果

　　gStatus = IN_VALID; //每次调用时都初始化为IN_VALID

　　if(str != NULL)

　　{

　　const char* digit = str;

　　bool minus = false;

　　if(*digit == '+')

　　digit++;

　　else if(*digit == '-')

　　{

　　digit++;

　　minus = true;

　　}

　　while(*digit != '\0')

　　{

　　if(*digit >= '0' && *digit <= '9')

　　{

　　result = result * 10 + (*digit -'0');

　　//溢出

　　if(result > std::numeric_limits::max())

　　{

　　result = 0;

　　break;

　　}

　　digit++;

　　}

　　//非法输入

　　else

　　{

　　result = 0;

　　break;

　　}

　　}

　　if(*digit == '\0')

　　{

　　gStatus = VALID;

　　if(minus)

　　result = 0 - result;

　　}

　　}

　　return static_cast(result);

　　}

　　6.思路：先利用前序和中序构建出二叉树，然后后序遍历输出结果

/**

　　*返回二叉树的根节点

　　*preOrder:前序遍历序列

　　*inOrder:中序遍历序列

　　*len:节点数目

　　*/

　　Node* getBinaryTree(char* preOrder， char* inOrder， int len)

　　{

　　if(preOrder == NULL || *preOrder == '\0' || len<=0)

　　return NULL;

　　Node* root = (Node*) malloc(sizeof(Node));

　　if(root == NULL)

　　exit(EXIT_FAILURE);

　　//前序遍历的第一个节点就是根节点

　　root->data = *preOrder;

　　int pos = 0;//找到根节点在中序遍历中的位置，其值也代表了左子树的节点数目

　　while(true)

　　{

　　if(*(inOrder+pos) == root->data)

　　break;

　　pos++;

　　}

　　//通过递归找到左子树和右子树，注意子树的前序中序的下标的计算

　　if(pos == 0)

　　root->lchild = NULL;

　　else

　　root->lchild = getBinaryTree(preOrder+1， inOrder， pos);

　　if(len-pos-1 == 0)

　　root->rchild = NULL;

　　else

　　root->rchild = getBinaryTree(preOrder+pos+1， inOrder+pos+1，len-pos-1);

　　return root;

　　}

　　/**

　　*后续遍历二叉树

　　*

　　*/

　　void postOrder(Node* root)

　　{

　　if(root == NULL)

　　return;

　　postOrder(root->lchild);

　　postOrder(root->rchild);

　　printf("%c"， root->data);

　　}

　　/**

　　*根据前序遍历和中序遍历输出后续遍历

　　*

　　*/

　　void printPostOrderViaPreOrderAndInorder(char* preOrder， char* inOrder)

　　{

　　Node* root = getBinaryTree(preOrder， inOrder， strlen(preOrder));

　　postOrder(root);

　　}

　　7.一是利用数学知识，从左上角到右下角总共要走2n步，其中横向要走n步，所以总共就是C2n~n。

　　二是利用递归实现

/**

　　*返回总路径数

　　*参数m:表示矩形的横向格子数

　　*参数n:表示矩形的纵向格子数

　　*/

　　int getTotalPath(int m， int n)

　　{

　　//如果横向格子数为1，则类似“日”字，此时路径数为纵向格子数加1

　　if(m == 1)

　　return n + 1;

　　//如果纵向格子数为1，此时路径数为横向格子数加1

　　if(n == 1)

　　return m + 1;

　　//由于从当前点出发，只能向右或向下移动：

　　//向右移动，则接下来就是getTotalPath(m-1， n)的情形

　　//向下移动，则接下来就是getTotalPath(m， n-1)的情形

　　return getTotalPath(m-1， n) + getTotalPath(m， n-1);

　　}