2008年11月程序员笔试考前练习（15）-深圳教育在线

　　阅读以下说明和C＋＋程序，将应填入(n)处的字句写在答题纸的对应栏内。
　　【说明】
　　设计一个类模板Sample用于对一个有序数组采用二分法查找元素下标。
　　【C＋＋程序】
　　#include<iostream．h>
　　#define Max 100∥最多元素个数
　　template<class T>
　　class Sample
　　{
　　T A［Max］：∥存放有序数序
　　int n：∥实际元素个数
　　public
　　Sample(){}∥默认构造函数
　　Sample(T a［］，int i)；∥初始化构造函数
　　int seek(T c)；
　　void disp()
　　{
　　for(int i=0；i<n；i＋＋)
　　cout<<A［i］<<""；
　　cout<<end1：
　　}
　　}；
　　template<class T>
　　Sample<T>：：Sample(T a［］，int i)
　　{
　　n=i；
　　for(intj=0；j<i；j＋＋)
　　(1) ；
　　}
　　template<class T>
　　int Sample<T>：：seek(T c)
　　{
　　int low=0，high=n-1，mid；
　　while( (2) )
　　{
　　mid=(low+high)／2；
　　if( (3) )
　　return mid；
　　else if( (4) )
　　low=mid+l；
　　else
　　(5) ；
　　}
　　return-1；
　　}
　　void main()
　　{
　　char a［］="acegkmpwxz"；
　　Sample<char>s(a，1。)；
　　cout<<"元素序列："；s．disp()；
　　cout<<"元素′g′的下标："<<s．seek(′g′)<<endl；
　　}
　　【答案】(1)A［j］=a［j］(2)low<=high(3)A［mid］==c(4)A［mid］<c(5)high=mid-1
　　【解析】在主函数中，首先由类模板实例化成Sample<char>模板类。(1)空所在处为构造函数的声明，将参数中的值赋值到类的成员变量中，所以(1)空应填入"A［j］=a［j］"。
　　成员函数seek()采用二分法查找元素下标，变量low和high分别表示查找区间的下标，如果查询到目标，则返回相应的下标，若没有查询到，则其结束的条件即(2)空的内容为"low<=high"。根据二分法的原理，当中间的元素恰好等于目标元素时，则返回其下标，所以(3)空应填入"A［mid］==c"；若中间的元素小于目标元素时，则mid+1作为新的查找区间的起始下标，所以(4)空应填入"A［mid］<c"；否则mid-1作为新的查找区间的结束下标，所以(5)空应填入"high=mid-1"。