考研面试C/C++和数据结构常见问题
C和C++的区别堆和栈的区别由C/C++编译的程序占用内存分区引用与指针的区别关键字static的作用全局变量与局部变量的区别全局变量与静态全局变量的区别堆栈溢出一般是由什么原因导致数组与指针的区别贪心与动态规划的区别分治法与动态规划的区别什么是迭代头指针和头结点区别栈在递归中的应用队列在计算机系统中的应用树的存储结构哈希函数构造方法哈希函数解决冲突方法排序C和C++的区别
C语言:面向过程,目的是分析出解决问题的步骤然后把这些步骤一步步实现,是自顶向下的编程。按步骤划分,性能比面向对象高。
C++:面向对象,把问题分解成各个对象,建立对象的目的不是为了完成一个步骤,而是为了描述某个事物在整个解决问题的步骤中的行为,是功能划分,高度十五抽象化。比面向过程易维护、易复用、易扩展。
C与C++关键字不同(32个/63个)
后缀名不同(.c/.cpp)
返回值(C语言中如果函数没有指定返回值类型默认返回int型,C++中无返回值必须指定为void)
参数列表(C语言中函数没有指定参数列表时默认可接收多个任意参数,而C++中不接受任何参数)
C语言不支持给函数指定默认值
C++支持函数重载。
堆和栈的区别
栈由系统自动分配;堆由程序员自己申请并指明大小。只要栈的剩余空间大于申请空间即可提供内存,否则报异常显示栈溢出;而堆首先要找到空闲链表中第一个大于申请空间的堆结点,然后将结点从空闲链表中删除分配给程序。栈由于是系统自动分配,速度较快,但程序员无法控制;堆由程序员申请速度较慢且容易生成内部碎片,不过用起来最方便。由C/C++编译的程序占用内存分区
栈区:由编译器自动分配释放,存放 函数的参数值,局部变量的值等等。堆区:由程序员分配释放,若程序员不释放可能由操作系统回收全局区:也叫静态区,全局变量和静态变量的存储是放在一块的,程序结束后由系统释放文字常量区:放常量字符串,程序结束后由系统释放;程序代码区放函数体的二进制代码。引用与指针的区别
引用必须初始化,指针不必;引用初始化后不能被改变,指针可以改变所指对象;不存在指向空值的引用,但是存在指向空值的指针。
关键字static的作用
在函数体中,一个被声明为静态的变量在函数被调用的过程中维持其值不变在模块内,一个被声明为静态的变量可以被模块内所用函数访问,但不能被模块外的其他函数访问,是一个本地的局部变量。3.在模块内,一个被声明为静态的函数只可被这一模块内的其他函数调用,也就是这个函数被限制在声明它的模块的本地范围内使用。
全局变量与局部变量的区别
全局变量储存在静态数据区,作用于整个程序;局部变量在堆栈中,作用于定义变量的模块内。
全局变量与静态全局变量的区别
两者都是静态存储方式,而非静态全局变量的作用域是整个源程序;而静态全局变量则限制了其作用域,即只在定义该变量的源文件内有效,在同一源程序的其他源文件中不能使用它。可避免在其它源文件中引起错误。
堆栈溢出一般是由什么原因导致
没有回收垃圾资源;层次太深的递归调用。
数组与指针的区别
数组要么在静态存储区被创建,要么在栈上被创建;指针可以随时指向任意类型的内存块。
贪心与动态规划的区别
贪心算法作出的每步贪心决策都无法改变,因为贪心策略是由上一步的最优解推导下一步的最优解,而上一步之前的最优解则不做保留。每一步的最优解一定包含上一步的最优解。
动态规划中,全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解。动态规划的关键是状态转移方程,急如何由求出的最优解来推导全局最优解。边界条件是局部最优解。
总结为一句话就是:贪心寻找的是局部最优解,全局不一定最优;而动态规划寻找的是全局最优。
分治法与动态规划的区别
动态规划也是一种分治思想,但分治算法是把原问题分解为若干个子问题,自顶向下求解子问题,合并问题的解得到原问题的解;动态规划同样是把原问题分解为若干个子问题,但是是自底向上求解。先求最小的子问题,把结果存在表格中,在求解大的子问题时直接从表格中询问小的子问题的解,避免重复计算,从而提高算法效率。
分治法将分解后的子问题看成相互独立,通过递归实现;动态规划将分解后的子问题理解为相互间有联系,有重叠部分,需记忆,通过迭代来实现。
什么是迭代
迭代是重复反馈过程的活动,目的通常是为了逼近所需目标或结果,每一次对过程的重复称为一次“迭代”。每一次迭代得到的结果会作为下一次迭代的初始值。
头指针和头结点区别
头指针是指向第一个节点存储位置的指针,具有标识作用,头指针是链表的必要元素,无论链表是否为空,头指针都存在。
头结点放在第一个元素节点之前,便于在第一个元素节点之前进行插入和删除的操作,头结点不是链表的必需元素,可有可无,且数据域也可以不存储任何信息。
栈在递归中的应用
将递归算法转换为非递归算法,通常需要借助栈来实现这种转换。
队列在计算机系统中的应用
解决主机与外部设备之间速度不匹配问题解决由多用户引起的资源竞争问题树的存储结构
双亲表示法:在每个结点中增设一个伪指针,指示其双亲结点在数组中的位置。
孩子表示法:将每个结点的孩子结点都用单链表链接起来形成一个线性结构,n个结点有n个孩子链表。
孩子兄弟表示法:又称二叉树表示法,每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针及指向结点下一个兄弟结点的指针。
哈希函数构造方法
直接定址法、除留余数法、数字分析法、平方取中法、折叠法、随机树法
哈希函数解决冲突方法
1.开放定址法:又包括线性探查法、二次探查法、双重散列法
2.拉链法