数据结构课本习题答案
数据结构
第⼀章绪论
⼀、单项选择题
1、（1）A（2）B
2、（1）B（2）D
3、C
4、A
5、A
6、（1）C（2）A
7、（1）C（2）A
8、C
9、C 10、B 11、D
⼆、填空题
1、存储结构、算法
2、⾮线性结构
3、线性、树型、图形
4、映射
5、线性结构、树型结构、图形结构
6、有穷性、确定性、可⾏性
7、错误
三、算法分析
1、（1）O(n）、(2)O(n) 、（3）O(n）、（4）O(n)、（5）O（n）、（6）O（log3n）、
（7） O（log2n）
2、(1) order()函数是⼀个递归排序过程，设T（n）是排序n个元素所需要的时间。在排序n个元素时，算法的计算时间主要花费在递归调⽤order()上。第⼀调⽤时，处理的元素序列个数为n-1，也就是对余下的n-1个元素进⾏排序，所需要的计算时间应为T(n-1)。⼜因为在其中的循环中，需要n-1次⽐较。所以排序n个元素所需要的时间为：
T(n)=T(n-1)+n-1 n﹥1
据此可得：T(1)=0
T(2)=T(1)+1=0+1=1
T(n)=T(n-1)+n-1 n﹥1
求解过程为：
T(n)=[T(n-2)+(n-2)]+n-1
=[T(n-3)+(n-3)]+(n-2)+n-1
=…
=(T(1)+1)+2+…+ n-1
=0+1+2+…+ n-1
=n(n-1)／2
=O(n2)
故order函数的时间复杂度为O(n2)
（2）解：设fact(n)数是T(n)。该函数中语句If (n≤1),return1；的运⾏时间是O（1），语句return(n*fact(n-1)); 运⾏时间是T(n-1）+O(1)，其中O(1)为乘法运算的时间。
因此
T(n)=O（1）n≤1
T(n)= T(n-1)+O(1) n＞1
则T(n)=O(1)+T(n-1)
=2*O(1)+T(n-2)
=…
=(n-1)*O(1)+T(1)
=n*O(1)
=O(n)
即fact(n)的时间复杂度为O(n)。
（3）解：设Fn的时间复杂度为T(n)，有：
T(n)=T(n-1)+T(n-2)＜2T(n-1)
＜22T(n-2)＜…
＜2n T(0)
=O（2n）
⼜：T(n)=T(n-1)+T(n-2)＞2T(n-2)
＞22T(n-4)＞…
＞22n T(1) （n为奇数时，或22n T(0)，n为偶数时）
即：T(n)＞O（22n）
则：O（22n）＜T(n) ＜O(2n)
取最坏情况上限，即T(n) = O(2n)。
第⼆章、线性表
⼀、单项选择题
1、A
2、B
3、C
4、A
5、D
6、D
7、D
8、B
9、B 10、C 11、A 12、A 13、
A 14、D 15、C 16、
数据结构与算法第二版课后题答案
B 17、B 18、D
⼆、判断题
1、F
2、T
3、F
4、F
5、F
6、F
7、F
8、F
9、F 10、F
三、填空题
1、顺序
2、n-1／2
3、p y→next=px→next; px→next=py;
4、n-i+1
5、（1）便于处理⾸元结点，使得在创建链表和删除结点时，可以将⾸元结点与其他结点同等对待。
（2）利⽤头结点的数据域存储链表的相关信息
6、O（1）O（n）
7、单链表和多重链表动态链表和静态链表
8、f→next=p→next; f→prior=p; p→next→prior=f; p→next=f;
9、指针
10、物理上相邻指针
四、简答题
1、（1）由于链式存储结构可以⽤任意的存储空间来存储线性表中的各数据元素，且其存储空间可以是
连续的，也可以是不连续，此外，这种存储结构对元素进⾏插⼊和删除操作时都⽆需移动元素，⽽仅仅修改指针即可，所以很适⽤于线性表容量变化的情况。
（2）由于顺序存储结构⼀旦确定了起始位置，线性表中的任何⼀个元素都可以进⾏随机存取，即存取速度较⾼；并且，由于线性表的总数基本稳定，且很少进⾏插⼊和删除，故这⼀特点恰好避开了顺序存储结构的缺点，因此，应选⽤顺序存储结构。
2、不⼀定，由于链式存储需要额外的空间来存储指针，所以要⽐顺序存储多占⽤空间。在空间允许的情况下，链式存储结构可以克服顺序存储结构弱点，但空间不允许时，链表存储结构会出现新的问题。
3、该线性表宜采⽤链表存储结构。因为采⽤链式存储结构的线性表，插⼊和删除操作只需要改变指针，时间复杂度为
O（1），⽽采⽤顺序存储结构的线性表插⼊和删除涉及到数据的⼤量移动，时间复杂度为O（n）
4、线性结构包括线性表、栈、队列、串，线性表的存储结构⼜分成顺序存储和链式存储。⽤C语⾔描述顺序存储类型：
Typedef struct
{
ElemType data[maxlen]; //存放元素
int len; //存放长度
}Sqlist;
链式存储类型：
Typedef struct node
{
ElemType data ; //数据域
struct node*next; //指针域
}SNode;
5、先到值为23和15的两个结点，q指向值为23 的结点，p指向值为15 的结点，p 和q结点互换：
q→llink→rlink=p; p→llink=q→llink;
p→rlink=q;q→llink=p; q→rlink!=null;
6、(1) p→rlink→llink=p→llink；
p→llink→rlink= p→rlink；
dispose (p) ;
(2) new (q);
q→llink=p;
q→rlink=p→rlink;
p→rlink→llink=q;
p→rlink=q;
五、算法分析
1、Void Insert (Lnode *head , ElemType x, ElemType y)
{
Lnode *q, p;
q = head;
p = q→next;
while(p→data!=x && p!=null)
{ q = p ;
p = p→next ;
}
if (p = = null)
p→next=s;
else s=( Lnode *) malloc(sizeof(Lnode ));
s→data=x;
s→next=p;
q→next=s;
}
2、Void getVoionList(SqList &A, SqList &B,SqList &C)
{ node pa, pb, pc, q;
pa=A→next; pb=B→next;
C = A;
A→next=null;
while (pa!=null && pb!=null)
{if (pa →data <= pb→data)
{q=pa; pa=pa→next;q→next=C→next; C→next=q;
} else
{ q=pb; pb=pb→next;q→next=C→next; C→next=q;
}
}
if (pa!= null)
{
while (pa!= null)
{ q=pa;pa=pa→next;q→next=C→next; C→next=q;
}
}
if (pb!=null)
{
while (pb!=null)
{q=pb; pb=pb→next ;q→next =C→next ;C→next =q;
}
}
}
3、State changeList (SqList &heada,SqList &headb,int i,int len int j) {node *a,*b ,p , q; a= heada ;b= headb;
count=1;
if(i= =1)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。