发布时间 : 星期日 文章数据结构习题及答案更新完毕开始阅读
故该排序方法是不稳定的。例如，初始序列为8，5，5，按从小到大进行排序，则初始状态为：
调整为堆 输出5 调整为堆 输出5 显然，两个5的相对顺序发生了变化，所以是不稳定的。
五、应用题 1．（1）计算 的值。时间复杂性为O（n）。
（2）打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法项为i与j（i≤j≤n）的乘积。时间复杂性为O（n2）。
（3）使数组a[M，Ｎ]中的每一个元素均乘以ｄ的值。时间复杂性为Ｏ（M*N）。 2．顺序表Ｌ为：（15，12，8，5，50，30，5，8，12，15） 3．HL单链表所对应的线性表为：（12，26，8，15，30，50，9） 4．算法如下：
/* 从顺序表上统计出值为x的元素个数的算法*/
int Count（sqlist &L，datatype x）? { int i=0，j； for （j=0；j /*从单链表上统计出值为x的元素个数的算法*/ int Count（lklist &HL，datatype x） {node p=HL．Head—>next； int i=0； while（p！=NULL） {if（p—>data==x）i++； p=p—>next； } return； } 5．算法如下： /*从顺序表中删除具有给定值x的所有元素*/ void Deletel（sqlist &L．datatype x） {int i，j=0； while（i {if （L．data[i]==x） /*删除下标为i的元素*/ {for（j=i+1;j /*从单链表中删除具有给定值的x的所有元素*/ void Deletel（lklist &HL，datatype x） {node *p=HL．head； node *q； while（p—>next!=NULL） {q=p—>next； if （q—>data==x）/*删除p的后继结点，即q结点*/ {p—>next=q—>next； delete q； } else p=p—>next； } } 6 算法如下： / *从顺序表中删除所有其值重复的多余元素，使所有元素的均值不同*/ void Delete2（sqlist &L） {int i = 0; /* 每循环一次将删除data[i]后面与此值相同的所有元素*/ while （i while（j {if（L.data[j]= =L.data[i]）/*从顺序表中删除data[j]元素*/ {int k; for（k=j+1;k，L.last;k++） L.data[k－1]=L.data[k]; L.last――; } else j++; } i++; } } /*从单链表中删除所有其值重复的多余结点，使所有结点的均值不同*/ void Delete2（lklist &HL） {node *p=HL.head; /* p指向第一个结点*/ while （p!=NULL） {/*用t2指向待处理的结点，t2指向t2的前趋结点*/ node *t1=p，*t2=p－>next; /*此循环将从p后面的单链表中删除所有与p结点值相同的结点*/ while（t2!=NULL） {if（t2－>data= = p－>data） /*删除t2结点*/ {t1－>next=t2－>next; delete t2; t2=t1－>next; /*t2指向新的结点*/ } else /*指针后移，以便处理下一个结点*/ {t1=t2;t2=t2－>next; } } p=p－>next; /*p指向下一个结点*/ } } ７．第（1）列可以得到，操作过程为：Push（S，A），Push（S，B），Push（S，C），Pop（S），Push（S，D），Pop（S），Pop（S），Push（S，E），Pop（S），Push（S，F），Pop（S），Pop（S）。 第（2）个序列可以得到，操作过程为：Push（S，A），Pop（S），Push（S，B），Pop（S），Push（S，C），Push（S，D），Push（S，E），Pop（S），Pop（S），Push（S，F），Pop（S），Pop（S）。 第（3）个序列不可以得到，因为按照栈的后进先出或者称先进后出的原则，当A，B，C，D相继入栈，再进行两次出栈时，A＆B仍在栈中，此后只能B在A前面出栈，而在此序列中出现了A先于B出栈的情况，所以说此序列是错误的。 第（4）个序列不可以得到，因为在某一时刻，C和D同在栈中，并且D是栈顶，此后只能D先于C出栈，而在此序列中出现了C先于D出栈的情况，所以是错误的。 8．int SquareSum（int n） { if（n==0）return 0； else return n*n+Square（n-1）； } 9．递归算法如下： int Fib（int n） {if （n==1||n==2）return 1； /*终止递归条件*/ else return Fib（n-1）+Fib（n-2））；} 非递归算法如下： int Fib1（int n） {int a，b，c；/*c代表当前项，a和b分别代表当前项前面的第二项和第一项*/ a=b=1； if（n==1||n==2） return 1； else for（int i=3；i<=n；i++） {c=a+b； /*求出当前项*/ a=b； /*把前面第一项赋给前面第二项*/ b=c； /*把当前项赋给前面第一项*/ } return c； /*返回所求的第n项*/ } 10．插入操作的算法如下： void EnQueue（node *&rear，datatype &x）/*使新元素x的值插入到循环链队中*/ {node *newptr=new node；/*得到一个由newptr指针所指向的新结点*/ if（newptr==NULL） {printf（”Memory allocation failare！”）； exit（1）； } newptr—>data=x；/*把x的值赋给新结点的值域*/ if（rear==NULL） rear=newptr—>next=newptr；/*若链队为空，则新结点既是队首结点又是队尾结点*/ else {newptr—>next=rear—>next；/*使新结点的指针域指向队首结点*/ rear—>next=newptr； /*使队尾结点的指针域指向新结点*/ rear=newptr； /*使新结点成为新的队尾结点*/ } } } 删除操作的算法如下： datatype OutQueue（node *&rear） /*从循环链队中删除队首元素*/ {if（rear==NULL） {printf（”Linked queue is empty！”）； exit（1）； } node *p=rear—>next； /*使P指向队首结点*/ if（p==rear） rear=NULL；/*若链队中只有一个结点，则删除后队尾指针为空*/ else rear—>next=p—>data； /*使队尾结点的指针域指向队首结点的后继指针*/ datatype temp=p—>data； /*暂存队首元素*/ delete p； /*回收原队首结点*/ return temp； /*返回被删除的队首元素*/ } 11．/*当二叉树r中每个结点的左孩子的值大于右孩子的值时交换左右子树*/ void change（bitreptr r） { if （r！=NULL） { if（r—>lchild！=NULL&& r—>rchild！=NULL） if（r—>lchild—>data>r—>rchild—>data） {bitreptr t=r—>lchild； r—>lchild=r—>rchild； r—>rchild=t； } change（r—>lchild）； change（r—>rchild）； } } 12．/*统计出二叉树中等于给定值x的结点个数，该统计值由引用变量带回*/ void count1（bitreptr r，datatype x，int &k） {if （r！=NULL） {if（r—>data==x） k++； count1（r—>lchild，x，k）；