工大数据结构作业

数据结构与算法上机作业第二章线性表、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。A.O(log2n) B.O(1)C.O(n) D.O(n2)2、以下关于线性表的说法中，不正确的是 。A.线性表中的数据元素可以是数字、字符、结构等不同类型B.线性表中包含的数据元素个数不是任意的C.线性表中的每一个结点都有且只有一个直接前驱和直接后继(单项链表)D.存在这样的线性表：表中各结点都没有直接前驱和直接后继(数组实现)3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为 。A.O(1)B.O(n)C.O(n2) D.O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为A.nB.(n-1)/2C,n/2D.(n+1)/2已经有N个点了，再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.i的取值服从1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为。A.nB,n/2C.(n+1)/2D,(n-1)/26、在顺序表中，只要知道 ，就可以求出任一结点的存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小TOC\o"1-5"\h\z7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 。A.nB.2n-1C.2nD.n-18、线性表采用链表存储时其存储地址要求 。A.必须是连续的 B.部分地址必须是连续的C.必须是不连续的 D.连续的和不连续的都可以9、下面关于线性表的描述中，错误的是 。A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一片连续的存储单元D.线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O(1)B.O(n)C.O(n2) D.O(log2n)11、语句是 。A.HL=p;p->next=HL;C.p->next=HL;p=HL;A.HL=p;p->next=HL;C.p->next=HL;p=HL;D.p->next=HL->next;HL->next=p;HL为链表的头指针。HL指示链表中第一个节点的存储位置，在表头插入一个由指针p指向的节点后，头指针指向p，p的指针域指向原链表中第一个节点12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是p=q->next;p->next=q->next;p=q->next;q->next=p;p=q->next;q->next=p->next;q->next=q->next->next;q->next=q;顺序进入一个栈结构的站台，下列不可能的出栈顺13、设有编号为1,2,3,4的4辆列车，序为。顺序进入一个栈结构的站台，下列不可能的出栈顺A.1234B,1243C,1324D,1423至少有14种。①全进之后再出情况只有1种：4,3,2，1②进3个后再出的情况有3种3,4,2,1 3,2,4,13,2,1,4③进2个后再出的情况有5种2,4,3,12,3,4,1 2,1,3,42,1,4,32,1,3,4④进1个后再出的情况，有5种1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,314、4个元素按A,B,C,D顺序进入S栈，执行两次Pop(S,x)运算后，栈顶元素的值是一。A.AB.BC.CD.D15、从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 命令。A.x=top;top=top->next; B.top=top->next;x=top->data;C.x=top->data; D.x=top->data;top=top->next;16、向顺序栈中输入元素时 。A.先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素C.谁先谁后无关紧要 D.同时进行17、设有一个顺序栈，元素A,B,C,D,E,F依次进栈，如果6个元素出栈的顺序是B,D,C,F,E,A，则栈的容量至少为。A.3B.4C.5D.6顺序如下A入栈B入栈然后B出栈,C入栈D入栈,D出栈,C出栈,E入栈,F入栈,F出栈,E出栈.栈里元素最多时候就是acd和aef,所以3个就够了18、设已将元素A,B,C依次入栈，元素D正等待进栈。那么下列4个序列中不可能出现的出栈顺序为。CADBB.CBDAC.CDBAD.DCBA19、栈和队列的相同之处是 。A.元素的进出满足先进后出 B.元素的进出满足后进先出C.只允许在端点进行插入和删除操作 D.无共同点栈Insert(L,n+1,x)Delete(L,n)而栈只允许在表尾一端进行插入和删除队列Insert(L,n+1,x)Delete(L,1)队列只允许在表尾一端进行插入，在表头一端进行删除20、设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈，一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,el,则栈S的容量至少应该是 。A.6B.4C.3D.2设栈长度为s,起始为0因为栈后进先出，队列先进先出.又因为元素E1..E6是顺序入栈,那么分析过程如下：按照出栈过程分析,因为给定出栈顺序：E2,E4,E3,E6,E5,E1,E2要进栈，所以E1必须进栈，进栈顺序：E1,E2,所以s为2下面E2出栈,打印出E2,剩余结果为E4,E3,E6,E5,E1,因为E2出栈了，所以当前栈容量为2,但是只是用了1个，存放E1,下面继续E3进栈,E4进栈，此时s为3,根据出栈结果，那么E4出栈,E3出栈,此时栈容量为3但是只有E1在栈中，剩余结果为E6,E5,E1,同理,E5进栈,E6进栈，此时栈被填满,容量为3,后E6出栈,E5出栈,E1出栈，栈空溶量为3.所以S的容量至少为3.21、队列通常采用的两种存储结构是()。A.顺序存储结构和链式存储结构 B.散列方式和索引方式C.链表存储结构和线性存储结构 D.线性存储结构和非线性存储结构22、循环队列SQ队满的条件是 。A.SQ->rear==SQ->front B.(SQ->rear+1)%MAXLEN==SQ->frontSQ->rear==0 D.SQ->front==0队空:Q.front=Q.rear队满:(Q.rear+1)%MAXQSIZE=Q.front23、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为。A.5和1B.4和2C.2和4D.1和5TOC\o"1-5"\h\z24、链栈与顺序栈相比，有一个较为明显的优点是 。A.通常不会出现满栈的情况 B.通常不会出现栈空的情况C.插入操作更加方便 D.删除操作更加方便25、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32,头指针front=15,则当前循环队列的元素的个数为 。A.42B.16C.17D.4126、串是一种特殊的线性表，其特殊性体现在 。A.可以顺序存储 B.数据元素是一个字符C.可以链式存储 D.数据元素可以是多个字符27、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为 。A.O(m)B,O(n)C,O(m+n)D,O(mXn)28、已知串S="abab"，其Next数组值为。A.0123B.0121C.0112D.012229、若字符串"ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为 。A.20%B.40%C.50%D.33.3%存储密度;结点数据本身所占的存储量/结点结构所占的存储量 1/(1+3)30、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是 。p->Prior=q;q->Next=p;p->Prior->next=q;q->Prior=q;p->Prior=q;p->Prior->next=q;q->next=p;q->Prior=p->Prior;q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;q->Prior=p->Prior;q->Next=q;p->Prior=q;p->Next=q;TOC\o"1-5"\h\z31、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是 。A.0,0 B,0,n-1C,n-1,0D.n-1,n-132、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作(称为输出受限的双端队列)，若a,b,c,d,e元素依次进队，则不可能得到的顺序是 。A.bacdeB.dbaceC.dbcaeD.ecbad33、在双向链表中间插入一个结点时，需要修改修改个指针域。A.1B.2C.3D.434、在按行优先顺序存储的三元组表中，下述陈述错误的是 。A.同一行的非零元素，是按列号递增次序存储的B.同一列的非零元素，是按行号递增次序存储的C.三元组表中三元组行号是非递减的D.三元组表中三元组列号是非递减的35、在稀疏矩阵的三元组表示法中，每个三元组表示 。A.矩阵中非零元素的值B.矩阵中数据元素的行号和列号C.矩阵中数据元素的行号、列号和值D.矩阵中非零数据元素的行号、列号和值36、对特殊矩阵采用压缩存储的目的主要是为了。A.表达变得简单 B.对矩阵元素的存取变得简单C.去掉矩阵中的多余元素D,减少不必要的存储空间TOC\o"1-5"\h\z37、广义表是线性表的推广，它们之间的区别在于 。A.能否使用子表 B.能否使用原子项C.表的长度 D.是否能为空38、已知广义表(a,b,c,d)的表头是 ，表尾是 。A.aB.()C,(a,b,c,d)D,(b,c,d)39、下面说法不正确的是 。A.广义表的表头总是一个广义表 B,广义表的表尾总是一个广义表C.广义表难以用顺序存储结构表示 D.广义表可以是一个多层次的结构40、若广义表A满足Head(A)=Tail(A)，则A为。A.()B.(())C.((),())D.((),(),())二、填空题1、线性表中结点的集合是有限的，结点之间的关系是一对一 关系。2、顺序表中访问任一个结点的时间复杂度为—0(1) 。3、线性表中第一个结点没有直接前驱，称为 头 结点。4、在一个长度为n的顺序表中删除第i个元素，要移动—n-i 个元素。5、在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移—n-i-1一个元素，在插入操作中，移动元素的均值为 （n+1）/2。6、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单向链表和双向链表7、链式存储的特点是利用指针 来表示数据元素之间的逻辑关系。8、静态链表（线性表的游标实现）是指用数组下标 表示单链表的指针。9、在静态链表中，一般都有一个变量available表示的结点链，其中的结点为空闲结点。10、在栈中，可进行插入和删除操作的一端称 栈顶 。11、在进栈运算时，应先判别栈是否一满—。在出栈运算时应先判别栈是否_空—。当栈中元素为n个时，进栈运算时发生上溢，则说明该栈的最大容量为—n 。12、设有一空栈，现有输入序列为1,2,3,4,5,经过push,push,pop,push,pop,push,push,pop,pop之后，输出序列为2354。13、对于循环向量的循环队列，求队列长度的公式为 （rear-front+n+1）%n14、栈的逻辑特点是先进后出 。队列的逻辑特点是先进先出两者的共同特点是只允许在它们的 端点 出插入和删除数据元素，区别是TOC\o"1-5"\h\z栈在栈顶进行插入删除，队列在两端操作，队尾插入，队首删除 。15、链队列LQ为空时，LQ->front->next=NULL.16、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为 front.next==rear 。17、设串S="Ilikecomputer"，T=“com”，则ULength（S）=13。Index（S,T）= 6。18、在KMP算法中，next用只与—王—串有关，而与主串 无关。19、字符串“ababaab”的Next数组值是, 011234220、稀疏矩阵一般压缩存储的方式有三种，分别是三原组存储、行指针链表和十字链表21、二维数组M中每个元素的长度是3字节，行下标i从0〜7,列下标j从0〜9,从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放，元素M[7][5]的起始地址为 M[0][0]+225 ；若按列优先方式存放，元素M[7][5]的起始地址为M[0][0]+14122、广义表(a,(a,b),d,e,((i,j),k))的长度是■—5 ，深度是_3_23、设广义表A(((),(a,(b),c))),则Cal(Cdr(Cal(Cdr(Cal(A))))=(b)三、写一个算法合并两个已排序的线性表。（用两种方法：数组表示的线性表（顺序表）和指针表示的线性表（链表））要求：1、定义线性表节点的结构，并定义节点的型和位置的型。2、定义线性表的基本操作3、在1,2的基础上，完成本题。4、在main函数中进行测试：先构建两个有序的线性表，然后合并这两个线性表。四、已知一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1,2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。五、写出从一个带表头的单链表中删除其值等于给定值x的结点的算法函数：intdelete(LIST&L,intx);如果x在该链表中，则删除对应结点，并返回其在链表中的位置(逻辑位置，第一个结点的逻辑位置为1)，否则返回-1。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。三，四，五#include<iostream>usingnamespacestd;typedefintelementtype;/^素类型structcelltype//链表节点{elementtypeelements;celltype*next;);typedefcelltype*LIST;typedefcelltype"position;//线性表的“型”与位置的“型”相同positionEnd(LISTL)〃返回L中指向最后一个节点的指针{positionp;p=L;while(p->next!=NULL)p=p->next;returnp;)voidInsert(elementtypex,positionp,LIST&L)//创建元素x的节点插在p的后面{positionqq=newcelltypeq->elements=xq->next=p->nextp->next=q)〃时间复杂性：O(1)positionLocate(elementtypex,LISTL)//i返回元素x在线性表中的位置{positionpp=Lwhile(p->next!=NULL)if(p->next->elements==x)returnpelsep=p->next;returnp)〃时间复杂性：O(n)elementtypeRetrieve(positionp,LISTL){return(p->next->elements);)〃时间复杂性：O(1)voidDelete(positionp,LIST&L)/删除位置p的下一个节点{positionqif(p->next!=NULL){q=p->nextp->next=q->nextdeleteq))〃时间复杂性：O(1)positionPrevious(positionp,LISTL)//返回位置p的前驱元素{positionqif(p==L->next)8a<<"不存在前驱元素！"<<endl;else{q=Lwhile(q->next!=p)q=q->nextreturnq})〃时间复杂度O(n)positionNext(positionp,LISTL)/返回位置p的后驱元素{positionqif(p->next==NULL)cout<<"不存在后继元素！"<<endl;else{q=p->next;returnq}}〃时间复杂度O(1)positionMakeNull(LIST&L){L=newcelltypeL->next=NULL;returnL}〃时间复杂性：O(1)positionFirst(LISTL){returnL;}〃时间复杂性：O(1)voidTravel(LISTL)/遍历线性表元素{positionpp=L->nextwhile(p!=NULL){cout<<p->elements<<endl;p=p->next}}〃=================================================voidMerge(LIST&L,LISTL1,LISTL2)〃合并两个线性表(链表)，将L1,L2合并到L中(positionp1=0,p2=0,p3=0;for(p3=L1;p3;p3=p3->next)(p1=newcelltype;p1->elements=p3->elements;If(L==0)(L=p1;p2=p1;)else(p2->next=p1;p2=p1;))for(p3=L2;p3;p3=p3->next){p1=newcelltype;p1->elements=p3->elements;if(L==0){L=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}〃==============================================〃复制链表voidcopy(LIST&L1,LISTL2){positionp1=0,p2=0,p3=0;for(p3=L2;p3;p3=p3->next){p1=newcelltype;p1->elements=p3->elements;If(L1==0){L1=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}//=====================================================//删除指定元素的节点intDelete(LIST&L,intx)(intm=1;//指定元素在线性表中的位置positionp1=0,p2=0;if(L->elements==x){p1=L;L=L->next;deletep1;returnm;)else{p1=p2=L;while(p1->elements!=x&&p1->next!=NULL){p2=p1;m++;p1=p1->next;)p2->next=p1->next;deletep1;returnm;)return-1;//不存在元素x}voidRead(LIST&L,inti)//输入数据{cout<<"请输入第"<<1<<"个线性表"<<endl;LISTp1=0,p2=0;elementtypex;for(;;){cout<<”请输入数据(-1作为结束标志):"；cin>>x;if(x==-1)break;p1=newcelltype;p1->elements=x;if(L==0){L=p1;p2=p1; }else{p2->next=p1;p2=p1;}}p2->next=NULL;}voidWrite(LISTL)//输出{positionp=L;for(;p;p=p->next)cout<<p->elements<<'\t';cout<<endl;}voidmain()(cout<<"本次测试的类型为int"<<endl;LISTL=NULL,L1=NULL,L2=NULL;Read(L1,1);cout<<"L1的元素为："<<endl;Write(L1);Read(L2,2);cout<<"L2的元素为："<<endl;Write(L2);Merge(L,L1,L2);cout<<"L1,L2合并后L的元素为："<<endl;Write(L);/*LISTL=NULL,L1=NULL;read(L);cout<<"原有的元素："；write(L);copy(L1,L);cout<<"复制之后的元素：”；write(L1);LISThead=NULL;read(head);cout<<"删除前：";write(head);cout<<"请输入要删除的数据:";Elementtypex;cin>>x;intm=Delete(head,x);cout<<"删除后："；write(head);if(m==-1)cout<<"需要删除的数不存在"<<endl;elsecout<<"需要删除的数是第"<<m<<"个"<<endl;*/}〃线性表的数组实现-线性表的合并#include<iostream>usingnamespacestd;#definemaxlength100typedefintposition;/4位置类型typedefintElementtype;//下标类型structLIST(Elementtypeelements[maxlength];intlast;//最后一个元素的下标};positionEnd(LISTL)〃线性表的长度(return(L.last+1);)voidInsert(Elementtypex,positionp,LIST&L)/在表L的位置p处插入x(positionq;if(L.last>=maxlength-1)cout<<"listisfull"<<endl;elseif((p>L.last+1)||(p<1))cout<<"positiondoesnotexist"<<endl;else{for(q=L.last;q>=p;q--)L.elements[q+1]=L.elements[q];L.last=L.last+1;L.elements[p]=x;))voidDelete(positionp,LIST&L)//删除位置p处的元素{positionq;if((p>L.last+1)||(p<1))cout<<"positiondoesnotexist"<<endl;else{L.last=L.last-1;for(q=p;q<=L.last;q++)L.elements[q]=L.elements[q+1];})positionLocate(Elementtypex,LISTL)/返回x在表L中的位置{positionq;for(q=0;q<L.last;q++)if(L.elements[q]==x)returnq;return(L.last+1);//x不存在}ElementtypeRetrive(positionp,LISTL)/返回L中位置为p的元素{if((p<1)||(p>L.last+1)){cout<<"positiondoesnotexist"<<endl;return-1;}returnL.elements[p];}//======================================================//将两个线性表合并voidMerge(LIST&L,LISTL1,LISTL2){positionp,p1,p2;positionlen1=End(L1);//L1的长度positionlen2=End(L2);//L2的长度L.last=len1+len2-1;/^并后L的最后一个元素的位置p=p1=p2=0for(;p1<len1;)//#L1的元素写进L{L.elements[p]=L1.elements[p1];p++;p1++;}for(;p2<len2;)//继续将L2的元素写进L{L.elements[p]=L2.elements[p2];p++;p2++;})voidRead(LIST&L,inti)//输入线性表{cout<<"请输入第"<<1<<"个线性表的长度:";cin>>L.last;L.last--;cout<<"请输入第"<<1<<"个线性表的元素："<<endl;for(positionp=0;p<=L.last;p++)cin>>L.elements[p];}voidWrite(LISTL)//输出线性表{cout<<"线性表的长度为："<<End(L)<<endl;cout<<"线性表的元素为："<<endl;for(positionp=0;p<=L.last;p++)cout<<L,elements[p]<<'\t';cout<<endl;}voidmain(){cout<<"本次测试的类型为int"<<endl;LISTL,L1,L2;Read(L1,1);Read(L2,2);Merge(L,L1,L2);Write(L);}六、写出一个将两个静态链表(属于同一个存储池)合并的算法函数：voidMerge(cursorM,cursorN);合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置(position)和游标(cursor)的型。2、定义静态链表的基本操作：voidInitialize();初始化，将所有存储池中的结点设置为空闲；cursorGetNode();从空闲链中获取一个结点；voidFreeNode(cursorq);将结点q加入到空闲链；voidInsert(elementtypex,positionp,cursorM);在链表M中的位置为p的元素后面添加一个值为x的结点；voidDelete(cursorM,positionp);在链表M中删除位置为p的元素的后一个元素。3、在1、2的基础上完成本题。4,在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。#include<iostream>usingnamespacestd;#definemaxsize100typedefintelementtype;typedefstruct{elementtypeelementintnext}spacestr;/*结点类型*/spacestrSPACE[maxsize]/*存储池*/typedefintposition,cursor;cursoravailable;/*标识线性表/空闲池*/voidInitialize(){intj;/*依次链接池中结点*/for(j=0;j<maxsize-1;j++)SPACE[j].next=j+1;SPACE[j].next=-1;/*最后一个接点指针域为空*/available=0;/*标识线性表，将所有存储池中的结点设置为空闲，avilable为头结点，不利用*/}//可用空间的分配操作，从空闲链中获取一个结点cursorGetNode()//q=newspacest{cursorp;if(SPACE[available].next==-1)p=-1;else{p=SPACE[available].nextSPACE[available].next=SPACE[p].next}returnp;}/*将空闲池头结点的下一个节点从空闲池中删除*/voidFreeNode(cursorq)//deleteq;{SPACE[q].next=SPACE[available].nextSPACE[available].next=q}/*将q指向的节点放回池中*///在位置p后面插入元素值为x的结点voidInsert(elementtypex,positionp){positionqq=GetNode()SPACE[q].element=xSPACE[q].next=SPACE[p].nextSPACE[p].next=q}//删除位置p后的一个结点voidDelete(positionp){positionq；if(SPACE[p].next!=-1){q=SPACE[p].next；SPACE[p].next=SPACE[q].next；FreeNode(q)}}〃创建静态链表voidCreate(cursorM){elementtypeinput;positionp=M;while(1)(cout<<"请输入静态链表的值，输入-1结束："<<endl;cin>>input;if(input!=-1)(Insert(input,p);p=SPACE[p].next;)elsebreak;))voidMerge(cursorM,cursorN)〃连接两个链表，将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中(positionp;p=M;while(SPACE[p].next!=-1)p=SPACE[p].next;positionq;q=SPACE[N].next;SPACE[p].next=q;FreeNode(N);)〃输出静态链表voidPrint(cursorM){positionp;p=M;while(SPACE[p].next!=-1){cout<<SPACE[SPACE[p].next].element<<'\t';p=SPACE[p].next;}cout<<endl;}voidmain(){spacestrs;Initialize();positionp=GetNode();cursorM=GetNode();SPACE[M].next=-1;cursorN=GetNode();SPACE[N].next=-1;cout<<"创建静态链表M："<<endl;Create(M);Print(M);cout<<"创建静态链表N："<<endl;Create(N);Print(N);cout<<"#M和N合并后："<<endl;Merge(M,N);Print(M);)七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：A(x)=atem+axem_1+...+ax)m m-1 1其中，系数叫，0，指数ei满足em>em1>...>e2>e1>=0。要求：1、定义多项式每一项的结构。。2、定义两个多项式的相加和相乘运算函数。3、在main函数中，构建两个多项式，并测试相加和相乘运算。#ifndefPOLYNOMIAL_H#definePOLYNOMIAL_H#include<stdlib.h>#include<stdio.h>#include<float.h>〃链表结构typedefstructNode{structNode*next;doublecoefficient;intexponent;}Node,"Polynomial; 〃链表初始化voidinitList(Polynomial*L){ 〃头结点if(NULL==*L){*L=(Polynomial)malloc(sizeof(Node));(*L)->coefficient=0.0;(*L)->exponent=-1;(*L)->next=NULL;}else{8a<<"表已经存在！"；}} 〃判断指数同否intcompareExponent(PolynomialnodeA,PolynomialnodeB){inta=nodeA->exponent;intb=nodeB->exponent;if(a==b)return0;)else(returna>b?1:-1;))〃系数判断boolisZeroByCoefficient(Polynomialnode)(if(node->coefficient>=-LDBL_EPSILON&&node->coefficient<=LDBL_EPSILON)(returntrue;)else(returnfalse;))//判断2〃系数判断boolisZeroByDouble(doublea)(if(a>=-LDBL_EPSILON&&a<=LDBL_EPSILON)(returntrue;else(returnfalse;)) 〃尾插法建表voidcreatListByTail(Polynomial*L,intn)(〃头结点if(NULL==*L)(*L=(Polynomial)malloc(sizeof(Node));(*L)->coefficient=0.0;(*L)->exponent=-1;(*L)->next=NULL;Polynomialtail=NULL;Polynomialptr=*L;//初始化？if(NULL==(*L)->next)(Cout<<"请按照指数升幕，连续的输入项的系数(double)和指数6nt)：(中间 空格隔开)"<<endl;〃循环建表for(inti=0;i<n;i++)(tail=(Polynomial)malloc(sizeof(Node));tail->next=NULL;scanf("%lf%d",&tail->coefficient,&tail->exponent);while(getchar()!='\n')(continue;)//链接ptr->next=tail;〃移动指针ptr=ptr->next;〃尾结点))else(Cout<<"表已经建立！"<<endl;))else(Cout<<"表头已经存在！"<<endl;))〃遍历voidtraverseList(PolynomialL)(Polynomialptr=L->next;inti=1;while(ptr!=NULL)(Cout<<”一元多项式的第％4项：%gXA%d\n"<<i<<ptr->coefficient<<ptr->exponentendl;i++;ptr=ptr->next;))〃求最高阶数intgetMaxExp(PolynomialL)(Polynomialptr=L;while(ptr->next!=NULL)(ptr=ptr->next;)returnptr->exponent;}〃删除结点，删除L中ptr指向的结点voiddeleteNode(PolynomialL,Polynomialptr)(Polynomialp=L;while(p->next!=ptr)(p=p->next;}ptr=p->next;p->next->next=ptr->next;free(ptr);ptr=NULL;165}〃多项式相加，本质是链表的归并算法〃可以另外开辟空间，也可以使用已存在的空间存储，这里使用后者的算法voidaddPolynomial(PolynomialLA,PolynomialLB){〃不再开辟内存Polynomiala=LA->next;Polynomialb=LB->next;PolynomialLC=LB;Polynomialtail=LC;while(a!=NULL&&b!=NULL){〃判断指数的关系a>b?1:-1else0switch(compareExponent(a,b)){case1:tail->next=b;tail=tail->next;b=b->next;break;case-1:tail->next=a;tail=tail->next;a=a->next;break;default:doubletemp=a->coefficient+b->coefficient;//0？if(isZeroByDouble(temp))a=a->next;b=b->next;〃删除deleteNode(LC,tail->next);)else(tail->next=b;tail=tail->next;b->coefficient=temp;a=a->next;b=b->next;}//endofif}//endofswitch}//endofwhile〃一表比完if(NULL==a)(tail->next=b;}else(tail->next=a;}//endofiffree(LA);LA=NULL;}〃多项式相乘voidmulPolynomial(PolynomialLA,PolynomialLB,PolynomialLC)(Polynomiala=LA->next;Polynomialb=LB->next;Polynomialc=LC;Polynomialptr=NULL;〃两多项式的阶数intnumA=getMaxExp(LA);intnumB=getMaxExp(LB);〃结果多项式的阶数intmaxNum=numA+numB;〃动态开辟数组空间double*receive=(double*)malloc((maxNum+1)*sizeof(double));〃为数组赋值for(inti=0;i<maxNum+1;i++)//i相当于指数，数组值就是相应指数的系数receive[i]=0.0;)〃指数及数组下标intexpBylndex=0;//顺次扫描Awhile(a!=NULL){//A不空，顺次扫描Bwhile(b!=NULL){〃两项做乘法之后的指数和expByIndex=a->exponent+b->exponent;〃系数之间做乘，结果保存到对应的指数下(下标)，receive[expByIndex]+=(a->coefficient)*(b->coefficient);b=b->next;)b=LB->next;a=a->next;}//endofwhile〃数组保存的是全部项，两两分别乘法之后的结果，保存在对应的下标(数组位置)for(inti=0;i<maxNum+1;i++){//0？if(isZeroByDouble(receive[i])){//notdosth}else{〃生成结点ptr=(Polynomial)malloc(sizeof(Node));〃接到LC表c->next=ptr;c=c->next;〃赋值c->coefficient=receive[i];c->exponent=i;}//endofif}//endofforc->next=NULL;}〃链表销毁voiddestroyList(Polynomial*L){Polynomialptr=NULL;while(*L!=NULL)ptr=(*L)->next;free(*L);*L=ptr;)//*L=NULL;cout<<"销毁完毕"endl;)#endif八、试编写一个整数进制转换的通用函数convert(intnum,STACKS,intn),要求将整数m转换为n进制数，n进制数的各位依次存放在栈S中。并在主函数中进行测试。要求：1、定义栈以及栈的型。2、定义栈的各种操作。3、实现函数converto4、在main函数中，通过调用函数convert将num的n进制数存放到一个栈中，并通过出栈的方法输出该n进制数〃栈的数组实现〃此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素#include<iostream>usingnamespacestd;#definemaxlength100//栈的容量typedefintElementtype;structSTACK//定义整型线性数组栈(inttop;Elementtypeelements[maxlength];);boolisEmpty(STACKS)//栈是否为空(if(S.top>=maxlength)returntrue;elsereturnfalse;)voidmakeNull(STACK&S)//栈置空(S.top=maxlength;)Elementtypetop(STACKS)/返回栈顶元素(if(isEmpty(S))cout<<"栈为空！"<<endl;elsereturn(S.elements[S.top]);)voidpop(STACK&S)//出栈,删除栈顶元素(if(isEmpty(S))cout<<"栈为空！"<<endl;elseS.top++;)voidpush(STACK&S,Elementtypex)/进栈(if(S.top==0)8a<<"栈已满！"<<endl;else(--S.top;S.elements[S.top]=x;))voidconvert(intnum,STACK&S,intn)/进制转换函数(while(num!=0)(push(S,num%n);num/=n;))voidprint(STACKS)//输出转后的结果(while(!isEmpty(S))(cout<<S,elements[S.top];++S.top;)cout<<endl;)voidmain()(STACKS;makeNull(S);intnum=1024;intn=2;cout<<"转化前的十进制数为："<<num<<endl;cout<<"转化后的"<<n<<"进制数为："；convert(num,S,n);print(S);)九、设有一个循环队列Queue,只有头指针front,不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。要求：1、定义相应的循环队列的型(只有头指针，没有尾指针，但有一个元素个数的计数器)；2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法；3、在main函数验证算法的正确性。〃没有尾指针的队列，但有一个计数器，所以尾指针rear可以用头指针表示出来#include<iostream>usingnamespacestd;#definemaxlength20typedefintelementtype;structQUEUE(elementtypeelements[maxlength];intfront;intcountJ/元素个数计数器：rear=(front+count-1)%maxlength);intaddone(inti)//指针后移(return((i+1)%maxlength);)boolisEmpty(QUEUEQ)//队列是否为空(if(Q.count==0)returntrue;elsereturnfalse;)boolisFull(QUEUEQ)〃队列是否已满(if(Q.count==maxlength)returntrue;elsereturnfalse;)elementtypefront(QUEUEQ"/返回队头元素(if(isEmpty(Q))returnNULL;elsereturn(Q.elements[Q.front]);)voidenQueue(elementtypex,QUEUE&Q)//队列后插入一个元素，入队(if(isFull(Q))cout<<"队列已满"<<endl;else(Q.count++;Q.elements[(Q.front+Q.count-1)%maxlength]=x;))voiddeQueue(QUEUE&Q)〃删除队头元素，出队(if(isEmpty(Q))cout<<"队列为空"；else(Q.front=addone(Q.front);Q.count--;))voidprint(QUEUEQ)for(intj=0;j<Q.count;j++)cout<<Q.elements[(Q.front+j)%maxlength]<<"\t";cout<<endl;)voidmain()(QUEUEQ;Q.front=0;Q.count=0;for(inti=1;i<10;i++)enQueue(i,Q);cout<<"队头："<<front(Q)<<endl;print(Q);for(i=0;i<6;i++)deQueue(Q);cout<<"删除前六个元素后的队列："<<endl;print(Q);)十、设主串T="abcaabbabcabaacbacba“，模式为p="abcabaa”。1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟匹配过程(可参照教材P61从第8行开始的内容)；3、不需要编写程序。Nextval：abcabaa0110132第一趟匹配：i=5,j=5abcaabbabcabaacbacbaabcab(匹配失败)第二趟匹配：i=5,j=1abcaabbabcabaacbacbaabc(匹配失败)第三趟匹配：i=7,j=1abcaabbabcabaacbacbaa(匹配失败)第四趟匹配：i=8,j=1Abcaabbabcabaacbacbaabcabaa匹配成功！十一、假设表达式中允许包含三种括号：圆括号、方括号和大括号。设计一个算法采用顺序栈(用数组表示的栈)判断表达式中的括号是否正确配对。要求：1、定义栈以及栈的型，栈中所存放元素的类型为字符型，定义枚举类型Boolean，其中两个元素分别为TRUE和FALSE。2、定义栈的各种操作。3、定义函数Booleancheck(char*s);判断s中的括号是否正确配对，如果正确配对，返回TRUE，否则返回FALSEo4、在主函数中验证所编写函数的正确性。〃栈的数组实现〃此处将栈底规定在数组的底部，即让maxlength-1指向栈底的第一个元素#include<iostream>usingnamespacestd;#definemaxlength100〃栈的容量//typedefintElementtypel/数制转换中元素类型为inttypedefcharElementtype;/^号匹配中元素类型为字符型charenumBoolean{TRUE,FALSE};structSTACK//定义整型线性数组栈{inttop;Elementtypeelements[maxlength];};boolisEmpty(STACKS)//栈是否为空{if(S.top>=maxlength)returntrue;elsereturnfalse;}voidmakeNull(STACK&S)//栈置空{S.top=maxlength;}Elementtypetop(STACKS)//返回栈顶元素if(isEmpty(S))returnNULL;elsereturn(S.elements[S.top]);)voidpop(STACK&S)//出栈,删除栈顶元素(if(isEmpty(S))cout<<"栈为空！"<<endl;elseS.top++;)voidpush(STACK&S,Elementtypex)/进栈(if(S.top==0)8a<<"栈已满！"<<endl;else(--S.top;S.elements[S.top]=x;))〃==================================数制转换voidconvert(intnum,STACK&S,intn)/进制转换函数(while(num!=0)(push(S,num%n);num/=n;))voidprint(STACKS)//输出转后的结果(while(!isEmpty(S))(cout<<S,elements[S.top];++S.top;)cout<<endl;//=================================括号匹配Booleancheck(char*s)(STACKS;makeNull(S);intj=0;while(s[j]!='\0')(switch(s[j])(case'(':push(S,'(');break;case')':if(top(S)=='(')pop(S);elsereturnFALSE;break;case'[':push(S,'[');break;case']':if(top(S)=='[')pop(S);elsereturnFALSE;break;case'{':push(S,'{');break;case'}':if(top(S)=='{')pop(S);elsereturnFALSE;break;}j++;}if(isEmpty(S))returnTRUE;elsereturnFALSE;)voidmain(){/*STACKS;makeNull(S);intnum=1024;intn=2;cout<<"转化前的十进制数为："<<num<<endl;cout<<"转化后的"<<n<<"进制数为："；convert(num,S,n);print(S);*/char*s="{((ab)b[cf])}";char*p="{{(sd)asdf{}]”;if(check(s)==TRUE)cout<<"{((ab)b[cf])}括号匹配！"<<endl;elsecout<<"{((ab)b[cf])}括号不匹配！"<<endl;if(check(p)==TRUE)cout<<"{{(sd)asdf{}]括号匹配！"<<endl;elsecout<<"{{(sd)asdf{}]括号不匹配！"<<endl;}十二、设有一个带头结点的双向链表h,设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。要求：1、定义带头结点的双向链表的型DLISTo2、定义双向链表DLIST的基本操作。3、定义函数intswap(elementtypex,DLIST&h)，查找第一个元素之为x的结点，如果在链表中存在元素值为x的结点，并其与其前驱结点进行交换，并返回1,否则返回0o4、在主函数中测试所编写函数的正确性。〃带头结点的双向链表h,设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行交换。#include<iostream>usingnamespacestd;typedefintElementtype;structcelltype{ElementtypeelementJ/数据域celltype*previous,*next;//前驱和后驱);typedefcelltype"positionJ/位置的型typedefcelltype*DLIST;//双向链表的型〃插入元素，在p后面插入voidinsert(positionp,Elementtypex)(if(p->next){positionq=newcelltype;q->element=x;q->next=p->next;q->previous=p;p->next->previous=q;p->next=q;)else{positionq=newcelltype;q->element=x;q->next=p->next;q->previous=p;p->next=q;))〃删除中间结点voidDelete(positionp){if(p->next!=NULL&&p->previous!=NULL)〃删除的不是头尾结点{p->previous->next=p->next;p->next->previous=p->previous;deletep;)elsecout<<"不能删除头尾结点！"<<endl;)voidcreate(DLIST&head)//创建双向链表{head->previous=NULL;//让头结点的前驱指向自己head->next=NULL;positionp=head;intx=0,i=1;while(1){cout<<"请输入第"<<1++<<"个插入的元素(输入-1结束创建)："<<endl;cin>>x;if(x!=-1){insert(p,x);p=p->next;)elsebreak;))voidprint(DLISThead)//输出链表元素{positiontemp=head;while(temp->next){temp=temp->next;cout<<temp->element<<'\t';)cout<<endl;)intswap(Elementtypex,DLIST&head)//查找交换{positiontemp,L;temp=head;while(temp->next){temp=temp->next;if(temp->element==x&&temp->previous!=head)//元素匹配并且前驱不能是头结点{L=temp->previous;L->previous->next=temp;temp->previous=L->previous;L->next=temp->next;temp->next->previous=L;L->previous=temp;temp->next=L;return1;))return0;voidmain()(DLISThead=newcelltype;create(head);print(head);Elementtypex;cout<<"请输入你想查找的元素："<<endl;cin>>x;if(swap(x,head))(cout<<"查找交换成功！"<<endl;print(head);)elsecout<<"查找失败！"<<endl;)十三、试编写一个求三元组顺序表示的稀疏矩阵对角线元素之和的算法十四、当具有相同行值和列值的稀疏矩阵A和B均以三元组顺序表方式存储时，试写出矩阵相加的算法，其结果存放在以行逻辑链接顺序表方式存储的矩阵C中。十三，十四算法分析：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。〃三元组表示的稀疏矩阵对角线元素相加，以及稀疏矩阵相加#include<iostream>usingnamespacestd;#defineNumVertices6/稀疏矩阵非零元素个数structnode{introwJ/行intcol;〃列intdata;//值);typedefnodetripleJ/三元组voidInput(triple2[])//输入三元组(cout<<”请输入系数矩阵的行、列数和非零元素个数："<<endl;cin>>a[0].row>>a[0].col>>a[0].data;if(a[0].row!=a[0].col)cout<<"请注意您输入的系数矩阵不是n阶矩阵，无法求对角元素的和！"<<endl;for(inti=1;i<=a[0].data;i++)(cout<<"请以按行优先的规则依次输入第<々<<个非零元素的下标和值："<<endl;cin>>a[i].row>>a[i].col>>a[i].data;))voidInit(triplea[])//初始化三元祖(a[0].row=4;a[0].col=4;a[0].data=6;a[1].row=0;a[1].col=0;a[1].data=50;a[2].row=1;a[2].col=0;a[2].data=10;a[3].row=1;a[3].col=2;a[3].data=20;a[4].row=3;a[4].col=0;a[4].data=-30;a[5].row=3;a[5].col=2;a[5].data=-60;a[6].row=3;a[6].col=3;a[6].data=5;)intFind(triplea[],introw,intcoly/判断三元组A所标示的稀疏矩阵是否存在下标[row][col]的非零元素，存在的话返回该非零元素(for(inti=1;i<=a[0].data;i++){if(a[i].row==row&&a[i].col==col)returna[i].data;)return0;)intSum(triplea[])//求对角矩阵对角元素的和{inti,sum=0;if(a[0].row!=a[0].col)cout<<"此稀疏矩阵不是n*n矩阵，无法求对角元素和"<<endl;elsefor(i=1;i<=a[0].data;i++)if(a[i].row==a[i].col11a[i].row+a[i].col==a[0].row-1)sum+=a[i].data;returnsum;)voidPrint(triple*a)//输出三元组(for(intj=0;j<=a[0].data;j++)cout<<a[j].row<<'\t'<<a[j].col<<'\t'<<a[j].data<<endl;)voidPrintMT(triple*a)//输出三元组所表示的稀疏矩阵(fo