2025年高效编程挑战数据结构与算法实战解析

浙江大学远程教育学院

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

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

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

一对多关系,图形构造中元素之间存在多对多关系。

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

[3,1,2】存储构造可根据数据元素在机器中的位置与否一定持续分为次序存储构造

，链式存储构造°

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

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

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

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

if(i+j==n-1)

@a[iJ|j]=O;

(

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

(l)i=l;k=0;

while(i<=n-l){

i++;

@k+=l()*i；//语句的频度是1-L。

(

⑵k=0;

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

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

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

}

[7,3,2]线性表（ai,az,a"有两种存储构造：次序存储构造和链式存储构造，

请就这两种存储构造完毕下列填充：一次序存储密度较大;存储运用率较高；.

次序一可以随机存取；链式一不可以随机存取;插入和删除操作比较以便。

[8,3,2]从一•种长度为n的次序表中删除第i个元素（l<i<n）时，需向前移动

ivi个元素o

[9,3,2】带头结点的单链表Head为空的条件是Hed->nct=NULL一八

[10,3,2】在一种单链表中p所指结点（p所指不是最终结点）之后插入一种由指针s所

指结点，应执行s->ncxt=p->nextp->ncxt=§的操作。

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

q=p->ncxt;

p->data=p->next->da（a;

D->next二D->next->next;

free（q）;

[12,3,2]带头结点的单循环链表Head的判空条件是Head・>next==Head—；不带

头结点的单循环链表的判空条件是Head=NULL0

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

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

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

b.删除结点P的语句序列是10127314—。

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

(1)P=P->next;

(2)P->next=P;

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

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

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

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

(7)while(P->next!=Q)P=P->next;

(8)while(P->next->next!=Q)P=P->next;

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

(10)Q=P;

(11)Q=P->next;

(I2)P=L;

(13)L=L->next;

(14)free(Q);

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

不也许得到的输出序列有CAB。

[15,3,3】.在栈顶指针为HS的链栈中，鉴定栈空的条件是一head〉next==NULL。

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

voidconversion10_16()

{InitStack(&s);

scanf("％d”,&N);

\vhilc(N){

Push(s,N%16):

N=N/16;

1

while(!StackEmpty(s)){

_P()D(s,e)_______;

if(c<=9)printfCt%d,；c);

elseprimR"%c'',e-10+'A，)；

I

}/*conversion*/

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

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

4。

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

先进先出的线性表。

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

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

2和4。

[20,4,2]已知一棵树边的集合是{va,d>,<d,c>,<d,j>,ve,a>,<f,g>,<d,b>,<g,h>,vg,i>,<e,f>}

o那么根结点是e,结点b的双亲是一d,结点a的子孙有bedi,树的

深度是一4,树的度是-3,结点。在树的第3层。

[21,4,3]从概念上讲，树与二义树是二种不一样的数据构造，将树转化为二义树的

基本的目的是树可采用二叉树的存储构造并运用二叉树的已经有算法处理树的有

关问题。

[22,4,3]满三义树的第i层的结点个数为于」，深度为h时该树中共有3卜・1结

点。

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

行编号，根结点为1号。则该完全二叉树总共结点有_1H_个；有2层;第91

号结点的双亲结点是45号:第63号结点的左孩子结点是契号。

[24,4,3]下列表达的图中，共有」_个是树；有3个是二叉树:有—个是

完全二叉树。

[25,4,4】n个结点的二叉排序树的最大深度是3,最小深度为II。gn]+l。

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

,则其先序遍历序列的第一种字母是」,最终一种字母是G。

[27,4,3]下列二叉树的中序遍历序列是DBNGOAEC:后序遍历序列是

DNIGBECAo

A

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

散列措施Hi=(H(key)+di)mod10(di=lU,32,...,)处理冲突,在HASH表中依次插入关

键字{1,14,55,20.84,27}后来，关键字1、20和27所在地址的下标分别是1、7

和5°插入上述6个元素的平均比较次数是

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

等于1,22、设无向图G的邻接矩阵为A,若等于0,则等于

0O

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

矩阵第i行所有置为零。

[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>)0那么顶点e的

入度是2；出度是1；通过顶点f的简朴回路有2条;就连通

性而言，该图是强连通图:它的强连通分量有1个:其生成树也许的最大

深度是5o

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

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

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

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

排序措施中，不稳定的排序措施有希尔排序.迅速排序、堆排序,

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

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

if(A>B){

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

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

A+=R;

)

else{

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

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

A+=B;

}

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

为O(N*N(N-1)),也就是N的三次方。

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

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

[2,1,3]测试例1.3中秦九韶算法与直接法的效率差异。令/a)=l+Z=f7i,计

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

1(1.1)=137797.40625

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

若记整体时间复杂度为T(N)o通过递归实现“分”的复杂度为2T(N/2)。求跨分界

线的最大子列和有两个简朴的for循环，所用环节一共不超过N,可以在。(N)时间

完毕。其他环节都只需要常数0(1)

T(1)=0(1);

T(N)=2T(N/2)+0(N)

=2[2T((N/2)/2)+0(N/2)]+0(N)=22T(N/22)+20(N)

=,,,,=2kT(N/2k)+k0(N)

不停对分至I」N/2k=1,即2k=N,可得至ijT(N)=NT(l)+logN-0(N)=0(NlogN)

[4,1,3】试给出判断N与否为质数的0（屈）的算法。

^include<stdio.h>

^include<math.h>

intis_prime(intn)

inti;

if(n!=2&&n%2==0||n==l)

{return0;}

if(n==2){return1;};

for(i=3;i<=sqrt((double)n);i+=2)

{if(n%i==0)

{return0;}

3t■

)

At■>

return1;“iet(・，i•;？”•二，•♦»||»-1>

rrtwro•;

]

“(・tft

voidmain()

retera1;

{

a«iM)

intnum,result;

printf("Inputthenum:"

.......cnflariflX:rt.Via37•…修

scanf("*d”,&num);Linkiaq...

-•errordJ.■

result=is_prime(num);

if(result)ZU3CB3济理而XT万彩胸EWT“j

printf(',%disaprime\n",num);

else

printf(n%disnotaprime\nu,num);

[5,2,2】请编写程序，输入整数n和a,输出S=a+aa+aaa+…+aa...a（n个a）的成

果。

#include<stdio.h>

0»tt<D・«£.帆0・A8IJkD.OMIWbHi

intmain()(CK宙2JH

[iGlobehT•囚Imember;-三］a・出曲，，M9

TiiKbide<5tdio.h>

{iatMin(>

•破tictomg

int".b.it.£.、・•；

inta,b,n,i,s=0;Print1(•清|fi/,U舒MQ•:；

3Mstd'.&n.M);

printf("请输入整数n和a:\n")9d

uHj“n；

scanf(%d%d,&n,&a);printf<**S>d«da*aaa«・・・・a・・♦(哈㈤；

b=a;

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

(

s+=a;

Conflqurat

a=a*10+b;LiMtlaf...

rt.exe-9errord),•

)

printf(nS=a+aa+aaa+,,,+aa,,a(n个a)=%d\n"，s);

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

渐增大时程序的运行时间。

^include<stdio.h>

^include<time.h>

voidpailie(int*data,intnzintcurr)

(

inti;

if(curr==n-l)

|

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

uM

printf(%dzdata[i]);

printf("\nu);

)

else

|

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

intt;

t=data[curr]/data[curr]=data[i],data[i]=t;

pailie(data,n,curr+1);

t=data[curr],data[curr]=data(ij,data[i]=t;

)

}

}

intmain()

{

clock_tend;

clock_tstart=clock();

intn=0;

inti=0;

intas[10];

scanf(*'%<i"r&n);

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

(

as[i]=i+1;

)

pailie(as,n,0);

end=clock();

printf("Thetimewas:%d\nn,(end-start)/CLK_TCK);

return0;

)

[7,3,2]给定一种次序存储的线性表L=(〃一出，…，%),请设计一种算法

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

Hnclude<stdio.h>

|include<stdlib.h>

ftinclude<math.h>

typedefintElemType;

typedefstructLNode

(

ElemTypedata;

structLNode*next;

}LNode;

LNode*L；

/*函数申明*/

LNode*creat_L();

voiddelete_L(LNode*L,inti);//返回值格式变为空

产简历线性链表*/

LNode*cr©at_L()

(

LNode*h,*p,*s;ElemTypex;

h=(LNode*)malloc(sizeof(LNode));

h->next=NULL;

P=h;

printf("输入一串数字(以T结束)：、ndata=");

n

scanf("%dz&x);

while(x!=-l)

|

s=(LNode*)malloc(sizeof(LNode));

s->data=x;s->next=NULL;

p->next=s;p=s;

printf(Hdata=")；

un

scanf(%dz&x);

)

return(h);

)

/*输出单链表中的数据元素*/

voidout_L(LNode*L)

(

LNode*p;

p=L->next;

printf(n\n数据是：”)；

while(p!=NULL)

printf("%5d",p->data);

p=p->next;

}

}

/*输出不小于x不不小于y的值*/

voiddelete_L(LNode*L,inta,intb)

(

LNode*p,*q;

P=L;

q=p；

p=p->next;

if(p==NULL)printf("ERROR:链接表为空”);

while(p!=NULL)

(

if((p->data>a)&&(p->data<b))

(

q->next=p->next;

free(p);

p=q->next;

)

else

(

q=p；

p=p->next;

)

}

}

voidmain()

(

inta,b;

L=creatL();outL(L);

printf(H\n\n请输入你要删除的元素的范围min和max:\nM);

scanf(H%d%dn,&a,&b);

delete_L(L,a,b);out_L(L);

printf(n\n");

}

[8,3,2]给定一种次序存储的线性表L=(q,alf*),请设计一种算法查

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

列为(3,4,6,8)。

4include<iostream>

^include<algorithm>

usingnamespacestd;

#defineMAXN1003

intA[MAXN];

intdp[MAXN];

intmain()

(

intn,i,j,k;

cin>>n;

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

cin»A[i];

dp[l]=1;

for(i-2;i<—n;iii)

(

dp[i]=1;

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

(

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

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

)

}

intmaximum=dp[1];

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

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

cout<<maximum;

)

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

次序可得到不一样的堆栈输出序列。请问共有多少种不一样的输出序列？为何？

共有34种不一样的输出序列

123451235412435125431324513254143251543221345

214352154323145231542341523451235412431524351

245312543132145321543245132541342153425134521

354214321543251435214532154321

[10,3,2】请编写程序将中缀体现式转换为后缀体现式。

^include<iostream>

令include<stack>

令include<string>

usingnamespacestd;

intprior(charop)

(

if(op=='+'||op=='_,)

return1;

if(op==**1IIop==*/*)

return2;

return0;

}

stringmiddletolast(stringmiddle)

(

stack<char>op;

stringans;

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

|

charc=middle[i];

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

{ans.append(1,c);}

else

if(c==,(*)

op.push('(');

else

{

if(c==,)•)

(

while(op.top()!='(')

{

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

op.pop();

)

op•pop();

}

else

(

if(op.empty())

(

op.push(c);

}

else

(

if{prior(c)>prior(op.topO))

op.push(c);

else

(

while(lop.empty()&&prior(c)<=prior(op.top()))

(

ans.append(1zop.top());

op.pop();

}

op.push(c);

}

}

}

)

)

while(!op.empty())

(

ans.append(1zop.top());

op.pop();

)

returnans;

}

intmain()

{

stringmdata,res;

cin>>mdata;

res-micldletolast(mdata);

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

{

if(i==0)

cout<<res[i];

else

cout<<**<<res[i];

)

cout«endl;

return0;

)

}

[11，4,3]设二叉树的存储构造如下：

12345678910

Lchild00237580101

dataJHFDBACEGI

Rchild0009400000

其中根结点的指针值为6,Lchild,Rchild分别为结点的左、右孩子指针域，data为

数据域。

(1)画出二叉树的逻辑构造。

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

前序遍历:ABCEDFHGIJ

中序遍历：ECBHFDJIGA

后续遍历：ECHFJIGDBA

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

4个。

可以生成如上二叉排序树的关键字的初始排列有30种

任写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分）;

716716

22

（2）画出依次把给定序列关键字插入一棵空的平衡二叉树后的成果（4分）;

11

716

422135

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

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

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

74

/\

4232

/\/\

23191220

/\/\

158910

/\

87

/\

35

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

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

带权途径长度。

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

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

924300

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

74),散列函数为：H(key)=key%17,采用平方探测措施处理冲突。试在0到

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

首先将各个数除以17取余数：(6,2,7,1,2,7,7,6)可见20,85与46冲突，58与

71冲突。将7+1再对13取余，直到无冲突，类似的6+1对13取余，最终可得

H(71)=6;H(28)=2;H(14)=l;H(2)=3;H(20)=8;H(85=9;H(58)=10)；哈希表存

储构造：

012345678910

142827146208558

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

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

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

列函数为：H(key)=(key><3)modTableSize>规定装入因子为0.7。

关键字78301118914

放列地址1403472

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

0123456789

插入77

插入88

插入3030

插入1111

插入185dl=l

插入97

插入1414

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

Vo101011000、

ViI0101000

V201000100

v310000010

V411000010

V500100000

V600011001

V700000001

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

深度优先序列V0,V1,V2,V5,V4,V6,V3,V7

广.度优先序歹UV0V1V3V4V2V6V5V7

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

（1）每个顶点的入度和出度；j'.一/'

各顶点的入/出度如下：顶点1:3/0;顶点2:2⑵

顶点3:1/2;顶点4:1/2;顶点5:2/1;顶点6:2/3

（2）邻接矩阵;

123456

1000000

100100

3010001

4001011

5100000

611()010

（3）邻接表;

iQ

2►I►4

3►6►2

4——>3——>5——>6

5——►1

6——►1—►2一>5

(4)逆邻接表:

1—►2-■>5—►6

2―►3*6

3>4

4——>2

5—►46

（5）。各个强连。通分量。

[20,6»3]试运用Dijkstra算法在从顶点A到其他顶点的最短距离及对应的

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

最短途径

A到B：A-B,大小为15

A到C:A-C,大小为2

A到D:A-D,大小为12

A至IJE:A—C—E.大小为10

A到F:A-*C-*F,大小为6

A至IJG:A-*D-*G,大小为15

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

(I)画出该网的邻接矩阵;

012346

00130005

11004006

23000403

30400072

40040015

50007102

65632520

ky

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

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

分别用简朴选择排序、直接插入排序和冒泡排序分别进行排序，写出排序过程中每一步

操作后的成果，分析各自比较和互换的次数，以及排序成果与否稳定。

简朴选择排序过程如下:

环节4825690178462482793497217

16482590178462482796497217

26174825908462482796497217

36171748259084624827964972

46171725489084624827964972

56171725274890846248964972

e6171825274890846248964972

7