第2章-线性表习题及参考答案

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;参考答案：B5.在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next;（C）p->next=p->next; （D）p =p->next->next;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第二章线性表习题及答案‎一、基础知识题‎2.1 试描述头指‎针、头结点、开始结点的‎区别、并说明头指‎针和头结点‎的作用。

答：始结点是指‎链表中的第‎一个结点，也就是没有‎直接前趋的‎那个结点。

链表的头指‎针是一指向‎链表开始结‎点的指针(没有头结点‎时)，单链表由头‎指针唯一确‎定，因此单链表‎可以用头指‎针的名字来‎命名。

头结点是我‎们人为地在‎链表的开始‎结点之前附‎加的一个结‎点。

有了头结点‎之后，头指针指向‎头结点，不论链表否‎为空，头指针总是‎非空。

而且头指针‎的设置使得‎对链表的第‎一个位置上‎的操作与在‎表其他位置‎上的操作一‎致(都是在某一‎结点之后)。

2.2 何时选用顺‎序表、何时选用链‎表作为线性‎表的存储结‎构为宜?答：在实际应用‎中，应根据具体‎问题的要求‎和性质来选‎择顺序表或‎链表作为线‎性表的存储‎结构，通常有以下‎几方面的考‎虑：1.基于空间的‎考虑。

当要求存储‎的线性表长‎度变化不大‎，易于事先确‎定其大小时‎，为了节约存‎储空间，宜采用顺序‎表；反之，当线性表长‎度变化大，难以估计其‎存储规模时‎，采用动态链‎表作为存储‎结构为好。

2.基于时间的‎考虑。

若线性表的‎操作主要是‎进行查找，很少做插入‎和删除操作‎时，采用顺序表‎做存储结构‎为宜；反之，若需要对线‎性表进行频‎繁地插入或‎删除等的操‎作时，宜采用链表‎做存储结构‎。

并且，若链表的插‎入和删除主‎要发生在表‎的首尾两端‎，则采用尾指‎针表示的单‎循环链表为‎宜。

2.3 在顺序表中‎插入和删除‎一个结点需‎平均移动多‎少个结点?具体的移动‎次数取决于‎哪两个因素‎?答：在等概率情‎况下，顺序表中插‎入一个结点‎需平均移动‎n/2个结点。

删除一个结‎点需平均移‎动(n-1)/2个结点。

具体的移动‎次数取决于‎顺序表的长‎度n以及需‎插入或删除‎的位置i。

i 越接近n‎则所需移动‎的结点数越‎少。

2.4 为什么在单‎循环链表中‎设置尾指针‎比设置头指‎针更好?答：尾指针是指‎向终端结点‎的指针，用它来表示‎单循环链表‎可以使得查‎找链表的开‎始结点和终‎端结点都很‎方便，设一带头结‎点的单循环‎链表，其尾指针为‎rear，则开始结点‎和终端结点‎的位置分别‎是rear‎->next->next 和rear, 查找时间都‎是O(1)。

第二章线性表练习题一、选择题1.线性表是具有n个的有限序列。

A、表元素B、字符C、数据元素D、数据项E、信息项2.线性表的静态链表存储结构与顺序存储结构相比优点是。

A、所有的操作算法实现简单B、便于随机存储C、便于插入和删除D、便于利用零散的存储器空间3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。

A、O(log2n)B、O(1)C、O(n)D、O(n2)4.（1）静态链表既有顺序存储的特点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关；（2）静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加；（3）静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是。

A、（1）、（2）B、（1）C、（1）、（2）、（3）D、（2）6.在双向链表存储结构中，删除p所指的结点时须修改指针。

A、p－＞next－＞prior=p－＞prior; p－＞prior－＞next=p－＞next;B、p－＞next=p－＞next－＞next;p－＞next－＞prior=p;C、p－＞prior－＞next=p;p－＞prior=p－＞prior－＞prior;D、p－＞prior=p－＞next－＞next;p－＞next=p－＞prior－＞prior;7.在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是。

A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q;B、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next;C、q－＞prior=p; q－＞next=p－＞next; p－＞next－＞prior=q; p－＞next=q;D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q;8.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。

第二章线性表习题(答案)1.描述以下三个概念的区别：头指针，头结点，首元素结点。

首元结点是指链表中存储线性表中第一个数据元素a1的结点。

为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。

否则表示空表的链表的头指针为空。

2.填空：（1）在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置也相邻。

在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。

3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：（4）、（1）。

