某互联网公司20分钟笔试题

原创
2016/04/25 18:34
阅读数 138

某互联网公司C++ 面试

1 分析C++程序运行内存分布

2 写一个函数,输入n,求斐波那契数列的第N项 0 1 1 2 3 5 ......

3 杨辉三角实现


code部分没有在纸上写出来,知道思路,但是就是不知道如何code,不知道是不是脑子抽筋了!

第一题:

我们先说一下程序的组成,典型的可执行文件分为两部分:

  • 代码段(code),由机器指令组成,该部分是不可改的,编译之后就不在改变,放置在文本段(.text)
  • 数据段(data),它由一下几部分组:
    • 常量(constant),通常放置在只读 read-only的文本段(.text)
    • 静态数据(static data),初始化的放置在数据段(.data);未初始化的放置在(.bss, BSS段的变量只有名称和大小缺没有值)
    • 动态数据(dynamic data),这些数据存储在堆(heap)或栈(stack)

源程序编译后链接到一个以0地址为始地址的线性或者多维虚拟地址空间。而且每一个进程都拥有这样一个空间,每个指令和数据都在这个虚拟地址空间拥有确定的地址,把这个地址称为虚拟地址。将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。典型的虚拟存储器中有类似布局:

  • Text Segment(.text) 代码段
  • Initialized Data Segment(.data) 初始化数据段
  • Uninitialized Data Segment(.bss) 未初始化数据段
  • The Stack 栈
  • The Heap 堆

如下图所示: memory layout

第二题

第二题是C语言基础课本上的例子,可能是面试经历太少,忽略了基础,找到了规律,但是就是不知道如何在纸上codeing出来.........

  • 递归
int fib(int n)
{
	if(n == 0 || n == 1)
		return n;
	return fib(n-1) + fib(n-2)
}
  • 非递归
int fib(int n)
{
  if(n < 2)
  {
  	return n;
  }
  int fib1 = 0;
  int fib2 = 1;
  int fibn = 0'
  int i = 0;
  for(i = 2; i <= n; i++)
  {
  	fibn = fib1 + fib2;
    fib1 = fib2;
    fib2 = fibn;
  }
  return fibn;
}

测试程序

int main(int argc,char **argv)
{
	int n = 6;
	int i = 0;
	for( ; i < n ; i++)
	{
		printf("%d\t", fib(i));
	}
	printf("\n");
	return 0;
}

第三题

#define N 6
int main(int argc,char **argv)
{
	int i,j;
	int a[N][N] = {0};
	for(i = 0; i < N ; i++)
	{
		a[i][0] = 1;
	}
	for(i = 1; i < N ; i++)
	{
		for(j = 1; j <= i; j++)
		{
			a[i][j] = a[i-1][j-1] + a[i-1][j];
		}
	}
	for(i = 0; i < N; i++)
	{
		/*for(j = 0; j < N - i ; j++)
			printf(" ");*/
		for(j = 0; j <= i; j++)
		{
			printf("%3d", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

总结

每一次请假面试,自己内心都是崩溃的。还是自己基础不够牢固!接下来,多看面试题,多看小算法~

展开阅读全文
打赏
1
1 收藏
分享
加载中
更多评论
打赏
0 评论
1 收藏
1
分享
返回顶部
顶部