数据结构期末考试复习总结2.pdf

《数据结构期末考试复习总结2.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试复习总结2.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构期末考试题型及分值(1)简 答 题6题*5分=30分简要回答要点。(2)分析题 6题*5分=30分给出结果(3)设 计 题1题*1 0分=10分设计思想及结果(4)编 程 题1题*1。分=1 0分完整代码(5)综 合 题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析 定义=功 能(ADT)表示=存储结构体 实现=算法(基本操作)算法分析=时间、空间复杂度考试概念有：1.数据结构 一、线性表(栈一队-列-串一数组一广义表-逻辑结构一存储结构一运算结构)二、非线性表(集 合 一 树 一 图)2.抽象数据类型 数据对象一数据关系-基本操作3.算法 性质一要求(设 计)-效 率

2、(度 量)4。实例 查找：高效查找算法排序：高效的排序算法分析题考试题目参考(1)1-23-45-6顺序建 BBST(2)6 54-32-1 顺序建 BBST数据结构复习资料一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对公 以 及 它 们 之 间 的 关 系和运算等的学科.2.数据结构被形式地定义为（D.R）,其中D 是 数据元素 的有限集合,R 是 D 上的 关系 有限集合.3.数据结构包括数据的 逻 辑 结 构、数据的存储结构 和数据的 运W 这三个方面的内容.4.数据结构按逻辑结构可分为两大类，它 们 分 别 是 线 性 结 构 和非线性结构,5.线性结构中元素

3、之间存在二对二关系，树形结构中元素之向存在一对多关系,图形结构中元素之间存在多对多关系.6.在线性结构中，第一个结点没 有 前驱结点，其余每个结点有且只有1 个前驱结点:最后一个结点 没直_后续结点，其余每个结点有且只有1个后续结点.7.在树形结构中，树根结点没有前驱 结 点,其 余 每 个 结 点 有 且 只 有 个 前 驱 结 点；叶子结点没有后续 结点,其余每个结点的后续结点数可以任意影个.8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个.9.数据的存储结构可用四种基本的存储方法表示，它们分别是顺 序、域式、索 引 和 散 列，10.数据的运算显常用的有5 种，它们分别是摘

4、入、删除*修改、中找、排序.11.一个算法的效率可分为时间 效 率 和 空 间 效率。12.在顺序表中插入或删除一个元素，需要平均移动表中一半元素,具体移动的元素个数与表长和该元素在表中的的置有关.13.线性表中结点的集合是为限 的,结 点 间 的 关 系 是 一 对 一 的.14.向一个长度为n 的向量的第i 个元素（IWiWn+l）之前插入一个元素时，需向后移动n-i+1 个元素。15.向一个长度为n 的向量中删除第i 个元素（IWiWn）时，需向前移动n-i 个元素。简答题实例2.简述顺序表和铳表存储方式的特点。答：顺序表的优点是可以随机访问数据元素，缺点是大小固定，不利于增减结点（增减

5、结点操作需要移动元索建链表的优点是采用指针方式增减结点，非常方便（只需改变指针指向.不移动结点）。其缺点是不能进行随机可问，只能顺序访问。另外，每个结点上增加指针域,造出额外存储空间增大.3.对链表设宽头结点的作用是什么？（至少说出两条好处）答：其好处行:头绪点的作用出1.空表与非空表处理一样2 结点之前操作更方便（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域,因为任何元素结点都有前驱结点（若链表没有头结束，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些兀（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表

