【2022.7.20 星期三】考研日记：顺序栈、链栈
上午高数网课+线代强化+660题（定积分，积分不等式）
下午200单词，傍晚复习200单词。
晚上408，数据+计组+操系+计网，七点半到十点半。
408知识积累：
【数据结构】
①栈和队列具有相同的（逻辑结构），都是线性结构。
②
进栈：S.data[++S.top]=x;【++在前】
出栈：x=S.data[S.top–];【–在后】
③不同出栈序列的总数
(2n)! / (n+1)(n!)(n!)
(6x5x4x3x2x1) / (3+1)(3x2x1)(3x2x1) = 5种
④
【单循环链表】知尾找头容易，知头找尾困难（需要遍历整个单循环链表）
所以，没尾巴的单循环链表，不适合作为链栈。
⑤链栈插入x结点：直接头插。
x->next=top;【x插在原来栈顶的上面】
top=x;【x取代原来的栈顶】
⑥链表头部作为栈顶，说明：
- "入栈"操作时，需要将数据从链表的头部插入；
- "出栈"操作时，需要删除链表头部的首元节点；
因此，链栈实际上是一个，只能采用头插法，进行插入删除的链表
【计组】
计算机性能指标
1、字长：字长越长，计算精度越高。
2、数据通路带宽：指外部数据总线DB的宽度，≠CPU内部DB宽度
3、主存容量：字数x字长（512K x 16位）
4、吞吐量：系统在单位时间内，处理请求的数量
5、响应时间：发送请求，直到系统响应并给出结果，的总时间
6、CPU时钟周期：主频的倒数。最小时间单位，指令的每个动作至少占一个时钟周期。
7、主频：时钟周期的倒数。主频越高，执行指令越快。
8、CPI：一整条指令所需的时钟周期数目。
9、执行时间：运行整个程序的总时间
执行时间 = 周期数/主频 = 周期数x周期 = 指令总数xCPI / 主频
10、MIPS（Million Instructions Per Second）（每秒执行几百万指令）
11、MFLOPS、GFLOPS、TFLOPS
12、基准程序：测电脑性能的。
系列机：使用同一套基本指令系统
固件：将程序固化在ROM，组成的硬件。
固件速度比硬件快，灵活度比软件好
【操作系统】
①单道 批处理系统：自动，顺序进行，只有一个单道。
缺点：发出请求时，高速CPU只能等待低速IO，等待输入输出完成。
②多道 批处理系统：多道，“宏观上并行，微观上串行”。
优点：资源充分利用，系统吞吐量大，硬件保持忙碌
缺点：完全没有人机交互
并发（concurrent）并行（parallel）顺序（sequent）串行（serial）
③分时操作系统：多个终端用户，同时玩一台电脑，各用户的操作彼此独立
同时性、交互性、独立性、及时性（短时间内收到响应）
④实时操作系统：硬实时（飞机自动控制系统），软实时（订票系统）
⑤网络操作系统
⑥分布式操作系统
⑦嵌入式操作系统Linux、服务器操作系统、iOS、Android
【计网】
SDU：Service Data Unit，服务数据单元
PCI：Protocol Control Information，协议控制信息
PDU：Protocol Data Unit，协议数据单元