苏州大学05年计算机真题
数据结构部分(算法用类C，C++或类pascal语言编写，要有说明)
一(10分) 什么叫平衡二叉树?一棵结点数为N的平衡二叉数的平均查找时间为多少?请简述之。
二(15分)有1000个无序的数值，希望从快速排序，基数排序，堆排序，归并排序中选一种排序算法，能以最快的速度排出10个最大的数据来，试问选哪种排序算法?为什么?
三(15分)试编写在单向链表中删除值相同的多余结点的算法(要求不使用辅助空间)。
四(20分)设稀疏矩阵M(m*n)中有t个非零元素，用三元组顺序表的方式存储，请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O(n+t)。
五(15分)试设计一个递归算法，产生n!个不同的全排列。
操作系统部分
六(15)请解释并比较以下概念
1，共享设备和独占设备
2，SMP和ASMP
3，物理地址和逻辑地址
七(15)简答题:
1，目录在文件系统中的作用是什么?
2，在操作系统中引入线程有什么好处?
3，在设计操作系统时，主要有哪几种结构可供选择?
八(15)有一个虚拟存储系统，每个进程在内存占有3页数据区，刚开始数据为空，某个进程按照以下的序列对页面进行访问
2，3，4，5，3，4，1，2，3，5，1，4，1，4，5，1，3，2，1，3
试分别给出下列情况发生的缺页次数，并说明什么时候发生(即访问哪一页时发生)
1， 系统采用先进先出(FIFO)算法
2， 系统采用最近最少使用(LRU)淘汰算法
3，系统采用最优(OPT)淘汰算法
九(15)桌上有一个空的水果盘，盘中一次只能放一个水果，服务员，男顾客和女顾客共用这个盘子，服务员可以向盘中放草莓，也可以向盘中放香蕉，男顾客专等吃盘中的草莓，女顾客专等吃盘中的香蕉，规定每次当盘子空时只能放一个水果供顾客取用，请用信号量机制实现服务员，男顾客，女顾客三个进程的同步
十(15)一个系统中存在某类资源m个，被n个进程共享，资源的分配和释放必须一个一个进行，请证明在以下两个条件下系统不会发生死锁:
1，每个进程需要资源的最大数在1~m之间;
2，所有进程需要的资源总数小于m+n 。 | 
