2014湖北省分析数据库的考试题目入门

2014湖北省分析数据库的考试题目入门

1、给出折半查找的递归算法，并给出算法时间复杂度性分析。

2、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。

void PreToPost(ElemType pre[] ,post[],int l1,h1,l2,h2)

//将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。 {if(h1>=l1)

{post[h2]=pre[l1]; //根结点

half=(h1-l1)/2; //左或右子树的结点数

PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) //将左子树先序序列转为后序序列 PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) //将右子树先序序列转为后序序列 } }//PreToPost

32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

LinkedList head,pre=null; //全局变量

LinkedList InOrder(BiTree bt)

//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head

{if(bt){InOrder(bt->lchild); //中序遍历左子树

if(bt->lchild==null && bt->rchild==null) //叶子结点

if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点

else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表

InOrder(bt->rchild); //中序遍历左子树

pre->rchild=null; //设置链表尾

}

return(head); } //InOrder

时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)

3、对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。

int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0);

BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大

int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数 int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数

while(front<=rear)

{p=Q[++front];

if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点

if(p->lchild) Q[++rear]=p->lchild; //左子女入队

if(p->rchild) Q[++rear]=p->rchild; //右子女入队

if(front==last) {level++; //二叉树同层最右结点已处理,层数增1

last=rear; } //last移到指向下层最右一元素

if(level>k) return (leaf); //层数大于k 后退出运行

}//while }//结束LeafKLevel

第1页下一页