6、与非空表的处理是一样的。设计题:(1)1.设计计算二叉树中所有结点值之和的算法。void sum(bitiee*bt.mt&s)(if(bt!=O)s=s+bt-data:siun(bt-lcluld.s);siun(bt-rcliild.s);)(2)设计在链式结构上实现简单选择排序算法。void simpleselectsorlklist(lklist*&head)(Ikhst*p.*q.*s;mt mrn.t;if(head=0|head-next=O)retiini:fbr(q=head:q!=0:q=q-next)(min=q-data:s=q;fbr(p=q-next:p!=0:p

7、=p-next)if(niuip-data)mm=p-data:s=p;if(s!=q)t=s-data:s-data=q-data:q-data=t:)三、计算题(每题6分，共 24分)数据结构试卷(-)2.请画出下图的邻接矩阵和邻接表。3.已知一个图的顶点集2,3,4,5,6,7)；E=(1,2)3,3)6,(3,4)15,2V 和 边 集 E 分别为：V=1,(1,3)5,(1,4)8,(2,5)10,(2,(3,5)12,(3,6)9,(4,6)4,用克鲁斯卡尔算法得到最小生成树,(4,7)2 0,(5,6)18,(6,7)2 5 ：试写出在最小生成树中依次得到的各条边.用克鲁斯卡尔算

8、法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)204.画出向小根堆中加入数据4,2,5,8,3 时，每加入一个数据后堆的变化。见四、阅 读 算 法(每 题 7 分，共 1 4 分)1.L i n kList mynote(L i nkL i st L)/!_ 是不带头结点的单链表的头指针if(L&L-)next)q=L：L=L ne x t;p=L；S1：w h i I e (p-)n ext)p=p-n e x t;S 2:p n e xt=q;q next=NULL;)return L;请回答下列问题：(1)说明语句S 1 的功能；

9、查询链表的尾结点(2)说明语句组S 2 的功能；将第一个结点链接到链表的尾部，作为新的尾结点(3)设链表表示的线性表为(ai,a?,，a ),写出算法执行后的返回值所表示的线性表。返回的线性表为(a2,a?,，a”a)2.vo i d ABC(BTNode*BT)if BT(ABC(BT-I e f t)：ABC(B T rig h t);cout da t a d a t a)i t e m=BS T-d a ta；/查找成功re t u rn t r ue:else if (i t e m I eft,i t e m);e I se r e turn F i n d(BST-rig h t

10、 i t em);/i f六、编 写 算 法(共 8 分)统计出单链表H L 中结点的值等于给定值X 的结点数。i nt Co u n t X(LNode*HL,ElemType x)i n t CountX(LNode*HL,ElemType x)in t i=0；LNode*p=HL；/为计数器_ wh i le(p!=NULL)_ i f (P-d a ta=x)i+;_ p=p-n ex t ;_/w h i l e,出循环时i 中的值即为x 结点个数_ret urn i;/Coun t X数据结构试卷(二)三、应 用 题(36分)1.设一组初始记录关键字序列为(45,80,48,40

11、,22,7 8),则分别给出第4 趟简单选择排序和第4 趟直接插入排序后的结果。(22,40,45,48,80,78),(40,45,48,80,2 2,78)2.设指针变量p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的 后 面 插 入 结 点B的操作序列(设双向链表中结点的两个指针域分别为II in k和r I i nk)。q11 i n k=p;q-r I ink=p-r lin k;p-r I ink-I I i nk=q；p rIi n k=q;3.设一组有序的记录关键字序列为(1 3,18,24,35,47,50,62,83,9 0),查找方法用二分查找，要求

12、计算出查找关键字6 2时的比较次数并计算出查找成功时的平均查找长度。2,A S L=9 1 *1+2*2+3*4+4*2)=25/94.设一棵树 T 中边的集合为(A,B),(A,C),(A,D),(B,E),(C,F),(C,G),要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树。树的链式存储结构略,二叉树略5.设有无向图G,要求给出用普里姆算法构造最小生成树所走过的边的集合。E=(1,3),(1,2),(3,5),(5,6),(6,4)6.设有一组初始记录关键字为(45,80,48,40,22,78),要求构造一棵二叉排序树并给出构造过程。四、算 法 设 计

