复试题Day 13
数据结构
时间复杂度为 O(nlogn)的排序方法？：
快速排序
从数组中取出一个数，称之为基数
遍历数组，将比基数大的数字放到它的右边，比基数小的数字放到它的左边。遍历完成后，数组被分成了左右两个区域
将左右两个区域视为两个数组，重复前两个步骤，直到排序完成
按照上述规则，每轮中的基数都被调整到其最终的位置上：第一轮遍历排好 1 个基数，第二轮遍历排好 2 个基数（两个子数组中有两个基数），第三轮遍历排好 4 个基数（四个子数组中有四个基数）… 因此总遍历轮数为logn ~ n 次
归并排序
针对两个无序数组：开辟一个长度等同于两个数组长度之和的新数组，并使用两个指针来遍历原有的两个数组，不断将较小的数字添加到新数组中，并移动对应的指针即可。
针对一个无序数组：我们可以把数组不断地拆成两份，直到只剩下一个数字时，这一个数字组成的数组我们就可以认为它是有序的，两个对于两个由一个数字组成的数组我们就可以使用归并排序得到一个有两个数字的有序数组；然后再将这些拆分的数组不断的两两组合起来，就完成了归并排序。
堆排序
- 用数列构建出一个大顶堆，取出堆顶的数字；
- 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
- 循环往复，完成整个排序。
希尔排序
将待排序数组按照一定的间隔进行排序，如此时排序间隔为gap：则从index=gap处的元素开始排序；对于index = i的元素，每次和当前index - gap处的元素进行比较，直到符合插入条件；然后继续比较index = i++的元素，直到数组末尾，完成当前间隔的排序
逐渐缩小间隔进行下一轮排序
最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
计算机组成原理
什么是存储器的刷新？刷新有哪些典型的方式？
计算机内部有控制信息流和数据信息流。控制信息流包括指令信息、状态信息、时序信息，这些信息的组合产生各类控制信号，对数据信息进行加工处理，并控制数据信息的流向，实现计算机的各项功能。
操作系统
目前常用的磁盘调度算法有哪几种？
(1)先来先服务(FCFS，First-Come First-Served)
此算法根据进程请求访问磁盘的先后次序进行调度。
(2)最短寻道时间优先(SSTF ，ShortestSeekTimeFirst)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3)扫描(SCAN)算法
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
(4)循环扫描(CSCAN)算法
CSCAN算法规定磁头单向移动，避免了扫描算法导致的某些进程磁盘请求的严重延迟。
(5) N-Step-SCAN和FSCAN调度算法
\1) N-Step-SCAN算法。为克服前述SSTF、SCAN、CSCAN等调度算法都可能出现的磁臂停留在某处不动的情况即磁臂粘着现象，将磁盘请求队列分成若干个长度为N的子队列，按先来先服务算法依次处理这些子队列，而各队列分别以扫描算法进行处理。
\2) FSCAN算法
FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在 扫描期间，新出现的所有请求磁盘I/O进程的队列，放入另一等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
计算机网络
面向连接服务与无连接服务各自的特点是什么?：
面向连接的服务是按顺序，保证传输质量的，可恢复错误和流量控制的可靠的连接。基于TCP/IP协议。
无连接服务是不按顺序，不保证传输质量的，不可恢复错误不进行流量控制的不可靠连接。基于UDP/IP的连接。
数据库
E-R 图的三种冲突?：
存在的冲突
(1).命名冲突：项名、项目名异名同义，统一命名为项目名；
(2).结构冲突：项目在两个局部 ER 图中，一个做多值属性，一个作实体。
(3).属性冲突。统一 为实体；运动队在两个局部图里的结构不一致也需统一。
专业面试
在考研的过程中，你认为在什么方面提升最大
? 我认为在考研的过程中，我的基础知识提升很大，对于基本的数据结构和构造方式都有了更好的理解，在于对操作系统以及计算机网络有关的算法协议以及设计模式也有了更清楚的认识与理解。让我对于整体学习体系框架的构建有了更深的理解，还有就是通过学习数学，我的逻辑思维得到了很多的锻炼，我不在拘泥于一种解题方式，而且去弄清楚出题人的意图，以及想考的知识点，从而加深了我对于知识的理解，以及解决问题方法的构思。
?
英语面试
How did you get along with your classmates or friends？？
Thank you for your question. I want to say two things about this question.
The first aspect is that in daily learning, discussing problems together can increase the goodwill among classmates, and can also exercise teamwork ability.
There is another aspect that I often go to work with my friends to do a good job together. Through cooperation, the friendship is enhanced and the learning ability of both parties is enhanced. My optimism makes my friends more cohesive. I enjoy working with each other. their time together.
? 感谢老师的提问，针对这个问题我想说的有两个方面。
? 首先一个方面是在日常的学习方面，一起探讨问题可以增加同学之间的好感，也可以锻炼团队协作能力。
? 还有另一个方面我经常和朋友去为了做好一件事一起努力，通过一起合作增进了友情也增进了双方的学习能力，我的乐观让朋友们变得更有凝聚力，我很享受和他们在一起的时光。
?
|