1、数据结构经典算法试题1 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学 1998 三、1 （5分）】LinkedList Union(LinkedList la,lb) pa=la-next; pb=lb-next; la-next=null; while(pa!=null & pb!=null) 当两链表均不为空时作if(pa-datadata) r=pa-next; pa-next=la-next; 将pa结点链于结果表中，同时逆置。la-next=pa
2、;pa=r; elser=pb-next; pb-next=la-next; 将pb结点链于结果表中，同时逆置。la-next=pb;pb=r; while(pa!=null) 将la表的剩余部分链入结果表，并逆置。r=pa-next; pa-next=la-next; la-next=pa; pa=r; while(pb!=null)r=pb-next; pb-next=la-next; la-next=pb; pb=r; 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归
3、并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】LinkedList Union(LinkedList ha, hb) ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 LinkedList la;la=(LinkedList)malloc(sizeof(LNode);la-next=ha; pa=ha; pb=hb; pre=la; while(pa&pb)if(pa-datadata) 处理ha中数据pre-next=pa;
4、pre=pa;pa=pa-next;else if(pa-datapb-data) 处理hb中数据。r=(LinkedList)malloc(sizeof(LNode); r-data=pb-data; pre-next=r;pre=r; pb=pb-next; Else 处理pa- data=pb-data; pre-next=pa; pre=pa;pa=pa-next; 两结点数据相等时，只将ha的数据链入。pb=pb-next; if(pa!=null)pre-next=pa; 将两链表中剩余部分链入结果链表。else pre-next=pb;free(la); 2）已知头指针分别为la
5、和lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将la 和 lb两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。【燕山大学 1998 五 （20分）】pa=la-next;pb=hb-next;lc=(LinkedList )malloc(sizeof(LNode);pc=lc; pc是结果链表中当前结点的前驱while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;if(pa)pc-next=pa; else pc
6、-next=pb;free(la);free(lb); 释放原来两链表的头结点。2. 设带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学 1992 二 （15分）】LinkedList Union(LinkedList ha,hb) pa=ha-next; pb=hb-next;设工作指针pa和pb。pc=ha;pc为结果链表当前结点的前驱指针。while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-
7、next;else if(pa-datapb-data)pc-next=pb;pc=pb;pb=pb-next;Else pc-next=pa;pc=pa;pa=pa-next; 处理pa-data=pb-data.u=pb;pb=pb-next;free(u);if(pa) pc-next=pa; 若ha表未空，则链入结果表。else pc-next=pb; 若hb表未空，则链入结果表。free(hb); return(ha);1）已知递增有序的两个单链表A，B分别存储了一个集合。设计算法实现求两个集合的并集的运算A:=AB【合肥工业大学 1999 五、1（8分）】解答完全同上22）已知两个
8、链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】pa=la-next;pb=lb-next; pc=la; 结果表中当前合并结点的前驱的指针。while(pa&pb)if(pa-data=pb-data) 交集并入结果表中。pc-next=pa; pc=pa; pa=pa-next; u=pb; pb=pb-next; free(u);else if(pa-datadata) u=pa;pa=pa-next; free(u);else u=pb; pb=pb-next; free(u);while(pa) u=
9、pa; pa=pa-next; free(u); while(pb) u=pb; pb=pb-next; free(u); pc-next=null; free(lb); 注： 本算法中也可对B表不作释放空间的处理3）设有两个从小到大排序的带头结点的有序链表。试编写求这两个链表交运算的算法（即L1L2）。要求结果链表仍是从小到大排序，但无重复元素。【南京航空航天大学 （10分）】pa=L1-next;pb=L2-next; pa、pb是两链表的工作指针。pc=L1;L1作结果链表的头指针。while(pa&pb)if(pa-datadata) u=pa;pa=pa-next;free(u);
10、删除L1表多余元素else if (pa-datapb-data) pb=pb-next; pb指针后移else 处理交集元素if(pc=L1) pc-next=pa;pc=pa;pa=pa-next; 处理第一个相等的元素。else if(pc-data=pa-data) u=pa;pa=pa-next;free(u); 重复元素不进入L1表。else pc-next=pa;pc=pa;pa=pa-next; 交集元素并入结果表。 whilewhile(pa) u=pa;pa=pa-next;free(u); 删L1表剩余元素pc-next=null; 置结果链表尾5）已知递增有序的单链表A
11、,B和C分别存储了一个集合，设计算法实现A：=A（BC），并使求解结构A仍保持递增。要求算法的时间复杂度为O(|A|+|B|+|C|)。其中,|A|为集合A的元素个数。【合肥工业大学 2000 五、1（8分）】LinkedList union(LinkedList A,B,C)pa=A-next;pb=B-next;pc=C-next; 设置三个工作指针。pre=A; pre指向结果链表中当前待合并结点的前驱。if(pa-datadata|pa-datadata) A中第一个元素为结果表的第一元素。pre-next=pa;pre=pa;pa=pa-next;elsewhile(pb&pc) 找
12、B表和C表中第一个公共元素。if(pb-datadata)pb=pb-next;else if(pb-datapc-data)pc=pc-next;else break; 找到B表和C表的共同元素就退出while循环。if(pb&pc) 因共同元素而非B表或C表空而退出上面while循环。if(pa-datapb-data) A表当前元素值大于B表和C表的公共元素，先将B表元素链入。pre-next=pb;pre=pb;pb=pb-next;pc=pc-next; B，C公共元素为结果表第一元素。 结束了结果表中第一元素的确定while(pa&pb&pc)while(pb&pc)if(pb-d
13、atadata) pb=pb-next;else if(pb-datapc-data) pc=pc-next;else break; B表和C表有公共元素。if(pb&pc)while(pa&pa-datadata) 先将A中小于B，C公共元素部分链入。pre-next=pa;pre=pa;pa=pa-next;if(pre-data!=pb-data)pre-next=pb;pre=pb;pb=pb-next;pc=pc-next;elsepb=pb-next;pc=pc-next; 若A中已有B，C公共元素，则不再存入结果表。 while(pa&pb&pc)if(pa) pre-next=
14、pa; 当B，C无公共元素（即一个表已空），将A中剩余链入。3. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学1996 二 (12分)】LinkedList Union(LinkedList L1,L2;int m,n)L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。本算法用最快速度将L1和L2合并成一个循环单链表。if(m0|n0) printf(“表长输入错误n”)；exit(0);if(mn) 若mnext!=L1) p=p-next; 查最后一个元
15、素结点。p-next=L2-next; 将L1循环单链表的元素结点插入到L2的第一元素结点前。L2-next=L1-next;free(L1); 释放无用头结点。处理完mnext!=L2) p=p-next; 查最后元素结点。p-next=L1-next; 将L2的元素结点插入到L1循环单链表的第一元素结点前。L1-next=L2-next;free(L2); 释放无用头结点。1）试用类Pascal语言编写过程PROC join（VAR la：link； lb：link） 实现连接线性表la和lb(lb在后)的算法，要求其时间复杂度为0（1）， 占用辅助空间尽量小。描述所用结构。【北京工业大学
16、 1997 一、1 (8分)】LinkedList Union(LinkedList la,lb)la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一个单循环链表。 q=la-next; q指向la的第一个元素结点。la-next=lb-next; 将lb的最后元素结点接到lb的第一元素。lb-next=q; 将lb指向la的第一元素结点，实现了lb接在la后。return(lb); 返回结果单循环链表的尾指针lb。2）设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学 1997
17、四（8分）】若循环单链表带有头结点，则相应算法片段如下：q=lb-next; q指向lb的头结点；lb-next=la-next; lb的后继结点为la的头结点。la-next=q-next; la的后继结点为lb的第一元素结点。free(q); 释放lb的头结点return(lb); 返回结果单循环链表的尾指针lb。其核心算法片段如下（设两链表均有头结点）q=hb-next; 单向循环链表的表头指针hb-next=ha-next; 将循环单链表最后元素结点接在ha第一元素前。ha-next=q-next; 将指向原单链表第一元素的指针指向循环单链表第一结点free(q); 释放循环链表头结点
18、。若两链表均不带头结点，则算法片段如下：q=hb-next; q指向hb首元结点。hb-next=ha; hb尾结点的后继是ha第一元素结点。ha=q; 头指针指向hb的首元结点。4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。【北京工业大学 1997 一、2 (12分)】PROC Union(VAR LA:SeqList;LB:SeqList)LA和LB是顺序存储的非递减有序线性表，本算法将LB合并到LA中，元素仍非
19、递减有序。m:=LA.last;n:=LB.last;m，n分别为线性表LA和LB的长度。k:=m+n; k为结果线性表的工作指针（下标）。i:=m;j:=n; i，j分别为线性表LA和LB的工作指针（下标）。WHILE(i0)AND(j0)DOIF LA.elemi=LB.elemjTHENLA.elemk:=LA.elemi;k:=k-1;i:=i-1;ELSELA.elemk:=LB.elemj;k:=k-1;j:=j-1;WHILE(j0) DO LA.elemk:=LB.elemj;k:=k-1;j:=j-1;LA.last:=m+n;ENDP;数据结构综合练习题一、简答题：1、简述
20、堆栈和队列两种数据类型的异同点。2、什么静态查找表和动态查找表。3、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？4、分析稳定的排序和不稳定的排序方法。5、图的存储结构有哪些？6、简述度为2的树与二叉树的区别。二、画图题1、请把下图的树的图形应用二叉链表表示法画出来。2、已知某二叉树先序序列ABCDEFG，中序序列CBEDAFG，试画出这棵二叉树。3、根据给定的连通网图，采用Prim算法思想画出下图的最小生成树。4、电文中字符A、B、C、D、E、F、G出现的概率分别为5%,25%,7%,8%,14%,23%,3%,11%；试设计对应Huffman树并给出各字符的前缀编
21、码。5、如下图表示的树的结构。将此树转换成二叉树6、根据下图所示的AOE网，试求解其关键路径。7、请对下面的无向带权图：（1）写出它的邻接矩阵。（2）按普里姆算法求其最小生成树。8对于右图所示的树： (1) 写出先根遍历得到的结点序列； (2) 写出按层遍历得到的结点序列；三、程序分析写结果：1、写出下列程序段的输出结果（栈的元素类型为 char；字符型）。Void main() Stack S; Char x,y; InitStack(S); X=c; y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x);
22、Pop(S,x); Push(S,s); While(!StackEmpty(S)Pop(S,y); printf(y); ; Printf(x);2、写出下列程序段的输出结果（队列的元素类型为 char；字符型）。Void main() Queue Q; InitQueue(Q); char x=e,y=c; EnQueue(Q,h); EnQueue(Q,r); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,a); while(!QueueEmpty(Q) DeQueue(Q,y); printf(y); printf(x);
