2012

感受

总计3+3+4=10H

1、玛德，做了好几套卷子了，结果选择题正确率来看，和去年年底没差，气，心态难绷啊。

2、玛德，做了好几套卷子了，结果还是这么慢！

3、应该要做到一套卷子在6-9小时能完成，每天做出来一套卷子 这很重要 可行性，不然一天的努力小时数其实不能保证的

要有舍有得

4、还是要记录每天自习小时数和进度这两点比较好

5、一度做错题时非常之气愤，当然做对了题目或者悟出来以后确实是快乐，还算个Happy Ending。

20230717

选择题

做题	正确答案
B
C	A	前中后缀表达式
A
B
5D	C
A	C	key在不一定是上三角矩阵
C
8	A
9	D
10A
11	D
12D
A	B	典型的大数，十进制转二进制方法 不是用除法，而是找近的值，再加减，可用8类比
D
15B	D
A
A	C
B	C
C
C	D
21A	D
D	B
A	C
A	B记住
D	B	记住虚拟内存一定要离散分配内存。 虚拟内存大小取决于CPU寻址能力。
A
D
28D	A
B
D	C	记住。
31A
B（不确定）
	B	ICMP是网络层中高于IP的一种协议；PPP协议是数据链路层协议
34C
C （不会）	A	记住，MAC协议和IP协议都是无连接、不可靠的。
B（不会）
D（不确定）	C	III是进行差错校验，但是不保证IP分组不丢失。
A
D
D
	粗略估一下分	都是很好的题目
T41	0	归并排序
42	0	链表算法
43	3	I/O，存储器的总线带宽，DMA等等的结合
44	3	指令流水线
45	9	请求分页机制
46	9	文件的块索引
47	5	TCP报文段、IP数据报、MAC数据帧，TCP的连接、传输、路由全流程结合

需要去专门看的：

• 图的应用：最小生成树之Prim算法和Kruskal算法、最短路径之Dijkstra算法与Floyd算法

• 十大内部排序：（动态图、稳定性、时间空间复杂度、三级分类）

• 树形排序之平衡树的调整、红黑树的调整

• 操作系统之文件系统

• 计算机网络的IP分组、TCP的数据怎么去读分析前面n字节的内容？？

T2（不确定）——核心问题就俩：如何转化表达式（一个栈方法、一个快速方法，栈方法还演化出二叉树表达方式）

https://blog.csdn.net/AngelDg/article/details/104526308

• [x] 中缀表达式和后缀表达式分别怎么看（计算机怎么运算的）？——本质上是前缀后缀如何转化为中缀（后缀是从右往左扫，遇到运算符了就弹出两个操作数来运算）
• [x] 有没有前缀表达式——有
• [x] 哪一个是个二叉树有关的？——前后缀表达式——前后缀如何转化为中缀，每弹出一个运算符，就形成了一个父结点

后缀表达式

• [x] 中缀表达式如何转化为后缀表达式的（栈在这个过程起了什么作用）？

从左到右，遇到操作数，直接生成到后缀表达生成式中；

遇到运算符，拿他和运算符栈的栈顶元素比一比优先级，如果优先，则放进栈顶，否则先输出栈顶再比较。

遇到左括号，先放进来，遇到右括号，输出栈顶直到和做括号抵消。

• [x] 中缀如何转化为前缀？——（从右往左扫描、输出时从右往左、优先级相同也先保留、先输入右括号再左括号抵消，其他是和转化为后缀一样的） ； 快速的中缀和前后缀的互相转化方法？——先写出括号，然后移动运算符/先看连续的两个数，调整运算符并画括号。

T3.（确定）

• [x] 有没有更快的办法？——有

当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。 ae ea 故e为a的孩子结点；e[bcd] -- [bcd]e，故[bcd]是e的子树

T4.（确定）

• [x] 高度为6是有6层还是7层

6层

T5（不会）

• [x] 邻接表的表示形式（画图）？——《数据结构》P201 顶点表结点和（出）边表结点

• [x] 广度优先遍历？——借助一个队列，类似二叉树的层序遍历，也类似拓扑排序（这是我自己觉得的） ——《数据结构》P212

-- BTW---

深度优先遍历，借助栈来实现类似先序遍历。

T7（不确定）

• [x] Dijkstra算法求最短路径 的过程？——《数据结构》图的应用-最短路径问题P226 它是竖着每一轮生成一个最短路径

T8（不会）P222

• [ ] 最小生成树？ 从叶子结点往上拼的那个？

• [ ] 最小生成树的代价？

• [ ] Prim算法，Kruskal算法？

T9（不会）

• [ ] B- 树 B树，B+树，红黑树

B- Tree就是B树，翻译问题。

删除方式，直接删除、兄弟借、兄弟不够借三种情况，见《数据结构》-排序方式-B树的删除P298

T10（确定）

• [x] 各种排序的过程

  快排不是只分成了左边比它小、右边比他大两部分嘛？ ——每次定位基数元素到它确定的位置（左边都比他小，右边都比他大）

