数据结构答案a魏振钢 (2)

《数据结构答案a魏振钢 (2)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、期末考试试题参考答案科目名称：数据结构一、1.广义表为：list=（（（a,b,（）），（）），（a,（b）），（））长度为3深度为32、从顶点A到其他个顶点的最短路径及距离为：C:A>C15B:A>C>B19F:A>C>F25E:A>C>B>E29D:A>C>F>D293.①插入（20）后的3阶B-树如图所示。5010030150204012018080906070②再删除（150）后的3阶B-树如下图所示。80501009030401201808560704.初始堆为：90865389750346217051

2、22756187共4页第1页5.对应二叉树为：141513121110786543921二、答案：1．×2．√3．√4．×5．√6．√7．√8．×9．×10．×11．×12．√13．√14．×15．√三、答案依题意：设n为总的节点个数，n0为叶子结点（即度为0的结点）的个数，则有：n=n0+n1+n2+…+nm①又有：n-1=度的总数，即：n-1=n1*1+n2*2+…+nm*m②①-②式得：1=n0-n1-2n2-…-(m-1)nm则有：n0=1+n2+2n3…+(m-1)nm=1+ni共4页第2页四、思想：调

3、用一趟快速排序以后，有P-1(P：轴元素位置)个元素小于等于轴元素，且n-P个元素大于等于轴元素，若KP，则A(1..n)中的第K个最小元素就是A(P+1..n)中的第（K-P）个最小元素。PROCEDUREqpass(R:listtype;lqw,hig:integer;vardivinteger）Begini=low;j:=hig;x:=R[I];whileIx)doj:

4、=j-1R[i]:=R[j];While(i

5、k-p,key)]End.五、解答：为判定二叉树是否为二叉排序树同样是建立在中序遍历的框架基础下，遍历中附设一指针pre指向当前访问结点的中序直接前驱，每访问一个结点便比较前驱结点pre和此结点是否有序，若遍历结束后各结点和其中序直接前驱均满足有序，则此二叉树为二叉排序树；否则只要有一个结点不满足，那么此二叉树就不是二叉排序树。共4页第3页VoidBisortTree(BiTreeT,BiTree&pre,bool&flag){//初始时pre＝NULL，flag＝true；若结束时flag为true，则此二叉树

6、是二叉排序树if(T&&flag){BiSortTree(T->lchild,pre,flag);If(pre==NULL){//访问中序序列的一个结点，不需要比较Flag=true;Pre=T;}else{//比较T与中序直接前驱pre的大小，这里假定没有相同的关键字if（pre->keykey）{//pre与T有序flag=true;pre=T;}elseflag=false;//pre与T无序}BitSortTree(T->rchild,pre,flag);}}//endBiSortTree共4页第

7、4页