下载文档原格式
算法设计题打印部分假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学1998 三、1 5分】类似本题的另外叙述有1设有两个无头结点的单链表头指针分别为hahb链中有数据域data链域next两链表的数据都按递增序存放现要求将hb表归到ha表中且归并后ha仍递增序归并中ha表中已有的数据若hb中也有则hb中的数据不归并到ha中hb的链表在算法中不允许破坏。
【南京理工大学1997 四、315分】PROCEDURE mergehahb 2已知头指针分别为la和lb 的带头结点的单链表中结点按元素值非递减有序排列。
写出将la 和lb两链表归并成一个结点按元素值非递减有序排列的单链表其头指针为lc并计算算法的时间复杂度。
【燕山大学1998 五20分】 2. 图编者略中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。
两表中的元素皆为递增有序。
请写一算法求A和B的并集AUB。
要求该并集中的元素仍保持递增有序。
且要利用A和B的原有结点空间。
【北京邮电大学1992 二15分】类似本题的另外叙述有1 已知递增有序的两个单链表AB分别存储了一个集合。
设计算法实现求两个集合的并集的运算A:A∪B【合肥工业大学1999 五、18分】2已知两个链表A和B分别表示两个集合其元素递增排列。
编一函数求A与B的交集并存放于A链表中。
【南京航空航天大学2001 六10分】3设有两个从小到大排序的带头结点的有序链表。
试编写求这两个链表交运算的算法即L1∩L2。
要求结果链表仍是从小到大排序但无重复元素。
【南京航空航天大学1996 十一10分】4己知两个线性表A B均以带头结点的单链表作存储结构且表中元素按值递增有序排列。
设计算法求出A 与B的交集C要求C另开辟存储空间要求C同样以元素值的递增序的单链表形式存贮。
链表的反转与合并掌握链表反转和合并操作的实现链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
链表的反转和合并是链表操作中常见且重要的操作，在很多编程问题中都有应用。
本文将介绍链表的反转和合并操作的实现方法。
一、链表的反转链表的反转是指将链表中节点的顺序反向排列。
例如，对于链表1→2→3→4→5，反转后的链表为5→4→3→2→1。
实现链表的反转有两种常见的方法：迭代法和递归法。
1. 迭代法迭代法的实现思路是，从链表头节点开始，依次遍历每个节点，将该节点的指针指向前一个节点。
具体步骤如下：1）定义三个指针：当前节点指针cur、前一个节点指针prev、下一个节点指针next。
2）遍历链表，将当前节点的指针指向前一个节点，然后更新prev、cur和next指针的位置。
3）重复上述步骤，直到遍历到链表末尾。
以下是迭代法的实现代码示例（使用Python语言）：```pythondef reverse_list(head):prev = Nonecur = headwhile cur:next = cur.nextcur.next = prevprev = curcur = nextreturn prev```2. 递归法递归法的实现思路是，从链表的尾节点开始，依次反转每个节点。
具体步骤如下：1）递归地反转除最后一个节点外的链表。
2）将当前节点的指针指向前一个节点。
3）返回反转后的链表的头节点。
以下是递归法的实现代码示例（使用Python语言）：```pythondef reverse_list(head):if not head or not head.next:return headnew_head = reverse_list(head.next)head.next.next = headhead.next = Nonereturn new_head```二、链表的合并链表的合并是指将两个有序链表按照一定的规则合并成一个有序链表。
第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
数据结构课程设计实现两个链表的合并一、需求分析：题目：实现两个链表的合并问题描述：1. 建立两个链表A和B，链表元素个数分别为m和n个。
2. 假设元素分别为(x1,x2,…xm)，和(y1,y2, …yn)。
把它们合并成一个线形表C，使得：当m>=n时，C=x1,y1,x2,y2,...xn,yn, (x)当n>m时，C=y1,x1,y2,x2,…ym,xm,…,yn输出线性表C。
由题目的相关信息可以分析得到：首先我们需要建立两个链表AB，A链表的元素个数为m；B链表的元素个数为n；在将A\B链表进行合并，更具m和n的大小关系决定链表C的元素顺序；再将C经行直接插入排序得到一个新的链表D；最后输出ABCD的相关信息。
二、算法的流程图三、算法设计分析这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义节点，将链表的创建、计算链表的长度、链表A,B的交叉组合、链表内容升序排列、删除链表指定位置元素、删除指定的元素等算法写成了独立函数，通过主函数调用。
这样就大大精简了主函数的操作。
但主函数中很大篇幅用到了if、else语句，用以指定链表指定结点和指定元素的删除操作，这样就使得本来很精简变得繁琐，降低了程序的质量。
所以其有优点和缺点，但需要不断的改进，不断优化该程序。
四、源代码程序源代码:#include<stdio.h>#include<stdlib.h>typedef struct node //节点定义{int data;struct node *next;} node,*linklist;linklist creat(linklist head) //该函数用来创建链表{node *r,*s;int a;r = (linklist)malloc(sizeof(node));head = r;scanf("%d",&a);while(a != 0){s =(node*)malloc(sizeof(node));s->data=a;r->next=s;r=s;printf("please input a data:");scanf("%d",&a);}r->next=NULL;return head;}linklist length(linklist l) // 返回L中数据元素个数{int i=0;linklist p=l->next; // p指向第一个结点while(p){i++;p=p->next;}return i;}linklist mergel(linklist A,linklist B) //用于实现链表A,B的交叉组合 {int m,n;node *p,*q,*s,*t;linklist C;p=A->next;q=B->next;m=length(A);n=length(B);C=A;if(m<n){p=B->next;q=A->next;C=B;}while(p&&q){s=p->next;p->next=q;if(s){t=q->next;q->next=s;}p=s;q=t;}return C;}linklist sort(linklist L) //链表内容升序排列{linklist p,q,min;int temp;p=L;while( p=p->next ){q=min=p;while(q=q->next){if( q->data<min->data )min = q;}if( min!=p ){temp = p->data;p->data = min->data;min->data=temp;}}return L;}linklist Delete(linklist l,int index) //删除链表指定位置元素{ linklist p,t;int cx=1; //用于计数p=l;if(index<length(l)){while(p&&(cx<index)){t=p;p=p->next;cx++;}t->next=p->next;}elseprintf("input indext error");return l;}linklist Delete_element(linklist l,int data) //删除指定的元素{ linklist p;p=l;if(p->next){while(p->next->data!=data){p=p->next;}p->next=p->next->next;}elseprintf("don't faind the element");return l;}linklist display(linklist l) //打印{ linklist p;printf("new linklist :\n");p = l->next;while(p){printf("%d\n",p->data);p= p->next;}return l;}main(){linklist p,q,A,B,C,D;int indexs;int datas;char name;int cmd;printf("Creat linklist A:\n"); //创建A链表,并打印printf("please input a data:");A = creat(A);printf("Creat linklist B:\n"); //创建B链表,并打印printf("please input a data:");B = creat(B);C = mergel(A,B); //生成C链表，并打印 printf("linklist C\n");p = C->next;while(p){printf("%d\n",p->data);p=p->next;}D=C; //对C进行排序生成D sort(D);printf("linklist D:\n");q = D->next;while(q){printf("%d\n",q->data);q = q->next;}printf("\nplease input 0 or 1 \n");//用1和0判断是按位置删除还是直接删除元素scanf("%d",&cmd);if(cmd==0) //位置删除{printf("please input linklist name\n ");fflush(stdin);scanf("%c",&name);printf("\nplease input index \n");scanf("%d",&indexs);fflush(stdin);if(name=='A'){Delete(A,indexs);display(A);}else if(name=='B'){Delete(B,indexs);display(B);}else if(name=='C'){Delete(C,indexs);display(C);}else if(name=='D'){Delete(D,indexs);display(D);}elseprintf("nameError");}else if(cmd==1) //元素删除{fflush(stdin); //清除缓冲printf("please input linklist name\n ");//fflush(stdin);scanf("%c",&name);printf("\nplease input datas \n");scanf("%d",&datas);if(name=='A'){Delete_element(A,datas);display(A);}else if(name=='B'){Delete_element(B,datas);display(B);}else if(name=='C'){Delete_element(C,datas);display(C);}else if(name=='D'){Delete_element(D,datas);display(D);}elseprintf("name2error");}elseprintf("cmdError");printf("\nOver\n");getchar();return 0;}六、实验运行结果显示：设计体会及今后改进的意见;短短一周的数据结构课程设计结束了，回想着这一周自己的表现，感觉不是很满意，感到自己许多不足之处。
《数据结构（C语言版第2版）》（严蔚敏著）第二章练习题答案第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。
A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。
（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。
顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。
（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。
A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。
（4）链接存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。
A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。
（7）单链表的存储密度（）。
A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共20小题，共计40分）1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（）。
x=1;while (x<=n)x=5*x;A. O(log5n)B.O(n)C.O(n log5n)D.O(n5)2、顺序表和链表相比存储密度较大，这是因为（）。
A.顺序表的存储空间是预先分配的B.顺序表不需要增加指针来表示元素之间的逻辑关系C.链表中所有节点的地址是连续的D.顺序表中所有元素的存储地址是不连续的3、在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂度为（）。
A. O(n2)B.O(n)C. O(1)D.O(n log2n)4、设栈的输入序列是1、2、3、4，则（）不可能是其出栈序列。
A.1，2，4，3B.2，1，3，4C.1，4，3，2D.4，3，1，25、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（）。
A. 设置在data[0]或data[n-1]处B.设置在data[n-1]处C. 设置在data[0]处D.设置在data数组的任何位置6、在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（）来保存这些数据。
A.线性表B. 队列C. 栈D.单链表7、在环形队列中，元素的排列顺序（）。
A.与队头和队尾指针的取值有关B.与元素值的大小有关C.由元素进队的先后顺序确定D.与存放队中元素的数组大小有关8、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。
A.100B.40C.80D.559、设目标串为s，模式串为是t，在KMP模式匹配中，next[4]=2的含义是（）。
A.表示t4字符前面最多有2个字符和开头的2个字符相同B.表示s4字符前面最多有2个字符和开头的2个字符相同C.表示目标串匹配失败的位置是i=4D.表示模式串匹配失败的位置是j=210、由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为（）。
/* 链表的操作1) 定义链表的结构；2) 写函数创建链表；3) 输入两个正数链表，连接成一个非递减链表（用借助辅助链表的方法）。
*/#include<stdio.h># include <stdio.h># include <malloc.h># define null 0typedef struct LNode{int data;struct LNode *next;} LNode,*linklist;linklist creatlist (){LNode *p,*L;L=(LNode *)malloc(sizeof(LNode));L->next=null; L->data=0;while(1){p=(LNode *)malloc(sizeof(LNode));scanf("%d",&p->data);if(p->data==-1) break;++L->data;p->next=L->next;L->next=p;}return L;}void output(linklist L){LNode *p;printf("the follow is the Linklist data:\n");for(p=L->next;p!=null;p=p->next)printf("%3d",p->data);printf("\n the data is over.\n") ;}linklist sort(linklist L){int i;linklist p,q,r,s;r=(linklist)malloc(sizeof(LNode));r->next=null;for(i=0;i<L->data;i++){p=L->next;q=L->next->next;do{if((p->data)>(q->data))q=q->next;else{p=q;q=q->next;}} while(q) ;s=(linklist)malloc(sizeof(LNode));s->data=p->data;p->data=0;s->next=r->next;r->next=s;}return r;}linklist Merglist(linklist L1,linklist L2,linklist L3) {linklist p1,p2,p3;p1=L1->next;p2=L2->next;L3=p3=L1;while(p1&&p2){if(p1->data<=p2->data){p3->next=p1;p3=p1;p1=p1->next;}else {p3->next=p2;p3=p2;p2=p2->next;}}p3->next=p1?p1:p2;free(L2);return L3;}main(){linklist Lb;linklist La,Lc;La=creatlist();Lb=creatlist();La=sort(La);Lb=sort(Lb);output(La);output(Lb);Lc=Merglist(La,Lb,Lc);output(Lc);getch();}。
1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
输入: 1 2 5 6 83 4 7 9 10输出: 10 9 8 7 6 5 4 3 2 1测试数据输入：7 9 10 118 12 13 14输出：14 13 12 11 10 9 8 7链表翻转2.带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。
两表中的元素皆为递增有序。
请写一算法求A和B的并集AUB。
要求该并集中的元素仍保持递增有序。
且要利用A和B的原有结点空间。
输入: 1 2 5 6 82 5 7 9输出: 1 2 5 6 7 8 9测试数据输入：7 9 10 118 9 10 11输出：7 8 9 10 113. 知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。
要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。
4. 顺序结构线性表LA与LB的结点关键字为整数。
LA与LB的元素按非递减有序，线性表空间足够大。
试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。
高效指最大限度的避免移动元素。
5. 已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。
请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。
要求链接过程中不得使用除该链表以外的任何链结点空间。
6. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。
7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。
编一PASCAL 过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。
精品文档考试教学资料施工组织设计方案数据结构（C语言版）（第2版）课后习题答案李冬梅2015.3目录第1章绪论 (1)第2章线性表 (5)第3章栈和队列 (13)第4章串、数组和广义表 (26)第5章树和二叉树 (33)第6章图 (42)第7章查找 (54)第8章排序 (65)第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
