算法与数据结构C语言习题参考答案

1、1 .将下列爱杂度由小到大重新排序：D . 10 000 E . /?*log2(n)B . 6*log2(n) + 9nD . 5n2 + n3/2C ： O (/I4)D ： O Q?2)A.2B.nlC.Il5【答】10000</?*log2(n)<n5<2vn2 .将下列更杂度由小到大重新排序：A./7*10g2(7l)B.+J?+户【答】24<?i05<n*log2(/1)<n+n2+n33 .用大“O”表示法描述下列复杂度:A.5.5/2+m5C.3/?4+/*log：(/?)【答】A：O(52)B:O()4 .按照增长率从低到高的顺序排列以下表

2、达式：4112,log3n,3n,20n,2000,log2n,n2/3o又n!应排在第几位？【答】按照增长率从低到高依次为：2000,log3/7,log：/，产3,20，4n2,3"。！的增长率比它们中的每一个都要大，应排在最后一位。5 .计算下列程序片断的时间代价：inti-1;while(i<-n)()【答】循环控制变量1从1增加到n,循环体执行n次，第一句i的初始化执行次数为1,第二句执行n次，循环体中第一句pnntf执行n次，第二句i从1循环到n,共执行n次。所以该程序段总的时间代价为：T(n)=1+2n=3+1=。()6 .计算下列程序片断的时间代价：inti-1

3、;while(i<-n)(while(j<-n)wlule(k<-n)pdntfGi-%d,j-%d.k-%duT,Lj,k);k*l;J-J+l;i-i+1;)【答】循环控制变量i从1增加到n,最外层循环体执行n次，循环控制变量j从1增加到n,中间层循环体执行n次，循环控制变量k从1增加到n,最内层循环体执行n次，所以该程序段总的时间代价为：T(n)=1+1+nl+n+2n+1+1+1)+1=33+3标+4+2=。?3)精选范本2.线性表L试写一个插入算法mtinsertPost_seq(palist,p,x),在palist所指顺序表中，卜标为p的元素之后，插入一个值为x

4、的元素，返回插入成功与否的标志。【答】数据结构采用2.1.2节中顺序表定义。mtinseitPost_seq(PseqListpalist,mtp.Datalypex)/*在palist所指顺序表中下标为p的元素之后插入元素x*/mtq;/*溢出*/if(palist->n>-palist-MAXNUM)pnntff'Oveiflow!n)return0;if (p<0 | p>palist->n-l) /*不存在下标为p的元素/pnntfC'Notexist!n”)；renirn0:_foi(q-palist->n-1;q"p十1

5、;q-)/*插入位置及之后的元素均后移一个位置*/palist->elementq+l-palist->elementq;palist->elementp+l - x;palist->n - palist->n + 1;/*插入元素x /*元素个数加1return1;2试写一个删除算法deleteV_seq(palist,x),在palist所指顺序表中，删除一个值为x的元素，返回删除成功与否的标志。【答】数据结构采用2.1.2节中顺序表定义。mtdeleteV_seq(PseqListpalist.p,DataTypex)/*在palist所指顺序表中删除值为x

6、的元素*/mtpqfor(p-0;pn;pH)/查找值为x的元素的下标率/if(x-palist->elementp)for(q-p:q<pahst->n-l;q+)/*被删除元素之后的元素均前移一个位置*/palist->elementq-palist->elementq+1;/*元素个数减1，palist->n-palist->n-1;renun1;return0;3 .设有一线性表e=(%,ei,e?,，ed),其逆线性表定义为e，=仁吐1,e2,ei,e0)o请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的空间。【答】数

7、据结构采用2.1.2节中)11酹表的定义。思路考虑对数组element进行置逆，即把第一个元素和最后一个元素换位置，把第二个元素和倒数第二个元素换位置。它注意这种调换的工作只需对数组的前一半元素进行，所以设置整数变量count用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进行如上的对元素"换位置”的工作？(提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。)顺序表的置逆算法voidrev_seq(PSeqListpalist)DataTypex:intcount,i;if(palist->n0|palist->n1)return:/空表

8、或只有一个元素，直接返回本/count-palist->n/2;for(1-0:1<count;i+)只需调换半个表的元素亭/x-palist->elementi;palist->elementi一palist->elementpalist->n一1一口；palist->elementpalist->n-1-i-x:)代价分析该算法中包含一个f。循环,其循环次数为n/2o因此，算法的时间代价为。4 .已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。【答】数据结构采用2.1.2节中顺序表定义。思路设置变量nun,

9、遍历整个表，不断更新当前已经经历过的元素的最小值即可。为方便起见，事先假设表不为空。算法DataType min_seq(PSeqList palist)DataType nmi;mt i;min - palist->elementO;fbi (i - 1; i< palist->n; ifif (nun > palist->elementi) min - palist->elementi;return nun:八求非空顺序表中的最小数据元素*/八初始化nmi*/Onm中保存的总是当前的最小数据可代价分析该算法访问顺序表中每个元素各一次，时间代价为。()。科

