习题集解析部分

第2章 线性表

——《数据结构题集》-严蔚敏.吴伟民版

       源码使用说明  链接☛☛☛ 《数据结构-C语言版》（严蔚敏,吴伟民版）课本源码+习题集解析使用说明

       课本源码合辑  链接☛☛☛ 《数据结构》课本源码合辑

       习题集全解析  链接☛☛☛ 《数据结构题集》习题解析合辑

      相关测试数据下载  链接☛ 数据包

      本习题文档的存放目录：数据结构\▼配套习题解析\▼02 线性表

      文档中源码的存放目录：数据结构\▼配套习题解析\▼02 线性表\▼习题测试文档-02

      源码测试数据存放目录：数据结构\▼配套习题解析\▼02 线性表\▼习题测试文档-02\Data

2.1❶描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

2.2❶填空题

    （1）在顺序表中插入或删除一个元素，需要平均移动  表中一半  元素，具体移动的元素个数与  该元素的位置  有关。

    （2）顺序表中逻辑上相邻的元素的物理位置  必定  相邻。单链表中逻辑上相邻的元素在物理位置  不一定  相邻。

    （3）在单链表中，除了首元结点外，任一结点的存储位置由  其直接前驱结点的链域的值  指示。

    （4）在单链表中设置头结点的作用是  插入和删除首元素时不必进行特殊处理  。

2.3❷在什么情况下用顺序表比链表好？

2.4❶对以下单链表分别执行下列各程序段，并画出结果示意图。

    （1）Q=P->next;

    （2）L=P->next;

    （3）R->data=P->data;

    （4）R->data=P->next->data;

    （5）P->next->next->next->data=P->data;

    （6）T=P;

            while(T!=NULL)

            {

                T->data=T->data*2;

                T=T->next;

            }

    （7）T=P;

            while(T->next!=NULL)

            {

                T->data=T->data*2;

                T=T->next;

            }

2.5❶画出执行下列各行语句后各指针及链表的示意图。

    L = (LinkList) malloc (sizeof(LNode));

    P = L;

    for(i=1; inext= (LinkList) malloc (sizeof(LNode));

        P = P->next;

        P->data = i*2-1;

    }

    P->next = NULL;

    for(i=4; i>=1; i--)

        Ins_LinkList(L, i+1, i*2);

    for(i=1; inext=S;

    （2）P->next=P->next->next;

    （3）P->next=S->next;

    （4）S->next=P->next;

    （5）S->next=L;

    （6）S->next=NULL;

    （7）Q=P;

    （8）while(P->next!=Q)

                P=P->next;

    （9）while(P->next!=NULL)

                P=P->next;

    （10）P=Q;

    （11）P=L;

    （12）L=S;

    （13）L=P;

2.7❷已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

    a.删除P结点的直接后继结点的语句序列是   （11）（3）（14）  。

    b.删除P结点的直接前驱结点的语句序列是  （10）（12）（8）（11）（3）（14）  。

    c.删除P结点的语句序列是  （10）（12）（7）（3）（14）  。

    d.删除首元结点的语句序列是  （12）（11）（3）（14）  。

    e.删除尾元结点的语句序列是  （9）（11）（3）（14）  。

    （1）P=P->next;

    （2）P->next=P;

    （3）P->next=P->next->next;

    （4）P=P->next->next;

    （5）while(P!=NULL)

                P=P->next;

    （6）while(Q->next!=NULL)

            {

                P=Q;

                Q=Q->next;

            }

    （7）while(P->next!=Q)

                P=P->next;

    （8）while(P->next->next!=Q)

                P=P->next;

    （9）while(P->next->next!=NULL)

                P=P->next;

    （10）Q=P;

    （11）Q=P->next;

    （12）P=L;

    （13）L=L->next;

    （14）free(Q);

2.8❷已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

    注：此题答案不唯一

    a.在P结点后插入S结点的语句序列是  （7）（12）（3）（6）  。

    b.在P结点前插入S结点的语句序列是  （8）（13）（5）（4）  。

    c.删除P结点的直接后继结点的语句序列是  （15）（1）（11）（18）  。

    d.删除P结点的直接前驱结点的语句序列是  （16）（2）（10）（18）  。

    e.删除P结点的语句序列是  （14）（9）（17）  。

    （1）P->next=P->next->next;

    （2）P->priou=P->priou->priou;

    （3）P->next=S;

    （4）P->priou=S;

    （5）S->next=P;

    （6）S->priou=P;

    （7）S->next=P->next;

    （8）S->priou=P-priou;

    （9）P->priou->next=P->next;

    （10）P->priou->next=P;

    （11）P->next->priou=P;

    （12）P->next->priou=S;

    （13）P->priou->next=S;

    （14）P->next->priou=P->priou;

    （15）Q=P->next;

    （16）Q=P->priou;

    （17）free(P);

    （18）free(Q);

2.9❷简述下列算法的功能。

    （1）Status A(LinkedList L)          //L是无表头结点的单链表

            {

                if(L&&L->next)

                {

                    Q=L;

                    L=L->next;

                    P=L;

                    while(P->next)

                        P=P->next;

                    P->next=Q;

                    Q->next=NULL;

                }

                return  OK;

            }//A

    （2）void BB(LNode *s, LNode *q)

            {

                p=s;

                while(p->next!=q)

                    p=p->next;

                p->next=s;

            }//BB

            void   AA(LNode *pa, LNode *pb)

            {//pa和pb分别指向单循环链表中的两个结点

                BB(pa, pb);

                BB(pb, pa);

            }//AA

       本章算法设计题设计的顺序表和线性链表的类型定义如下：

#define LIST_INIT_SIZE 100

#define LISTINCREMENT 10

typedef struct

{

ElemType *elem;          //存储空间基址

int            length;         //当前长度

int            listsize;        //当前分配的存储容量   

}SqList;                        //顺序表类型

注：此文档中，ElemType被定义为int类型。

typedef struct LNode

{       

ElemType data;       

Struct   Lnode   *next;   

}LNode, *LinkList;               //线性链表类型

2.10❷ 指出以下算法的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。

    Status  DeleteK(SqList &a, int i, int k)

    {//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素

        if(iem-1>…>e1≥0，ci≠0(i=1,2,...,m),m≥1。试采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法(x0为给定值)，并分析你的算法的时间复杂度。

2.40❸采用2.39题给定的条件和存储结构，编写求的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。

       在2.41至2.42题中，稀疏多项式采用的循环链表存储结构LinkedPoly定义为：

typedef struct PolyNode

{

    PolyTerm data;

    struct PolyNode *next;

}PolyNode, *PolyLink;

typedef  PolyLink  LinkedPoly;

2.41❷试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。

2.42❷试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。