数据结构课后习题答案(1~5章).pdfVIP

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

精品文档

第1章绪论

5．选择题：CCBDCA

6．试分析下面各程序段的时间复杂度。

（1）O（1）

（2）O（m*n）

2

（3）O（n）

（4）O（logn）

3

2

（5）因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n）

（6）O(n)

第2章线性表

1．选择题

babadbcabdcddac

2．算法设计题

（6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

ElemTypeMax(LinkListL){

if(L-next==NULL)returnNULL;

pmax=L-next;//假定第一个结点中数据具有最大值

p=L-next-next;

while(p!=NULL){//如果下一个结点存在

if(p-datapmax-data)pmax=p;

p=p-next;

}

returnpmax-data;

（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表

的存储空间。

voidinverse(LinkListL){

//逆置带头结点的单链表L

p=L-next;L-next=NULL;

while(p){

q=p-next;//q指向*p的后继

p-next=L-next;

L-next=p;//*p插入在头结点之后

p=q;

}

.

乐民之乐者，民亦乐其乐；忧民之忧者，民亦忧其忧。——《孟子》

精品文档

}

（10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间

复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。

[题目分析]在顺序存储的线性表上删除元素，通常