10、讨论读者可以试图对上面的算法进行修改，使返回的值不是最小元素的值而是它的下标。5 .已知线性表A的长度为n,并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。【答】数据结构采用2.1.2节中顺序表的定义。思路为了减少移动次数，可以采用快速检索的思想，用两个变量"记录顺序表中被处理的两端元素的下标，开始时i=O.j=n-l,边检索第i个元素边增加i,直到找到一个元素值等于x,再边检索第J个元素边减少J,直到找到一个元素值不等于,把下标为，的元素移到下标为i的位置后重复上述过程，直至IJi>jo另用一变量count记录删除了多少个元素。算法voiddelx_seq(PS

11、eqListp、DataTypex)/率删除顺序表中所有值为、的元素，新顺序表可能不保持原有顺序*/mti-0j-p->n-1,count-0;八，定位于顺序表开始处,，定位于顺序表最后力while(i<j)if(p->elementi一x)尸找到了一个要删除的元素while(p->elementj-x)&&(i!-j)/*从后往前找不会被删除的元素.当LJ相等时退出循环，count记录从后往前找的过程中遇到了多少个要删的元素*/coun;p->n-p->n-count-1;return;elsep->elementi-p->el

12、ementj：count+;j-；ifp->n-p->n-count;if(p->elementi-x)p->n;)代价分析该算法访问顺序表中每个元素各一次，时间代价为。()。#讨论这个算法使用了一点技巧使得在中间删除元素时，避免了最后一串元素的移动。但是，它破坏了原来线性表中元素之间的顺序关系。如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表,如果元素不是X,则继续向后；如果元素是X,则寻找其后第一个不是X的元素，将这两个元素互换。具体算法请读者自己实现。6.写一算法，在带头结点的单链表Ihst中，p所指结点前面插入值为x的新结点，并返回插入成

13、功与否的标志。【答】数据结构采用2.1.3节中单链表定义。思想：由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插入。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locatejuik类似的方式进行搜索。算法：mtinseitPre_lmk(LmkListllist,PNodep,DataTypex)产在ihst带头结点的单链表中，P所指结点前面插入值为x的新结点*/PNodepl;if(llist-NULL)return0:pl-Hist;while(pl!-NULL&&pl>hnk!-p)pl-pl->l

14、ink;/率寻找p所指结点的前驱结点*/if(pl-NULL)return0;PNodeq-(PNode)malloc(sizeof(sunctNode);/率申请新结点if(q-NULL)prmtfC,Outofspace?return0;q->mfb-x;q->lnik-pl->lmk;pl->luik-q;renun1;7,写一算法，在带头结点的单链表Hist中，删除p所指的结点，并返回删除成功与否的标志O【答】数据结构采用2.1.3节中单链表定义。思想：由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成删除。而找p所指结点

15、的前驱结点，只能从单链表的第一个结点开始，使用与locatejuik类似的方式进行搜索。mtdeletePJink(LinkListllist,PNodep)/*在Uist帚头结点的单链表中，删除p所指的结点*/PNodepl;if(llist-NULL)renirnNull;pl-Hist;while(p1!-NULL&&p1->hiik?-p)p1-pl->lnik;/*寻找p所指结点的前驱结点率/if(p1-NULL)retuin0;pl->link-p->liiik;free(p);/*删除结点p*/return1;)8.已知list是指向无头结

16、点的单链表的指针变量，写出删除该链表下标为1的(第1+1个)结点的算法。【答】数据结构采用2.1.3节中单链表定义。思路依次遍历表中的每一个结点并计数，到第i+1个结点时实行删除。由于链表是无头结点的，所以在删除第一个结点时要特别注意。算法mtdeletenidexJiiik_nohead(LmkList*pllist.mti)/*删除单链表中下标为i的结点。删除成功返回TRUE,否则返回FALSE。*/intj;PNodep、q:if(*pllist)-NULL|i<0)returnFALSE;if(i-0)严如果需要删除第一个结点本/一(*pllist)->link;free(

17、q);returnTRUE;p-(*pllist);j-O；wlule(p->lmk!-NULL1)片寻找下标为的结点的地址，p-p->link;j+;if(p->link-NULL)returnFALSE;/*此元素不存在*/q-p->link;p->lnik-q->link;free(q);leturnTRUE;)代价分析该算法访问单链表中前面i个结点，时间代价为。，最大不超过。()。#讨论如果函数参数不是LnikList*类型而是LnikList类型，在删除/=0的结点时，程序不能正确实现，其原因请读者思考(考虑C语言的参数传递方式X如果单链表带表头结

