欢迎来到天天文库
浏览记录
ID:43489033
大小:512.08 KB
页数:11页
时间:2019-10-08
《北京工业大学计算机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)
此文档下载收益归作者所有