一、选择题

1.线性表是〔  〕

A．一个有限序列，可以为空            B．一个有限序列，不可以为空

    C．一个无限序列，可以为空            D．一个无限序列，不可以为空

2.一维数组与线性表的特征是〔  〕。 

    A．前者长度固定，后者长度可变         B．两者长度均固定 

    C．后者长度固定，前者长度可变         D．两者长度均可变 

3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是(   ). 

    A．当前结点所在地址域                B．指针域 

    C．空指针域                            D．空闲域 

4.用链表表示线性表的优点是〔  〕。 

    A．便于随机存取                        B．便于进展插入和删除操作 

    C．占用的存储空间较顺序表少            D．元素的物理顺序与逻辑顺序一样 

5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O〔n〕。 

    A．遍历链表和求链表的第i个结点        D．删除地址为P的结点的后继结点

    B．在地址为P的结点之后插入一个结点 C．删除开场结点

6.下面关于线性表的表达中，错误的选项是〔  〕。 

    A．线性表采用顺序存储必须占用一片连续的存储单元 

    B．线性表采用顺序存储便于进展插入和删除操作 

    C．线性表采用链式存储不必占用一片连续的存储单元 

    D．线性表采用链式存储便于进展插入和删除操作

7.单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的选项是〔  〕。

A . q = p->next;          p->next = q->next ;

B . p->next = q->next;     q = p->next ;

    C . q->next = p->next;      p->next = q ; 

D . p->next = q;          q->next = p->next ;

8.设 al，a2， a3为三个结点； p , 10 , 20 代表地址，那么如下的链表存储构造称为〔  〕。

    A．链表            B．单链表        C．双向循环链表        D．双向链表 

9.单链表的存储密度〔  〕。 

    A．大于 1         B．等于1        C．小于1            D．不能确定 

10.己知一个顺序存储的线性表，设每个结点需占 m 个存储单元，假设第一个结点的地址al ，那么第i个结点的地址为〔  〕。

    A. al+(i-1)*m        B. al+i*m        C. al-i*m        D. al+(i+1)*m 

11.在 n 个结点的顺序表中，算法的时间复杂度是 O(l〕的操作是〔  〕。 

    A．访问第i个结点〔1≤i≤n〕和求第 i 个结点的直接前驱〔2≤i≤n) 

    B．在第 i 个结点之后插入一个新结点〔1≤i≤n-1〕 

    C．删除第 i 个结点〔 1≤i≤n ) 

    D．将 n 个结点从小到大排序 

12.在线性表中〔  〕只有一个直接前驱和一个直接后继。 

    A．首元素        B．中间元素        C．尾元素        D．所有元素 

13.对具有 n 个结点的线性表进展查找运算，所需的算法时间复杂度为〔  〕。 

    A. 0 (n2)        B. 0 (nlog2n)    C. O (log2n)        D. O (n) 

14.线性表采用顺序存储的缺点是〔  〕。 

    A．存储密度降低                            B．只能顺序访问    

    C．元素的逻辑顺序与物理顺序不一致        D．插入、删除操作效率低 

15.以下链表构造中，从当前结点出发能够访问到任一结点的是〔  〕。

    A．单向链表和双向链表                B．双向链表和循环链表   

    C．单向链表和循环链表                D．单向链表、双向链表和循环链表 

16.线性表是具有 n 个〔  〕的有限序列。 

    A．数据项        B．数据元素            C．表元素        D．字符 

17.假设长度为 n 的线性表采用链式存储构造，访问其第 i 个元素的算法时间复杂度为〔  〕。

    A. 0 ( l )        B. 0 ( n )            C. 0 ( n2 )        D. 0 ( log2n )

18.指针 P 指向循环链表 L 的首元素的条件是〔  〕。 

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

19.指针 P 所指的元素是双循环链表 L 的尾元素的条件是〔  〕。 

    A. P＝＝L     B. P->prior＝＝L    C. P＝＝NULL    D. P->next＝＝L 

20.不带头结点的单链表L为空的条件是(  )

    A. L!＝NULL        B. L＝＝NULL C. L->next＝＝NULL D. L->next＝＝L

21.带头结点的单链表L为空的条件是(  )

    A. L!＝NULL        B. L＝＝NULL    C. L->next＝＝NULL D. L->next＝＝L

22.两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件是〔  〕。 

A. P->next＝＝Q->next            B. P->next＝＝Q    

C. Q->next＝＝P                    D. P＝＝Q 

