2011

总结

实在绷不住了，这次是个大教训————完成度比完美度重要，驴总是吃不到眼前的萝卜也就忽悠不动了。
到了最后关头的3道答题还是搞不定，让我彻底心态崩了。也明白了不一定要一次性全部搞懂搞熟练，不然的话真的没法搞，重要的是每天一套卷，这才是要紧的。

so赶紧完结这一篇，带回要看部电影，打游戏，猛吃西瓜+猛喝可乐，好好爽一把以后————然后开始看真题视频和王道冲刺班视频，明天白天要刷出新的一套卷子，yep，就是要快、要做出东西来才行。
————20230715

做题

ABBCC

DACDA

BDB D

T28.（确定）D

缺页处理在哪一章出现？操作系统-内存管理？——是的，虚拟内存之请求式分页存储管理。

缺页时总共有哪些操作？为什么问的是“可能是”？——就是要io进来，然后分配页框（页框是对内存而言，页是对进程而言），然后修改页表，这个可能是题目出得有点奇怪

T29.（不会）

抖动，是在哪儿的？是指什么？——操作系统-虚拟内存，是频繁得把页框调入调出内存的情况。

磁盘交换区是什么？——外存中有存文件的文件区和存从内存中取出的交换区。

D——A

T30.（确定）——《操作系统》P166

C

这不是编程的各个阶段的术语嘛？编辑edit，编译成二进制文件，装载是指文件块到内存中去嘛？编译是从.c-->.o目标模块，链接是形成可执行文件.exe，装载是装入内存。逻辑地址是指在目标模块内的相对地址，所以是链接后形成的

T31.（确定）

缓存区和用户区以外，还有什么区？这是哪里提出的概念？——IO章节提的，就缓冲区、用户进程（用户区、工作区）P299

B

T32.（确定）

并发执行有没有可能是P1执行完了P2才开始执行呢？——有可能

C

T33.A

T34（不确定）C——B

是vlog2W还是v/log2W啊？——除以，波特率是比特率除以log2W

T35（不确定）B

SR、GBN、还有个啥协议，这仨哪些是满足确认帧以前都默认收到啊？——停等协议、GBN协议、SR协议。停-等是单帧传送，没有累计确认的问题，而SR协议不是累积确认的。

T36.（不会）C——D

这四个有接受端的确认这个工作嘛？——CDMA是物理层的。CSMA和CSMA/CD没有明说用了ACK，但是CSMA/CA是用了ACK确认帧的。

T37.D

T38.B ——C，我搞错了，00和11之间有两个数01和10.

T39（不会）C

忘了TCP连接中——SYN 是做什么用的了。seq是要加一嘛？——《计算机网络》P230，SYN=1,seq=x ; ACK=1,SYN=1,seq=y,ack=x+1 ; ACK=1, seq=x+1,ack=y+1

T40.（不确定）C——B

忘了这个序号是一定往后排嘛？是排在开头还是结尾？——序号是该TCP数据段首字节的编号；确认序号是期望下一个收到的数据的首字节编号。

TCP连接是累积确认，所以现在它期望的是第二段。

T41.（不确定）

邻接矩阵是什么图像？——就是矩阵

为什么只有15个数据而不是36个？——上三角矩阵，第一行5个数，第二行4个，以此类推。

（1）
$$
要改：a=\left[\matrix{0 \quad 4 \quad 6 \quad \infty \quad \infty \quad \infty \
0 \quad 0 \quad 5 \quad \infty \quad \infty \quad \infty \
0 \quad 0 \quad 0 \quad 4 \quad 3 \quad \infty \
0 \quad 0 \quad 0 \quad 0 \quad \infty \quad 3 \
0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 3
}\right]
$$

??无穷是不是等价于 不指向？——问：邻接矩阵中什么时候填0什么时候填1？异同是什么？

答：11年408真题第41题的参考答案采用了对角线设为0、其他不可达边设为∞的写法。个人理解应该是为了算法目的，∞表达暂时不可达的边，0则表示无意义的边，暂时不可达的边与无意义的边在某些算法里是存在一定区别的

关键路径是不是经过所有的点，但是不打结的最短路径？ 0->2->4->5 12

——不是！《数据结构》AOV网的内容。p230. 关键路径是从源点到终点的具有最大路径长度的路径。所以是0 ->1 ->2 ->3 ->5 总路径长度为16.

T42.

（1）先建立一个新的数组C，其大小为A或者B序列大小(假设为n)的两倍2n；然后将AB序列合并并重新排序到C中，最后选出处在C中「2 n/2」=「n]的那个位置的数。

（2）见手写

（3）时间复杂度：比较次数只与n有关，O(2n)=O(n)；空间复杂度为创建一个数组，大小为2n所以为O(2n)=O(n)

这个题目想不到答案给的算法方法是不是就0分呢？——倒也不是，15分的题目扣一半的分差不多。

T43.——不确定， 此题对扩展我的理解很有帮助！

unsigned 是什么意思？——无符号数

无符号数和有符号数都是以补码的形式存储，加减运算没有区别（不考虑溢出情况时），只是输出的时候若是有符号数的最高位是符号位。

