DS第二章课后习题答案

第二章 线性表

2.1 填空题

(1)一半 插入或删除的位置

(2)静态 动态 不一定 头结点的 next 前一个元素的 next

(3)一定 (4)头指针2.2 选择题 (1)A

(3)D (4)D (5) D 2.3

在不带头结点的链表中， 头指 头指针： 在带头结点的链表中，头指针存储头结点的地址；

针存放第一个元素结点的地址；

头结点： 为了操作方便， 在第一个元素结点前申请一个结点， 其指针域存放第一个元素结 点

的地址，数据域可以什么都不放；

首元素结点：第一个元素的结点。 2.4已知顺序表L递增有序，写一算法，将 X插入到线性表的适当位置上，以保持线性表的 有序

性。 void InserList(SeqList *L,ElemType x) {

int i=L->last; if(L->last>=MAXSIZE-1) return FALSE; //顺序表已满

while(i>=0 && L->elem[i]>x)

{

L->elem[i+1]=L->elem[i]

(2) DA GKHDA EL IAF IFA(IDA)

;

i--;

L->elem[i+1]=x;

L->last++; 2.5 删除顺序表中从 i 开始的 k 个元素

int DelList(SeqList *L,int i,int k) {

int j,l;

if(i<=0||i>L->last) {printf(\

Error!\

if(k<=0) return 1; /*No Need to Delete*/

if(i+k-2>=L->last) L->last=L->last-k; /*modify the length*/

for(j=i-1,l=i+k-1;llast;j++,l++) L->elem[j]=L->elem[l]; L->last=L->last-k; return 1;

}

O(n) 、空间复杂度

item 的数据元素。

2.6 已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为

为 O(1) 的算法，删除线性表中所有值为

[ 算法 1]

void DeleteItem(SeqList *L,ElemType item) {

int i=0,j=L->last; while(i

while(ielem[i]!=item)

i++;

while(ielem[i]==item)

j--; if(ielem[i]=L->elem[j]; }

i++; j--;}

L->last=i-1;

}

[ 算法 2]

void DeleteItem (SeqList *L,ElemType e) {

int i,j; i=j=0;

while(L->elem[i]!=e && i<=L->last) i++; j=i+1;

while(j<=L->last) {

while(L->elem[j]==e && j<=L->last) j++;

if(j<=L->last) {

L->elem[i]=L->elem[j]; i++; j++;

}}

L->last=i-1;

2.7 编写算法，在一非递减的顺序表 L 中，删除所有值相等的多余元素。要求时间复杂度为 0( n)，

空间复杂度为 0(1)。

void DeleteRepeatItem(SeqList *L) {

int i=0,j=1; while(j<=L->last) {

if(L->elem[i]==L->elem[j])

j++; else {

L->elem[i+1]==L->elem[j]; i++; j++;

}

}

L->last=i;

}

2.8 已知线性表中的元素(整数)以值递增有序排列，并以单链表作存储结构。试写一高效 算法，删除

表中所有大于 mink 且小于 maxk 的元素(若表中存在这样的元素) ，分析你的算 法的时间复杂度。

void DelData(LinkList L,ElemType mink,ElemType maxk) {

Node *p=L->next,*pre=L; while(!p && p->data <= mink) {pre=p; p=p->next;} while(p) {

//寻找开始删除的位置

if(p->data > maxk) break; else