13、题(16分)1.设有一组初始记录关键字序列(Ki,K2,，K),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K,.设有一组初始记录关键字序列(K“Kz,，Kn),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于R,右半部分的每个关键字均大于等于Kv o id q uick p ass(int r,i nt s,i nt t)(int i=s,j=t,x=r s;wh i I e(i(j)wh i Ie(i x)j=j-1;i f (i j)r i =r j;i=

14、i+1 ;wh ile (i j&r i x)i=i+1 ;i f (i next)f o r (q=hb;q!=0;q=q-ne x t)i f(q-data=p-da t a)b r e a k;if(q!=0)t=(I k I i st*)mall o c(s i z e o f(I k I ist);t-dat a=p-data;t-next=hc；hc=t;1)数据结构试卷(三)三、计 算 题(每 题1 0分，共3 0分)1 .已知二叉树的前序遍历序列是AEFBGCDH I K J,中序遍历序列是EFAGBCHKI J D,画出此二叉树，并画出它的后序线索二叉树.2.已知待散列的线性

15、表为(36,15,40,63,2 2),散列用的一维地址空间为0.。6,假定选用的散列函数是H (K)=K mod 7,若发生冲突采用线性探查法处理，试：H(36)=36 mod 7=1；Hi(22)=(1+1)mod 7=2;.冲突H(15)=15 m o d 7=1；。冲突 H2(22)=(2+1)m o d 7=3;Hi(15)=(1+1)mod 7=2;H (40)=40 mod 7=5;H(63)=6 3 m o d 7=0;H(22)=22 mod 7=1;冲突(1)计算出每一个元素的散列地址并在下图中填写出散列表:0 12 3 45 6求出在查找每一个元素概率相等情况下的平均查找

16、长度。6336152 2403.已 知 序 列(10,1 8,4,3,6,1 2,1,9,1 8,8)请用快速排序写出每一趟排序的结果.(8,9,4,3,6,1),10,(12,18,18)(1,6,4,3),8,(9),10,12,(18,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,1 0,12,18,181,3,4,6,8,9,10,12,18,18四、算 法 设 计 题(每 题15分，共3 0分)1.设计在单链表中删除值相同的多余结点的算法。设计在单链表中删除值相同的多余结点的算法。t y p e def i n t d a t aty p e

17、;t yp e d e f s t rue t n o de datat y p e data；s t ruct n o d e *nex t;I kIi st;void delr e d u n d ant(I kl i st*&head)(IkIi st*p,*q,*s;for(p=h e a d;p!=0;p=p n e xt)(f or(q=p-)next,s=q;q!=0;)i f(q d a t a =p-dat a)s-n e xt=qnext;f r ee(q);q=snex t;e l s e s=q,q=q next;)2.设计一个求结点x在二叉树中的双亲结点算法.设计一个

18、求结点x在二叉树中的双亲结点算法。typedef s t ruct no d e dat a t y p e d a t a；struct node*lch i Id,*rchiId;bitree;b i t ree*q 20;int r=0,f=0,f I ag=0;vo i d preor d er(bitree*bt,cha r x)(i f(bt!=0&flag=O)if(b t-da t a=x)f I a g=1 ;return;else r=(r+1)%20;q r =bt;preord e r(b t I ch i I d,x);pre o rder(b t-)r chi Id

19、,x);)vo i d pare n t(bitre e*bt,c h ar x)i n t i ;pre o rder(bt,x);f o r(i =f+1;i I chi Idda t a=x 11 qi rch i I d da t a)b r e ak;i f(f lag=0)pr i n tf(n n ot fo u nd x nH);else i f(i d ata);e I se p r int f(wnot pare n t );)数据结构试卷(四)三、计 算 题(每 题10分，共30分)1、画出广义表L S=(),(e),(a,(b,c,d)的头尾链表存储结构。LS-l|人|

20、H 一|I,|口 一 11 口 八2、下图所示的森林：(1)求 树(a)的先根序列和后根序列：(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK：B D EFC A I J K HG 林转换为相应的二叉树；(2)求森林先序序列和中序序列:ABCDEF；BDEFCA;(3)将此森林转换为相应的二叉树;D)(E)(玲(I(2)ABCDEFGHI J K;BDEFCA IJK HG 林转换为相应的二叉树;3、设散列表的地址范围是0.o 9,散列函数为H(key)=(key?+2)MOD 9,并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。H(4)=H

21、(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6四、算法设计题(每题1 0分，共30分)1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。ty p e d e f char da t a t y p e;ty p ede f s t ruct no d e datatype data;struct node*n e xt;I k

22、list;void s p I i t(I k I i st*hea d,lkl i st*&h a,I k I i st*&hb,lkl i s t*&h c)(Ik I ist*p;ha=0,hb=O,hc=O;for(p=h e a d;p!=0；p=he a d)(head=p-ne x t;pn e x t=0；if(p-)dat a=A&p-d a t a ne x t=h a;ha=p;e l s e i f(p data二O&p-)d a t a I c h i Id);s(bt-rch i Id);p=bt-Ich i Id;b t-Ichi ld=bt r chi Id;b

23、 t rchi Id=p;)3.在链式存储结构上建立一棵二叉排序树。在链式存储结构上建立一棵二叉排序树。#def ine n 1 0t yp e d e f struct n ode i n t k ey；stru c t nod e*l c h i l d,*r c h i l d；bit r e e;void bst i nse r t(bi t ree*&bt,int k ey)(i f(b t-=0)bt=(b it r ee*)m a l l o c (si zeof(b it r ee);bt key=k ey;bt-)Ichi I d=b t rch i ld=0;eIse if

24、(b t-keykey)b s tin s e r t(b t-I ch i Id,key)；else b stinse r t(bt-rchi I d,k e y);voi d crea t e b stt r ee(bitree*&b t)(i nt i;for(i=1;i I child,bt2 Ic h i I d)*ju d geb i tr e e(bt1 rchi I d,b t 2 rchi I d);)2.设计两个有序单链表的合并排序算法。设计两个有序单链表的合并排序算法。void mergelkl ist(Ik I i st*ha,Iki ist*hb,I k I i st

25、*&h c)I k I ist*s=hc=0;wh i Ie(ha!=0&h b!=0)i f(ha-data(hb)data)if(s=0)h c=s=ha;e l s e s-nex t=ha;s二 ha;ha=han ex t;else i f(s=0)h c=s=h b;e l s e s next=h b；s=h b;h b=hb n e xt;i f(ha=0 )s nex t=h b;e l s e s n e xt=ha；数据结构试卷(六)四、算 法 设 计 题(2 0分)1.设计在顺序有序表中实现二分查找的算法。设计在顺序有序表中实现二分查找的算法.s truct recor

26、d i n t key;in t o thers;i nt b i search(s tr u ct r ecord r ,i n t k)(i n t I ow=0,mid,h i gh=n-1;wh i I e(l o w lchi Id);if(m inn um)b t k e y)f lag=0 ;m i nn u m=bt-key;i n order(b t-)rchi Id);)3 o在链式存储结构上设计直接插入排序算法在链式存储结构上设计直接插入排序算法vo i d st r a i g h tin s ertsor t(Ik I i st*&h e a d)(I k I i s

27、t*s,*p,*q;i n t t;if(head=0 I|head)n ex t=0)r e t ur n;else for(q=he ad,p=hea d-n e xt;p!=0;p=q-n ex t)(f or(s=head;s!=q)next;s=s-nex t)if(s-d atapd ata)break;i f(s=q-next)q=p;e Ise qn e xt=p-nex t;p-nex t=s-n ext;s-nex t=p;t=p-da t a;p-data=s-dat a;s-d ata=t;1数据结构试卷(七)四、算法设计题(20分)1.设计在链式结构上实现简单选择排序

28、算法.设计在链式结构上实现简单选择排序算法。v o i d s i mp I e s e I e ctsor Iki i s t(I k I i s t*Ahead)(IkIist*p,*q,*s;int min,t;if(head=0 I I hea d-next=0)r e t u r n;for(q=hea d;q!=0;q=q-next)(mi n=q-d ata;s=q;fo r(p=q-next;p!=0;p=p-next)i f(mi n p dat a)(min=p-data;s=p；i f(s!=q)t=s-data;s-da t a=q-d ata;q-data=t;)2.

29、设计在顺序存储结构上实现求子串算法。设计在顺序存储结构上实现求子串算法。vo i d sub s t r ing(c h ar s ,long s t a rt,long coun t,c h ar t )(I o ng i,j,lengt h=str len(s);i f(start1 11 star t I e n gth)p r i nt f(M The c o p y positi oni s w r ong);else i f(star t+co unt_1)length)p r i n t f(M Too ch a ra c te r s tobe copi ed);else f

30、o r(i =s tar t _1,j=0 ;i keyx)level(bt Ich i Id,x);else I eve I (b t r chi Id,x);)数据结构试卷(八)四、算 法 设 计 题(20分)1.设计一个在链式存储结构上统计二叉树中结点个数的算法。设计一个在链式存储结构上统计二叉树中结点个数的算法。vo i d co untnod e(bitre e*bt,int&count)(if(bt!=0)co u nt+;co u n t n o d e(b t-I ch i Id,count);c o un t no d e(bt-rch i Id,count);)2.设计一个

31、算法将无向图的邻接矩阵转为对应邻接表的算法。设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。ty p edef s truct i nt ve r te x mJ;int edg e m m ;g adjmatrix;typedef struct node 1 int info；int a d j v e rte x;str u c t node 1 *next arc；g I i nk I i s t n ode;typ e d e f s tr u ct node2 in t verte x i nf o;g I ink I i st n ode*f ir stare;gl i n k

32、 h eadno de;v o i d adjm a tri x t oa d j I ist(gadjmatr ix g1 ,g I i nkheadnode g2)(i n t i,j;g I i n k I i s tn o de*p；f o r(i =0;i=n 1;i+)g2 i .firstar c=0;f o r (i=O ;i =n-1 ;i+)for(j=0;j a d jver t ex=j;p-n e xtarc=g i .f i r s tare;g i.firsts r c=p;p=(g I inkl is t no d e*)m a 11oc(s i z e of(

33、gI i nkI ist n ode)；p adjv ertex=i;pn e xta r c=g j 0 f irs t a r c;g jo firstar c=p;)数据结构试卷(九)五、算法设计题(20分)1.设计计算二叉树中所有结点值之和的算法.设计计算二叉树中所有结点值之和的算法。void s um(bitree*bt,int&s)(i f(bt!=0)s=s+b t-d a t a；sum(bt-lchi Id,s);s u m (bt r chi Id,s);12.设计将所有奇数移到所有偶数之前的算法。设计将所有奇数移到所有偶数之前的算法。void quickp ass(i n

34、 t r ,int s,i n t t)(i nt i =s,j=t,x=r s ;wh i I e(i j)(whi I e(i j&r j%2 =0)j=j-1;i f(ij)r i =r j;i =i+1;while(i j&r i%2=1 )i =i+1；if(i nex t=0)re t u rn(1 );elsefor(q二 head,p=hea d-next;p!=0;q=p,p=p next)if(q-d a ta)p一d ata)r e tur n(0);r e tu r n(1);)数据结构试卷(十)三、算法设计题(22分)1.设计在链式存储结构上合并排序的算法.设计在链式

35、存储结构上合并排序的算法.vo i d m e r geIkI i st(Iki is t*ha,IkI ist*hb,Iki i s t*&h c)(I kl is t*s=h c=0;while(ha!=0&hb!=0)i f(h a da t a da t a)i f(s=0)hc=s=ha;else s-next=ha;s=h a;ha=h a-)next;e l s e i f(s=0)hc=s=hb;else snext=hb;s=hb;h b=hb-n e xt;i f(h a=0)s n e xt=h b;else s next=h a;)2.设计在二叉排序树上查找结点X 的算

36、法。设计在二叉排序树上查找结点X 的算法。b it r e e*bst s earchi(b itr e e*t,i n t ke y)(b i tree*p=t;w hile(p!=0)i f(p k e y=key)r eturn(p);e Ise if(p-key ke y)p=p Ichi Id:e I se p=prchi Id;retur n(0);)3.设关键字序列(k I,k2,-,kn-l)是堆，设计算法将关键字序列(k I,k2,，kn-1,X)调整为堆。设关键字序列(kl,k2,kn-1)是堆，设计算法将关键字序列(k|,k2,，k e,X)调整为堆。v o i d ad

37、 j u s t heap(i n t r ,int n)(int j=n,i=j/2,tem p=rj-1;whi I e(i)=1)if(t e m p 二r i-1 )b r eak;elser j-1 =r i1;j=i;i =i /2;r j-1 =tem p;)数 据 结 构 试 卷（一）参考答案三、计 算 题（每 题 6 分，共 2 4 分）1.线性表为：(78,50,40,6 0,3 4,9 0)2.邻接矩阵:0 11101 0 1 0 1110 1 11 0 1 0 10 1110邻接表如图1 1 所示:3.用克鲁斯卡尔算法得到的最小生成树为:(1,2)3,(4,6)4,(1

38、,4)8,(2,5)10,(4,7)204.(1,3)5,四、读 算 法（每 题 7 分，共 14分）1.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,a,a,）2.递归地后序遍历链式存储的二叉树。五、法 填 空（每 空 2 分，共 8 分）tru e BST-le ft BSTr i ght六、编 写 算 法（8 分）i nt C o unt X(LN o de*HL,El e m T y pe x)in t i=O;LNode*p=HL；i 为计数器w hile(p!=NULL)if (P d a t a=x)i+；p=p-nex

39、 t ;/w h i I e,出循环时i 中的值即为x 结点个数r e tu r n/Cou n t X数据结构试卷（二）参考答案四、算法设计题1.设有一组初始记录关键字序列(K i,K2,-,K )，要求设计一个算法能够在。(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K：,右半部分的每个关键字均大于等于K,。void qu i ckpa s s(int r 口，int s,int t)i n*t i=s,j=t,x=r s;wh i I e(i j)whi Ie(i x)j=j-1 ;i f(i j)r i=r j：i=i+1;whi I e(i j&r ix)i

40、=i+1;i f (i n ext)if (q-data=p-data)break;i f(q!=0)t =(I k I i s t *)m a l loc(s i zeo f(Ik i i s t);t-)data=p-data;t n e xt=h c;hc=t ;)数据结构试卷(三)参考答案三、计算题1.2、H(36)=36 mod 7=1;H,(22)=(1+1)mod 7=2；.冲突H(15)=15 mod 7=1;.冲突Hz(22)=(2+1)mod 7=3；Hi(15)=(1+1)H(40)=40 mo dH(63)=63 modH(22)=22 m o d(1)0mod 7=2

41、;7=5;7=0;7=1;-o 冲突1 2345 663361522401+2+1+1+3 I,(2)A S L=-=1.654,3,6,1 ),10,(12,181 8)4,3),8,(9),10,1 2,(18.,1 8)4,6),8,9,1 0,1 2,18,(18)(4,6),8,9,1 0,12,_1_8,1 84,6,8,9,1 0,1 2,18,183、(8,9,(1,6,1,(3,1,3,1,3,四、算法设计题1.设计在单链表中删除值相同的多余结点的算法。typedef i n t dataty p e;typed e f st r u c t n o d e da tat y

42、 pe dat a;str u ct node*n e x t;I k I ist;voi d del re d undant(Iki i s t*&head)(Iki ist*p,*q,*s;for(p=h ead;p!=O ：p=p-next)(f or(q二 pnext,s=q;q!=0 ;)if(q-data-p-)data)s next=q-nex t;free(q);q=s ne x t;e I se(s=q,q=q n e x t;)2.设计一个求结点x 在二叉树中的双亲结点算法。ty p e d ef st r uct no d e dat a t yp e data;s t

43、ru c t n o de Ichi I d,*rchild;bit r ee;b i t r ee*q 20;int r=O,f=0,f lag=0;void p r e or d er(b i t ree*bt,cha r x)(i f(b t!=O&f I ag=0)i f(btd a ta=x)f lag=1 ：return;!else r=(r+1)%20;q r =b t;pre o r der(bt I chi I d,x);pre o r der(bt rch i Id,x);)void parent(bi tree*b t,c h a r x)i nt i;p reor d

44、er(bt,x);f or(i=f+1;i rchi ld-data)break;i f(fl a g=O )p r intfe Ise i f(i I chi I d dat a=x|I q(not found x n);%c ，bt d a t a);e I se pr i ntf(*not三、计算题j 111 I AE E 西 Fold2.四、算法设计题1.设单链表中有仅三类字符的数据元素（大写字母、数字和其它字符），要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符.typedef char d at a type;t yped e f st r u ct n

45、 od e da t a t y p e data;st r u c t n o de*n e x t;I kli s t：voi d s p I i t(Iki i s t*head,Iki i st&ha,Iki i s t*&hb,I k I i st*&hc)(IkI i s t*p;ha=0,hb=0,hc=0;fo r(p=h ea d;p!=0;p=head)(h e a d =p )n e x t;p next=0；i f(p d a t a =A&p d a t a n e x t=ha；h ae I se i f(p d a t a=1 01&p-d atane x t=h

46、c;he=p;)2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。t y p edef struc t n o d e i nt data;s t ruct n ode*I ch i Id,*rch i Id;b itree;void s(b i tr e e*bt)(b i t ree*p;i f(b t=0)re t ur n：s(bt I ch i Id);s(b t-rc h i Id);p=b t Ichi Id;bt-lchi ld=b t-r c h i I d;btrc h i I d=p;3.在链式存储结构上建立一棵二叉排序树。#d e f i ne n 10ty

47、p ede f st r uct nod e in t key；struc t n o de*lch i Id,*rchi Id;b it r e e;v o i d bst inser t(b i tr e e*&bt,i nt key)(i f(bt=O)b t=(bi tree*)ma I Ioc(s i z e o f(b i tre e);bt k ey二 key;b t l chi ld=b t-rc h i I d=0；e I se i f(b t-k e y k e y)b st i n s er t(bt-I ch i Id,key);e I se bst i n se r

48、t(b t-r c h i I d,k ey);)void c r e a t ebst t r ee(b i tr e e*&bt)(i nt i;f o r(i=1 ;i I ch i I d)*j u d geb i tree(bt1-r chi Id,bt2r chi I d);)2.设计两个有序单链表的合并排序算法.void mer g e I k I i st(I k I i s t*ha,Ik I i s t*h b,l k l i s t*&hc)(I k I ist*s =hc=0;whi I e(ha!=0&hb!=0)i f(h a d a ta(h b-d ata)i

49、f(s=0)hc=s=h a;e I se snext=ha;s=ha;ha=h a-)ne x t;e I se i f(s=0)h c=s=hb；else s-nex t=h b；s=h b;hb=hb-next;i f(h a=0)s-next=h b；e I se s-)n e x t =ha;)数据结构试卷(六)参考答案四、算法设计题1.设计在顺序有序表中实现二分查找的算法.s tru c t re c ord i n t k e y;int others;i nt b i s e arch(struc t r e c o r d r ,i nt k)(i n t Iow=0,mid

50、,high=n-1;whi le(l o w k e y)f Iag=0 ;m i n num=bt-k ey；i n o r der(bt-)r c h i Id);)3.在链式存储结构上设计直接插入排序算法voi d s t r a i ght i nsert s o r t (I k list*&head)(Iki i st*s,*p,*q;int t;i f(hea d=0|I he a dn e xt=0)ret u rn：e I se f o r(q=h e a d,p=headnext;p!=0 ;p=q-nex t)(for(s=he a d;s!二 q n ex t;s=s一