- —四川最大高校综合门户网
说明： 1、本试卷为数据结构和操作系统两部分。数据结构部分共六题，满分100分：操作系统部分共三题满分50分。全试卷共十题，满分150分。 2、答案一律写在答题纸上。 3、答卷应字迹清楚，语义确切。 数据结构部分 注意事项： 1、算法应说明基本思路，应对主要数据类型
说明：
1、本试卷为数据结构和操作系统两部分。数据结构部分共六题，满分100分：操作系统部分共三题满分50分。全试卷共十题，满分150分。
2、答案一律写在答题纸上。
3、答卷应字迹清楚，语义确切。
数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你所熟悉的高级语言编写，但要注明语种。
一、解答下列问题（共30分）；
1、[5分]根据数据元素之间关系的不同特性，数据的逻辑结构通常有哪些基本结构？数据元素之间的关系在计算机中有哪几种表示方式？
第1页
2、[5分]将N*N的上三角矩阵A（i>j时A[i][j]=0,i<j时A[i][j]>0）的非零元存储在一维数组B（下标k从0开始），试给出B[k]与A[i][j]之间的元素对应关系。
3、[5分]写出后缀表达式abxcde/-fx+的运算顺序。
4、[5分]画出广义表（a,(x,y),((x))）的存储结构。
5、[5分]比较哈希表与其它查找表的不同之处。
6、[5分]利用两个栈S1和S2模拟一个队列，写出入队算法和出队算法的算法思想。
二、[10分]已知树T的先序访问序列为：ABEFCDGHIK后序访问序列为：EFBCHIKGDA。
1、画出树T。
2、将树T转换为对应的二叉树BT。
3、将二叉树BT后序线索化。
三、[15分]有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小。假设针对某一个记录，统计出的计数值为c，那么，这个记
第2页
录在新的有序表中的合适的存放位置即为c（如C=0则当前元素存放在新表的号单元）。
编程实现计数排序算法
四、[15分]编写一递归属算法，删除单链表中所有值为x的结点。
五、[15分]试写一算法，求二叉树T中任意指定两个结点最近的共同祖先结点。
六、[15分]度写一算法，判断有向图G中任意指定两个结点之间是否存在路径。
操作系统部分
一、判断题（正确者打√错误者×，每小题1分，共10分）
1．进程控制块是进程存在的唯一标识。
2．作业调度是高级调度，而进程调度是低级调度。
3．时间片越小，系统的响应时间就越小，系统物效率就越高。
4．按首次适应算法分配的分区，一定与作业要求的容量大小最接近。
5．在分页存储管理中，减少面百大小，可以减少内存的浪费。所以，页面越小越好。
6．进程A与进程B共享变量S1，需要互斥；进程B与进程C共享变量S2，需要互斥。从而，进程A与进程C也必须互斥。
7．虚拟存储器的基本思想是把作业地址空间和主存空间视为两个不同的地址空间，前者称为虚存，后者称为实存。
8．虚拟设备技术是在一类物理设备上模拟另一类物理设备的技术，它可以将独占设备改造为共享设备。
9．文件的物理结构密切依赖于文件存储器的特性和存取方法。
10．移臂调度的目标是使磁盘的旋转周数最小。
第3页
二、名词角释（每小题词分，共15分）
1．操作系统2．周转时间3．碎片4．设备驱动程序5．事务
三、综合题（25分）
1．（6分）设有两个进程P1和P2的程序如下，其信号量的初始值S1=S2=0，试求P1，P2并发执行结束后的x,y,z的值，并对结果加以解释。
进程1 进程2
Y=1; x=1;
Y=y+2; x=x+1;
Signal(s1); wait(s1);
Z=y+1; x=x+y;
Wait(S2); signal(S2);
Y=y+z; z=z+x;
2．（4分）简述产生死锁的原因和必要条件。
3．（6分）考虑下面的页访问串：
1，2，3，4，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6假定有4，5个页块，应用下面的页面置换算法，计算会出现多少次缺页中断。注意，所给定的页块初始均为空，因此，首次访问一页时就会发生缺页中断。
（1）Optimal; (2)FIFO; (3)LRU
4．（4分）设备管理中为什么要引入缓冲区？
5．（5分）对空闲磁盘空间的管理采用哪儿种分配方式？并简述UNIX系统中所采用分配方式的分配过程。