9月1日,腾讯为2017年校招提供了模拟笔试,地址
题目涉及到了内容:

  1. 数据结构
    • 图:最小生支撑树
    • 排序:排序的算法时间复杂度和稳定性
  2. 编程语言
    • C++继承和多态
    • Java语言中Integer的equals和"=="的区别点
  3. 数据库
    • SQL语句查询执行顺序
  4. 操作系统
    • 线程相关知识
    • 栈和堆区别 总体来讲,考察了计算机基础知识的方方面面,像我这种非科班出身的差不多go die了。

0 最小生支撑树

对于一个加权无向图(weighted undirected graph),最小生支撑树(minimal spanning trees)就是选取权重和最小的边组成最小的无向无环图。针对最MST主要有两种算法:Prim Algorithm 和Kruskal Algorithm。
+ Prim

算法的主要针对图的节点算法而言,提供加入支撑树节点集合Set和尚未支撑树的节点补集cutSet,依次从两个集合中选取两点之间边权重最小的边,将补集中该点加入集合Set,重复进行,直至补集cutSet为空。
  • Kruskal

    算法主要从边来考虑,首先将所有的边排序,从其中依次选择权重最小的边依次加入到最小支撑树中,如果该边的两个顶点不属于同一集合,则加入;否则丢弃掉改边,选择下一条权重较小的边。

1 Sorting Algorithm

Algorithm Time cost Stability PostScript
BubbleSort $n^{2}$ Yes a isSorted flag
InsertSort $n^{2}$ Yes intput sensitive
HeapSort $nlogn$ No heap data structure
SelectionSort $n^{2}$ No nothing
MergeSort $nlogn$ Yes divide and conquer
QuickSort $nlogn$ No divide and conquer

2 Stack and Heap

编程语言书籍中经常解释值类型被创建在栈上,引用类型被创建在堆上,但是并没有本质上解释这堆和栈是什么。我仅有高级语言编程经验,没有看过对此更清晰的解释。我的意思是我理解什么是栈,但是它们到底是什么,在哪儿呢(站在实际的计算机物理内存的角度上看)?

  1. 在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?
  2. 它们的作用范围是什么?
  3. 它们的大小由什么决定?
  4. 哪个更快?
  • 答案1

栈是为执行线程留出的内存空间。当函数被调用的时候,栈顶为局部变量和一些 bookkeeping 数据预留块。当函数执行完毕,块就没有用了,可能在下次的函数调用的时候再被使用。栈通常用后进先出(LIFO)的方式预留空间;因此最近的保留块(reserved block)通常最先被释放。这么做可以使跟踪堆栈变的简单;从栈中释放块(free block)只不过是指针的偏移而已。堆(heap)是为动态分配预留的内存空间。和栈不一样,从堆上分配和重新分配块没有固定模式;你可以在任何时候分配和释放它。这样使得跟踪哪部分堆已经被分配和被释放变的异常复杂;有许多定制的堆分配策略用来为不同的使用模式下调整堆的性能。每一个线程都有一个栈,但是每一个应用程序通常都只有一个堆(尽管为不同类型分配内存使用多个堆的情况也是的)。直接回答你的问题: 1. 当线程创建的时候,操作系统(OS)为每一个系统级(system-level)的线程分配栈。通常情况下,操作系统通过调用语言的运行时(runtime)去为应用程序分配堆。 2. 栈附属于线程,因此当线程结束时栈被回收。堆通常通过运行时在应用程序启动时被分配,当应用程序(进程)退出时被回收。 3. 当线程被创建的时候,设置栈的大小。在应用程序启动的时候,设置堆的大小,但是可以在需要的时候扩展(分配器向操作系统申请更多的内存)。 4. 栈比堆要快,因为它存取模式使它可以轻松的分配和重新分配内存(指针/整型只是进行简单的递增或者递减运算),然而堆在分配和释放的时候有更多的复杂的 bookkeeping 参与。另外,在栈上的每个字节频繁的被复用也就意味着它可能映射到处理器缓存中,所以很快(译者注:局部性原理)

  • 答案2

Stack:

  1. 和堆一样存储在计算机 RAM 中。
  2. 在栈上创建变量的时候会扩展,并且会自动回收。
  3. 相比堆而言在栈上分配要快的多。
  4. 用数据结构中的栈实现。
  5. 存储局部数据,返回地址,用做参数传递。
  6. 当用栈过多时可导致栈溢出(无穷次(大量的)的递归调用,或者大量的内存分配)。
  7. 在栈上的数据可以直接访问(不是非要使用指针访问)。
  8. 如果你在编译之前精确的知道你需要分配数据的大小并且不是太大的时候,可以使用栈。
  9. 当你程序启动时决定栈的容量上限。