18、点，重写本题的算法。比较这两个算法，是否能体会到表头结点的作用。9.已知list是指向无头结点的单链表的指针变量，写出删除该链表中从下标为1的(第计1个)结点开始的连续k个结点的算法。【答】数据结构采用2.1.3节单链表定义。思路这道题与上题相似，只需要增加计数即可。要注意的是应该判断给出的i和k是否合理，是不是会超出链表长度。算法intdel_link_nohead(LHikList*i.mtk)删除单链表中从下标i开始的k个结点。删除成功返回TRUE,否则返回FALSE。*/intj;PNodep、q:if(*plhst)NULL|i<0'k<-0)r

19、eturnFALSE;产如果需要删除从第一个结点开始的k个结点*/for(j-0;j<k&&(*pllist)!-NULL;j+)q-(*pllist);(*pllist)-(*pllist)->lmk;free(q);leturnTRUE;p-j-O；wlule(p->link!-NULL&&j<i-l)严寻找下标为/-I的结点的地址写p-p->link;jfif(p->linkNULL)returnFALSE;产第i个结点不存在Vfor(j-0:j<k&&p->liiik!-NULL;j+)q-

20、p->link;p->lnik-q->link;free(q);returnTRUE;)代价分析该算法访问单链表中前面i+k个结点，时间代价为。(海),最大不超过。13.请设计一个算法，求出循环表中结点的个数。【答】数据结构采用不带头结点的循环链表。structNode;typedefstructNode*PNode;structNodeDataTypeinfb;PNodelink;typedefstructNode*LinkList;思路遍历整个循环链表，同时计数即可。¥错误算法mtcount(LinkListclist)intcount;PNodep、q:p-c

21、list;q-p->link;if(cHst-NULL)return0:/如果是空表率/count-1;while(q!-p)q-q->liiik:counts;returncount;)错误：如果clist是一个空表，那么第5行的语句"q=p-Xink;"是非法的。分析：应把第6行语句(用下划线表示)提前1行或2行。一定要放在语句"q=pAlmk;"之前。缺点：增加局部变量p。分析：这样做没有必要，因为p的初值置为chst,在程序中并没有对p做其他修改，所以程序中不需要引入P而直接使用clist即可。算法mtcount(LinkListcl

22、ist)mtcount;PNodeq;if(cHst-NULL)return0:/亭如果是空表率/q-clist->link;count-1;while(q!-clist)q-q->link;count十十；returncount:)代价分析该算法访问循环链表中每个结点各一次，时间代价为。()。4.栈与队列1 .写一个递归算法来把整数字符串转换为整数。(例：“43567”-43567o)【答】思路先递归调用本算法转换除去末位夕陵U余的字符串，结果乘以10。再转换末位。将两结果相加即为所求。算法intsumgToIntl(char*s，intstart,mtend)/*把整数字符串5

23、中从start至!Jend的部分转换为整数率/if(start>end)return-1;产转换失败if(start-end)renirnsend-10*;/*只有一个字符f直接转换以returnstimgToIntl(s,start,end-1)*10+send-'O'/率先转换其他位，再转换末位率/)intsuingToInt(char*s)，率把整数字符串s转换为整数率/inti-0:while(si!-i;/率计算字符串的长度率/returnstimgToIntl(s,0,i-1);)代价分析设为字符串的长度。该算法访问每个字符各一次，时间代价为。()，计算字符串

24、的长度的时间代价也为。()。故总的时间代价为。()。递归算法需要栈的支持，栈的大小与递归调用的深度成正比。所以实际空间开销为。()。2 .编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印出来。【答】数据结构采用4.1.2节中栈的顺序表小。思路将输入的十进制数字反复除以2,直到它变为0。将每次的数字模2的余数入栈。栈中存放的就是所要求的二进制表示。再将栈中的元素依次弹出打印即可。算法voiddec_numbei)产将十进制非负整数转化为二进制数打印出来7PSeqStackpastack;mttemp-dec_numbei:if(temp<0)printfC'EnodiT

25、);return;pastack-createEmptyStack_seq();产建立一个空栈if(pastack-NULL)reuirn;while(temp>0)push_seq(pastack,temp%2);tempI-2;wlule(!isEmpty,Stack_seq(pastack)top_seq(pastack);pop_seq(pastack);free(pastack);)代价分析设输入的十进制数字为，则算法的时间代价为O(log2n)0空间代价主要是栈的大小，为O(log2w)o3 .写一个算法：PSeqStackcreateEmptyStack_seq(mtm)创

26、建一个空栈。数据结构采用4.1.2节中栈的II页序表示。PSegStackcreateEmptyStack_seq(mtm)/*创建一个空栈*/PSeqStackpastack-(PSeqStack)malloc(sizeof(stnictSeqStack);if(pastack!-NULL)pastack->s-(DataType*)malloc(sizeof(DataType)*m);if(pastack->s)pastack->MAXNUM-m;pastack/栈顶变量赋值为-1率/return(pastack);)elsefreepastack;)printfC

