2012年春季学期信息管理与信息系统专业数据结构课程计算题
- 格式：doc
- 大小：145.00 KB
- 文档页数：3
2012年春季学期信息管理与信息系统专业数据结构课程计算题
1. 写出下列算法的功能和时间复杂度（教材第一章）
（1）
int sum(int n)
{
int i,j,s=0;
for(i=1;i<=n;i++)
{
int p=1;
for(j=1;j<=i;j++)
p*=j;
s+=p;
}
return s;
}
（2）
int Prime(int n)
{ int i=1;
int x = (int) sqrt(n);
while(++i<=x)
if (n%i==0)break;
if (i>x) return 1;
else return 0;
}
2. 对于图中给出的树，指出树中的根结点、树叶结点和分支结点，并指出各个结点的度数和层次数。（教材第五章）
3. 给定一组元素为{45, 24, 65, 80, 32, 16, 90, 72}，试画出按这一排列顺序依次输入元素所创建的一棵二叉搜索树的过程。（教材第六章）
4. 与上题相同的一组元素，采用的输入次序不同，创建得到的二叉搜索树相同吗？为什么？（教材第六章）
5. 对于图(a)和(b)，求出：（教材第七章）
a) 每一个图的二元组表示，对于带权图，可以将边的权写在该边的后面；
b) 图(a)中从v0到v4的所有简单路径及相应路径长度；
c) 图(b)中从v0到v4的所有简单路径及相应带权路径长度。
6. 对于图(a)和(b)，画出每个图的邻接矩阵。（教材第七章）
1
2 9 3
4
5 7 0
1 2 3 4 0 1
2 3
4
(a) (b) 8
1
2 9 3
4
5 7 0
1 2 3 4 0 1
2 3 4
(a) (b) 8 7. 假定一个待散列存储的数据集合为{32,75,29,63,48,94,25,46,18,70}，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。（教材第八章）