Heap:

  1. 和栈一样存储在计算机RAM。
  2. 在堆上的变量必须要手动释放,不存在作用域的问题。数据可用 delete, delete[] 或者 free 来释放。
  3. 相比在栈上分配内存要慢。
  4. 通过程序按需分配。
  5. 大量的分配和释放可造成内存碎片。
  6. 在 C++ 中,在堆上创建数的据使用指针访问,用 new 或者 malloc 分配内存。
  7. 如果申请的缓冲区过大的话,可能申请失败。
  8. 在运行期间你不知道会需要多大的数据或者你需要分配大量的内存的时候,建议你使用堆。
  9. 可能造成内存泄露。
  • 答案3

堆和栈是两种内存分配的两个统称。可能有很多种不同的实现方式,但是实现要符合几个基本的概念:
1.对栈而言,栈中的新加数据项放在其他数据的顶部,移除时你也只能移除最顶部的数据(不能越位获取)
在通常情况下由操作系统(OS)和语言的运行时(runtime)控制吗?
如前所述,堆和栈是一个统称,可以有很多的实现方式。计算机程序通常有一个栈叫做调用栈,用来存储当前函数调用相关的信息(比如:主调函数的地址,局部变量),因为函数调用之后需要返回给主调函数。栈通过扩展和收缩来承载信息。实际上,程序不是由运行时来控制的,它由编程语言、操作系统甚至是系统架构来决定。
堆是在任何内存中动态和随机分配的(内存的)统称;也就是无序的。内存通常由操作系统分配,通过应用程序调用 API 接口去实现分配。在管理动态分配内存上会有一些额外的开销,不过这由操作系统来处理。
它们的作用范围是什么?
调用栈是一个低层次的概念,就程序而言,它和“作用范围”没什么关系。如果你反汇编一些代码,你就会看到指针引用堆栈部分。就高级语言而言,语言有它自己的范围规则。一旦函数返回,函数中的局部变量会直接直接释放。你的编程语言就是依据这个工作的。
在堆中,也很难去定义。作用范围是由操作系统限定的,但是你的编程语言可能增加它自己的一些规则,去限定堆在应用程序中的范围。体系架构和操作系统是使用虚拟地址的,然后由处理器翻译到实际的物理地址中,还有页面错误等等。它们记录那个页面属于那个应用程序。不过你不用关心这些,因为你仅仅在你的编程语言中分配和释放内存,和一些错误检查(出现分配失败和释放失败的原因)。
它们的大小由什么决定?
依旧,依赖于语言,编译器,操作系统和架构。栈通常提前分配好了,因为栈必须是连续的内存块。语言的编译器或者操作系统决定它的大小。不要在栈上存储大块数据,这样可以保证有足够的空间不会溢出,除非出现了无限递归的情况(额,栈溢出了)或者其它不常见了编程决议。
堆是任何可以动态分配的内存的统称。这要看你怎么看待它了,它的大小是变动的。在现代处理器中和操作系统的工作方式是高度抽象的,因此你在正常情况下不需要担心它实际的大小,除非你必须要使用你还没有分配的内存或者已经释放了的内存。
哪个更快一些?
栈更快因为所有的空闲内存都是连续的,因此不需要对空闲内存块通过列表来维护。只是一个简单的指向当前栈顶的指针。编译器通常用一个专门的、快速的寄存器来实现。更重要的一点事是,随后的栈上操作通常集中在一个内存块的附近,这样的话有利于处理器的高速访问(译者注:局部性原理)。

4 Greedy snake

给定一个数字n,构建一个$n \times n$ 的矩阵,将数字$1 \sim n^{2}$ 从矩阵外圈向内圈填写,输出按行扫描矩阵的字符串。
解决办法:提供了left,right,top,bottom 四个指针,按照上,右,下,左依次填写矩阵。

class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine());
            int[,] mat = new int[n, n];
            int left = 0;
            int right = n - 1;
            int top = 0;
            int bottom = n - 1;
            int counter = 0;
            while (left <= right || top <= bottom)
            {
                int cursor;
                //top
                for (cursor = left; cursor <= right; cursor++)
                {
                    mat[top, cursor] = ++counter;
                }
                top++;
                //right
                for (cursor = top; cursor <= bottom; cursor++)
                {
                    mat[cursor, right] = ++counter;
                }
                right--;
                //bottom
                for (cursor = right; cursor >= left; cursor--)
                {
                    mat[bottom, cursor] = ++counter;
                }
                bottom--;
                //left
                for (cursor = bottom; cursor >= top; cursor--)
                {
                    mat[cursor, left] = ++counter;
                }
                left++;
            }
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    Console.Write(mat[i, j]);
        }
    }
Comments
Write a Comment