数据结构和算法课后作业.pdf

作业布置
作业一
第一章
什么是数据对象、数据元素、数据结构？
什么是数据类型？什么是抽象数据类型？
什么是算法？它有哪些特性？它与程序有何区别？
试判定下列计算过程是否为一个算法？
1)开始
2)n<=0
3)n=n+1
4)重复 3)
5)结束
用图形表示下列数据结构：
1) S=(D, R) , D={a,b,c,d,e,f,g} , R={<a,e>, <b,c>, <c,a>, <e,f>, <f,g>}
2) S=(D, R) , D={48,25,64,57,82,36,75} , R={R1, R2}
R1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>}
R2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}
2 3 n
将 O(1) 、O(n) 、O(n )、O(n )、O(nlog2n) 、O(log2n) 、O(2 )按增长率递增排列。
计算下列算法的时间复杂度：
1)
x=100; y=0;
while(x>=y*y)
y=y+2;
2)
sum(int n)
{int sum=0,x, j,k;
for(j=1; j<=n; j++)
{x=1;
for(k=1; k<=j; k++)
p=p*k;
sum=sum+p;}
return sum;
}
>> 查看 /完成作业： 作业一
作业二
试编写一个算法，将一个顺序表逆置，并使用最少的辅助存储空间实现。
试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。
试编写一个算法，计算带头结点的循环单链表的长度。
试编写一个算法，在一个递增有序排列的单链表中插入一个新结点 x，并保持有序。
试编写一个算法，将一个单链表逆置。
试编写一个算法，在一个双向循环链表中将结点 x 插入到指定结点 p 之前。
试编写一个算法，计算一个循环队列中包含的元素个数。
试编写一个算法，实现对一个以只带尾指针的循环单链表表示的队列的入队出队操作。
>> 查看 /完成作业： 作业二
作业三
设字符串 S= ＂good ＂， T=＂I am a student ＂，R= ＂!＂，求：
（1） CONCAT(T ，R，S)
（2） SUBSTR(T ，8，7)
（3） Len(T)
（4） index(T ，＂a＂)
（5） insert(T ，S，8)
（6） replace(T