数据结构与数据库第二章线性表习题与答案

数据结构与数据库第二章线性表习题与答案一、选择题1.以下关于线性表的描述中，正确的是（）。A.顺序表的存储空间必须是连续的，而链表的存储空间可以是不连续的B.顺序表的插入操作时间复杂度一定为O(n)，链表的插入操作时间复杂度一定为O(1)C.顺序表和链表都支持随机访问D.若线性表需要频繁在头部插入元素，顺序表比链表更高效2.已知一个顺序表L，其长度为n，若要在第i个位置（1≤i≤n+1）插入一个新元素，需要移动的元素个数为（）。A.n-i+1B.n-iC.iD.i-13.单链表中，每个节点包含一个指针域，该指针指向（）。A.前驱节点B.后继节点C.头节点D.尾节点4.设一个循环单链表的尾节点为p，若要将其转换为非循环单链表，需要执行的操作是（）。A.p->next=NULLB.p->next=headC.head->next=pD.head=p5.对于双向链表，在节点p之后插入节点s的正确操作顺序是（）。①s->prev=p②s->next=p->next③p->next->prev=s④p->next=sA.①②③④B.②①④③C.②①③④D.①②④③二、填空题1.线性表的两种存储结构分别是________和________。2.顺序表中，第i个元素的存储地址可以表示为LOC(a₁)+________（假设每个元素占k个存储单元）。3.单链表中，若要删除指针p所指节点的后继节点，需执行的操作是________（假设p的后继节点为q）。4.设一个顺序表的长度为n，在最好情况下，删除操作的时间复杂度为________；在最坏情况下，时间复杂度为________。5.循环链表与非循环链表的主要区别是________。三、判断题（正确打√，错误打×）1.顺序表的存储空间需要预先分配，可能造成空间浪费或溢出。（）2.单链表的头指针指向头节点时，头节点的数据域可以不存储任何信息。（）3.在双向链表中，每个节点都有两个指针域，分别指向直接前驱和直接后继，因此双向链表的存储密度比单链表高。（）4.对于长度为n的顺序表，插入和删除操作的平均时间复杂度均为O(n)。（）5.若线性表的元素类型变化较大，链表比顺序表更适合作为存储结构。（）四、综合题1.已知顺序表L中的元素按非递减顺序排列，设计一个算法删除L中所有值重复的元素，要求时间复杂度为O(n)。2.编写一个函数，将一个单链表逆置（例如，原链表为1→2→3→4，逆置后为4→3→2→1）。3.设有两个非递减有序的单链表A和B，设计算法合并A和B，得到一个新的非递减有序单链表C（要求不破坏原链表A和B）。4.约瑟夫环问题：n个人围成一圈，从第1个人开始报数，数到m的人出圈；接着从下一个人开始继续报数，数到m的人出圈，直到所有人出圈。使用循环链表模拟该过程，输出出圈顺序。5.设计一个算法，在双向链表中查找值为x的节点，并在其前驱节点之后插入一个值为y的新节点（若x不存在则不插入）。答案与解析一、选择题1.答案：A解析：顺序表的存储空间连续，链表通过指针链接离散的存储单元，A正确。链表插入操作若需找到插入位置（如中间插入），时间复杂度可能为O(n)，B错误。链表不支持随机访问，C错误。顺序表头部插入需移动所有元素，时间复杂度O(n)，链表头部插入O(1)，D错误。2.答案：A解析：在第i个位置插入元素，需将原第i到第n个元素后移一位，共ni+1个元素。3.答案：B解析：单链表的指针域指向后继节点，前驱节点无法直接访问（无头指针时）。4.答案：A解析：循环单链表的尾节点p的next指向头节点，断开循环需将p->next置为NULL。5.答案：D解析：插入步骤为：s的前驱指向p（①），s的后继指向p的后继（②），p的后继的前驱指向s（③），p的后继指向s（④）。二、填空题1.顺序存储结构；链式存储结构2.(i-1)×k3.p->next=q->next（需先保存q，避免内存泄漏）4.O(1)；O(n)（最好情况删除尾元素，无需移动；最坏情况删除首元素，需移动n-1个元素）5.循环链表的尾节点指针指向头节点，非循环链表尾节点指针为NULL三、判断题1.√（顺序表需预分配空间，可能因预分配过大导致浪费，或过小导致溢出）2.√（头节点的作用是简化操作，数据域可空）3.×（双向链表每个节点多一个指针域，存储密度=数据域大小/(数据域+指针域)，比单链表低）4.√（平均需移动n/2个元素，时间复杂度O(n)）5.√（链表无需预分配固定大小空间，适合元素类型变化大或长度不确定的场景）四、综合题1.算法思路：利用双指针法，设置慢指针i和快指针j。i指向当前不重复元素的末尾，j遍历顺序表。若L[j]≠L[i]，则i后移并将L[j]的值赋给L[i]；否则j继续后移。最终顺序表长度为i+1。算法实现（伪代码）：```voidDeleteDuplicates(SqList&L){if(L.length==0)return;inti=0;//慢指针，指向当前不重复元素的末尾for(intj=1;j<L.length;j++){//快指针遍历if(L.data[j]!=L.data[i]){//发现不重复元素i++;L.data[i]=L.data[j];//覆盖到i的下一个位置}}L.length=i+1;//更新顺序表长度}```2.算法思路（迭代法）：使用三个指针prev、curr、next。初始时prev为NULL，curr为头节点。每次循环中，保存curr的下一个节点next，将curr的next指向prev，然后prev和curr分别后移（prev=curr，curr=next），直到curr为NULL，此时prev为新头节点。函数实现（C语言）：```LinkListReverseList(LinkListhead){LNodeprev=NULL;LNodecurr=head;while(curr!=NULL){LNodenext=curr->next;//保存下一节点curr->next=prev;//反转指针prev=curr;//prev后移curr=next;//curr后移}returnprev;//prev成为新头节点}```3.算法思路：创建新头节点C，用三个指针pa（遍历A）、pb（遍历B）、pc（构建C）。比较pa和pb的值，将较小的节点复制到C的末尾，直到其中一个链表遍历完毕，最后将未遍历完的链表剩余节点复制到C末尾。算法实现（伪代码）：```LinkListMergeLists(LinkListA,LinkListB){LNodeC=(LNode)malloc(sizeof(LNode));//头节点LNodepc=C;//pc指向C的尾节点LNodepa=A->next,pb=B->next;//跳过A、B的头节点（假设含头节点）while(pa!=NULL&&pb!=NULL){if(pa->data<=pb->data){//复制A的当前节点LNodes=(LNode)malloc(sizeof(LNode));s->data=pa->data;pc->next=s;pc=s;pa=pa->next;}else{//复制B的当前节点LNodes=(LNode)malloc(sizeof(LNode));s->data=pb->data;pc->next=s;pc=s;pb=pb->next;}}//处理剩余节点while(pa!=NULL){LNodes=(LNode)malloc(sizeof(LNode));s->data=pa->data;pc->next=s;pc=s;pa=pa->next;}while(pb!=NULL){LNodes=(LNode)malloc(sizeof(LNode));s->data=pb->data;pc->next=s;pc=s;pb=pb->next;}pc->next=NULL;//尾节点置空returnC;}```4.算法思路：构建循环链表表示n个人，用指针p指向当前报数起点。每次报数m-1次（因为从当前节点开始数1），然后删除p的后继节点（即数到m的节点），直到链表为空。模拟过程（以n=5，m=3为例）：初始化循环链表：1→2→3→4→5→1第一次报数：p指向5（初始p指向头节点），数1（p=p->next=1），数2（p=p->next=2），数3（删除p->next=3），出圈顺序[3]第二次报数：p指向2，数1（p=p->next=4），数2（p=p->next=5），数3（删除p->next=1），出圈顺序[3,1]第三次报数：p指向5，数1（p=p->next=2），数2（p=p->next=4），数3（删除p->next=5），出圈顺序[3,1,5]第四次报数：p指向4，数1（p=p->next=2），数2（p=p->next=4），数3（删除p->next=2），出圈顺序[3,1,5,2]最后出圈4，最终顺序[3,1,5,2,4]算法实现（关键步骤）：```voidJosephus(intn,intm){//创建循环链表LNodehead=(LNode)malloc(sizeof(LNode));head->data=1;LNodep=head;for(inti=2;i<=n;i++){LNodes=(LNode)malloc(sizeof(LNode));s->data=i;p->next=s;p=s;}p->next=head;//形成循环//模拟出圈过程p=head;//p初始指向第一个节点while(p->next!=p){//剩余不止一人for(inti=1;i<m-1;i++){//移动m-2次，使p指向待删除节点的前驱p=p->next;}LNodeq=p->next;//q是待删除节点printf("%d",q->data);//输出出圈顺序p->next=q->next;//从链表中删除qfree(q);p=p->next;//p指向新的起点}printf("%d\n",p->data);//输出最后一人}