找了几道研究生复试面试题.md

当时应导师任务，出几道题给研究生复试面试用，“不能太难”，于是乎琢磨，从C/C++、数据结构、计算机组成原理、计算机网络中各选数题。最后发现也没怎么用上，但觉得也算基础，贴在这里吧。

链表和数组的特点，什么时候使用链表，什么时候使用数组？

• 数组数据连续存储，链表数据存储可不连续
• 数组访问元素只需要O(1)时间，链表则需要O(N)
• 主要执行插入删除操作时使用链表，为快速检索时使用数组

二维数组与指针的关系？

二维数组是一维指针，不是二维指针。

在32位的机器上，sizeof(指针)=？

4字节

C++中struct与class的区别

struct默认成员都是public，而class默认都为private

static作用于局部变量和.c文件中的函数前有什么区别？

• static作用于局部变量表示将数据存储到全局数据区，但依然具有局部变量的属性
• static作用于.c文件中的函数表示该函数只能在该文件中访问，是相对于extern而言

new与malloc的区别

1. new是C++关键字（操作符），属于编译器的范畴；malloc是C语言中的函数，clib的范畴
2. new创建的是一个对象，包含构造函数的初始化过程；malloc仅仅是分配一块内存，需要手动初始化

定义void *p；，指针p指向的是什么类型？

void *表示指针可指向任意类型（任意类型的指针都能直接给p赋值），在C语言函数传参中很有用

冯诺依曼结构

1. 计算机处理的数据和指令一律用二进制数表示
2. 存储程序概念，把要执行的程序和处理的数据首先存入主存储器（内存），计算机执行程序时，将自动地并按顺序从主存储器中取出指令一条一条地执行，这一概念称作顺序执行程序

死锁

是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。

快速排序的平均时间复杂度？快速排序是否总是比一般的排序快？

O(NlogN)。数据已经排好序，在选择参考标准的时候总是选择最后一个数据作为参考标准，此时快排效率最低，O(N^2)。

进程与线程区别。操作系统设计中为什么要在进程的基础上提出线程的概念？

区别：

1. 线程是进程的一个实体，一个进程可以拥有多个线程，多个线程也可以并发执行。一个没有线程的进程也可以看做是单线程的，同样线程也经常被看做是一种轻量级的进程。并且进程可以不依赖于线程而单独存在，而线程则不然。
2. 线程没有独立的存储空间，它共享进程的资源，而进程有独立的用户空间

线程引入：

1. 因为进行的创建要分配存储空间，要花费较大的系统开销和占用较多的资源
2. 进程涉及的上下文切换耗费时间（连带存储资源的切换）

线程就是为了提高CPU的执行效率，避免硬件资源浪费而提出的

进程调度的方法

• 优先级轮转：又分抢占式（实时）和非抢占式
• 时间片轮转

因特网协议栈包括哪些层？UDP协议属于哪层的协议？

1. 应用层
2. 传输层
3. 网络层
4. 数据链路层
5. 物理层

UDP是传输层协议。

CSMA/CD

Carrier Sense Multiple Access with Collision Detection。

有人将CSMA/CD的工作过程形象的比喻成很多人在一间黑屋子中举行讨论会，参加会议的人都是只能听到其他人的声音。每个人在说话前必须先倾听，只有等会场安静下来后，他才能够发言。人们将发言前监听以确定是否已有人在发言的动作称为"载波监听"；将在会场安静的情况下每人都有平等机会讲话成为“多路访问”；如果有两人或两人以上同时说话，大家就无法听清其中任何一人的发言，这种情况称为发生“冲突”。发言人在发言过程中要及时发现是否发生冲突，这个动作称为“冲突检测”。如果发言人发现冲突已经发生，这时他需要停止讲话，然后随机后退延迟，再次重复上述过程，直至讲话成功。如果失败次数太多，他也许就放弃这次发言的想法。通常尝试16次后放弃。

中断的作用

1. 响应用户事件（如键盘、鼠标等）
2. 响应实时性要求的紧急任务

栈和队列的区别

• 栈：后入先出
• 队列：先入先出

怎么从尾到头打印单向链表，不改变链表结构？（可给提示：“请提供某种可用的数据结构”）

使用栈或递归可以方便地从尾到头打印链表，从头扫描入栈，扫描完成后全部出栈。