23.在长度为 n 的顺序表中，假设要删除第 i (1≤i≤n 〕个元素，那么需要向前移动元素的次数为〔  〕。 

    A. 1        B. n一i        C. n一i+1        D. n一i一l 

24.在长度为 n 的顺序表中第 i (1≤i≤n〕个位置上插入一个元素时，为留出插入位置所需移动元素的次数为〔  〕。

    A. n-i        B. i            C. n–i+1        D. n-i-l 

25.假定己建立以下动态链表构造，且指针 Pl 和 P2 已指向如下图的结点：那么以下可以将 P2 所指结点从链表中删除并释放该结点的语句组是(   )

A. pl->next=p2->next; free (pl);        B. pl=p2; free (p2);

    C. pl->next=p2->next；free (p2);     D. pl=p2->next; free (p2);

26.假设已建立如下图的单向链表，那么以下不能将 s 所指的结点插入到链表尾部，构成新的单向链表的语句组是〔  〕。

A . s->next = a->next->next ; a->next->next = s ;

B . a = a->next; a->next =s ; s->next = NULL ;

C . s->next = NULL ; a = a->next; a->next = s ;

    D . a = a->next ; s->next = a->next ; a->next = s->next ;

27.有如下函数，其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此函数的功能是〔  〕。

    Void   fun( struct node * hl , struct node * h2 ){ 

    struct node * t ; 

    t = hl ;

while ( t->next ! ＝'\\0' ) 

t = t->next ; t->next = h2 ;

    }  

    A．将链表 h2 接到链表 h1 后                B．将链表 h1 接到链表 h2 后 

    C．找到链表 hl 的最后一个结点由指针返回    D．将链表 hl 拆分成两个链表 

二、判断题

1.循环链表不是线性表. ( × )

2.线性表就是顺序存储的表。( × ) 

3.线性表只能用顺序存储构造实现。( × ) 

4.链表中的头结点仅起到标识的作用。( √ )

5.线性表的链式存储构造优于顺序存储。( × ) 

6.顺序存储的线性表可以实现随机存取。( √ ) 

7.顺序存储方式只能用于存储线性构造。( √ )

8.链表的每个结点都恰好包含一个指针域。( × )

9.所谓静态链表就是一直不发生变化的链表。( × ) 

10.集合与线性表的区别在于是否按关键字排序。( × ) 

11.取线性表的第i个元素的时间同i的大小有关. ( × ) 

12.顺序存储构造的主要缺点是不利于插入或删除操作。( √ )

13.线性表的特点是每个元素都有一个前驱和一个后继。( × ) 

14.对任何数据构造链式存储构造一定优于顺序存储构造。( × ) 

15.顺序存储方式的优点是存储密度大，插入、删除效率高。( × ) 

16.为了很方便的插入和删除数据，可以使用双向链表存放数据。( × ) 

17.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × ) 

18.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 

19.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( √ ) 

20.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。( √ ) 

21.在线性表的顺序存储构造中，逻辑上相邻的两个元素在物理位置上并不一定相邻。( × ) 

22.在线性表的顺序构造中，插入和删除元素时，移动元素的个数与该元素的位置有关。( × ) 

23.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储构造。( × ) 

24.链表是采用链式存储构造的线性表,进展插入、删除操作时，在链表中比在顺序存储构造中效率高。 ( √ ) 

25.在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开场查找任何一个元素。( √ )

26.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有一样的特性，因此属于同一数据对象。( √ )

三、填空题

1.顺序表中逻辑上相邻的元素在物理位置上        相邻。

2.在链表中逻辑上相邻的元素的物理位置            相邻。

3.带头结点的双循环链表L为空表的条件是：            。

4.在单链表p结点之后插入s结点的操作是：            。

5.

6.顺序表相对于链表的优点有            和            。

7.在双链表中要删除结点*p ，其时间复杂度为            。

8.在顺序表中访问任意一个结点的时间复杂度均为            。

9.链接存储的特点是利用            来表示数据元素之间的逻辑关系。

10.带头结点的双循环链表L中只有一个元素结点的条件是：            

11.在单链表L中，指针p所指结点有后继结点的条件是：            

12.

13.在单链表中除首结点外，任意结点的存储位置都由        结点中的指针指示。

14.指针p指向单链表L中的某结点，那么删除其后继结点的语句是：            

15.

16.在 n 个结点的单链表中要删除结点*p ，需要找到            .其时间复杂度为            。

17.链表相对于顺序表的优点有            和            操作方便；缺点是存储密度            。

18.建立单链表的算法时间复杂度               ；建立有序单链表的算法时间复杂度             。

19.在单链表中设置头结点的作用是                                                            。

20.对于双向链表,在两个结点之间插入一个新结点需修改的指针共            个，单链表为            个。

21.在一个长度为n的顺序表中第i个元素〔1<=i<=n〕之前插入一个元素时，需向后移动            个元素。

22.在循环链表中，可根据一个结点的地址访问整个链表，而单链表中需知道            才能访问整个链表。

23.顺序存储构造是通过            表示元素之间的关系的;链式存储构造是通过            表示元素之间的关系的。

24.有一单链表构造如下，假设要删除值为 c 的结点，应做的操作是                                            

25.在 n 个结点的顺序表中插入一个结点，平均需要移动            个结点，具体的移动次数取决于                        。

26.在 n 个结点的顺序表中删除一个结点，平均需要移动            个结点，具体的移动次数取决于                        。

27.在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是            、            、            、            。

28.线性表L=〔a1,a2,…,an〕用数组表示，假定删除表中任一元素的概率一样，那么删除一个元素平均需要移动元素的个数是            。

29.循环单链表与非循环单链表的主要不同是，循环单链表尾结点的指针         ，而非循环单链表的尾结点指针                     。

30.当线性表的元素总数根本稳定，且很少进展插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用            存储构造。

31.线性表 L = ( a1, a2 ， … ，an〕用数组存储。假定删除表中任一元素的概率一样，那么删除一个元素平均需要移动的元素个数是             。

32.在单链表中要在结点*p 之前插入一个新结点，需找到            ，其时间复杂度为            ；而在双链表中，完成同样操作时其时间复杂度为        。

33.对于一个具有n个结点的单链表，在的结点*p后插入一个新结点的时间复杂度为            ,在给定值为x的结点后插入一个新结点的时间复杂度为            。

34.根据线性表的链式存储构造中每一个结点包含的指针个数，将线性链表分成            和            ；而又根据指针的连接方式，链表又可分成            和            。

35.在双向链表构造中，假设要求在p 指针所指的结点之前插入指针为s 所指的结点，那么需执行以下语句：

s^ .next:=p； s^ .prior:=             ；p^ .prior:=s；            :=s；

36.设单链表的结点构造为(data,next)，next为指针域，指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 假设将结点y插入结点x之后，那么需要执行以下语句:             ；             ;

37.设有结点定义如下，且已建立如以下图所示的带有头结点的单向链表：

  struct  node 

{ int data ;

  struct  node * next ; };

函数 sum 的功能是：计算链表中各结点数据域之和，作为函数值返回。请填空。 

int sum (struct  node * head ) 

{ int   s = 0 ; 

struct node * p ;

p = head->next ;

 do

{ s= s＋              ；

p = p->next ; }

 while ( p ! ＝          )；

return  s; }

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.己知 head 指向一个带有头结点的单向链表，链表中每个结点包含整型数据域〔 data ) 和指针域〔 next 〕。以下算法用来查找链表所有结点中数据域值最大的结点的位置，由指针 s 传回调用程序。请填空。

struct link { 

    char data ; 

    struct link  *next;};

main ( ){

    struct link  * head , * q ; 

    findmax ( head , & q ) ;

printf ( " max = % d \\ n " , q->data ) ; }

findmax ( struct  link * head , struct  link * * s ) { 

    struct link * p ; 

p = h ead->next ;

    * s = p ; 

    while 〔            〕{ 

            p ＝                ; 

if ( p->data ＞             )

    * s=p ; } }

20.设线性表顺序存储构造定义如下：

# define MAXSIZE 20

typedef int datatype

type struct {

    datatype data [ MAXSIZE + l ] ; 

    int last ; 

}sequenlist ; 

    函数 int 1ocate2 ( sequenlist * L , int  x ) ；利用在表头设立监视哨    的算法，实现在顺序表 L 中查找值为 x 的元素的位置。请填空。 

    int locate2 ( sequenlist  * L , int x ) { 

        int  i =              ；

     L->data [0] = x ;

     while ( L->data[i]! = x 〕

                    ;

return  i ; }

21.设有两个由尾指针表示的带有头结点的单向环形链表 ra 和 rb ，以下算法实现将rb 所指的链表连接到 ra 所指链表之后。请填空。 

LinkList * Connect (LinkList * ra , LinkList * rb ){

    LinkList * p ;

p = ra->next ;

ra->next ＝              ；

free ( rb->next ) ;

    rb一＞ next =                 ；

    return  rb; }下载本文