一、单项选择题（共30题，每题1分，共计30分）

 1．对于线性表基本运算，以下结果是正确的是                    (   )

   A.初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф

   B. 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度

   C.插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X为值的新结点

   D.删除DELETE(L,i), 引用型运算.其作用是撤销线性表L的第i个结点Ai

2.线性结构中的一个结点代表一个                                 （  ）

  A. 数据元素        B. 数据项        C. 数据       D. 数据结构

3．顺序表的一个存储结点仅仅存储线性表的一个                    （    ）

  A. 数据元素        B. 数据项        C. 数据       D. 数据结构         

4．顺序表是线性表的                                             （    ）

  A.链式存储结构     B.顺序存储结构   C. 索引存储结构    D. 散列存储结构

5.对于顺序表，以下说法错误的是                      （     ）

  A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址

  B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列

  C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻

  D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中

6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（   ）为标准操作.

  A.条件判断        B.结点移动

  C.算术表达式      D.赋值语句

7.对于顺序表的优缺点，以下说法错误的是         （      ）

  A.无需为表示结点间的逻辑关系而增加额外的存储空间

  B.可以方便地随机存取表中的任一结点

  C.插人和删除运算较方便

  D.由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

  E.容易造成一部分空间长期闲置而得不到充分利用

8.指针的全部作用就是                             （       ）

  A.指向某常量        B. 指向某变量

  C.指向某结点        D.存储某数据

9.单链表的一个存储结点包含　　　　　　　　　　　　　（　　　　）

  A.数据域或指针域

  B.指针域或链域

  C.指针域和链域

  D.数据域和链域

10．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是      （  ）

A.将“指针型变量”简称为“指针”

B.将“头指针变量”称为“头指针”

C.将“修改某指针型变量的值”称为“修改某指针”

D.将“p中指针所指结点”称为“P值”

11．设指针P指向双链表的某一结点，则双链表结构的对称性可用（  ）式来刻画

A. p->prior->next->==p->next->next

B. p->prior->prior->==p->next->prior

C. p->prior->next->==p->next->prior

D. p->next->next==p->prior->prior

12.以下说法错误的是 （  ）              

A.对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表

B.对单链表来说，只有从头结点开始才能扫描表中全部结点

C.双链表的特点是找结点的前趋和后继都很容易

D.对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

13．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是  （  ）

A. rear和rear->next->next

B. rear->next 和rear

C. rear->next->next和rear

D. rear和rear->next

14.以下说错误的是  (  )

A.对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）

B.读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构.

C.在链表上实现读表元运算的平均时间复杂性为O（1）

D.链入、摘除操作在链表上的实现可在O（1）时间内完成

E.链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n）

15．循环链表主要优点是      （  ）

A.不再需要头指针了

B.已知某个结点的位置后，能够容易找到它的直接前趋

C.在进行插入、删除运算时，能更好地保证链表不断开

D.从表中任一结点出发都能扫描到整个链表

16．以下说法错误的是   （  ）

A.数据的物理结构是指数据在计算机内实际的存储形式

B.算法和程序没有区别，所以在数据结构中二者是通用的

C.对链表进行插人和删除操作时，不必移动结点

D.双链表中至多只有一个结点的后继指针为空

17．以下说法正确的是

A.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继

B.线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低

C.在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置及表长有关

D.顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动

18．以下说法错误的是  （  ）

A.求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B.顺序存储的线性表可以随机存取

C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D.线性表的链式存储结构优于顺序存储结构

19.以下说法正确的是（     ）

A.顺序存储方式的优点是存储密度大、且插入、删除运算效率高

B.链表的每个结点中都恰好包含一个指针

C.线性表的顺序存储结构优于链式存储结构

D.顺序存储结构属于静态结构，链式结构属于动态结构

20.下面关于线性表的叙述正确的是(     )

A.线性表采用顺序存储，不必占用一片连续的存储单元

B.线性表采用顺序存储，便于进行插人和删除操作

C.线性表采用链接存储，不必占用一片连续的存储单元

D.线性表采用链接存储，不便于插人和删除操作

21.线性表L=(a₁,a₂,...,a_i,...,a_n),下列说法正确的是(  )

A.每个元素都有一个直接前驱和直接后继

B.线性表中至少要有一个元素

C.表中诸元素的排列顺序必须是由小到大或由大到小的

D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继

22.线性表的逻辑顺序与存储顺序总是一致的，这种说法(  )

A.正确                B.不正确

23.设p,q是指针,若p=q,则*p=*q ,这种说法(     )      

A.正确                B.不正确

24.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为(      )

A. p=rear;                           B. rear=rear->next;

