数据结构习题解答

C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 （ ）4. 计算机算法指的是：C

A．计算方法 B．排序方法 C．解决问题的有限运算序列 D．调度方法

（ ）5. 计算机算法必须具备输入、输出和 等5个特性。B A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性

第2章 线性表

一、基本内容

线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。

二、学习要点

1．了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

2．熟练掌握这两类存储结构的描述方法，如一维数据中一个区域[i..j]的上、下界和长度之间的变换公式（L=j-i+1,i=j-L+1,j=i+L-1）,链表中指针P和结点*p的对应关系（结点*(p->next)是结点*p的后继等），链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内在动态分配的编程技术是学好本章的基本要求。 3．熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。

4．熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。

5．能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

三、基础知识题

2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是当对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这3个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。

2.2 填空题

1. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。答：表中一半，表长和该元素在表中的位置

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

答：必定，不一定

3. 在单链表中，除了首元结点外，任一结点的存储位置由 指示。其前驱结点的链域的值 4．在单链表中设置头结点的作用是 。插入和删除首元素时不必进行特殊处理

2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是 。4，1

b.在P结点前插入S结点的语句序列是 。7，11，8，4，1 c.在表首插入S结点的语句序列是 。5，12 d.在表尾插入S结点的语句序列是 。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;

2.7 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a.删除P结点的直接后继结点的语句序列是 。11，3，14

b.删除P结点的直接前驱结点的语句序列是 。10，12，8，11，3，14 c.删除P结点的语句序列是 。10，12，7，3，14 d.删除首元结点的语句序列是 。12，11，3，14 e.删除尾元结点的语句序列是 。9，11，3，14 （1）P=P->next; （2）P->next=P;

（3）P->next=P->next->next; （4）P=P->next->next;

（5）while (P!=NULL) P=P->next;

（6）while (Q->next!=NULL) {P=Q; Q=Q->next;} （7）while (P->next!=Q) P=P->next; （8）while (p->next->next!=Q) P=P->next; （9）while (P->next->next!=NULL) P=P->next; （10）Q=P; （11）Q=P->next; （12）P=L; （13）L=L->next; （14）free(Q);

2.8 已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是 。7，12，3，6 b.在P结点前插入S结点的语句序列是 。8，13，5，4 c.删除P结点的直接后继结构的语句序列是 。15，1，11，18 d.删除P结点的直接前驱结点的语句序列是 。16，2，10，18

e.删除P结点的语句序列是 。9，14，17 （1）P->next=P->next->next; （2）P->priou=P->priou->priou; （3）P->next=S; （4）P->priou=S; （5）S->next=P; （6）S->priou=P; （7）S->next=P->next; （8）S->priou=P->priou; （9）P->priou->next=P->next; （10）P->priou->next=P; （11）P->next->priou=P; （12）P->next->priou=S; （13）P->priou ->next =S; （14）P->next->priou=p->priou; （15）Q=P->next; （16）Q=P->priou; （17）free(P); （18）free(Q); 2.7 简述以下算法的功能。

（1） Status A(LinkedList L) {//L是无表头结点的单链表 if (L&&L->next) {

Q=L; L=L->next; P=L; While (P->next) P=P->next; P->next=Q; Q->next=NULL; } return OK; }//A

答：如果L的长度不小于2，则将首元结点删去并插入到表尾。 （2） void BB(LNode *s, LNode *q) {

p=s;

while (p->next!=q) p=p->next; p->next=s; ]//BB

void AA(LNode *pa, LNode *pb) {

//pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); }//AA

答：将s至q之前的结点组成一个新的单循环链表，将q断开。

四、算法设计题

2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持