II III IV（是不是输出一个，末尾的树放上去再下沉——不是输出，而是根末尾的元素交换，最终能形成一个层序遍历后得到升序的二叉树） V（相邻两个为一组排序，再相邻4个为一组排序等等——是的，希尔排序就不是相邻两个，而是间隔着的两个）

https://zhuanlan.zhihu.com/p/355745303

https://blog.csdn.net/weixin_46629453/article/details/126078678

T11（不会）

• [x] 插入排序的过程？ 折半插入排序的过程？ 快排是插入排序？——快排属于交换排序

T14（确定）

• [x] 中间8位难道最大不是128？为什么是127？——IEEE规定E码中全0（0）和全1（255）的要舍去，所以只能表示1-254，也就是只能表示-126 ~ 127

T15（不确定）

• [x] 小端存储喝低地址交叉编址的异同？—— 小端存储是数据的低位的存在低地址（左边）， 低位交叉编址是体号存在地址的低位，而不是低地址，所以遍历地址时是各个“体”轮流遍历

• [x] 高位存在小端还是说低位存在小端？ —— 小端大端，都是说 低位放在小端还是大端。

• [x] char占几个字节？ ——1个字节

• [x] 数据按边界对齐 存储 ——K字节大小的数据 必须要存储在 K的整数倍的地址 上

T16（确定）

• [x] 哪些由MOS管组成，对应的复杂的是什么元件（SRAM什么管）？ SRAM---MOS管，DRAM--栅极电容，这道题我才知道原来Flash也是MOS管

T17（确定）

• [ ] 块号%路数=组号——————不是，是块号%行数（4），余数为0、1的在第0组，余数为2，3的在第1组——余数为0就在第0组的0行吗？——不见得，随机叭？？——————据说有改版，所以要看近几年的真题怎么说了

T18（不确定）

• [x] 它是问指令操作码有几位（至少）嘛？——是的
• [x] 操作码是类号+类内号嘛？ ——不是，是互斥类各个位数直接拼起来，每个类除了那几个微命令，还要加一个不发出微命令的命令。

T19（不确定）

• [ ] 同步总线是什么？
• [x] 是先要传地址嘛？地址是8bit但是也要传一次，所以要先占10ns嘛？——是的；地址多少位取决于地址空间的大小/地址线的bit数，但是这里说了“传输一个地址占用一个时钟周期，所以是10ns”

T20（确定）

• [x] D意思是一次只能传输2位？传输率是传输速率嘛？—— 实际上串行总线，同时（不是说一次）只能传1位；不晓得。

T21(不会)

• [x] 哪些信息分别属于数据总线和控制总线？——不是的。

片内总线、系统总线（控制总线、数据总线、地址总线）、I/O总线（命令线、数据线、地址线）、通信总线

命令线、地址线是CPU发往I/O接口的。

I/O 接口中的命令字、状态字以及中断类型号均是由 I/O 接口发往 CPU 的，故只能通过 I/O 总线的数据线传输。

T22（不确定）忘了

• [x] 《组成原理》P300

中断的十大流程：中断隐指令（关中断、保存断点、中断服务程序的寻址） 、 保存现场和屏蔽字、 开中断、中断服务程序、关中断、恢复现场和屏蔽字、开中断、中断返回。

断点就是下次指令的地址、现场就是当时的通用寄存器的内容、开中断意味着允许嵌套，中间五个是对称的

T23（不会）

系统调用：调用程序发生在用户态，被调用程序完成在内核态。

外部中断发生在用户态，完成在内核态

缺页中断发生在用户态，完成在内核态。

进程切换是执行中的系统调用执行中的一个事件，所以发生在内核态。

T24（不会）

T26（不会）忘了

• [x] 设备驱动程序和中断处理程序，哪些是用户态、哪些是内核态？——应该都是内核态。

  https://blog.csdn.net/Albert_weiku/article/details/121315919

T28（不确定）

• [ ] 哪些操作是在内核、用户态。。。。。。。。。。传输文件的过程是内核态（中断服务程序）嘛？

• [x] 进程的五种状态？什么时候进入？ 建立-就绪-运行-阻塞-完成 中断时原来的进程就阻塞态，中断执行时会进入内核态。

• [x] read的参数：open（它倒是需要文件名这个参数）返回的fd（file description）、读取字节数n、目标缓冲区位置buf

T33（不会）

• [x] ICMP？？

T36——这题因为没有明确定义信道利用率的概念，所以只能先记住经验——相同时间传的帧越多越好，所以这样计算。

• [ ] 信道利用率=？ n*（帧长度/传输速率）/nT+540ms ——不是，是单帧传输时长/2个单帧传输时长和2个单向传播时延，所以要用128字节而不是256字节
• [ ] 帧序号和帧长度有什么关系？ （帧的结构）——这题目要问的是一次能传多少帧？算得出来能传10帧左右，所以