大数据结构习题(有问题详解)

弟1幸绪

1.1有下列几种二元组衣示的数据性构，试离出它们分别对应的图形表示，(1)集合

并指出它们分别属于何料姑构.(2)慢性表

(1)A=(D,R),其中，D={a,,a2,a>,a.),R={}(3)树(4)图

(2)E=(D,R),其中，D={a,b,c,d,e|,R={(a,b),(b,c),

(c,d),(d,e))

(3)C=(D,R),其中，D={a,b,c,d,e,f,gl,R={(d,b),(d,

g),(b,a),(b,c),(g,e),(e,f)J

(4)K=(D,R),其中，D={1,2,3,4,5,6|,R=(<1,2>,<2,

3>,<2,4>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>}

1.2设n为正整数，求下列各程序段中的下划数语句的执行次数。

(1)i=1;k=0(2)for(inti=1;i<=n;i++)解：

wbile(i<=n-1)for(intj=1;j<=n;j++)(1)n-1

({c[i][j]=0;ItItIt

⑵ZZ2M

k+=10*i;for(intk=1;k<=n;k++)

t-l/-IkA

i++；

)

Ki]

}

(3>x=0;y=0;££力=£力=泮&，公产+1£i」・"("+L5+i)+L"5+i)

for(inti=1;i<=n;i++)(3)匕tii=ifzi22片।2人।2o22

for(intj=1;j<=i;j++)

=n(n+]Mn+2)

for(intk=1;k<=j;k++)6

x=x+y;

1.3卷出下列个算法的功版，并求其时网复杂度。

(1)intsum1(intn)(2)intsum2(intn)解：

({ints=0；

(1)之i!,T(n)=0(n)

intp=1,s=0;for(inti=1;i<=n；i++)

for(inti=1;i<=n；i++){intp=1;

{P*=i;s+=p;}for(intj=1;j<=i;j++)p*=j;

(2)Ji!,T⑹=02

returns；s+=r；

)}

returns；

}

1.4算法设计

有3枚硬币，其中有1枚是假的，伪币与真币亚量略有不同。如何借用一架（开,）

天平，找出伪币？以流杈图表示算法。

是

<A-B?一►C是伪币—

I否

是

<A=C?-----►-B是伪币一►

产

A是伪币

rL__________________

（结束）

上机练习题

.佟李：给出问及分析.洋汰描述、源程序攻运行成图.右建提至..

1.设a,b,c为3个整数，求其中位于中间值的空数。

(3)定低到尼站点；

while(p->next)p=p->next;

(4)定住到尾结点的前驱。p=head;

while(p->next->ncxt)p=p->next;

4.描述一下三个概念的区别：头指针，头结点，首元结点。并给头指针：是一个括针变里面存储的爰链表中首结点的地址.并以此来标识一个艳表.

于图示。头结点：附加在第一个元素结点之就的一个结点.头指针指向头结点。

首元结点：指处表中的第一个元素结点。

।;-l^iln~Ta21-l-.......-13Tl.1

5.4r无失站点单歧表，给出叫除第i个结点的算法树还。lenip1u1»»T>

template<calssT>TLinkList<T>::Delete(inti){//在单能表上制除第i个数据元素

TLinkList<T>"Delete(inti)if(head==NULL)throw“表空！”；〃空表，不能恻

elseif(i=1]{//删除第1个元素

p=Head；x=p->data;//保存敕删元素值

Head=p->next;

de1etep;

)

else{//元素定位到第a,-i

p=Head;j=1;//定住查找起始住五

while{p->next&&j<i-1}{

p=p->next;;}

if(!p->next||j>i-1);//定位失败

throw“刑僚位巽不合理”；

else{//定住成功，进行鳍点刑除

q=p->next;

x=p>data;

p->next=q->ncxt;

deleteq;

}

retrunx;//返回被酚I除元素位

)//#

6.用我材定义的乂算序表的屡本操作实现下列操作：#incIude"SqList.h“

template<calssT>template<calssT>

irtDeleteElem(SqListL.Te)intDeleteElem(SqListL.Te){//

i=L.LocateElem：e);//按依在找

if(!i)//未找到

return0;

else//找到

delete(i);//切除祓找到的元素

)

7.已加1.藏有表头结点的单犍表，且P结点既不是首元结点，【解】

也不走是结点，试写出实现下列功能的话句序列。(1)s->next=p->next；p->next=s；

(1)在P结点后插入S结点：⑵q=L；

(2)在P结点浒插入S结点;whi1e(q->next!=p)q=q->next；

(3)在表首插入S结点；s->next=p或q->next;

(4)在表尾插入S结点.q->next=s；

(3)s->next=L->next；L->next=s；

(3)q=L;

while]q->next!=NULL)q=q->next；