（1） 86H 70H(所以应该是90H)（忽然意识到只有负数取反加一的话，那怎么凭借十六进制数本身判断它是不是补码呢？还是说一定要先声明这是补码？——反正全都是补码） F6H（搞错了，我写成了R2=246，实际上是溢出了，所以应该是7C=x+y-256，当然保险一点是先转成2进制的x和y然后做加法再转成十六进制）

是不是a+b=c，c的值是存在b的寄存器上的？

（2）86H 90H（看题啊，是十进制表示，然后m是符号数，因此x赋予它的值的最高位被当作了负数了，所以这个补码要转换为原码，符号位不变，数值位取反加一得到-122）

（3）减法是怎么利用加法器实现的？

整理

x = 134= 1000 0110B =86H y=246=1111 0110B =F6H

m=1000 0110B = 86H ，原码等于 1111 1010B=-122 n= 1111 0110B=F6H ，原码等于1000 1010B=-10

所以x+y=134+246-256=124，然后转成B或者H，也可以二进制加法得到正溢出为0111 1100B=7CH；

x-y=134-246=-112转成补码等于10010000B=90H，也可以先把246转换成-246写出它的补码（把246作为原码取反加一）直接二进制加法，也等于1001 0000B=90H

所以m+n=1000 0110B+ 1111 0110B=0111 1100B（和x+y是一样的）=124= -122+-10=-132（注意，这里其实发生了负溢出，因为真值只有7位了，所以最多表示的只有-128到+127而已）=128-4=124

m-n=10000110B + (注意，带符号取反+1得到-n的补码) 0000 1010B=1001 0000B=90H（和x-y的二进制结果是一样的），它的原码是1111 0000B=-112 恰恰等于 -122 - （-10）

无符号整数的加法，减法是直接带”符号位“的补码进行相加嘛？ 是的。不过原来x,y被赋值以后可都是正数（补码）

带符号整数的加法，减法是直接带”符号位“的补码进行相加嘛？ 是的，不过被赋值以后可是补码。

所以x+y和m+n 以及 x-y 和m-n在二进制数值上是一样的（都是补码相加嘛）

所以说，先转换成十进制来加减也可，先转换成补码（变成相反数时，都是全部取反+1，包括符号位也取反）然后加法，然后再转成原码（但是这个时候，就是符号位不变，数值位取反加一了）再变成十进制结果也可。

补码相加的结果在

T44.（不会，尽管看上去好像有点点熟悉的影子）非常好的一道连接OS和计组的TLB等等难点的题目！

• [x] 页面大小是一个页的大小嘛？和块的大小为什么不同？ —— 页框frame 是内存而言， 页面page是进程而言

• [x] 虚拟地址和物理地址的结构是怎样？ 页号？+ 页内地址？ 是的

• [x] 为什么虚页号要12位？这里却只有8位？是因为页表只有“部分”？——这里题目给的图例应该是错了，右边cache的应该分别是“行号、有效位、标记位）

• [x] 为什么页表内的页框号是2位数，Cache内页框号是3位数？ ——同上

（1） 8位，3位？？？？

（2）？？？

• [x] 什么叫字段？——见下，cache中对于地址是分成了三段而不是两段。

（3）

• [x] 是如何去击中内存的？（从逻辑地址到物理地址？）——逻辑地址解析出页面号，看看在不在页表中。如果在就取出页框号，然后合成在主存中的物理地址。

（4）

• [x] 这个TLB快表是不是连接虚拟内存用看在不在内存中，还是看在不在cache中？——图表中是页框而不是块，所以是虚拟内存用的。

• [x] 怎么看页框号和标记号到底占多少？——标记号占11位，页框号这是它给的。

解答：

（1）这里是《操作系统》内存进程管理的内容

逻辑地址空间-----虚拟地址要占多少位，所以24位。

页面大小——页内地址占多少位，所以12位。

虚页号+页内地址=逻辑地址——所以虚页号12位。

主存地址空间——物理地址占多少位，所以20位。

页面大小——页内地址占多少位，所以12位。注意，不是cache行或者主存交换块的大小32B

（2）这里是《计算机组成原理》-cache的内容：

物理地址，又可以分成三个字段——块内地址、cache字块标记、主存字块标记

块的大小——块内地址，所以5bit

cache行数——cache字块标记，所以3bit

剩下的为主存字块标记（？？为什么不是主存除以块大小？因为它是想标记这个cache行到底是对应哪一组主存块）——所以12bit

(3)

在页表中有 页号为1 的，说明此时该进程的页面在主存中而不是外存中，它的页框号是04.

所以物理地址是页框号+ 页内地址 = 04C60H

注意，这里不是拿逻辑地址去命中！！而是它在内存中的物理地址！！根据（2）可知对应的cache行数是0000 0100 1100 0110 0000 B 中的011B也就是第3行（这里答案说第4行是答案又错了），此时的页框号是105H，但是我们的标记位是04CH

(4)

看TLB中记录的是页框号而不是块号，所以应该是记录虚拟内存的。

