一、数据结构 1.判断题 1对f（n）=o(g（n）)，也不一定有f（n）=o(g（n-1）) 2 3 4 散列表用不超过长度的素数，即使分布理想，使用取余法仍然会堆积 5 6 7 2.选择题 1.五个互异结点构造二叉搜索树有多少种 2.直接插入排序（64，63，62...1）比较次数最接近 …… 6.逆波兰表达式 3.利用广度优先搜索求无向连通图的围长，最短回路长度。o(n)空间复杂度，o(n·e)时间复杂度 1)算法思想 2）伪码表示 3）时间空间复杂度 4.有序向量的二路归并排序 1）填空merge 2）对ABCDE处的注释补充 3）rotate（） 4）说明这种算法的优缺点 5.利用后序遍历查找第一个结点和当前结点的后序遍历下一个结点 1）first（） 2）next（） 3）证明总时间平均与结点数线性相关 二、组成原理 1.填空题 1）指令由指令操作码和——组成 2）海明码 xxxxxxxx 有（）位错误，正确的D1D2D3为—— 3）DMA使用总线的方式——和—— 2.选择 （）计算机运行的最小单位 a） b）微指令 c）指令 d） 3.30位虚拟地址，28位物理地址，一级页表，页表大小16KB，访问5ns，cache采用直接相连映射，大小64KB,块大小4B，访问5ns，主存访问40ns 1）虚拟页表脏位1位，有效位1位，问页表大小 2）cache标志位，索引位，块内地址各多少位 3）一次cache命中访问时间，cache失效访问时间，命中率为90%平均访问时间 4）系统进程切换时以下操作是否需要，原因 a）清除cache有效位 b）将已经调入页表清空 5）注意到页表访问和cache访问时间相同，可否通过修改cache映射方式，使cache和页表一同访问，可以的话做出相应设计，并计算cache90%命中率的时候的平均访问时间。 4.指令流水线可能发生的冲突分类，以及原因 三、操作系统 1.多选题 1）exec（）系统调用 4）产生很多不必要的小碎片的分区 a）最佳匹配 b）首次适应 c）最坏匹配 能够有效避免产生小碎片的 abc同上 5）管程错误的是 7）belay异常，当增加长度反而使命中率降低的页面置换算法 FIFO,OPT,LRU... 8）磁盘阵列哪种最快 a）RAID0 b）RAID1 c）RAID x(忘了3？4？) d）RAID5 2. 1）很多代码balabala，求intr 2）flag，turn balabala填一行代码 2.一台计算机虚拟空间8KB，物理空间4KB，二级页表，页表项32B,页目录项1B，页表大小32B，求进程页面大小有多少b 四、计算机网络 4.太空站的128kbps，发送512字节，端到端的传输延迟300ms，确认帧长度忽略不计，接收窗口足够大，问发送窗口分别为1，15，27时，吞吐率，以及发送窗口多少吞吐率最大 5.给一个网络的表填写距离向量表和路径表，ip地址为200.1.5.0/24四个局域网分别有78，38，14，9个主机，划分子网，每个路由器的端口，网络地址范围。 本文来源：https://www.wddqw.com/doc/9c9941f9d838376baf1ffc4ffe4733687f21fc7e.html