s->next=q->next;q->next=s；

上机蚱习题

要求：给出问K分析、算法描逑、源程序及运行般图，在级提交。

编程实现：州除单链表中仅为e的元素。

第3中栈与队列

1.铁路进行列车溺度时，常把站台设计成投式姑构的站台，如解：325641可以

右图所示。武问：若进站的六柄列车顺序如上所至，那么是否能154623不可以。

够得到325641和154623的出站序列，如来不能，说明为什么不

能；如果能，说明如何得到（印写出”进栈-或“出栈”的序列）。

2.研述以下算法的功於(栈眄元东夫型为ini)。解：(1)借助一个敷组，带收中的元泰义理。

(1)statusaIgo_1(SqStackS){

inti,n,A[255];

n=0;

whiIe(!S.StackEmpty()){n**;A[n]=S.Pop();}(2)借助栈T,将栈S中所有值为e的数据元漆剧除之。

for(i=1;i<=n;i++)S.Push(A[i]);

}

(2)statusaIgo_2(SqStackS,inte){

SqStackT;

intd;

while(!S.tackEmpty()){

d=S.Pop();

if(d!=e)T.Push(d);)

whiIe(!T.StackEmpty0)(

d=T.Pop0;

T.Push(d);}

}

3.痂答一个算法,将一个非负的十进制登敦N转换为B进制效，#includeMstack.h"

弁输出转换后的结果。当N=248D.B分别为8和16时,转换后intNumTrans(intN,intB){//十进制整致N转犊为B进制数

的结果为多少？stack<int>S;//洪立一个栈

while(N!=0){//N非零

i=N%8；//从低到雨，依次未评各位

N=N/B;

S.push(i);}//各位入栈

while(IS.StackEmpty0)(//栈不空

{i=S.pop();

If(i>9)i='A'+10-i；

cout«S.pop()：}//依次出栈,得到从高到低的输出姑果

)

}//#

4借且投，设计算法：必设一个算术表达式中包含“(二“)”括解：以字符中存储表达式,也可以边馀入边判断。

号.讨一个合法的教学表达式来说，括号“1”和3”应是相互度序扫描表达式，左括号,人枝；右括号，如果此时我空，表示多右括号.不匹

匹配的。若匹记,返回1；否到.返回0。出：如果栈不空,出栈一个左括号。扫描结束，如果我空，表示括号匹配；否则，括

号不匹比，多左括号。

intblank_match(char*exp)(用字符■串存表达式

SoStack<char>s；〃创比一个栈

char*p=exp；//工作指针p指向表达式首

while(*p!='=f)]〃不是表达式结束符

switch(p){

case'(':〃左括号，入栈

s.push(ch);break；

case')'//右括号

if(s.StackEmpty0)return0;//栈空,不匹配•.多右括号

else{s.Pop0；break；}//左括号出技

)//switch

pi;//取表达式下一个字符

)//while

if(!s.SlaukEirplyO)//表达式结表,找不空

rulurri0;〃不匹51,多左打弓

else

return1;〃匹Si

}//#

5.同汪我和队列的逻辑特点，各举一个应用实例。

