苏 州 大 学
二○○一年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：操作系统原理
struct mode{
struct list_head I_hash; struct list_head I_dentry; unsigned long 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_blocks; union{
struct ext2_inode_info ext2_I; }u; };
struct ext2_inode_info{ _u32 I_data[15]; u32 I_flags; };
stuct 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; };
注意：答案请不要做在试题纸上
试卷编号：91 第（2）页共（2）页
苏 州 大 学
二○○一年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：数据结构及程序设计卷
七、1、何谓二叉排序树？（5分）
2、把数据组织为二叉排序树有何优点？（5分）
3、设有一组数据，试编写一程序把这个数据放入一二叉排序树中，要求该树尽可能平衡（二叉排序树用链表表示，算法输出为该二叉排序树的根结点）。（10分）
八、编写一算法，输出一集合的幂集。（15分） 注意：答案请不要做在试题纸上
试卷编号：96 第（2）页共（2）页
苏 州 大 学
二○○二年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：数据结构及程序设计卷
算法请用类PASCAL或类C语言编写，程序请用PASCAL或类C语言编写
一、填空题（20分）
1、栈和队列都是操作受限的＿＿＿ 。对于顺序存储的栈的空间是有限的，在进行＿＿＿ 运算时，可能发生栈的上溢，在进行＿＿＿ 运算时，可能发生栈的下溢。
2、用kmp算法进行主串和子串模式匹配，已知子串为：abababababb，其next函数值为＿＿＿ ， nextval 函数值为：＿＿＿.
3、存储密度定义为＿＿＿，存储密度大时，运算处理的特点是＿＿＿.
4、在三元组表表示的稀疏矩阵快速转置算法中，为了得到矩阵M的转置矩阵N，需附设num和cpot俩个向量，它们的作用分别为＿＿＿和＿＿＿。
5、数组A（1：10，－2：6，2：8），若以低下标优先存储，第一个元素的首址是100，每个元素占2个字节，则A（5，0，8）的存储地址为＿＿＿。
二、n个结点的m叉树转化为二叉树所需存储资源比转化前用定长结点存储结点存储节省多少（设链域占二个单元，数据域占一个单元）？（10分）
三、已知如下所示长度为12的表：
（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）按表中元素顺序插入，构造一棵平衡二叉排序树。（10分）
四、设一数列的顺序为1，2，3，4，5，6，通过栈操作。（10分） （1） 能否排成顺序为3，2，5，6，4，1 为什么？ （2） 能否排成顺序为1，5，4，6，2，3 为什么？ 注意：答案请不要做在试题纸上
试卷编号：552 第（1）页共（2）页
苏 州 大 学
二○○二年攻读硕士学位研究生入学考试试题
学科、专业：???????研究方向：???????考试科目：数据结构及程序设计卷
五、试编写一循环队列的出对操作和入队操作的算法。（10分）
六、如下图，利用算法求从顶点a到其他各顶点间的最短距离，写出执行算法过程中的各步状态。（10分）
七、字符串快速匹配算法KMP所使用的next函数的定义为：
0当j＝1时?next(j)???max{k|1?k?j且'p1....pk?1'?pj?k?1...pj?1'}当此集合不空时
?1其它情况?试编写一算法计算next(1),next(2),??直到next(m)，要求算法复杂度为O(m)。（10
分）
八、有n个人围坐在一张圆桌，座位依次从1至n。开始时第m个人退席，接着往下数又是第m个人退席，如此下去，试编一个程序打印出这些人退席的顺序。例如n=8,m=4时，其顺序为48521376（10分）
九、有一个银行的帐目文件，其主文件f保存着各存户的存款余额，每个存户作为一个记录，存户帐户为关键字；记录按关键字从小到大顺序排列。一天的存入和支出集中在一个事务文件g中，事务文件也按帐号排序。写一过程成批地更改主文件，得到一个新文件h。（10分） 注意：答案请不要做在试题纸上
试卷编号：552 第（2）页共（2）页
