数据结构2.3.课后题

发表于 更新于 分类于 ， 阅读次数： 本文字数： 9.1k 阅读时长 ≈ 16 分钟
数据结构2.3.课后题做题记录

2.3

一

  1. B 链式储存结构比顺序储存结构更方便地表示各种逻辑结构（√）

  2. B 散列储存只不过是提供了一个“关键字”到物理空间的映射方法，无法反映逻辑关系

  3. C A 链式储存中各个不同结点的储存空间可以不连续，但结点内的储存单元地址必须连续

  4. D设有头指针和尾指针的单链表中，删除表尾元素的时间复杂度与表长无关（×）2

    删除表尾结点时，必须从头开始找到表尾元素的前驱，其时间和表厂有关。

  5. A

  6. C

  7. B D给定n个元素的一维数组，建立一个有序链表的最低时间复杂度？

    可能流程1.提供数组—>按数组顺序直接插入排序，（就是直接插入排序O（n2））2提供数组->数组排序->按序建立起单链表 数组排序最小时间复杂度O(nlog2n) 建立单链表时间复杂度O(n) 相加为O(nlog2n)

  8. A C 将长度为n的单链表链接到长度为m的单链表后面，求时间复杂度？

    先遍历长度为m的单链表，找到单链表的表尾结点，然后将next域指向另一个单链表的首结点，其空间复杂度为O（m）

  9. C

  10. B

  11. B A

  12. D

  13. B

  14. B C

  15. D

  16. A

  17. BA

  18. C

  19. B

  20. D

  21. DC 对于一个带头节点的循环单链表L，判断该表为空表的条件是（）L->next==L 头结点的指针域与L的值相等（√）头结点的指针域与L的地址相等（×）

  22. D

  23. A

  24. C

  25. B

  26. A

  27. D

  28. D

  29. D

  30. B

  31. B

  32. [16统考]D

  33. [16统考]D

  34. [21统考]D

  35. [23统考]C

