数据结构课后习题答案讲解.ppt

第一章习题讲解(3)for(inti=1;i<=n;i++)
for(intj=1;j<=i;j++)
for(intk=1;k<=j;k++)
x++;
划线语句的执行次数为n(n+1)(n+2)/6,渐近时间复杂度为O(n3)

(4）x=n;y=0;
while(x>=(y+1)*(y+1))y++;
划线语句的执行次数为n1/2,渐近时间复杂度为O(n1/2)2-4．Loc(A[i][j][k])=134+(i*n*p+j*p+k)*22-9.设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列

voidInvert(Telements[],intlength) //length数组长度
//elements[]为需要逆序的数组
{
Te;
for(inti=1;i<length/2;i++)
{
e=elements[i-1];
elements[i-1]=elements[length-i];
elements[length-i]=e;
}
}2-12.设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。
Node*pInvert(Node*first)
{
Node*p=first,*q;
first=NULL; while(p)
{
q=p->Link;p->Link=first;
first=p;p=q;
}
returnfirst;
}3-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。
（1）A，B，C，D，E3-1.设A，B，C，D，E五个元素依次进栈（进栈后可立即出栈），问能否得到下列序列。若能得到，则给出相应的push和pop序列；若不能，则说明理由。
（2）A，C，E，B，D（3）不能得到该序列，在C出栈时，A和B在栈中，A比B先进栈，所以B应比A先出栈。（4）能得到该序列。
相应的push和pop序列为：push(A);push(B);push(C);push(D);push(E);pop();pop();pop();pop();pop();第四章习题讲解intSearch_Insert(List*lst,Tx)
{inti,j;
for(i=0;(x>lst->Elements[i])&&(i<lst->Size);i++);
//查找首个大于等于x的元素位置，并记录在i中
if(lst->Elements[i]==x)
returni; //x在表中时，返回x的位置
if(IsFull(lst)) //或if(lst->Size==lst->maxList)
return-1; //表已满时，无法插入，返回-1
for(j=lst->Size-1;j>=i;j--)
lst->Element[j+1]=lst->Element[j];
lst->Element[i]=x; //新元素即插入位置i处
lst.Size++;
returni; //插入新元素并返回该元素的位置
}4-1.设线性表采用顺序表示方式，并假定顺序表是有序的（设表中元素已按非递减次序排列）。编写函数，实现线性表的如下运算：
（2）voidSearch_Delete(List*lst,Tx,Ty)
前置条件：x<y
后置条件：删除有序表中元素值在x和y之间（含x和y）的所有元素。voidSearch_Delete(List*lst,Tx,Ty)
{
if(lst->Size==0)
{printf(“Thelistisempty”); return-1;}
inti,j,sum=0;
for(i=0;temp[i]<x&&i<n;i++);
//找到首个大于等于x的元素位置i
if(i>n-1)return; //没有符合条件的元素
for(j=i;lst[j]<=y&&j<n;j++);
//找到首个大于y的元素位置j
sum=j-i;
while(j<n)lst[i++]=lst[j++]; //删除sum个元素
n=n-sum;
}4.6给出下列稀疏矩阵的行优先和列优先顺序存储的行三元组和列三元组表示。6-2.对于三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？6-3.设在度为m的树中，度为1，2，…，m的节点个数分别为n1,n2,…,nm，求叶子节点的数目。6-5.找出所有二叉树，其节点在下列两种次序下恰好都以同样的次序出现：
（1）先序和中序；（2）先序和后序；（3）中序和后序6-6.设对一棵二叉树进行中序遍历和后序遍历的结果分别为：（1）中序遍历（BDCE）A（FHG