苏州大学 - 话题

苏州大学
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如再加一个限制条件：同一个顾客进出必须通过同一扇门，那么相应算法如何写







2001年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：操作系统.

一，是非题：判断是非并给出解释。（5‘*4）
1．1分布式操作系统和网络操作系统没有本质区别。
1．2使用快表技术事实上将增加一次快表的访问时间，所以在内存中应该慎用该技术。
1．3死锁在操作系统的设计和实现中是绝对不容许出现。
1．4原语操作是不可被中断的。
二，简述题。（5‘*4）
2．1进程和线程的异同。
2．2操作系统本质上也需要时空开销的，这样解释这些开销还是值得的。
2．3简述存储器管理的基本目的和基本问题。
2．4简述设备分配的基本类型和基本策略。
三，叙述中断机制在操作系统中的地位和作用。（10‘）
四，试给出一种实现虚存的解决方案。（10‘）
五，举出设备管理子系统中利用中断，轮询和DMA的例子。（12‘）
六，以下是 Linux文件系统的四个相关的结构定义的一部分：
6．1请描述这些结构的作用和相互关系；（8‘）
6．2根据这些结构，请描述文件的物理结构；（8‘）
6．3基于这些结构，请设计至少四条有关文件系统功能调用的实现。（12‘）
struct inode{
struct list_head i_hash;
struct list_head i_dentry;
unsigned ling i_ino;
unsigned int i_count;
kdev_t i_dev;
umode_t i_mode;
off_t i_size;
time_t i_atime;
time_t i_mtime;
time_t i_ctime;
unsigned long i_blksize;
unsigned long i_block;
union{
struct ext2_inode_info ext2_i;
}u;
};
struct ext2_inode_info{
_u32 i_data[15];
_u32 _flags;
};

struct dentry{
int d_count;
struct inode *d_inode;/*Where the name belongs to –NULL is negative*/
struct dentry *d_parent;/*parent directory*/
struct list_head d_hash;/*lookup hash list*/
unsigned char d_iname[DNAME_INLINE_LEN];/*small names*/
};
struct list_head{
struct list_head *next,*prev;
};
2001年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：数据结构及程序设计
算法请用类 PASCAL或类C 语言编写，程序请用PASCAL 或类C语言编写
一．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（注意不设头指针），试编写相应的置空队列，入队列和出队列的算法。（10分）

二．假设有两个按元素值递增有序排列的线性表A和B，A和B均一单链表表示，请编写算法将表A，B归并成一按元素值递减有序排列的线性表C，并要求利用原表（即表A和表B）结点空间存放表C。（10分）

三．1．何谓排序方法的稳定性？（3分）
2．下列排序方法哪些是稳定的哪些是不稳定的？（4分）
3．对不稳定的方法举实例说明之。（8分）
直接插入排序，希尔排序，快速排序，归并排序

四．试编写归并排序算法。（10分）

五．有下列关键字：（10分）
15，23，29，31，47，66，74，85，90，98，102
1．画出描述折半查找过程的判别树。
2．对含关键字的有序表，采用折半查找，在查找成功时，关键字比较次数至多是多少？在查找不成功时，关键字比较次数至多是多少？

六．编写一算法，判别以邻接表方式存储的有向图中是否存在顶点Vi到顶点Vj的路径。（10分）

七．1．何谓二叉排序树？（5分）
2．把数据组织为二叉排序树有和优点？（5分）
3．设有一组数据a1,a2,a3,……,an,试编写一程序把这n个数据放入一二叉排序树中，要求该树尽可能平衡（二叉排序树用链表表示，算法输出为该二叉排序树的根结点）。（10分）

八．编写一算法，输出一集合的幂集。（15分）
苏州大学
2000年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：操作系统

1， 简述题（4*8‘）
1．1， 请简述进程和现程之间的异同。
1．2， 程序的链接方法中有一种是运行时动态链接，什么是运行是动态链接，有什么特点？
1．3， 如何区分分时操作系统的客户运行的程序和网络操作系统所支持的客户端的运行程序？
1．4， 简述设备管理的基本功能。

2，如果一个作业在执行中，按下列页号访问：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6作业固定占用4块内存空间，采用先进先出淘汰算法和最近最少调用淘汰算法是，各产生多少次缺页中断？写出在淘汰时在内存的页面号和被淘汰的页面号。（18‘）

3， 用管程的方法解决生产者—消费者问题：有若干个生产者和消费者共享一个容量为m的缓冲区。（10‘）

4， 描述请求分页存储管理方式的实现过程。（20‘）
5， 请叙述UNIX的文件管理系统的设计和实现。（20‘）
苏州大学
2000年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：数据结构及程序设计
算法请用类 PASCAL或类C 语言编写，程序请用PASCAL 或类C语言编写
一．填空（15分）
1．已知一棵二叉树的前根序列是BEFCGDH，中根序列是FEBGCHD，则后根序列必为（ ）。
2．设二叉树根结点的层次为1，深度为K的二叉树至多有（ ）个结点。
3．ISAM文件是（ ）文件，VSAM文件是（ ）文件。
二．若在三对角线矩阵A中，三条对角线组成的带状区域按行的顺序放在一维数组中，即a11放在B[1]中，a12放在B[2]中，……，写一个地址公式，由B[1]的地址Loc（B[1]）确定aij的地址Loc（A[i，j]）。（10分）

a11 a12
a21 a22 a23
A= a32 a33 a34

a n-1 n-1 a n-1 n
a n n-1 a n n

三．设一篇短文中出现的字符D={S，I，P，Q，T}，每个字符出现的次数为F={10，29，4，9，5}
1．如何对上面的诸字符进行二进制编码，使得
（1） 该短文的总长度最短；
（2） 为了译码，任一字符的编码不应是另一字符的编码的前缀。
2． 按你得出的字符编码，将二进制字串‘000100011010100’进行译码（译成字符）。
（15分）
四．试编写广度优先遍历图的算法。（10分）

五．已知二叉树前根遍历序列的后根遍历序列，试编写生成该二叉树的算法。算法的输入为二个以字符串形式表示的前根遍历序列和后根遍历序列，算法的输出为该二叉树，用根结点指针表示。（10分）

六．生成一个按蛇形方式排列自然数1，2，3，4，……，n（n+1）/2的上三角N阶方阵，N阶方阵用二维数组表示，试编写程序。（10分）
N=5的N阶方阵的上三角为：
1 3->4 10->11
2 5 9 12
6 8 13
7 14
15

七．选取哈希函数H（k）=(3k)MOD 11,d1=H(k),di=(di-1 + (7k)MOD 10 + 1)MOD 11 (i=1,2,3……)。试在0到10的地址空间里对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求在等概情况下查找成功与不成功时的平均查找长度。（15分）

八．有若干条红色，黄色的色条随机摆满一行，试用复杂度为O（n）的算法把他们按颜色有序摆放（颜色相同放在一起），最多使用一个单元的额外附加空间。（15分）
zz

在中国8月1日是什么节？（答案为两个字）

考研论坛提示：
1、请勿发布个人联系方式或询问他人联系方式，包括QQ和手机等。
2、未经允许不得发布任何资料出售、招生中介等广告信息。
3、如果发布了涉及以上内容的话题或跟帖，您在考研网的注册账户可能被禁用。