有两张单调递增有序的线性表A和B-采用顺序存储结构-将这两张表合并成C表-要求C表单调递减有序。Wo

一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。

A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。

A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。

A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。

D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。

A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。

A )。

A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。

第一章测试1【单选题】(2分)图书馆的数目检索系统采用关系的数据结构。

A.树形B.图状C.集合D.线性2【单选题】(2分)是相互之间存在一种或多种特定关系的数据元素的集合。

A.数据项B.数据结构C.数据元素D.数据3【单选题】(2分)（）是一个值的集合和定义在这个值集上的一组操作的总称。

A.数据项B.数据类型C.数据元素D.数据结构4【单选题】(2分)算法的确定性是指（）A.算法中没有逻辑B.在任何情况下，算法不会出现死循环C.算法中的每一条指令必须有确切的含义D.当输入数据非法时，算法也能作出反应或进行处理第二章测试1【单选题】(2分)线性表中的数据元素有一个前驱多个后继。

A.错B.对2【单选题】(2分)用顺序结构存储，删除最后一个结点时，（）A.其它B.会移动其它结点位置C.可能会移动其它结点位置D.一定不会移动其它结点位置3【单选题】(2分)链表中逻辑上相邻的元素的物理地址__________相邻。

A.一定不B.必定C.其它D.不一定4【单选题】(2分)1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。

//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头A->next=qa;}else{qb=pb;pb=pb->next;()//将当前最小结点插入B表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}A.qa->next=A->nextB.qa->next=A;C.qb->next=A->nextD.qb->next=A;5【单选题】(2分)假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

第2部分习题解析第1章绪论1.1选择题1. 算法的时间复杂度取决于（C）A）问题的规模 B）待处理数据的初态 C） A和B【答案】C2.计算机算法指的是解决问题的步骤序列，它必须具备（B）这三个特性。

A）可执行性、可移植性、可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性【答案】B5．从逻辑上可以把数据结构分为（C）两大类。

A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构【答案】C6．在下面的程序段中，对x的赋值的语句频度为（C）for(i=0;i<n;i++)for(j=0;j<n;j++) x=x+1;A） O(2n) B）O(n) C．O(n2) D．O(log2n)【答案】C7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（D）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；A. O（n）B） O(nlog2n) C） O(n3) D） O(n2)【答案】D1.2填空题2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。

【答案】（1）集合（2）线性结构（3）树形结构（4）图状结构或网状结构4．数据结构中评价算法的两个重要指标是_____________。

【答案】算法的时间复杂度和空间复杂度。

5. 数据结构是研讨数据的_____________和_____________，以与它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。

【答案】（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。

实验报告课程名称：数据结构实验名称：线性表班级：学生姓名：学号：指导教师评定：签名:题目：有两张非递增有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C为非递减有序的，然后删除C表中值相同的多余元素。

一、需求分析⒈本演示程序根据已有的两张表的信息，实现两张表的合并及删除值相同元素的操作，需要用户输入学生的信息。

⒉在演示过程序中，用户输入需要合并的顺序表，即可观看合并结果。

⒊程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Stack {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2,…n≥0}基本操作:init(list *L)操作结果：构造一个空的线性表L。

ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1≤i≤ListLength(&L)操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。

Less_EquaList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。

LocateElem(List *La,ElemType e,int type)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。

MergeList(List *La,List *Lb,List *Lc)初始条件：非递减线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。

数据结构合并两个顺序表合并两个顺序表是在数据结构中常见的操作之一，本文将介绍如何合并两个顺序表，并给出相应的算法实现。

顺序表是一种线性表的存储结构，它使用连续的存储空间存储元素，并按照顺序存放。

合并两个顺序表的意思是将两个顺序表中的元素按照一定的顺序合并到一个新的顺序表中。

假设有两个顺序表A和B，它们的长度分别为m和n。

要合并这两个顺序表，可以使用以下步骤：1. 创建一个新的顺序表C，用于存放合并后的结果。

2. 首先将顺序表A中的元素复制到顺序表C中，保持元素的顺序不变。

3. 然后将顺序表B中的元素依次插入到顺序表C中的合适位置。

插入的位置可以根据需要进行调整，可以选择插入到顺序表C的末尾，也可以选择按照某种规则插入。

4. 最后，顺序表C中的元素就是合并后的结果。

在实现合并两个顺序表的算法时，可以使用两个指针分别指向顺序表A和顺序表B的元素。

比较指针指向的元素大小，然后将较小的元素插入到顺序表C中，并将对应的指针向后移动一位。

重复这个过程，直到遍历完两个顺序表中的所有元素。

下面是一个具体的算法实现示例：```void merge(SeqList A, SeqList B, SeqList C) {int i = 0; // 指向顺序表A的指针int j = 0; // 指向顺序表B的指针int k = 0; // 指向顺序表C的指针// 将顺序表A中的元素复制到顺序表C中while (i < A.length) {C.elements[k++] = A.elements[i++];}// 将顺序表B中的元素插入到顺序表C中while (j < B.length) {int x = B.elements[j++];// 找到插入位置int insertPos = 0;while (insertPos < k && C.elements[insertPos] < x) { insertPos++;}// 将元素插入到合适位置for (int m = k; m > insertPos; m--) {C.elements[m] = C.elements[m - 1];}C.elements[insertPos] = x;k++;}C.length = k; // 更新顺序表C的长度}```这个算法的时间复杂度为O(m+n)，其中m和n分别为顺序表A 和顺序表B的长度。

上机实验的目的、要求和评分标准一、实验目的上机实践是各位对本门课程所学知识的一种全面、综合的能力训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节，也是对课堂教学与实践教学效果的一种检验。

通常，实验题中的问题比平时的习题复杂得多，也更接近实际。

实验着眼于原理与应用的结合，使你们学会如何把书上学到的知识运用于解决实际问题的过程中去，培养从事软件开发设计工作所必需的基本技能；另一方面，能使书上的知识变“活”，起到深化理解和灵活掌握教学内容的目的。

平时的练习较偏重于如何编写功能单一的“小”算法，而实验题是软件设计的综合训练，包括问题分析（需求分析）、总体结构设计和用户界面设计（概要设计）、程序设计基本技能和技巧等，即一整套软件工程规范的训练和科学作风的培养。

此外，还有很重要的一点是：机器是比任何教师都严厉的主考者。

为了达到上述目的，本课程共安排了10个实验单元，各单元的训练重点在于基本的数据结构，而不强调面面俱到。

各实验单元与教科书的各章具有紧密的对应关系。

二、要求：⒈做好每一次上机前的准备以提高上机效率：①预先认真阅读相关实验内容，做到心中有明确的目的要求和任务，要有备而来，应该自己独立的思考和设计你的算法和程序，并争取在规定的时间内如期完成上机工作任务。

对于个别目前基础较差的同学，实在是没法完成任务的建议你先参考其他同学的算法，勤学好问，最终自己独立完成，以增强你的感性认识，强化你的实践基础，提高你的实践能力。

②按照实验内容规定的习题题目，事先在实验预习报告上编写好源程序及运行程序所需的典型数据，并经人工静态检查认为无误；手编程序应书写整齐，应在每个题目之间留出一定的空间，以备记录上机调试情况和运行结果等；对程序中自己有疑问的地方，应作出记号，以便上机时给以注意。

③将想要上机验证的问题草拟提纲；制定一个简捷的程序调试计划。

⒉上机时输入和调式自己所编写的程序。

对“出错信息”，应善于自己分析判断，并充分利用开发工具提供的错误信息和调试手段解决出现的问题，及时修改与完善算法、源程序，随时记录有价值的内容。

两个顺序链表的合并【openjudge】总时间限制: 2ms内存限制: 1024kB描述已知两个线性单链表A和B中的元素以递增有序排列（数据长度和元素由键盘输⼊），编写算法将A表和B表归并成⼀个按元素值递增的有序表C，并要求利⽤原表（即A和B表的）节点空间存储表C。

再输⼊链之前，先要输⼊链的长度样例输⼊61 3 6 7 12 135-1 3 8 10 15样例输出-1 1 3 3 6 8 9 10 12 13 15提⽰只有⼀组测试数据，不需要循环重复输⼊搞了N久，才搞出来的，发现了不少⾃⾝的问题。

后来参考了⽹上的代码。

但是那个代码有点错误，坑爹呢，⾃⼰⼜边调试边改正。

最初想交叉合并的，但是发现太难了。

后来直接⽤插⼊排序的思想吧。

即便知道了插排，实现起来还是困难。

感觉数据结构这个东西，技巧性太强了。

有很多时候，即使你有思想，也实现不了，或许这是语法基础的⽋缺吧。

不写了，要上思修了。

后天放五⼀，所以这周末补课。

#include <stdio.h>#include <malloc.h>typedef struct Lnode{int data;struct Lnode *next;}LNode,*Linklist;LNode *A,*B,*p;void Initlist(Linklist *L){*L=(LNode *)malloc(sizeof(LNode));(*L)->next=NULL;}void Inselem(LNode *L,int n){int x,i;LNode *s,*p;p=L;for(i=0;i<n;i++){scanf("%d",&x);s=(LNode *)malloc(sizeof(LNode)); s->next=NULL;s->data=x;p->next=s;p=s;}}void Mergelist(LNode *a,LNode *b){Linklist p,q,s,t;int x;p=a->next;q=a;s=b->next;t=b;while(p!=NULL&&s!=NULL){while(p->data<=s->data){q=p;p=p->next;if(p==NULL)goto end;}q->next=s;while(p->data>s->data) {t=s;s=s->next;if(s==NULL)goto end;}t->next=p;}end:if(p==NULL)q->next=s;if(s==NULL)t->next=p;}int main(){int n,m;Initlist(&A);Initlist(&B);scanf("%d",&n);Inselem(A,n);scanf("%d",&m);Inselem(B,m);Mergelist(A,B);p=A->next;while(p!=NULL){printf("%d ",p->data); p=p->next;}return 0;}。