27、9;Outofspace!/*存储分配失败*/returnNULL;4,写一个算法：intisEmptyStack_seq(PSeqStackpastack)判断pastack所指的栈是否为空栈。数据结构采用4.1.2节中栈的II页序表示。mtisEmptyStack_seq(PSeqStackpastack)/*判断pastack所指的栈定否为空栈*/iftpastack->t-1)renirn1;elsereturn0:8.假设以循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设队头指针)，试编写相应的创建空队列、入队列和出队列的算法。【答】数据结构采用不带头结点的循环链表

28、表示队列。structNode;typedefstructNode*PNode;structNodeDataTypemfb;PNodelink;structClmkQueue产循环链表表示的队列类型事/PNoder;/*尾指针*/)typedefstructClmkQueuePClu±Queue:/本指向循环链表表示的队列的指针类型*/rrr队头一*RdIt队尾队列的循环链表表示思路与队列的单链表表示相似，但节省了指向队头的指针变量，所以在需要找表头结点时必须通过表尾指针进行。算法PChnkQueuecieateEmptyQueujclink()产创建空队列*/PClmkQueuep

29、cqu-(PClmkQueue)inalloc(sizeof(sti-uctClmkQueue);pcqu->r-NULL;xeturnpcqu;进队列*/voidenQueue_clmk(PClinkQueuepcqu.DataTypex)PNode p;p 一 (PNode)malloc(sizeof(suiict Node); p->mfb - x;if (pcqu->r NULL) pcqu->r - p;p->lmk - p;retuni;)p->lnik - pcqu->r->link;pcqu->r->link - p;

30、pcqu->r - p:)void deQueue_clmk(PClmkQueue pcqu) PNode p;if (pcqu->r NULL) printf<MUndeiflow!1nH);return;if (pcqu->r->link - pcqu->r) free(pcqu->r);pcqu->r - NULL;return;p - pcqu->r->link;pcqu->r->link - p->link;free(p);产进空队列，即往空队列中加入第一个结点*/外出队列*/产是空队列*/只有一个元素的队

31、列*/产指向队头*/代价分析上述几个算法都不包含循环，只有常数条语句，因此每个算法的时间代价均为0(1)。称讨论本题可以看成队列的循环表实现。5.二叉树与树1 .写一个算法来计算给定二叉树的叶结点数。【答】数据结构采用5.1.3节中二叉树的链接表示。算法intnum_of_leaves(BmTreet)/字计算二叉树的叶结点个数率/if(t-NULL)remm0;产空树，返回01if(t->llHik-NULL&&-NULL)return1;产根结点是树叶，返回1本/leturnnum_of_leaves(t->llHik)+num_oflleaves(t->

32、rlink):产返回左子树的叶结点数十右子树的叶结点数"率/)代价分析该算法访问每个结点各一次，时间代价为。以空间代价为。(/九2 .假设二叉树采用链接方法存储，编写一个计算一棵二叉树f的高度的函数。【答】数据结构采用5.1.3节中二叉树的链接表示。思路对一棵二叉树/,考察它左右子树的高度，取其中大的一个，再加1即为/的高度。算法mtdepth(BniTreet)(PBmTreeNodepbtree;intdLdr;pbtree-t;if(pbueeNULL)(return-1;dl-ckpth(pbtiee->Hmk);dr-depth(pbtiee->rlink);r

