清华大学计算机考试数据结构与程序设计试题（2）
有子女(当k=2)链接到其双亲结点上. 若遇到的是左括号”(“, 则表明子表的开始,将k置为1;若遇到的是右括号”)”, 则表明子表结果. 若遇到的是逗号”,”, 则表示以左子女为根的子树处理完
毕,应接着处理以右子女为根的子树, 将k置为2.
在算法中使用了一个栈s, 在进入子表之前,将根结点指针进栈, 以便括号内的子女链接之用. 在子
表处理结束时退栈. 相关的栈操作如下:
MakeEmpty(s) 置空栈
Push(s,p) 元素p进栈
Pop(s) 进栈
Top(s) 存取栈顶元素
的函数
下面给出了建立二叉树的算法, 其中有5个语句缺失. 请阅读此算法并把缺失的语句补上.
(每空3分)
Void CreateBinTree(BinTreeNode *&BT, char ls){
Stacks; MakeEmpty(s);
BT=NULL; //置二叉树
BinTreeNode *p;
int k;
istream ins(ls); //把串ls定义为输入字符串流对象ins
Char ch;
ins>>ch; //从ins顺序读入一个字符
While(ch!=”#”){ //逐个字符处理,直到遇到'#'为止
Switch(ch){
case’(‘: _______(1)_______
k=1;
break;
case’)’: pop(s);
break;
case’,‘: _______(2)_______
break;
default: p=new BinTreeNode;
_______(3)_______
p->leftChild=NULL;
p->rightChild=NULL;
if(BT==NULL)
_______(4)_______
else if (k==1) top(s)->leftChild=p;
else top(s)->rightChild=p;
}
_______(5)_______
}
}
七、下面是一个用C编写的快速排序算法. 为了避免最坏情况,取基准记录pivot采用从left,right
和mid=[(left+right)/2]中取中间值, 并交换到right位置的办法. 数组a存放待排序的一组记录,
数据类型为Type, left和right是呆排序子区间的最左端点和最右端点.
Void quicksort(Type a&#;,int left,int right){
Type temp;
If(leftType pivot=median3(a,left,right);
Int I=left, j=right-1;
For( ; ; ){
While(iWhile(iif(itemp=a[i]; a[j]=a[i]; a[i]=temp;
I++; j--;
}
else break;
}
if(a[i]>pivot)
{temp=a[i]: a[i]=a[right]; a[right]=temp;}
quicksort(a,left,i-1); //递归排序左子区间
quicksort(a,i+1,right); //递归排序右子区间
}
}
(1) 用C或Pascal实现三者取中子程序 median3(a,left,right); (5分)
(2) 改写 quicksort 算法, 不用栈消去第二个递归调用 quicksort(a,i+1,right); (5分)
(3) 继续改写 quicksort 算法, 用栈消去剩下的递归调用. (5分)