数据结构第二章习题

第2章 线性表

一、单项选择题

1．线性表是具有n个_________的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项 2．线性表是_________。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 3．线性表采用链表存储时，其地址_________。

A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 4．链表不具备的特点是_________。

A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

A．输出第i(1≤i≤n)个元素值

B．交换第1个元素与第2个元素的值 C．顺序输出这n个元素的值

D．输出与给定值x相等的元素在线性表中的序号

6．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。 A．删除指定的元素

B．在最后一个元素的后面插入一个新元素 C．顺序输出前k个元素

D．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)

7．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。

A．单链表 B．双链表

C．单循环链表 D．顺序表 8．与单链表相比，双链表的优点之一是_________。

A．插入和删除操作更简单 B．可以进行随机访问 C．可以省略表头指针或表尾指针 D．访问前后相邻结点更灵活 9．带头结点的单链表L为空的判定条件是_________。

A．L= =NULL B．L->next= =NULL C．L->next= =L D．L!=NULL

10．在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

11．在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单逻表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素

12．对于一个具有n个元素的线性表，建立其单链表的时间复杂度_________。 A．O(log2n) B．O(1) C．O(n2) D．O(n)

二、填空题

1．在线性表的顺序存储中，元素之间的逻辑关系是通过_________决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。 2．向一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_________个元素。

3．在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动________个元素。

4．为了设置一个空的顺序表L，应采用的操作是_________。

5．删除顺序表的_________元素，不需要移动任何元素。 6．删除顺序表的_________元素，需要移动的元素最多。

7．在顺序表_________元素后面插入一个元素，不需要移动任何元素。 8．在顺序表的第_________元素前插入元素1个元素，需要移动的元素最多。 9． 在长度为n的顺序表L中查找与指定元素值相同的元素，其时间复杂度为_________。

10．在单链表中设置头结点的作用是_________。

11．在单链表中，要删除某一指定的结点，必须找到该结点的_________结点。 12．访问单链表中的结点，必须沿着_________依次进行。 13．求单链表长度的时间复杂度为_________。

14．删除单链表L中某结点*p之后的一个结点，其时间复杂度为_________。 15．删除单链表L中某结点*p之前的一个结点，其时间复杂度为_________。 16．在一个单链表L中，指针p指向L的某个结点，在p之前插入一个指针s所指结点时的操作为： (1) s->next=_________； (2) p->next=s； (3) t=p->data；

(4) p->data=_________； (5) s->data=_________；

17．在一个单链表（已知每个结点含有数据域data和指针域next）中删除p所指结点时的操作为： (1) q=p->next； (2) p->data=q->data； (3) p->next=_________； (4) free(q)；

18．在一个单链表L中，p指向L中的某个结点，在指针p指向的结点之后插入

指针s指向的结点时，应执行s->next=_________和p->next=_________的操作。

19．对于一个具有n个结点的单链表，在指针p指向结点之后插入一个新结点的

时间复杂度是_________；在给定值为x的结点后插入一个新结点的时间复杂度是_________。

三、判断题

1．线性表中每个元素都有一个直接前驱和一个直接后继。 2．线性表中所有元素的排列顺序必须由小到大或由大到小。 3．线性表的顺序存储结构优于链式存储结构。

4．在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。

5．在单链表中，可以从头结点开始查找任何一个结点。

6．在双链表中，可以从任一结点开始沿同一方向查找到任何其他结点。

四、简答题

1．简述顺序表和链表存储方式的特点。 2．在什么情况下使用顺序表比链表好。

3．若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构，为什么？

4．对链表要设置头结点的作用是什么？（至少说出两条好处）

5．在单链表．双链表和单循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去（不允许进行结点之间数据域的复制）？若可以，其时间复杂度各为多少？

五、算法设计题

1．设计一个求元素逆置的算法。

(1) 将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。 (2) 将带头结点的单链表的所以元素逆置，要求空间复杂度为O(1)。 2．设计一些有关删除元素的算法。

(1) 从顺序表中删除所有元素值为x的元素，要求空间复杂为O(1)。

(2) 从顺序表中删除元素值在x到y（x≤y）之间的所有元素，要求空间复杂度为O(1)。

(3) 从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 (4) 从单链表L中删除值为x的结点的直接前驱结点。 (5) 从带头结点的单链表L中删除一个最小值的结点。

(6) 从一个递增单链表中，删除值域重复的结点。并分析算法的时间复杂度。 (7) 从一个非有序单链表（允许出现值域重复的结点）中，删除值域重复的结点。

(8) 从一个带头结点递增有序表的单链表L中，删除表中data值在大于或等于min且小于或等于max之间的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。

(9) 从一个带头结点非有序表的单链表L中，删除表中data值在大于或等于min且小于或等于max之间的结点（若表中有这样的结点），同时释放被删结点的空间，这里min和max是两个给定的参数。并分析算法的时间复杂度。 3．设计与集合运算有关的算法。

(1) 用顺序表表示集合，实现集合的交集、并集和差集的运算。 (2) 用单链表表示集合，实现集合的交集、并集和差集的运算。 4．综合问题的算法

(1) 设有一个顺序表Ｌ，其元素为整型数据，设计一个算法将Ｌ中所有小于０

的整数放在前半部分，大于０的整数放在后半部分。

(2) 设C={a1,b1,a2,b2,…,an, bn }为一线性表，采用带头结点的hc单链表存放，

设计一个就地算法，将其拆分为两个线性表，使得： A={ a1,a2,…, an},B={ b1, b2,…, bn} 作业：

1．设计一个算法判定单链表L（带头结点）是否是递增的。

2．有一个带头结点的单链表L，其ElemType类型为int，设计一个算法使其元素递增有序。

本文来源：https://www.bwwdw.com/article/j6rt.html