第二章 线性表
一、选择题
1．下述哪一条是顺序存储结构的优点？（ ）
A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2．下面关于线性表的叙述中，错误的是哪一个？（ ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
4．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
5．在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（ ）个元素
A．n-i        B．n-i+l        C．n-i-1        D．i
6．从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个元素结点
A．n/2           B．n            C．（n+1）/2        D．（n-1）/2
7．设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）
A．p->next=p->next->next;        B．p=p->next;
C．p=p->next->next;                D．p->next=p;
8．在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）
A．s->next=p->next;  p->next=s
B．q->next=s;  s->next=p
C．p->next=s->next;  s->next=p
D．p->next=s;  s->next=q
9．线性表的顺序存储结构是一种（ ）的存储结构。
A．随机存取        B．顺序存取        C．索引存取        D．散列存取
二、填空
1．在线性表的顺序存储中，元素之间的逻辑关系是通过      决定的；在线性表的链接存储中，元素之间的逻辑关系是通过      决定的。
2．在双向链表中，每个结点含有两个指针域，一个指向       结点，另一个指向       结点。
3．当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用        存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用        存储结构为宜。
三、算法设计
1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）
①确定在序列中比正整数x大的数有几个（相同的数只计算一次）
②将单链表中比正整数x小的偶数从单链表中删除
2．设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。






3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。
4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若是，则返回1，否则返回0，并分析算法的时间复杂度。
5．设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。






















参 考 答 案
第二章 线性表
一．选择题
1．A
2．B
3．A
4．D
5．A
6．C
7．A
8．B
9．A
二、填空
1．物理位置相邻  指针
2．直接前驱  直接后继
3．顺序  链式
三、算法设计
1．①　　
int count(Linklist h,int x)
{
  int num=0;
  Linknode *p;
  p=h->next;
  while(p&&p->data<=x)
    p=p->next;
  while(p)
    if(p->next&&p->data==p->next->data)
      p=p->next;
    else
    {
      num++;
      p=p->next;
    }
   return num;
}

②   void delevenl(Linklist h,int x)
{
  Linknode *p,*r;
  p=h->next;r=h;
  while(p&&p->data<x)
  {
    if(p->data%2==0)
    {
      r->next=p->next;
      free(p);
      p=r->next;
    }
    else
    {
      r=p;
      p=p->next;
    }
  }
}
2．
void Inverse（Linklist &h）
{
 Linklist p,q;
 p=h; h=null;
 while(p)
{ q=p; p=p->next;
  q->next=h;
  h=q; }
}
3．
void merge(Linklist La,Linklist &Lb,Linklist &Lc)
{
    Linknode *p;
    Lc=new Lnode;
    Lc->next=NULL;
    p=La->next;
    Lb=La;
    Lb->next=NULL;
    while(p)
    {
        La=p->next;
        if(p->data>0)
        {
            p->next=Lc->next;
            Lc->next=p;
        }
        else
        {
            p->next=Lb->next;
            Lb->next=p;
        }
        p=La;
    }
}
4．
int insect(Linklist La,Linklist Lb)
{
    Linknode *p,*q;
    p=La->next;
    while(p)
    {
        q=Lb->next;
        while(q)
        {
            if(p->data==q->data)
                break;
            else
                q=q->next;
        }
        if (!q)
            return 0;
        p=p->next;
    }
    return 1;
}
5．
void change(Dublist &h)
{
    DubLnode *p;
    p=h;
    while(p->next!=h)
    {
        p->next->prior=p;
        p=p->next;
    }
    h->prior=p;
}