33、eturn(dl>dr?dl:dr)+1;)代价分析设树中的结点个数为，递归访问次数只可能是几所以，时间代价为。()。空间代价为。(/小h为二叉树的高度。6 .设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二叉树。【答】数据结构采用5.1.3节中二叉树的链接表示。思路二叉树的先根序列和对称序序列，用两个数组preoider和inorder存放。先根序列的第一个元素的值pwdei0应为二叉树的根上的元素值在另一个数组中查到此值设为inorderA-0此时，数组preorder中从pieordmi到preorderk的序列(长度为k)和数组morder中从inoidW

34、O到inordei-1(长度为k)的序列，恰好分别是根结点左子树(k个结点)的先根序列和对称序序列。数组preoider中从pieorder2+l到preorder-1的序列(长度为n-k-l)和数组inorde中从inorde伙+1倒inoider/?-l(长度为n-k-1)的序列，恰好分别是根结点左子树(n-k-1个结点)的先根序列和对称序序列。根据上述分析，算法先创建根结点，再递归调用自己两次来分别创建左右子树。算法mtcreate_BTree(PBmTreepbtree.DataType*preoider,DataType*inorder,mtn)产根据先根序列preoider和对称序

35、序列morder(长度为)创建二叉树pbtree0对于正确的先根序列和对称序序列，算法返回TRUE,否则返回FALSE。*/mti,k;mttagl.tag2;if(n0)*pbtree-NULL;returnTRUE;for(i-0;i<n;i+)if(inoideiipreoider0)break;if(in)*pbtree-NULL;returnFALSE;芦输入的先根序列或对称序序列有误，创建失败*/k-i;*pbtree-(PBinTieeNode)malloc(sizeof(stiiictBinTreeNode);(*pbtree)->infb-preorder0;ta

36、gl-create_BTiee(&(*pbtree)->liiiik,preorder+1,inorder,k);产递归调用本算法创建左子树率/tag2-create_BTiee(&(*pbtree)->ilink,preordei+k十Lmorder+k+Ln-k-l);产递归调用本算法创建右子树率/if(tagl-TRUE&&tag2TRUE)returnTRUE:returnFALSE;二叉树创建成功当且仅当其左右子树都创建成功年代价分析最坏的W况是，每t非口磔点只有左子树。这时两W眨间需要版交次。所以，该算法的时间代价为。(，空间代价主要包括

37、：存放二叉树的空间。和用于递归调用的栈空间(不超过。()X7.试设计树的子表表示法的存储结构，并给出在这种表示基础上主要运算的实现算法。【答】数据结构厂边表中结点的定义本/J*子结点位置*/*下一个边的指针*/"结点的定义*/，*结点本身信息，/*到子结点的边表率/树的定义*/产结点表率/根的位置*/产结点的个数*/structEdgeNode(mtnodeposition:stmctEdgeNode*link:;structChiTreeNode(DataTypeinfb;structEdgeNode*children:;structChiTree(structChiTreeNod

38、enodelistMAXNUM;mtroot;mtn;typedefstructChiTree*PCluTree;算法创建空树PChiTreeCreateNullTree_chitree(void)(PChiTreep;p一(PCliiTree)nialloc(sizeof<stiiictChiTree);if(pNULL)print.Outofspace!n");elsep->root1;returnp;)判断树是否为空intisNull_clutree(,PChiTreet)(returnt->n0;)返回非空树的根结点的下标DataTyperoot_chitr

39、ee(PCluTreet)(returnt->root;)返回下标为p的结点的父结点的下标mtpaient_chitree(PCluTreet.mtp)(mti;stmctEdgeNode*v;if(p<0|p>-t->n)return-1;for(i-0;i<t->n;if(v-t->nodelisti.children;wlule(v!-NULL)if(v->nodepositionp)returni;elsev_v->link;return-1;)返回下标为p的结点的最左子结点的下标mtleftChild_clutxee(PPaiTi

40、eet.mtp)(stmctEdgeNode*v;if(p<0|p>-t->n)return-1;v-t->nodelisti.cluldien;if(vNULL)return-1;leturnv->nodeposition;返回下标为p的结点的右兄弟结点的下标mt nghtSiblmg_chitree(PPaiTree t. mt p) (mt i;stmct EdgeNode * v;if (p < 0 | p >- t->n) xeturn-1;for (i - 0; i < t->n; if(v - t->nodelis

41、ti.children;wlule (v!- NULL)if (v->nodeposition p) if(v->lmk NULL) return-1;/手没有下标为p的结点率/产for循环每次检查结点下标中一个元素率/户每次循环检查结点，的边表中的一个元素中/产没有右兄弟结点率/else/率返回右兄弟结点在结点表中的位置率/returnv->inik->nodeposition;v-v->link;return-1;/*没有右兄弟结点*/)代价分析这是一个两重循环程序，外层循环最多执行次，内层循环对每个结点的子结点进行检查,子结点的个数最大可能与接近，所以表面看