2013秋学期数据结构-期未复习(成人2012)-参考答案(2)

五．算法题

typedef struct node { typedef struct node{ Elemtype data; int data; struct node *next; struct node *lchild,*rchild; }SLNode, *SLinkedList; }BTNode, *BiTree;

1. 阅读算法f un,并回答下列问题：

(1)设队列Q=(1，4，7，3，6，9)。写出执行算法fun后的队列Q; (2)简述算法fun的功能。

void fun(SqQueue &Q){ QElemType e; if (!QueueEmpty(Q)){ e=DeQueue(Q); fun(Q);

EnQueue(Q,e); } }

(1) Q=（9，6，3，7，4，1） (2) 将队列中的元素逆置

2. 下列算法利用折半查找方法在有序表L中插入元素x，并保持表L的有序性。请在空缺处填入合适的内容，使其成为一个完整的算法。 void BinInsert(SqList &L,ElemType x) { int low=1,high=L.length,mid,i; while(low<=high)

{ mid= (1) ; // (1)：（low+high）/2 if (x

else (2) ; //(2)：low=mid+1 }

for(i=L.length; (3) ;i--) //(3)：i>=low L.elem[i+1]=L.elem[i];

(4) ; //(4)：L.elem[low]=x; L.length++; }

3. 已知长度为n的线性表A采用顺序存储结构,并且每个数据元素均为一个无符号整数,请写一算法,删除线性表中的所有奇数。 void Delete_Odd(Sqlist &A) { i=0;

while(i

if(A.elem[i]%2 != 0 ) {

for(j=i+1;j

} //end of if else i++; }//end of while }//end

4. 已若二叉树采用二叉链表存储结构，请写出求该二叉树的高度的递归算法。

int High(BiTree T)//求二叉树中的深度 { if( !T ) return 0; //空树没有叶子 else {

lh=High(T->leftchild);//左子树高 rh=High(T->rightchild); //右子树高

return (lh>rh?lh+1:rh+1);//左右子树高度中较高者加1

}//High

5. 二叉树是指每个结点至多有2个子树，并且其子树有左右之分的一种树型结构。请编写算法计算二叉树T中度数分别为0、1和2的结点个数。

(1)只求叶子的：int leaf(BiTree T) (框架： 分) {{if( !T) return 0; //空树没有叶子 (指出空树情况： 分)

else if( !T->lchild && !T->rchild ) return 1; //如果是叶子结点 (指出叶子情况： 分) else return (leaf(T->lchild)+leaf(T->rchild) );//非叶子时为左右子树叶子之和(指出非终端结点情况： 分)

}// leaf

(2)三类结子同时求的，

void Count_node(BinaryTree r, int &no,int &n1,int &n2)

{ //调用之前，no,n1,n2均为0

if(r) // { if((r->lChild==NULL) &&(r->rChild!=NULL)) n0++;

if((r->lChild==NULL) &&(r->rChild!=NULL)) n1++; if((r->lChild!=NULL) &&(r->rChild==NULL)) n1++; if((r->lChild!=NULL) &&(r->rChild!=NULL)) n2++; count_node(r->lChild,n0,n1,n2); count_node(r->rChild,n0,n1,n2); }

}