2017年初试真题（回忆版）
2．用基数排序方法对关键字序列 012、321、234、543、456、765、678、987、890、109 从小到大排序，写出各趟的结果。
3．一个由两两不等数组成的有序序列具有以下特点：（1）数1在该序列中 （2）若数x在序列中，则2x、3x、5x也在该序列中 （3）除此之外，该序列无其他数。编写算法，输出该序列中最小的100个数，要求使用递归实现。
4．设用二叉链表实现二叉排序树（即二叉查树），一个节点除了一个数据域data，一个左孩子指针域lchild和一个右孩子指针域rchild外，还有一个存储该结点的右子树的结点个数与1之和的域rsize。编写算法，给出存储第k大元素的结点地址。
5．设用邻接表实现有向图，基于图的广度优先搜索策略，编写算法，判断有向图中是否存在
从序号为i的顶点到序号为j的顶点的路径。
6．判断题（20分、10道） 错误请说理由。
（1）操作系统实现双模式需要硬件支持
（2）
（3）一个系统n个进程，最多一个处于运行状态
（4）线程资源分配的基本单位是xx（记不得了）
（5）m个进程系统死锁，死锁进程数：1<k<m。
（6）触摸屏是一个输出设备。
（7）一个12000RPM磁盘的平均旋转延迟时间是5ms。
（8）磁盘上存储的文件一般组织为顺序文件。
（9）产生颠簸（抖动）原因是内存中进程太多。
（10）树形目录和无环图目录无法实现文件共享
7．请用管程来实现读者优先的读写者问题，并写出管程的伪代码以及读者写者的伪代码。
8．一个进程p的空间为64k，运行在一个请求式分页系统中，每个页面大小为8k，该进程的页表如下
页框号 | 有效位 |
12 | 1 |
3 | 1 |
0 | 1 |
6 | 0 |
2 | 1 |
15 | 0 |
5 | 1 |
8 | 0 |
其中，有效位=1表示页面在内存，0表示页面不在内存，请将逻辑地址OX050c、OX1302、OX1F71、OX2C57、OX4400转换为对应的物理地址并写出计算过程。
9．一个文件系统采用索引方式分配磁盘物理，其中磁盘块的大小为4KB索引项大小为32位，回答：
（1）一级索引的文件A、二级B、三级C容量最大为多少？
（2）假设上述A、B、C文件控制块在内存，则删除文件A、B和C的任意一个物理块最多需要多少磁盘块。
（3）
10.举例说明：和FCFS相比，SJF可以获得更短平均等待时间，KR可获得更短的平均响应时间。
一般考研真题是从哪里
发布评论