rear=rear->next;                   free(rear);

free(p)

C. rear=rear->next->next;            D. p=rear->next->next;

free(rear);                        rear->next->next=p->next;

                                         free(p);

25. 单链表中，增加头结点的目的是为了  (  )

A.使单链表至少有一个结点     B.标示表结点中首结点的位置

C.方便运算的实现             D.说明单链表是线性表的链式存储实现

26.线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着

A.每个结点所代表的数据元素都一样。

B.每个结点所代表的数据元素包含的数据项的个数要相等

C.不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致

D.结点所代表的数据元素有同一特点

27．带头结点的单链表Head为空的判定条件是

A. Head=Null          B. Head->next=NULL     C.Head->next=Head

28.非空的单循环链表L的尾结点*P,满足

A. P->next=NULL       B.P=NULL           C. P->next=L       D.  P=L.

29.双向链表结点结构如下：

LLink

data

RLink

其中：LLink是指向前驱结点的指针域：

data是存放数据元素的数据域；

Rlink是指向后继结点的指针域。

下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。不能正确完成要求的算法段是

A. Q->LLink=P->LLink;             B. P->LLink=Q;

Q->Rlink=P;                          Q->Rlink=P;

P->LLink=Q;                          P->LLink->Rlink=Q;

P->LLink->Rlink=Q;                 Q->LLink=P->LLink;

C. Q->LLink=P->LLink;

Q->Rlink=P;

P->LLink->Rlink=Q;

P->LLink=Q;

30.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（   ）存储方式最节省时间。

A. 顺序表        B. 单链表        C. 双链表        D. 单循环链表

二、 填空题（每空4分，共20分）

1、已知p结点是某双链表的中间结点，试从下列提供的答案这选择合适的语句序列。

      ①在p结点后插入s结点的语句序列是___                           __；

      ②在p结点前插入s结点的语句序列是___                           __；

      ③删除p结点的直接后继结点的语句序列是____                     ___；

      ④删除p结点的直接前驱结点的语句序列是_                     ______；

      ⑤删除p结点的语句序列是____                                   ___。

（1）P->next=p->next->next ;    (2) P->prior=p->prior->prior;    (3) P->next=S;     

 (4) p->prior=S;                (5) S->next=P;               (6) S->prior=P;

(7) S->next=P->next;           (8) S->prior=P->prior;         (9) P->prior->next=P->next;      

(10) P->prior->next=P;         (11) P->next->prior=P;         (12) P->next->prior=S ;   

(13) P->prior->next=S;         (14) P->next->prior=P->prior;    (15) Q=P->next;     

(16) Q=P->prior;              (17) free(P);                 (18) free(Q);

三、读程序写结果（共4题，每题8分，共计32分）

1. #include<stdio.h>

int main()

{

    int i, a, b, c, d, f[4];

    for (i = 0; i < 4; i++)

       scanf ("%d", &f[i]);

    a = f[0] + f[1] + f[2] + f[3];

    a = a / f[0];

    b = f[0] + f[2] + f[3];

    b = b / a;

    c = (b * f[1] + a) / f[2];

    d = f[(b / c ) % 4];

    if(f[(a + b + c + d) % 4] > f[2])

       printf("%d\n", a + b);

    else

       printf("%d\n", c + d);

    return 0;

}

输入：9 19 29 39   

输出：                       

2．#include<stdio.h>

void foo(int a, int b, int c)

{

    if(a > b)

       foo(c, a, b);

    else

       printf("%d,%d,%d\n", a, b, c);

}

int main()

{

    int a, b, c;

    scanf("%d %d %d", &a, &b, &c);

    foo(a, b, c);

    return 0;

}

输入: 3 1 2                   输出:                      

3．#include <stdio.h>

void func(int ary[], int n )

{

    int i=0, j, x;

    j=n-1;

    while(i<j)

    {

       while (i<j&&ary[i]>0) i++;

       while (i<j&&ary[j]<0) j--;

       if (i<j){

           x=ary[i];

           ary[i++]=ary[j];

           ary[j--]=x;

       }

    }

}

int main()

{

    int a[20], i, m;

    m=10;

    for(i=0; i<m; i++)

       scanf("%d", &a[i]);

    func(a, m);

    for (i=0; i<m; i++)

       printf( "%d ", a[i] );

    printf("\n");

    return 0;

}

输入：5 4 -6 -11 6 -59 22 -6 1 10            输出：                               

4. #include<stdio.h>

#define MAX 100

void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)

{

    int i, root_m;

    if(spos_f > epos_f)

       return;

    for(i = spos_m; i <= epos_m; i++)

       if(first[spos_f] == mid[i])

       {

           root_m = i;

           break;

       }

    solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);

    solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);

    printf("%c", first[spos_f]);

}

