🧶数据结构
下列排序算法中,其时间复杂度和记录的初始排列无关的是___(中国科学院大学 2012)
A. 折半插入排序 B. 堆排序 C. 快速排序 D. 冒泡排序 复制代码
答案及解析
答案:B
🔊 堆排序时间复杂度最好情况最坏情况都为 O(nlog2n),故选B。
排序方法 | 时间复杂度平均情况 | 最好情况 | 最坏情况 | 稳定性 |
插入排序 Insertion Sort | O(n2) | O(n) | O(n2) | 稳定 |
希尔排序 Shell Sort | O(n1.3) | O(n) | O(n2) | 不稳定 |
选择排序 Seletion Sort | O(n2) | O(n2) | O(n2) | 不稳定 |
堆排序 Heap Sort | O(nlog2n) | O(nlog2n) | O(nlog2n) | 不稳定 |
冒泡排序 Bubble Sort | O(n2) | O(n) | O(n2) | 稳定 |
快速排序 Quick Sort | O(nlog2n) | O(nlog2n) | O(n2) | 不稳定 |
归并排序 Merge Sort | O(nlog2n) | O(nlog2n) | O(nlog2n) | 稳定 |
- 稳定:如果a原本在b前面,而a=b,排序后a仍然在b的前面。
- 不稳定:如果a原本在b的前面,而a=b,排序后a可能会出现在b的后面。
🎨计算机网络
下面关于IP地址的论述中哪个是不正确的___(北京邮电大学2011)
A. 用户主机的IP地址可静态分配也可以动态分配 B. IP地址有单播地址,也有多播地址 C. 一个用户主机只能有一个IP地址 D. 在以太局域网中使用ARP协议查找与一IP地址对应的 复制代码
答案及解析
答案:C
🔊 常识:一个主机可以有多个IP地址。
被人提醒并非常识后补充:
⛳ 一个主机可以有多个IP地址,有多个IP地址证明主机属于多个逻辑网络,但是同一时刻一个合法的IP地址只能分配给一台主机,否则会造成冲突。
🎎计算机组成原理
在虚拟存贮器中,当程序正在执行时,由__完成地址映射(北京科技大学2014)
A. 程序员 B. 编译器 C. 装入程序 D. 操作系统 复制代码
答案及解析
答案:操作系统
🔊 地址映射交由操作系统来完成,对程序员透明(不可见)。
🎁操作系统
设某进程的页面走向为:5,4,3,2,4,3,1,4,3,2,1,5,系统有3页物理内存,请问采用LRU和FIFO淘汰算法的缺页次数分别为__(北京航空航天大学2015)
A. 9和10 B. 5和7 C. 6和6 D. 8和10 复制代码
答案及解析
答案:D
🔊 LRU(least recently used),即选择最近最久未使用的页面淘汰。
FIFO(first in first out),即先进先出,先进的先淘汰。
画图模拟即可,方框中情况并不是物理块中情况,这样写比较方便:
FIFO算法: