算法2-1：集合union【线性表】 Description 假设利用两个...

算法2-2：有序线性表的有序合并【线性表】 Description 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列，现要求将 LA 和 LB 归并为一个新的线性表 LC， 且 LC 中的数据元素仍然按值非递减有序排列。例如，设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,5,6,8,8,9,11,11,15,20) 算法描述如下： 从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针 i 和 j 分别指向LA和LB中某个元素，若设 i 当前所指的元素为 a，j 所指的元素为 b，则当前应插入到 LC 中的元素 c 为 c = a < b a b i j LC LA LB br/>图：有序列表有序插入算法 Input 有多组测试数据，每组测试数据占两行。第一行是集合A，第一个整数m（0< m="100）代表集合A起始有m个元素，后面有m个非递减排序的整数，代表A中的元素。第二行是集合B，第一个整数n(0<=n<=100)代表集合b起始有n个元素，后面有n个非递减排序的整数，代表b中的元素。每行中整数之间用一个空格隔开。output 2 3 5 6 7 8 9 11 15 每组测试数据只要求输出一行，这一行含有 m+n 个来自集合 a 和集合b 中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。 sample input4 20sample output2>

算法5-5：有向无环图的拓扑排序【图】 Description 由某个集合上的一个偏序得到该集合上的一个全序，这个操作被称为拓扑排序。偏序和全序的定义分别如下： 若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。 由偏序定义得到拓扑有序的操作便是拓扑排序。 拓扑排序的流程如下： 1. 在有向图中选一个没有前驱的顶点并且输出之； 2. 从图中删除该顶点和所有以它为尾的弧。 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。 采用邻接表存储有向图，并通过栈来暂存所有入度为零的顶点，描述拓扑排序的算法 在本题中，读入一个有向图的邻接矩阵（即数组表示），建立有向图并按照以上描述中的算法判断此图是否有回路，如果没有回路则输出拓扑有序的顶点序列。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个整数，如果为1，则表示第i个顶点有指向第j个顶点的有向边，0表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。 Output 如果读入的有向图含有回路，请输出“ERROR”，不包括引号。 如果读入的有向图不含有回路，请按照题目描述中的算法依次输出图的拓扑有序序列，每个整数后输出一个空格。 请注意行尾输出换行。 Sample Input4 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0Sample Output3 0 1 2 HINT 在本题中，需要严格的按照题目描述中的算法进行拓扑排序，并在排序的过程中将顶点依次储存下来，直到最终能够判定有向图中不包含回路之后，才能够进行输出。 另外，为了避免重复检测入度为零的顶点，可以通过一个栈结构维护当前处理过程中入度为零的顶点。

【Test-9-2】下面算法的功能是：编写一个递归算法实现在有序顺序表上的折半查找。算法的参数表中应增加两个形参 left 和 right，分别指定算法在本层执行时的查找区间的左、右端点。当查找成功时函数返回查找到的元素的存放位置；当查找不成功时函数返回-1。 请在空白处填入正确的语句。 递归算法的首部为 int binarySearch ( seqList &L, DataType x, int left, int right )。主程序的调用方式为 { int loc = binarySearch( L, x, 0, L.n-1 )。 int binarySearch(seqList &L, DataType x, int left, int right) { //在查找区间[left..right]采用折半查找算法查找与给定元素匹配的元素。 int mid = ________①_______; if(__________②_______) { mid = (left + right) / 2; if(________③_________) mid = binarySearch1(L, x, _____④_______, right); //右缩区间 else if(x < data[mid]) mid = binarySearch(L, x, left, ______⑤_______); //左缩区间 } return _______⑥_________; };

实验一 线性表一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。 3. 掌握使用 C++面向对象的程序设计技术，设计数据结构源程序的方法。二、实验内容 1. 线性表的顺序存储表示（结构）及实现。 阅读下列程序请注意几个问题。 （1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vector）”。在下列类设计中，采用静态一维数组elem[]表示向量,同时用length表示线性表长度。 ElemType elem[MAXSIZE]; int length; (2)在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。 l 源称序结构： 见本资料的第1页。 l 数据结构类定义（包括成员函数的定义）的程序代码 对于小型程序，这部分代码可以直接放入源称序之中，如上图所示。 对于复杂较大的程序，这部分代码可以生成一个头文件（例如Sqlistc.h）与源程序文件存储在同一个文件夹中。再在源程序之中写入一个语句，如下： #include “Sqlistc.h”; l 主函数 在学生没有学习可视化图形界面之前，建议在主函数中简单设计一个“菜单”(do-while循环内嵌套一个 switch结构)。随着学习的深入，应该学会熟练使用“菜单”技术，这样会明显提高编程和运行效率。一个主函数一般样式如下： int main( ) { //声明程序所需要的一般变量 int i,k; ElemType e,x; //声明和创建类对象，这个类往往是典型数据结构类 Sqlist as; System.out.print（"\n ） 线性表顺序存储结构演示"; Scanner s = new Scanner(System.in); do{ //显示菜单内容 System.out.print（"\n\n" ） ; System.out.print（"\n\n 1. 初步建立一个线性表 " ） ; System.out.print（"\n\n 2. 插入一个数据元素" ） ; System.out.print（"\n\n 3. 删除一个元素，返回其值 " ） ; System.out.print（"\n\n 4. 结束程序" ） ; System.out.print（"\n********************************" ） ; System.out.print（"\n请输入你的选择(1,2,3,4)" ） ; Int n = s.nextInt(); //接收用户的选择 //根据k值，转向对应的case 分支程序段执行 switch(n) { case 1:{ as.SetData(); as.PrintOut(); }break; case 2:{ System.out.print（"\n\n 插入的位置，数据 i,e=?"）; Int i = s.nextInt(); Int e = s.nextInt(); as.Insert(i,e); as.PrintOut(); }break; case 3:{ System.out.print（"\n 删除第几个元i=?"）; Int i = s.nextInt(); x=as.Delet(i); System.out.print（" 元素数值= "）; as.PrintOut(); }break; default:break; } //switch }while(k>=1&&k<4); system.out.print（"\n 再见!"）; 按任意键，返回。"）; _getch(); return 0; } ----------------------------------------------->

【单选题】

A、必有一个向量可以表为其余向量的线性组合

B、必有两个向量可以表为其余向量的线性组合

C、必有三个向量可以表为其余向量的线性组合

D、每一个向量可以表为其余向量的线性组合

A、m+n

B、min(m,n)

C、max(m,n)

D、无法确定

请完成下列算法，将两个非空有序链表L1和L2逆序合并至新链表L。（20分） 例如给定两个有序链表（默认升序）： 3->4->6 和 2->7->9，逆序合并的结果是：9->7->6->4->3->2 单链表的类型定义如下： typedef struct node { ElemType element; struct Node *link; }Node; typedef struct { Struct node * first; int n; }SingleList; SingleList* ReversedMerge(SingleList *L1, SingleList*L2, SingleList* L) { Init(L);//假设L非空，初始化新链表L Node* p1 = L1->first; Node* p2 = L2->first; while(__________(1)___________) { Node* p = L->first; if(p1->element<=p2->element) { Node * q = (Node*)malloc(sizeof(Node)); q->element =______(2)_____; q->link = ____(3)____; ________(4)________; p1 = p1->link; } else { Node * q = (Node*)malloc(sizeof(Node)); q->element = ________(5)_________; q->link = p; L->first = q; p2 = p2->link; } } while(p1!=NULL) { Node * q = (Node*)malloc(sizeof(Node)); q->element = p1->element; q->link = p; L->first = q; p1 = p1->link; } while(p2!=NULL) { Node * q = (Node*)malloc(sizeof(Node)); q->element = p2->element; q->link = p; L->first = q; p2 = p2->link; } return &L; }

A. 线性表顺序存储结构可以随机存取表中任一元素

B. 线性表链式存储结构只能顺序存取表中任一元素

C. 线性表顺序存储结构在插入或删除某一元素时，需要移动大量元素

D. 线性表链式存储结构在插入或删除某一元素时，不需要移动大量元素

此题为判断题(对，错)。