考研计算机复试面试题总结.docx
《考研计算机复试面试题总结.docx》由会员分享，可在线阅读，更多相关《考研计算机复试面试题总结.docx（46页珍藏版）》请在冰点文库上搜索。
考研计算机复试面试题总结
概念问题
C++/数据结构
1、简述你对“面向对象”和“面向过程”编程思想的认识与思考用就可以了。
面向过程
就是分析出解决问题所需要的步骤，然后用函数把这些步骤一步一步实现，使用的时候一个一个依次调
面向对象是把构成问题事务分解成各个对象，建立对象的目的不是为了完成一个步骤，而是为了描叙某个事物在整个解决问题的步骤中的行为。
例如五子棋，面向过程的设计思路就是首先分析问题的步骤：
1、开始游戏，2、黑子先走，3、绘制画面，4、判断输赢，5、轮到白子，6、绘制画面，7、判断输赢，8、返回步骤2，9、输出最后结果。
把上面每个步骤用分别的函数来实现，问题就解决了。
而面向对象的设计则是从另外的思路来解决问题。
整个五子棋可以分为1、黑白双方，这两方的行为是一模一样的，2、棋盘系统，负责绘制画面，3、规则系统，负责判定诸如犯规、输赢等。
第一类对象（玩家对象）负责接受用户输入，并告知第二类对象（棋盘对象）棋子布局的变化，棋盘对象接收到了棋子的i变化就要负责在屏幕上面显示出这种变化，同时利用第三类对象（规则系统）来对棋局进行判定。
可以明显地看出，面向对象是以功能来划分问题，而不是步骤。
同样是绘制棋局，这样的行为在面向过程的设计中分散在了总多步骤中，很可能出现不同的绘制版本，因为通常设计人员会考虑到实际情况进行各种各样的简化。
而面向对象的设计中，绘图只可能在棋盘对象中出现，从而保证了绘图的统一。
功能上的统一保证了面向对象设计的可扩展性。
比如我要加入悔棋的功能，如果要改动面向过程的设计，那么从输入到判断到显示这一连串的步骤都要改动，甚至步骤之间的循序都要进行大规模调整。
如果是面向对象的话，只用改动棋盘对象就行了，棋盘系统保存了黑白双方的棋谱，简单回溯就可以了，而显示和规则判断则不用顾及，同时整个对对象功能的调用顺序都没有变化，改动只是局部的。
再比如我要把这个五子棋游戏改为围棋游戏，如果你是面向过程设计，那么五子棋的规则就分布在了你的程序的每一个角落，要改动还不如重写。
但是如果你当初就是面向对象的设计，那么你只用改动规则对象就可以了，五子棋和围棋的区别不就是规则吗？
（当然棋盘大小好像也不一样，但是你会觉得这是一个难题吗？
直接在棋盘对象中进行一番小改动就可以了。
）而下棋的大致步骤从面向对象的角度来看没有任何变化。
当然，要达到改动只是局部的需要设计的人有足够的经验，使用对象不能保证你的程序就是面向对象，初学者或者很蹩脚的程序员很可能以面向对象之虚而行面向过程之实，这样设计出来的所谓面向对象的程序很难有良好的可移植性和可扩展性。
2、ADT是什么？
简述你对“数据抽象”和“信息隐藏”的认识
抽象数据类型（AbstractDataType简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。
抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。
抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。
对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。
一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。
抽象数据类型通过类（class）实现
程序设计语言对抽象数据类型的支持是指允许用户自定义具有如下特征的数据类型：
1.模块封装：
Therepresentationof,andoperationson,objectsofthetypearedefinedinasingle
syntacticunit
2.信息隐蔽：
Therepresentationofobjectsofthetypeishiddenfromtheprogramunitsthatusethese
objects,sotheonlyoperationspossiblearethoseprovidedinthetype'sdefinition
3、const和static有什么作用？
const是一个C和C++语言的关键字，它限定一个变量不允许被改变，即只读。
使用const在一定程度上可以提高程序的安全性和可靠性，也便于实现对此进行优化（如把只读对象放入ROM中）。
const作为类型限定符，是类型的一部分。
4、友元关系的利与弊
如果将一个函数或一个类声明为另一个类的友元，那么它就可以直接存取这个类对象中的各种数据，而不必在意这些数据的封装级别，即无论是private的，protected的，还是public的，有钱同使，有难同当。
5、C++多态的实现
1.用virtual关键字申明的函数叫做虚函数，虚函数肯定是类的成员函数。
2.存在虚函数的类都有一个一维的虚函数表叫做虚表。
类的对象有一个指向虚表开始的虚指针。
虚表是和类对应的，虚表指针是和对象对应的。
3.多态性是一个接口多种实现，是面向对象的核心。
分为类的多态性和函数的多态性。
4.多态用虚函数来实现，结合动态绑定。
5.纯虚函数是虚函数再加上=0。
6.抽象类是指包括至少一个纯虚函数的类。
构造函数顺序：
基类构造函数派生类构造函数
前面输出的结果是因为编译器在编译的时候，就已经确定了对象调用的函数的地址，要解决这个问题就要使用迟绑定（latebinding）技术。
当编译器使用迟绑定时，就会在运行时再去确定对象的类型以及正确的调用函数。
而要让编译器采用迟绑定，就要在基类中声明函数时使用virtual关键字（注意，这是必须的，很多学员就是因为没有使用虚函数而写出很多错误的例子），这样的函数我们称为虚函数。
一旦某个函数在基类中声明为virtual，那么在所有的派生类中该函数都是virtual，而不需要再显式地声明为virtual。
前面输出的结果是因为编译器在编译的时候，就已经确定了对象调用的函数的地址，要解决这个问题就要使用迟绑定（latebinding）技术。
当编译器使用迟绑定时，就会在运行时再去确定对象的类型以及正确的调用函数。
而要让编译器采用迟绑定，就要在基类中声明函数时使用virtual关键字（注意，这是必须的，很多学员就是因为没有使用虚函数而写出很多错误的例子），这样的函数我们称为虚函数。
一旦某个函数在基类中声明为virtual，那么在所有的派生类中该函数都是virtual，而不需要再显式地声明为virtual。
编译器在编译的时候，发现基类中有虚函数，此时编译器会为每个包含虚函数的类创建一个虚表（即vtable），该表是一个一维数组，在这个数组中存放每个虚函数的地址。
那么如何定位虚表呢？
编译器另外还为每个类的对象提供了一个虚表指针（即vptr），这个指针指向了对象所属类的虚表。
在程序运行时，根据对象的类型去初始化vptr
，从而让
vptr正确的指向所属类的虚表，从而在调用虚函数时，就能够找到正确的函数。
对于例1-2的程序，由于pAn实际指向的对象类型是fish，因此vptr指向的fish类的vtable，当调用pAn->breathe（）时，根据虚表中的函数地址找到的就是fish类的breathe（）函数。
那么虚表指针在什么时候，或者说在什么地方初始化呢？
答案是在构造函数中进行虚表的创建和虚表指针的初始化。
还记得构造函数的调用顺序吗，在构造子类对象时，要先调用父类的构造函数，此时编译器只“看到了”父类，并不知道后面是否后还有继承者，它初始化父类对象的虚表指针，该虚表指针指向父类的虚表。
当执行子类的构造函数时，子类对象的虚表指针被初始化，指向自身的虚表。
对于例2-2的程序来说，当fish类的fh对象构造完毕后，其内部的虚表指针也就被初始化为指向fish类的虚表。
在类型转换后，调用pAn->breathe（），由于pAn实际指向的是fish类的对象，该对象内部的虚表指针指向的是fish类的虚表，因此最终调用的是fish类的breathe（）函数。
要注意：
对于虚函数调用来说，每一个对象内部都有一个虚表指针，该虚表指针被初始化为本类的虚表。
所以在程序中，不管你的对象类型如何转换，但该对象内部的虚表指针是固定的，所以呢，才能实现动态的对象函数调用，这就是C++多态性实现的原理。
6、STL是什么？
组成部分和核心作用
标准模板库于1994年2月年正式成为ANSI/ISOC++的一部份，它的出现，促使C++程序员的思维方式更朝向泛型编程（genericprogram）发展。
7、阐述C++在什么情况下必须进行运算符重载。
？
8、为什么说“继承是C++面向对象的一个主要特征之一”，请做一下简要说明。
?
9、请说明函数模板（FunctionTemplate）和函数模板实例化（function-templatespecification）的区别和联系。
函数模板实例化
在函数模板为每个类型时首先调用中，编译器创建一个实例化。
每个实例化是为该类型的该模板化功能的版本。
在中，此函数为类型时，使用此实例化将调用。
如果您有几个相同的实例化，即使在不同的模块，因此，只有该实例化的一个副本在可执行文件将结果。
函数参数将所有参数的函数模板允许和参数，对该参数不依赖于模板参数的位置。
函数模板可以通过声明与特定类型的模板显式实例化作为参数。
C++中提供了函数模板，实际上是建立一个通用函数，其函数类型和形参类型不具体指定，用一个虚拟的类型来代表，这个通用函数就成为函数模板。
使用模板的好处就是对于那些函数体相同的函数都可以用这个模板来代替，而不必去定义每个具体的函数去实现。
下面通过一个简单的具体例子（比较两个数的大小）来说明：
#include
usingnamespacestd;
template//模板声明，T为类型参数
TMax（Ta,Tb）//定义一个通用函数，用T作虚拟的类型名
{
if（a>b）
{
returna;
}
else
returnb;
}
模板实例化（templateinstantiation）是指在编译或链接时生成函数模板或类模板的具体实例源代码。
ISOC++定义了两种模板实例化方法：
隐式实例化（当使用实例化的模板时自动地在当前代码单元之前插入模板的实例化代码）、显式实例化（直接声明模板实例化）。
10、编译和链接的过程
源文件的编译过程包含两个主要阶段，而它们之间的转换是自动的。
第一个阶段是预处理阶段，在正式的编译阶段之前进行。
预处理阶段将根据已放置在文件中的预处理指令来修改源文件的内容。
#include指令就是一个预处理指令，它把头文件的内容添加到.cpp文件中还有其他许多预处理指令
这个在编译之前修改源文件的方式提供了很大的灵活性，以适应不同的计算机和操作系统环境的限制。
一个环境需要的代码跟另一个环境所需的代码可能有所不同，因为可用的硬件或操作系统是不同的。
在许多情况下，可以把用于不同环境的代码放在同一个文件中，再在预处理阶段修改代码，使之适应当前的环境。
预处理器显示为一个独立的操作，但一般不能独立于编译器来执行这个操作。
调用编译器会自动执行预处理过程，之后才编译代码。
编译器为给定源文件输出的是机器码，执行这个过程需要较长时间。
在对象文件之间并没有建立任何连接。
对应于某个源文件的对象文件包含在其他源文件中定义的函数引用或其他指定项的引用，而这些函数或项仍没有被解析。
同样，也没有建立同库函数的链接。
实际上，这些函数的代码并不是文件的一部分。
这些工作是由链接程序（有时称为链接编辑器）完成的
链接程序把所有对象文件中的机器码组合在一起，并解析它们之间的交叉引用。
它还集成了对象模块所使用的库函数的代码。
这是链接程序的一种简化表示，因为这里假定在可执行模块中，模块之间的所有链接都是静态建立的。
实际上有些链接是动态的，即这些链接是在程序执行时建立的。
链接程序静态地建立函数之间的链接，即在程序执行之前建立组成程序的源文件中所包含的函数链接。
动态建立的函数之间的链接（在程序执行过程中建立的链接）将函数编译并链接起来，创建另一种可执行模块——动态链接库或共享库。
动态链接库中的函数链接是在程序调用函数时才建立的，在程序调用之前，该链接是不存在的。
动态链接库有几个重要的优点。
一个主要的优点是动态链接库中的函数可以在几个并行执行的程序之间共享，这将节省相同函数占用的内存空间。
另一个优点是动态链接库在调用其中的函数之前是不会加载到内存中的。
也就是说，如果不使用给定动态链接库中的函数，该动态链接库就不会占用内存空间
11、解释“优先级队列”这一抽象数据类型及实现方法
如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。
这样，我们就引入了优先级队列这种数据结构。
缺省情况下，优先级队列利用一个最大堆完成函数列表：
empty（）如果优先队列为空，则返回真
pop（）删除第一个元素
push（）加入一个元素
size（）返回优先队列中拥有的元素的个数
top（）返回优先队列中有最高优先级的元素
用途就不用多说了吧，例如Huffman编码、分支限界、A*启发式都需要用到优先队列存放信息。
12、逆波兰式用什么数据结构算法的效率比较高，为什么
13、C和C++，C++和Java的区别
C是一个结构化语言，如谭老爷子所说：
它的重点在于算法和数据结构。
C程序的设计首要考虑的是如何通过一个过程，对输入（或环境条件）进行运算处理得到输出（或实现过程（事务）控制），而对于C++，首要考虑的是如何构造一个对象模型，让这个模型能够契合与之对应的问题域，这样就可以通过获取对象的状态信息得到输出或实现过程（事务）控制。
所以C与C++的最大区别在于它们的用于解决问题的思想方法不一样。
之所以说C++比C更先进，是因为面向对
14、什么是预处理
程序设计中的预处理（Preprocess），程序设计领域，预处理是在程序源代码被编译之前，由预处理器（Preprocessor）对程序源代码进行的处理。
这个过程并不对程序的源代码进行解析，但它把源代码分割或处理成为特定的符号用来支持宏调用。
预处理器的主要作用就是把通过预处理的内建功能对一个资源进行等价替换，最常见的预处理有：
文件包含，条件编译、布局控制和宏替换4种。
15、堆和栈的区别
栈区（stack）—由编译器自动分配释放，存放函数的参数值，局部变量的值等。
其操作方式类似于数据结构中的栈。
堆栈（英文：
stack），也可直接称栈。
台湾作堆叠，在计算机科学中，是一种特殊的串行形式的数据结构，它的特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指标，英文为top）进行加入资料（push）和输出资料（pop）的运算。
另外堆栈也可以用一维阵列或连结串行的形式来完成。
堆栈的另外一个相对的操作方式称为伫列。
由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO,LastInFirstOut）的原理运作。
堆栈数据结构使用两种基本操作：
推入（push）和弹出（pop）：
17、简述在面向对象程序设计中，引入继承和封装的主要作用继承：
代码重用封装：
代码安全
18、简述C语言中指针及其作用
19、Java语言的多线程机制
20、简述四种常见的数据逻辑结构
①集合集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。
④图状结构图状结构中的结点按逻辑关系互相缠绕，任何两个结点都可以邻接
21、简述在一棵二叉排序树中查找一特定元素x的算法过程
二叉排序树（BinarySortTree）又称二叉查找树。
它或者是一棵空树；
或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
在最坏的情况是，两子数列拥有大各为1和n-1，且调用树（calltree）变成为一个n个嵌套（nested）调用的线性连串（chain）。
第i次调用作了O（n-i）的工作量，且递归关系式为：
这与插入排序和选择排序有相同的关系式，以及它被解为T（n）=O（n2）。
它的最坏情况是很恐怖的，需要
空间，远比数列本身还多。
23、简述在一带权有向图中寻找关键路径的基本思想
关键路径：
关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。
在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径为关键路径关键活动：
关键路径上的活动称为关键活动。
只有所有关键活动提前完成，整个工程才能提前完成。
最早可能开始时间Ve[i]：
从原点到顶点Vi最长路径的长度（之前所有事情做完了才可能开始）；最迟允许开始时间Vl[i]：
保证汇点Vn-1在Ve[n-1]时刻完成的前提下（整体工期不拖），事件Vi最迟允许的开始时间。
Vl[i]=min{Vl[k]-dur（）}
关键活动：
松弛时间（slacktime）Al[j]-Ae[k]==0的节点。
24、类作用域和文件作用域的区别是什么
文件作用域也称“全局作用域”。
定义在所有函数之外的标识符，具有文件作用域，作用域为从定义处到整个源文件结束。
文件中定义的全局变量和函数都具有文件作用域。
如果某个文件中说明了具有文件作用域的标识符，该文件又被另一个文件包含，则该标识符的作用域延伸到新的文件中。
如cin和cout是在头文件iostream.h中说明的具有文件作用域的标识符，它们的作用域也延伸到嵌入iostream.h的文件中。
操作系统1.进程和线程的区别及联系，操作系统的程序栈…
线程和进程的区别：
1、线程是进程的一部分，所以线程有的时候被称为是轻权进程或者轻量级进程。
2、一个没有线程的进程是可以被看作单线程的，如果一个进程内拥有多个进程，进程的执行过程不是一条线（线程）的，而是多条线（线程）共同完成的。
3、系统在运行的时候会为每个进程分配不同的内存区域，但是不会为线程分配内存（线程所使用的资源是它所属的进程的资源），线程组只能共享资源。
那就是说，出了CPU之外（线程在运行的时候要占用CPU资源），计算机内部的软硬件资源的分配与线程无关，线程只能共享它所属进程的资源。
4、与进程的控制表PCB相似，线程也有自己的控制表TCB，但是TCB中所保存的线程状态比PCB表中少多了（上下文保存一下就行）。
5、进程是系统所有资源分配时候的一个基本单位，拥有一个完整的虚拟空间地址，并不依赖线程而独立存在。
进程与程序的区别：
程序是一组指令的集合，它是静态的实体，没有执行的含义。
而进程是一个动态的实体，有自己的生命周期。
一般说来，一个进程肯定与一个程序相对应，并且只有一个，但是一个程序可以有多个进程，或者一个进程都没有也可以只有一个进程。
除此之外，进程还有并发性和交往性。
简单地说，进程是程序的一部分，程序运行的时候会产生进程。
总结：
线程是进程的一部分，进程是程序的一部分。
前一句说的不太准确，线程也有自己的资源，比如栈，私有数据等等。
说他使用而不拥有资源指的是使用的是进程的打开文件句柄，进程的全局数据，进程的地址空间等等,这些都属于进程，而不属于线程，进程内个线程共享。
进程切换比线程切换开销大是因为进程切换时要切页表，而且往往伴随着页调度，因为进程的数据段代码段要换出去，以便把将要执行的进程的内容换进来。
本来进程的内容就是线程的超集。
而且线程只需要保存线程的上下文（相关寄存器状态和栈的信息）就好了，动作很小。
2.OS里面进程的“三态”“五态”“七态”是什么
3.什么是操作系统
4.死锁的条件，检测死锁的可能方法及其基本思想
Adeadlockisasituationinwhichtwoormorecompetingactionsareeachwaitingfortheothertofinish,andthusneithereverdoes.
1.（互斥）:
Atleasttworesourcesmustbenon-shareable.[1]Onlyoneprocesscanusetheresourceatanygiveninstantoftime.
2.HoldandWaitorResourceHolding:
Aprocessiscurrentlyholdingatleastoneresourceandrequesting
additionalresourceswhicharebeingheldbyotherprocesses.
3.No（禁止抢占）:
Theoperatingsystemmustnotde-allocateresourcesoncetheyhavebeen
allocated;theymustbereleasedbytheholdingprocessvoluntarily.
4.Aprocessmustbewaitingforaresourcewhichisbeingheldbyanotherprocess,
whichinturniswaitingforthefirstprocesstoreleasetheresource.Ingeneral,thereisaofwaiting
processes,P={P1,P2,...,PN},suchthatP1iswaitingforaresourceheldbyP2,P2iswaitingforaresourceheldbyP3andsoonuntilPNiswaitingforaresourceheldbyP1.[1][7]
ThesefourconditionsareknownastheCoffmanconditionsfromtheirfirstdescriptionina1971article
by[7]Unfulfillmentofanyoftheseconditionsisenoughtoprecludeadeadlockfromoccurring.
Ensurethatthesystemwillneverenteradeadlockstate.
Prevention:
Ensureoneofthefourconditionsfails.
Avoidance:
TheOSneedsmoreinformationsothatitcandetermineifthecurrentrequestcanbesatisfiedor
delayed.
死锁检测：
1.Resource-AllocationGraph
2.DetectionAlgorithm
5.用户态和内核态
当程序运行在3级特权级上时，就可以称之为运行在用户态，因为这是最低特权级，是普通的用户进程运行的特权级，大部分用户直接面对
升级会员 