第1章
4． 答案：
（1）顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
（2）链式存储结构
顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
5. 选择题
(1)~(6)：CCBDDA
6．
（1）O(1)      （2）O(m*n)  （3）O(n2) 
（4）O(log3n)  （5）O(n2)     （6）O()
第2章
1．选择题
（1）~（5）：BABAD    （6）~（10）： BCABD    （11）~（15）：CDDAC
2．算法设计题
（1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。
[题目分析]
合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次
摘取其中较小者重新链接在Lc表的最后。如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{//合并链表La和Lb，合并后的新表使用头指针Lc指向
  pa=La->next;  pb=Lb->next;   
  //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
  Lc=pc=La;  //用La的头结点作为Lc的头结点
  while(pa && pb)
  {  if(pa->data<pb->data){pc->next=pa; pc=pa; pa=pa->next;}
    //取较小者La中的元素，将pa链接在pc的后面，pa指针后移
    else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}
      //取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移
    else //相等时取La中的元素，删除Lb中的元素
    {pc->next=pa;pc=pa;pa=pa->next;
      q=pb->next; delete pb ; pb =q;
    }
  }
  pc->next=pa?pa:pb;    //插入剩余段
  delete Lb;            //释放Lb的头结点
} 
（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。
[题目分析]
B表的头结点使用原来A表的头结点，为C表新申请一个头结点。从A表的第一个结点开始，依次取其每个结点p，判断结点p的值是否小于0，利用前插法，将小于0的结点插入B表,大于等于0的结点插入C表。
[算法描述]
void DisCompose(LinkedList A)
{      p=A->next;        ∥p为工作指针
    B=A;
B->next= NULL;    ∥B表初始化
    C=new LNode;∥为C申请结点空间
    C->next=NULL;    ∥C初始化为空表
    while(p!= NULL)
    { r=p->next;      ∥暂存p的后继
      if(p->data<0)
      {p->next=B->next; B->next=p; }∥将小于0的结点链入B表,前插法
      else {p->next=C->next; C->next=p; }∥将大于等于0的结点链入C表
      p=r;∥p指向新的待处理结点。
    }
}
（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
[题目分析]
假定第一个结点中数据具有最大值，依次与下一个元素比较，若其小于下一个元素，则设其下一个元素为最大值，反复进行比较，直到遍历完该链表。
[算法描述]
ElemType Max (LinkList L )
{
    if(L->next==NULL) return NULL;
        pmax=L->next; //假定第一个结点中数据具有最大值
    p=L->next->next;
    while(p != NULL ){//如果下一个结点存在
        if(p->data > pmax->data) pmax=p;//如果p的值大于pmax的值，则重新赋值
        p=p->next;//遍历链表
    }
    return pmax->data;
}
（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
[题目分析]
从首元结点开始，逐个地把链表L的当前结点p插入新的链表头部。
[算法描述]
void  inverse(LinkList &L)
{// 逆置带头结点的单链表 L
    p=L->next;  L->next=NULL;
    while (p) {
        q=p->next;    // q指向*p的后继
        p->next=L->next;
        L->next=p;      // *p插入在头结点之后
        p = q;
    }
}
（8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同 ）。先序中序后序遍历二叉树

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