数据结构与算法课后作业Word格式文档下载.docx
- 文档编号:6292281
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:10
- 大小:78.27KB
数据结构与算法课后作业Word格式文档下载.docx
《数据结构与算法课后作业Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构与算法课后作业Word格式文档下载.docx(10页珍藏版)》请在冰点文库上搜索。
1.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>
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试编写一个算法,将一个顺序表逆置,并使用最少的辅助存储空间实现。
2.2试编写一个算法,将两个元素值递减排列的顺序表合并为一个非递增的顺序表。
2.3试编写一个算法,计算带头结点的循环单链表的长度。
2.4试编写一个算法,在一个递增有序排列的单链表中插入一个新结点x,并保持有序。
2.5试编写一个算法,将一个单链表逆置。
2.6试编写一个算法,在一个双向循环链表中将结点x插入到指定结点p之前。
2.7试编写一个算法,计算一个循环队列中包含的元素个数。
2.8试编写一个算法,实现对一个以只带尾指针的循环单链表表示的队列的入队出队操作。
作业二
作业三
3.1设字符串S="good",T="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)babbabab
3.3若X和Y是两个单链表存储的串,试设计一个算法,找出X中第一个不在Y中出现的字符。
作业四
4.1已知二维数组A[m][n]采用行序维主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是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[((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已知一棵树边的集合为
{<
i,m>
i,n>
e,i>
b,e>
b,d>
a,b>
g,j>
g,k>
c,g>
c,f>
h,l>
c,h>
a
c>
},画出这棵树,并回答下列问题:
(1)哪个是根结点?
(2)哪个是叶子结点?
(3)哪个是结点g的双亲?
(4)哪些是结点g的祖先?
(5)哪些是结点g的孩子?
(6)哪些是结点e的子孙?
(7)哪些是结点e的兄弟?
哪些是结点f的兄弟?
(8)树的深度是多少?
(9)树的度数是多少?
5.2一棵二叉树的结点数据采用顺序存储结构,存储于数组t中,如图5-2所示,画出该二叉树的链接表示形式?
图5-2一棵二叉树的顺序存储数组t
5.3如图5-3所示的二叉树,回答下列问题:
(1)写出先序、中序、后序遍历的序列;
(2)画出该二叉树的中序线索二叉树;
(3)画出该二叉树对应的森林。
图5-3一棵二叉树
5.4已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树。
5.5有一份电文中共使用5个字符:
a、b、c、d、e,它们的出现频率依次为4、7、5、2、9,试画出对应的哈夫曼树,(请按左子树根结点的权小于等于右子树根结点的权的次序构造),并求出每个字符的哈夫曼编码。
5.6设给定权集w={2,3,4,7,8,9},试构造关于w的一棵哈夫曼树,并求其加权路径长度WPL。
5.11试编写一个将二叉树中每个结点的左右孩子交换的算法。
作业六
6.1图6.24所示为一有向图:
(1)求每个顶点的入度和出度;
(2)画出它的邻接矩阵;
(3)画出它的邻接链表与逆邻接链表;
(4)画出它的强连通分量。
6.2已知如图6.25所示的无向带权图:
写出它的邻接矩阵,并在此存储表示基础上用普里姆算法求其MST树,简画出其生成过程示意图。
6.3列出如图6.26所示AOV网的全部可能的拓扑序列。
6.4已知如图6.27所示的AOE网。
求
(1)每项活动的最早开始时间Ve和最迟开始时间Vl;
(2)完成此工程最少需要多少单位时间?
(3)关键活动与关键路径。
作业七
7.1分别画出在线性表(5,10,15,20,30,35,40)中进行折半查找,查找关键字10和39的过程,并分别求出ASL成功和ASL不成功的值。
7.2设一组记录的关键字按序列{4,5,7,2,1,3,6}次序进行插入生成一棵AVL树。
试描述其生成及调整成平衡二叉树的过程,并指明该步骤是属于什么调整平衡方式的基本类型。
7.3使用哈希函数:
H(key)=3key%11,并采用开放地址法处理冲突,求其下一地址的函数为:
d1=H(key)
di=(di-1+(7(key))%11(i=2,3,…)
试在0~10的散列地址空间中对关键字序列{22,41,53,46,30,13,01}构造哈希表,并求出等概率情况下查找成功的平均查找长度。
7.4已知序列{17,18,60,40,7,32,73,65,85},请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
7.5已知序列{503,87,512,61,908,896,257,653,465},请给出采用快速排序法对该序列作升序排序时的每一趟的结果。
7.6已知序列{503,87,512,61,908,170,897,275,653,462},请给出采用堆排序法对该序列作升序排序时的每一趟的结果。
7.7已知序列{10,15,4,3,6,12,1,9,18,8},请给出采用希尔排序法对该序列作升序排序时的每一趟结果。
7.8试说明归并排序的基本过程,并给出对关键字序列{47,33,61,82,72,11,25,57}进行两路归并排序的示意。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 课后 作业