发布时间 : 星期六 文章数据结构课程课后习题集答案解析更新完毕开始阅读
C.一定是不连续的 D.连续或不连续都可以 答：D
（6）一个线性表在（ ）情况下适用于采用链式存储结构。 A.需经常修改其中的结点值 B.需不断对其进行删除插入 C.其中含有大量的结点 D.其中结点结构复杂 答：B
（7）单链表的存储密度（ ） A.大于1 B.等于1 C.小于1 D.不能确定 答：C 2. 填空题
（1）在顺序表中插入或删除一个元素时，需要平均移动（ ① ）元素，具体移动的元素个数与（ ② ）有关。
答：①表中一半 ②表长和该元素在表中的位置
（2）向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动（ ）个元素。
答：n-i+1
（3）向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。
答：n-i
（4）在顺序表中访问任意一个元素的时间复杂度均为（ ① ），因此顺序表也称为（ ② ）的数据结构。
答：①O(1) ②随机存取
（5）顺序表中逻辑上相邻的元素的物理位置（ ① ）相邻。单链表中逻辑上相邻的元素的物理位置（ ② ）相邻。
答：①一定 ②不一定
（6）在带头结点的单链表中，除头结点外，任一结点的存储位置由（ ）指示。 答：其前驱结点的链域的值
（7）在含有n个数据结点的单链表中要删除已知结点*p，需找到它的（ ① ），其时间复杂度为（ ② ）。
答：①前驱结点的地址 ②O(n)
（8）含有n（n>1）个结点的循环双向链表中，为空的指针域数为（ ）。 答：0
3. 简答题
（1）试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：顺序存储结构中，相邻数据元素的存放地址也相邻，并要求内存中可用存储单元的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素
数据结构简明教程
时不方便。
链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？
答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。
（3）在链表中设置头结点的作用是什么？
答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。
（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？
答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。
对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。
（5）某含有n（n>1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。
①单链表；
②仅有头指针不带头结点的循环单链表； ③双链表；
④仅有尾指针的循环单链表。
答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。
在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。
在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。
在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。
4. 算法设计题
（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。 解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：
void reverse(SqList &L) { }
int i; ElemType x;
for (i=0;i x=L.data[i]; //L.data[i]与L.data[L.length-i-1]交换 L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=x; 本算法的时间复杂度为O(n)。 （2）设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 解：对于顺序表L，用i从1开始遍历其元素，设L.data[0..j]（j的初值为0）中没有重复的元素。检测L.data[i]（j void delsame(SqList &L) { } int i,j=0,k; for (i=1;i L.length=j+1; //顺序表长度置新值 k=0; while (k<=j && L.data[k]!=L.data[i]) { } k++; //表示L.data[i]和L.data[0..j]中所有元素都不相同 j++; L.data[j]=L.data[i]; if (k>j) //L为引用型参数 本算法的时间复杂度为O(n2)，空间复杂度为O(1)。 （3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data[0..0]，置e=L.data[0]，用i从1开始遍历L的所有元素：当L.data[i]≠e时，将它放在L.data[k]中，k增1，置e=L.data[i]，最后将L的length置为k。对应的算法如下： void delsame1(SqList &L) { int i,k=1; ElemType e; //L为引用型参数 //k保存不重复的元素个数 数据结构简明教程 } e=L.data[0]; for (i=1;i L.length=k; //顺序表长度置新值 if (L.data[i]!=e) { } k++; e=L.data[i]; //只保存不重复的元素 L.data[k]=L.data[i]; 本算法是一个高效算法，其时间复杂度为O(n)，空间复杂度为O(1)。如果每次遇到重复的元素，都通过移动其后所有元素来删除它，这样的时间复杂度会变成O(n2)。 （4）设计一个算法删除单链表L中第一个值为x的结点。 解：用p、q遍历整个单链表，p指向*q的前驱结点，q用于查找第一个值为x的结点，当找到后将*q结点删除，返回1；否则返回0。对应的算法如下： int delx(SLink *&L,ElemType x) { } SLink *p=L,*q=p->next; { } if (q!=NULL) { } else return 0; //未找到值为x的结点 free(q); return 1; //找到值为x的结点 p->next=q->next; p=q; q=q->next; //p指向*q的前驱结点 while (q!=NULL && q->data!=x) （5）设计一个算法判定单链表L是否是递增的。 解：判定链表L从第2个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下： int increase(SLink *L) { SLink *pre=L->next,*p; p=pre->next; { } return 1; while (p!=NULL) if (p->data>=pre->data) { } else return 0; pre=p; p=p->next; //若正序则继续判断下一个结点 //pre、p同步后移 //pre指向第一个数据结点 //p指向*pre结点的后继结点