《数据结构-C语言版》
数组和链表第一章  绪论
单项选择题
1．在数据结构中，数据的基本单位是_____ ____。
A. 数据项      B. 数据类型      C. 数据元素        D. 数据变量
2．数据结构中数据元素之间的逻辑关系被称为__ ____。
A. 数据的存储结构  B. 数据的基本操作  C. 程序的算法  D. 数据的逻辑结构
3．在数据结构中，与所使用计算机无关的是数据的____ ___。
A. 存储结构          B. 逻辑和物理结构    C. 逻辑结构        D. 物理结构
4．在链式存储结构中，数据之间的关系是通过____ ____体现的。
A. 数据在内存的相对位置    B. 指示数据元素的指针
C. 数据的存储地址          D. 指针
5．计算算法的时间复杂度是属于一种____ ___。
A. 事前统计的方法      B. 事前分析估算的方法     
C. 事后统计的方法      D. 事后分析估算的方法
6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。
A. n2      B. nlogn      C. n        D. logn
7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。
A. O(1)    B. O(n)    C. O(200n)    D. O(nlog2n)
CDCBBDD
第二章  线性表
单项选择题
1．链表不具有的特点是____ ____。
A. 可随机访问任一元素                B. 插入和删除时不需要移动元素
C. 不必事先估计存储空间              D. 所需空间与线性表的长度正比
2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为            。
A. 139            B. 140        C. 147              D. 148
3．在线性链表存储结构下，插入操作算法            。
A. 需要判断是否表满      B. 需要判断是否表空
C. 不需要判断表满        D. 需要判断是否表空和表满
4．在一个单链表中，若删除p所指结点的后继结点，则执行          。
A. p->next = p->next->next;    B. p->next = p->next;
C. p = p->next->next;          D. p = p->next; p->next = p->next->next;
5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为          。
A. O(n)      B. O(1)      C. O(m)        D. O(m+n)
6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是        。
A. 单链表        B. 静态链表      C. 线性链表          D. 顺序存储方式
ACCABB
填空题
1．在带表头结点的单链表中，当删除某一指定结点时，必须到该结点的_____结点。
2．在单链表中，指针p所指结点为最后一个结点的条件是      。
3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是          。
4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是        。
5．在长度为n的顺序表中插入一个元素的时间复杂度为        。
1前驱 
2 p->next==NULL
3.1
4.n-i+1
5.O(n)
例题解析
【例2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。
解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点
的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：
  void inverse(Lnode *h)
{s=h->next;
    if(s==NULL)  return;
  q=NULL;
  p=s;
  while(p!=NULL)
  { p=p->next;
    s->next=q;                        /*逆转指针*/
    q=s;                              /*指针前移*/
    s=p;
  }
  h->next=q;                          /*头指针h的后继是p*/
}
【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。
解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C中的元素c为
    例如：A=(3,5,8,11)
          B=(2,6,8,9,11,15,20)
则   C=(2,3,5,6,8,8,9,11,11,15,20)
实现本题功能的函数如下：
Lnode *hb(Lnode *pa,Lnode *pb)
{Lnode *p,*q,*pc;
pc=(Lnode*)malloc(sizeof(Lnode));          /*建立表c 的头结点pc*/
p=pc;                                  /*p指向C表头结点*/
while(pa!=NULL&&pb!=NULL)
    {
          q=(Lnode*)malloc(sizeof(Lnode));    /*建立新结点q*/
      if(pb->data<pa->data)  /*比较A、B表中当前结点的数据域值的大小*/
      {q->data=pb->data;        /*B中结点值小，将其值赋给q的数据域*/
        pb=pb->next;                              /*B中指针pb后移*/
        }
      else
      {q->data=pa->data;          /*相反，将A结点值赋给q的数据域*/
        pa=pa->next;                            /*A中指针pa后移*/
        }
p->next=q;                                /*将q接在p的后面*/
p=q;                                    /*p始终指向C表当前尾结点*/
}
while(pa!=NULL)            /*若表A比B长，将A余下的结点链在C表尾*/
    {q=(Lnode*)malloc(sizeof(Lnode));
    q->data=pa->data;
    pa=pa->next;
    p->next=q;
    p=q;
  }
while(pb!=NULL)          /*若表B比A长，将B余下的结点链在C表尾*/
    {q=(Lnode*)malloc(sizeof(Lnode));

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