历真题及部分答案.pdfVIP

苏州大学

2013年入学考试初试试题

科目代码：872科目名称：数据结构与操作系统满分：150

分

注意：认真阅读答题纸上的注意事项；所有答案必须写在答题

纸上；本试题纸须同答题纸一并交回。

一、数据结构部分

注意：算法可以用类C、类C++、类JAVA或类PASCAL等语言编写，并请写出类

型说明。

1、(15分)简答题。

(1)写出邻接矩阵的类型定义；

(2)写出使用Dijkstra算法求单源最短路径的思想，并写出其时间复杂度；

2、(15分)

已知一组关键字为{26,36,41,38,44,15,68,12,6,51,25}，假设装填因子

α=0.75,

(1)使用线性探测再散列的方法来构造改散列表；

(2)写出关键字68的查找过程；

3、(15分)

一棵树采用孩子兄弟法，写出查找其结点个数的递归算法。

4、(15分)

写出递归删除单链表中所有值为item的算法。

5、(15分)

给定一个值，求出所有得到的新值的个数。例如给出值为345，将其各位数

字相加得到新值为12，对12各位相加得到新值为3，则对345得到的新值的个

数为3个（包括其本身）。

二、操作系统部分

6、(15分)名词解析。

(1)寻道时间

(2)动态装入

(3)用户态线程

(4)内碎片

(5)临界区

7、(15分)判断正误，并说明其理由。

(1)存在m个进程的系统中，产生死锁的条件是1k=m；

(2)分页引入TLB能减少每一次内存的时间；

(3)在引入虚存的系统中，磁盘无限大，进程编址就无限大；

(4)文件存放在外存中；

(5)进程从等待到就绪，一定有就绪到运行；

8、(15分)已知某系统中,CPU的利用率为3%，磁盘I/O的利用率是97%，其

它I/O是5%，以下改进是否能够提高系统的利用率，请说明理由。

(1)安装更高速的CPU;

(2)撤销内存中进程；

(3)增加内存容量；

(4)选择更大的硬盘；

(5)选择更快速的硬盘；

9、(15分)假设某系统采用一级页表，TLB为98%，TLB时间是10ns,

内存时间是100ns,页面置换时间是200ns,并假设当TLB失败时才开

始内存，求：

(1)TLB命中时的平均时间是多少？

(2)不命中时的平均时间是多少？

(3)产生缺页中断，并进行页面置换后的平均时间是多少？