二

  1. 带头结点单链表L，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一。

    做题

    void delete_x(struct &L){  //错误应该是Linklist 未传入x
    LNode *p=L,q;
    while (p->next!=NULL){
        if(p->next->data==x){
            q=p->next;
            p->next=P->next->next;
            free(q)
        }
        p=p->next;
    }
}

    答案

    解法一：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指向的结点值为x则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。

    void DEl_x_1(Linklist &L,Elemtype x){
    Lnode *p=L->next,*pre =L,*q; //置p和pre的初始值
    while(P!=NULL)
    {
        if(p->data==x){
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

    解法二采用尾插法建立单链表。用p指针扫描L的所有结点，当其值不为x时，将其链接到L之后，否则将其释放

    void DEl_x_2(Linklist &L,Elemtype x){
    LNode *p =L->next,*r=L,*q;//r指向尾结点初值为头结点
    while(p!=NULL){
        if (p->data!=x){
            r->next=p;
            r=p;
            p=p->next;
        }
        else{
            q=p;
            p=p->next;
            free(q);
        }
    }
    r->next=NULL；
}

    上述俩个算法扫描一遍链表，时间复杂度O(n),空间复杂度O(1)

  2. 试编写在带头节点的单链表L中删除一个最小值结点的高效算法（假设该结点唯一）

    做题

    void delete_min(Linklist L)
{
    LNode *p=L->next,*q=L->next;
    ElemType min=L->next->data;
    while (p->next!=NULL){
        if (p->next->data<min)
        {
            q=p;
            min=p->next->data
        }
        p=p->next;
    }
    p=q;
    p->next=p->next->next;
    free(q);
}

    答案

    用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的结点指针（初值为p），minpre指向*minp结点的前驱（初值pre）。一边扫描一边比较，若p->data小于mino->data，则将p、pre分别赋值给minp、minpre。当p扫描完毕时，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指向的结点删除即可。

    Linklist Delete_Min(Linklist &L){
    LNode *pre=L,*p=pre->next;
    LNode *minpre=pre,*minp=p;
    while(p!=NULL){
        if(p-data<minp->data){
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
    return L;
}

    扫描一遍链表，时间复杂度O(n),空间复杂度O(1)

  3. 试编写算法将带头结点的单链表逆置，所谓“就地”是指辅助空间复杂度为O（1）

    做题

    void reverse (Linklist &L)//头插法
{
    LNode *p=L->next->next,*q=L->next,i;
    L.next=q;
    
    while (p!=NULL){
        L->next=p;
        q=p->next;
        p->next=q;
        
    }
}

    答案

    解法一，将头结点摘下，然后从第一个结点开始，依次插入到头结点的后面（头插法建立单链表）

    直到最后一个结点为止，这样就实现了链表的逆置。

    Linklist Reverse_1(Linklist L){
    LNode *p,*r;
    p=L->next;
    L->next=NULL;
    while(p!=NULL){
        r=p->next;
        p->next=L.next;
        L->next=p;
        p=r;
    }
    return L;
}

    解法二：假设pre、p和r指向三个相邻的结点，如图2.3-2-3

    假设经过若干操作,*pre 之前的结点指针都已调整完毕，他们的next都指向其原前驱结点，现令*p结点的next域指向*pre结点，注意一旦调整指针的指向，*p的后继结点的链就会断开，为此需要用r来指向原*p的后继结点。处理时需注意：一是处理第一个结点的时候应将其next域置为NULL，而不是指向头结点，二是在处理完最后一个结点后，需要将头结点的指针指向它。

    Linklist  Reverse_2(Linklist &L){
    LNode *pre,*p=L->next,*r=p->next;
    p->next=NULL;处理第一个结点
    while(r!=NULL){
        pre=p;
        p=r;
        r=r->next;
        p->next=pre;
    }
    L->next=p;处理最后一个结点
    return L;
}

    时间复杂度O(n),空间复杂度O(1)

  4. 设在一个带表头结点的单链表中，所有结点的元素值无序，试编写一个函数，删除表中所有介于给定的俩个值（作为函数参数给出）之间的元素(若存在)

    做题

    void Delete_1 (Linkinst &L,ElemType x，ElemType y){
    LNode *pre=L,*p=L->next;
    while (p!=NULL){
         if(x<p->data&&p->data<y){
        pre->next=p->next;
        free(p);
        p=pre->next;
    }else{
        pre=p;
        p=p->next;
    }   
    } 
}

    貌似完全正确

    答案：因为链表无序，所以只能逐个结点进行检查，执行删除

    void RangeDelete(Linklist  &L,int min,int max){
    LNode *pr=L,*p=L->next;
    while(p!=NULL){
        if(p->data>min&&p->data<max){
            pr->link=p->link;
            free(p);
            p=pr->link;
        }
        else{
            pr=p;
            p=p->link;
        }
    }
}

  5. 给定俩个单链表，试分析找出俩个链表的公共结点的思想（不用写代码）

    作答：

    依次遍历第一个链表的元素，取出每个元素后遍历第二个链表，看第二个链表中是否有相同元素，如果有相同元素则标记为公共结点。

    答案：（题意都理解错了。。）

    俩个单链表有公共结点，即俩个单链表从某个结点开始，他们的next都指向同一个结点。由于每个单链表结点只有一个next域，因此从第一个公共结点开始，之后的所有结点都是重合的，不可能在出现分叉。所以俩个有公共结点而部分重合的单链表，拓扑形状看起来像Y，而不可能像X。
本题极易想到蛮的方法:在第一个链表上顺序遍历每个结点，每遍历一个结点，在第二个链表上顺序遍历所有结点，若找到俩个相同的结点，则找到了他们俩个的公共结点。显然该算法的时间复杂度为O(len1xlen2)。
接下来我们试着去寻找一个线性时间复杂度的算法。先把问题简化：如何判断两个单向链表有没有公共结点？应注意到这样一个事实：若两个链表有一个公共结点，则该公共结点之后的所有结点都是重合的，即它们的最后一个结点必然是重合的。因此，我们判断两个链表是不是有重合的部分时，只需要分别遍历两个链表到最后一个结点。若两个尾结点是一样的，则说明它们有公共结点，否则两个链表没有公共结点。
然而，在上面的思路中，顺序通历两个链表到尾结点时，并不能保证在两个链表上同时到达尾结点，这是因为两个链表长度不一定一样。但假设一个链表比另一个长k个结点，我们先在长的链表上遍历k个结点，之后再同步遍历，此时我们就能保证同时到达最后一个结点。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的，因此它们肯定也是同时到达第一公共结点的，于是在通历中，第一个相同的结点就是第一个公共的结点。
根据这一思路中，我们先要务别遍历两个链表得到它们的长度，并求出两个长度之差、在长的链表上先遍历长度之差个结点后，在同步遍历俩个链表，直到找到相同的结点，若一直到链表结束。此时，该方法的时间复杂度为 O（lenl+len2）。

  6. 设C={a1，b1，a2，b2，…，an，bn}为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为俩个线性表，使得A={a1，a2，…，an}，B={bn，…，b2，b1}.

    作答

     void divide (Linkinst &L){ //void divide(LinkList &L, LinkList &a, LinkList &b) {
     LNode *p=L->next,*q=L->next->next;
     LNode *a=L->next,*b=L->next->next;
     while (p->next->next!=NULL){  //(p->next != NULL && q->next != NULL) 
         p->next=p->next->next;
         q->next=q->next->next;
         p=p->next;
         q=q->next;
     }
     return a,b;//错误 return;
 }

    错误，一个是题目要求b反向 另一个思维错误，链表的原地。。。

    答案：思想：循环遍历链表C，采用尾插法将一个结点插入表A，这个结点为奇数号结点，这样建立得表A与原来的结点顺序相同；采用头插法将下一结点插入表B，这个结点为偶数号结点，这样建立起B与原来的结点顺序正好相反。

    Linklist Discreat_2(Linklist &A){
    Linklist B=(Linklist)malloc(sizeof(LNode));//创建B表头
    B->next=NULL;
    LNode *p=A->next,*q;
    LNode *ra=A;
    while(p!=NULL){
        ra->next=p,ra=p;//将*p链接到A的表尾
        p=p->next;
        if(p!=NULL){
            p->next=B-next;
            B-next=p;
            p=q;
        }
    }
    ra->next=NULL;
    return B;
}

  7. 在一个递增有序的单链表中，存在重复的元素，设计算法删除重复的元素，例如（7，10，10，21，30，42，42，42，51，70)将变为(7,10,21,30,42,51,70).

    作答

    void Delete_repetition(Linklist &L){
    LNode *p=L->next,*pre =L;
    while(p!=NULL){
        if (p->data==pre->data){
            pre->next=p->next;
            free(p);
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
}

    应该基本正确，不如答案好，

    答案：思想：由于是有序表，因此所有相同值域的结点都是相邻的，用p扫描递增单链表L，若*p结点的值域等于其后继结点的值域，则删除后者，否则p移向下一个结点

    void Del_Same(Linklist &L){
    LNode *p=L-next,*q;
    if (p==NULL)
        return;
    while(p->next!=NULL){
        q=p->next;
        if(p->data==q->data){
            p->next=q->next;
            free(q);
        }
        else
            p=p->next;
    }
}

    时间复杂度O(n),空间复杂度O(1)

  8. 设A和B是俩个单链表（带头结点），其中元素递增有序，设计一个算法从A和B的公共元素产生单链表C，要求不破坏A，B的结点。

    作答

    Linklist Creat_same(Linklist A,Linklist B){
    Linklist C=(Linklist)malloc(sizeof(LNode));
    LNode *p=A->next,*q=B->next,*m=C,*n;//后面几个漏了星号
    while (p!=NULL&&q!=NULL){
        if(p->data==q->data){ //判断相等要俩个等于
            n=(LNode *)malloc (sizeof(LNode));//开始没有定义结点n
            n->data=p->data;
            n->next=NULL;
            m->next=n;
            m=n;
            p=p->next;
            q=q->next;
        }else if(p->data<q->data){
            p=p->next;
        }else{
            q=q->next;
        }
    }
    return C;
}

    基本正确 小细节有许多

    答案：表A、B都有序，可以从第一个元素起依次比较A，B俩表的元素，若元素值不等则小的指针往后移，若元素值相等，则创建一个值等于俩结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾。

    void Get_Common(Linklist A,Linklist B){
    LNode *p=A->next,*q=B->next,*r,*s;
    Linklist C=(Linklist)malloc(sizeof(LNode));
    r=c;
    while(p!=NULL&&q!=NULL){
        if(p->data<q-data)
            p=p->next;
        else if(p->data>q->data)
            q=q->next;
        else{
            s=(LNode *)malloc(sizeof(LNode));
            s->data=p->data;
            r-next=s;
            r=s;
            p=p->next;
            q=q->next;
        }
    }
    r->next=NULL;
}

  9. 已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A和B的交集，并存放于A链表中。

    作答

    void Get_Common(Linklist &A,Linklist B){
    LNode *p=A->next,*q=B->next,*r,*s,*n;
    free(B);
    r=A;
    while(p!=NULL&&q!=NULL){
        if(p->data<q->data){
            n=p;
            p=p->next;
            free(n);
        }
        else if(p->data>q->data){
            n=q;
            q=q->next;
            free(n);
        }
        else{
            s=(LNode *)malloc(sizeof(LNode));
            s->data=p->data;
            r->next=s;
            r=s;
            n=p;
            p=p->next;
            free(n);
            n=q;
            q=q->next;
            free(n);
        }
    }
    if(p!=NULL){
        while(p!=NULL){
            n=p;
            p=p->next;
            free(n);
        }
    }
    else if(q!=NULL){
        while(q!=NULL){
            n=q;
            q=q->next;
            free(n);
        }
    }
    r->next=NULL;
}

    答案：思想：采用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两个集合的元素才能链接到结果表中且仅保留一个，其他结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。

    Linklist Union(Linklist &la,Linklist &lb){
    Lnode *pa=la->next;
    LNode *pb=lb->next;
    LNode *u,*pc=la;
    while(pa&&pb){
        if(pa->data==pb->data){
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb;
            pb=pb->next;
            free(u);
        }else if(pa->data<pb->data){
            u=pa;
            pa=pa->next;
            free(u);
        }else{
            u=pb;
            pb=pb->next;
            free(u);
        }
    }while(pa){
        u=pa;
        pa=pa->next;
        free(u);
    }
    while(pb){
        u=pb;
        pb=pb->next;
        free(u);
    }
    pc->next=NULL;
    free(lb);
    return la;
}

    时间复杂度O(len1+len2),空间复杂度O(1)。

  10. 两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已存入两个单链表中，设计一个算法，判断B序列是否是序列A的连续子列。

    作答

    bool son(Linklist A,linklist B){
    LNode *p=A->next,*q=B->next,*n;
    while(p){
       if(p->data==q->data){
           n=p
       }
    }
    if (n)
        while(p&&q){
            if(p->data!=q->data)
                return false;
            p=p->next;
            q=q->next;
        }
    else
        return false;
    return true;
}

    错误

    答案:思想：因为两个整数序列已经存入两个链表中，操作从两个链表的第一个结点开始，若对应数据相等则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始，B链表仍从第一个结点开始比较，直到B链表到尾才匹配成功。A链表到尾而B链表未到尾则表示匹配失败。操作应记住A链表，每次的开始结点，以便下次匹配时好从其后继开始。

    int Pattern(Linklist A,Linklist B){
    LNode *p=A:
    LNode *pre=p;
    LNode *q=B;
    while(p&&q){
        if(p->data==q->data){
            p=p->next;
            q=q->next;
        }else{
            pre=pre->next;
            p=pre;
            q=B;
        }
    }
    if(q==NULL)
        return 1;
    else
        return 0;
}