数据结构算法设计题复习题.doc

《数据结构算法设计题复习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计题1.设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。【答案】intcount=0;voidalgo2(BTNode*bt){if(bt){if(bt->lchild

2、

3、bt->rchild){printf(bt->data);count++;}algo2(bt->lchild);algo2(bt->rchild);}}2.阅读下列函数arrange()intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；whil

4、e(i=x)j--；while(i=x)i++；if(i

5、落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}}3.假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。【答案】voidalgo1(LNode*h,int

6、k,ElemTypey){q=h;P=h->next;j=1;while(p!=h&&jnext;j++;}s=(LNode*)malloc(sizeof(Lnode));s->data=y;q->next=s;s->next=q;}4.二叉排序树的类型定义如下：typedefstructBSTNode{∥二叉排序树的结点结构intdata;∥数据域structBSTNode*lchild,*rchild;∥左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。【答案】intf3

7、4(BSTreeroot){intcount;BSTNode*p;p=root;if(p&&p->datalchild);returncount;}5.设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左至右次序编号）【答案】BTNode*Firstleaf(BTNode*bt){InitQueue(Q);//初始化队列Qif(bt){EnQueue(Q,bt);;while(!EmptyQueue(Q)){DeQueue(Q,p);if(!p->lchild&&!

8、p->rchild)returnp;if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);}}}6.已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和孩子结点。【答案】intalgo2(charbt[],intn,intk){if(k<1

9、

10、k>n)return0;if(k==1)printf(“%cisaroot”,bt[1]);elseprintf(“%c’sparentis%c”,bt[k],bt[k/

11、2]);if(2*k<=n)printf(“%c’slchildis%c”,bt[k],bt[2*k]);elseprintf(“%cisnotlchild”,bt[k]));if(2*k+1<=n)printf(“%c’srchildis%c”,bt[k],bt[2*k+1]);elseprintf(“%cisnotrchild”,bt[k]));return1;}7.编写算法，将非空单链表hb插入到单链表ha的第i(0

12、>next;p=p->next);for(j=1,q=ha;j