(0012)《数据结构》复习思考题答案.docx
版权申诉
90 浏览量
2022-11-05
12:06:04
上传
评论
收藏 555KB DOCX 举报
（0012）《数据结构》复习思考题答案
一、
常用的存储表示方法有哪几种?
常用的存储表示方法有四种：
顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑
关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附
加的指针字段表示的。由此得到的存储表示称为链式存储结构。
索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
二、
下列程序段带标号语句的频度和时间复杂度。
( 1 ) I=0;
while (I<n)&&(a[I]!=k)
I++; //语句 3
return(I);
( 2 ) n 为不小于 1 的整数（设 k 的初值等于 1）
void pp ( int k)
{
if (k==n) //语句 1
for (I=0; I<n; I++) //语句 2
printf(a[I]); //语句 3
else
{ for (I=k-1;I<n;I++) //语句 4
a[I]=a[I]+I; //语句 5
pp(k+1); //语句 6
}
}//pp
（1）这个算法完成在一维数组 a[n]中查找给定值 k 的功能。语句三的频度不仅与问题的规
模 n 有关，还与输入实例中 a 的各元素取值以及 k 的取值相关，即与输入实例的初始状态复
杂有关。若 a 中没有与 k 相等的元素，则语句三的频度为 n；若 a 中的第一个元素 a[0]等于
k，则语句三的频度是常数 0。在这种情况下，可用最坏情况下的时间复杂度作为时间复杂
度。在此例中即为 O(n)。这样做的原因是：最坏情况下的时间复杂度是在任何输入实例上
运行时间的上界。
有时,也可能选择将算法的平均(或期望)时间复杂度作为讨论目标。所谓的平均时间复杂度是
指所有可能的输入实例以等概率出现的情况下算法的期望运行时间与问题规模的数量级的
关系。此例中，以 k 出现在任何位置的概率相同，都为 1/n，则语句三的执行频度为
[0+1+2+…+(n-1)]/n=(n-1)/2。它决定了此程序段的平均时间复杂度的数量级为f(n)=n,记作
O(n)。
剩余16页未读，继续阅读
评论0
最新资源