数据结构(第3版)习题答案.doc

十二五普通高等教育国家级本科规划教材第 1 章绪论高等学校精品资源共享课程、1什么就是数据结构？【答】:数据结构就是指按一定得逻辑结构组成得一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合.1、数据结构涉及哪几个方面?【答】：数据结构涉及三个方面得内容，即数据得逻辑结构、数据得存储结构与数据得运算集合.、3 两个数据结构得逻辑结构与存储结构都相同,但就是它们得运算集合中有一个运算得定义不一样，它们就是否可以认作就是同一个数据结构？为什么？【答】:不能，运算集合就是数据结构得重要组成部分，不同得运算集合所确定得数据结构就是不一样得,例如,栈与队列它们得逻辑结构与存储结构可以相同，但由于它们得运算集合不一样，所以它们就是两种不同得数据结构。1、4线性结构得特点就是什么?非线性结构得特点就是什么？【答】：线性结构元素之间得关系就是一对一得,在线性结构中只有一个开始结点与一个终端结点,其她得每一个结点有且仅有一个前驱与一个后继结点。而非线性结构则没有这个特点，元素之间得关系可以就是一对多得或多对多得.、5数据结构得存储方式有哪几种？【答】:数据结构得存储方式有顺序存储、链式存储、散列存储与索引存储等四种方式.1、6 算法有哪些特点？它与程序得主要区别就是什么？【答】:算法具有(1)有穷性(2)确定性（3）0 个或多个输入（） 个或多个输出（5)可行性等特征。程序就是算法得一种描述方式,通过程序可以在计算机上实现算法。1、7 抽象数据类型得就是什么?它有什么特点？【答】：抽象数据类型就是数据类型得进一步抽象,就是大家熟知得基本数据类型得延伸与发展.抽象数据类型就是与表示无关得数据类型，就是一个数据模型及定义在该模型上得一组运算。对一个抽象数据类型进行定义时,必须给出它得名字及各运算得运算符名，即函数名,并且规定这些函数得参数性质。一旦定义了一个抽象数据类型及具体实现,程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型得设计者根据这些描述给出操作得具体实现，抽象数据类型得使用者依据这些描述使用抽象数据类型。、 算法得时间复杂度指得就是什么？如何表示？【答】：算法执行时间得度量不就是采用算法执行得绝对时间来计算得，因为一个算法在不同得机器上执行所花得时间不一样，在不同时刻也会由于计算机资源占用情况得不同,使得算法在同一台计算机上执行得时间也不一样,另外,算法执行得时间还与输入数据得状态有关，所以对于算法得时间复杂性，采用算法执行过程中其基本操作得执行次数,称为计算量来度量.算法中基本操作得执行次数一般就是与问题规模有关得,对于结点个数为 n 得数据处理问题,用T(n)表示算法基本操作得执行次数。为了评价算法得执行效率,通常采用大写 O符号表示算法得时间复杂度,大写 O 符号给出了函数 f 得一个上限。其它义如下：3十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程定义：f (n）O (g （n)） 当且仅当存在正得常数c 与n0,使得对于所有得 ，有 f（) g(n）。上述定义表明，函数 f 顶多就是函数g 得 c倍，除非 n 小于 n0.因此对于足够大得 n （如n0)，g 就是f 得一个上限(不考虑常数因子c）。在为函数 提供一个上限函数 g 时，通常使用比较简单得函数形式。比较典型得形式就是含有 n得单个项(带一个常数系数)。表 11 列出了一些常用得 g 函数及其名称。对于表1 中得对数函数lgn，没有给出对数基,原因就是对于任何大于 1 得常数 与 b 都有 lganlgb/loba,所以 logan与 obn都有一个相对得乘法系数 1/lgba，其中 就是一个常量。表1-1 常用得渐进函数1、 算法得空间复杂度指得就是什么？如何表示？【答】：算法得空间复杂度就是指算法在执行过程中占用得额外得辅助空间得个数。可以将它表示为问题规模得函数,并通过大写符号表示空间复杂度。、10 对于下面得程序段,分析带下划线得语句得执行次数,并给出它们得时间复杂度（n)。（1) i+ ;() for（=0；in；i+）if（ax） x=a;（3）for（i;iaj+1) k=j；=a；ak=ai； i=t；（5）fo(i=0;i；i+）for（j0;jn；j+）+；s=x;【答】:(1)O（1）;（2)O（n）；（3）O(n2)；（4)O（）;(5）O（n2）4函数名称1lognnnlogn2n3nn2n!常数对数线性n 个 logn平方立方指数阶乘十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第 2 章线性表及其顺序存储、1 选择题（1）表长为n得顺序存储得线性表,当在任何位置上插入或删除一个元素得概率相等时，插入一个元素所需移动元素得平均个数为（为( A)。）,删除一个元素所需移动元素得平均个数(n1）En/B。n.（+1）2C.n+1G(n2）/2D.（2）设栈 与队列 Q 得初始状态为空，元素 e、e2、3、e4、e5与 e 依次通过栈 S,一个元素出栈后即进入队列,若 个元素出队得序列为 e、e4、3、e、e5与e1,则栈 S得容量至少应该为( C)。A。B。4C.3D.（3)设栈得输入序列为 1、3 n,若输出序列得第一个元素为 ，则第i 个输出得元素为( ).不确定ni+1.。ni（4)在一个长度为 n 得顺序表中删除第i 个元素（leth;i+)if （Ldatai=x）c+；retur c；、4设计一个算法,将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组中,倒置得结果就是使得数组a 中得 a0等于原来得最后一个元素, 等于原来得倒数第 2个元素，,a得最后一个元素等于原来得第一个元素。【答】：顺序表得存储结构定义同题 2、3，实现顺序表倒置得算法程序如下:void vege（sqt)it t,i,j；=0;j=L-lng-1;hile (j） t=L-datai;L-daa+=Lataj;L-data-t；2、5 已知一个顺序表中得各结点值就是从小到大有序得，设计一个算法，插入一个值为 得结点，使顺序表中得结点仍然就是从小到大有序.【答】:顺序表得定义同题 2、3，实现本题要求得算法程序如下:十二五普通高等教育国家级本科规划教材oid setx(seqlist L,datatype x）int j；if （L-engthN） =Legth1;he （j=0 & Ldtaj) L-dataj=L-dataj;；Ldatj+=x；Leth+；2、6 将下列中缀表达式转换为等价得后缀表达式。(1) 56*7(2) (5）7（3)*8（4) 5*7() 5（6)+/9（6) 7*（58)9【答】:高等学校精品资源共享课程(7) +67（8） （5)7（） 567*8(）57-8（11)5(7-6)+9（12）7(5-6)-后缀表达式：5 6 +后缀表达式： 6-7/后缀表达式：56 78*后缀表达式:5 7* 8-后缀表达式:5 6*8 9/+后缀表达式：7 5 6 8-2、7 循环队列存储在一个数组中，数组大小为n，队首指针与队尾指针分别为 front与 rear，请写出求循环队列中当前结点个数得表达式。【答】:循环队列中当前结点个数得计算公式就是：(n+rearfrnt)%n2、8 编号为1,，4 得四列火车通过一个栈式得列车调度站,可能得到得调度结果有哪些？如果有 列火车通过调度站，请设计一个算法,输出所有可能得调度结果。【答】：方法一：算法思想：逐次输出所有可能,用回溯法。即:总体：对原始序列中得每一个元素，总就是先入栈,后出栈1。入栈后得操作：a、该元素出栈;b、下一个元素入栈；2出栈后得操作:a、（栈中其她元素)继续出栈;b、 (原始序列中）下一个数入栈;注意：回溯法,关键在于回溯，即在某分支结点 X：处理 得一个子分支,再退回分支X,接着处理 得下一个子分支,若所有 X得子分支处理完，再退回上一层分支节点。所谓“退回”,7十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程实际上就就是恢复。程序代码：（_8_1、)nd top=-；voidh(Sck , har x） 进栈/i（SopAX）retur;S-op+；SS-topx;charpop（Stck S）/*出栈*if(St=1） printf(ERROR,POPEmpt Sak”）;eurn1;S-top；etr -aS-tp1;int isEmpy（Sack *S)/*判断栈就是否为空*/if (Sto=-1) retrn1；return 0;voidoutSe(harseq，iten)/输出顶点序列/int i；or(i； ile; +）pintf（”2c,se)；prnt（n);vodchedler(int pos, int se_o)8十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程/pos:处理到原始数据中得第 po 个元素，seq_os：若出栈，应放在当前输出数组得第 so个位置/int i=0；char t；对任何一个数,总就是先进栈,再出栈。另外，这里不需要循环,类似于“查找数组中元素”用递归*/i（polen）/一个数进栈后,有两种处理方式:要么立刻出栈，要么进行下一个数得进栈/push(S，dos）；sheduler（os+,eqpos）;pop（&S）；i （!isEmpty(）)*一个数出栈后，有两种处理方式:要么继续出栈，要么继续下一个数得进栈*/tpop(&S)；see_pos+=t;schedul（os，sq_po);pus（S,t）；if （poen ismpty(S)outSq（seq，len）; cot+; int min(）in i;pintf（”plaeinputt num be chedled: ）;scan(”%d”， &en）; /用 l 存储待调度得火车数量/r(i=0； ien； i+)di=+i; /*创建火车编号,如 a、b、c、等/prntf（”h orginaseq is：”)；outSe(d，len);initStac(&S）；schduler（0,0);prnf（n ont=%d”， unt）;rurn ；方法二:解题思路：栈具有先进后出、后进先出得特点,因此,任何一个调度结果应该就是1，,3，4 全排列中得一个元素。由于进栈得顺序就是由小到大得，所以出栈序列应该满足以下条件:对于序列中得任何一个数其后面所有比它小得数应该就是倒序得，例如 4321 就是一个有效得出栈序9十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程列，42 不就是一个有效得出栈结果( 后面比它小得两个数 ,3 不就是倒序）。据此，本题可以通过算法产生 n 个数得全排列，然后将满足出栈规则得序列输出.产生n个数得全排列有递归与非递归两种实现算法.产生全排列得递归算法:设 R=r，r，rn就是要进行排列得 n 个元素,Riri。集合 中元素得全排列记为pem(X)。（ri）per(X）表示在全排列 per(X)得每一个排列前加上前缀 ri得到得排列。R 得全排列可归纳定义如下：当 n 时,pem(R)（）,其中 r 就是集合 中惟一得元素；当 时,perm(R)由（r1）perm（），（2）pem(R),，（）perm（R)构成。依此递归定义，可设计产生 pe(R)得递归算法如下:递归解法：(2_8_2、c)#icudestdio、hnt cnt；/全局变量,用于记录所有可能得出栈序列个数*/void print(int str，it n）；/求整数序列 str从 k 到n 得全排列*/oid per（nt str,int k,int ）nti，temp；if （k=1） rin（st,n）;el for (i=k;in;i+）mp=strk； sk=stri； stitemp;em（sr,k+,n); /*递归调用*/emp=ti; tr=sk； st=tmp;/*本函数判断整数序列 s就是否满足进出栈规则，若满足则输出/vod print（ttr,nt n)int i，j，k，l,m，flag=1,b2；for（=0;in；i+)*对每个sri判断其后比它小得数就是否为降序序列*/ m0；for（j=i+1；j&ag;j+)if (tristrj） if (m) b+=trj;else if （rb0) fla=;els b0=tj；i（）满足出栈规则则输出 tr中得序列*/10十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程printf(” d：，ont+）;f（i=0;it pl（it n) it 10；it lag1,flag1=0；E *rf ；in i,j，k,x,cout=；r = fope（tac、t， ”w） ;for （i=1;i=n;+)=i;whl （flg) fag1=1;/*最大处理范围为 个数*/pl、txt 用于存放进出栈序列结果/初始序列/* 还剩余未输出得排列/* 判断本次排列就是否符合进栈出栈序列 for （1；i=n;i+) j+1;hie(j= ai）j+； / 找 ai后第一个比 ai小得元素 aj*/k=j+；while （k=n）/如果 aj后还有比ai小且比 aj大得元素，则此排列无效/if （aka & kaj）fag1=0；k+; (flg1) or （i=1；in;i+)*输出当前排列*/ printf（4,ai); fprinf（rf,”%4”，ai）;rit(n）； fprintf(rf，”n”）；cout+;=n；/*计数器加*/从后向前找相邻位置后大前小得元素值/hie(i1 &aii-1） i；f （=1） fag=0; /未找到则结束/lse=i1;i=n；/若找到,则在该位置得后面从右向左找第一个比该元素大得值/while (ijaine=adD.=head(3）在带头结点得单链表中查找 x 应选择得程序体就是( ).ode *p=headnext； whil （ & p-ino!x） =pext；if (p-nfox）retrn p esereturnUL；.ne *hed； whle(p& pifo!=x） pp-next; return p;Cnde *p=heanext；whie （ppino！=x) p=p-next； reurn p；.nd*phead; while （-o！x） p=next ; rtur p；（4）线性表若采用链式存储结构时，要求内存中可用存储单元得地址（D）。必须就是连续得C.一定就是不连续得。部分地址必须就是连续得D.连续不连续都可以（5）在一个具有 n 个结点得有序单链表中插入一个新结点并保持单链表仍然有序得时间复杂度就是（ B)。O(1).O（n).O（2）。O（nlgn）(6）用不带头结点得单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D ）.A。仅修改队头指针C.队头、队尾指针都要修改B。仅修改队尾指针D.队头，队尾指针都可能要修改(7)若从键盘输入 个元素,则建立一个有序单向链表得时间复杂度为（B )。O（n）B.O(n2)C.（3)D.O（ng)（8)下面哪个术语与数据得存储结构无关（ ).A。顺序表B.链表C。散列表.队列(）在一个单链表中，若删除p 所指结点得后续结点，则执行（ A）。A。p-net=p-nex-nxt；C。p-ext=p-nx;.pp-next； p-next=nexnex;.p =pntext;（10）在一个单链表中，若 p 所指结点不就是最后结点，在 之后插入 所指结点,则执行（B ).A-next=p；p-next=s；C.sxt=-ne;p=；B.s-net=-;pnext=s；.px=s;snex;3、2 设计一个算法，求一个单链表中得结点个数。【答】:单链表存储结构定义如下（相关文件:liklit、h)ncud sdib、h14十二五普通高等教育国家级本科规划教材inclde stdio、htypde sructnoe int data;strctod *nx;linknode;ypedfiknoelinis；尾插法创建带头结点得单链表*/lils relinlis() inkis had,r，；int x;headr(inklist）malo（sizo(liknod）;pintf（n请输入一组以0 结束得整数序列:n”);can（%,&x）;ile (） =（linklist）mallo（zef（linnde）)；sdaax；rnet=s；r=；canf(%d,&x）;r-next=NUL；eturn head；/输出带头结点得单链表vd prnt(linkli hea) iklst ；p=hed-next；intf(”Lt is:n”）；while（p）prnf（5d”,pdat);p=next；pint(n)；基于上述结构定义，求单链表中得结点个数得算法程序如下：i cont（linklisthead)高等学校精品资源共享课程int=0；linklst phead;wile （）1十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程+；p=ne;return c；3、3 设计一个算法，求一个带头结点单链表中得结点个数。【答】：带头结点得单链表得存储结构定义同题 3、，实现本题功能得算法程序如下(33、c）#includ linkist、hin ount（linisthea） t0；linkist p=hedxt;hie （）c+;p=p-nxt;return；ain（)/*测试函数/linkistad;ea=ceatlin();rint（hd）；printf(”nLenthof head is：%d，co（hed）;gch();当输入 5 个数据时，产生得输出结果如下图所示：3、4 设计一个算法，在一个单链表中值为 得结点前面插入一个值为 x得结点.即使值为x 得新结点成为值为 y 得结点得前驱结点。【答】：#nclud”linklist、h”vid insr(linlished,n ，n x)*在值为 得结点前插入一个值为 x 得结点/lnklis pe,p,s；pre=ead;16十二五普通高等教育国家级本科规划教材hd-n；he （p& pdta！y) pre=p;p=-next;if （p）找到了值为 得结点 s=（lst)lloc(sizeof（liknoe）;sata=；s-next=p;pr-next=s;高等学校精品资源共享课程o mai（)liklistha;ity,x；ha=ceatlinklit（);prnt(hed）；/*测试程序*/*创建单链表*/输出单链表*/pritf(n 请输入 y 与 x 得值：”);scanf( %d,&，)；insert(head,y,x）；prit(ead);程序得一种运行结果如下图所示：、5 设计一个算法,判断一个单链表中各个结点值就是否有序.【答】:incldeikit、hint iored（linklistead,hr c）/当参数 c=a时判断链表就是否为升序,当参数 =d就是判断链表就是否为降序/ i flag=1；liklst p=had-next;wth （）17十二五普通高等教育国家级本科规划教材case ：/判断带头结点得单链表he 就是否为升序*/hile ( pnex flg)if（pdatap-exdta） p=p-nt；es g=0;brea；a d:/判断带头结点得单链表 hed 就是否为降序/whle (p&nxt &ag）i (pta=next-a） p=pne;ele lg=0;break;turn lag；高等学校精品资源共享课程int ai(）/*测试程序/ linkit ad；ea=eatlinklit（)；int(ha）；i （issrted(he，a)）pintf（”单链表head 就是升序排列得！);lef（otd(head,d）tf(单链表 hea 就是降序排列得!n)；