北理工数据结构作业5.doc

《北理工数据结构作业5.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章作业1、分别画出在线性表（a,b,c,d,e,f,g）中进行折半查找，以查关键字等于e、f和g的过程。(1)查e1):abcdefg↑low↑mid↑high此时de说明d若存在，必在区间[low,mid-1]令high=mid–1;3):abcdefghigh↑low↑mid此时mid指向的元素为e，查找成功;(2)查f1):abcdefg↑low↑mid↑high此时d

2、+1;2):abcdefg↑↑↑lowmidhigh此时mid指向的元素为f，查找成功;(3)查g1):abcdefg↑low↑mid↑high此时dh

3、igh)return0;else{mid=(low+high)/2;switch{cases.elem[mid].keyK:returnBinSearch(s,low,mid-1,K);break;default:;}//switch}//else}//BinSearch2、编写判别给定二叉树是否为二叉排序树的算法。假设此二叉树是以二叉链表的形式存储的，且树中关键字均不同

4、。typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;intflag=1,last=0; intBiSortTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 { if(T->lchild&&flag)BiSortTree(T->lchild); if(T->datadata与其中序前驱last比较大小 last=T->data; if(T->rchild&&flag)BiSortTree(T

5、->rchild); returnflag; }//BiSortTree实验四输入10个数，从插入排序、快速排序、选择排序三类算法中各选一种编程实现。程序如下（均为.cpp）插入排序：#include#defineMAXSIZE100#defineERROR0typedefstruct{intR[MAXSIZE+1];intlength;}SqList;voidInsertSort(SqList&L){//对顺序表L作直接插入排序inti,j;for(i=2;i<=L.length;++i)if(L.R[i]

6、[i];L.R[i]=L.R[i-1];for(j=i-2;L.R[0]

7、

8、n>MAXSIZE){printf("nmustmorethan0andlessthan%d.",MAXSIZE);returnERROR;}L.length=n;printf("inputtheelements:");fo

9、r(i=1;i<=n;i++)scanf("%d",&L.R[i]);InsertSort(L);printf("Sequenceaftersort:");for(i=1;i<=n;i++)printf("%4d",L.R[i]);}快速排序：#include#defineMAXSIZE100#defineERROR0typedefstruct{intR[MAXSIZE+1];intlength;}SqList;intPartition(SqList&L,intlow,inthigh){intp;L.R[0]=L.R[low