所以逻辑地址要改变了：12 bit记录页内地址，12bit记录页号，其中8个页表项分成4路，也就是2组，组号占1bit（而不是反过来2bit）.所以最低的1bit为组号，其他11bit位标记（注意，不是说题目给的图有多少位十六进制表示页号就一定要有多少位的页号，它可以多表示（比如写00AH，实际上只有后11位表示），但是不可以少表示。）

所以024BACH也就是0000 0010 0100 1011 1010 1100 B 在0组，然后剩下的十一位，从右往左每4位转成一个十六进制（而不是从左往右搞12位）变成了012H，发现对的上，所以能命中。还有个页框号是1F（这里其实就也能写出它的物理地址了）

T45.

不会的

• [x] T8.简单路径？？——路径（点序列），简单路径（无重复点的点序列）

拓扑序列？？？——就是之前做拓扑排序方法的那个题对应的知识点。AOV网

• [x] T10.快速排序

1、常见的排序方法，需要看看视频记一下。——https://blog.csdn.net/alzzw/article/details/97970371

2、内部排序—— 顺序存储

• [x] T12.IPC是啥？——CPI的倒数 clock per instruction

  MFLOPS——Million Floating-point Operations per Second

• [x] T13——float型数据用IEEE 754单精度浮点数格式表示

十进制数---->二进制表达：

符号位：0正1负

指数位：真值+127（double则加1023）

尾数：从$$2^{-1}位开始记 $$，左对齐。

不熟的

• [x] T3，增减时front rear谁变，怎么变，然后找初始状态前的那个点，往初始状态变化。

插入元素时，front不变，rear+1.

• [x] T4.不是：度的和+1-结点数 。 结点个数结构 ——第n层有多少结点，前n层有多少个结点，叶子结点要在最后两层选

确实可以用度的方法去做，key在“度为1的结点只有0或者1个”，当总结点数为奇数时，度为1的结点数为0；当总结点数为偶数时，有1个度为1的结点。

• [x] T5.生疏了。看前序遍历、中序遍历、后序遍历，要找序列上的点，其左边都是左子树、右边都是右子树等等方法来构建图像。

前序、后序遍历序列----根结点，再到中序遍历序列去找左右子树，再依次类推。

• [x] T14.CDROM等等分别用于做什么

SRAM贵，CPU

DRAM便宜，DDR5，内存条

CD-ROM:做光盘的，顺序读取

EEPROM，做成flash，再做成SSD和U盘

• [x] T16.十种寻址方式——王道《组成原理》P165

• [x] T17. 标志寄存器——https://blog.csdn.net/weixin_46013401/article/details/111823010

  进位/借位标志CF（针对无符号数）——进位:1，加法进位加1或者0；错位是减法，1表示减成负数了

  零标志ZF——1是零，0否零

  符号标志SF——0正数，1负数

  溢出标志OF（针对有符号数）——1是溢出，0否溢出

T26.系统调用——用户层、与设备无关软件层、设备驱动程序以及中断处理程序。与设备无关软件层也就是系统调用的处理程序。

疑惑的

• [x] T6.树转化为二叉树，和森林转为二叉树是一样的方法嘛？ ——是的，一样的

没有右孩子 ------没有右兄弟---？--->详解如下：

https://blog.csdn.net/qq_33514421/article/details/102774026

简单来说，1、它把二叉树的分为$$n_0、 n_1左、 n_1右、 n_2 $$分别对应原来树的无子无（右）兄、有子无兄、无子有兄、有子有兄。

2、二叉树由于$$ N=n_0+n_1+n_2\ N=n_1+2*n_2+1 \---> n_0=n_2+1$$

所以，已知了原来数的叶子结点，也就是无子的，也就是新的二叉树的$$ n_0+n_1右$$，要求的是$$n_0+n_1左 $$ 所以它等于N+1-已知的部分。

• [x] T11 大根堆插入元素如何调整（向上调整） https://blog.csdn.net/Zj_boring/article/details/105157360 王道数据结构P342

大根堆，小根堆，的序列是不是层遍历，而不是先序、中序后序？——对

大根堆，小根堆 是不是完全二叉树？——对

小根堆插入元素如何调整？——一样的，按照完全二叉树插入（在数组末尾插入）后依次跟根比较，看能否交换上调。

无序序列如何建立大根堆/小根堆？——从下往上建立大根堆或者小根堆，上层堆下坠时会破坏下层堆，于是再调用一次“建立堆”

删除一个堆元素——输出顶部根——调整方法是将最后一个元素覆盖最顶层元素，然后向下交换（最后一个元素置顶并下坠）

• [x] T13.

浮点数的表示格式中：是用补码嘛？

——阶码是用移码，尾数用的是原码

• [x] T20.总线有哪几类？每一类又分为哪几种线？系统总线（控制线、数据线）、通讯总线？——《组成原理》p274

按功能分。片内总线、系统总线（数据总线、控制总线、地址总线）、I/O总线、通讯总线

• [ ] T27银行家算法？
• [ ]

8.25*2^-11用IEEE754表示 网上居然没有