2003年苏州大学数据结构试题
数据结构
1、 设以单向链表存储串，试编写判别给定串是否具有对称性的算法，并要求算法时间复杂度为O（length（s））。可以设辅助空间，length（s）可以设为已知参数。（10）
2、 设一有向环用邻接表表示，试设计递归算法，设计以Vo出发最长路径的长度。（15）
3、 简述表达式求值的基本思想，并对表达式6/（3-1）求值的操作过程，要求写出操作数栈和运算栈的变化情况。（15）
4、 推导上三角阵在压缩存储时的地址计算公式。（10）
5、 编写算法，求给定结点在给定的二叉排序树中解的层次。（10）
6、 画出有序表（18、34、56、77、78、100、345、450、888）中进行折半查找的判定树，求等概率时查找成功时的平均查找长度。（15）
操作系统
1.1 操作系统及其功能
1.2内存地址重定位
1.3进程和线程
2.4Spooling技术
2、叙述操作系统提供系统调用的原因，并举例说明应用程序使用这些系统功能调用的两种方式。（10）
3、为了支持请求式分页内存管理，通常页表项内存有一标志位，用来记录相应的页是否被写过，请解释该标志位的操作者及其作用。
4、假设有一组任务序列{（x、y）}，x表示到达时间，y表示需要运行的时间，在FCFS和最短作业优先下的平均周转时间。（10）
5、给出一种文件目录结构的设计，并评价这种设计的优缺点。
6、超市可容纳500人同时购物，有6扇可供出入的门，既可进又可出，每扇门只允许一个人通过：
6.1用PV操作及信号量描述进入和离开该超市的算法，使得该超市的购物容量得到最大发挥。
6.2如再加一个限制条件：同一个顾客进出必须通过同一扇门，那么相应算法如何写附件:
2003苏州大学数据结构.doc (2006-12-29 14:09, 19.5 K)
