---

2019考研北大软微867专业课大题简要回忆

数据结构4个题

1. 给了一个二叉树的图，具体记不清了，中序反正是ABCDEFGHIJ ，要求写出前序，中序，后续遍历序列。10分

2. 要求根据查找频率设计排列顺序，并且计算查找长度。（这个题在王道真题分析上面的原题）。这个题我从真题分析上抄下来给大家看看，是2013年408统考真题第42题。原题如下：

设计包含4个元素的集合S={“do”, ”for”, ”repeat”,  “while”},各元素的查找概率为p1=0.35,p2=0.15, p3=0.15, p4=0.35, 将S保存在一个长度为4的顺序表中，采用折半查找算法，查找成功时的平均查找长度为2.2，请回答：

（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

（2）若采用链式存储结构保存S，切要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？

3. 给了ABCDEFGH 8个字母，并且给了使用频率，0.02,0.03, 0.06，... ，0.32, 要求对其进行哈夫曼编码。

4. 给出了一个有向图，要求使用Dijstra最短路径算法求出V0到V1，V2，V3，V4的距离和路径，要求写出过程。

操作系统3个题

1. （1）请求分页的知识考察以及逻辑地址到物理地址的变换

（2）画出内存地址变换的机构【我有话要说: 这个图，平时看了N遍，但是让你考试的时候手画出来还真不好画，我花了很多时间雕琢这幅画....】

（3）根据LRU和FIFO置换算法，分别列出一个内存访问序列的缺页次数。【15分】

2. 给出了3个进程，P0,P1,P2,三类资源X0,X1,X2，给出了最大需求矩阵和已分配资源矩阵，即Max矩阵，Allocation矩阵，问能不能给 P1分配其请求的（0,2,1）资源请求？【10分】

3. （1...