数据结构与算法课后作业

《数据结构与算法课后作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业布置作业一第一章1.1什么是数据对象、数据元素、数据结构？1.2什么是数据类型？什么是抽象数据类型？1.3什么是算法？它有哪些特性？它与程序有何区别？1.4试判定下列计算过程是否为一个算法？1)开始2)n<=03)n=n+14)重复3)5)结束1.5用图形表示下列数据结构：1)S=(D,R),D={a,b,c,d,e,f,g},R={,,,,}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>,

2、<75,82>}R2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}1.6将O(1)、O(n)、O(n2)、O(n3)、O(nlog2n)、O(log2n)、O(2n)按增长率递增排列。1.7计算下列算法的时间复杂度：1)x=100;y=0;while(x>=y*y)y=y+2;2)sum(intn){intsum=0,x,j,k;for(j=1;j<=n;j++){x=1;for(k=1;k<=j;k++)p=p*k;sum=sum+p;}returnsum;}>>查看/完成作业：作业一作业二2.1试编写一个算法，将

3、一个顺序表逆置，并使用最少的辅助存储空间实现。2.2试编写一个算法，将两个元素值递减排列的顺序表合并为一个非递增的顺序表。2.3试编写一个算法，计算带头结点的循环单链表的长度。2.4试编写一个算法，在一个递增有序排列的单链表中插入一个新结点x，并保持有序。2.5试编写一个算法，将一个单链表逆置。2.6试编写一个算法，在一个双向循环链表中将结点x插入到指定结点p之前。2.7试编写一个算法，计算一个循环队列中包含的元素个数。2.8试编写一个算法，实现对一个以只带尾指针的循环单链表表示的队列的入队出队操作。>>查看/完成作业：作业二作业三3.1设字符串S=＂good＂，T=＂

4、Iamastudent＂，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，SUBSTR(T，8，7)，＂teacher＂)3.2计算下列串的next值：（1）aaabcaaba（2）abaabcacb（3）abcabcacb（4）babbabab3.3若X和Y是两个单链表存储的串，试设计一个算法，找出X中第一个不在Y中出现的字符。作业四4.1已知二维数组A[m][n]采用行序维主方式存储，每个元素占k个存储单元，并且第一个元素的存储地

5、址是LOC(A[0][0])，则A[i][j]的地址是什么？4.2设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中，若按行序为主存储，则A[i][j]对应的S中的存储位置是什么？4.3一个稀疏矩阵下图所示，求对应的三元组表示，十字链表表示？4.4求下列广义表操作的结果（1）GetHead[(p,h,w)]（2）GetTail[(b,k,p,h)]（3）GetHead[((a,b),(c,d))]（4）GetTail[((a,b),(c,d))]（5）GetHead[GetTail[((a,b),(c,d))]]（6）GetTail[GetHead

6、[((a,b),(c,d))]]注：[]为函数的符号4.5利用广义表的GetHead和GetTail运算，将原子student从下列广义表中分离出来。（1）L1=(solder,teacher,student,worker,farmer)（2）L2=(solder,(teacher,student),worker,farmer)4.6画出下列广义表的头尾链表表示法和扩展线性链表表示法，并求出它的深度。（1）((()),a,((b,c),(),d),(((e))))（2）((((a),b)),(((),d),(e,f)))作业五5.1已知一棵树边的集合为{,

7、,n>,,,,,,,,,,,},画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪个是叶子结点？（3）哪个是结点g的双亲？（4）哪些是结点g的祖先？（5）哪些是结点g的孩子？（6）哪些是结点e的子孙？（7）哪些是结点e的兄弟？哪些是结点f的兄弟？（8）树的深度是多少？（9）树的度数是多少？5.2一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图5-2所示，画出该二叉树的链接表示形式？图5-2一棵二叉树的顺序存储数组t