2021秋-计软实验一：图与散列表V31
需积分: 0 130 浏览量
2022-08-08
19:18:14
上传
评论
收藏 23KB DOCX 举报
《计算机软件基础》实验指导书
1
计软实验一：图与散列表
一、 实验目的
通过编程掌握图的度分布、平均路径长度、聚类系数、度度相关性和簇度相关性的概念
和计算方法；掌握散列表的常见构造方法和两种冲突处理方法。
二、 实验内容
图实验
1． 生成节点个数
N
=
1000
，连边概率
p
=
0.05
的
ER
随机图。
2． 计算该图的度分布、聚类系数和平均路径长度。
3． 分析该图的度度相关性和簇度相关性。
散列表实验
1. 已知关键字序列：
{24,30,23,41,51,68,46,11,14,61,35}
1) 关键字个数
n
=
11
，哈希表长度
m
=
15
,使用哈希函数为
H
(key)
=
key mod 13
，
采用线性探测法解决冲突。输出哈希表。计算查找成功和失败的 ASL。
2) 关键字个数
n
=
11
，哈希表长度
m
=
13
,使用哈希函数为
H
(key)
=
key mod 13
，
采用线性探测法解决冲突。输出哈希表。计算查找成功和失败的 ASL。观察比
较
1
）和
2
）
中查找成功 ASL 的关系以及查找失败 ASL 的关系并简要分析填充系
数对查找性能的影响。
2. 已知关键字序列：
{46,25,40,15,67,34,6,21}
1) 关键字个数
n
=
8
，哈希表长度
m
=
11
，使用哈希函数
H
（
key
）
=
key mod 11
，
采用线性探测法解决冲突。输出哈希表。计算查找成功和失败的 ASL。
2) 关键字个数
n
=
8
，哈希表长度
m
=
11
，使用哈希函数
H
（
key
）
=
key mod 11
，
采用二次探测法解决冲突。输出哈希表。计算查找成功和失败的 ASL。观察比
较
1
），
2
）
中查找成功 ASL 的关系以及查找失败 ASL 的关系并简要分析两种探
测法的优劣。
三、 实验步骤
图实验
1. 编制主程序，实现
2
―
7
中的功能。
2. 通过以下步骤生成 1000 个节点，p=0.05 的 ER 随机图。
1) 选择一对没有边相连的不同的节点。
2) 生成一个随机数
rϵ[0,1]
。
3) 如果
r
<
p
，那么在这对节点之间添加一条边，否则就不添加。
4) 重复以上三个步骤，知道所有节点对都被选择。
3. 输出该无向图的度分布到文件
degree
Distribution.txt
中，格式按照：
2 0.1
评论0
最新资源