数据结构(C语言版)习题及答案

习 题

2.1选择题

1、线性表的顺序存储结构是一种（ A ）的存储结构，线性表的链式存储结构是一种（ B ）的存储结构。

A、随机存取 B、顺序存取 C、索引存取 D、散列存取

2、对于一个线性，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该选择（ B ）。

A、顺序存储方式 B、链式存储方式

C、散列存储方式 D、索引存储方式

3、已知，L是一个不带头结点的单链表，p指向其中的一个结点，选择合适的语句实现在p结点的后面插入s结点的操作（ B ）。

A、p->next=s ; s->next=p->next ; B、s->next=p->next ; p->next=s ;

C、p->next=s ; s->next=p ; D、s->next=p ; p->next=s ;

4、单链表中各结点之间的地址（ C D ）。

A、必须连续 B、部分地址必须连续

C、不一定连续 D、连续与否都可以

5、在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（ B ）个元素。

A、n-i B、n-i+1 C、n-i-1 D、i

2.2填空题

1、顺序存储的长度为n的线性表，在任何位置上插入和删除操作的时间复杂度基本上都一样。插入一个元素大约移动表中的（ n/2 ）个元素，删除一个元素时大约移动表中的（ (n-1)/2 ）个元素。

2、在线性表的顺序存储方式中，元素之间的逻辑关系是通过（物理顺序）来体现的；在链式存储方式，元素之间的逻辑关系是通过（指针）体现的。

3、对于一个长度为n的单链表，在已知的p结点后面插入一个新结点的时间复杂度为（o(1)），在p结点之前插入一个新结点的时间复杂度为（o(n)），在给定值为e的结点之后插入一个新结点的时间复杂度为（o(n)）。

4、在双向链表中，每个结点包含两个指针域，一个指向（前驱）结点，另一个指向（后继）结点。

5、对于循环链表来讲，逐个访问各个结点的结束判断条件是（设P为指向结点的指针，L为链表的头指针，则p->next= =L）。

2.3读下面的程序段，画出执行过程的示意图及所完成的功能。

1、 # define N 6

void main ( )

{ ListSq L ;

int A[ N ];

int i , elem ;

InitList(L); //初始化函数

for ( int j=0; j<N; j++)

scanf("%d",&A[ j ]) ;

for ( int m=0; m<N; m++)

InsertList ( L , m ,A[m]) ;

PrintList( L ) ; // 输出函数}