南邮数据结构课后习题课.ppt

1、习题课一,1.5 确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。,习题一（第18页）,(1) i=1; k=0; do k=k+10*i; i+; while(i=n-1),答： 划线语句的执行次数为 n-1 。O(n),(2）i=1; x=0; do x+; i=2*i; while （in）;,划线语句的执行次数为 log2n。O(log2n),(3) for(int i=1;i=n;i+) for(int j=1;j=i;j+) for (int k=1;k=j;k+) x+;,划线语句的执行次数为 n(n+1)(n+2)/6 。O(n3),(4）x=n;y

2、=0; while(x=(y+1)*(y+1) y+;,2.1 利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。,划线语句的执行次数为 。O( ),习题二（第37页）,#include #include seqlist0.h #include conio.h template void InterSection(SeqList ,2.1 利用线性表类LinearList提供的操作，涉及实现两个集合的交和差运算。,template void Difference(SeqList ,void main() SeqList LA(10),LB(10); for (int i

3、=1;i=8;i+) LA.Insert(i,i); for (i=1;i=3;i+) LB.Insert(i,i+3); InterSection(LA,LB); Difference(LA,LB); ,template void SeqList:Invert1() T temp; for (int i=0;ilength;i+) Find(length,temp);/得到序列的最后一个元素 Delete(length); Insert(i,temp); ,2.2 (2) 在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。利用类SeqList 提供

4、的操作直接实现,2.2 (2) 在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。,template void SeqList:Invert() T e; for (int i=0;ilength/2;i+) e=elementsi; elementsi=elementslength-1-i; elementslength-1-i=e; ,O(n),2.5 在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。,template void SingleList:in

5、vert() Node *p=first,*q; first=NULL; while (p) q=p-link; p-link=first; first=p; p=q; ,2.7 单链表中结点按元素值递增链接，在类SingleList中增加一个成员函数，直接实现删除结点值在a至b之间的结点(ab)。,template void SingleList:DeleteAb(T a,T b) Node *p=first,*q=first; while (p 思考结点a和b有没有删除掉？,习题三（第50页）,3.1 设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。若能得到，

6、则给出相应的push和pop序列；若不能，则说明理由。 1) A,B,C,D,E 2) A,C,E,B,D 3) C,A,B,D,E 4) E,D,C,B,A 答：2）和3）不能。对2）中的E，B，D而言，E最先出栈则表明，此时B和D均在栈中，由于，B先于D进栈，所以应有D先出栈。同理3）也不能。 (1)能。 push,pop,push,pop,push,pop,push,pop,push,pop (4)能。 push,push,push,push,push,pop,pop,pop,pop,pop,3.2 设计2个栈共享一个数组，画出示意图。,定义一个足够大的栈空间。该空间的两端分别设为两个栈

7、的栈底，用bottom1和bottom2指示，让两个栈的栈顶，用top1和top2指示，都向中间伸展，直到两个栈的栈顶相遇，才会发生溢出。 栈空，两栈均空：top1=0且 top2=n-1 栈满：top1=top2-1,写出下列表达式的后缀表达式： (a+b)/(c+d) ab+cd+/ b2-4*a*c b24a*c*-, 编程实现利用队列将栈中元素逆置的算法 template void invertstack(SeqStack ,4.1给出三维数组元素Aijk的存储地址loc(Aijk)。,习题四（第68页）,答： 设有三维数组声明为An1n2n3，每个元素占m个存储单元，则 loc(Ai

8、jk)=loc(A000)+m*(i*n2*n3+j*n3+k),4.5 给出下列稀疏矩阵的行优先和列优先顺序存储的三元组表。, 设计递归算法，对整数数组An， 求数组A的最大整数； 求数组A中n个整数的平均值。 /求数组的最大值 int Maximum(int a,int n) if (n=1) return a0; /数组只有一个元素时返回a0 else if (Maximum(a,n-1)an-1) return an-1; else return Maximum(a,n-1); /求数组的平均值 float Average(int a,int n) if (n=1) return fl

9、oat(a0); else return (Average(a,n-1)*(n-1)+an-1)/n; ,习题五（第81页）,5.2 设计一个递归算法，实现对一个有序表的顺序搜索。,template int SeqList:Search4(const T ,template int SeqList:Sch4(const T ,5.3 画出对长度为12的有序表进行对半查找的二叉判定树，并求等概率搜索时，成功搜索的平均搜索长度 解：1 二叉判定树如下：,成功搜索的平均搜索长度 由于第i层有2i个结点，故平均搜索长度为： ASL log2(n+1) /P.77,习题六（第107页）,6.2（2）对于

10、三个结点A，B和C，可分别组成多少不同的无序树、有序树和二叉树？ 答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵,6.4 求一棵二叉树的叶子结点个数； template int BTree:Leaves() int count=0; Leaf(root,count); return count; template void BTree:Leaf(BTNode* t,int 其中Leaves声明为public型，Leaf声明为private型。,6.4 设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 B D C E A F H G （2）后序遍历 D E

11、C B H G F A 画出该二叉树。 答：,6.5 写出图6-23的遍历结果。 先序：ADEHFJGBCK 中序：HEJFGDABKC 后序：HJGFEDKCBA,6.6（6） 设计算法，交换一棵二叉树中每个结点的左、右子树。,template void BTree:Exch(BTNode *p) if (p) BTNode *q=Exch(p-lchild); p-lchild=Exch(p-rchild); p-rchild=q; ,6.10 将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。,6.11 给出对图6-24中的树的先序遍历和后序遍历的结果。 答：先序：A，D，E，F，J，G，M，B，L，H，C，K 后序：J，G，F，E，D，M，H，L，K，C，B，A, 分别以下列数据为输入，构造最小堆。 80，10，70，20，60，30，50，40,WPL=(7