数据结构(C语言版)习题及答案第二章.pdf

以铜为镜，可以正衣冠；以古为镜，可以知兴替；以人为镜，可以明得失。——《旧唐书·魏征列传》

可编辑

习题

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、单链表中各结点之间的地址（CD）。

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

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

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

向后移动（B）个元素。

A、n-iB、n-i+1C、n-i-1D、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、#defineN6

voidmain()

{ListSqL;

intA[N];

inti,elem;

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