工大数据结构第二章作业

数据结构与算法上机作业第二章 线性表一、选择题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. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是 。A. nB. 2n-1C. 2nD. n-18、线性表采用链表存储时其存储地址要求 。A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是 。A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链式存储，不必占用一片连续的存储单元D. 线性表采用链式存储，便于插入和删除操作10、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 A. O(1)B. O(n)C. O(n2)D. O(log2n)11、 语句是 。A. HL=p; p-next=HL;B. p-next=HL; HL=p;C. p-next=HL; p=HL;D. p-next=HL-next; HL-next=p;HL为链表的头指针。HL指示链表中第一个节点的存储位置，在表头插入一个由指针p指向的节点后，头指针指向p，p的指针域指向原链表中第一个节点12、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是 。A. p=q-next; p-next=q-next;B. p=q-next; q-next=p;C. p=q-next; q-next=p-next;D. 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,1 3,2,1,4进2个后再出的情况有5种2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4进1个后再出的情况，有5种1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,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个序列中不可能出现的出栈顺序为 。A. 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 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是 。 A. 6 B. 4 C. 3 D. 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-frontB. (SQ-rear+1)%MAXLEN=SQ-frontB. SQ-rear=0D. 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和524、链栈与顺序栈相比，有一个较为明显的优点是 。A. 通常不会出现满栈的情况B. 通常不会出现栈空的情况C. 插入操作更加方便D. 删除操作更加方便25、设用一个大小为M=60的顺序表AM表示一个循环队列，如果当前的尾指针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(mn)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所指向的结点，操作是 。A. p-Prior=q; q-Next=p; p-Prior-next=q; q-Prior=q;B. p-Prior=q; p-Prior-next=q; q-next=p; q-Prior=p-Prior;C. q-Next=p; q-Prior=p-Prior; p-Prior-Next=q; p-Prior=q;D. q-Prior=p-Prior; q-Next=q;p-Prior=q; p-Next=q;31、已知循环队列存储在一维数组A0n-1中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A0处，则初始时front和rear的值分别是 。A. 0, 0B. 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. 减少不必要的存储空间37、广义表是线性表的推广，它们之间的区别在于 。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、顺序表中访问任一个结点的时间复杂度为 O（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）%n 。14、栈的逻辑特点是 先进后出 。队列的逻辑特点是 先进先出 。两者的共同特点是只允许在它们的 端点 出插入和删除数据元素，区别是 栈在栈顶进行插入删除，队列在两端操作，队尾插入，队首删除 。15、链队列LQ为空时，LQ-front-next= NULL .16、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为 front.next=rear 。17、设串S=“Ilikecomputer”，T=“com”，则Length(S)= 13 。Index(S, T)= 6 。18、在KMP算法中，nextj只与 子 串有关，而与 主串 无关。19、字符串“ababaab“的Next数组值是 。20、稀疏矩阵一般压缩存储的方式有三种，分别是三原组存储、行指针链表和 十字链表。21、二维数组M中每个元素的长度是3字节，行下标i从07，列下标j从09，从首地址&M00开始连续存放在存储器中。若按行优先的方式存放，元素M75的起始地址为 M00+225 ；若按列优先方式存放，元素M75的起始地址为 M00+141 。22、广义表(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的结点的算法函数：int delete(LIST &L, int x);如果x在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。要求：1、定义线性表的节点的结构以及节点的型和位置的型。2、定义线性表的基本操作3、在1，2的基础上，完成本题。4、在main函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。三，四，五#includeusingnamespacestd;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)/返回元素x在线性表中的位置positionpp=L while(p-next!=NULL)if(p-next-elements=x)returnp else p=p-next;returnp /时间复杂性：O(n) elementtypeRetrieve(positionp,LISTL)return(p-next-elements);/时间复杂性：O(1) voidDelete(positionp,LIST&L)/删除位置p的下一个节点positionq if(p-next!=NULL)q=p-nextp-next=q-nextdeleteq /时间复杂性：O(1) positionPrevious(positionp,LISTL)/返回位置p的前驱元素positionqif(p=L-next)cout”不存在前驱元素！next!=p) q=q-next returnq /时间复杂度O(n) positionNext(positionp,LISTL)/返回位置p的后驱元素positionq if(p-next=NULL) cout不存在后继元素！next;returnq /时间复杂度O(1) positionMakeNull(LIST&L) L=newcelltype L-next=NULL;returnL /时间复杂性：O(1) positionFirst(LISTL)returnL;/时间复杂性：O(1) voidTravel(LISTL)/遍历线性表元素positionpp=L-nextwhile(p!=NULL)coutelementsnext /=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; elsep2-next=p1;p2=p1; for(p3=L2;p3;p3=p3-next)p1=newcelltype; p1-elements=p3-elements;if(L=0)L=p1;p2=p1; elsep2-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; elsep2-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; elsep1=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请输入第i个线性表endl;LISTp1=0,p2=0;elementtypex;for(;)coutx;if(x=-1)break;p1=newcelltype;p1-elements=x;if(L=0)L=p1;p2=p1; elsep2-next=p1;p2=p1; p2-next=NULL; voidWrite(LISTL)/输出positionp=L;for(;p;p=p-next) coutelementst; coutendl; voidmain()cout本次测试的类型为intendl;LISTL=NULL,L1=NULL,L2=NULL;Read(L1,1); coutL1的元素为：endl;Write(L1);Read(L2,2); coutL2的元素为：endl;Write(L2);Merge(L,L1,L2); coutL1,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); coutx; intm=Delete(head,x);cout删除后：;write(head);if(m=-1)cout需要删除的数不存在endl; elsecout需要删除的数是第m个endl; */ /线性表的数组实现-线性表的合并#includeusingnamespacestd; #definemaxlength100typedefintposition;/位置类型typedefintElementtype;/下标类型 structLISTElementtypeelementsmaxlength;intlast;/最后一个元素的下标 ; positionEnd(LISTL)/线性表的长度return(L.last+1); voidInsert(Elementtypex,positionp,LIST&L)/在表L的位置p处插入xpositionq; if(L.last=maxlength-1)coutlistisfullL.last+1)|(p1)coutpositiondoesnotexist=p;q-) L.elementsq+1=L.elementsq; L.last=L.last+1;L.elementsp=x; voidDelete(positionp,LIST&L)/删除位置p处的元素positionq; if(pL.last+1)|(p1)coutpositiondoesnotexistendl; elseL.last=L.last-1;for(q=p;q=L.last;q+) L.elementsq=L.elementsq+1; positionLocate(Elementtypex,LISTL)/返回x在表L中的位置positionq; for(q=0;qL.last;q+)if(L.elementsq=x) returnq; return(L.last+1); /x不存在 ElementtypeRetrive(positionp,LISTL)/返回L中位置为p的元素if(pL.last+1)coutpositiondoesnotexistendl;return-1; returnL.elementsp; /=/将两个线性表合并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(;p1len1;)/将L1的元素写进LL.elementsp=L1.elementsp1;p+;p1+; for(;p2len2;)/继续将L2的元素写进LL.elementsp=L2.elementsp2;p+;p2+; voidRead(LIST&L,inti)/输入线性表cout请输入第iL.last;L.last-; cout请输入第i个线性表的元素：endl;for(positionp=0;pL.elementsp; voidWrite(LISTL)/输出线性表cout线性表的长度为：End(L)endl;cout线性表的元素为：endl; for(positionp=0;p=L.last;p+)coutL.elementspt; coutendl; voidmain()cout本次测试的类型为intendl;LISTL,L1,L2;Read(L1,1);Read(L2,2);Merge(L,L1,L2);Write(L); 六、写出一个将两个静态链表（属于同一个存储池）合并的算法函数： void Merge(cursor M, cursor N); 合并的方法是将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中。要求：1、定义静态链表的结点的结构以及结点的型SPACE以及位置（position）和游标（cursor）的型。2、定义静态链表的基本操作：void Initialize(); 初始化，将所有存储池中的结点设置为空闲；cursor GetNode(); 从空闲链中获取一个结点；void FreeNode(cursor q); 将结点q加入到空闲链； void Insert ( elementtype x, position p, cursor M ); 在链表M中的位置为p的元素后面添加一个值为x的结点；void Delete (cursor M, position p ); 在链表M中删除位置为p的元素的后一个元素。3、在1、2的基础上完成本题。 4，在main函数中进行测试：先构建一个存储池，然后在该存储池中创建两个静态表，最后将这两个静态表合并。#includeusingnamespacestd;#definemaxsize100typedefintelementtype;typedefstructelementtypeelementintnext spacestr;/*结点类型*/ spacestrSPACEmaxsize/*存储池*/ typedefintposition,cursor; cursoravailable;/*标识线性表/空闲池*/ voidInitialize()intj; /*依次链接池中结点*/for(j=0;jmaxsize-1;j+) SPACEj.next=j+1; SPACEj.next=-1;/*最后一个接点指针域为空*/ available=0;/*标识线性表,将所有存储池中的结点设置为空闲，avilable为头结点，不利用*/ /可用空间的分配操作,从空闲链中获取一个结点cursorGetNode()/q=newspacestcursorp; if(SPACEavailable.next=-1)p=-1; elsep=SPACEavailable.next SPACEavailable.next=SPACEp.nextreturnp; /*将空闲池头结点的下一个节点从空闲池中删除*/ voidFreeNode(cursorq)/deleteq;SPACEq.next=SPACEavailable.nextSPACEavailable.next=q /*将q指向的节点放回池中*/ /在位置p后面插入元素值为x的结点voidInsert(elementtypex,positionp)positionqq=GetNode()SPACEq.element=x SPACEq.next=SPACEp.nextSPACEp.next=q /删除位置p后的一个结点voidDelete(positionp)positionq； if(SPACEp.next!=-1)q=SPACEp.next；SPACEp.next=SPACEq.next；FreeNode(q) /创建静态链表voidCreate(cursorM)elementtypeinput;positionp=M;while(1)cout请输入静态链表的值，输入-1结束：input;if(input!=-1) Insert(input,p);p=SPACEp.next; else break; voidMerge(cursorM,cursorN) /连接两个链表,将N链表中的所有结点添加到M链表的后面，并将N链表的表头结点添加到空闲结点链表中positionp;p=M; while(SPACEp.next!=-1) p=SPACEp.next; positionq;q=SPACEN.next;SPACEp.next=q;FreeNode(N); /输出静态链表voidPrint(cursorM)positionp;p=M; while(SPACEp.next!=-1)coutSPACE