软件技术基础课程学习报告参考模板.pdfVIP

软件技术基础课程学习报告

数据为{1，0，9，2，0，3，8，9，0，8，0，

3}

1依次做如下操作：

建立一棵二叉排序树如下：

1

09

29

0

3

0

8

0

838

一个哈希表长12，试用模除求余法设计哈希

算法，用线性探测法解决冲突，并求平均查

找长度ASL；

解：

M=12，P取11

地01234567891011

址

1/10

软件技术基础课程学习报告

关012030038998

键

字

查111426751124

找

次

数

平均查找长度：

ADSL=(1+1+1+4+2+6+7+5+1+1+2+4)/12

=35/12

写出进行直接插入排序、简单选择排序、冒泡排序、

快速排序的前两趟趟结果，并构造一个小堆；（排序

时重复数据忽略）

解：

重复数据忽略后为{1，0，9，2，3，8}

直接插入排序：

【1】09238

【01】9238

【019】238

简单选择排序：

【009238】

0【19238】

软件技术基础课程学习报告

01【9238】

冒泡排序：

【109238】

【01238】9

【0123】89

快速排序

【109238】

【0】1【9238】

【0】1【9238】

小堆：

0

12

389

将每一位数据作为一个页面调用，若在分页方式下的

内存分块数为4块，试求出用FIFO进行页面淘汰时

的缺页中断率，要求有过程。

软件技术基础课程学习报告

解：

调用顺109203890803

序

内存块109223880000

1

内存块10992338888

2

内存块1009223333

3

内存块1109