6.写出下列中俄表达式的后绥表达式。(1)A-B+C-D+

(D-A+B-C+D(2)AB+D*EFAD*+/+C+

(2)(A+B)*D+E/(F+A*D)+C(3)AB&&EF!||

(3)A&&B||!(E〉F)

7.计票后端表达式：45*32+-的值。解：15

8.料下列递推过程改写为递加过程。解：voidrecurision(intj)

voidrecursion(intn){{if(j>1)

irti=n；(cour«j;

wbile(i>1){recurision(j-1)；}

cout«i;i一；J)

)

夕.・特下列遂乃过任改写为非递抬过任。解:vuid(inlAbuni)

voidtest(int&sum){{stackS;〃借助一个栈

intx；intx;

cin»x;cin»x;

if(x=0)sum=0;while(x){

else(S.push(x);

test(sum);sunH-=x;}cin»x;}

cout«sum;sum=0;

)cout«sum;

while(x=S.pop0)(

sum十二x;cout<<sum;}

)//

10.筠述以下洋法的功能（找和仄列的元素类型均为int）。解：利用我.将仄列中的元素逆直

vuida1gu(QUDUDSO)

1

StackS;〃创立一个栈

intd；

while(!0.OueueEmpty0)(

d二DeQueue(0);S.Push(d);)

while(!S.StackEmpty0){

d=S.Pop0;Q.EnOueue(d);)

}

12.仅设以敦如se[m]存放循环队列的元素，同时设变量rear解：来川找材队空与队涡利别方法。为了区分队空与队满条件,栖城一个元素空间。

和front分别作为队首、队足指针.且队首指针将向从首前一个即：rear==front.为私.空；rear==(front+1)%m,为队涌。

位置，队是指针指向队甩元素处，初始时，rear==-fornt=-1.template<caIssT>

写出这样设计的娟环队列入队、出队的«■法。voidEnOueue(TSe[],Te.intm){〃入队

if(rear+1)%m=fornt){〃队满.不能插A.

throw”队满.不能,插入！”

else{

rear=(rear+1)%m；//队尾棺针后移

se[rear]=e；//元素入队

return；

)

}//#

template<calssT>

TDnOueue(TSe[],intm){〃出从

if(rear==fornt)//队空.不能出FJ、！

Lhruw“从空，不能出队！”

DIS>D{

front=(front>1)%m;//指针后移，指向队首元素

e=se[front];//取队首元素

returne;)

)//#

上机炼习迎

要求：给出问题分析、算法描述、源叔序及运行■板图，在线提交。

1.借助我，实现单注表上的逆量运算.

第4中率

1.试问执行以下加数会产生怎样的输出站果？解：t=THESEAREBOOKS

voiddemonstrate()v=YXY

(w=XWXWXW

StrAssign(s,'THISISABOOK');

StrRep(s,StrSub(s,3,7),ESEARE');

StrAssign(t,StrConcat(s,'S'));

StrAssign(u,'XYXYXYXYXYXY');

StrAssign(v,StrSub(u,6,3));

StrAssign(w,'W');

cout«,•'t=w«t«endl;

cout«,<v=,'«V；

uuut«"u="«StiRep(u,v,w);

}//demonstrate

2,设字符串S='aabaabaabaac',P='aabaac'1)S的next与nextval值分别为9和9.

1)绐出S和P的next值和nextval值：p的next与nextval值分别为012123和002003

2)若S作主中.P作模式中.送给出KMP«■法的匹配过程。2)利用KMP集法的匹出立程：

第一船匹配：aabaabaabaac

aabaacj=6,j=6)

第二筋匹配：aabaabaabaac

(aa)baac

第三箭匹配：aabaabaabaac

(成功)：aa)baac

3.算法设计

申延均定义如下：

structSString

