2023年数据结构与算法离线作业答案

浙江大学远程教育学院

《数据结构与算法》课程离线作业

姓名：陈翠学号：7

年级：2023秋学习中心：金华学习中心

一、填空题：(【序号，章，节】。。。。。。)

[1,1,2]线性结构中元素之间存在一对一关系，树形结构中元素之间存在

_一对多—关系，图形结构中元素之间存在—多对多—关系。

[2,1,2]为了最快地存取数据元素，物理结构宜采用顺序存储

—结构。

[3,1,2]存储结构可根据数据元素在机器中的位置是否一定连续分为—顺序存储结构

—，_链式存储结构—o

[4,1,3】度量算法效率可通过_时间复杂度—来进行。

[5,1,31设n为正整数，下面程序段中前置以记号@的语句的频度是—n(n+l)/2

______o

for(i=0；i<n;i++){

for(j=0;j<n;j++)

if(i+j==n-l)

a[i]Ej]=0;

[6,1,3]设n为正整数，试拟定下列各程序段中前置以记号@的语句的频度：

(1)i=1;k=0;

while(i<=n-l){

i++；

@k+=l0*i;〃语句的频度是n-1o

)

(2)k=0;

for(i=l；i<=n;i++){

for(j=i；j<=n;j++)

@k++;//语句的频度是n(n+1)/2

[7,3,2]线性表(ai,a2,...,a0)有两种存储结构：顺序存储结构和链式存储结构,请就这

两种存储结构完毕下列填充：顺序_存储密度较大;一顺序存储运用率较

高；顺序可以随机存取；―链式不可以随机存取;一链式插入

和删除操作比较方便。

[8,3,2]从一个长度为n的顺序表中删除第i个元素(IgiSn)时，需向前移动

11-1_个元素O

[9,3,2]带头结点的单链表Head为空的条件是—Head->next=NULL

[10,3,2】在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所

指结点，应执行s->next=__p->next-：和p->next=s的操作

o

[11,3,2】在一个单链表中删除p所指结点时，应执行以下操作：

q=p->next;

p->data=p->next->data;

p->next=p—>next->next

free(q);

[12,3,2】带头结点的单循环链表Head的判空条件是_Head->next=Head

；不带头结点的单循环链表的判空条件是一Head==NULL-。

[13,3,2]已知L是带表头结点的非空单链表，且P结点既然不首元结点，也不是尾元结

点，试从下列提供的答案中选择合适的语句序列。

a.删除P结点的直接前驱结点的语句序列是_1012811414—。

b.册U除结点P的语句序列是_10127314。

c.删除尾元结点的语句序列是911314o

(1)P=P->next;

(2)P->next二P；

(3)P->next=P->next->next；

(4)P=P—>next—>next;

(5)whi1e(P!=NULL)P=P->next;

(6)while(Q->next!=NULL){P=Q;Q=Q->next};

⑺whi1e(P->next!=Q)P=P->next;

(8)whi1e(P—>next—>next!=Q)P=P—>next;

(9)while(P->next->next!=NULL)P=P->next；

(10)Q=P；

(11)Q=P->next;

(12)P=L;

(13)L=L->next;

(14)free(Q);

[14,3,3]对一个栈，给定输入的顺序是A、B、C,则所有不也许的输出序列有

—不也许得到的输出序列有CABo

[15,3,31.在栈顶指针为HS的链栈中，鉴定栈空的条件是_head—>next==NULL_。

[16,3,31下列程序把十进制数转换为十六进制数，请填写合适的语句成分。

voidconversionl0_16()

{InitStack(&s);

scanf("%d”,&N);

whi1e(N){

①Push(s,N%16);

N=N/16；

)

while(!StackEmpty(s)){

②Pop(s,e)；

if(e<=9)printf("％d”，e);

elseprintf("％c”,e—10+'A')；

}

}/*conversion*/

[17,3,4]若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front=3

。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_2

和4_o

[18,3,4]堆栈和队列都是线性表，堆栈是后进先出______的线性表，而队

列是—先进先出的线性表。

[19,3,4]若用一个大小为6个元素的数组来实现循环队列,且当前rear=0和front

=3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是

2_和_4o

[20,4,2]已知一棵树边的集合是{<a,d>,Vd,c>,<d,j>,<e,a>,<f,g>,<d,b>,

<g,h>,<g,i>,<e,f>}o那么根结点是_e,结点b的双亲是d,结点a的

子孙有_bcdj—,树的深度是4,树的度是_3_,结点g在树的第—3—层

[21,4,3]从概念上讲，树与二叉树是二种不同的数据结构，将树转化为二叉树的基本

的目的是一树可采用二叉树的存储结构并运用二叉树的已有算法解决树的有关问题—o

[22,4,3]满三叉树的第i层的结点个数为—3i-1，深度为h时该树中共

有3-lh结点。

[23,4,3】已知一棵完全二叉树有56个叶子结点，从上到下、从左到右对它的结点进行

编号，根结点为1号。则该完全二叉树总共结点有111个;有—7—层;

第91号结点的双亲结点是—45—号；第63号结点的左孩子结点是32

号。

[24,4,3】下列表达的图中，共有5个是树；有3个是二叉树；有

_2个是完全二叉树。

[25,4,4]n个结点的二叉排序树的最大深度是_n—，最小深度为」1。g2n]+1

[26,4,3]假如某二叉树的后序遍历序列是ABCDEFGHI,中序遍历序列是ACBIDFE

HG,则其先序遍历序列的第一个字母是一I_，最后一个字母是_G_。

[27,4,3]下列二叉树的中序遍历序列是_DBNGOAEC_;后序遍历序列是DN

IGBECAo

[28,5,4]设HASH表的大小为n(n=10),HASH函数为h(x)=x%7,假

如二次探测再散列方法Hi=(H(key)+di)mod10(di=l2,22,32,...,)解决冲突,

在HASH表中依次插入关键字｛1,14,55,20,84,27｝以后，关键字1、20和27所在

地址的下标分别是_1_、_7_和5。插入上述6个元素的平均比较次数是2

[29,6,3]设无权图G的邻接矩阵为A,若(vi,vj)属于图G的边集合，则相应元

素A[i][jl等于1,22、设无向图G的邻接矩阵为A,若A[i][j]等于0,则A[j][i]

等于0。

[30,6,3]若一个图用邻接矩阵表达，则删除从第i个顶点出发的所有边的方法是

矩阵第i行所有置为零—0

1

[31,6,2]设一个图

G={V,{A}},V={a,b,c,d,e,f},A={<a,b>,<b,e>,<a,e>,<c,a>,<e,d〉,<d,

f>,<f,c>}□那么顶点e的入度是2；出度是1；通过顶点f

的简朴回路有2条:就连通性而言.该图是强连通—图；它的强连通分量有

」_个:其生成树也许的最大深度是5。

[32,7,1]排序过程一般需通过两个基本操作，它们是—比较—和—移动

[33,7,2]在对一组关键字是(54,38,96,45,15,72,60,23,83)的记录进行直接插入排序

时，当把第七个记录(关键字是60)插入到有序表时，为寻找插入位置需比较三次。

[34,7,4]插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序、和基

数排序方法中，不稳定的排序方法有_希尔排序_、_快速排序_、_堆排序

二、综合题(选自教材《数据结构》各章习题，采用word文献格式上传)

[1,1,31试分析下面一段代码的时间复杂度：

if(A>B)

(

for(i=0；i<N；i++)

for(j=N*N;j>i;j--)

A+=B;//A=A+B

)

eIse{

for(i=0；i<N*2；i++)

for(j=N*2;j>i;j--)

A+=B;//A=A+B

)

Answer:

ifA>B为真，则for语句的外循环N次，内循环为N(N-l)次，因此时间复杂

度为0(N*N(N-l)),也就是N的三次方。

ifA>B为假，则f。r语句的外循环2N次，内循环为N次，因此时间复杂度为

0(2N*N)，也就是N的平方。

[2,1,3]测试例1.3中秦九韶算法与直接法的效率差别。令/(x)=l+Ztx'/3+

算/(L1)的值。运用clock()函数得到两种算法在同一机器上的运营时间。

Answer：

f(1.1)=137797.40625

[3,1,31试分析最大子列和算法1.3的空间复杂度。

[4,1,31试给出判断N是否为质数的0(灰)的算法。

Answer：

intsushu(intN)A{Mnti;

intflag=1；^if(N==1)returnfalse;//1既不是合数也不是质数

if(N==2)returntrue;

for(i=2；i<=sqrt(N);i++)

(

if(N%i==0)A{Aflag=0

break;

4}

returnflag;

[5,2,2]请编写程序，输入整数n和a,输出S=a+aa+aaa+…+aa...a(n个a)

的结果。

Answer：

#inc1ude"stdio.h"

intmain()J»{

inta,b,n,i,s=0;

scanf("%d%d",&a,&n)；Ab=a;Afor(i=1;i<=n;i++)

{4s+=a;

a=a*10+b;A}

printf("%d\n",s);A}

[6,2,3】请编写递归函数，输出123..n的全排列(n小于10),并观测n逐步增

大时程序的运营时间。

Answer:

#include<stdio.h>

#defineswap(a,b)

intt=a;Wa=b;\Ab=)

AVOidpermutation(int*a,intb,inte)

{ginti*if(b==e)

(

for(i=0;i<e;++i)

{△printf("%d",a[i]);»^}

Aprintf("\n")；A}

else

(

4or(i=b；i<e;++i)

{3swap(a[b],a[i])；^permutation(a,b+1,

e)。swap(a[b],a[i])；

0卜}A

intmain(void){

inta[4]={1,2,3,4};Apermutation(a,0,4);

»/*system("pause");*/丛return0;

)

[7,3,21给定一个顺序存储的线性表L=(%,a2l%),请设计一个算法

删除所有值大于min并且小于max的元素。

#include<stdio.h>A#inc1ude<stdlib.h>

#include<math.h>AtypedefintElemType;

typedefstractLNod{ElemTypedata;/*数

据子域*/AstructLNode*next;/*指针子域

小)LNode;I*结点结构类型*/

LNode*L;AA/*函数声明*/ALNOde*creat_L()；svoiddelete_L(LNode*L,in

ti);〃返回值格式变为空

/*建立线性链表*/

LNode*creat_L()A»LNode*h,*p,*s；ElemTypex；

h=(LNode*)malloc(sizeof(LNode));/*分派头结点*/

h->next=NULL;

P=h;Aprintf("输入一串数字(以一1结束):\ndata=")：△scanf

("%d"，&x)；/*输入第一个数据元素*/△

while(x!=-1)/*输入-1,

结束循环*/

(

s=(LNode*)malloc(sizeof(LNode));/*分派新结点办

s->data=x;s->next=NULL;*p->next=s；p=s;

printf("data=");△scanf("%d",&x);

r输入下一个数据*/

}Areturn(h)；A}/*creat_L*/AA/*输出单链表中的数据元素*/AV0id

out_L(LNode*L)

{ALNode*p；Ap=L->next；Aprintf("\n数据是：")*while(p!=NU

LL)A{

printf("%5d",p->data);Ap=p—>next；A}△}/*out—Ii

nk*M*删除大于x小于y的值*/

voiddelete_L(LNode*L,inta,intb)-*{

LNode*p,*q；Ap=L；Aq=p；

p=p—>next；Aif(p==NULL)printf("ERROR:链表为空")；

while(p!=NULL)A{

Aif((p—>data>a)&&(p->data<b))A{q->next=p->n

ext；Afree(p);

p=q->next；

△)

else

{q=p；

p=p->next;

}

卜}/*delete，*/4voidmain()A{

inta,b;AL=creat_L();out—L(L);

printf("\n\n请输入你要删除的元素的范围min和max:\n");劣scanf("%d%d

",&a,&b);

delete_L(L,a,b);out—L(L);

Printf("\n")；呼/*main7

[8,3,2]给定一个顺序存储的线性表L=(a,,a2r*),请设计一个算法查

找该线性表中最长递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子

序列为(3,4,6,8)o

#include<iostream>

#include<a1gorithm>

usingnamespacestd；

#defineMAXN1003

intA[MAXN];

intdp[MAXN]；

//动态规划思想O(n-2)

intmain()

{

intn,i,j,k；

cin>>n;

for(i=1;i<=n;i++)

cin>>A[i];

dp[1]=1;

//有n个阶段

for(i=2;i<=n；i++)

dp[i]1；//每个阶段只有1个状态

//每个状态有i种决策，以得出以元素i结尾的最长递归子序列的长度

for(j=i-l;j>=0;j--)

{

if(A[i]>A[j])

dp[i]=max(dp[i],dp[j]+l);

}

}

intmaximum=dp[1];

for(i=2;i<=n;i++)

maximum=max(maximum,dp[i])；

cout<<maximum;

[9,3,3]假如有1、2、3、4、5按顺序入栈，不同的堆栈操作(pop,push)顺

序可得到不同的堆栈输出序列。请问共有多少种不同的输出序列？为什么？

Answer：

共有34种不同的输出序列

12345123541243512543132451325414325154322

13452143521543231452315423415234512354124315

243512453125431

3214532154324153245132541342153425134521354

214321543251435214532154321

[10,3,2]请编写程序将中缀表达式转换为后缀表达式。

#inc1ude<iostream>

#include<stack>a#include<string>

usingnamesPacestd;

intprior(charop)a{

if(op==z+'||op==,J)

return1;

if(op=='*'||op==7')

return2;

return0;4}

stringmidd1etolast(stringmiddle)

{^stack<char>op；

stringans;

for(inti=0;i<middIe.size();i++)X

charc=middle[i];

if(c>='0,&&c<='9'>{

ans.append(lzc)；

else

{

if(c=='C)aop.push('C);

eIse

if(c==')/)

while(op.top()1=，(')a{

ans.append(l,op.top());

op.pop();a}aop.pop();

)

eIse

{&if(op.empty())&{

op.push(c)；^}

else

{

if(prior(c)>prior(op.top()))

op.push(c)；4else{awhi1e(!op.empty()&&prior(c)<=p

rior(op.top()))

{&ans.append(1,op.top())；

op.pop()；

}&op.push(c)；a}&}

b)

)

}4while(!op.empty())

(

ans.append(l,op.top());^op.pop()；4}

returnans;而}

intmain()

{

stringmdata,res2cin>>mdata;

res=midd1eto1ast(mdata);afor(inti=0;i<res.size();i++)

{而if(i==0)

cout<<res[i]；j5»e1se

cout<<''<<res[i]2}4cout<<endl;j>return0;

)

[11,4,31设二叉树的存储结构如下：

的指针值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data为数据域。

（1）画出二叉树的逻辑结构。

（2）写出该树的前序、中序和后序遍历的序列。

Answer

(1)A

BC

DFGI

EH

(2)前序:ABDFECGHI

中序:DBEFAGHCI

后序:DEFBHGICA

[12,4,4】可以生成如下二叉排序树的关键字的初始排列有几种？请写出其中的任

意4个。

答：可以生成如上二叉排序树的关键字的初始排列有3()种

任写4个序列如下：

(5,7,6,4,2,1,3)

(5,7,6,4,2,3,1)

(5,4,2,3,7,6,1)

(5,4,2,1,7,6,3)

[13,4,5]给定关键字序列(11、7、16、4、22、13、5),请回答:

(1)画出依次插入到一棵空的二叉排序树后的最终二叉树(6分)；

(2)画出依次把给定序列关键字插入一棵空的平衡二叉树后的结果(4分)；

ANSWER

11

716

422135

[14,4,6]假设一个文本使用的字符集为{a,b,c,d,e,f,g},字符的哈夫曼编码依

次为{0110,10,110,111,00,0111,010}o

(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应的字符；

(2)若这些字符在文本中出现的频率分别为:{3,35,13,15,20,5,9},求该哈夫

曼树的带权途径长度。

ANSWER：

74

4232

23191220

/\/\

158910

/\

87

/\

35

编码:A(010)B(00000)C(00001)D(001)E(10)F(11)G(0001)H(011)

带权途径长度值为：(3+5)*5+7*4+(8+9+10)*3+(12+20)*2=213

[15,5,3】用公式5.6计算一下你的身份证号码的散列值是多少。

Answer：924300

[16,5,4]设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},

散列函数为：H(key)=key%17,采用平方探测方法解决冲突。试在。至U18的

散列地址空间中对该关键字序列构造散列表。

ANSWER:

一方面将各个数除以17取余数：(627,1,2,7,7,6)可见20,85与46冲突，58与71冲突。

将7+1再对13取余，直到无冲突，类似的6+1对13取余，最后可得H(71)=6;H(28)=2;

H(46)=7；H(14)=1；H(2)=3;H(20)=8；H(85)=9；H(58)=10；哈希表存储结构:

0123456789181428。

2。7146208558

平均查找长度=(1x4+2x2+3x1+4x1)/8=15/8

[17,5,4】将关键字序列(7,8,30,11,18,9,14)散列存储到散列列表中，散歹I」

表的存储空间是一个下标从0开始的一个一维数组。解决冲突采用线性探测法，散列函

数为：H(key)=(keyx3)modTableSize,规定装入因子为0.7。

Answer:

关键字78301118914

散列地址1403472

线性探测法构建列表的过程

0123456789

插入77

插入88

插入3030

插入1111

插入185d1

=1

插入99

插入1414

[18,6,3]已知一个无向图的顶点集为{Vo,Vi,...,V7},其邻接矩阵如下所示:

r

Vo01011000

Vi101010)0

V201000100

V310000010

b10J

v400010

v500100000

v600011001

v700000001

(1)画出该图的图形；

(2)给出从Vo出发的深度优先遍历序和广度优先遍历序。

[19,6,3]已知有向图如右图所示，请给出该图的

15

(1)每个顶点的入度和出度;

(2)邻接矩阵；

(3)邻接表；

(4)逆邻接表；

(5)各个强连通分量。

答：(1)各顶点的入/出度如下：顶点1:3/0;顶点2:2/2；

顶点31/2;顶点41/2；顶点5:2/1；顶点6:2/3。

(2)邻接矩阵如下:

123456

10()0000

100100

3010001

4001011

5100()00

6110010

(3)邻接表如下:

1____

2—A1三4

3I->16I—2

4I・I3I1I5I»Ifi

5I-1

6I->11I-2I>IS

(4)逆邻接表如下：

1I・I2I1•I51-^；；,I6

2I~>13I-»l6

3I-4

4I-2

5II4II6

6I，hI•I4

(5)故意向3个强连通分量

错误！

错误！错误！磐!/

错误！

\

Xo\ac（O，3）

[20,6,3]试运用Dijkstr,a算法求下图在从顶点A到其它顶点的最短距离及相应的

乱

3

途径,写出计算过程中各步状态。

Answer:

1c:22Ac：2f：6

3c:2f:6e:10

4c：2f：6e:10d:11

5c:2f:6e:10d:11g：146c：2f:6e:10d:11g:14b:15

[21,6,31给出如下图所示的具有7个结点的网G。请：

（1）画出该网的邻接矩阵；

（2）采用Prim算法，从4号结点开始，给出该网的最小生成树（画出Prim算法

的执行过程及最小生成树的生成示意图）。

[22,7,4]给定数组｛48,25,6,90,17,84,62,48,27,96,49,72,

17）,请分别用简朴选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中

每一步操作后的结果,分析各自比较和互换的次数，以及排序结果是否稳定。

Answer

简朴选择排序过程如下:

环节4825690178462482796497217

16482590178462482796497217

2617482908462482796497217

5

3611748259084624827964972

7

461717254898462482794972

06

56171725274890846248964972

66171725274890846248964972

7617172527484890846964972

2

8617172527484849908469672

2

96171725274848496290849672

1