int N;int * pQueenPos; void NQueen( int n) { int i; if( n == N ) { for( i = 0; i < n;i ++ ) cout << pQueenPos[i] + 1 << \" \"; cout << endl; return ; }
11
for( i = 0;i < N;i ++ ) { for( int j = 0; j < n; j ++ ) { if( pQueenPos[j] == i || abs(pQueenPos[j] - i) == abs(n-j)) { break; } } if( j == n ) { _________________; _________________; } } }
main() { cout << \"Please input the queen number:\"; cin >> N; cout << \"The solutions are: \" << endl; pQueenPos = new int [N]; NQueen(0); delete []pQueenPos; }
2) (8分)
下面的程序用枚举法解决如下问题,请填空。
平面上的一个矩形,如果其边平行于坐标轴,我们就称其为“标准矩形”。给定不重复的 n 个整点(横、纵坐标都是整数的点),求从这n个点中任取4点作为顶点所构成的四边形中,有多少个是标准矩形。
输入数据:
第一行是点的数目
其后每一行都代表一个点,由两个整数表示,第一个是x坐标,第二个是y坐标
输出要求:
输出标准矩形的数目
12
输入样例: 6 2 3 2 5 4 5 4 4 2 4 4 3
输出样例: 3
#include #include #include using namespace std; struct Point { int x; int y; Point( int x_,int y_):x(x_),y(y_) { } };bool operator < ( const Point & p1, const Point & p2) { if( p1.y < p2.y ) return true; else if( p1.y == p2.y ) return p1.x < p2.x; else return false; }
main() { int t; int x,y; cin >> t; vector v; while( t -- ) { cin >> x >> y;13
}
3) (6分)
下面的程序输出结果是: (4,5) (7,8)
请填空
#include class Point { private: int x; int y; public: Point(int x_,int y_ ):x(x_),y(y_) { }; __________________________________________________; };____________ operator << ( ________________, const Point & p) { ___________________________________; return _________________; }
v.push_back(Point(x,y)); }
_____________________; vector::iterator i,j; int nTotalNum = 0;for( i = v.begin(); i < v.end() - 1;i ++ ) for(___________; ______________; _____________) { if(binary_search( v.begin(),v.end(),Point( j->x, i->y)) &&
___________________________________________ && ____________________________________________ && ______________________________________________ )
nTotalNum ++; }
cout << _________________;
14
main() { cout << Point(4,5) << Point(7,8);
}
4) (4分)
下面的程序输出结果是:1 2 6 7 8 9 请填空
main() { int a[] = {8,7,8,9,6,2,1}; ___________________; for( int i = 0;i < 7;i ++ ) ___________________; ostream_iterator o(cout,\" \"); copy( v.begin(),v.end(),o); }5) (3分)
下面的程序输出结果是: A::Fun A::Do A::Fun C::Do
请填空
#include class A { private: int nVal; public: void Fun(){ cout << \"A::Fun\" << endl; }; virtual void Do() { cout << \"A::Do\" << endl; } };
15
class B:public A { public: virtual void Do() { cout << \"B::Do\" << endl;} };
class C:public B { public: void Do( )
{ cout <<\"C::Do\"<{ cout << \"C::Fun\" << endl; } };void Call(____________) { p->Fun(); p->Do(); }
main() { Call( new A()); Call( new C()); }
6) (6分)
下面的程序输出是:TomHanks
请填空。注意,不允许使用任何常量。 #include #include using namespace std; template class myclass { _________; int nSize; public: myclass ( ______________, int n) { p = new T[n]; for( int i = 0;i < n;i ++ ) p[i] = a[i]; nSize = n; }16
~myclass( ) { delete [] p; } void Show() { for( int i = 0;i < nSize;i ++ ) { cout << p[i]; } } };
void main() { char * szName = \"TomHanks\"; myclass obj(_________________________); obj.Show(); }7) ( 4 分)
下面程序的输出结果是: 5*3*4*2*1* 1*2*3*4*5* 1*2*9*4*5*
请填空
using namespace std; template class MyClass:public list {public: ____________________ (int n) { iterator i; int k = 0; for( ____________________________) { if( k == n) return _______________; k ++;
17
} } MyClass(int n):___________________ { } }; main() { MyClass obj(5); int a[] = { 5, 3, 4, 2,1 }; copy( a, a + 5, obj.begin()); ostream_iterator output(cout,\"*\"); copy( obj.begin(),obj.end(),output); cout << endl; obj.sort(); copy( obj.begin(),obj.end(),output); cout << endl; obj[2] = 9; copy( obj.begin(),obj.end(),output);}四、编程题(14分)
1.(6分)下面的程序输出结果是: 5,5 4,4 8,4
请补足class B中缺失的部分。要求补足的部分都必须都是class B的成员,而且class B最多只能有一个构造函数
#include using namespace std; class A { public: int i; A(int n):i(n) { }; };class B :public A{
18
public: int nVal; ………………….. }; main() { B b1,b2(4); cout << b1.nVal<< \cout << b2.nVal<< \ b1 = b2; cout << b1.nVal<< \}
<< endl;
<< endl; << endl; 19
2. ( 8分)
写一个自己的 CMyostream_iterator 模板,使之能和 ostream_iterator 模板达到一样的效果,即 #include #include #include using namespace std; main(){int a[5] = {1,2,3,4,5};
CMyostream_iterator output(cout,\"*\"); vector v(a,a+5);copy(v.begin(),v.end(),output); }
程序的输出结果是: 1*2*3*4*5*
注意,编写CMyostream_iterator时不能使用 ostream_iterator ,假定所有需要的头文件都已经包含。
20
考试科目:程序设计实习(B卷) 考试时间2007年6月
题 一 号 分 数 阅卷人 二 三 四 五 六 七 八 九 十 总分
1. POJ上的1013是称硬币问题,有12枚硬币,其中1枚是假币,根据三
次称量的结果,判断哪枚硬币是假币,数据保证有唯一解。请遵照原题的本意回答:测试数据中可否出现这样的测试数据 ABCD EFGH even, ABCD EFJK up, ABEF EFJK up?
2. 2007年1月1日是周一,现在已知今天是2007年第n天,请写出一个
函数返回今天是星期几(周一到周日分别为数字1- 7)。
3. 在作业POJ1565中,我们实现了一段把二进制串转换为十进制数的程
序。现假设char a[]中存储了0,1字符(非0,1数字),请补全下面的代码。 …
#define MAXLENGTH 100 char a[MAXLENGTH];
cin>>a; //输入二进制字符串,不超过99字符长 int number = 0;
int length = strlen(a);
for(int i = 0; i < length ; i++) {
21
}
cout<4. 在讲到链表的时候,留了一道POJ2746作业题,该题大意是有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再重新报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。题目要求使用循环链表,现假设链表每一个节点都代表一个猴子,如不能使用额外的变量存储剩下的猴子的数量,请问应该如何设计程序使得程序在选出猴王时候终止。
5. POJ上1222的熄灯问题,以及一道类似的作业POJ1166画家刷墙的问
题,在问题中每一刷都会影响到自己和周围的方格。在解该题时,我们采用了哪一种编程思想?
6. 在讲到递归方法时,我们讲了POJ2753菲波那契数列的例题,请补全
求数列中第n个数的递推函数。(n >= 1) int f( int n) {
}
7. 我们在第六讲时,曾经做过一个时钟问题的题目1166。
在这个题目中有一个拨钟的动作是ABDE,请问给定如下图的输入情况,使用拨钟动作ABCD两次,时钟会变成什么样子。用一个由9个数字组成的序列表示结果。其中,0表示12点, 1表示3点, 2表示6点, 3表示9点。例如右图的时钟序列表示为330222212。
22
8. 我们在第六讲中曾经做过一道滑雪的题目1008,大体意思是:有一个
二维的数组表示雪地的高度,要你在这个二维空间中找到一个最长的下降路径(4连通)。请你简述一下你的解题思路。
9. 在第13讲类和对象后,留了书上作业 6.15写一个大整数类
HugeInteger, 要求在该类中给出一些比较对象的成员方法,例如:isEqualTo, 请写出你所实现的isEqualTo的函数。
10. 在第14讲运算符重载后,留了一个作业写一个大整数类,并重载一些
运算符,使得给定的一段程序可以正常运行。在下面给定的程序段中,为使得注释处语句能实现其功能,请写出其对应的函数(包括函数实现)。
void main(){
hugeInt a(\"123454543634242435435436529834234235\"); hugeInt
b(\"3453555623234576669567601199439201990001356\"); hugeInt temp;
float f;
temp = a * 436; temp++;
cin>>temp>>f;//输入大整数,再输入一个浮点数 }
23
11. 第15讲继承过后,留了一个作业几何形体练习1 - 编写一个程序,计
算任给一个几何形体的面积和周长。几何形体可以是矩形、三角型、圆形、扇型、梯形。这个题目是否要有用户界面,如果有,你的用户界面是什么样的?
12. 在第16讲后,留了一个作业几何形体练习2 – 要求在几何形体练习
1的基础上,对用户输入的全部几何形体按照面积从小到大进行排序,并输出排序的结果。假定几何形体的数量不超过100。几何形体练习2与几何形体练习1相比,用到了哪些不同的面向对象的技术。
13. 在第17讲几何形体练习3中,几何形体在文件中的存储格式是什么?
(举出两个几何形体的存储格式, 顺序不限)。
14. 在第18讲作业中的压缩算法设计中,我们接触过一种压缩算法RLE,
请简述其大致思想,该算法是否保证将文件压缩得更小?
24
15. 在第19讲后,留了书上20.14作业,编写一个函数模板palindrome, 取
const vector参数并根据vector是否正向逆向都一样而返回true或false。假设一样返回true,不一样返回false。补全下面函数模板。 template bool palindrome(vector &temp) {vector::iterator i;vector::reverse_iterator j;for(i = temp.begin(), j = temp.rbegin(); i != temp.end() && j !=temp.rend(); i ++, j ++){ }
return true; }
16. 在第20讲后,留了一个过滤单词的程序,in1.txt ,in2.txt 都是纯
文本文件,每行一个英文单词,最多可能有二十万行,一个单词长度最多可以有2000个字符。要求编程输出out.txt,out.txt里是in2.txt里有,而in1.txt里没有的单词,每个单词一行。单词不分大小写 。在这个程序里,你是如何存储单个单词的?
17. 在第21讲后,作业要求写一个自己的 CMyostream_iterator 模板,
题目要求它和哪个模板达到一样的效果?你在做这个题目中遇到过哪些问题?
18. 本学期所有作业中,有哪些作业是你完成的?哪些是在同学的帮
助下完成的?哪些是在助教的帮助下完成的?
25
19. 你觉得教材还有哪方面需要改进?
20. 你觉得课堂授课和助教最需要改进的地方是什么?
26