(

char*data;//小首址

int1en：〃*长

intStrSize：//存放数组的最大长度.

1；

(1)缗药一个再效，计算一个子串在一个字符串中出现的次数.解：intstr_count(SStringS,SStringT)(

如果不出现,则为0。inti,j,k,count=0；

intstr_count(SStringS.SStringT)for(i=0；S.data[i];i++)(

for(j=i,k=0；(S.data[j]=T.data[k]；j++,k++)

if(k==T.len-1)

count++;

}

returncount;

}

(2)统写算法，从*6中删除所有和串t相同的子串。解：

intSubString_DeIete(SString&s,SStringt)

〃从小s中科除所有与t相同的子巾，并返回删除次数

(

for(n=0,i=0;i<=s.len-t.Ion;i++)

(

for(j=0;j<t.len&&s[i*j]==t[i];;

if(j>t.len)〃找到了与t匹品的子串

{

for(k=i;k<s.len-t.Icn;ki)

s[k]-s[k*t.Icn];〃左移用，侏

b.Iwn-=l.Icn；

//被射除次数滔1}

)//for

returnn;

}//Delete_SubString

(2)编写一个再数.求申s和串t的一个景长公共子事。解：voidmaxcomstr(SString*s,SString*t)(

voidmaxcomstr(SString*s.SString*t)intindex=0,len1=0,i,j,k,Ien2;

i=0；〃作为扫描s的指针

while(i<s.len){

j=0;〃作为担描t的指针

while(j<t.len){

if(s.data[i]==t.data[j])]〃序号为i,长度为Ien2的子

串

Ien2=1；//开始计数

for(k=1；s.data[i+k]=t.data[j+k]&&

s.data[i+k]!=NULL；k++)

Ien2++；

if(Ien2>len1){//将较大长度者给index和Ien1

ir»dex=i;

Ien1=len2；

Ii

j+=Ien2；

}//if

elsejf

}//whiIe

uuui«w最长公共•了申：”

fur(i=0,i<len1;i++;)

cout«s.data[index+1];

}//#

1.已知下列字符串

a=•THIS<,f='ASAMPLE,,c=GOOD",d='NE',b=

••

9

s=StrConcat(a.StrConcat(StrSub(f.2,T,,StrConcat(b,

StrSLb(a,3,2)))),

t=StrRep(f,StrSub(f,3,6),c),

u=StrConcat(StrSub(c,3,1),d),R="IS",

v=

StrCcncat(s,StrConcat(b.StrConcat(t,StrConcat(b,u)))),

试问：s.t.v,StrLength(s),$trlndex(v,g),

StrIrdex(u.g)各是什么?

已知：s='(XYZ)**t='(X+Z)*Y'.试利用下列运算，将s转

化为t,

联接:StrConcat(&S,T)

求子市：(char*)StrSub(S,i,len)

直换：StrRep(&S,T,R)

上机练习卷

妥东：给出问速分析、算法描述、通程序及运行救图.在线提交。

审结的定义如下：

structSString

(

char*data：//小首址

intlen;〃小箕

ini3lr3iz«;〃有放敷组的最.k箕度.

）；

求：$S所含不同字符的总数和每仲字符的个数，不区分英文字

母的大小写。

第5中数组身压策衽阵

1.忸设有二维教组\八,每个元素M相邻的6个字节存钻，存储器按解:(1)6X8X6=288Byte

字节场址。已知A的起始存储位基他址)为1000,计算：(2)1000*288-6=1282;

(1)数组A的体枳(即存储量)；(3)1(XX>*HX8+4)X6=1072

(2)数组A的最后一个元素as?的第一个字行的城址；(4)1000*(7X6+4)X6=1276

(3)按行存储时，元素au的第一个字节的地址；

(4)按列存储时，元素呢的第一个字节的地址。

2.忸设按低下标优先存转抡数款组Aex,xsx,时，第一个元末的字节地址解：⑴100

是1C0.每个整数占四个字节。问下列元素的存偌地址是什么？(2)100+8X3X5X8+2X5X8+4X8+7=4500

(1)a>xo(2)a174.*

3.一个林前矩阵如图所示