2023年人武学院数据结构课后习题答案及期末综合练习

第十章内部排序一、基本知识题答案１．排序:将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。内部排序:数据存储在内存中，并在内存中加以解决的排序方法叫内部排序。堆:堆是一个完全二叉树,它的每个结点相应于原始数据的一个元素,且规定假如一个结点有儿子结点,此结点数据必须大于或等于其儿子结点数据。稳定排序：一种排序方法,若排序后具有相同关键字的记录仍维持本来的相对顺序,则称之为稳定的，否则称为不稳定的。2.回答下面问题(1)5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最佳？为什么？（2）大多数排序算法都有哪两个基本操作？答:(1)采用堆排序最佳。由于以上几种算法中,快速排序、归并排序和基数排序都是在排序结束后才干拟定数据元素的所有顺序,而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小)的。根据题意,只要选取前10个最大的元素，故采用堆排序方法是合适的。(2）两个基本操作:比较两个关键字的大小、改变指向记录的指针或移动记录自身。3.3．已知序列{1７,2５，55,43,３,３2,78,6７,91｝,请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。答:采用冒泡排序法排序时的各趟结果如下：初始:17,25，55，43,3，3２，78,６7，９1第1趟:17，2５，43,3,32，55，67,78,9１第2趟：１７，２5，3，３2,4３，55，67,78，9１第3趟:1７，3,25,３2，4３，55,67，７8，91第４趟：３，17,25,32,4３，55，67，７8,91第5趟:３，17，25，32，４3,55，67，78，91第５趟无元素互换，排序结束。4．已知序列{4９1，77,57２，１6,9９6,10１，８６3,2５8,68９,32５}，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。答:采用快速排序法排序时的各趟结果如下:初始:4９1,77,572,16,9９6，101，863,2５8，６89,325第1趟:[325,77，258,16,１0１］４９1[863，9９６，689，５７2]第2趟：[10１,７7，258,16]32５，491[86３，9９6,６８9，572]第3趟:[16，7７]1０1[25８]325，491[863,99６，６89，５7２]第4趟:16［77]101[258]325，491[863,996,689,572］第5趟：１６,77，101［２58]３25,４91[８6３，99６，68９,572］第6趟:１６，7７，１01,25８，３25，4９1[863，９9６,689，５72]第7趟：16,77,101,258,３25,491［572,689]86３［996]第８趟:１６,77，101，258，325，4９１,5７２[6８9］863[9９6］第9趟：1６,7７,101，258，３25,4９１,572,689，86３［996］第10趟：16,７7，101，2５8,32５,491，5７2，689,86３,996采用堆排序法排序时各趟的结果如下图所示:(a)初始堆(b)建堆(c)互换9９6和77,输出99６(d)筛选调整采用基数排序法排序时各趟的结果如下：初始:４９1,７7，572,1６，99６，10１，863,2５8，689，325第1趟（按个位排序):４９1，101，572,86３，35２,１6,996，77,258，68９第２趟（按十位排序)：101,16,３52,２58，863,572，77,6８９,49１,996第3趟（按百位排序）:１6,77,10１,2５8，352，491，５7２，689，8６3，99６5.已知序列｛８６，9４，138，62，４1,54,1８，32},请给出采用插入排序法对该序列作递增排序时，每一趟的结果。答:采用插入排序法排序时各趟的结果如下:初始:(86)，9４,13８，62，4１,54,18,32第1趟：(86,94)，138，６２,41，54,18，32第2趟:(86,94,１38）,6２,41,5４,18，32第3趟：(62,８6,９4，138）,41，54，18,３２第４趟：（41,62，86，９４,１３8），54,18，32第5趟:（41,54，６2，86，94,138）,１8,32第6趟:(18,41,54，62，86,94,138）,32第7趟：(１8,３2,41,54,62，８6,94,１３８)6．已知序列｛27,35,11，9,１8，３0，3，２3，35，20}，请给出采用归并排序法对该序列作递增排序时的每一趟的结果。答:采用归并排序法排序时各趟的结果如下:初始：27，35,11,9,18,30，３,23,３5，20第１趟：［2７,35］[９,11]［18,3０][3,2３]［20,35]第2趟:[9,１1,27，3５］[3，18,23，3０][20，35]第3趟：［9，11，27，3５］［３，18，２0,２3,３0，35]第4趟:[3,9,11，1８,2０,23，27,3０，３5,35]二、算法设计题答案１.二、算法设计题1．一个线性表中的元素为所有为正或者负整数，试设计一算法,在尽也许少的时间内重排该表，将正、负整数分开，使线性表中所有负整数在正整数前面。解：本题的算法思想是:设立两个变量分别指向表的首尾，它们分别向中间移动，指向表首的ﻫ假如碰到正整数,指向表尾的假如碰到负整数则互相互换,然后继续移动直至两者相遇。实现本ﻫ题功能的算法如下:ｖoｉdpart（iｎｔarray[]，iｎｔｎ){ﻩｉｎｔi,j；ﻩi＝1; j=ｎ;wｈｉｌｅ(ｉ＜j） ｛whｉlｅ(i＜j＆&ａrray[i]<0) ﻩﻩｉ++;ﻩ ｗｈile（ｉ<ｊ&&ａrｒａy[j］>=０)ﻩﻩ ｊ－－; ﻩif(i＜j) {arｒay[0]=ａrray［i]； ﻩﻩarrａｙ[i]=arrａy［ｊ];ﻩﻩﻩarray[ｊ］＝aｒｒay[0］;ﻩ }ﻩ}}2.设计一个用单链表作存储结构的直接插入排序算法。解：实现本题功能的算法如下：vｏｉｄiｎsｅrｔｓort（nodｅ＊head){ﻩnｏｄe*p,*ｑ，*pre；ﻩｐre=ｈeaｄ;ﻩp=heaｄ->neｘt;/*p指向待插入的元素*/ﻩwｈile(p！=NUＬL)ﻩ{ﻩﻩq＝heａｄ; ﻩif(p->keｙ＜ｑ->key)/*插到表首＊/{pre->next=p->nexｔ;ﻩ p->ｎext=ｈead;ﻩﻩﻩhｅad=p;ﻩ }ﻩ eｌｓｅﻩﻩ{ﻩﻩwｈile(q->next!=p＆＆q->next-＞ｋey<ｐ－>kｅｙ) ﻩﻩq=q-＞nexｔ; ﻩif(q->nexｔ＝=p） ﻩ{ ﻩﻩpre=p;p=p->next; }ﻩﻩﻩelsｅﻩ ﻩ｛prｅ->neｘt=p->next;ﻩ ﻩp－>next＝q->neｘｔ; ﻩ ｑ->nｅｘｔ＝ｐ;ﻩ ﻩﻩp=pｒe->ｎexｔ；ﻩﻩﻩ}ﻩﻩ}ﻩ｝}3.试设计一个算法实现双向冒泡排序。(双向冒泡排序就是在排序的过程中交替改变扫描方向。）解：实现本题功能的算法如下：voidｄbuｂbｌesort(ｓqliｓtｒ,iｎtｎ){ inti，j,fｌag; ｆlaｇ=1; i=1;ﻩwhile（flag!=0)ﻩ{ﻩ flａg=0; ｆｏr(j=i;j＜n-i；j＋+){ ﻩif（ｒ[ｊ］>r[j+1]) ﻩ{ ﻩ ﻩflag＝1;ﻩﻩ r[０]=ｒ[ｊ］; ﻩﻩ r[j]=r[j+1];ﻩﻩ r[ｊ＋１]=r[０］;ﻩﻩ }ﻩﻩ｝ﻩﻩｆor(j=ｎ-ｉ；j>i;j--){ ﻩ if(r[j]<r［j-1])ﻩﻩ {ｆlag=1;ﻩﻩ ﻩｒ[0]=r[j]；ﻩﻩﻩﻩｒ[j]=r[j-１]; ﻩｒ[ｊ-1]=r[0];ﻩ ﻩ} }ﻩﻩ i+＋;ﻩ}}4.设一个一维数组Ａ［n］中存储了n个互不相同的整数,且这些整数的值都在０到n-1之间，即A中存储了从0到n－1这n个整数。试编写一算法将A排序，结果存放在数组B[ｎ]中，规定算法的时间复杂性为O(n)。解:实现本题功能的算法如下：voidsｏrt(intＡ［n］，iｎtB[n］){ﻩiｎti； fｏr(ｉ=０;i＜n；ｉ＋+） ﻩB[A［i]]=A[ｉ］;}第九章一、基础知识题1.(１)查找：查找又称为查询或检索,是在一批记录中依照某个域的指定域值,找出相应的记录的操作。(2)树型查找：将原始数据表达成二叉排序树，树的每个结点相应一个记录,运用此二叉排序树进行类似于二分查找思想的数据查找，这种查找方法称为树型查找。(3）平衡因子：二叉树中每一结点的左子树高度减右子树高度为该结点的平衡因子。（４)散列函数：根据关键字求存储地址的函数称为散列函数。(５)两个不同的关键字，其散列函数值相同,因而被映射到同一个表位置上的现象称为冲突。２.设有序表为{a,b,c,d，ｅ,f,g}，请分别画出对给定值f,g和h进行拆半查找的过程。答：查找f的过程如下:查找成功，找到k＝f值查找g的过程如下：查找成功，找到k=g值查找h的过程如下:试述顺序查找法、二分查找法和分块查找法对被查找表中元素的规定，每种查找法对长度为n的表的等概率查找长度是多少答:顺序查找法:表中元素可以任意存放。查找成功的平均查找长度为(ｎ+1)／2。二分查找法：表中元素必须以关键字的值递增或递减地存放且只能以顺序表存放。查找成功的平均查找长度为log2（n+1)－１。分块查找法:表中每块内的元素可以任意存放,但块与块之间必须按关键字的大小递增或递减地存放,即前一块内所有元素的关键字不能大(或小)于后一块内任意一个元素的关键字。若用顺序查找拟定所在块,平均查找长度为1／２（n/s+s)+1;若用二分查找拟定所在块,平均查找长度为lｏｇ2(ｎ/ｓ+1）＋s/2。4.设散列表长m=14，哈希函数为H(k)＝ｋmod11,表中一共有8个元素{15,27,50,73,49,61，37,6０｝，试画出采用二次探测法解决冲突的散列表。答:采用二次探测法解决冲突的散列表如下：5.线性表的关键字集合为{113,1２,1８0,138,９2,67,94,13４,２52,６，7０,323，60｝，共有1３个元素,已知散列函数为：H（k）=kmod13,采用链接表解决冲突，试设计这种链表结构。答:由题意，可得:H(113）=113%1３=９H(１2)=12％13＝1２H(１８0）=180%１3＝１１H(１３8)=138%13=８H(９2)=９2%13=1H(67)＝67%１3=2H(94)=94%１3=３H(13４)=1３4%1３=4H(252）=２52%13＝5H(６)=6％13＝6H（70）=７0%13=5Ｈ（323）=３23%13=１1H（60）=60%13=8链接表法的散列表如下图所示:6.设关键字集合为{２7,49,７9，5,37，1,56,65,83}，散列函数为：H（k）=kmod7，散列表长度m＝１0，起始地址为０,分别用线性探测和链接表法来解决冲突。试画出相应的散列表。答：线性探测法的散列表如下图所示：链接表法的散列表如下图所示：二、算法设计题1.从小到大排列的，试写出对此链表的查找算法,并说明是否可以采用折半查找。解：实现本题功能的算法如下，假如查找成功,则返回指向关键字为x的结点的指针，否则返回ＮULL。noｄｅ＊sqseａrｃh（nodｅ*heａｄ，intx）{nｏdｅ*p=ｈead;ﻩｗhile(p!=ＮUＬL）ﻩ if(x>p-＞key) ﻩﻩp=p->ｌiｎｋ；elｓｅiｆ（ｘ＝=p->kｅy)ﻩ ﻩｒｅturnｐ;eｌｓｅ{p=NULL;retuｒnｐ;ﻩﻩ}}虽然链表中的结点是按递增顺序排列的,但是其存储结构为单链表，查找结点时只能从头指针开始逐步进行搜索，所以不能用折半查找。2．假如线性表中各结点查找概率不等,则可以使用下面的策略提高顺序表的查找效率:假如找到指定的结点,则将该结点和其前趋(若存在）结点互换,使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法(注意查找时必须从表头开始向后扫描）。解:采用顺序存储结构的算法如下,设记录存储在线性表的１~n单元中。假如查找成功，返回关键字为k的记录在线性表中的位置，假如失败则返回0。intseｑsearch(sqlｉsｔr,intn,iｎtk）{ inti,ｊ;ﻩi=1;ﻩwhile（(r[i］.key！＝k)&&(i＜=n)) i＋+；ﻩif（i<＝ｎ)｛ r[0]＝r[i]； r[i]=r[i－1］;r［ｉ-１]=r［i];ﻩﻩi－－; return(i); ｝ﻩelse ﻩreｔurn(0);}采用链式存储结构的算法如下。假如查找成功，则返回指向关键字为ｋ的结点的指针,否则返回ＮULL。nodｅ＊sｅqseaｒｃｈ（node*head,ｉntk){ﻩiｆ(head－＞key=＝k)ｒeturｎ(hｅad);ﻩelse{ﻩﻩnode＊p,＊q;intx；p=ｈｅａd; ﻩｑ＝head->ｌink;ﻩ ｗhile(q!=NULL&＆ｑ->kｅy!=k）ﻩﻩ{ﻩﻩﻩp=q；ﻩ ﻩｑ=ｑ－>ｌinｋ; ｝ if(ｑ!=ＮUＬL)｛ ﻩx=p－>key;ﻩ ﻩp－＞ｋｅy=q-＞kｅy； ﻩ q->ｋey＝ｘ; ﻩq=p; ﻩ} retｕrｎ(q）；ﻩ}}3.试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。解:本题的算法思想是：一方面计算要删除的关键字为k的记录所在的位置，将其置为空（即删除）,然后运用线性探测法查找是否有与k发生冲突而存储到下一地址的记录,假如有则将记录移到本来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下：vｏｉdｄｅlｅｔe(sqlisｔｒ,ｉntｎ，intk）{ｉnth，h0，h1;ﻩｈ＝k%n;ﻩwhｉle（r[ｈ].key！=k）ﻩ h＝(h+1)％n；ｒ［h]＝NＵLL;ﻩh0=h; h1=(ｈ+１)%ｎ；ﻩwhilｅ（h1!=h)ﻩ{while(r［h1].key%n!=ｈ)ﻩ ｈ1＝（h1+1)%ｎ； r［h0]=r[h１]； ｒ[h1]=NULL; h0=h1; ｈ1＝（h１+１)%n;ﻩ}}4.设给定的散列表存储空间为H[1~ｍ］，每个单元可存放一个记录，H[i](1≤ｉ≤m)的初始值为零，选取散列函数为H(R．kｅy),其中key为记录R的关键字,解决冲突方法为线性探测法,编写一个函数将某记录R填入到散列表H中。解：本题的算法思想：先计算地址H（R.key）,假如没有冲突,则直接填入；否则运用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下:vｏidiｎsｅrt（recｏｒdH，inｔｍ,rｅｃoｒdＲ){ iｎti;ﻩｉ=H(R.key)；ﻩｉf(H［i]＝＝NＵLL)ﻩ Ｈ[i]=Ｒ;elｓe ｛ while(H[ｉ]!=ＮUＬL） ｛ﻩﻩ i=(i+１)%(ｍ+1)； }ﻩﻩＨ[i]＝R; }}第七章一、基本知识题1.图的逻辑结构特点是什么?什么是无向图和有向图？什么是子图？什么是网络?答：图是比树更为复杂的一种非线性数据结构,在图结构中，每个结点都可以和其它任何结点相连接。无向图:对于一个图Ｇ，若边集合E（G）为无向边的集合，则称该图为无向图。有向图:对于一个图G，若边集合E（G)为有向边的集合，则称该图为有向图。子图:设有两个图Ｇ＝(V,E)和G’＝(V’,E’)，若Ｖ(G’)是Ｖ（G）的子集，且E（G’)是Ｅ(G)的子集，则称G’是G的子图(Subgraｐh)。网络：有些图，相应每条边有一相应的数值,这个数值叫做该边的权。边上带权的图称为带权图,也称为网络。2.什么是顶点的度？什么是途径？什么是连通图和非连通图？什么是非连通图的连通分量?答：顶点的度：图中与每个顶点相连的边数，叫该顶点的度。在一个图中,若从某顶点Ｖp出发,沿一些边通过顶点V1,V2，…,Vm到达，Vq，则称顶点序列（Vｐ,V1,V２,…,Ｖｍ,Vq）为从Vp到Vq的途径。在无向图中,假如从顶点Vi到顶点Ｖj之间有途径，则称这两个顶点是连通的。假如图中任意一对顶点都是连通的,则称此图是连通图。非连通图的连通分量:非连通图的每一个连通的部分叫连通分量。3.给出图６.25所示的无向图G的邻接矩阵和邻接表两种存储结构。答:图G所相应的邻接矩阵如下:图G所相应的邻接表如下：图254.假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。答:(a)所相应的无向图如下图(a）所示,(ｂ）所相应的有向图如下图(ｂ)所示:5.5.分别给出图6．26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。图26答：深度优先搜索得到的顶点访问序列:0、1、3、7、8、4、9、5、6、2;ﻩ广度优先搜索得到的顶点访问序列:0、１、2、３、4、５、6、7、8、9。６.应用ｐriｍ算法求图6．27所示带权连通图的最小生成树。答:该图的最小生成树如下：ﻩﻩﻩﻩﻩ ﻩ ﻩ ﻩ 图27ﻩ７.写出图6．28所示有向图的拓朴排序序列答:该有向图的拓朴排序序列为:3、１、4、5、２、６。二、算法设计题 ﻩ ﻩ ﻩ 图28二、算法设计题答案1.如图6.2９所示图G,试给出其相应的邻接表,并写出深度优先算法。解:该图相应的邻接表如下:深度优先算法：ｖoiddfsgｒaph（adjlistadj,ｉntn)/＊深度优先遍历整个图*/{ iｎti; for（i=1;i＜＝n;ｉ++） ﻩvｉsiteｄ[i］=0; for(ｉ＝1;i＜=n;i++)ﻩﻩif(！visiteｄ[i］)ﻩﻩ dｆs(adj，i）;}voiｄdfs(adjｌistadｊ，intv)/*以v为出发点,对图进行dfｓ遍历*/{structedgenode*p;viｓited[ｖ]=1;printｆ(＂％d",v）;p＝adj［v]→ｌink;whiｌｅ(p！=NULL){if（visitｅd[p→adjveｘ]＝=0)ﻩﻩ dｆs(ａdjlｉst，p→adjvex）;ﻩﻩp=p→nｅｘt；ﻩ}｝2.如图6.2９所示图G,试给出其相应的邻接矩阵，并写出广度优先算法。解：该图相应的邻接矩阵如下:广度优先算法:voidｂfｓgｒaph（ｉnｔadjａｒray[n］[ｎ］,ｉntn）/＊广度优先遍历整个图*/{ﻩinti;ﻩfｏr(i=0；i<n；ｉ＋+)ﻩﻩvisited[i]＝０;ﻩfor(ｉ=０;ｉ<ｎ;i++) 图2９ﻩ if(!ｖisｉｔｅd[i］) bｆs(ａdjaｒray,i);}ｖoidbfs(intadｊａｒrａy［][],intｖ)/＊以v为出发点,对图进行ｂfｓ遍历*/｛ ｉｎti，j; ｑueuｅｑ;ﻩｐｒintf（"%d",ｖ）;ﻩviｓｉtｅd[v]=1;ﻩeｎquｅuｅ(＆q,v); wｈiｌe（！queuｅeｍty(&q))ﻩ{ ﻩi=dequeｕｅ(&q)；ｆor(j＝0;j<n；j＋+)ﻩ if(aｄjaｒray[i][j］=＝1&＆！ｖisｉteｄ[j]) ﻩ {ﻩﻩﻩ printf("%d",ｊ);ﻩﻩ ﻩvisited［ｊ]＝1；ﻩﻩﻩﻩｅnqueue（＆ｑ,j）;ﻩ }ﻩ}}3.编写一个函数通过与用户交互建立一个有向图的邻接表。解:实现本题功能的算法如下：ｖｏiｄcreatｅｇraph(aｄjlｉstｇ)｛ﻩiｎte,i，s,d,n;stｒuｃtedgenodｅ*p; pｒinｔf("请输入结点数(n)和边数(e):\ｎ"）; scanf（"%d,%d",&n,&e); foｒ(ｉ=1;i＜=n；i＋+){prｉnｔf("\ｎ请输入第%d个顶点信息:"，i）;ｓcａnf("％c",&ｇ[i]．dａｔa)；g［ｉ].liｎk＝NULL;ﻩ} for(ｉ＝1;ｉ<＝ｅ;i++)ﻩ{ｐrｉnｔf("＼n请输入第%d条边起点序号，终点序号:",i)；ﻩﻩscanf("%ｄ,％ｄ",&s，＆ｄ)；ﻩ p=(strｕctedｇeｎode*)malloc(sizeｏf（edgenode)）；ﻩ p→aｄjvｅx=d; p→nｅxt=g[s]．linｋ;ﻩ ｇ[s］．liｎk=p;ﻩ}}4．编写一个无向图的邻接矩阵转换成邻接表的算法。解:本题的算法思想是：逐个扫描邻接矩阵的各个元素,如第i行第j列的元素为1，则相应的邻接表的第i个单链表上增长一个j结点。实现本题功能的算法如下:ｖｏｉdtｒansform(intaｄjaｒrａｙ［n][n],aｄｊlistadj)｛ﻩinti,j;ﻩedgenode*ｐ; for(i=０;ｉ<n;i++) {ﻩﻩａdj[ｉ]．dａta＝i;aｄj［i］．ｌink=NUＬL；}foｒ(ｉ=０;ｉ<n；i＋+) for(j＝0;j<n;ｊ+＋) ﻩ{ｉｆ（adｊarrａy［i][j]=＝1)ﻩﻩﻩ｛p=(edgenodｅ*)malｌoc(sizｅof(edgenｏde）);ﻩ ｐ→adjvex=j;ﻩ ﻩp→ｎｅｘｔ=adj[i］.link; ﻩ ａdj[ｉ]．lｉnk=p;ﻩﻩ } }}５.已知一个有n个顶点的有向图的邻接表，设计算法分别实现1）求出图中每个顶点的出度。2)求出图中每个顶点的入度。３)求出图中出度最大的一个顶点,输出其顶点序号。4）计算图中出度为0的顶点个数。解:（1）本题的算法思想是:计算出邻接表中第i个单链表的结点数，即为i顶点的出度。求顶点的出度数的算法如下:ｉntoutdegrｅe(aｄjlｉstadj,intv){iｎtdegree=0; edgｅnｏdｅ*ｐ; p=ａdｊ[v].lｉnk;ﻩwhile(p!=ＮULL）ﻩ{dｅｇｒeｅ++;ｐ＝ｐ->neｘｔ;ﻩ}retuｒndeｇreｅ;}voidpｒｉｎtout(ａdjlｉstadｊ，intn)｛ﻩinｔｉ,deｇrｅe;ﻩpriｎtf(＂Tｈeoutdegreｅsａrｅ:\n＂); for(i=0；i<n;i++)ﻩ{ﻩdeｇree＝oｕtｄｅgree（ａdj,ｉ）； ﻩpriｎtｆ("（％d,%ｄ）＂,ｉ,degｒｅe); }}（２)本题的算法思想是：计算出整个邻接表中所具有的结点为i的结点数,这就是ｉ顶点的入度。求顶点的入度数的算法：intindegree（ａdjlｉstadｊ,intn,intv)｛ intｉ，ｊ,degree;ﻩedｇenode＊ｐ； for(i＝０;i<n;ｉ++)ﻩ{ ﻩp=ａdｊ[i].lｉnk; ﻩwhile(p!=NULL){ ﻩ iｆ(p-＞ａdjvex==ｖ) ﻩdｅgreｅ++；ﻩ ﻩp＝ｐ－>next;ﻩ } }ﻩreｔurnｄｅgree;}voｉdprｉｎtin(adjlistadj，intn){ ｉntｉ,dｅgree; printf(＂Tｈｅindeｇｒeｅsａre:\n")； fｏｒ（i=0；i<ｎ;i++） {ﻩｄegｒeｅ＝ｉndegree(adj,n,i)； pｒiｎtf(＂(%d,％d)",ｉ,ｄegｒee）； }}(3）求最大出度的算法:voｉdｍａxoutdegrｅe(adｊlistadj,intn){ iｎtmａｘｄegreｅ=０,maxv=0,degｒee，i;ﻩfｏr（i=０;i＜n;i++)ﻩ{ﻩﻩｄegｒeｅ＝ｏutｄeｇreｅ(adj,ｉ)；ｉf(deｇree>mａxdegｒee) ｛ﻩﻩﻩmａxdeｇree=degree； ﻩ ｍａxv=i; ﻩ} } ｐｒintf("maxouｔdeｇrｅe=%d,ｍaxvｅrteｘ=%d",maxｄegrｅe,maxv);}(4)求出度数为0的顶点数的算法：intoｕtzｅｒo(aｄｊlｉstａdｊ，intｎ){ iｎtnum＝0,i； ｆor（ｉ=0;i<n;ｉ++） { ﻩｉf(outdｅgree(adj,i）=＝0)ﻩﻩﻩnum+＋;ﻩ} returnnum;}第六章一、基础知识题1.就如图5．21所示的树回答下面问题：1)哪个是根结点？２）哪些是叶子结点?３)哪个是E的父结点？4）哪些是Ｅ的子孙结点？５)哪些是E的兄弟结点?哪些是Ｃ的兄弟结点？6)结点B和结点I的层数分别是多少？７）树的深度是多少？8）以结点G为根的子树的深度是多少?9)树的度是多少？答:１）A是根结点２)D、H、I、J、F、G是叶子结点3)Ｂ是E的父结点4)H、I、J是E的子孙结点5）D是Ｅ的兄弟结点,B是C的兄弟结点6)B的层数是2,I的层数是47）树的深度是48）以结点G为根的子树的深度是１9)树的度是32.分别画出含3个结点的树与二叉树的所有不同形态。答：3个结点的树: 3个结点的二叉树:3.高度为ｈ的完全二叉树至少有多少个结点？最多有多少个结点?答：高度为ｈ的完全二叉树至少有个结点，最多有个结点。4.采用顺序存储方法和链式存储方法分别画出图５.２2所示二叉树的存储结构。答:该二叉树的顺序存储:该二叉树的链式存储:5.分别写出图5.22所示二叉树的前序、中序和后序遍历序列。图22答:先序遍历序列:1、2、4、７、３、5、8、6、９中序遍历序列：7、4、2、1、8、５、3、6、9后序遍历序列:7、4、2、8、５、9、６、3、１6.若二叉树中各结点值均不相同。1)已知一个二叉树的中序和后序遍历序列分别为ＧDHBAECIＦ和ＧHDBEIFCA,请画出此二叉树。2)已知一个二叉树的前序和中序分别为ＡBＣDEＦＧＨ和BDCEAFＨG,请画出此二叉树。答：7．一个二叉树如图5.２３所示,分别写出其前序、中序、后序的遍历序列。答：先序遍历序列:A、Ｂ、D、E、F、C、G中序遍历序列：D、F、Ｅ、B、A、G、C后序遍历序列:F、Ｅ、D、Ｂ、G、Ｃ、A８.输入一个正整数序列｛55,３4,18,88，1１９,１1，76,9,９７,９９,46｝,试构造一个二叉排序树。9.有一份电文中共使用5个字符：ａ、b、c、ｄ、ｅ,它们的出现频率依次为5、2、1、6、4。试画出相应的哈夫曼树,并求出每个字符的哈夫曼编码。第8题 各字符相应的哈夫曼编码如下：a:10,b:001,c：０00,d:1１,e：０1二、算法设计题答案1.一个二叉树以链式结构存储,分别给出求二叉树结点总数和叶子结点总数的算法。解：求二叉树结点总数的算法如下：iｎtCounｔNoｄｅ(btree*t,inｔnum）/＊nuｍ初值为0*／{if(t!=NULL)ﻩ{ｎｕm＋+;ﻩﻩｎum=ＣouｎtNode(t-＞lｅft,num)；ﻩﻩnuｍ=ＣoｕnｔＮoｄe(t->ｒighｔ,nｕm)； }ﻩｒetｕrnnuｍ;}求二叉树叶子结点总数的算法如下：ｉｎtＣoｕｎtLeａf(btｒee＊t,inｔnuｍ)／*nuｍ初值为0*/{if(ｔ!=NＵＬL)ﻩ{ｉf(ｔ－>ｌefｔ==NULL＆&t-＞rｉght＝=NUＬL) ﻩ nｕm＋+;ﻩ num=CｏuｎtＬeａf（t-＞left，num)；ﻩﻩnum=CｏuｎtLeaf（t->righｔ,nｕｍ);ﻩ} rｅｔurnnum;}2.2．一个二叉树以链式结构存储,写出在二叉树中查找值为x的结点的算法。解:本题可以用先序、中序和后序遍历中的任意一种遍历，只要将遍历算法中的访问根结点改为判断其值是否等于x。下面是用中序遍历求解的算法，函数返回值为ｘ的结点的地址,若没有找到则返回空。btree*seａｒｃh(btrｅe*t,ｉntx,ｂtreｅｐ)/*ｐ的初值为NULL*/{ iｆ（ｔ!＝NUＬL）{ p=search(t->left,x,ｐ); ﻩif(t－>dａta==x）ﻩﻩﻩp=t；/*找到x的地址放在ｐ中＊/ﻩ p＝ｓeａｒch(t->rｉght，x，p）;ﻩ}returnp；}３.设计一个算法将一个以链式存储结构的二叉树，按顺序方式存储到一维数组中。解:这是一个递归算法，如下:vｏidcreate(btｒｅe*t,ｉnttree[],inti)｛ if(t!=NUＬL） { ﻩtrｅe[i]=t->data; ｃrｅａｔe(t－>left,tｒｅｅ,２*i）； ﻩcｒｅａte(ｔ->rｉgｈt，tree,２*i＋1); }}4.假设二叉排序树t的各元素值均不相同，设计一个算法按递增顺序打印各元素值。解:按中序序列遍历二叉排序树即按递增顺序遍历，所以递增打印二叉排序树各元素值的函数如下:ｖoiｄiｎoｒder(btree＊t)｛ﻩｉf（t!=NULL) {ﻩﻩｉnｏrder（ｔ－>ｌｅｆt); ﻩpｒinｔf（"%ｄ＂,t->daｔa）;ﻩﻩinordｅr(t-＞righｔ）; }｝5.已知一个中序线索二叉树,试编写中序遍历的非递归算法。解:在中序线索二叉树中进行非递归中序遍历，只要从头结点出发,反复找到结点的后继,直至结束即可。在中序线索二叉树中求结点后继的算法如下:ｔｂtree＊sｕcc(tｂtree*p）{ btrｅe*q； if(p->rtａｇ==１) retｕrn（p->riｇht）;ｅlseﻩ{ q=p-＞right；ﻩ while（q->ltag=＝0) ﻩq=q－＞left; retｕrｎ(q);ﻩ｝}由此得到中序遍历线索二叉树的非递归算法如下：voidthｉｎｏrder(tbｔreｅ＊p){if(p!＝ＮULL） {wｈile(p->ｌtag==0) ﻩﻩp=p->lｅft；ﻩ do{ﻩﻩﻩｐrintf("%ｄ"，ｐ-＞ｄaｔa); ﻩﻩp＝succ(ｐ）； ｝while(ｐ!＝ＮULL）;ﻩ｝}第五章A[10][20]采用列为主序存储，每个元素占1个单元,A［０]［０]的地址为200,则A[6][1２］的地址是多少？3２62.稀疏矩阵m×n采用三元组顺序表存储结构,非零元个数ｔｕ满足什么条件时，该存储结构才故意义?tu<m*n/3３.二维数组A［10..２0]［５．.10]采用行为主序存储,每个元素占4个单元,A[10][5]的地址为1000,则A[１８][9]的地址是多少?(１20８)４.稀疏矩阵的三元组顺序表存储结构是随机存储结构吗?为什么?(不是）５.广义表((a,b，c，d）)的表头和表尾分别是什么?((a,ｂ,c,d）;空表)6.广义表(（a),((ｂ）,c)，(((d)）))的长度和深度分别是多少?(3，4)第一章数据物理结构算法二、简答一、名词解释数据:就是一切可以由计算机接受和解决的对象。数据项：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。数据元素:是数据的基本单位,在程序中作为一个整体加以考虑和解决，也称为元素、顶点或记录。它可以由若干个数据项组成。数据结构：指的是数据之间的互相关系,即数据的组织形式，它涉及数据的逻辑结构、数据的存储结构和数据的运算三个方面的内容。数据逻辑结构:是指数据元素之间的逻辑关系，是从逻辑上描述数据，与数据的存储无关,独立于计算机。数据物理结构：是指数据元素及其关系在计算机存储器内的表达，是数据的逻辑结构用计算机语言的实现，是依赖于计算机语言的。算法:是对特定问题求解环节的一种描述。它是一个有穷的规则序列,这些规则决定了解决某一特定问题的一系列运算。由此问题相关的一定输入，计算机依照这些规则进行计算和解决，通过有限的计算环节后能得到一定的输出。算法的时间复杂性:是该算法的时间花费,它是该算法所求解问题规模ｎ的函数。当n趋向无穷大时,我们把时间复杂性T（n)的数量级称为算法的渐进时间复杂性。二、简答题1.算法分析的目的是什么？答:对算法进行分析的目的有两个：第一个目的是可以从解决同一问题的不同算法中区分相对优劣，选出较为合用的一种;第二个目的是有助于设计人员考虑对现有算法进行改善或设计出新的算法。2.什么是算法的最坏和平均时间复杂性?答:算法的最坏时间复杂性是研究各种输入中运算最慢的一种情况下的运算时间；平均时间复杂性是研究同样的n值时各种也许的输入,取它们运算时间的平均值。三、答案１.三、分析下列算法的时间复杂性:1.ｓuｍ=0;for（i=1;i<=n;i++){ｓum＝suｍ+i;}答：该程序段的时间复杂性为T（ｎ)＝O(ｎ)。2．2.i=1;ｗｈile(i<＝ｎ)i=i*１0；１*10fｏr(ｊ＝0;ｊ<n;j++)答：该程序段的时间复杂性T(n)=O(ｌｏｇ10n)。3．3.ｓum＝0;for(i＝0;i＜n;i++)ﻩﻩﻩｓuｍ=sｕm+Ａrｒaｙ[i]［j];答：该程序段的时间复杂性(n)＝Ｏ(n2)。第二章一、基础知识题一、基本知识题答案1．1.试比较顺序表与链表的优缺陷。的操作。答：顺序表用结点物理位置的相邻性来反映结点间的逻辑关系，其优点是:节省存储、随机存取，当表长变化较小，重要操作是进行查找时，宜采用顺序表。链表用附加的指针来反映结点间的逻辑关系，插入和删除操作相对比较方便,当表长变化较大,重要操作是进行插入和删除时,宜采用链表。２.２.试分析单链表与双链表的优缺陷。答:双链表比单链表多增长了一个指针域以指向结点的直接前趋，它是一种对称结构,因此在已知某个结点之前或之后插入一个新结点、删除该结点或其直接后继都同样方便,操作的时间复杂度为O(1)；而单链表是单向结构,对于找一个结点的直接前趋的操作要从开始结点找起，其时间复杂度为O(n)。３.３.为什么在单循环链表中设立尾指针比设立头指针更好？答:由于对表的操作经常在表的两端进行，所以对单循环链表,当知道尾指针reaｒ后，其另一端的头指针是reaｒ->ｎeｘt->next（表中带头结点）。这会使操作变的更加容易。4.4.写出在循环双链表中的ｐ所指结点之后插入一个s所指结点答：ｓ－>prｉor=ｐ;s-＞ｎeｘt＝p-＞nｅxｔ;p－>nexｔ-＞prioｒ=ｓ;ｐ->next=ｓ；5．5．写出在单链表中的p所指结点之前插入一个s所指结点的操作。答：ｓ－＞next=p->nexｔ;p-＞ｎext=s；teｍp=p->data;p->datａ＝s－>dａtａ;ｓ－＞ｄata=teｍp;6.6．请运用链表来表达下面一元多项式A(x)＝4*ｘ＾11+9＊x＾8+1１*x^3+8*x＋7答:多项式A(x）用链表表达如下:heａd_A-->4,１１-－>9,8-－．11,３-－＞８，1－->7,０^二、算法设计题答案1.１.有一个有n个结点的单链表，设计一个函数将第ｉ－1个结点与第i个结点互换,但指针不变。解:本题的算法思想是:要使结点互换而指针不变,只要将两个结点的数据进行互换即可。实现本题功能的函数如下:voiｄeｘchange(node＊ｈeａd,inti,n）{ﻩｎodｅ*ｐ,*q;ﻩｉｎtdata; ｉf(i>n）ﻩ pｒｉntf("erｒor!\n");elｓeﻩ｛ p=heａd;ﻩﻩfｏｒ(ｉｎtj＝１；j＜i;j＋+) ｐ=ｐ->next;ﻩq=p－>ｎexｔ;ﻩdata＝q-＞daｔa；ﻩq->dａta=p－＞data; p－>dａta=data; }}２．2．设计一个函数,查找单链表中数值为ｘ的结点。解：实现本题功能的函数如下:ｖoidsearｃh(noｄe*head,intｘ）｛ﻩnｏde*ｐ；ﻩp=heaｄ; wｈｉle(p->data!=x&&p！=ＮUＬＬ)ﻩ p＝ｐ->nexｔ；ﻩif(p!=NULL)ﻩﻩprｉnｔf("结点找到了！\n＂）;ﻩeｌsｅ ﻩpｒintf("结点未找到！\n");}３..已知一个单链表,编写一个删除其值为x的结点的前趋结点的算法。解：本题的算法思想是：先找到值为x的结点*p和它的前趋结点＊ｑ,要删除*q，只需把＊p的值x放到*q的值域中,再删除结点*p即可。实现本题功能的函数如下:voiddｅleｔe（node*head,ｉntx)｛node*p,*q; q=head;ﻩp=head->ｎext;ﻩwhiｌe((p!=ＮＵLL)&&(p-＞daｔa!＝ｘ)){q=p；ﻩp=ｐ-＞neｘt；}ﻩif(p==NＵＬL） ﻩprｉnｔf("未找到x!\n＂);elｓeiｆ（q==ｈeａd)ﻩ prinｔf（"x为第一个结点，无前趋!\n＂);elsｅ{ q－>datａ＝x; q->ｎexｔ＝p->nexｔ; ｆｒee(ｐ);}｝４．4.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的lｅngth个元素。解：实现本题功能的函数如下：voiｄｄeleteleｎgth(ｎode＊ｈｅad,iｎｔｉ,ｉnｔleｎgth){nｏde*p,*q;ﻩinｔj; if(i==1) for(j=1;j<=lｅngtｈ;j++)/*删除前k个元素*/ﻩﻩ{ｐ=hｅad；／*p指向要删除的结点＊/ head=heａd->next;ﻩﻩ frｅe(ｐ);ﻩ }ﻩeｌse解：实现本题功能的函数如下：voiddeletelength(noｄｅ*hｅａd，inti，intlenｇth）｛node*p,*q;ﻩintj;ﻩif(i==1） ﻩfor(j=1;ｊ<=ｌeｎgtｈ;j++）/＊删除前k个元素*／ﻩ ｛p=heａd;/*p指向要删除的结点*/ ﻩ hｅad=head－>next；ﻩﻩﻩfrｅe（p);ﻩﻩ} elｓe{p=head; ﻩfｏr(j＝1；j＜＝i-2;j++) p＝p->ｎexｔ;/*ｐ指向要删除的结点的前一个结点＊／ﻩﻩfor(j=1;j<=length;j+＋)ﻩ ｛ ﻩq=p->next;/*q指向要删除的结点*/ﻩﻩ p->ｎext=ｑ->nｅxt; ﻩfree(q);ﻩ } }｝5．已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为ｘ的结点,使插入后该链表仍然递增有序。解：本题算法的思想是:先建立一个待插入的结点,然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置,然后插入该结点。实现本题功能的函数如下:ｖｏｉｄinsert(noｄe*head,iｎtx){ node*s，*p,*q;ﻩs=（ｎode＊)mａlloc(ｓｉzeoｆ(node))；/*建立一个待插入的结点*/ s->ｄaｔａ＝x; s－>ｎｅxt＝NULL;if(heａd=＝NＵLＬ||ｘ＜hｅad－＞dａta)／＊若单链表为空或ｘ小于第一个结点ｄata域＊／{ s->neｘt=ｈeaｄ；/＊插入到表头后面＊/ head=s; ｝ elsｅﻩ{ q=hｅad;ﻩ ｐ=q－>ｎext; ﻩwhilｅ(p!＝NULＬ&&x＞p->datａ){ ﻩﻩq=p; ﻩﻩｐ=p->neｘｔ; ﻩ｝ﻩﻩｓ-＞nｅxt=p;/*插入结点＊/ﻩﻩq->next=s;ﻩ}}6.已知一个单链表,编写一个函数将此单链表复制一个拷贝。解：本题算法的思想是依次查找原单链表(其头指针为hｅａd1)中的每个结点,对每个结点复制一个新结点并链接到新的单链表(其头指针为heaｄ2)中。实现本题功能的函数如下：voidｃopy(ｎoｄe＊heａd1，node*hｅａｄ2）{ﻩnode*ｐ,＊q，*s;ﻩheaｄ2=(ｎｏde*)maｌloc(ｓｉｚeoｆ(node)）;ﻩq=ｈeaｄ２;ｑ->ｄata=ｈeａｄ1->datａ；ｐ=heaｄ1－>ｎext; ｗｈｉle(p!=NULL) {ﻩ s=(nｏde*)malｌoｃ(sizeｏf(noｄe))；ﻩﻩｓ－＞ｄata=ｐ－>datａ;ﻩﻩq->next＝ｓ; q=ｓ;ﻩ ｐ=p->nｅｘt;ﻩ} q－>nｅxt=NＵLL；｝7.有一个共１０个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。解：本题的算法思想是：在原单链表一半处将其分开,第５个结点的neｘt域置为空，为第一个单链表的表尾。第二个单链表的表头指针指向原单链表的第6个结点。实现本题功能的函数如下,函数返回生成的第二个单链表的表头指针,第一个单链表仍然使用原单链表的表头指针。noｄe*ｄｉvidｅ（node*head1){ noｄe*head2,*pｒiｏr; heａd２=head1;ﻩfｏr(inti=１;i<＝5;i+＋) { priｏr=ｈｅad2；ﻩhｅad２=head2->nｅｘt; ｝ ｐrｉｏｒ－＞nｅxt=NULL;ﻩｒｅｔuｒnhead2;}8.与上题相同的单链表,设计一个函数，将此单链表提成两个单链表,规定其中一个仍以原表头指针heａd1作表头指针,表中顺序涉及原线性表的第一、三等奇数号结点;另一个链表以heａd２为表头指针，表中顺序涉及原单链表第二、四等偶数号结点。解:本题算法的思想是将第一个链表中的所有偶数序号的结点删除,同时把这些结点链接起来构成第二个单链表。实现本题功能的函数如下：ｖoiｄspｌit(node*heaｄ1,noｄe*hｅaｄ2)｛ node＊ｔemp,＊odd,*even;ﻩodｄ＝head1; head2＝head1-＞next； temp=ｈeａd2;ｗhiｌe（ｏdd!=ＮUＬＬ＆&ｏdd－>neｘｔ！=NULＬ) { ﻩeｖen=odd->next；／*even指向偶数序号的结点*/ﻩﻩoｄd－>ｎext＝eveｎ->nｅxt； ﻩtｅmp->ｎext=even;ﻩ tｅｍp=even；ﻩ ｏdd=odd->ｎext；/*odd指向奇数序号的结点＊/ } eｖｅn->nｅxｔ=NULL;}9.已知一个指针p指向单循环链表中的一个结点,编写一个对此单循环链表进行遍历的算法。解：本题的算法思想是：由于是单循环链表,所以只要另设一指针q指向p用来帮助判断是否已经遍历一遍即可。实现本题功能的函数如下：voidtrａvｅｌ(node*p)｛ｎodｅ*q＝p；ﻩｗｈｉle(q-＞next!=p) { priｎtf（"%4d＂,q->data）;ﻩ q=q->next; }ﻩpｒiｎｔf(＂％4d",q－＞dａｔａ）;｝1０.已知一个单循环链表，编写一个函数,将所有箭头方向取反。解：本题算法的思想是:从头到尾扫描该循环链表,将第一个结点的next域置为ＮＵLL,将第二个结点的next域指向第一个结点，如此直到最后一个结点,便用head指向它。由于是循环链表，所以鉴定最后一个结点时不能用p->next=NUＬL作为条件,而是用q指向第一个结点，以p！=q作为条件。实现本题功能的函数如下：ｖｏidiｎvｅrt（nｏｄe*heａｄ)｛ﻩnodｅ*ｐ,*q,＊r;p=head；q=p->ｎext;ﻩwhile(p!＝q) {ﻩﻩr=ｈead;ﻩ whiｌe（ｒ->next!=ｐ) ﻩ ｒ＝r-＞neｘｔ；ﻩﻩｐ->nｅxt=r；ﻩ p=ｐ->ｎeｘt;ﻩ｝ q->nexｔ=heaｄ；｝１1.在双链表中,若仅知道指针ｐ指向某个结点，不知头指针，能否根据p遍历整个链表?若能,试设计算法实现。解:能。本题的算法思想是:分别从p开始沿着next以及ｐｒioｒ向右、向左扫描直至各自的链为空即可遍历整个链表。实现本题功能的函数如下：voiｄtrａvellｉｓt(nｏdｅ＊p){nodｅ*q;ﻩq=p；ﻩwhｉｌe(ｑ！＝NUＬL)ﻩ{ pｒintf(＂%4d＂，q->ｄata）; q＝q->nexｔ;ﻩ}ｑ＝ｐ->prｉor; whilｅ(q！=NULＬ)ﻩ{ﻩﻩprintf("%４d",q->ｄata）；ﻩﻩq=q->prior;ﻩ}}12.试编写一个在循环双向链表中进行删除操作的算法,规定删除的结点是指定结点ｐ的前趋结点。解:实现本题功能的算法如下：voｉdｄｅlｅteｐｒior(nodｅ*p){ nodｅ*ｐｒi，q;ﻩｐri＝ｐ->pｒｉor;ﻩq＝pri－＞ｐrｉor;ﻩif(pri==ｐ) ﻩpｒintｆ("p结点无前趋!\ｎ")；第三章二、算法设计题习题解答(3)一、基本知识题答案1.什么是栈?什么是队列?它们各自的特点是什么?答：栈是限定在表的一端进行插入或删除操作的线性表；队列是元素的添加在表的一端进行,而元素的删除在表的另一端进行的线性表;栈的特点是后进先出，队列的特点是先进先出。2.线性表、栈、队列有什么异同?答:栈和队列都是线性表，但是是受限的线性表,对插入、删除运算加以限制。栈是只允许在一端进行插入、删除运算,因而是后进先出表；而队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表。３.简述栈的入栈、出栈操作的过程。答:栈的入栈、出栈操作均在栈顶进行，栈顶指针指向栈顶元素的下一个位置。入栈操作先将入栈元素放到栈顶指针所指示的位置上，然后将栈顶指针加１。出栈操作先将栈顶指针减1，然后从栈顶指针指向位置取值。4.在循环队列中简述入队、出队操作的过程。答：在循环队列中,设队首指针指向队首元素,队尾指针指向队尾元素后的一个空闲元素。在队列不满时,可执行入队操作,此时先送值到队尾指针指向的空闲元素,队尾指针再加１(要取模)。在队列不空时,可执行出队操作,此时先从队首指针指向处取值，队首指针再加1(要取模）。二、算法设计题答案1.设用一维数组stack[n]表达一个堆栈,若堆栈中一个元素需占用lｅｎgｔh个数组单元(lengｔh＞１),试写出其入栈、出栈操作的算法。解:用一整型变量tｏｐ表达栈顶指针，top为０时表达栈为空。假如栈不空，则从stａck［1]开始存放元素。实现本题功能的函数如下：入栈算法:voｉdＰush(ElｅＴｙｐex）{ if(（top＋ｌeｎgth)>n) ｐｒｉnｔf("上溢出＼n")；ﻩelｓe{ﻩiｆ(tｏp==0)／*为空栈*／{ ｔop++;ﻩﻩﻩstack[toｐ]=ｘ;ﻩ ｝ elseﻩ {ﻩﻩ tｏｐ=top+ｌengtｈ;ﻩ ﻩstａｃk[toｐ］=x; }ﻩ｝｝出栈算法:voidＰop（EｌeTyｐex)｛ﻩiｆ(top==0） ｐｒintf("为空栈\n"); elｓeﻩ｛ﻩﻩif（top＝=1) { x＝stack[tｏp];top--;ﻩﻩ} ｅlseﻩﻩ｛ x=stack[top]; ﻩﻩtop=ｔop-lengtｈ； }ﻩ}}2.试编写一个遍历及显示队列中元素的算法。解:设表达式在字符数组a[]中，使用一堆栈S来帮助判断。实现本题功能的函数如下:intｃorｒeｃt(cｈａｒa［]){StackＳ； ＩnｉtSｔaｃk（S）；ﻩfoｒ(i=０;i<ｓtrlｅn(a)；i+＋)ﻩﻩiｆ(a[i]==＇(')ﻩﻩ Pｕsh(S,'（'）;ﻩ elsｅif(ａ[i]==')'){ﻩ ﻩiｆ(StackEmｐty(S）) ﻩﻩrｅturｎ0； else ﻩﻩPop（S）;ﻩ } iｆ(SｔackＥｍptｙ(S)) rｅturｎ1；／＊配对对的*/ ﻩelｓereｔurｎ0；/*配对错误*/｝3．设一循环队列Queｕe,只有头指针front，不设尾指针，另设一个内含元素个数的计数器，试写出相应的入队、出队算法。解:实现本题功能的函数如下:ｖoidｔraｖel（Ｑueue,ｉnｔfrｏnt，ｒeaｒ){ﻩinｔi； foｒ（i=frｏnt；i＜=reａｒ；i＋+）{ﻩ ｐｒｉntｆ("%４d",Queuｅ[i])；ﻩ}}４.设计一算法能判断一个算术表达式中的圆括号配对是否对的。（提醒:对表达式进行扫描，凡碰到“(”就进栈,碰到“)”就退出栈顶的“(”，表达式扫描完毕时栈若为空则圆括号配对对的。)解：用一个循环数组Queue[0，ｎ－1]表达该循环队列,头指针为fｒｏnｔ，计数器cｏunt用来记录队列中结点的个数。入队算法如下:voidenquｅue(intx){ﻩｉｎttｅmp； if（count==ｎ) ﻩｐrintf("队列上溢出\n"）;ﻩelse｛ ﻩｃouｎt++;ﻩﻩｔemp＝（front+cｏｕｎt)％n; Ｑueuｅ［ｔemp]=x; }｝出队算法如下：intdｅqueue(){intｔeｍp；iｆ(coｕnt==0） priｎtf("队列下溢出\n")； eｌse ｛ｔemp=Queue［fronｔ］; froｎｔ=(frｏnt＋１)%n；count－-; ﻩｒetuｒnｔeｍp；ﻩ}}数据结构（本科)期末综合练习一（单选题）单选题１.一个数组元素a[ｉ]与(A)的表达等价。A.*（a＋i)B.a＋iC．＊a＋iD.＆a+i２.若需要运用形参直接访问实参，则应把形参变量说明为(Ｂ)参数。A.指针B.引用C.传值D.常值3.下面程序段的时间复杂度为(C)。ｆor（ｉntｉ＝0;ｉ<m;i++)ｆor（iｎtj＝0；j<ｎ;j+＋)ａ[ｉ][j］=i*j;A.O(m２)B.O（n２）Ｃ.Ｏ(m*n)D.O（m+n)4.执行下面程序段时，执行Ｓ语句的次数为（D)。for(inｔi=1；ｉ<=n;ｉ++)fｏr(intj＝１；j<=ｉ;j++)Ｓ;A．ｎ２B.n2/2C.ｎ（n＋１）D.ｎ（n+1)／25.下面算法的时间复杂度为(Ｂ)。intf(uｎsigｎｅdintn)｛ｉｆ(n==０||n＝=１)return１;elsｅreturｎn*ｆ(n－1);｝A.O（１)B.O(n)Ｃ.O(n2)D.O(n！)6.一种抽象数据类型涉及数据和（Ｂ)部分。Ａ.数据类型B．操作Ｃ.数据抽象Ｄ.类型说明7.当一个作为实际传递的对象占用的存储空间较大并也许被修改时，应最佳说明为(Ｂ),以节省参数值的传输时间和存储参数的空间。Ａ.基本类型B.引用型C．指针型D.常值引用型８.当需要进行标准I/O操作时,则应在程序文献中包含ioｓtrｅam.h头文献，当需要进行文献Ｉ／O操作时，则应在程序文献中包含(A)头文献。A.fstreａm.hB．stdlib．hC.ｉｏmanip.hD.ｓtring.h9.一个记录ｒ理论上占有的存储空间的大小等于所有域类型长度之和,事实上占有的存储空间的大小即记录长度为(Ｄ)。A.所有域长度之和Ｂ.最大域所占字节长度Ｃ．任意一个域长度Ｄ．ｓｉｚeof(ｒ)的值1０.输出一个二维数组b[ｍ][n］中所有元素值的时间复杂度为(Ｄ)。A.O（ｎ)B.O(m＋n）C.O（n２)Ｄ.O（m*n）11.一个算法的时间复杂度为(3n2+2ｎlog2n+4ｎ-７)/（5ｎ),其数量级形式的复杂度表达为（Ａ)。A.O(n)B．O（nｌｏg2n)C．O(n２）Ｄ.O(log2n)12.某算法的时间代价为T(n)=１00n+1０nｌog2n+ｎ2+10，其时间复杂度为（C)。A.O（n）B．O(nｌog2n)C.O（ｎ2)D.Ｏ(1)１3.某算法仅含程序段1和程序段2,程序段１的执行次数3n2,程序段2的执行次数为0．0１ｎ3，则该算法的时间复杂度为（C）。A.O(n)Ｂ.Ｏ(n2）C.O(n３)D.Ｏ(1)14.以下说法错误的是（Ｃ）。A.抽象数据类型具有封装性。B．抽象数据类型具有信息隐蔽性。Ｃ.使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。Ｄ.抽象数据类型的一个特点是使用与实现分离。15．在二维数组中,每个数组元素同时处在(Ｃ）个向量中。A.０个ﻩ B.１个ﻩﻩC．2个 D．n个16．多维数组事实上是由嵌套的（A）实现的。A．一维数组B.多项式Ｃ.三元组表D.简朴变量１7.在一个长度为n的顺序表中顺序搜索一个值为x的元素时,在等概率的情况下,搜索成功时的数据平均比较次数为（C）。A.nB.ｎ/2C．（n＋1)／2D.（n-1)/218．在一个长度为n的顺序表中向第ｉ个元素（0≤i≤ｎ-1)位置插入一个新元素时,需要从后向前依次后移（A)个元素。A.n-iB.n－i+1C.ｎ－i-1D．i19.在一个长度为n的顺序表中删除第ｉ个元素（０≤i≤n-1）时，需要从前向后依次前移（C)个元素。