数据结构习题集答案(C语言版严蔚敏)
第2章  线性表
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
    (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
    (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
    (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好？
解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。
解：
2.5 画出执行下列各行语句后各指针及链表的示意图。
    L=(LinkList)malloc(sizeof(LNode));    P=L;
    for(i=1;i<=4;i++){
        P->next=(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;i<=3;i++) Del_LinkList(L,i);
解：
2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是__________________。
b. 在P结点前插入S结点的语句序列是__________________。
c. 在表首插入S结点的语句序列是__________________。
d. 在表尾插入S结点的语句序列是__________________。
(1) P->next=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;
解：a. (4) (1)
        b. (7) (11) (8) (4) (1)
        c. (5) (12)
        d. (9) (1) (6)
2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
    a. 删除P结点的直接后继结点的语句序列是____________________。
    b. 删除P结点的直接前驱结点的语句序列是____________________。
    c. 删除P结点的语句序列是____________________。
    d. 删除首元结点的语句序列是____________________。
e. 删除尾元结点的语句序列是____________________。
(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);
解：a. (11) (3) (14)
        b. (10) (12) (8) (3) (14)
        c. (10) (12) (7) (3) (14)
        d. (12) (11) (3) (14)
        e. (9) (11) (3) (14)
2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是_______________________。
b. 在P结点前插入S结点的语句序列是_______________________。
c. 删除P结点的直接后继结点的语句序列是_______________________。
d. 删除P结点的直接前驱结点的语句序列是_______________________。
e. 删除P结点的语句序列是_______________________。
(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);
解：a. (7) (3) (6) (12)
        b. (8) (4) (5) (13)
        c. (15) (1) (11) (18)
        d. (16) (2) (10) (18)
        e. (14) (9) (17)
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;
        }
(2) void BB(LNode *s, LNode *q) {
            p=s;
            while(p->next!=q) p=p->next;
            p->next =s;
        }
        void AA(LNode *pa, LNode *pb) {
            //pa和pb分别指向单循环链表中的两个结点
            BB(pa,pb);
            BB(pb,pa);
        }
解：(1) 如果L的长度不小于2，将L的首元结点变成尾元结点。
        (2) 将单循环链表拆成两个单循环链表。
2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。
Status DeleteK(SqList &a,int i,int k)
{
    //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
    if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法
    else {
for(count=1;count<k;count++){
    //删除第一个元素
    for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j];
            a.length--;
        }
    return OK;
}
解：
Status DeleteK(SqList &a,int i,int k)
{
    //从顺序存储结构的线性表a中删除第i个元素起的k个元素
    //注意i的编号从0开始
    int j;
    if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE;
    for(j=0;j<=k;j++)
        a.elem[j+i]=a.elem[j+i+k];
    a.length=a.length-k;
    return OK;
}
2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
解：
Status InsertOrderList(SqList &va,ElemType x)
{
    //在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
    int i;
    if(va.length==va.listsize)return(OVERFLOW);
    for(i=va.length;i>0,x<va.elem[i-1];i--)
        va.elem[i]=va.elem[i-1];
    va.elem[i]=x;
    va.length++;
    return OK;
}
2.12 设和均为顺序表，和分别为和中除去最大共同前缀后的子表。若空表，则；若=空表，而空表，或者两者均不为空表，且的首元小于的首元，则；否则。试写一个比较，大小的算法。
解：
Status CompareOrderList(SqList &A,SqList &B)
{
    int i,k,j;
    k=A.length>B.lengthA.length:B.length;
    for(i=0;i<k;i++){
        if(A.elem[i]>B.elem[i]) j=1;
        if(A.elem[i]<B.elem[i]) j=-1;
    }
    if(A.length>k) j=1;
    if(B.length>k) j=-1;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。