北京工业大学计算机896数据结构考研真题答案2

《北京工业大学计算机896数据结构考研真题答案2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京工业大学《数据结构》考研题解答2010年算法设计1.递归计算二叉树的高度。【解析】没有太大难度，辅导时讲过的。递归程序注意先写好递归终止条件。intBinTreeHigh(BTreetree){if(tree==NULL)return0;else{intL=BinTreeHigh(tree->lchild);intR=BinTreeHigh(tree->rchild);return1+(L>R?L:R);//1+max{L,R}}}2.荷兰国旗问题。【解析】思路类似快速排序的一趟划分算法。要想按红白蓝顺序排列，只要扫描整个序列，遇到红色交换到前面，遇到蓝色交换到后面，设置两个变量

2、，分别记录前面和后面两个子序列的位置。（也可以想象在序列的前后两端各有一个栈。）[i,k]=323132311332=[j][k]==3交换[k][j],j--[i,k]=22313231133=[j]3[k]==2跳过：k++[i]=2[k]=2313231133=[j]3[k]==2跳过：k++[i]=22[k]=313231133=[j]3[k]==3交换[k][j],j--[i]=22[k]=31323113=[j]33[k]==3交换[k][j],j--[i]=22[k]=3132311=[j]333[k]==3交换[k][j],j--[i]=22[k]=1

3、13231=[j]3333[k]==1交换[k][i],i++,k++(这里k++防止i==k时死循环)1[i]=22[k]=13231=[j]3333[k]==1交换[k][i],i++,k++11[i]=22[k]=3231=[j]3333[k]==3交换[k][j],j--11[i]=22[k]=123=[j]33333[k]==1交换[k][i],i++,k++111[i]=22[k]=23=[j]33333[k]==2跳过：k++111[i]=222[k]=3=[j]33333[k]==3交换[k][j],j--(k==j时还要继续循环)111[i]=2

4、22=[j][k]=333333k>j结束【参考解答】设红、白、蓝分别用1、2、3表示。序列为线性结构，故采用线性表作为数据结构，针对该问题选择n个元素的数组作为线性表的存储结构。算法如下：//将n个红、白、蓝元素（分别用1、2、3表示）组成的序列//按照红、白、蓝的顺序排列voidArrange(inta,intn){inti=0;//从前向后保存红色（1）元素intj=n-1;//从后向前保存蓝色（3）元素intk=1;while(k<=j){if(a[k]==1){intt=a[k];a[k]=a[i];a[i]=t;//交换a[k]和a[i]i++;k++;//注意：这里k+

5、+防止i==k时陷入死循环}elseif(a[k]==3){intt=a[k];a[k]=a[j];a[j]=t;//交换a[k]和a[j]j--;}else{k++;}}}【补充】对于数据结构，最简单就是用数组表示线性表。如果非要复杂一点，可以用顺序表。【参考解答】设红、白、蓝分别用1、2、3表示。序列为线性结构，故采用线性表作为数据结构，针对该问题特点选择顺序表作为线性表的存储结构。算法如下：//顺序表最大容量constintMAX_SIZE=1024;//顺序表结构typedefstruct{intelem[MAX_SIZE];intlength;}SqList;//将n个红、

6、白、蓝元素（分别用1、2、3表示）组成的序列//按照红、白、蓝的顺序排列voidArrange(SqList&L){inti=0;//从前向后保存红色（1）元素intj=L.length-1;//从后向前保存蓝色（3）元素intk=1;while(k<=j){if(L.elem[k]==1){intt=L.elem[k];L.elem[k]=L.elem[i];L.elem[i]=t;//交换[k]和[i]i++;k++;//注意：这里k++防止i==k时陷入死循环}elseif(L.elem[k]==3){intt=L.elem[k];L.elem[k]=L.elem[j];L.e

7、lem[j]=t;//交换[k]和[j]j--;}else{k++;}}}2011年算法设计1、冒泡排序。【解析】本题考查冒泡排序，采用顺序表作为存储结构。要做到一旦发现待排记录有序就立即停止排序，只要在每趟排序过程中检查是否有交换发生，如果某一趟排序结束后，没有发生交换，则可以断定待排记录已经有序，则可以结束排序。本题难度不大，但要特别注意以下细节：（1）待排记录用顺序表存储，且r[0]空闲，这意味着待排序列为L.r[1..n]（n代表L.length）