int main()

{

    char first[MAX], mid[MAX];

    int len;

    scanf("%d", &len);

    scanf("%s", first);

    scanf("%s", mid);

    solve(first, 0, len - 1, mid , 0, len - 1);  

    printf("\n");

    return 0;

}

输入：  7

ABDCEGF

BDAGECF                   输出：                           

四、完善程序（共10题，每题3分，其中第4、7、8题，每题4分，第9题8（3+3+2）分。共38分）

1、INITIATE()的功能是建立一个空表。请在________处填上正确的语句。

    lklist initiate_lklist()                      

{ t = malloc (size);

 ________________;

  return(t);

}

2、以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。

Void insert_sqlist(sqlist L，datatype x，int i)

 

{ if( L.last == maxsize) error(“表满”)；

if((i<1)||(i>L.last+1))error(“非法位置”);

for (j=L.last;j>=i;j--)______;

L.data [i-1]=x;

L.last =L.last+1;

}

3、以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。

void delete_sqlist(sqlist L,int i) 

{if((i<1)||(i>L.last))error(“非法位置”)；

  for(j=i+1;j<=L.last;j++)________;

  L.last=L.last-1;

}

4、以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。

    int length_lklist(lklist head)           

    {________;

j=0;

while(p->next!=NULL)

    {________________;

     j++;

}

return(j);                             

}

5、以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。

  pointer find_lklist(lklist head,int i)

    { p=head;j=0;

      while(________________)

        { p=p->next; j++; }

          if(i==j) return(p);

          else return(NULL);

}

6、以下为单链表的定位运算，分析算法，请在____处填上正确的语句。

    int locate_lklist(lklist head,datatype x)

   

   { p=head;j=0;

while(________________________________){p=p->next;j++;}

if (p->data==x) return(j);

else            return(0);

}

7、以下为单链表的删除运算，分析算法，请在____处填上正确的语句。

    void delete_lklist(lklist head,int i)

{ p=find_lklist(head,i-1);

  if(____________________________)

    { q=________________;

      p->next=p->next->next;

      free(q);

    }

    else error(“不存在第i个结点”)

}

8、以下为单链表的插入运算，分析算法，请在____处填上正确的语句。

    void insert_lklist(lklist head,datatype x,int i)

   

   { p=find_lklist(head,i-1);

if(p==NULL)error(“不存在第i个位置”)；

else {s= mailloc(size);____________=x;

       s->next=________________;

       p->next=s;

      }

}

9、以下为单链表的建表算法，分析算法，请在____处填上正确的语句。

    lklist create_lklist2()           

{ head=malloc(size);

  p=head;

  scanf(“%f”,&x);

  while(x!=’$’)

    { q=malloc(size);

       q->data=x;

       p->next=q;

      ________________;

       scanf(“%f”,&x);   }

  ________________;

  return(head);

}             此算法的量级为________________。

10、以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。

int locate_sqlist(sqlist L,datatype X)

 

{i=1;

 while((i≤L.last)&&(L.data[i]!=X))i++;

 if(________)return(i);

    else   return(0);

}

 

线性表复习试题二答案（满分120分）

一、 单项选择题（共30题，每题1分，共计30分）

 

1	2	3	4	5	6	7	8	9	10
B	A	A	B	A	B	C	C	D	D
11	12	13	14	15	16	17	18	19	20
C	A	B	C	D	B	C	D	D	C
21	22	23	24	25	26	27	28	29	30
D	B	B	D	C	C	B	C	B	A

 

二、 填空题（每空4分，共20分）

      ①_    7 3 12 6              __；②__      8 13 4 5          _；

      ③____   15 1 18           ___；④_       16 2 18       _____；

      ⑤___     9 14 17              。

三、阅读程序写结果（共4题，每题8分，共计32分）

1、                   23                    2、             2 3 1              

3、 5 4 10 1 6 22 -59 -6 -11 -6     4、        DBGEFCA               

三、 完善程序（共10题，每题3分，其中第4、7、8题，每题4分，第9题8（3+3+2）分。共38分） 

1、t->next=NULL

2、L．data[j]=L．data[j-1]

3、L.data[j-2]=L.data[j-1]

4、p=head  p=p->next

5、(p->next!=NULL)&&(j<I)

6、(p->next!=NULL)&&(p->data!=x)

7、(p!=NULL)&&(p->next!=NULL)  p->next

8、s->data,  p->next

9、p=q(或者p=p->next)  p->next=NULL   O(n)

10、L.data[i]==x