b. 在P结点前插入S结点的语句序列是：（7）、（11）、（8）、（4）、（1）。

c. 在表首插入S结点的语句序列是：（5）、（12）。

d. 在表尾插入S结点的语句序列是：（11）、（9）、（1）、（6）。

供选择的语句有：（1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next;（4）S->next= P->next; （5）S->next= L; （6）S->next= NULL;（7）Q= P; （8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next; （10）P= Q;（11）P= L; （12）L= S; （13）L= P;4.设线性表存于a[n]中且递增有序。

第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。

(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next=s;s->next=p;参考答案：B5.在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next;（C）p->next=p->next; （D）p =p->next->next;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）2.如果没有提供指针类型的语言，就无法构造链式结构。

（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

《数据结构》吕云翔编著第2章线性表习题解答数据结构第2章线性表习题解答一、习题解答1. 假设有一个线性表L={a1, a2, ..., an}，设计一种算法，将线性表的所有元素逆置。

解答：可以使用两个指针i和j，分别指向线性表的第一个元素和最后一个元素，然后交换这两个指针所指向的元素，接着i向后移动一个单位，j向前移动一个单位，再次交换他们所指向的元素。

依次类推，直到i和j指针相遇为止。

这样就完成了线性表的逆置。

2. 设线性表L={a1, a2, ..., an}，设计一个算法，删除其中所有值为x 的元素。

解答：可以使用一个指针i遍历线性表，当遇到一个元素值等于x 时，将该元素删除，同时将后面的元素依次前移一位。

直到整个线性表遍历完毕。

3. 设有两个线性表LA={a1, a2, ..., am}和LB={b1, b2, ..., bn}，其中元素递增有序排列。

设计一个算法，将LA和LB合并成一个新的线性表LC，且元素递增有序排列。

解答：可以使用两个指针i和j分别指向LA和LB的第一个元素，并且使用一个指针k指向LC的最后一个元素。

比较LA[i]和LB[j]的大小，将较小的元素插入到LC的末尾，然后相应指针后移一位，直到其中一个指针到达对应线性表的末尾。

最后，将剩余的元素插入到LC的末尾，即可得到合并后的线性表LC。

4. 设线性表L={a1, a2, ..., an}，设计一个算法，找出其中最大的元素以及最大元素的位置。

解答：可以使用一个变量max记录当前遍历到的最大元素，初始化为L[0]，同时使用变量position记录最大元素的位置，初始值也为0。

然后遍历整个线性表，若遇到L[i]大于max，则更新max为L[i]，同时更新position为i。

遍历完毕后，max就是最大元素，position就是最大元素的位置。

5. 在线性表L={a1, a2, ..., an}中，设计一个算法，找出倒数第k个位置上的元素。

第二章线性表习题一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表 (B)双链表 (C)单循环链表 (D)带头结点的双循环链表6．循环链表的主要优点是( )。

第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。

（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。

（4）链接存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

（7）单链表的存储密度（）。

A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。

习题二参考答案一、选择题1.链式存储结构的最大优点是（ D ）。

A.便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作2.假设在顺序表{a0,a1,……,a n－1}中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。

A.106B. 107C.124D.1283.在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。

A.顺序表B. 带头结点的单链表C.不带头结点的单链表D. 循环单链表4.在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。

A.顺序表B. 用头指针标识的循环单链表C. 用尾指针标识的循环单链表D. 双向链表5.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为S,则修改链的java语句序列是（ D ）。

A.s.setNext(p); q.setNext(s);B. p.setNext(s.getNext()); s.setNext(p);C. q.setNext(s.getNext()); s.setNext(p);D. p.setNext(s); s.setNext(q);6.在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。

A.O(1)B. O(log2n)C. O(n)D. O(n2)7.要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，需要移动（ B ）个数据元素。

A.iB. n-i-1C. n-iD. n-i+18.在带头结点的双向循环链表中的p结点之后插入一个新结点s，其修改链的java语句序列是（ D ）。

A.p.setNext(s); s.setPrior(p); p.getNext().setPrior(s);s.setNext(p.getPrior());B.p.setNext(s); p.getNext().setPrior(s); s.setPrior(p);s.setNext(p.getNext());C.s.setPrior(p); s.setNext(p.getNext()); p.setNext(s);p.getNext().setPrior(s);D.s.setNext(p.getNext()); s.setPrior(p); p.getNext().setPrior(s);p.setNext(s);9.顺序表的存储密度是（ B ），而单链表的存储密度是（ A ）。