笔试练习题001...to be continued...

笔试练习题001…to be continued…

加粗代表未解决问题

希尔排序的时间复杂度和增量的选取有关，下界是O(nlogn)，不稳定 输入非法时能给出适当处理，是健壮性 冒泡排序的比较次数 霍夫曼编码：每次取出两个权值最小的合并再放回去 快排在数据基本无序时最有优势 二分查找：如果大于num[mid], left = mid + 1;小于则right = mid - 1（注意mid位置的数不再参与下次的比较） 一趟排序后：快速排序分两边，冒泡排序大小端，希尔排序间隔有序，堆排……画个图吧 排序算法稳定性：冒泡插入和归并：稳定；希尔和快排：不稳定 list采用链式结构存储，可以用在快排和冒泡上，但快排更快；不适合二分插入这种需要随机访问元素的 数据项才是数据不可分割的最小单位，数据元素是组成数据的有一定意义的基本单位 折半查找，查找成功的平均比较次数先形成二叉树然后再计算比较方便 n个数值选出最大的m个数（3 < m < n）的最小算法复杂度 排序趟数和序列的原始状态有关的排序方法有：优化的起泡排序、快速排序。（插入和选择的排序趟数和序列原始状态无关）

---

操作系统的功能：处理器管理、存储器管理、设备管理、作业管理和文件管理等 操作系统中，进程是可以并行的基本单位 摒弃不可剥夺条件能预防多个打印机死锁的发生 进程P一旦被唤醒就能投入运行：抢占式调度方式，P的优先级高于当前运行的进程（不是只比就绪队列里的优先级高哦，而是直接剥夺在运行的进程）（注意审题：一旦被唤醒就能投入「运行」） 子网掩码 关中断指令不能在用户态执行。而trap指令、跳转指令、栈操作（后栈指令是什么鬼？？） 关于四次挥手，个人理解如下：（四次挥手内容在“「」”中） 前提：假设A是主动关闭方，B是被动关闭方 A要主动关闭连接，A告诉B「我不再发消息啦」并进入FIN-WAIT-1状态（此时A还可以接收消息） B告诉A「我知道你不发了」，并进入CLOSE-WAIT状态 A收到B的报文，知道了B知道自己不再发消息，进入FIN-WAIT-2状态，此时A->B通道已经关闭 B发现自己也没消息要发了，（发出“被动关闭”请求），就告诉A「我也不再发消息了」，并进入LAST-ACK A收到B的报文，知道B不再发消息，于是给B发消息「我知道你不发了」，并进入TIME-WAIT状态，等待2MSL之后进入CLOSED状态 B收到A的确认，知道了A知道自己不再也发消息，进入CLOSE状态，此时B->A通道也关闭了

-TBC-